基于格的高效范围证明方案

作者：胡春雅

来源：信息安全学报, 2021, 6(06): 64-78.

• 格密码
• 范围证明
• 零知识证明
• 基于分解技术

早在1985年,Goldwasser、Michali和Rackoff就提出了零知识证明。近年来,区块链这一新技术越来越为人们所熟悉。由于区块链的应用和发展,在实现零知识证明的相关结构方面取得了很大进展。同时,随着量子计算机的研究,许多传统的密码体制受到了严重的威胁。因此,如何构造一个既高效又能抵抗量子攻击的密码方案是密码学领域的一个新的难题。范围证明是一种特殊的零知识证明协议。范围证明可应用于各种实际应用中,如电子投票系统或匿名凭证场景,以确保匿名性和隐私性。在这种协议中,证明者可以使验证者确信他知道一个属于开放连续整数区间的秘密整数。并且证明者不会泄漏有关秘密值的任何信息,除了它位于特定区间的事实。通常,这个秘密整数会被加密方案或承诺方案隐藏。但是现有的范围证明方案要么是不抗量子的,要么在实际应用中效率很低。最糟糕的是,在目前的范围证明方案中,可以证明范围集合是有限的。换言之,如果我们需要证明一个属于任意范围的秘密整数,现有的方案无法做到这一点。针对上述问题,本文提出了两种更有效的基于格的范围证明方案,它们都是后量子方案。首先,我们针对Regev经典加密方案给出了一个高效的范围证明。该范围证明协议可以证明任意范围内的被加密值,例如:证明秘密整数a在范围[α,β],其中α,β是Z_q中整数。同时,我们针对KTX08承诺方案也给出了一个高效的范围证明方案。该范围证明协议能够证明在[0,2~d]中的被承诺值。与目前已有的基于格假设的范围证明方案相比,我们的方案都有着更小的合理性错误和更低的通信成本。

• 单位
  信息安全国家重点实验室; 中国科学院信息工程研究所; 中国科学院大学