| 引用本文： |
-
高红敏,黄桂芳,王梦凡,胡磊.关于ISIS问题的零知识证明实例化[J].信息安全学报,已采用 [点击复制]
- gaohongmin,huangguifang,wangmengfan,hulei.Instantiations of Zero Knowledge Proof for ISIS Problem[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 随着量子计算的快速发展，传统数论困难性假设面临挑战，设计量子安全的密码学原子使其逐步替代现存的数论方案已经成为后量子密码时代的迫切需求。格困难性假设作为候选的抗量子困难性假设之一备受关注，在后量子密码算法设计中表现优异，格密码已经成为后量子密码学中的主流方向，具有抗量子、渐近高效性、最坏情况困难性假设等优势。非齐次小整数解（Inhomogeneous small integer solution，ISIS）是格密码中经常用到的一个问题，ISIS问题的零知识证明是许多后量子密码协议的核心部件之一。ISIS问题的零知识证明方案可以分为两大类：精确证明与宽松证明，虽然宽松证明具有更短的证明长度，但是精确证明更加能够覆盖一些特殊应用场景对证明精确性的需求。现存的对ISIS问题的精确型证明包括Stern型方案和一些使用分圆环的代数结构的方案，其中后者只适用于满足某种限制条件的模数q。本文聚焦ISIS的Stern型零知识证明的实例化问题。Stern型零知识证明由Ling San等人在PKC 2013上给出（记为LNSW协议），对通用的模数q均适用。协议对秘密向量进行二进制分解等预处理，使用Stern框架的“承诺—挑战—应答”模式证明预处理后的断言取得零知识性质。由于他们使用的承诺方案是计算绑定的，LNSW协议是零知识的知识论证，其知识合理性仅对计算有界的恶意证明者成立。在本文中，首先给出LNSW协议的两个实例化，实例化一是通过构造基于LWE的承诺方案并将其嵌入LNSW协议得到的，实例化二是使用现存的基于xLPN的承诺方案实现的，它们的共同特点是：均使用了完美绑定承诺方案，从而均具有更强的知识合理性—计算无界知识合理性，整个协议是零知识的知识证明。其次，分别从困难性假设和效率两方面对这两个实例化方案进行比较。最后，分别从零知识性质和通信效率方面与以往实例化方案进行比较，以某具体应用为例，说明实例化一在该应用中具有更优的通信效率。 |
| 关键词: 零知识证明 ISIS LWE 承诺方案 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2024.02.06 |
| 投稿时间：2021-11-22修订日期：2022-02-21 |
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目） |
|
| Instantiations of Zero Knowledge Proof for ISIS Problem |
|
gaohongmin, huangguifang, wangmengfan, hulei
|
| (State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences) |
| Abstract: |
| With rapid developments of quantum computation, traditional number-theoretic difficulty assumptions are confronting with challenges, and designing quantum-secure cryptographic primitives to replace the existing number-theoretic versions gradually has been an urgent demand in post-quantum era. As one of popular candidate quantum-secure assumptions, lattice-related difficulty assumption has received much attention and made a good performance in design of post-quantum algorithms. Lattice cryptography has been a main direction in post-quantum cryptography, which enjoys the advantages of quantum resistance, asymptotic efficiency and worst-case difficulty assumption. Inhomogeneous small integer solution (ISIS) is frequently used in lattice cryptography, and zero knowledge proof for ISIS is one of central building blocks in many post-quantum cryptographic protocols. Zero knowledge proof schemes for ISIS are divided into two categories: exact proof and relaxed proof. Though relaxed proof achieves much shorter proof size, exact proof does cover the special demand on exactness better in some application circumstances. The existing exact proofs for ISIS problem include Stern-type schemes and the schemes taking usage of the algebraic structure of cyclotomic fields, where those in the latter hold only for some special restricted modulus q. This paper aims at instantiation of Stern type zero knowledge proof for ISIS. Stern type zero knowledge proof was given by Ling San et al. in PKC 2013 (called LNSW protocol), which can be applicable to any general modulus q. Their protocol preprocessed the secret vector with binary decomposition and then proved the resulting statement by Stern framework obeying the “commit-challenge-response” paradigm. The commitment scheme they use is computationally binding, thus LNSW protocol is zero knowledge argument of knowledge, implying that its knowledge soundness holds only with respect to computationally-bounded malicious prover. In this paper, firstly, we give two instantiations of LNSW protocol: The first one is obtained by constructing an integral LWE-based commitment scheme and embedding it into LNSW protocol, and the second one is implemented by using the existing xLPN-based commitment scheme. They are common in that both of them use perfectly binding commitment scheme and thus have stronger knowledge soundness—computationally-unbounded knowledge soundness and thus the whole protocol turns out to be zero knowledge proof of knowledge. Secondly, we compare these two instantiations from the respect of difficulty assumption and efficiency. At last, taking some concrete application as example, we compare their zero knowledge property and communication efficiency with previous ones and take some concrete application as an example to conclude that our first instantiation has better communication efficiency in this setting. |
| Key words: zero knowledge proof ISIS LWE commitment scheme |
