zero knowledge prove - 0知識證明

zero knowledge prove

0知識證明: 神經病的理論cs學家想的

很有趣

A要如何證明某件事情給B

但是B 無法得到任何有用的資訊 B 不知道為什麼，但A 可以convince B

假設有兩個graph 點很多 邊很多 超級大 兩個graph點個數一樣

B 想要證明 兩個graph 是non isomorphic 也就是不能透過重新編排 使得兩圖一樣 直接證明很困難

但現在A 跟B 說 : 你隨機選一個圖，然後隨機排列這些點，你把圖給我，我可以告訴你，你是從哪一張圖開始的

如果 兩圖一樣，那A 只有1/2機會猜中

如果 兩圖不一樣，A 總是成功，那B就會相信這兩張圖不一樣

但他媽他就是不知道為什麼不一樣，他還是看不出來。

也就是這個動作執行夠多次，A 就有辦法convince B such that 兩張圖不一樣。但是B什麼資訊都沒有得到。如果B想要更確定，可以執行這動作200次。這樣A 全部猜中機率就是1/2^200 趨近於0

如果A總是猜對。B就可以被說服。

實際上 所有數學證明都可以轉成這種形式。所以

你可以證明某事情給我，但我永遠不知道為什麼，不知道你怎麼證明的。

人間相