在不公開雜湊的原像的情況下證明它的知識？
我們考慮一個公共雜湊函式 $ H $ ，假定抗碰撞和抗原像（對於第一和第二原像），在結構上類似於 SHA-1 或 SHA-256。
愛麗絲公開了一個價值 $ h $ ，聲稱她（或/和她可以與之通信的各方或/和他們有權訪問的設備）知道一條消息 $ m $ 這樣 $ H(m)=h $ . 某些協議能否在沒有 Bob 信任的第三方/設備的幫助下，也不允許 Bob 找到的情況下說服 Bob 這個聲明？ $ m $ ?
在 Crypto 98 臀部會議上，Hal Finney 做了一個 7 分鐘的展示，一個零知識證明擁有一個似乎是為此而設計的 SHA-1 雜湊的前映像。這個顯著的結果偶爾會被說成是事實，包括最近的 here和nextdoor。但我不明白它應該如何工作。
更新：本演講提到使用 Ronald Cramer 和 Ivan B. Damgård 的 Crypto'98 論文中的協議：有限域算術的零知識證明或：零知識可以免費嗎？（這個版本非常相似，或者有這個更早，更長的版本）。
是的，NP 中的所有陳述都有一般的零知識證明。
這一結果可以追溯到1986 年 Oded Goldreich、Silvio Micali 和 Avi Wigderson 的一篇論文。基本思想是為圖 3 著色給出一個零知識證明，它是 NP 完全的，即 NP 中的所有其他語句都可以在其中編碼。
和聲明 $ \exists m. H(m) = h $ 顯然是一個 NP 語句：如果你有 $ m $ ，您可以在多項式時間內檢查語句（通過計算散列函式）。
不過我們需要小心一點。你要求的不僅僅是一個零知識證明，而是一個“知識的零知識證明*”，*因為證明者想要證明的不僅僅是這樣一個 $ m $ 存在，但它也“知道”一個。但是這個問題也可以解決（參見下面第三個教程中的第 7 節）。
如果您有興趣了解零知識證明，我推薦這三個教程，它們明確考慮了 NP 語句的一般證明（按技術性遞增的順序）：
- http://www.cs.ox.ac.uk/people/gerardo.simari/personal/publications/zkp-simari2002.pdf
- http://www.wisdom.weizmann.ac.il/~oded/zk-tut02.html
- http://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes6.pdf
據我了解，Hal Finney 演講的動機是展示當時（不）實用的通用零知識證明系統如何。但這是 20 年前的事了，情況已經有了很大的改善。我們當然已經接近實用性，即使證明應該是非互動式的，即證明者只發送一條消息。
如果你現在正在尋找實用的協議，最有效的候選者是STARKs、Bulletproofs、Ligero、BCCGP16、WTTSW17和ZKBoo。例如，ZKBoo 非常快（證明和驗證大約需要幾毫秒），而Bulletproofs 則慢得多，但有趣的是，證明大小非常關鍵。WTSTW17 包含一個很好的性能比較。（這個討論忽略了需要可信設置的證明系統。使用可信設置，證明可以變得更加高效，請參閱libsnark以獲得很好的概述。）跟踪最新發展的一個很好的資源是https://zkp。科學/.