Threshold cryptosystem

Last updated

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.



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. [1]

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. [2] 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. [3]

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. [4] In November, NIST published a draft roadmap "towards the standardization of threshold schemes for cryptographic primitives" as NISTIR 8214A. [5] [6]


Let 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.[ citation needed ]


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: [7]


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.

See also

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.

Public-key cryptography Cryptographic system with public and private keys

Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys: public keys, which may be disseminated widely, and private keys, which are known only to the owner. The generation of such keys depends on cryptographic algorithms based on mathematical problems to produce one-way functions. Effective security only requires keeping the private key private; the public key can be openly distributed without compromising security.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at GCHQ, by the English mathematician Clifford Cocks. That system was declassified in 1997.

In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.

The Digital Signature Algorithm (DSA) is a Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant of the Schnorr and ElGamal signature schemes.

Digital signature

A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very strong reason to believe that the message was created by a known sender (authentication), and that the message was not altered in transit (integrity).

A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.

Articles related to cryptography include:

An adaptive chosen-ciphertext attack is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, then uses the results to distinguish a target ciphertext without consulting the oracle on the challenge ciphertext, in an adaptive attack the attacker is further allowed adaptive queries to be asked after the target is revealed. It is extensing the indifferent (non-adaptive) chosen-ciphertext attack (CCA1) where the second stage of adaptive queries is not allowed. Charles Rackoff and Dan Simon defined CCA2 and suggested a system building on the non-adaptive CCA1 definition and system of Moni Naor and Moti Yung.

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message , and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length. This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy means that the ciphertext reveals no information at all about the plaintext, whereas semantic security implies that any information revealed cannot be feasibly extracted.

Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth.

In cryptography a universal one-way hash function, is a type of universal hash function of particular importance to cryptography. UOWHF's are proposed as an alternative to collision-resistant hash functions (CRHFs). CRHFs have a strong collision-resistance property: that it is hard, given randomly chosen hash function parameters, to find any collision of the hash function. In contrast, UOWHFs require that it be hard to find a collision where one preimage is chosen independently of the hash function parameters. The primitive was suggested by Moni Naor and Moti Yung and is also known as "target collision resistant" hash functions; it was employed to construct general digital signature schemes without trapdoor functions, and also within chosen-ciphertext secure public key encryption schemes.

Homomorphic encryption A form of encryption that allows computation on ciphertexts

Homomorphic encryption is a form of encryption allowing one to perform calculations on encrypted data without decrypting it first. The result of the computation is in an encrypted form, when decrypted the output is the same as if the operations had been performed on the unencrypted data.

The Damgård–Jurik cryptosystem is a generalization of the Paillier cryptosystem. It uses computations modulo where is an RSA modulus and a (positive) natural number. Paillier's scheme is the special case with . The order of can be divided by . Moreover, can be written as the direct product of . is cyclic and of order , while is isomorphic to . For encryption, the message is transformed into the corresponding coset of the factor group and the security of the scheme relies on the difficulty of distinguishing random elements in different cosets of . It is semantically secure if it is hard to decide if two given elements are in the same coset. Like Paillier, the security of Damgård–Jurik can be proven under the decisional composite residuosity assumption.

Cryptography Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of third parties called adversaries. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages; various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation are central to modern cryptography. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, electrical engineering, communication science, and physics. Applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography.

Post-Quantum Cryptography Standardization is a program and competition by NIST to update their standards to include post-quantum cryptography. It was announced at PQCrypto 2016. 23 signature schemes and 59 encryption/KEM schemes were submitted by the initial submission deadline at the end of 2017 of which 69 total were deemed complete and proper and participated in the first round. Seven of these, of which 3 are signature schemes, have advanced to the third round, which was announced on July 22, 2020.


  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". 2019-03-20. Retrieved 2019-05-02.
  5. Computer Security Division, Information Technology Laboratory (2018-07-25). "NIST Releases Draft NISTIR 8214 for Comment | CSRC". CSRC | NIST. Retrieved 2020-03-24.
  6. Brandão, Luís T. A. N.; Davidson, Michael; Vassilev, Apostol (2019-11-08). "Towards NIST Standards for Threshold Schemes for Cryptographic Primitives: A Preliminary Roadmap".Cite journal requires |journal= (help)
  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).Cite journal requires |journal= (help)
  13. Gennaro, Rosario; Goldfeder, Steven; Narayanan, Arvind (2016). "Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security" (PDF).Cite journal requires |journal= (help)
  14. Gągol, Adam; Straszak, Damian; Świętek, Michał; Kula, Jędrzej (2019). "Threshold ECDSA for Decentralized Asset Custody" (PDF).Cite journal requires |journal= (help)CS1 maint: date and year (link)