Trapdoor function

A trapdoor function is a function that is easy to compute in one direction, and difficult to compute in the opposite direction (finding its inverse) without special information (the trapdoor) termed a "key". Trapdoor functions are widely used in cryptography.

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 candidates for such functions are prime factorisation (in the RSA algorithm), the discrete logarithm problem (in the ElGamal algorithm or in the elliptic curve problem, although the last is rather newer than the others).

References

• W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6): 644-654 (1976)