#1 楼
Cramer和Shoup在名称哈希证明系统的名称下引入了光滑的投影哈希函数。语言$ L $的SPHF允许以两种不同的方式对单词$ x $进行哈希处理：使用某些秘密密钥（哈希密钥，通常表示为$ \ mathsf {hk} $）或使用关联的公共密钥（投影键，通常表示为$ \ mathsf {hp} $）。它必须满足两个属性：如果单词$ x $在语言中，则两种哈希方式都将返回相同的哈希值
如果单词$ x $是在语言之外，即使给定了公共密钥，从秘密密钥获得的哈希值在统计上也与随机变量没有区别。
直觉上，它可以用作一种指定验证者的零知识证明（尽管不满足经典的零知识性质）：为了证明$ x \ in L $，证明者从验证者那里收到投影密钥$ \ mathsf {hp} $，并使用$ \ mathsf {hp} $，然后将结果发送回去。验证者将其与使用密钥获得的哈希进行比较，如果两个哈希相同，则接受证明。
评论
$ \ begingroup $
因此，验证者需要知道$ x $，$ hk $，$ hp $和$ L $。零知识从何而来？
$ \ endgroup $
– Elias
17 Mar 20 '17在10:16
$ \ begingroup $
将$ NP $中的一种语言$ L $与一个多元时间关系$ R $关联如下：$ L = \ {x：\ exists w，R（x，w）= 1 \} $。证明者知道证人$ w $，该证人可以验证$ x $在多项式时间内是否属于$ L $-这是应该保持秘密的信息（例如，考虑了解密文的随机硬币）。但是，我提到的协议仅在验证者诚实地使用时才为零知识（因此，我的句子“它不满足经典的零知识属性”）；作弊验证者可以了解有关$ w $的信息。
$ \ endgroup $
– Geoffroy Couteau
17 Mar 20 '17在12:51
$ \ begingroup $
那么$ w $是使用$ hp $计算哈希值所必需的吗？
$ \ endgroup $
– Elias
17 Mar 20 '17 at 13:02
$ \ begingroup $
是的，这在定义上有些隐含：如果确定$ x \ in L $在计算上是不可行的，则情况$ x \ in L $和$ x \ notin L $在计算上是无法区分的，因此即使给定$ \ mathsf {hp} $，使用$ \ mathsf {hk} $进行散列计算也无法与随机计算区分开。知道$ w $是使用$ \ mathsf {hp} $计算散列值所必需的。
$ \ endgroup $
– Geoffroy Couteau
17 Mar 20 '17 at 13:08