| 摘要: |
早在1985年,Goldwasser、Michali和Rackoff就提出了零知识证明。近年来,区块链这一新技术越来越为人们所熟悉。由于区块链的应用和发展,在实现零知识证明的相关结构方面取得了很大进展。同时,随着量子计算机的研究,许多传统的密码体制受到了严重的威胁。因此,如何构造一个既高效又能抵抗量子攻击的密码方案是密码学领域的一个新的难题。
范围证明是一种特殊的零知识证明协议。范围证明可应用于各种实际应用中,如电子投票系统或匿名凭证场景,以确保匿名性和隐私性。在这种协议中,证明者可以使验证者确信他知道一个属于开放连续整数区间的秘密整数。并且证明者不会泄漏有关秘密值的任何信息,除了它位于特定区间的事实。通常,这个秘密整数会被加密方案或承诺方案隐藏。但是现有的范围证明方案要么是不抗量子的,要么在实际应用中效率很低。最糟糕的是,在目前的范围证明方案中,可以证明范围集合是有限的。换言之,如果我们需要证明一个属于任意范围的秘密整数,现有的方案无法做到这一点。针对上述问题,本文提出了两种更有效的基于格的范围证明方案,它们都是后量子方案。首先,我们针对Regev经典加密方案给出了一个高效的范围证明。该范围证明协议可以证明任意范围内的被加密值,例如:证明秘密整数a在范围[α,β],其中α,β是Zq中整数。同时,我们针对KTX08承诺方案也给出了一个高效的范围证明方案。该范围证明协议能够证明在[0,2d]中的被承诺值。与目前已有的基于格假设的范围证明方案相比,我们的方案都有着更小的合理性错误和更低的通信成本。 |
| 关键词: 格密码 范围证明 零知识证明 基于分解技术 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2021.11.06 |
| Received:January 17, 2020Revised:March 16, 2020 |
| 基金项目:本课题得到国家自然科学基金项目（No.61772521）；中科院前沿科学重点研究项目（No.QYZDB-SSW-SYS035）资助。 |
|
| Lattice-based Efficient Range Proofs |
| HU Chunya |
| State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China |
| Abstract: |
As early as 1985, zero-knowledge proof was proposed by Goldwasser, Micali and Rackoff. In recent years, blockchain, a new technology, is becoming familiar to people. Due to the application and development of blockchain, great progress has been made in the implementation of related structures of zero-knowledge proof. At the same time, with the research on quantum computer, many traditional cryptographic schemes are under serious threat. Therefore, how to construct a cryptographic scheme that is both efficient and resistant to quantum attacks is a new difficult problem in the field of cryptography.
Range proof is one kind of special zero-knowledge proof protocol. Range proof can be applied in various practical applications, such as electronic voting system or anonymous credential scenarios, to ensure anonymity and privacy. In this kind of protocol, the prover can convince the verifier that he knows a secret integer which belongs to an open continuous integer interval. The prover does not leak any information about the secret value, other than the fact that it lies in the certain interval. Usually, this secret integer will be hidden by encryption schemes or commitment schemes. But the present range proofs are either not quantum resistant or very inefficient in practical application. What’s worst, the range sets that can be proved are limited. In other words, if we need to prove a secret integer that belongs to any range, the existing schemes can not do it. In view of the above problems, in this paper, we propose two more efficient lattice-based range proof schemes which are all post-quantum schemes. In the first scheme, we give an efficient range proof for Regev’s classical encryption scheme. In contrast to the present range proof schemes, our range proof scheme can prove the encrypted secret integer that belongs to arbitrary integer range. Specifically, it can prove that the secret integer a is in the range [α,β]，where α,β are the integers in Zq.In the meantime, we also give an efficient range proof for KTX08 commitment scheme. The protocol can prove that the committed values are in [0,2d], where d is the integer in Zq.Compared with the present lattice-based range proofs, our range proofs have smaller soundness error and lower communication costs. |
| Key words: lattice-based cryptography range proof zero-knowledge proof decomposition-based method |
