Trapdoor function
Encyclopedia
A trapdoor function is a function
that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse
) without special information, called the "trapdoor". Trapdoor functions are widely used in cryptography
.
In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider a padlock
and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key is the trapdoor.
Trapdoor functions came to prominence in cryptography
in the mid-1970s with the publication of asymmetric (or public key) encryption techniques by Diffie
, Hellman
, and Merkle
. Indeed, Diffie and Hellman coined the term (Diffie and Hellman, 1976). Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. This turned out -- rather quickly -- to be unsuitable.
, the best known trapdoor function (family) candidates are the RSA and Rabin
families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorization.
Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve
) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logs. However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie–Hellman problem (CDH) and/or its decisional variant are used. The semantically secure version of the ElGamal Cryptosystem relies on the decision Diffie–Hellman problem (DDH). The Digital Signature Algorithm
is based on CDH in a prime order subgroup.
A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably and this is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
) without special information, called the "trapdoor". Trapdoor functions are widely used in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider a padlock
Padlock
Padlocks are portable locks used to protect against theft, vandalism, sabotage, unauthorized use, and harm. They are designed to protect against some degree of forced and surreptitious entry.- History :...
and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key is the trapdoor.
Trapdoor functions came to prominence in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
in the mid-1970s with the publication of asymmetric (or public key) encryption techniques by Diffie
Whitfield Diffie
Bailey Whitfield 'Whit' Diffie is an American cryptographer and one of the pioneers of public-key cryptography.Diffie and Martin Hellman's paper New Directions in Cryptography was published in 1976...
, Hellman
Martin Hellman
Martin Edward Hellman is an American cryptologist, and is best known for his invention of public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle...
, and Merkle
Ralph Merkle
Ralph C. Merkle is a researcher in public key cryptography, and more recently a researcher and speaker on molecular nanotechnology and cryonics...
. Indeed, Diffie and Hellman coined the term (Diffie and Hellman, 1976). Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. This turned out -- rather quickly -- to be unsuitable.
, the best known trapdoor function (family) candidates are the RSA and Rabin
Rabin cryptosystem
The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization, which is...
families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorization.
Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logs. However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie–Hellman problem (CDH) and/or its decisional variant are used. The semantically secure version of the ElGamal Cryptosystem relies on the decision Diffie–Hellman problem (DDH). The Digital Signature Algorithm
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...
is based on CDH in a prime order subgroup.
A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably and this is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.