執行並發零知識協議的不誠實驗證者
假設 Alice 和 Bob 參與了圖 3 著色性零知識協議，其中 Alice 置換著色 $ \varphi:V\rightarrow {1,2,3} $ 對於圖表 $ G(V,E) $ ，然後發送每個頂點的承諾 $ v $ , $ {\pi(\varphi(v))}_k $ 給鮑勃。然後 Bob 隨機選擇該圖的一條邊，Alice 向其打開相應頂點的承諾。最後 Bob 驗證了 edge $ (i,j) $ , $ \pi(\varphi(i))\neq\pi(\varphi(j)) $ . 然後他們迭代這個過程 $ |E|^2 $ 直到 Bob 以高機率確信 Alice 確實知道圖的 3 色。
這在 Goldreich、Micali 和 Wigderson 中有所體現
$$ 1991 $$滿足完整性、健全性和零知識。但是，如何阻止不誠實的驗證者執行並發協議，就像中間人攻擊一樣，以使某些第三方相信他們知道著色？ 假設 Alice 讓 Bob 相信她知道 3 種顏色，而 Bob 讓 Charlie 相信他知道相同的 3 種顏色。Bob 只是將收到的來自 Alice 的每條消息傳遞給 Charlie，反之亦然。按順序執行的操作如下所示：
- $ A\rightarrow B: {\pi(\varphi(v_1)}{k_1},…,{\pi(\varphi(v_n)}{k_n} $
- $ B\rightarrow C: {\pi(\varphi(v_1)}{k_1},…,{\pi(\varphi(v_n)}{k_n} $
- $ C\rightarrow B: (i,j) $
- $ B\rightarrow A: (i,j) $
- $ A\rightarrow B: (k_i,k_j) $
- $ B\rightarrow C: (k_i,k_j) $
那麼這怎麼不違反健全性呢？因為 Bob 不知道 3-coloring $ G(V,E) $ 但他能夠以很高的機率說服查理他做到了。我的想法是零知識協議應該像 Deniable Authentication 簽名一樣工作，但是我很難找到解決這種針對 ZK 協議的攻擊的文獻。如果它不違反健全性，那麼解釋或引用為什麼會非常有幫助。
互動式（零知識）證明的健全性定義表明，除了極小的機率外，沒有證明者可以說服驗證者相信*虛假陳述（即，不在相關語言中的陳述）。*在你的“Bob in the middle”場景中，這個陳述是正確的——圖表是 3 色的——所以如果“Bob”通過傳遞消息（或任何其他策略）來證明它，則不會違反可靠性。
一個單獨但相關的屬性是知識證明，它非正式地表示任何成功說服驗證者（具有足夠大的機率）的證明者必須“知道”正在證明的陳述的證人——在這種情況下，為有問題的圖表。（這個“知道”是通過為證明者設計一個提取器來形式化的。）重要的是，在這個屬性的形式化中，證明者只能與驗證者互動；它不能“打電話給朋友”尋求幫助。因此，鮑勃本身不會被認為是一個證明者可以說服驗證者，因此對於我們可以從 Bob 那裡提取什麼沒有任何要求。相比之下，Bob 和 Alice 作為“聯合實體”將有資格成為成功的證明者，但該聯合實體確實知道證人，因此與定義沒有矛盾。
有更強大的健全性和知識證明概念，允許證明者擁有更多權力，例如，與其他實體就其他陳述進行互動的能力、“重置”驗證者的能力等。這些有各種名稱，如並發、非延展性和可重置的穩健性。您的場景與不可延展性最相關，除了 Bob 根本沒有更改中繼的消息，這是我們永遠無法阻止的。不可延展性基本上是說這種直接複製是對手能夠成功的唯一途徑。