| 引用本文： |
-
黄春早,黄桂芳,方栋,杨浩楠,胡磊.基于格的承诺方案的线性关系证明[J].信息安全学报,已采用 [点击复制]
- Huang Chunzao,Huang Guifang,Fang Dong,Yang Haonan,Hu Lei.Proofs of Linear Relations for Lattice Commitments[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 基于格的承诺方案是格密码中的基本密码学原语之一，它关联的打开证明及其被承诺消息之间的线性关系证明是构造基于格的零知识证明的重要模块，有着许多广泛应用。BDLOP承诺是现今应用最为频繁的基于格的承诺方案，其打开阶段揭开的短向量以二范数或无穷范数作为度量，打开证明和线性关系证明的零知识性质是通过对离散高斯分布进行拒绝采样技术取得的。在PQCrypto 2020中，Tao等提出了BDLOP承诺的一种变体，以最大奇异值代替二范数和无穷范数度量打开阶段的短向量，通过对双峰高斯分布实施拒绝采样技术，设计出对该变体的打开证明，所得证明服从更窄的目标分布，从而具有更短的长度。
本文给出两个新结果。首先，延续Tao的研究路线，使用关于矩阵最大奇异值的更紧上界，提出BDLOP承诺的新变体并给出其相应的打开证明。新的承诺变体具有更弱的困难性假设和更短的证明长度。其次，考虑将基于双峰高斯分布的拒绝采样技术引入到证明被承诺消息之间的线性关系中，进一步设计出该变体的具有更短证明长度的线性关系证明。对上述两个工作，分别给出计算方法和具体实例对证明长度进行对比。 |
| 关键词: 承诺方案 零知识证明 MSIS MLWE 线性关系 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2025.04.17 |
| 投稿时间：2024-01-03修订日期：2024-03-12 |
| 基金项目:国家重点研发计划（No.2022YFB2703003）、国家自然科学基金（No.61932019）、北京市自然科学基金（No.M22003） |
|
| Proofs of Linear Relations for Lattice Commitments |
|
Huang Chunzao, Huang Guifang, Fang Dong, Yang Haonan, Hu Lei
|
| (Institute of Information Engineering, Chinese Academy of Sciences) |
| Abstract: |
| Lattice-based commitment scheme is one of the fundamental cryptographic primitives in lattice cryptography. Its associ-ated opening proof and linear relation proof between the committed messages are important building blocks in the con-struction of lattice-based zero knowledge proofs and have been widely used in many applications. Currently, BDLOP commitment is the most frequently used lattice-based commitment scheme, in which the revealed short vector in the opening phase takes norm as a measurement. By taking the rejection sampling technique on the discrete Gauss-ian distribution, the zero knowledge properties in the opening proof and linear relation proof are achieved. In PQCrypto 2020, Tao et al. proposed a variant of BDLOP commitment, measuring the short vector in the opening phase with the largest singular value instead of norm. By the implementation of the rejection sampling technique on bimodal Gaussian distribution, they designed an opening proof for the variant. The obtained proof has a narrower desired distribu-tion and thus is much shorter in length.
There are two results given in this paper. Firstly, in the research line with Tao’s, using the tighter upper bound on the largest singular value of matrices, we bring out a new variant of BDLOP commitment and present its corresponding open-ing proof. This new variant enjoys a weaker difficulty assumption and a shorter proof length. Secondly, considering the introduction of the bimodal Gaussian distribution based rejection sampling technique into proving the linear relation between the committed messages, we further design a linear relation proof for this variant with a much shorter length. For the above two results, the computation method and the concrete instances are given to take comparison on the size of the proofs. |
| Key words: commitment scheme, zero knowledge proof, MSIS, MLWE, linear relation |
