Re: [請益] 請問有人知道關於各類魔方的零知識嗎?

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 ((short)(-15074))時間17年前 (2008/10/17 01:34)推噓3(3推 0噓 9→)

留言12則, 4人參與討論串2/2 (看更多)

好像離版題遠了些不過有人問到了這個所以回個文 ※ 引述《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