问SIS的ZK证明
EN

Cryptography用户

提问于 2016-07-12 18:23:36

回答 1查看 342关注 0票数 5

设A x = 0 \bmod q与\Vert x \Vert < \beta作为格SIS问题的一部分。对于这种解决方案，是否存在有效的零知识证明？

我的想法是将它用于身份验证协议。但到目前为止，我看到的所有ZK协议都是承诺问题或gap问题。由于这一差距，我无法看到如何构建身份验证协议。因为攻击者如果有一个解决方案-- x和x > \beta，但是gap中的x --也可以说服验证者。

发布于 2016-08-13 06:13:13

如果你对基于格的(..and非交互式..)感兴趣零知识，最先进的是2008年的论文(是的，2008年.)在此发现：https://web.eecs.umich.edu/~cpeikert/pubs/latticeNISZK.pdf

从晶格中获取NIZK是一个主要的开放问题。(据我们所知，为了得到一种“类似格”的NIZK形式，你可能得一直走到多线性映射和IND混淆，才能得到一种类似格子的NIZK。)

如果你需要更多的SZK从那份文件，你必须使用一个非SIS，非LWE解决方案(或者，你可以花大钱，并从LWE自己建立NIZK！)

票数 2

页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://crypto.stackexchange.com/questions/37688

复制

相似问题

问SIS的ZK证明EN