Alice公开了一个值$ h $ ，声称她（或/和她可以与之通信的方或/和/或他们可以访问的设备）知道消息$ m $，使得$ H（m）= h $。某些协议可以在没有Bob信任的第三方/设备帮助下，也不允许Bob找到$ m $的情况下使Bob相信这一说法吗？
在Crypto 98臀部会议上，Hal Finney作了7分钟的演讲，零分拥有SHA-1散列原像的知识证明，似乎是为此目的而设计的。有时，包括最近在这里和隔壁的情况，有时都会说出这一非凡的结果。但是我不知道它应该如何工作。
更新：此演讲提到使用Ronald Cramer和Ivan B.Damgård在Crypto'98论文中使用的协议：有限域的零知识证明算术运算或：零知识可以免费吗？ （此版本非常相似，或者有较早的较长版本）。
#1 楼
是的，NP中所有语句都有通用的零知识证明。该结果可以追溯到Oded Goldreich，Silvio Micali和Avi Wigderson于1986年发表的一篇论文。基本思想是给零-图3着色的知识证明，它是NP完全的，即NP中的所有其他语句都可以在其中编码。
语句$ \ exists m。 H（m）= h $显然是一个NP语句：如果有$ m $，则可以以多项式时间检查该语句（通过计算哈希函数）。
我们需要注意虽然很少。您要求的不仅是零知识证明，而且是“知识的零知识证明”，因为证明者不仅想证明这样的$ m $存在，而且要“知道”一个$ m $。
但是这个问题也可以解决（请参见下面的第三篇教程的第7节）。
如果您想了解零知识证明，我推荐这三篇教程，其中明确考虑NP陈述的一般证明（以技术性递增的顺序）：
http://www.cs.ox.ac.uk/people/gerardo.simari/personal/出版物/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年前，并且情况已经大大改善。我们当然已经接近实用性，即使证明不应该是交互式的，也就是证明者只发送一条消息。
如果您今天正在寻找实用的协议，则最有效的候选人是STARK，Bulletproofs，Ligero，BCCGP16，WTTSW17和ZKBoo。例如，ZKBoo相当快（用于验证和验证的时间大约为几毫秒），而Bulletproof的速度要慢得多，但是有趣的证明大小至关重要。 WTSTW17包含一个不错的性能比较。
（此讨论忽略了需要可信设置的证明系统。使用可信设置，可以使证明更加有效，请参见libsnark以获得很好的概述。）有关最新发展的跟踪信息，请访问https://zkp.science/。
评论
$ \ begingroup $
这些都不是最有效的技术。您脑海中的MPC（例如Zkboo github.com/Sobuno/ZKBoo）或zkSNARK的验证速度都更快，验证速度也更快，就SNARK而言，则要小得多。
$ \ endgroup $
– imichaelmiers
18年4月8日在3:11
$ \ begingroup $
编辑，随时添加更多
$ \ endgroup $
–实数或随机数
18年4月8日在9:48
#2 楼
我不确定我可以添加的内容没有在谈话中提到。该方法是Alice提交原图并将承诺发送给Bob。承诺具有同态属性，这意味着可以对值进行计算。例如，如果Alice提交了$ x $和$ y $，则Bob可以计算出对$ z $的承诺，其中对于某些函数$，$ z = f（x，y）$ f $。例如，如果承诺是加法同态的，则Bob可以免费添加两个承诺或乘以一个常数。
或者$ f $不能直接计算。在这种情况下，知道实际值的爱丽丝会计算出$ z $，并向Bob发送对$ z $的承诺，断言这是正确的。 Bob持有对$ x $，$ y $和$ z $的承诺；以及知道$ f $。然后，爱丽丝可以交互地证明，对于$ f $，包含$ z $的承诺确实包含针对$ x $和$ y $的承诺中所包含输入的正确输出。
The Cramer-Damgaard论文展示了如何为布尔门和算术门（例如，NAND和模块化加/乘）的简单Turning-complete集完成这些证明。
实现SHA-1的电路的尺寸将非常大且不可行，例如仅用NAND门表示。在实践中，进行证明的技术是将其分解为最好由布尔或算术电路表示的子协议，并在适当时在证明系统之间进行切换。对于某些SHA运算，他使用布尔运算在位级别工作；对于其他运算，他在有限字段中使用整数。
评论
$ \ begingroup $
您是否有信心对这个问题的答案是明确的“是的，请使用Cramer-Damgård论文中的技术”？还是弱点？我知道没有任何不可能的证据。
$ \ endgroup $
–fgrieu♦
2012年1月30日12:54
$ \ begingroup $
无限的爱丽丝总能证明。有界的爱丽丝只能证明哈希的电路复杂度具有相同的界线。现实生活中的爱丽丝只能证明她能够使用具有有效的零知识证明的运算生成相对简单的电路描述。后者是SHA-1的情况，但其他哈希函数也是如此。
$ \ endgroup $
–PulpSpy
2012年1月30日15:08
$ \ begingroup $
我想上面的内容旨在阅读“但不一定是其他散列函数”，否则支持在演讲中声称的SHA-1情况下可以设计实用协议。我对这些（公认的弱点）论点仍然持怀疑态度：1）对于一般的散列，我们通常无法设计出这样的协议，但是我们无法通过计算来区分SHA-1（消息大小固定） ）取自完美的哈希，而不是因为它是SHA-1； 2）谈话方法的细节很少； 3）似乎未复制出此出色的结果。
$ \ endgroup $
–fgrieu♦
2012年1月30日20:10
$ \ begingroup $
@fgrieu：3）您是否有使用这种构造有用的用例（比纯文本的ZKPoK更可取）？
$ \ endgroup $
–鲍勃
2012年10月13日19:49
$ \ begingroup $
@bob：老实说，不，我没有用例。我当时的兴趣纯粹是理论上的。
$ \ endgroup $
–fgrieu♦
2012年10月15日上午11:14
#3 楼
我想对PulpSpy的答案发表评论，但是我的评论却太大了！我有一个直观的理解，为什么他们不坚持只使用布尔电路来进行所有证明的想法。在这里写下来。我可能是错的，我希望对此进行交叉检查。
布尔和算术电路会出现问题。我从线性代数的角度来看。我们可以以执行转换的相应矩阵的形式编写布尔电路。由于每个矩阵都是线性变换，因此已知下界的形式为$ \ Omega（n ^ 2 / r ^ c）$，其中$ n $是输入大小，$ c $是任意常数，而$ r $是线性相关的最大子矩阵的大小。由于SHA-1的混合效果很好，因此我敢肯定，即使对于任何小的输入（矩阵形式，是大尺寸的子矩阵，相当于$ n $），我们也无法拒绝恒定的输入。这进一步意味着计算电路将需要大量我们不愿进行的计算。
对于使用线性算术电路进行混合的大多数候选哈希函数，我认为此参数效果很好。
评论
我找不到任何支持他在下届会议上讲话的文章。您是否可以访问任何此类文章。我对此非常感兴趣，因为这听起来像是一个具有挑战性的问题，尤其是当人们在随机预言模型中看到哈希函数时。也许那对我有帮助。我超越了谈话的范围。我认为考虑RO模型并解决该问题在理论上将是一个很好的结果。
我目前的直觉是，没有任何实际的协议可以正确地使Bob相信Alice的主张，因为该协议将能够将$ H $与随机预言区分开来，而SHA-1从来没有这样做（仅限于恒定长度的消息） 。我认为在随机oracle模型中，让Bob确信，oracle为消息$ m $输出$ h $的唯一方法是自己提交它，这意味着$ m $的知识。
该协议可以让Bob区分$ H $和随机的oracle，但是它需要Alice的输入。我认为这与不可区分性矛盾。例如，Elgamal是IND-CPA安全的，但也接受纯文本知识的证明。爱丽丝可以允许鲍勃区分自己无法独自破解的密文。无论如何，在现实世界中，任何已实现的哈希函数都不能充当随机预言机。
需要知道哈希设计，以便双方都能跟踪整个电路的进度。我不认为我们总能在现实世界中拥有某种实用性（在谈话中并未声称可以做到；只有SHA-1可以做到）。这取决于功能如何使其自身适合某些技巧以加快证明速度。在将SHA-1转换为布尔/算术电路的混合体时，他所做的与艺术一样多。