好像離版題遠了些 不過有人問到了這個 所以回個文 ※ 引述《joeyeh (joe)》之銘言： : 推 aegius1r:可以解釋一下零知識嗎@"@? 10/16 23:15 所謂"零知識證明" 是指一個人P宣稱他知道某件事 他想說服另一人V說他知道某件事 但不想告訴V有關這件事的細節 P所用來向V證明的方法(或說兩人之間的互動過程)就叫"零知識證明"(或稱零知識協定) 這證明要成立有三個條件: (1) 完整性: 如果P果真知道這件事 那照這個方法做的V會被說服P的確知道 (2) 健全性: 如果P其實不知道這件事 那照這個方法做的V除了極小的機率之外都可以抓包 (3) 零知識性: 如果P果真知道這件事 那V除了知道「P知道這件事」是真的之外一無所知 (包含所謂"這件事"的細節) 我在前篇推文說要應用在「難」的問題上是表示說 V不會由證明的過程推出P所知道的東西是什麼 (從而知道了V不該知道的東西) 例如: (這是英文維基上的例子) 現在有一個洞窟 裡面岔成兩條路 在後面連起來 但有一個魔法門隔開 P現在宣稱他知道怎麼開這個魔法門 他想在不告訴V怎麼開門的情形下說服V 這裡 「開魔法門」就是那個「難」的問題的類比 P和V都知道有魔法門 但只有P知道怎麼開 這個"零知識證明"如下: 首先 P先進洞 V在外面 然後P隨機選一條岔路進去 接著V進來 大喊著要P從哪條路出來(也是隨機選) 看看P是否真的從那條路出來 重覆這個過程至少十幾二十次 如果P每次都能照所喊的出來 那"P知道怎麼開門"這件事就非常有可能是真的 因為如果P知道 那P一定可以每次都照所喊的路走出來 如果P不知道的話 他只會有1/2的機率猜中答案從所喊的路走出來 因此如果真不知道 重覆20次都猜中的機率就是一百萬分之一了 符合條件(2) 因此在夠多的次數之下 V會被說服P的確知道怎麼開門 符合條件(1) 而且這過程中 V完全不會知道這門怎麼開 他除了"P知道怎麼開門"之外什麼都不知道 符合條件(3) --- 這東西的用途主要是在密碼學 P要向V證明他有某個東西(例如RSA的密碼) 但不能給V知道這個東西是什麼 他就可以用和這個類似的過程來向V證明 --- 上面說的只是概念 尤其條件(3)裡所謂"除此外什麼都不知道"是個滿抽象的詞 是有個定義來定性描述這件事 不過我還沒搞懂 @_@ -- 実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」 亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」 実琴：「難道你沒有男人的尊嚴了嗎?!」 亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」 －－プリンセス・プリンセス 第二話 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.250.80