| 摘要: |
| 零知识证明是密码协议的核心原语之一， 其功能是证明者向验证者证明某个困难语言的成员归属关系或证据所有权而不泄露任何额外知识， 被广泛应用于数字签名、身份认证、安全多方计算等方面。 随着量子计算机的快速发展， 设计抗量子的高效零知识证明已经成为近年来的热点问题， 而其中基于格的高效零知识证明因其具有独特的渐进高效性、 抗量子攻击和更温和的困难性假设等优势脱颖而出。 在设计基于格的高层密码协议时， 经常涉及到一些具体问题，需要以关于它们的零知识证明作为构造模块为整个协议提供隐私性。 虽然可以使用对任意 完全问题的零知识证明作为通用的解决方案，但是归约开销昂贵影响效率，致使该解决方案不切实际。于是，人们开始设计专门的协议对这些具体问题进行高效的零知识证明。 非齐次小整数解（inhomogeneous small integer solution, ISIS） 问题就是这样一个例子。对ISIS问题的零知识证明经常被用于全同态加密、Fiat-Shamir型标准签名及环签名等方面。
本文聚焦关于ISIS的高效零知识证明， 将现存方案分为两大类：源于几何特征的一类和源于非几何特征的一类，其中前者中的方案均是对ISIS的间接证明。对于后者中的那些方案， 根据技术路线和证明精确程度，我们将它们分为四类： Stern精确型、FSwA松弛型、 S-FS精确型和其他精确型。 FSwA松弛型的方案均是对ISIS的松弛证明，它们的设计遵循FSwA框架，这个框架是将拒绝抽样技术引入Schnorr协议得到的。其他三个类型的方案均是精确证明，其区别在于： Stern精确型构造来自于Stern框架，S-FS精确型构造是介于Stern与FSwA的混合路线，其他精确型旨在提高效率，它们是通过将诸如特殊同态承诺、数论转换等工具组合在一起实现的。对每一种类型，我们首先深入分析每个方案的通信效率、困难性假设和适用环境， 然后总结每类方案的优缺点。 进一步， 以安全性和通信效率为度量指标， 对同类型方案、 对不同类型中的最佳方案进行对比。 |
| 关键词: 零知识证明 ISIS问题 协议 身份认证 数字签名 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2023.08.34 |
| 投稿时间：2021-07-01修订日期：2021-08-27 |
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目）,国家重点基础研究发展计划（973计划） |
|
| Lattice-Based Efficient Zero-Knowledge Proofs |
|
wangmengfan, huangguifang, gaohongmin, hulei
|
| (Institute of Information Engineering, Chinese Academy of Sciences) |
| Abstract: |
| Zero-knowledge proof is one of the key primitives of cryptographic protocols, which enables a prover to prove to a verifier the membership or the possession of a witness for some hard language without leaking any additional knowledge. It can be widely used in digital signature, identification, and secure multi-party computation, etc. With the rapid development of quantum computers, designing efficient zero-knowledge proofs secure against quantum attacks has been a popular problem in recent years, wherein the lattice-based such schemes are more attractive because they enjoy a unique combination of favorable features: asymptotic efficiency, resistance against quantum attacks, and much milder hardness assumptions. When designing a high-level cryptographic protocol, some specific problems are concerned and zero-knowledge proofs for them are required as building blocks to provide privacy. Although the existing zero-knowledge proofs for any complete language would provide a universal solution for such requirement, the expensive reduction has a negative influence on efficiency, which makes the solution impractical. Thus, researchers start to design special protocols to prove these specific problems efficiently in zero-knowledge sense. The inhomogeneous small integer solution (ISIS) problem is such an instance. Zero-knowledge proofs for ISIS problem are extensively used in fully homomorphic encryption, Fiat-Shamir type standard signature, and ring signatures, etc.
In this paper, we aim at zero-knowledge proof for ISIS problem and divide the existing constructions into two categories: the geometrical-feature originated category and the non-geometric-feature orginated category, where constructions in the former are all indirect proofs for ISIS. As for those constructions in the latter, according to the design routes and accuracy of the proofs, we classify them into four types: Stern-exact type, FSwA-relaxed type, S-FS-exact type and other-exact type. Here, FSwA-relaxed type constructions are relaxed proofs for ISIS, designed from FSwA framework which incorporates rejection sampling into Schnorr protocol. The other three types are all exact proofs, with the difference that Stern-exact type constructions are from Stern framework, S-FS-exact type constructions are from a hybrid route between Stern and FSwA, and other-exact type constructions combine some tools such as special homomorphic commitment, number theoretic transform, etc. to improve efficiency. For each type, we deeply analyze every construction from the aspects of communication efficiency, difficulty assumptions and suitable applications, and summarize the advantages and weaknesses. Furthermore, taking the security property and the communication efficiency as measurements, we give detailed comparisons among constructions of the same type, and the optimal constructions of different types. |
| Key words: zero-knowledge proof ISIS problem protocol identification digital signature |
