Protocol-Design
如何使用缺乏知識的證明?
這是一個純粹假設的例子,但可證明的無知在密碼學中有用嗎?
例如,假設我有一個活板門防碰撞功能。我知道活板門,因此有些 $ x_0 \neq x_1 $ 這樣 $ f(x_0) = f(x_1) $ . 然而,這很難找到。如果有人證明他們知道 $ x_0 $ , 我可以斷定他們不知道 $ x_1 $ .
有沒有這樣的問題的更複雜版本有用的上下文?
一般來說,你不能證明缺乏知識,因為即使你知道了一些你不應該知道的事情,你也可以假裝不知道,假裝不知道一樣進行證明。
對於您的具體範例,請考慮證明者如何知道 $ x_0 $ . 你告訴他們那是什麼嗎?如果是這樣,那證明不了,因為他們會知道 $ x_0 $ 即使他們也學會了 $ x_1 $ 從別的地方。
相反,如果你的函式 $ f $ 在沒有陷門的情況下是抗碰撞的,但不是單射的(即確實存在潛在的碰撞),那麼它也必須是抗原像的。因此,發現 $ x_0 $ 從 $ y = f(x_0) $ (至少)和尋找一樣難 $ x_1 $ . 因此,矛盾的是,證明者展示了 $ x_0 $ 實際上將是他們可以找到原像的證據 $ f $ ,因此可能會找到 $ x_1 $ 也是。