cover_image

基于格的类群签名方案

Kurt Pan XPTY
2021年05月05日 21:45

冯翰文, 刘建伟, 伍前红. 后量子安全的群签名和环签名[J]. 密码学报, 2021, 8(2): 183–201. [DOI: 10.13868/j.cnki.jcr.000430] 

  • 标准模型下的环签名

  • 标准模型下的群签名

  • 基于 MV03 和 FSwA 的类群签名方案

    • 基于 FSwA 证明系统的环签名方案

    • 基于 FSwA 和 MV03 证明系统的群签名方案

  • PLS18 的群签名方案

  • ESS+19 和 ESL+19 的环签名方案

  • 基于 Stern 类协议的类群签名方案

    • 基于 Stern 类协议的环签名方案

    • 基于 Stern 类协议的群签名方案

  • 基于 YAZ+19 证明系统的类群签名方案


Part1标准模型下的后量子安全类群签名方案

类群签名的构造通常依赖于 NIZK 证明系统或两轮证据不可区分证明系统 (ZAP) . 然而在标准模型, 包括共享字符串模型 (common reference string model, CRS) 和朴素模型 (plain model) 中, 高效 NIZK 证明系统和 ZAP 的已知构造方式非常有限, 主要为 Groth 和 Sahai 利用双线性映射构造的证明系统. Groth 和 Sahai 的证明系统也是现有的在标准模型下可证安全的群签名方案和环签名方案的构造 基础. 如何基于抗量子的困难问题假设构造类似于 Groth 和 Sahai 的 NIZK 证明系统目前是一个公开难题.

  • GROTH J, SAHAI A. Efficient non-interactive proof systems for bilinear groups[C]. In: Advances in Cryptology—EUROCRYPT 2008. Springer Berlin Heidelberg, 2008: 415–432.

理论上, 可证明所有 NP 语言的通用 NIZK 证明系统或者 ZAP 可以用于证明格密码学和对称密码学相关的语言. CRS 模型下的通用 NIZK 证明系统构造是一个非常经典的问题, 早在 FOCS 1990 上 Feige, Lapidot 和 Shamir 就已经提出了基于单向陷门置换 (one-way trapdoor permutation) 的通用 NIZK证明系统. 然而, 尽管单向陷门置换是一个简单且优美的密码学基本原语, 且可以基于大整数分解假设构造, 我们对它的其他构造方式尤其是基于抗量子假设的构造方式却知之甚少, 这也使得后量子安全的通用 NIZK 证明协议是长期以来的公开难题.

  • FEIGE U, LAPIDOT D, SHAMIR A. Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract)[C]. In: Proceedings of 31st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 1990: 308–317.

可喜的是, 近年来对 Fiat-Shamir 转换在标准模型下的构造方法研究取得了突破性进展. CRYPTO 2019 上, Piekert 和 Shehian 基于 LWE 假设构造了具有 Correlation Intractability (CI) 性质的 Hash 函数, 该 Hash 函数可以用于替换 Fiat-Shamir 转换中的随机预言机, 从而得到 CRS 模型下的通用 NIZK 证明系统 ; Eurocrypt 2020 上, Badrinarayanan 等人同样利用具有 CI 性质的 Hash 函数, 构造了基于 LWE 假设的 ZAP .

  • PEIKERT C, SHIEHIAN S. Noninteractive zero knowledge for NP from (plain) learning with errors[C]. In: Ad- vances in Cryptology—CRYPTO 2019, Part I. Springer Cham, 2019: 89–114.
  • BADRINARAYANAN S, FERNANDO R, JAIN A, et al. Statistical ZAP arguments[C]. In: Advances in Cryptology—EUROCRYPT 2020, Part III. Springer Cham, 2020: 642–667.

根据群签名的通用构造和环签名的通用构造, 上述抗量子的证明系统也从理论上解决了标准模型下后量子安全类群签名构造问题. 在实际效率方面, 基于 LWE 的具有 CI 性质的 Hash 函数构造复杂, 依赖于全同态加密等高级密码学原语, 目前距离实用化还存在非常巨大的差距.

  • BELLARE M, MICCIANCIO D, WARINSCHI B. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions[C]. In: Advances in Cryptology—EUROCRYPT 2003. Springer Berlin Heidelberg, 2003: 614–629.
  • BENDER A, KATZ J, MORSELLI R. Ring signatures: stronger definitions, and constructions without random oracles[C]. In: Theory of Cryptography—TCC 2006. Springer Berlin Heidelberg, 2006: 60–79.

本节所综述的标准模型下的环签名和群签名方案均在上述通用证明系统之前提出, 在当时解决了标准模型下后量子安全的类群签名的存在性问题.

1标准模型下的环签名

Brakerski 和 Kalai 提出了一种高效的通用框架来构造标准模型下的环签名方案. 具体的, 该文献定义了环陷门 (ring trapdoor) 函数这一概念, 并展示了如何利用环陷门来构造环签名. 其中, 环陷门函数是对普通陷门函数的扩展, 它不仅要求给定 和 找到 使得 是困难的, 也要求对于给定的 来找到 使得 是困难的; 但如果具有任何一个 对应的陷门, 则可以有效计算出所有满足条件的 运用环陷门函数构造环签名方案的思路也比较直观, 函数本身作为签名的公钥, 函数对应的陷门作为签名的私钥, 求出的逆 作为环 下的签名.

对于环陷门函数这一新定义, 该文献基于格上的最小整数解 (short integer solution, SIS) 问题和双线性对上的计算性 Diffie-Hellman 问题分别构造了具体的环陷门函数. 使用基于 问题的环陷门函数实例化通用框架可以得到在标准模型下可证安全的格基环签名方案. 由于该方案中, 签名由所有的逆组成, 因此签名的大小和环的规模线性相关. 同时, 基于格的环陷门函数依赖格的陷门函数, 该陷门函数需要较大的格维度, 这也导致签名的实际大小过大, 不满足实际应用需要.

  • BRAKERSKI Z, KALAI Y T. A framework for efficient signatures, ring signatures and identity based encryption in the standard model[J/OL]. IACR Cryptology ePrint Archive, 2010: 2010/086. https://eprint.iacr.org/2010/086.pdf

2标准模型下的群签名

Katsumata 和 Yamada 为了构造在标准模型下可证明安全的格基群签名方案, 他们绕过了传统的群签名设计框架，提出了不基于非交互零知识证明的构造方法. 他们构造的核心思想是利用属性基签名来替代群签名构造中非交互零知识证明的功能. 属性基签名有基于格的构造 ，且在标准模型可证明安全.

  • KATSUMATA S, YAMADA S. Group signatures without NIZK: From lattices in the standard model[C]. In: Advances in Cryptology—EUROCRYPT 2019, Part III. Springer Cham, 2019: 312–344.

属性基签名方案中, 由密钥中心向用户分发某一属性 对应的私钥 , 而持有该私钥的用户可以生成满足 的属性策略 下合法的签名. 与非交互零知识证明对应, 在属性策略 下的签名可以视为对满足 的 的知识证明. 不同的是, 持有属性 的用户必须事先从密钥中心获得私钥 才能完成进行签名. 在群签名中, 签名者需要证明密文的正确性, 而加密所用的随机数作为证据的一部分是在签名过程中产生的, 无法被密钥中心事先得知并生成对应的私钥, 因此直接使用属性基签名无法得到安全的群签名方案.

Katsumata 和 Yamada 借鉴了 Kim 和 Wu 构造预处理非交互零知识证明协议的思想, 使用对称加密方案对凭据进行加密, 并将证明加密正确性转换为证明解密的正确性, 通过解密的确定性移除加密的不确定性, 使得群管理员可以一次性生成用户所需的签名私钥, 从而解决了该问题. 由于用户同样掌握解密密钥, 可以确定某一签名是否由自己的私钥产生, 因此该方案的匿名性为无私匿名性而非完全匿名性. 该方案中, 密钥中心需要掌握用户所有的秘密信息, 并在启动阶段生成对应的私钥, 因此该方案属于静态群签名方案. 如何利用属性基签名来构造动态群签名方案尚缺乏清晰的技术途径.

  • KIM S, WU D J. Multi-theorem preprocessing NIZKs from lattices[C]. In: Advances in Cryptology—CRYPTO 2018, Part II. Springer Cham, 2018: 733–765.

Part2基于 ws-NIZK 证明系统的类群签名方案

基于 ws-NIZK 证明系统的格基类群签名方案可以分为两个阶段. 早期方案使用的 ws-NIZK 证明系统为 MV03 证明系统和 Fiat-Shamir-with-Abort(FSwA) 证明系统. 这两个证明系统最早被用于证明 GapCVP 或非齐次最小整数解问题 (inhomogeneous small integer solution, ISIS) 等格上困难问题, 应用到类群签名的构造时需要配合额外的技术, 效率较低.

  • MICCIANCIO D, VADHAN S P. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more[C]. In: Advances in Cryptology—CRYPTO 2003. Springer Berlin Heidelberg, 2003: 282–298.
  • LYUBASHEVSKY V. Lattice signatures without trapdoors[C]. In: Advances in Cryptology—EUROCRYPT 2012. Springer Berlin Heidelberg, 2012: 738–755.

2018 年后的部分格基类群签名方案发展了新的 ws-NIZK 证明系统, 包括 one-out-of-many 的证明系统 ESS+19 和 ESL+19 (适用于自组织的群成员关系证明), 以及证明自同构不变点的证明系统 PLS18 (适用于有管理员的群成员关系证明). 这些新型证明系统极大提升了格基类群签名的实际效率, 达到或接近了实用化需求.

  • ESGIN M F, STEINFELD R, SAKZAD A, et al. Short lattice-based one-out-of-many proofs and applications to ring signatures[C]. In: Applied Cryptography and Network Security—ACNS 2019. Springer Cham, 2019: 67–88.
  • ESGIN M F, STEINFELD R, LIU J K, et al. Lattice-based zero-knowledge proofs: New techniques for shorter and faster constructions and applications[C]. In: Advances in Cryptology—CRYPTO 2019, Part I. Springer Cham, 2019: 115–146.
  • DEL PINO R, LYUBASHEVSKY V, SEILER G. Lattice-based group signatures and zero-knowledge proofs of au- tomorphism stability[C]. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS). ACM, 2018: 574–591.

通用性方面, 基于格的 ws-NIZK 证明系统仅适用于非常有限的语言. 弱可靠性在密文正确性证明和数字签名持有证明等常见应用中缺乏明确的意义. 基于 ws-NIZK 的群签名方案中, 密文正确性证明需要额外的技术才能完成. 动态群签名所需要的数字签名持有证明难以通过 ws-NIZK 证明系统实现, 导致动态群签名难以通过 ws-NIZK 证明系统构造. 实际效率方面, 部分良好设计的 ws-NIZK 证明系统非常高效, 可以满足特定应用下的实用化需求.

3基于 MV03 和 FSwA 的类群签名方案

MV03 证明系统是由 Micciancio 和 Vadhan 于 CRYPTO 2003 提出的零知识证明系统可以证明 等格上最坏情况的困难问题. FSwA 证明系统由 Lyubashevsky 于 Asiacrypt 2009 和 Eurocrypt 2012 提出并发展, 其设计思想与基于离散对数的 Schnorr 协议类似, 它允许证明者证明自己持有 ISIS 问题的证据, 即持有某个短向量 满足 , 其中 和 为公开的矩阵或向量, 是公开的数值. MV03 证明系统的单次执行允许恶意证明者以 的概率欺骗验证者 (soundness error 等于 , 因此需要至少 次重复执行协议才能保证恶意证明者成功欺骗的概率是可忽略的 为安全参数), 效率较低. FSwA 证明系统单次执行即可保证 soundness error 为可忽略的, 效率明显优于 MV03. 事实上, MV03 证明系统仅被使用于非常早期的群签名方案.

  • MICCIANCIO D, VADHAN S P. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more[C]. In: Advances in Cryptology—CRYPTO 2003. Springer Berlin Heidelberg, 2003: 282–298.
  • LYUBASHEVSKY V. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[C]. In: Advances in Cryptology—ASIACRYPT 2009. Springer Berlin Heidelberg, 2009: 598–616.
  • LYUBASHEVSKY V. Lattice signatures without trapdoors[C]. In: Advances in Cryptology—EUROCRYPT 2012. Springer Berlin Heidelberg, 2012: 738–755.

MV03 和 FSwA 证明系统只能满足弱可靠性，即证明者对自己持有短向量 满 足 ISIS 的实例 的证明, 实际上只能确保证明者知道 满足 , 其中 . 的这一缺点也进一步限制了它在证明密文正确性等需要精确的可靠性场景下的使用. 受限于 MV03 和 FSwA 可证明的语言类型, 相应的环签名方案只能做到签名大小与环的规模线性相关, 而群签名需要借助格的特殊陷门函数才能完成密文正确性的证明.

  • LING S, NGUYEN K, STEHLE ́ D, et al. Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications[C]. In: Public-Key Cryptography—PKC 2013. Springer Berlin Heidelberg, 2013: 107–124.

基于 FSwA 证明系统的环签名方案

早期的格基环签名方案可以视作是经典的 CDS 机制在格密码中的应用. CDS机制是指 Cramer、Damgård 和 Schoenmakers 于CRYPTO 1994 上提出的一种按照 OR 关系组合 Sigma 协议机制. 具体的, 若对于某个 语言 , 存在满足特定条件的协议 可以证明 , 那么经由 机制可以得到一个新的协议 来证明

如果 协议是身份认证协议, 则 可经过 Fiat-Shamir 转换得到环签名方案。使用CDS机制，Melchor 等人将基于 的格基身份认证协议转换为环签名方案. 该环签名方案和所有经由 机制构造的环签名方案一样, 签名大小和环的规模线性相关.

  • MELCHOR C A, BETTAIEB S, BOYEN X, et al. Adapting Lyubashevsky’s signature schemes to the ring signature setting[C]. In: Progress in Cryptology—AFRICACRYPT 2013. Springer Berlin Heidelberg, 2013: 1–25.
  • CRAMER R, DAMG ̊ARD I, SCHOENMAKERS B. Proofs of partial knowledge and simplified design of witness hiding protocols[C]. In: Advances in Cryptology—CRYPTO ’94.

类似的构造方法也被应用与设计格基可链接环签名方案. Baum、Lin 和 Oechsner 的方案与 Torres 等人的方案非常类似. 他们的方案可以视作是基于离散对数的可链接环签名方案在格上的迁移. 他们首先设计 FSwA 协议证明用于实现链接性的向量是用签名者的私钥诚实生成的, 再利用 机制隐藏签名者的公钥, 经由 Fiat-Shamir 转换后形成可链接环签名. 这两个方案签名大小和环的规模成线性关系, 主要应用考虑的是匿名数字货币等环规模较小的场景.

需要指出的是, 这两个方案所实现的可链接性为一次可链接性, 即任意两个由同一私钥产生的签名可以被公开链接.  一次可链接性与标准的基于标签 (Tag-based) 的可链接性有严格的区别. 从应用角度, 一次可链接性足够匿名数字货币的使用需求. 从技术角度, 实现基于标签的可链接性需要引入伪随机函数作为组件, 并用零知识证明系统来保证伪随机函数的正确执行. 这样的证明任务难以通过 FSwA 完成.

  • BAUM C, LIN H, OECHSNER S. Towards practical lattice-based one-time linkable ring signatures[C]. In: Information and Communications Security—ICICS 2018. Springer Cham, 2018: 303–322.
  • TORRES W A A, STEINFELD R, SAKZAD A, et al. Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain (lattice RingCT v1.0)[C]. In: Information Security and Privacy—ACISP 2018. Springer Cham, 2018: 558–576. FRANKLIN M K, ZHANG H B. A framework for unique ring signatures[J/OL]. IACR Cryptology ePrint Archive, 2012: 2012/577. https://eprint.iacr.org/2012/577.pdf

基于 FSwA 和 MV03 证明系统的群签名方案

由于 MV03 和 FSwA 难以直接证明密文的正确性, 早期的格基群签名构造不得不依赖特殊的代数结构来降低需要证明的关系的复杂度. 最早的基于格 的群签名方案由 Gordon、Katz 和 Vaikuntanathan 提出. 在该方案中, 他们提出了带陷门的正交格 (orthogonal lattice with its trapdoor) 这一概念及其采样方法. 给定矩阵 , 可以生成矩阵 使得 及 是 的陷门 作为 个用户的分别的公钥. 如果编号为 的用户需要对消息 签名, 则可以利用对应的陷门 可以生成一个短向量 满足 , 再求解线性方程组生成 满足 然后加密每个 得到 该加密方案的安全性可以归约到格上的容错学习问题 (learning with errors, 由于 和 是正交矩阵, 因此验证者可以很轻易的验证 唯一需要证明的是至少有一 对应的 是一个短向量. 这样的证明系统可以结合 MV03 证明系统, CDS 机制, 以及 Fiat-Shamir 转换来实现. 安全性上, Gordon 方案提供的匿名性为抗选择明文攻击的匿名性, 即攻击者不具备获得任意指定签名的签名者身份的能力. 效率上, Gordon 方案中签名的大小和群成员个数线性相关, 并且由于使用了特殊的代数结构导致系统参数巨大, 实际效率也无法应用于真实场景. Camenisch、Neven 和 Rückert 对此方案进行了改进, 实现了具备完全匿名性的格基群签名方案, 且可以保护诚实的用户不被管理员恶意指控,但是构造上仍然依赖于正交格陷门和 MV02 协议, 效率没有明显提升.

  • GORDON S D, KATZ J, VAIKUNTANATHAN V. A group signature scheme from lattice assumptions[C]. In: Advances in Cryptology—ASIACRYPT 2010. Springer Berlin Heidelberg, 2010: 395–412.
  • CAMENISCH J, NEVEN G, RUCKERT M. Fully anonymous attribute tokens from lattices[C]. In: Security and Cryptography for Networks—SCN 2012. Springer Berlin Heidelberg, 2012: 57–75.

第一个基于格的对数级的群签名方案由 Laguilaumie 等提出. 该方案将用户的身份编码为比特的字符串 , 并使用 提出的格基签名方案来为用户生成证书. 在 Boyen 的签名方案中, 签名是一个陷门矩阵而非短向量, 获得签名的用户可以利用这个签名来生成自己的临时凭证 对消息 进行签名时, 用户需要对所有的 逐项加密 , 再证明密文是对的加密 (对应 为 1 或者 0 (对应 的加密. 因为 比特的身份编码最多有 个, 因此群成员最多有 个. 签名的大小与群成员个数成对数关系. 然而, 该方案在证明密文属性的时候仍然依赖于 Gordon 等人提出的带陷门的正交格, 因此产生的群签名的实际大小仍然非常巨大.

  • LAGUILLAUMIE F, LANGLOIS A, LIBERT B, et al. Lattice-based group signatures with logarithmic signature size[C]. In: Advances in Cryptology—ASIACRYPT 2013, Part II. Springer Berlin Heidelberg, 2013: 41–61.

Laguilaumie 等人在随后的工作中提出了支持了验证者本地撤销的格基群签名方案 , 但此方案的效率相比不支持本地撤销的方案没有提升. Nguyen、Zhang 和 Zhang 利用 Agrawal 等人在基于格的身份基加密方案中提出的身份编码技术, 来编码群签名中的用户身份, 并基于 证明系统来完成对方案中密文正确性的证明. 由于使用了更紧致的身份编码, Nguyen 等人的方案较 Laguilaumie 等人的方案有所提升, 但是仍然依赖 Gordon 等人 提出的陷门函数. 根据测试, 在群成员总数为 时, Nguyen 等人的方案的签名大小为 , 私钥大小为 上述群签名方案用户的密钥均是在系统启动阶段由群管理员生成, 用户无法动态加入, 因此上述方案为静态群签名方案.

  • LANGLOIS A, LING S, NGUYEN K, et al. Lattice-based group signature scheme with verifier-local revocation[C]. In: Public-Key Cryptography—PKC 2014. Springer Berlin Heidelberg, 2014: 345–361.
  • NGUYEN P Q, ZHANG J, ZHANG Z F. Simpler efficient group signatures from lattices[C]. In: Public-Key Cryptography—PKC 2015. Springer Berlin Heidelberg, 2015: 401–426.
  • AGRAWAL S, BONEH D, BOYEN X. Efficient lattice (H)IBE in the standard model[C]. In: Advances in Cryptology—EUROCRYPT 2010. Springer Berlin Heidelberg, 2010: 553–572.
  • LIBERT B, LING S, NGUYEN K, et al. Zero-knowledge arguments for lattice-based accumulators: Logarithmic- size ring signatures and group signatures without trapdoors[C]. In: Advances in Cryptology—EUROCRYPT 2016, Part II. Springer Berlin Heidelberg, 2016: 1–31.

4PLS18 的群签名方案

在 CCS 2018 上, Pino、Lyubashevsky 和 Seiler 充分利用了环的代数结构来设计群签名方案. 对于分圆环 , 存在多个元素可以在对应分圆数域的 Galois 自同构映射下保持不变. Pino 等人针对这种自同构不变性, 设计了一种高效格基 NIZK 证明系统, 证明某个承诺值属于自同构下的不变点. 将所有的不变点视作群元素, 该零知识证明协议可以用于证明群成员关系. 技术上, 该证明系统与 FSwA 证明系统类似, 单次执行即可实现可忽略的 soundness error, 但也仅满足弱可靠性. 为了证明密文是正确生成的, Pino 等人使用了 Lyubashevsky 和 Neven 在 Eurocrypt 2017 上提出的可验证加密技术. 结合可验证加密与新的群成员关系证明系统, Pino 等人提出了基于模 SIS 和模 LWE 问题的群签名方案. 该方案是目前最高效的格基群签名方案, 签名大小仅为 580KB 左右, 所有操作都可以在 0.5 秒以内完成. 但由于环中的不变点是在系统启动阶段就已经确定的, 如何利用该证明系统来设计动态群签名方案和环签名方案尚不清晰.

  • DEL PINO R, LYUBASHEVSKY V, SEILER G. Lattice-based group signatures and zero-knowledge proofs of au- tomorphism stability[C]. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS). ACM, 2018: 574–591.
  • LYUBASHEVSKY V, NEVEN G. One-shot verifiable encryption from lattices[C]. In: Advances in Cryptology—EUROCRYPT 2017, Part I. Springer Cham, 2017: 293–323.

5ESS+19 和 ESL+19 的环签名方案

经典密码体制下 Groth 和 Kohlweiss 设计基于离散对数困难问题设计了签名大小与环的规模成对数关系的环签名方案. 该环签名方案的核心构造是一种新的 one-out-of-many 的零知识证明协议: 证明 个承诺 的某个承诺值的消息为 . 证明系统与基于离散对数的 Schnorr 协议的相似性揭示了将更多的基于离散对数的协议迁移到格基协议的可能, 也启发研究人员思考如何利用 Groth 和 Kohlweiss 的设计方法来构造高效格基环签名.

  • GROTH J, KOHLWEISS M. One-out-of-many proofs: Or how to leak a secret and spend a coin[C]. In: Advances in Cryptology—EUROCRYPT 2015, Part II. Springer Berlin Heidelberg, 2015: 253–280.

在 ACNS 2019 上, Esgin 等人解决了将Groth 和 Kohlweiss  设计思想迁移到格上的若干问题, 设计了基于模格上的 SIS 问题的 one-out-of-many 协议, 并构造了具有对数级签名大小的环签名方案 ESS+19. 该 one-out-of-many 协议的 soundness error 为 , 需要多次重复执行协议才能实现可忽略的 soundness error.

  • ESGIN M F, STEINFELD R, SAKZAD A, et al. Short lattice-based one-out-of-many proofs and applications to ring signatures[C]. In: Applied Cryptography and Network Security—ACNS 2019. Springer Cham, 2019: 67–88.

在 CRYPTO 2019 上, Esgin 等人解决了该问题, 实现了单次执行即可保证可忽略的 soundness error. 他们将该证明技术提炼为适用于非线性多项式关系的零知识证明技术, 并发展了基于环中国剩余定理的批处理技术, 进一步降低此类零进行了重构, 得到了基于模格上困难问题的环签名方案 ESL+19. 对 规模的环, 该方案的签名大小仅为 左右, 是目前适用于大规模环的效率最高的后量子安全环签名方案.

  • ESGIN M F, STEINFELD R, LIU J K, et al. Lattice-based zero-knowledge proofs: New techniques for shorter and faster constructions and applications[C]. In: Advances in Cryptology—CRYPTO 2019, Part I. Springer Cham, 2019: 115–146

Part3基于 ss-NIZK 证明系统的类群签名方案

现有基于格的 ss-NIZK 证明系统包括 Stern 类协议和 YAZ+19 证明系统. Stern 类协议和 YAZ+19 证明系统的通用性强, 可以证明格密码学中常见的一大类语言, 可以构造类群签名的各种功能变种. 但 Stern 类协议单次执行的 soundness error 为 2/3, 需要多次重复执行才能实现可忽略的 soundness error, 根本上限制了基于 Stern 类协议的类群签名的效率. YAZ+19 可以视作 Stern 类协议的改进版本, 单次执行的 soundness error 为多项式的逆, 需要重复执行的次数显著降低. 二者都无法通过单次执行实现可忽略的 soundness error, 在特定应用上效率明显低于某些 ws-NIZK 证明系统.

  • STERN J. A new paradigm for public key identification[J]. IEEE Transactions on Information Theory, 1996, 42(6):1757–1768.
  • YANG R P, AU M H, ZHANG Z F, et al. Efficient lattice-based zero-knowledge arguments with standard soundness: Construction and applications[C]. In: Advances in Cryptology—CRYPTO 2019, Part I. Springer Cham, 2019: 147–175

6基于 Stern 类协议的类群签名方案

Stern 类协议最早由 Stern 提出并用于设计基于编码理论的身份认证协议，而后被 Tanaka 和 Xagawa 引入到格密码学中用于构造基于格的身份认证协议 . Ling 等人改进了Kawachi 等人的工作, 使得 Stern 类协议可以“精确地"证明 ISIS 问题 与 不同 此后, Stern类 协议被广泛地用于设计基于格的类群签名方案, Stern 类协议的设计技巧也在应用中不断发展. 目前 Stern 类协议可以证明符合如下形式的 关系 ： 使用 Libert、Ling、Nguyen 和 Wang 等人提出并发展的若干技巧, 格密码学中常见的密文结构关系和签名消息对关系等都可以转换为上述形式, 从而可以使用 Stern 来协议来证明此关系. Stern 类协议的发展丰富了格密码学工具库, 使得大量此前不知道如何基于格构造的密码学原语第一次有了基于格的具体构造.

  • STERN J. A new paradigm for public key identification[J]. IEEE Transactions on Information Theory, 1996, 42(6):1757–1768.
  • KAWACHI A, TANAKA K, XAGAWA K. Concurrently secure identification schemes based on the worst case hardness of lattice problems[C]. In: Advances in Cryptology—ASIACRYPT 2008. Springer Berlin Heidelberg, 2008: 372–389.
  • LING S, NGUYEN K, STEHLE ́ D, et al. Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications[C]. In: Public-Key Cryptography—PKC 2013. Springer Berlin Heidelberg, 2013: 107–124.

需要指出的是, 尽管 Stern 类协议功能强大, 基于 Stern 协议的类群签名方案的效率距离实际应用仍然有较大距离. 这是由于 Stern 类协议单次执行的 soundness error 为 , 为了使 soudness error 下降 到可忽略为一个可忽略的值如 , 需要重复执行 Stern 协议 200 次以上. Stern 类协议的这一特性是基于此类协议的签名方案无法进一步提高效率的主要原因.

基于 Stern 类协议的环签名方案

在 Eurocrypt 2016 上, Libert 等人基于 Stern 类协议设计了签名 大小与环规模成对数关系的环签名方案 , 解决了格基紧致环签名构造这一公开难题. 在经典密码体制下, 紧致的环签名方案通常需要依赖累加器这种特殊结构. 累加器可以视作是对集合的承诺方案, 且具备紧致的成员关系证明方式. 已知的累加器分为三类, 包括基于 Strong RSA 假设的累加器 , 基于双线性对的累加器 , 以及基于 Merkle 树的累加器. Libert 等人使用基于 SIS 困难问题的杂奏函数构建了墨克树 (Merkle tree) 作为基于格的的累加器方案, 再针对该累加器设计了Stern 类型的零知识证明协议. 对于墨克树中的叶子节点, 它到根节点的路径可以作为该叶子节点属于该墨克树的证据, 而该证据的大小和叶子节点的总数成对数关系. 这也是 Libert 等人的方案可以实现对数级签名大小的根本原因.

  • LIBERT B, LING S, NGUYEN K, et al. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[C]. In: Advances in Cryptology—EUROCRYPT 2016, Part II. Springer Berlin Heidelberg, 2016: 1–31.

Stern 类协议作为核心组件被用于设计一些环签名的变种方案. Yang 等人 在 Libert 等人提出的格基环签名方案基础上设计了基于格的可链接环签名方案. 在 CT-RSA 2020 上, Feng等人提出了可追踪环签名的通用设计框架, 并基于 Stern 类协议构造了格基可追踪环签名方案

  • YANG R P, AU M H, LAI J Z, et al. Lattice-based techniques for accountable anonymity: Composition of abstract Stern’s protocols and weak PRF with efficient protocols from LWR[J/OL]. IACR Cryptology ePrint Archive, 2018: 2017/781. https://eprint.iacr.org/2017/781.pdf
  • FENG H W, LIU J W, WU Q H, et al. Traceable ring signatures with post-quantum security[C]. In: Topics in Cryptology—CT-RSA 2020. Springer Cham, 2020: 442–468.

基于 Stern 类协议的群签名方案

Ling、Nguyen 和 Wang 发展了 Stern 协议, 使得群签名方案中的密文正确性可以通过 Stern 协议证明, 从而摆脱了对 Gordon等人    提出的正交格基陷门的依赖，而仅使用标准的格陷门函数. 相比于之前基于正交格基陷门的群签名方案, 该方案的安全假设更弱, 并且可以很容易地构造基于环 SIS 和环 LWE 的版本。基于环 LWE 和环 SIS 的方案通常比基于标准 LWE 和标准 SIS 的方案更加高效, 但此前的群签名方案所使用的正交格陷门缺乏基于环的构造方法.

  • LING S, NGUYEN K, WANG H X. Group signatures from lattices: Simpler, tighter, shorter, ring-based[C]. In: Public-Key Cryptography—PKC 2015. Springer Berlin Heidelberg, 2015: 427–449.

Libert 等人采用拓展环签名的方式来构造静态群签名方案。他们所拓展的环签名方案也即上文介绍的基于Merkle 树累加器的环签名方案. 他们的群签名方案的群公钥可以看做包含所有群成员公钥的一个固定的环。在对消息进行签名时, 签名者需要加密自己的公钥, 并证明密文是对环中某个公钥的加密. 该方案的构造方式移除了对格上陷门函数的需求, 可以更灵活的设置系统参数. 在此之前的格基群签名方案都是用了格上的陷门函数来为群中的用户生成凭证, 受限于陷门所需的系统参数选择, 签名的实际尺寸都过于巨大. 同时, 由于对应环签名方案的签名大小和环规模成对数关系, 该方案的签名尺寸也是对数级的. 根据 Libert 等人自己的测试结果, 该方案在群成员为 时, 签名大小为 左右, 较之前 级的签名大小有显著提升.

  • LIBERT B, LING S, NGUYEN K, et al. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[C]. In: Advances in Cryptology—EUROCRYPT 2016, Part II. Springer Berlin Heidelberg, 2016: 1–31.

利用 Stern 协议, Libert 等人在 Asiacrypt 2016 上构造了第一个基于格的动态群签名方案. 该构造的关键是设计零知识证明协议证明密文对应的明文是合法的格基数字签名. 在 ACNS 2017 上. Libert 等人拓展了文献累加器方案, 使其支持加入和撤销等动态操作, 从而得到了第一个基于格的全动态群签名方案. 此工作后, 大量的具有不同安全特性或者功能特性的格基群签名方案被提出, 包括具有前向安全性的群签名方案、支持对开启机构行为审计的群签名方案、支持层次结构的群签名方案和多群签名方案. Ling 等人为 Ducas 和 Micciancio的数字签名方案设计零知识证明协议, 支持证明持有该方案合法的消息签名对, 从而构造出了第一个基于格的常数级群签名方案. 这也是目前渐进效率最优的格基群签名方案.

  • LIBERT B, LING S, MOUHARTEM F, et al. Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[C]. In: Advances in Cryptology—ASIACRYPT 2016, Part II. Springer Cham,2016: 373–403.
  • BOHLF, HOFHEINZ D, JAGER T, et al. Confined guessing: New signatures from standard assumptions[J]. Journal of Cryptology, 2015, 28(1): 176–208.
  • LING S, NGUYEN K, WANG H X, et al. Lattice-based group signatures: Achieving full dynamicity with ease[C]. In: Applied Cryptography and Network Security—ACNS 2017. Springer Cham, 2017: 293–312.
  • LING S, NGUYEN K, WANG H X, et al. Forward-secure group signatures from lattices[C]. In: Post-Quantum Cryptography—PQCrypto 2019. Springer Cham, 2019: 44–64.
  • LING S, NGUYEN K, WANG H X, et al. Accountable tracing signatures from lattices[C]. In: Topics in Cryptology—CT-RSA 2019. Springer Cham, 2019: 556–576.
  • HOU L, LIU R Z, QIU T, et al. Hierarchical group signatures with verifier-local revocation[C]. In: Information and Communications Security—ICICS 2018. Springer Cham, 2018: 271–286.
  • QIU T, HOU L, LIN D D. A multi-group signature scheme from lattices[C]. In: Information and Communications Security—ICICS 2019. Springer Cham, 2019: 359–377.
  • LING S, NGUYEN K, WANG H X, et al. Constant-size group signatures from lattices[C]. In: Public-Key Cryptography—PKC 2018, Part II. Springer Cham, 2018: 58–88.

7基于 YAZ+19 证明系统的类群签名方案

在 CRYPTO 2019 上, Yang 等提出了一种新的格基零知识证明系统 YAZ+19. 功能方面, 证明系统与 Stern 类协议接近, 可以证明格密码学中常见的一大类 语言, 并具备标准的可靠性. 效率方面, 该证明系统单轮执行的 soundness error 仅为 poly, poly 代表安全参数的多项式. 该数值小于 Stern 类协议的 soundness error , 将 soundness error 降低到可忽略的大小所需要的重复次数也随之少于同等安全参数下 Stern 类协议所需重复次数, 因此该证明系统效率较 Stern 类协议有显著提升. 证明系统设计上结合了 FSwA 和 Stern 类协议的优点. 对于需要证明的 ISIS 问题 , 该证明系统首先采用类似于 的方式, “宽松地" 证明存在向量 满足 , 再采用类似于 Stern 类协议的方式“精确地"证明存在向量 满足 结合两者的优点, 实现了精确证明和更小的 soundness error.

Yang 等人使用该证明系统对基于 Stern 类协议的类群签名方案进行了全面的升级, 得到的类群签名方案是目前基于标准格效率最优的方案. 值得一提的是, Bootle、Lyubashevsky 和 Seiler 在 CRYPTO 2019 上发表了他们关于新型格基零知识证明系统的工作. 他们的证明系统设计方法和效率与 YAZ+19 接近, 但他们并没有将该证明系统应用到类群签名的设计中, 在此不再展开介绍.

  • YANG R P, AU M H, ZHANG Z F, et al. Efficient lattice-based zero-knowledge arguments with standard soundness: Construction and applications[C]. In: Advances in Cryptology—CRYPTO 2019, Part I. Springer Cham, 2019: 147–175.
  • BOOTLE J, LYUBASHEVSKY V, SEILER G. Algebraic techniques for short(er) exact lattice-based zero-knowledge proofs[C]. In: Advances in Cryptology—CRYPTO 2019, Part I. Springer Cham, 2019: 176–202.

Part4基于变色龙 Hash 的环签名方案

在 ACNS 2019 上, Lu、Au 和 Zhang 提出了适用于小规模环的实用格基环签名方案 Raptor. 与第三代的其他工作不同, Raptor 取得的效率提升并非是来源于新型零知识证明协议, 而是来源于环签名方案的新设计框架. Lu 等人深入分析了 Rivest、Shamir 和 Tauman 提出第一个环签名通用构造框架 RST01, 提炼出了RST01框架实际上所需要的密码组件, 即增强变色龙杂凑函数 (chameleon hash plus, CH+). 他们基于标准格和 NTRU 格分别构造了 CH+, 并在此基础上构造了格基环签名方案. 与 RST01 框架的其他环签名一样, Lu 等人的方案中签名大小与环的规模线性相关, 因此更适用于小规模环 的情况. 他们的实现测试结果说明该方案对于规模较小的环 (例如由5个公钥构成的环) 效率可以满足实用需求 (对应签名大小为6.3 KB).

Lu 等人也提出了一种新的一次可链接环签名设计方法. 他们的方案区别于 Franklin 和 Zhang 提出的构造方法, 通过在环签名中附加一次性签名的方法来实现同一私钥产生的不同签名的可链接性. Wang、Chen 和 Ma 总结并推广了此种可链接环签名设计技巧.

  • LU X Y, AU M H, ZHANG Z F. Raptor: A practical lattice-based (linkable) ring signature[C]. In: Applied Cryptography and Network Security—ACNS 2019. Springer Cham, 2019: 110–130.
  • RIVEST R L, SHAMIR A, TAUMAN Y. How to leak a secret[C]. In: Advances in Cryptology—ASIACRYPT 2001. Springer Berlin Heidelberg, 2001: 552–565.
  • FRANKLIN M K, ZHANG H B. A framework for unique ring signatures[J/OL]. IACR Cryptology ePrint Archive, 2012: 2012/577.
  • WANG X L, CHEN Y, MA X C. Adding linkability to ring signatures with one-time signatures[C]. In: Information Security—ISC 2019. Springer Cham, 2019: 445–464.

Part5具体效率

结合安全假设、具体功能和应用场景等指标, 在表1中总结了其中最高效的格基类群签名方案.