基于后量子假设的高效范围证明方案

作为零知识证明的一种特殊应用，范围证明技术广泛地应用于密码货币、电子投票、匿名凭证等多个场景。这项技术使得证明者能够向验证者证明某一秘密整数属于一个给定的连续整数区间，除此之外不泄露其他任何信息。大部分现有的范围证明方案都是针对基于经典的数论假设的承诺方案构造的，在量子攻击下不能保证安全性。本文针对串承诺方案，提出了一种构造后量子范围证明方案的新思路，并分别基于Exact Learning Parity with Noise（xLPN），Small Integer Solution（SIS）和Learning with Errors （LWE）等假设，给出了三类具体的范围证明方案。此外，文章还提出了一个批承诺方案，并针对该批承诺构造了适用于同时处理多个消息的批处理范围证明方案。该批处理范围证明方案中，对于多个秘密值分别属于不同整数区间的情况，证明者只需要产生一个证明。与对多个消息逐一生成证明的处理方式相比，批处理的方式有效地节约了生成证明过程中需要的随机数个数，明显地降低了双方的通信量和计算量。

Efficient Range Proofs from Post-Quantum Assumptions

As a special case of zero knowledge proof, range proof enables a prover to convince a verifier that a secret number lies in a given public interval, without leaking any other information. It is widely used in cryptocurrencies, e-voting, anonymous credentials, etc. However, most of existing range proof schemes are constructed for commitments based on hard problems of number theory, which are vulnerable against quantum attacks. In this paper, we present several post-quantum range proof schemes, based on the Exact Learning Parity with Noise (xLPN), Small Integer Solution (SIS) and Learning with Errors (LWE) assumptions respectively. In addition, we also propose a batch commitment scheme, together with a batch range proof scheme. Our batch range proof generates only one proof for multiple messages which lie in different ranges. It is efficient in both communication and computation.