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 less 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 ciphertext and the subsequent cryptanalysis on that ciphertext. Most often the secrets that are "split" are the secret key material of a public key cryptography key pair or the ciphertext of stored password hashes.[ citation needed ]

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 requires smaller keys compared to non-EC cryptography to provide equivalent security.

Public-key cryptography user Facebook key

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.

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 mathematical scheme for demonstrating the authenticity of digital messages or documents

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

Malleability is a property of some cryptographic algorithms. An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext , it is possible to generate another ciphertext which decrypts to , for a known function , without necessarily knowing or learning .

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:

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.

IEEE P1363 is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public-key cryptography. It includes specifications for:

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.

Cryptovirology is a field that studies how to use cryptography to design powerful malicious software. The field was born with the observation that public-key cryptography can be used to break the symmetry between what an antivirus analyst sees regarding malware and what the attacker sees. The antivirus analyst sees a public key contained in the malware whereas the attacker sees the public key contained in the malware as well as the corresponding private key since the attacker created the key pair for the attack. The public key allows the malware to perform trapdoor one-way operations on the victim's computer that only the attacker can undo.

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

Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext.

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 techniques for secure communication in the presence of adversaries

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.

The following outline is provided as an overview of and topical guide to cryptography:

Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.

Post-Quantum Cryptography Standardization is a project by NIST to standardize post-quantum cryptography. 23 signature schemes were submitted, 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. 26 of these have advanced to the second round.


  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 2019-05-02.
  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)