Trapdoor function
|
|
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, there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider taking an engine apart. It would not be very easy to put it together again unless of course you had the assembly instructions. These instructions would be the trapdoor that allow you to return the engine to its original state. A mathematical example would be the multiplication of two large prime numbers. Finding and verifying two large primes is easy, as is their multiplication. But factoring the resultant product can be very difficult.
Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric encryption techniques by Diffie, Hellman, and Merkle. Indeed, Diffie and Hellman first 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 knapsack problem. This turned out -- rather quickly -- to be unsuitable.
As of 2004, 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 factorisation.
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. Nevertheless, the hardness of computing discrete logs underlies the security of the ElGamal cryptosystem and DSA.
See also
References
- W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), pp644–654 (1976). PDF version of the paper (http://www.cs.rutgers.edu/~tdnguyen/classes/cs671/presentations/Arvind-NEWDIRS.pdf)