cover_image

门限密码系统综述

Kurt Pan XPTY
2022年01月03日 16:18

涂彬彬, 陈宇. 门限密码系统综述[J]. 密码学报, 2020, 7(1): 1-14.
TU B B, CHEN Y. A Survey of Threshold Cryptosystems. Journal of Cryptologic Research, 2020, 7(1): 1-14.

Part1引言

对于密码系统而言, 密钥是实现密码功能操作的关键, 密钥的安全保存是密码系统的安全核心. 但是 传统公钥密码的密钥唯一, 密钥的安全性完全依靠用户的秘密保存, 一旦用户的密钥丢失, 不仅难以恢复, 容易形成单点故障导致密码系统无法正常操作, 甚至恶意敌手在获得密钥后, 可任意窃取用户隐私信息或者伪造用户身份.

从 1979 年, Shamir 和 Blakley 分别独立地提出了门限方案, 又称秘密分享, 门限的思想便深入人心. 特别是, Desmedt 和 Frankel 等人后来引入了门限密码的概念, 彻底地打开了门限密码研究的大门. 门限密码通过将密钥信息分享给多个用户分散保存, 密码功能操作可由至少门限值个用户协作完成, 而且任意少于门限数量的用户无法进行合谋. 一方面提高了系统的健壮性, 即使少量用户丢失密钥, 不会导致密码系统丧失功能性. 另一方面, 提高了系统的安全性, 恶意故手即使窃取了部分 (少于门限值) 用户的密钥, 也难以打破密码系统的安全性.

近些年, 云计算、分布式计算以及区块链等技术持续发展并且广泛应用于互联网领域. 为了降低或者避免因单个用户完全掌握权限, 导致密钥丢失、权限滥用或该用户被攻击者控制等安全风险, 提升分布式计算系统的健壮性和安全性, 可将密钥分配给多个用户分散保存, 并要求密码操作由多个用户协同完成. 在传统公钥密码系统中, 由于只有私钥拥有者具有绝对权限, 难以满足多用户在分布式环境下的安全需求. 门限密码系统可看作关于密码功能操作 (解密/签名) 的特殊的多方安全计算, 多个用户秘密地分享了密钥信息, 在进行解密/签名操作时, 用户可使用自己的私钥, 通过多方安全计算的模式多方协作解密密文/签名消息, 对于解决单点故障问题, 以及分布式环境下多用户的数据安全、隐私保护和身份认证有着重要的应用意义.

门限密码系统主要包括门限加密和门限签名, 具体形式类似公钥系统中的加密和签名.

门限加密包括密钥生成、加密和解密过程, 以及一个消息组合器 (combiner). 在解密过程中, 用户使用自己的私钥解密密文, 并将解密分享发送给消息组合器, 消息组合器在接收到门限值个解密分享时可组合出原消息.

同样, 门限签名包括密钥生成、签名和验签过程, 以及一个签名组合器. 在签名过程中, 用户使用自己的私钥签名消息, 并将签名分享发送给签名组合器, 签名组合器在接收到门限值个签名分享时可组合出该消息的签名.

如果门限密码的密钥生成阶段不需要密钥生成中心, 系统的公钥和各用户的私钥是由用户自己交互完成, 则可称该门限密码是全分布式的 (full distributed) . 如果门限密码的解密/签名阶段, 不需要各用户之间或者与组合器进行交互, 则称该门限加密/签名是非交互的 (non-interactive).

与传统公钥密码相比, 门限密码有着丰富的功能性、更强的安全模型和特殊性质.

在密码功能方面, 门限密码将传统公钥密码操作从以往的单一模式扩展到多用户合作模式.

在安全性模型上, 门限密码除了考虑类似公钥密码方案的安全性外, 还要考虑敌手对于用户的攻击, 比如: (1) 弱的攻击模型——静态攻击模型 (static corruption model). 敌手在系统参数发布前先选定攻击的目标用户, 可获得目标用户的私钥信息; (2) 强的攻击模型——自适应攻击模型 (adaptive corruption model). 敌手可在系统运行的任何时刻, 根据具体的攻击情况自适应地选择攻击的目标用户, 获得目标用户的私钥信息.

除了丰富的功能性和更强的安全性, 门限密码还具有一些其它特性:

  1. 紧致性 (compactness). 公钥尺寸和密文/签名尺寸与参与用户的数量无关.
  2. 鲁棒性(robustness).各用户的解密/签名分享的正确性可被公开验证.
  3. 全分布式. 系统的公钥和用户的私钥可由用户自己通过交互生成, 避免了密钥生成中心的权限过大或者被攻击者控制等带来的安全风险.
  4. 抗合谋. 门限密码系统要求参与的用户数量达到门限值, 才能正确完成密码操作, 防止了单个用户失败导致整个系统瘫痪, 同时防止任意少于门限值个用户合谋.

基于上述良好的性质, 门限密码自从诞生以来, 就成为密码学领域非常热门的研究方向, 得到快速的发展, 并在分布式环境下的密钥恢复 、证书认证 (certification authorities)、电子投票 、密码货币以及多方安全计算等各方面都有着非常广泛的应用.

  • SHOUP V, GENNARO R. Securing threshold cryptosystems against chosen ciphertext attack[J]. Journal of Cryp- tology, 2002, 15(2): 75–96.
  • FOUQUE P, POUPARD G, STERN J. Sharing decryption in the context of voting or lotteries[C]. In: Financial Cryptography—FC 2000. Springer Berlin Heidelberg, 2000: 90–104.
  • GENNARO R, GOLDFEDER S, NARAYANAN A. Threshold-optimal DSA/ECDSA signatures and an applica- tion to bitcoin wallet security[C]. In: Applied Cryptography and Network Security—ACNS 2016. Springer Berlin Heidelberg, 2016: 156–174.
  • CRAMER R, DAMGÅRD I, NIELSEN J B. Multiparty computation from threshold homomorphic encryption[C]. In: Advances in Cryptology—EUROCRYPT 2001. Springer Berlin Heidelberg, 2001: 280–299.

本文主要概述了目前门限密码系统的研究现状, 分别介绍了门限加密的选择明文安全和选择密文安全, 门限签名的选择消息不可伪造安全, 以及相关构造方案和主要的构造技术. 探讨了目前门限密码系统分别在静态模型和自适应模型下的通用构造方法、抗量子安全等方向的发展趋势和依旧存在的问题.

Part2门限密码系统的基本概念

本节将重点介绍门限加密和门限签名的基本概念和安全性定义.

1门限加密

门限加密方案 (threshold encryption, TE) 包括以下 4 个算法:

  • : 密钥生成算法输入安全参数 , 用户数量 和门限值 , 输出公钥 和用户私钥分享 .

  • : 加密算法输入公钥 和消息 , 输出密文 .

  • ：解密算法输入任意用户的私钥分享 和密文 , 输出解密分享 .

  • : 消息组合算法输入任意 个解密分享 , 输出消息 .

正确性: 对于 , 加密任意消息 生成密文 , 任意门限值 个用户计算解密分享 , 则有 .

安全性: 定义静态模型下选择明文攻击的敌手优势函数 如下:

其中 是一个特殊的解密预言机, 该预言机输入任意用户的身份 id, 输出一个新的密文 以及该用户关于密文 的解密分享 . 对于任意概率多项式时间的敌手 , 如果优势函数 , 则门限加密是静态模型下选择明文安全的.

定义静态模型下选择密文攻击的敌手优势函数 类似 , 只是敌手可以访问更加强大的解密预言机 代替 . 该预言机输入任意用户的身份 id 和密文 , 输出该用户的解密分享 . 同样, 对于任意概率多项式时间的敌手 , 如果敌手优势函数 , 则门限加密是静态模型下选择密文安全的.

上述安全性定义都只是针对静态模型下的敌手, 这类敌手在系统参数建立 之前, 需要预先指定最多 个目标用户攻击 , 获得其私钥信息 . 自适应模型下的敌手可以在系统运行的任何时刻自适应地选择最多 个目标用户攻击, 并获得其私钥信息.

2门限签名

门限签名方案 (threshold signature, TS) 包括以下 4 个算法:

  • : 密钥生成算法输入安全参数 , 用户数量 和门限值 , 输出验证公钥 和用户私钥 .
  • : 签名算法输入任意用户私钥 和消息 , 输出签名分享 .
  • : 签名组合算法输入任意 个签名分享 , 输出签名 .
  • : 验证算法输入验证公钥 , 消息 和签名 , 当签名验证成功时输出 1 , 否则输 出 0 .

正确性: 对于 , 任意门限值 个用户签名消息 , 计算签名分享 , 获得签名 , 则有 .

安全性: 定义静态模型下选择消息攻击的敌手优势函数 如下:

其中敌手可以访问用户的签名预言机 , 该预言机可输入任意用户的身份 id 和消息 , 输出该用户关于消息的签名分享 . 对于任意概率多项式时间的敌手 , 如果敌手优势函数 , 则门限签名是静态模型下选择消息安全的 .

上述安全性定义只针对静态模 型下的敌手, 而自适应模型下的敌手可以在系统运行的任何时刻自适应地选择最多 个目标用户攻击.

Part3门限密码的发展及研究现状

Desmedt 和 Frankel 等人在研究面向群组的密码 (group oriented cryptography) 时, 引入了门限密码的概念. 门限密码具有多用户的协作解密/签名的功能, 在保障群组环境下的数据安全、隐私保护和身份认证等方面, 与传统公钥密码相比, 有着天然的优势.

3门限加密

门限加密通过将私钥信息分布式地保存在多个用户中, 要求少于门限值个用户无法成功合谋解密, 只 有不少于门限值个用户共同解密才能恢复消息. 因此, 构造门限加密方案除了需要考虑选择明文/密文安 全外, 还要考虑敌手对于用户的攻击.

选择明文安全的门限加密

与选择明文安全的公钥加密相比, 门限加密的选择明文安全定义中, 敌手能力更强, 可以任意选择少于门限值个目标用户进行攻击, 获得目标用户的解密私钥. 此外, 敌手还能访问一个特殊的解密预言机, 该预言机输入任意用户的身份, 输出一个新的密文和该用户的解密分享. 因此, 构造选择明文安全的门限加密方案, 不仅要考虑泄漏目标用户的解密私钥, 还要考虑特殊解密预言机泄漏用户解密分享对于明文不可区分性的影响.

在 Crypto 1989 上, Desmedt 和 Frankel 使用 Shamir 的门限秘密分享技术分割私钥, 对 ElGamal 加密方案进行门限化, 构造了高效的选择明文安全的门限加密方案. 但在安全性证明中, 由于归约算法 (reduction algorithm) 没有私钥信息, 无法回答自适应敌手关于目标用户的私钥询问. 只能在静态敌手固定攻击的目标用户后, 对系统参数和目标用户的解密私钥进行模拟, 在静态模型下可证明安全. 此外, 由于 Shamir 的门限秘密分享方案对于模数的限制, 该方案只能选择素数阶群. 同时, 因为在 RSA 加密中参数 是偶数, 不是一个域. 该问题也导致了无法通过分割 RSA 加密方案的私钥, 构造基于 RSA 假设的门限加密方案.

  • DESMEDT Y, FRANKEL Y. Threshold cryptosystems[C]. In: Advances in Cryptology—CRYPTO ’89. Springer Berlin Heidelberg, 1989: 307–315.

随后, De Santis 等人在 STOC 1994 上提出函数分享 (function sharing) 的概念. 该密码组件将单向陷门函数 (one-way trapdoor function) 的陷门进行分割, 每个陷门分享可用于计算任意函数像的求逆分享, 并且门限数量个求逆分享可以恢复出原像. 函数分享满足门限单向性: 任意概率多项式时间的敌手可以获得少于门限个陷门分享, 以及一条包含多项式个随机像的求逆分享的历史带 (history tape), 却无法以非可忽略的概率求逆该函数. 根据单向陷门函数构造公钥加密方案的思想, 基于函数分享设计了选择明文安全的门限密码的通用构造方法. 该方法中, 各参与方分别使用分享密钥进行解密, 并公布自己的解密分享, 门限值个解密分享可组合出明文. 在实例化方面, 通过扩展 Desmedt 和 Frankel 的技术, 给出了 Shamir 的门限秘密分享的扩展版本. 该版本可以在任意有限阿贝尔群上进行秘密分享, 突破了基于 RSA 假设难以构造门限加密方案的障碍, 解决了 Desmedt 和 Frankel  给出的困难问题, 基于 RSA 假设实例化了函数分享, 并构造了选择明文安全的门限加密方案.

  • DE SANTIS A, DESMEDT Y, FRANKEL Y, et al. How to share a function securely[C]. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing. ACM, 1994: 522–533.
  • DESMEDT Y, FRANKEL Y. Shared generation of authenticators and signatures (extended abstract)[C]. In: Advances in Cryptology—CRYPTO ’91. Springer Berlin Heidelberg, 1991: 457–469.

选择密文安全的门限加密

早期对于门限加密的研究主要关注于选择明文安全, 但是随着公钥加密选择密文安全概念的提出与推广, 选择密文安全的门限加密也受到了密码学家的广泛关注. 直观上, 门限加密的解密过程是多个用户以一种安全多方计算的模式进行解密运算. 因此, 构造选择密文安全的门限加密, 可以直接使用多方安全计算方法, 将选择密文安全的公钥密码方案门限化. 但是该技术需要各个解密用户之间进行大量的交互运算, 效率不高. 后来, 选择密文安全的门限密码方案构造主要在于实现密文的可验证性 或者保证各用户解密分享的随机化. 随着选择密文安全的公钥加密的设计技术的深入研究, 许多技术比如基于身份加密转化技术、基于可提取哈希证明系统的通用构造技术对构造选择密文安全的门限加密有着深远影响.

对于构造选择密文安全的门限加密方案的探索, Lim 和 Lee 在 Crypto 1993 上首先观察到设计选择密文安全的门限加密, 需要密文可公开验证. 在解密阶段, 各个用户需要先验证密文的合法性, 然后对密文进行解密, 输出解密分享. 如此可保证各用户解密的密文合法性, 用户的解密分享不会影响明文的不可区分性. 该思想对于后续构造选择密文安全的门限加密有着非常大的影响.

  • LIM C H, LEE P J. Another method for attaining security against adaptively chosen ciphertext attacks[C]. In: Advances in Cryptology—CRYPTO ’93. Springer Berlin Heidelberg, 1993: 420–434.

在 Eurocrypt 1998 上, Shoup 和 Gennaro 给出了非交互的选择密文安全的门限加密的形式化定义. 与门限加密的选择明文安全相比, 在选择密文安全中, 敌手拥有更强的攻击能力, 可获得任意用户的解密预言机. 该预言机输入密文和任意用户的身份, 输出该用户的解密分享. 基于 Lim 和 Lee 的密文可公开验证思想, 他们使用 Chaum-Pedersen 的 - 协议 , 应用 Fiat-Shamir 启发式设计的非交互的零知识证明来保证密文的可公开验证性, 并在随机预言机 (random oracle) 模型下设计了首个可实践的选择密文安全的门限加密方案.

  • SHOUP V, GENNARO R. Securing threshold cryptosystems against chosen ciphertext attack[J]. Journal of Cryptology, 2002, 15(2): 75–96.

随后在 Eurocrypt 1999 上, Canetti 和 Goldwasser 基于 Cramer 和 Shoup  的选择密文安全的公钥加密方案, 并在标准模型下将其门限化, 构造了选择密文安全的门限加密方案. Cramer-Shoup方案的密文具有特殊的代数结构, 在解密阶段, 当密文是有效时, 各用户的解密分享可正确组合出原消息, 而当密文无效时, 各用户的解密分享与随机垃圾 (random garbage) 不可区分. 因此, 该方案依靠特殊的解密结构, 保证了用户解密错误的密文, 输出的解密分享具有随机性, 不会影响明文的不可区分性, 精巧地避免了使用非交互零知识证明来保证密文的可公开验证性. 但是在解密阶段, 该方案需要各用户之间进行交互运算并且需要储存较多的预共享的秘密 (pre-shared secret) 与Shoup-Gennaro方案相比, 效率略低. 此外, Canetti 和 Goldwasser 还提出了基于多重加密思想构造门限加密方案, 该思想后续也影响了 Zhang 等人, Dodis 和 Katz , 以及 Xie 等人构造门限加密的方法.

  • CANETTI R, GOLDWASSER S. An efficient: Threshold public key cryptosystem secure against adaptive chosen ciphertext attack[C]. In: Advances in Cryptology—EUROCRYPT ’99. Springer Berlin Heidelberg, 1999: 90–106.
  • ZHANG R, HANAOKA G, SHIKATA J, et al. On the security of multiple encryption or CCA-security+CCA- security=CCA-security[C]? In: Public Key Cryptography—PKC 2004. Springer Berlin Heidelberg, 2004: 360–374.
  • DODIS Y, KATZ J. Chosen-ciphertext security of multiple encryption[C]. In: Theory of Cryptography—TCC 2005. Springer Berlin Heidelberg, 2005: 188–209.
  • XIE X, XUE R, ZHANG R. Efficient threshold encryption from lossy trapdoor functions[C]. In: Post-Quantum Cryptography—PQCRYPTO 2011. Springer Berlin Heidelberg, 2011: 163–178.

公钥密码的选择密文安全的设计新思想影响着门限加密的构造. Canetti 等人在 Eurocrypt 2004 上提出了 Canetti-Halevi-Katz (CHK) 范式, 证明了选择明文安全的基于身份加密蕴含选择密文安全的公钥加密. 基于该思想, Boneh 等人构造了标准模型下非交互的选择密文安全的门限加密方案. 他们首先将 Boneh 和 Boyen的基于身份加密方案的密钥生成算法门限化, 设计了门限的基于身份加密方案. 然后, 将 CHK 范式扩展至门限版本, 构造了基于双线性 (Bilinear) Diffie-Hellman 假设的选择密文安全的门限加密方案. 同样基于这种转化思想, Bendlin 等人 将格上两类重要的算法 (陷门生成算法和高斯抽样算法) 门限化, 并对 Gentry 等人的基于身份加密方案门限化, 构造了基于格的选择密文安全的门限加密方案.

  • CANETTI R, HALEVI S, KATZ J. Chosen-ciphertext security from identity-based encryption[C]. In: Advances in Cryptology—EUROCRYPT 2004. Springer Berlin Heidelberg, 2004: 207–222.
  • BONEH D, BOYEN X, HALEVI S. Chosen ciphertext secure public key threshold encryption without ran- dom oracles[C]. In: Topics in Cryptology—CT-RSA 2006. Springer Berlin Heidelberg, 2006: 226–243.
  • BENDLIN R, KREHBIEL S, PEIKERT C. How to share a lattice trapdoor: Threshold protocols for signatures and (H)IBE[C]. In: Applied Cryptography and Network Security—ACNS 2013. Springer Berlin Heidelberg, 2013: 218–236.

对于选择密文安全公钥加密的探索, Wee 在 Crypto 2010 上通过高度抽象传统公钥密码的选择密文安全的设计方法, 提炼出非交互零知识知识的证明 (Non-Interactive Zero-Knowledge Proof of Knowledge) 的思想, 首次提出了可提取哈希证明系统 (extractable hash proof system) 的概念, 并基于可提取哈希证明系统给出了选择密文安全的公钥加密的通用构造. 随后在 Eurocrypt 2011 上, Wee 对该思想扩展, 将可提取哈希证明系统门限化, 引入新的密码组件——门限的可提取哈希证明系统 (threshold extractable hash proof systems, TEHPS), 并基于门限的可提取哈希证明系统设计了门限加密的通用构造方法, 然后分别基于整数分解假设 (Factoring) 和 DDH 假设给出具体的实例化方案. 此后, 在 TCC 2012 上, Libert 和 Yung 对 Wee 提出的门限可提取哈希证明的思想进一步推广, 引入了 all-but-one perfectly sound threshold hash proof systems (ABO-PS-THPS) 的概念, 给出了自适应模型下选择密文安全的门限加密方案的构造, 并分别基于素数阶的双线性群上的 DLIN 假设和 symmetric external Diffie-Hellman (SXDH) 假设实例化了门限加密方案.

  • WEE H. Threshold and revocation cryptosystems via extractable hash proofs[C]. In: Advances in Cryptology— EUROCRYPT 2011. Springer Berlin Heidelberg, 2011: 589–609.
  • LIBERT B, YUNG M. Non-interactive CCA-secure threshold cryptosystems with adaptive security: New frame- work and constructions[C]. In: Theory of Cryptography—TCC 2012.

4门限签名

与传统数字签名相比较, 门限签名将签名私钥分散给多个用户, 只有当不少于门限值个用户协同签名, 才能完成正确的签名, 而少于门限个用户无法通过合谋签名. 因此, 在构造门限签名时, 不仅要考虑签名的不可伪造性, 还需要考虑敌手对于目标用户的攻击.

Desmedt 和 Frankel  在 Crypto 1991 上, 设计了可在阿贝尔群上运算的门限秘密分享方案, 首次基于 RSA 假设设计了门限签名方案. 随后, 基于不同的密码假设的门限签名方案也相继被设计. 在 Eurocrypt 2000 上, Shoup 采用了消除分母的技术 (clearing out the denominator), 在静态模型下基于 RSA 假设构造了非交互的门限签名方案. 徐秋亮 首先设计了一个特殊形式的 RSA 签名体制, 并通过证明所使用的 hash 函数具有强无碰撞性及单向性, 建立了一个改进的门限 RSA 签名方案, 可完全避免在任何代数结构中计算逆元素, 无须作任何代数扩张, 在应用中较为高效. 在 Asiacrypt 2002 上, Katz 和 Yung 对修改版本的 Rabin 签名方案进行了门限化, 获得静态模型下基于整数分解假设的非交互的门限签名方案. 在 Eurocrypt 2011 上, Wee 基于门限可提取哈希证明系统设计了静态模型下门限签名的通用构造, 并给出丰富的实例化. 在 ACNS 2013 上, Bendlin 等人将 Gentry 等人的基于格的签名方案门限化, 设计了基于格的门限签名方案. Boneh 等人提出了门限通用转化器 (universal thresholdizer) 的概念, 并基于该组件可将格上的签名方案转化成门限版本, 获得基于格的门限签名方案.

  • SHOUP V. Practical threshold signatures[C]. In: Advances in Cryptology—EUROCRYPT 2000. Springer Berlin Heidelberg, 2000: 207–220.
  • XU Q L. A modified threshold RSA digital signature scheme[J]. Chinese Journal of Computers, 2000, 23(5): 449–453.
  • KATZ J, YUNG M. Threshold cryptosystems based on factoring[C]. In: Advances in Cryptology—ASIACRYPT 2002. Springer Berlin Heidelberg, 2002: 192–205.
  • WEE H. Threshold and revocation cryptosystems via extractable hash proofs[C]. In: Advances in Cryptology— EUROCRYPT 2011. Springer Berlin Heidelberg, 2011: 589–609.
  • BENDLIN R, KREHBIEL S, PEIKERT C. How to share a lattice trapdoor: Threshold protocols for signatures and (H)IBE[C]. In: Applied Cryptography and Network Security—ACNS 2013. Springer Berlin Heidelberg, 2013: 218–236.
  • BONEH D, GENNARO R, GOLDFEDER S, et al. A lattice-based universal thresholdizer for cryptographic systems[J]. IACR Cryptology ePrint Archive, 2017: 2017/251.

上世纪九十年代, 随着数字签名标准 (digital signature algorithm, DSA) 的提出和广泛应用. 特别是, 近些年密码货币的爆发式发展, 基于椭圆曲线的数字签名标准 (ECDSA) 在比特币等密码货币中承担重要应用. 而在其中签名密钥的丢失也意味着具体经济的损失. 由于比特币系统中使用了多重签名的解决方案, 并非门限签名, 限制了系统的灵活性, 难以支持复杂的过程结构 . 因此, 对 DSA 进行门限化具有重要的应用意义.

在门限 DSA 的研究探索中, 由于签名算法是概率算法, 对其门限化需要所有签名参与方通过交互运算共同协商随机数, 导致门限化非常困难. 在 Eurocrypt 1996 上, Gennaro 等人给出了交互式门限签名的形式化定义, 并基于联合随机秘密分享方案 (joint random secret sharing, JRSS) 和联合零秘密分享方案 (joint zero secret sharing, JZSS), 并设计了计算乘积和求逆的多方安全计算方法, 对 DSA 进行门限化, 构造了全分布式的门限数字签名标准. 具体而言, 根据 JRSS 技术协商出 DSA 的签名验证公钥和签名私钥, 并分别保留私钥分享. 签名阶段, 各参与方使用 JRSS 协商随机数 并各自保留随机数分享, 使用多方安全求逆运算计算 , 使用多方安全乘积运算计算签名私钥与随机数 的组合, 各参与方可获得签名值的分享. 最后各参与方公布签名分享, 达到门限值即可组合出最终签名. 但是该方案在组合签名阶段, 各用户需要计算私钥与随机数的乘积与随机数的求逆, 导致了多项式的次数扩张. 具体而言, 当门限值是 时, 至少需要 个用户才能组合出签名. 因此, 该方案并非门限最优化的, 而且通信消耗非常大, 难以应用.

  • GENNARO R, JARECKI S, KRAWCZYK H, et al. Robust threshold DSS signatures[C]. In: Advances in Cryptology—EUROCRYPT ’96.

在 ACNS 2016 上, Gennaro 等人针对门限数字签名标准的多项式扩张问题, 基于 Paillier的同态加密方案 的门限版本配合陷门承诺技术 (trapdoor commitment) , 构造了最优化的门限数字签名标准. 具体而言, 该方案采用了门限同态加密技术, 各参与方可以使用同态加密的性质对于明文进行密态操作, 保证了各方隐私信息的安全性, 并可完成复杂的签名运算. 但是该方案依旧要求各用户之间进行大量的交互运算通信消耗较高, 而且签名算法需要复杂的零知识证明. 随后在 CCS 2018 上, Gennaro 和 Goldfeder 对上述方案进行优化, 使用了特殊的多方安全计算技术 (Smart,Pastro,Damgård,Zakarias 协议, SPDZ 协议), 避免了使用复杂的零知识证明方法, 设计了简单的门限 ECDSA 方案. 但是该方法依旧使用了 Paillier 的同态加密方案, 而目前并没有针对 Paillier 加密方案的高效分布式密钥生成算法. 针对该问题, 在 CCS 2018 上, Lindell 等人使用指数 (in-the-exponent) ElGamal 的加法同态算法代替Paillier 的加法同态加密算法设计了首个高效的门限 ECDSA 分布式密钥生成算法和签名算法.

  • GENNARO R, GOLDFEDER S, NARAYANAN A. Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security[C]. In: Applied Cryptography and Network Security—ACNS 2016. Springer Berlin Heidelberg, 2016: 156–174.
  • GENNARO R, GOLDFEDER S. Fast multiparty threshold ECDSA with fast trustless setup[C]. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS 2018). ACM, 2018:1179–1194.
  • LINDELL Y, NOF A, RANELLUCCI S. Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody[C]. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS 2018). ACM, 2018: 1837–1854.

5关键应用技术研究进展

门限密码具有比传统公钥密码更加复杂的安全模型和更加丰富应用特性, 仅考虑加密的选择明文/密文安全或者签名的选择消息不可伪造安全难以满足门限密码的现实应用需求. 在密码研究领域, 一方面, 主要探索基于较弱的密码组件设计密码方案, 可保证该密码方案可基于多数密码假设实例化, 丰富密码方案的构造. 另一方面, 在更强的安全性模型下的探索密码方案的设计技术, 可构造安全性更强的密码方案, 保证密码方案具有更强的应用适用性. 此外, 积极关注密码研究新动向, 针对新型密码分析技术, 构造具有针对性的安全密码方案, 可保证密码应用的安全性. 因此, 针对门限密码的关键应用技术研究, 一方面, 需要探索门限密码的通用构造技术, 可根据不同的底层困难假设构造具体的密码方案, 提高密码方案的适用性, 同时可进行模块化的代码实现, 提高代码实现效率. 另一方面, 门限密码主要应用于分布式环境下多用 户的合作场景. 该场景中自适应攻击模型与静态攻击模型相比, 敌手对于现实用户攻击的更加真实. 因此, 设计自适应模型下安全的门限密码是密码安全应用的关键. 此外, 基于传统数论假设的密码方案难以在量子攻击下保证安全性, 探索可抵抗量子攻击的门限密码方案引起了密码学家们的广泛关注. 不同于传统数论假设, 格上的困难假设被认为是可抗量子攻击的. 因此, 基于格构造抗量子安全的门限密码方案也是目前关键的研究方向.

门限密码的通用构造

探索密码方案的通用构造技术是密码研究的重要方向. 基于较弱的密码组件设计密码方案的通用构造, 可保证该方案能由多数的底层密码假设实例化. 如果当构造该组件的某个密码假设的安全性受到威胁, 或者发现能更高效地实例化该组件的密码假设, 可以及时替换密码假设来保证密码方案的安全和高效执行. 此外, 基于密码组件设计密码方案的通用构造技术, 是一种模块化的构造思想, 在密码方案的代码实现方面具有较大的优势. 对于门限密码系统的通用构造技术的探索, 特别是选择密文安全的门限加密和选择消息不可伪造的签名的通用构造技术的研究一直深受关注. 

对于探索选择密文安全的门限加密的通用构造技术, Canetti 和 Goldwasser 在 Eurocrypt 1999 上, 首次基于多重加密 (multiple encryption) 的思想给出了门限加密的通用构造方法. 在密钥生成阶段, 对每个用户生成一组公钥加密方案的公私钥对. 在消息加密阶段, 通过使用 Shamir 的门限秘密分享对加密消息进行分割, 使用每个用户的公钥对每个消息分享进行加密, 密文包含了所有消息分享加密后的结果. 在解密阶段, 每个用户使用自己的私钥解密相对应的密文, 获得对应的消息分享. 在组合阶段, 组合器接收到门限值个消息分享, 使用拉格朗日插值公式可恢复出原消息. 随后, Zhang 等人在 PKC 2004 上, 以及 Dodis 和 Katz 在 TCC 2005 上基于多重加密的思想, 分别设计了静态模型下选择密文安全的门 限加密的通用构造方法. 对上述方案的进一步弱化, Xie 等人发现上述文献的构造中, 使用的加密组件需要满足自适应选择标签安全 (adaptively chosen-tag secure). 他们观察到该条件并非是必要的, 并 对底层密码组件进行弱化, 使用选择标签安全 (selectively chosen-tag secure) 的基于标签加密 (tag-based encryption) 作为加密组件, 结合强不可伪造安全的一次签名设计了门限加密的通用构造, 然后基于有损陷门函数 (lossy trapdoor function) 设计了基于标签加密的通用构造, 最终获得了静态模型下选择密文安全的门限加密的通用构造. 但是使用多重加密技术设计的门限加密方案具有天然的缺陷——缺少紧致性, 导致该方案的公钥尺寸和密文尺寸较大, 与用户数量线性相关.

通过扩展 CHK 范式 构造选择密文安全的公钥加密的思想, Boneh 等人在 CT-RSA 2006 上给出了门限的基于身份加密可设计静态模型下选择密文安全的门限加密的通用构造方法, 并基于 Boneh 和 Boyen 的身份加密方案给出具体的实例化. 具体而言, 该技术通过对基于身份加密的主私钥进行分割, 将基于身份加密的私钥提取算法门限化, 要求达到门限值个参与方合作才能提取用户的身份私钥, 形成了门限的基于身份加密方案. 然后使用强不可伪造的一次签名技术, 设计了门限加密方案, 并证明了任意选择身份安全的门限的基于身份加密和强不可伪造一次签名可构造选择密文安全的门限加密. 该方法影响了后续较多的门限密码设计方法, 包括 Libert 和 Yung , 以及 Bendlin 等人构造门限密码方 案.

在 Eurocrypt 2011 上, Wee 通过扩展可提取哈希证明系统构造选择密文安全的公钥加密思想, 提出了门限的可提取哈希证明系统, 并基于该组件设计静态模型下可证明安全的门限加密和门限签名的通用构造方法. 具体而言, 门限的可提取哈希证明系统包括两种模式: 正常模式和 -模拟模式, 并且这两种模式 是统计不可区分的. 此外, 该系统还包括两种计算模式: 公开计算模式和秘密计算模式, 并且两种计算模式计算结果相同. 在正常模式下, 加密方可使用系统公钥, 选择随机数进行加密运算, 生成密文. 解密时要求各解密方运行秘密计算模式, 输入各自的私钥分享和密文, 计算解密分享. 当解密分享达到门限值时, 可使用抽取算法计算明文. -模拟模式可用于辅助安全性证明. Wee 分别基于 DDH 假设和大整数分解假设给 出该方案丰富的实例化. 该方法为构造门限密码提供了较好的思路, 而且基于单一密码组件可同时构造多个密码方案, 在应用实现上, 可通过模块化设计高效实现. 但是 Wee 在设计门限可提取哈希证明系统时, 只给出了静态模型下的形式化定义, 导致只能构造静态模型下的门限密码方案, 难以达到抵抗自适应模型下敌手的攻击. 针对该问题, Libert 和 Yung 在门限可提取哈希证明技术的启发下, 引入更强的密码组件 ABO-PS-THPS, 并基于该组件给出自适应模型下选择密文安全的门限加密的通用构造.

哈希签名范式 (the hash-and-sign paradigm) 是一种经典的签名通用构造技术  : 签名验证公钥为陷门函数 , 签名私钥为 . 在签名消息 时, 首先运算哈希算法计算 , 其中 是函数 的 某个像, 然后计算签名值为 . 验证签名 只需要简单验证 . 随后, Bellare 和 Rogaway  形式化上述签名通用构造思想, 叫做满域哈希技术 (full-domain hash), 并证明当 是一个陷门置换 (trapdoor permutation), 哈希函数 可模型为随机预言机 (random oracle) 时, 上述签名方案是选择消息攻击不可伪造的. 基于满域哈希技术设计签名的通用构造思想, 衍生出较多的门限签名算法.

De Santis 等人将陷门函数门限化, 提出了函数分享的概念. 该组件将陷门函数的陷门进行分割, 保证了门限数量个陷门分享才可进行函数求逆运算, 可完美地将满域哈希技术推广至门限版本, 用于门限签名的通用构造. 具体的门限签名构造思想如下: 签名验证公钥是函数描述, 各签名参与方掌握函数的陷门分享. 在签名消息 时, 首先将 哈希运算到函数的某个随机像, 各参与方使用自己的签名私钥 (陷门分享) 分别计算该像的原像分享, 最后通过组合算法可计算出签名值 (原像). 验证签名类似传统的满域哈希技术. 最后, 他们基于 RSA 假设实例化了函数分享, 获得了基于 RSA 假设的门限签名方案.

Wee 将满域哈希技术进一步扩展, 将底层的函数分享变换为门限可提取哈希函数, 设计了门限签名的通用构造. 在具体设计中, 他同样使用哈希函数将消息映射到一个具体 (实例) 空间, 签名参与方使用各自的签名私钥计算该消息的签名分享 (实例的证据分享), 最后使用提取算法可抽取签名值 (证据). 签名验证算法可利用证据验证实例来证明签名的正确性. 该方案巧妙地将单向关系 (one-way relation) 的可验证性用于门限签名的验证, 将签名的选择消息不可伪造安全性规约到单向关系的单向安全性上.

自适应模型下的门限密码

目前多数的门限密码方案主要考虑较弱的敌手模型——静态攻击模型. 在这种攻击模式下, 敌手必须在系统参数公开前就选定攻击的目标用户, 获得用户的私钥信息. 当系统参数公开后, 敌手不再具有攻击 其他用户的能力, 这种攻击模型并没有充分考虑敌手的攻击能力. 在实际攻击中, 敌手甚至可以在系统运行的任意时刻选择攻击的目标用户, 并根据获得的用户信息来决定下个目标用户, 这种攻击模型被称为自适应攻击模型. 自适应攻击模型严格地强于静态攻击模型 , 更加贴近于现实中敌手的攻击形式. 因此, 构造自适应模型下的门限密码方案比静态攻击下更加困难. 

在 Crypto 1999 上, Canetti 等人首先对构造自适应模型下安全的门限密码进行探索, 观察到主要困难点在于模拟器无法提前预测敌手准备攻击的目标用户. 而在可证明安全的角度, 模拟器需要模拟敌手的视角, 才能利用敌手的能力打破具体的底层困难假设. 当自适应的敌手询问任意用户私钥分享时, 模拟器需要掌握所有用户的隐私信息才能完成模拟, 但是困难问题需要嵌入到用户的隐私信息中, 模拟器无法获得全部用户的隐私信息, 也就无法完成模拟过程. 为了突破该困难, Canetti 等人给出了具体的尝试, 他们采用隐私信息擦除技术 (erasures) 配合 single inconsistent player 技术, 确保各个用户在系统参数公开前, 擦除自己的隐私信息. 因此, 敌手即使攻击了部分用户也无法获得用户的隐私信息, 保证了模拟器不需要向敌手提供用户的隐私信息, 并且可高效的模拟敌手的视角. 但是隐私信息擦除技术存在很大的弊端, 用户擦除的隐私信息在系统的后续过程中无法使用, 而且实现该技术本身就存在很多困难. 为了避免隐私信息擦除技术难实现的问题, Jarecki 和 Lysyanskaya 在 Eurocrypt 2000 上采用了承诺证明技术 (committed proof) 配合 persistently inconsistent player 技术, 避免了使用隐私信息擦除技术, 且在并发复合 (concurrent composition) 下构造了自适应模型下安全的门限密码, 但是该方案要求用户之间进行大量的交互运算.

Waters 在 Crypto 2009 上为构造基于身份加密方案, 首次提出了双系统证明技术 (dual system technique) , 也为设计自适应模型下安全的门限密码提供了新的思路. 双系统证明技术引入半功能密钥 (semi-functional secret key) 和半功能密文 (semi-functional ciphertext), 用于辅助安全性证明, 但不用于方案构造. 其中半功能密钥可以正常解密真实密文, 半功能密文可以被正常密钥解密, 但是半功能密钥不能解密半功能密文. 因此, 在敌手的询问用户私钥和构造挑战密文时, 模拟器可以生成半功能密钥和半功能密文, 并使用半功能密钥和半功能密文回应敌手询问, 模拟敌手视角. 由于半功能密钥不能解密半功能密文, 敌手拿到了半功能密钥, 对解密半功能密文没有任何帮助. 随后, 基于双系统证明技术, Libert 和 Yung 将 Boneh 等的门限基于身份加密转化为门限加密的思想, 根据 Boneh 和 Franklin 的身份加密方案, 设计了非交互的选择密文安全的门限加密方案, 并给出了该方案在自适应模型下的安全性证明.

在 TCC 2012 上, Libert 和 Yung 对 Wee  的门限可提取哈希证明的思想进行推广, 引入了密码组件 ABO-PS-THPS. 该组件可看做具有公开可验证 (publicly verifiable) 的可合理模拟证明的 (simulation-sound proofs) 门限哈希证明系统 (threshold hash proof systems). 该组件的每个证明都与 一个标记相关联, 具体包含了正常模式和 all-but-one 模式, 且正常选择的公共参数和 all-but-one 模式 下选择的参数不可区分, 其中正常模式用于方案构造, all-but-one 模式用于辅助安全性证明. 具体而言, 在 all-but-one 模式下非交互证明对于所有标签都是正确的, 除了在一个特定标记处设置陷门, 可对于不正确的实例进行模拟证明. 他们基于该组件构造了自适应模型下选择密文安全的门限加密方案. 在实例化方面, 利用 Groth-Sahai 证明系统 分别基于素数阶的双线性群上的 DLIN 假设和 symmetric external Diffie-Hellman (SXDH) 假设 实例化了门限加密方案.

基于格的门限密码

随着量子计算的快速发展, 基于传统数论假设的密码方案的安全性受到量子攻击的严重威胁, 构造抗量子安全的门限密码方案具有重要的意义. 因为目前不存在有效的量子算法打破格上的困难问题, 所以格密码被认为是能够抵抗量子攻击的. 同时, 格上的运算简单, 计算量小, 格密码与基于传统数论假设构造的密码方案相比, 实现效率较高.

在 TCC 2010 上, Bendlin 和 Damgård 首次构造了基于LWE 假设的选择明文安全的门限加密方案. 具体构造思想是基于 Regev 的加密方案的变种版本, 采用伪随机的秘密分享技术 (pseudorandom secret sharing) 切分私钥, 并根据 Peikert 给出的格上归约方法, 在通用复合模式 (universal composability) 下给出安全性证明. 但是该方案使用了特殊的切分消息技术导致在静态模型下, 限制了总用户的数量. 在自适应模型下, 要求各用户之间存在私密信道, 需要各用户之间进行交互运算, 并且该方案要求更大的模数, 密文尺寸较大.

  • BENDLIN R, DAMGÅRD I. Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems[C]. In: Theory of Cryptography—TCC 2010. Springer Berlin Heidelberg, 2010: 201–218.

基于多重加密构造门限加密的思想, Xie 等人对 Dodis 和 Katz 构造门限加密的密码组件进行弱化, 基于有损陷门函数设计了静态模型下选择密文安全的门限加密的通用构造, 并根据基于LWE 假 设实例化的有损陷门函数 , 构造了选择密文安全的门限加密方案. 但是该方案使用门限秘密共享方案切分消息和多重加密技术, 导致了公钥和密文尺寸与用户的数量线性相关.

  • XIE X, XUE R, ZHANG R. Efficient threshold encryption from lossy trapdoor functions[C]. In: Post-Quantum Cryptography—PQCRYPTO 2011. Springer Berlin Heidelberg, 2011: 163–178.

Zhang 等人通过对 Brakerski 的全同态加密方案进行修改, 摒弃了 Gentry  的标准压缩 (standard squashing) 和自举技术 (bootstrapping), 使用重线性化技术 (re-linearization) 大大减少了密文长度, 使用模量减少 (modulus reduction) 技术管理了噪声级别, 降低了解密复杂度, 并基于密钥同态性 (key-homomorphic property), 将该方案扩展至门限版本, 可保证多方协同完成解密.

  • BRAKERSKI Z, VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]. In: Advances in Cryptology—CRYPTO 2011. Springer Berlin Heidelberg, 2011: 505–524.

基于门限的基于身份加密转化技术, Bendlin 等人将格上两类重要的算法 (陷门生成算法和高斯抽样算法) 门限化, 将 Gentry 等人的基于身份加密方案和签名方案转化成门限版本, 并在通用复合模式下给出安全性证明, 分别构造了基于格的选择密文安全的门限加密和不可伪造的门限签名方案. 但是该方案在进行非交互的解密/签名过程之前, 需要各用户之间进行大量的交互运算.

  • BENDLIN R, KREHBIEL S, PEIKERT C. How to share a lattice trapdoor: Threshold protocols for signatures and (H)IBE[C]. In: Applied Cryptography and Network Security—ACNS 2013. Springer Berlin Heidelberg, 2013: 218–236.

Boneh等人根据全同态加密方案构造低轮数多方安全计算的思想,设计了()-门限密码, 并使用 Shamir 的门限秘密分享将门限值由 可转化成 , 并配合消除分母的技术 (clearing out the denominator) 保证了 LWE 的噪声增长可被界定. 基于上述技术思想, 他们提出了门限通用转化器 (universal thresholdizer) 的概念, 并基于该组件可将格上的加密和签名方案转化成门限版本, 获得基于格的门限加密方案和门限签名方案. 但是该方案使用了全同态加密、多方安全计算等技术, 导致方案效率不高.

  • BONEH D, GENNARO R, GOLDFEDER S, et al. A lattice-based universal thresholdizer for cryptographic systems[J]. IACR Cryptology ePrint Archive, 2017: 2017/251. http://eprint.iacr.org/2017/251

Part4门限密码的研究展望

6自适应模型下安全的门限密码的通用构造

目前设计选择密文安全的门限密码的通用构造方法, 主要通过多重加密技术 、门限的基于身份加密转换技术以及门限可提取哈希证明系统技术. 其中多重加密技术存在公钥尺寸和密文尺寸与用户数量线性相关的问题, 门限的身份加密方案本身就比较难以构造, 门限可提取哈希证明系统技术目前只能构造静态模型下的门限密码. 但是门限可提取哈希证明系统设计相对简单, 且同时可构造门限加密和门限签名方案. 因此, 探索基于门限可提取哈希证明系统设计自适应模型下安全的门限密码是未来较有意义的工作. 此外, 目前门限可提取哈希证明系统可基于 DDH 假设和整数分解假设实例化, 探索基于其他密码假设, 尤其是基于格上困难假设构造门限可提取哈希证明系统也具有重要意义.Boneh 等人基于全同态加密思想, 提出了门限通用转化器的概念, 可将格上的加密和签名方案直接门限化, 为构造门限密码提供了新的方向. 但是目前方案构造只能基于 LWE 假设, 而且效率不高. 探索基于其他密码假设构造的高效门限通用转化器, 可丰富自适应模型下的门限密码方案的构造.

7基于格的门限密码的高效设计

目前基于格的门限密码方案较少, 而且存在各种问题. 比如: Bendlin 和 Damgård , 以及 Bendlin 等人的门限密码方案需要用户之间进行大量交互运算, Xie 等人的门限加密方案只能在静态模型下可证明安全, 而且公钥尺寸和密文尺寸与用户数量线性相关, Boneh 等人的构造方法需要使用全同态加密技术, 实践效率较低. 因此, 基于格上困难假设在自适应模型下构造高效的非交互的门限密码方案是未来需要解决的问题.

8签名标准算法门限化

由于数字签名标准的广泛应用, 对其高效地门限化具有重要的应用意义. 但是目前对于数字签名标准的门限化都需要参与签名的用户进行大量的交互运算, 通信消耗非常大, 难以用于实际应用. 尽管 Gennaro 等人在 ACNS 2016 上设计的门限数字签名标准, 与之前的方案相比, 优化了参与签名的人数, 并 减少了用户之间交互轮数, 但是对于 ()-门限数字签名标准, 在签名阶段至少需要用户进行 7 轮交互. 如果对于 ()-门限数字签名标准, 在签名阶段用户交互轮数与门限值线性相关. 因此, 构造低轮数交互甚至非交互的门限数字签名标准是非常有意义且具有挑战性的研究工作.