基于国密SM2的高效范围证明协议

Efficient Range Proof Protocols Based on Chinese Cryptographic SM2

在范围证明这类特殊的零知识证明协议中,证明者无需提供具体元素信息即可向验证者证明某一承诺的元素在指定集合内.范围证明已被广泛应用于区块链、匿名证书、电子现金、群/环签名等需要身份/数据隐私保护的场景.范围证明协议的设计方法包括平方分解(Square Decomposition)、签名基(Signature-based)、内积(Innerproduct Argument)等,其中使用较为广泛的是Camenisch等在ASIACRYPT 2008会议上提出的签名基方法.然而,Camenisch等提出的范围证明协议不仅需要高耗时的双线性对运算,还涉及繁琐的证书管理,实用性还有待提高.虽然何德彪等(专利申请公布号:CN110311776A)利用国密SM9数字签名算法设计新的协议,避免了证书管理,但仍需要双线性对运算,所以协议的计算开销还较高.为了进一步减少计算量,丰富国产密码的应用,本文采用签名基方法,利用基于国密SM2的标识数字签名算法设计新的集合关系证明协议,有效解决证书管理和双线性对开销问题,在此基础上构造新的数值范围证明协议,支持更大范围的零知识证明.为了证明所设计协议的安全性,本文先证明基于国密SM2的标识数字签名算法在自适应选择消息和身份攻击下具有存在不可伪造性(EUF-CMID-A),在此基础上证明所设计协议满足完备性、可靠性和诚实验证者零知识性.与Camenisch等和何德彪等提出的协议相比,在相同优化参数情况下,本文协议的主要通信带宽约为1568字节,分别减少了41.66%和78.12%;主要计算开销约为491.5075毫秒,分别减少了85.93%和85.85%.这说明了本文设计的协议具有更强的实用性,更能满足前述场景的身份/数据隐私保护与有效性验证需求.

Range proof is a special type of zero-knowledge proofs,among which a prover can prove to a verifier that the element of a commitment is within a specified range,but the prover does not need to tell the verifier the concrete information of this hiding element.Due to this special property,the range proof protocols have been widely applied in various scenarios especially those requiring security requirements of identity or data privacy protection(e.g.blockchain,anonymous certificates,electronic cash,group or ring signatures).Correspondingly,there are also many design methods of range proof protocols have been proposed recently,such as square decomposition method,signature-based method,inner-product argument method,and so forth,among which the signature-based method(proposed by Camenisch et al.in the conference of ASIACRYPT 2008)is one of the most widely used methods at present.However,the range proof protocols proposed by Camenisch et al.not only require a high time-consuming and costly bilinear pairing computation,but also involve a cumbersome certificate management overhead.This means that the utility of their proposed protocols still needs to be further improved.He et al.used the Chinese cryptographic SM9 digital signature algorithm to design two novel range proof protocols without the need of certificate managements,which have been applied for a patent in China(where the patent application publication number is No.CN110311776A).Nevertheless,their proposed protocols are still involved with the bilinear pairing operation,resulting in that their proposals also require a high computational cost.To further reduce the computational cost of existing range proof protocols and also enrich the applications of Chinese cryptographic algorithms,this paper also adopts the signature-based method,but uses an identity-based digital signature algorithm(constructed from the Chinese cryptographic SM2 algorithm)instead to propose a novel set membership protocol.This design can efficiently solve the issues of certificate management and bilinear pairing overhead at the same time.Moreover,we extend our designed set membership protocol to construct a novel numerical range proof protocol,so as to support a wider numerical range of zero-knowledge proofs.Also,in order to prove the security of our proposed two protocols,we first prove the security of the adopted identity-based digital signature algorithm,that is,this signature scheme is proven owning existential unforgery against adaptively chosen message and ID attacks(abbreviated as EUF-CM-ID-A).On basic of this security proof,we then demonstrate that our proposals own the security properties of completeness,special soundness and honest-verifier zero-knowledge.In comparison with Camenisch et al.’s and He et al.’s proposed protocols and using the same optimized parameters,the main communication overhead in our protocols is only about 1568 bytes which has reduced about 41.66%and 78.12%respectively,and the main computation cost in our protocols is only about 491.5075 milliseconds,which has saved about 85.93%and 85.85%respectively.This indeed demonstrates that our proposed protocols have the stronger utility comparing to the existing signature-based range proof protocols,and hence they are more suitable for satisfying requirements of identity or data privacy protection and validity verification in the aforementioned scenarios.