請問有人知道關於各類魔方的零知識嗎? - 拼圖

好像離版題遠了些

不過有人問到了這個 所以回個文

※ 引述《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)裡所謂"除此外什麼都不知道"是個滿抽象的詞

是有個定義來定性描述這件事 不過我還沒搞懂 @_@

--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話

--