Complexity

外部匿名調查的紙筆單向功能

  • October 10, 2018

進行調查時,管理員可能會派一名調查員對受訪者進行調查。對於“敏感”問題(例如關於令人尷尬的行為),答辯人可能會接受向管理員透露真相而不是向普查員透露真相。

有沒有一種方法可以使用簡單(小而便宜)的物理對象(例如筆和紙)來創建單向函式/過程,並且不會太耗時或涉及復雜的數學?在調查期間或調查之後,對 Enumerator 來說反轉函式太難了,但管理員可以稍後再做。假設 Enumerator 可以快速做任何事情來發現答案(例如“不小心”打開一個密封的信封或聲稱非隨機數據是隨機的),只要管理員最終得到真實的答案。假設這是與調查的唯一互動,因此管理員和受訪者之間沒有傳遞任何秘密資訊。僅供參考:以前的問題包括關於非電腦/手動完整密碼系統密碼的問題,但兩者的答案都需要很長時間才能執行。

默克爾拼圖!

管理員建構了 676 個獨特的驗證碼,上面覆蓋著隨機字母,如下所示:

默克爾驗證碼

底部的圖片實際上是幼崽,而不是小貓。在現實生活中,管理員會使用更具挑戰性的驗證碼。他會在每個關鍵字母上使用一張圖片。

普查員遞給答辯人一袋驗證碼。當 Enumerator 沒有看時,Respondent 抓取一個隨機驗證碼並通過寫下覆蓋正確塊的所有字母並忽略不正確塊上的字母來解決它。

該字元串是 Respondent 的密鑰。

然後,受訪者使用直板計算密鑰的兩個字元校驗和。管理員必須確保每個密鑰都有唯一的校驗和。

再次使用直板,受訪者用他們的密鑰加密他們對調查的敏感答案,並用密鑰的校驗和標記他們的密文。

然後,他們將驗證碼扔回袋子中,並將其與加密響應一起交給 Enumerator。

列舉器將加密的消息(標有密鑰校驗和)傳遞給管理員。管理員有一個秘密校驗和密鑰查找表,這使他能夠快速查找任何標有給定校驗和的密文的正確密鑰。

列舉員在相對較短的時間內解密所有受訪者的敏感回复的唯一方法是讓一組人員處理驗證碼。這是他做不到的,除非他有很好的人脈或者有很多錢可以花。

引用自:https://crypto.stackexchange.com/questions/8482