Misplaced Pages

A threshold cryptosystem, the basis for the field of threshold cryptography, is a cryptosystem that protects information by encrypting it and distributing it among a cluster of fault-tolerant computers. The message is encrypted using a public key, and the corresponding private key is shared among the participating parties. With a threshold cryptosystem, in order to decrypt an encrypted message or to sign a message, several parties (more than some threshold number) must cooperate in the decryption or signature protocol.

History

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.

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. 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.

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. In July 2020, NIST published "Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives" as NISTIR 8214A.

Methodology

Let ${\displaystyle n}$ be the number of parties. Such a system is called (t,n)-threshold, if at least t of these parties can efficiently decrypt the ciphertext, while fewer than t have no useful information. Similarly it is possible to define a (t,n)-threshold signature scheme, where at least t parties are required for creating a signature.

Application

The most common application is in the storage of secrets in multiple locations to prevent the capture of the secret and the subsequent cryptanalysis of that system. Most often the secrets that are "split" are the secret key material of a public key cryptography or of a Digital signature scheme. The method primarily enforces the decryption or the signing operation to take place only if a threshold of the secret sharer operates (otherwise the operation is not made). This makes the method a primary trust sharing mechanism, besides its safety of storage aspects.

Derivatives of asymmetric cryptography

Threshold versions of encryption or signature schemes can be built for many asymmetric cryptographic schemes. The natural goal of such schemes is to be as secure as the original scheme. Such threshold versions have been defined by the above and by the following:

• Damgård–Jurik cryptosystem
• DSA
• ElGamal
• ECDSA (these are used in protecting Bitcoin wallets)
• Paillier cryptosystem
• RSA
• Schnorr signature

See also

• Broadcast encryption
• Distributed key generation
• Secret sharing
• Secure multi-party computation
• Shamir's Secret Sharing
• Threshold (disambiguation)

References

1. Alfredo De Santis, Yvo Desmedt, Yair Frankel, Moti Yung: How to share a function securely. STOC 1994: 522-533
2. Visa and Mastercard have just announced the selection of two companies -- CertCo and Spyrus, 1997-05-20, retrieved 2019-05-02.
3. Tom Simonite (2012-10-09). "To Keep Passwords Safe from Hackers, Just Break Them into Bits". Technology Review. Retrieved 2020-10-13.
4. "Threshold Cryptography". csrc.nist.gov. 2019-03-20. Retrieved 2019-05-02.
5. Brandao, Luis 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. S2CID 221350433. Retrieved 2021-09-19.
6. 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.
7. Jonathan Katz, Moti Yung:Threshold Cryptosystems Based on Factoring. ASIACRYPT 2002: 192-205
8. Ivan Damgård, Mads Jurik: A Length-Flexible Threshold Cryptosystem with Applications. ACISP 2003: 350-364
9. 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
10. Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin: Robust Threshold DSS Signatures. EUROCRYPT 1996: 354-371
11. "Distributed Privacy Guard (DKGPG)". 2017.
12. Green, Marc; Eisenbarth, Thomas (2015). "Strength in Numbers: Threshold ECDSA to Protect Keys in the Cloud" (PDF). IACR.
13. 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.
14. Gągol, Adam; Straszak, Damian; Świętek, Michał; Kula, Jędrzej (2019). "Threshold ECDSA for Decentralized Asset Custody" (PDF). IACR.
15. 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.
16. 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.

• Public-key cryptography