Trapdoor function

A trapdoor function is a function that is easy to compute in one direction, and difficult to compute in the opposite direction (its inverse. Trapdoor functions are often used in the science of encryption and in encryption programs such as PGP.

Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric encryption techniques by Diffie, Hellman, and Merkle. Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. In particular, the knapsack problem (in any of several flavors) turned out -- rather quickly -- to not be a trapdoor function. Currently, the best known such functions are prime factoring (in the RSA algorithm), the discrete logarithm problem (in the ElGamal algorithm and some others) and the elliptic curve problem. The last is rather newer than the others and has not been quite as useful as had been initially thought.