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 July 2020, NIST published "Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives" as NISTIR 8214A. [5]
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. [6]
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.
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]
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, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.
Ralph C. Merkle is an American computer scientist and mathematician. He is one of the inventors of public-key cryptography, the inventor of cryptographic hashing, and more recently a researcher and speaker on cryonics.
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.
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.
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).
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.
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.
CertCo, Inc., was a financial cryptography startup spun out of Bankers Trust in the 1990s. The company pioneered a risk management approach to cryptographic services. It had offices in New York City and Cambridge, Massachusetts. It offered three main public key infrastructure (PKI) based products: an Identity Warranty system ; an electronic payment system ; and an Online Certificate Status Protocol (OCSP) responder for validating X.509 public key certificates. It went out of business in Spring 2002 never having found a wide market for its products despite filing a number of patents and developing new technology.
Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted.
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.
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.
Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical 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:
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with popular algorithms currently used in the market is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.
Dr. Yvo G. Desmedt is the Jonsson Distinguished Professor at the University of Texas at Dallas, and in addition Chair of Information Communication Technology at University College London. He was a pioneer of threshold cryptography and is an International Association for Cryptologic Research Fellow. He also made crucial observations that were used in the cryptanalysis of the Merkle–Hellman knapsack cryptosystem and observed properties of the Data Encryption Standard which were used by Eli Biham and Adi Shamir when they invented Differential Cryptanalysis.
Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography.
The RSA Conference (RSAC) Award for Excellence in Mathematics is an annual award. It is announced at the annual RSA Conference in recognition of innovations and contributions in the field of cryptography. An award committee of experts, which is associated with the Cryptographer's Track committee at the RSA Conference (CT-RSA), nominates to the award persons who are pioneers in their field, and whose work has had applied or theoretical lasting value; the award is typically given for the lifetime achievements throughout the nominee's entire career. Nominees are often affiliated with universities or involved with research and development in the information technology industry. The award is cosponsored by the International Association for Cryptologic Research.
