Threshold cryptosystem

A threshold cryptosystem, the basis for the field of threshold cryptography, is a cryptosystem in which the secret key is split into a number of pieces that are given to different parties.

Uses your system voice; voice and rate in settings.

≈ 8 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A threshold cryptosystem, the basis for the field of threshold cryptography, is a cryptosystem in which the secret key is split into a number of pieces that are given to different parties. Several parties (more than some threshold number) can then cooperate to use the cryptosystem.

More precisely, let n be the number of parties. A cryptosystem is called (t,n)-threshold, if at least t of these parties can cooperate to perform the desired operation (usually sign a message or decrypt a ciphertext), while any subset of fewer than t parties cannot.[1]

Threshold cryptography allows to store secrets in multiple locations to prevent the capture of the secret and the subsequent cryptanalysis of that system. This makes the method a primary trust sharing mechanism, besides its safety of storage aspects.

Constructions for threshold cryptosystems often combine an existing non-threshold cryptosystem with a secret sharing.

History

edit edit source

Perhaps the first system with complete threshold properties for a trapdoor function (such as RSA) and a proof of security was published in 1994 by Alfredo De Santis, Yvo Desmedt, Yair Frankel, and Moti Yung.[2]

Historically, only organizations with very valuable secrets, such as certificate authorities, the military, and governments made use of this technology. One of the earliest implementations was done in the 1990s by Certco for the planned deployment of the original Secure electronic transaction.[3] However, in October 2012, after a number of large public website password ciphertext compromises, RSA Security announced that it would release software to make the technology available to the general public.[4]

In March 2019, the National Institute of Standards and Technology (NIST) conducted a workshop on threshold cryptography to establish consensus on applications, and define specifications.[5] In July 2020, NIST published "Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives" as NIST IR 8214A[6]. In August 2022, NIST published an initial public draft for "Notes on Threshold EdDSA/Schnorr Signatures" as NIST IR 8214B.[7] In January 2023, NIST published an initial public draft for the "NIST First Call for Multi-Party Threshold Schemes" as NIST IR 8214C, followed by a second public draft in March 2025.[8]

Threshold signatures

edit edit source

In a (t,n) threshold signature scheme, a signing key is split into n shares, each share being given to a party. Any subset of at least t of the n parties behaving honestly can cooperate to jointly sign a message. On the other hand, every subset of fewer than t parties cannot forge a signature, even if they collude.

There is a trivial way to create a threshold signature scheme using any signature scheme. Each of the n parties generates its own secret signing key, and publishes the corresponding verification key. A party willing to sign a message simply signs it with its own individual key, and publishes its signature. A signature for the threshold signature scheme is a concatenation of (at least) t individual signatures, and can be verified by verifying the individual signatures one by one. The downside of this trivial approach is that the size of the signature and the time needed for verification grows linearly with t. Usually, it is desired that the size of the signature and the time needed for verification are constant in t and n.

Many existing signature schemes have been thresholdized, notably Schnorr signatures[9], ECDSA[10][11][12], and BLS[13].

Threshold decryption

edit edit source

Similarly to threshold signatures, public-key encryption schemes can be thresholdized, so that at least t parties must cooperate to decrypt a message.

Such threshold versions have been defined by the above and for the following schemes:

See also

edit edit source

References

edit edit source
  1. ^ Desmedt, Yvo; Frankel, Yair (1990). "Threshold cryptosystems". In Brassard, Gilles (ed.). Advances in Cryptology — CRYPTO' 89 Proceedings. Lecture Notes in Computer Science. Vol. 435. New York, NY: Springer. pp. 307–315. doi:10.1007/0-387-34805-0_28. ISBN 978-0-387-34805-6. Wikipedia revision 1336993883, retrieved 2026-11-21
  2. ^ Alfredo De Santis, Yvo Desmedt, Yair Frankel, Moti Yung: How to share a function securely. STOC 1994: 522-533 [1] Wikipedia revision 1336993883, retrieved 2026-11-21
  3. ^ Visa and Mastercard have just announced the selection of two companies -- CertCo and Spyrus, 1997-05-20, retrieved 2019-05-02. Wikipedia revision 1336993883, retrieved 2026-11-21
  4. ^ Tom Simonite (2012-10-09). "To Keep Passwords Safe from Hackers, Just Break Them into Bits". Technology Review. Retrieved 2020-10-13. Wikipedia revision 1336993883, retrieved 2026-11-21
  5. ^ "Threshold Cryptography". csrc.nist.gov. 2019-03-20. Retrieved 2019-05-02. Wikipedia revision 1336993883, retrieved 2026-11-21
  6. ^ Brandão, Luís T. A. N.; Davidson, Michael; Vassilev, Apostol (2020-07-07). "NIST Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives". Computer Security Resource Center. NIST. doi:10.6028/NIST.IR.8214A. Retrieved 2021-09-19. Wikipedia revision 1336993883, retrieved 2026-11-21
  7. ^ Brandão, Luís T. A. N.; Davidson, Michael (2022-12-08). "Notes on Threshold EdDSA/Schnorr Signatures". Computer Security Resource Center. NIST. doi:10.6028/NIST.IR.8214B.ipd. Retrieved 2025-10-21. Wikipedia revision 1336993883, retrieved 2026-11-21
  8. ^ Brandão, Luís T. A. N.; Peralta, Rene (2025-03-27). "NIST First Call for Multi-Party Threshold Schemes". Computer Security Resource Center. NIST. doi:10.6028/NIST.IR.8214C.2pd. Retrieved 2025-10-21. Wikipedia revision 1336993883, retrieved 2026-11-21
  9. ^ Komlo, Chelsea; Goldberg, Ian (2021). "FROST: Flexible Round-Optimized Schnorr Threshold Signatures". In Dunkelman, Orr; Jacobson, Michael J. Jr.; O'Flynn, Colin (eds.). Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 12804. Cham: Springer International Publishing. pp. 34–65. doi:10.1007/978-3-030-81652-0_2. ISBN 978-3-030-81652-0. S2CID 220794784. Wikipedia revision 1336993883, retrieved 2026-11-21
  10. ^ Green, Marc; Eisenbarth, Thomas (2015). "Strength in Numbers: Threshold ECDSA to Protect Keys in the Cloud" (PDF). IACR. Wikipedia revision 1336993883, retrieved 2026-11-21
  11. ^ Gennaro, Rosario; Goldfeder, Steven; Narayanan, Arvind (2016). "Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security" (PDF). Applied Cryptography and Network Security. ACNS 2016. doi:10.1007/978-3-319-39555-5_9. Wikipedia revision 1336993883, retrieved 2026-11-21
  12. ^ Gągol, Adam; Straszak, Damian; Świętek, Michał; Kula, Jędrzej (2019). "Threshold ECDSA for Decentralized Asset Custody" (PDF). IACR. Wikipedia revision 1336993883, retrieved 2026-11-21
  13. ^ Bacho, Renas; Loss, Julian (2022). "On the Adaptive Security of the Threshold BLS Signature Scheme". Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS '22). Los Angeles, CA, USA: Association for Computing Machinery. pp. 193–207. doi:10.1145/3548606.3560656. ISBN 9781450394505. Wikipedia revision 1336993883, retrieved 2026-11-21
  14. ^ Ivan Damgård, Mads Jurik: A Length-Flexible Threshold Cryptosystem with Applications. ACISP 2003: 350-364 Wikipedia revision 1336993883, retrieved 2026-11-21
  15. ^ Ivan Damgård, Mads Jurik: A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System. Public Key Cryptography 2001: 119-136 Wikipedia revision 1336993883, retrieved 2026-11-21
  16. ^ Nishide, Takashi; Sakurai, Kouichi (2011). "Distributed Paillier Cryptosystem without Trusted Dealer". In Chung, Yongwha; Yung, Moti (eds.). Information Security Applications. Lecture Notes in Computer Science. Vol. 6513. Berlin, Heidelberg: Springer. pp. 44–60. doi:10.1007/978-3-642-17955-6_4. ISBN 978-3-642-17955-6. Wikipedia revision 1336993883, retrieved 2026-11-21
Theory Standardization Topics

Text derived from https://en.wikipedia.org/w/index.php?oldid=1336993883 under CC BY-SA 4.0; modifications have been made.

Words in each sectionHistoryHistoryHistory: 226 words226Threshold signaturesThreshold signaturesThreshold signatures: 215 words215Threshold decryptionThreshold decryptionThreshold decryption: 56 words56See alsoSee alsoSee also: 18 words18
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

References

  1. ↩Wikipedia “Threshold cryptosystem” revision 1336993883 · retrieved 2026-10-20 publication date (×2) · confidence 0.95 revision URL

Provenance

snapshot enwiki-001336993883 · captured 2026-02-06 · ledger · version history

Cite this page as: encyclopegia.org, “Threshold cryptosystem”, snapshot enwiki-001336993883. https://encyclopegia.org/a/threshold-cryptosystem