格基底整數關係的承諾與證明

Abstract

在[LNS20]中，作者設計兩個整數關係的晶格基底零知識證明協定，分別是證明第三個秘密整數是另外兩個秘密整數的和，而另一個則是其乘法版本的，然而這兩個協定都要求底層的環擁有多個CRT slots，這導致了無法忽視的可靠度誤差。

依據[LNP22]的基礎，我們建構了兩個零知識協定，用於證明先前所提及的整數問題，而無需對底層的環進行先前的限制。此外，我們將加法版本協定推廣到證明k個整數之和，其中k取決於秘密整數的二進位表示。

關鍵字: 整數關係的晶格基底零知識證明協定、ABDLOP承諾計畫、承諾與證明協定、MSIS問題、Extended-MLWE問題

In [LNS20], the authors designed two zero-knowledge protocols for integer relations. The underlying rings of the two lattice-based protocols possess many CRT slots, which has a negative effect on soundness error. One is for proving that the third secret integer is the sum of two other secret integers, while the other is the multiplicative version. Based on the foundation laid by [LNP22], we construct two zero-knowledge protocols dealing with the original problem without the previous requirement for the underlying ring. Moreover, we generalize the addition protocol from sum of two integers to sum of k integers, dependent of bits representing our secret ones. Keywords: Lattice-based zero-knowledge protocol for integer relations, ABDLOP commitment scheme, Commit-and-prove protocol, MSIS, Extended-MLWE