Trapdoor Function


Trapdoor Function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

Trapdoor Function are widely used in cryptography.

RSA Assumption#

In this example, having the inverse of e modulo φ(n), the Euler's totient function of n, is the trapdoor:

f(x)=xe mod (n)

If the factorization is known,

  • φ(n) can be computed,
  • so then the inverse d of e can be computed d = e−1 mod φ(n),
  • and then given y = f(x) we can find x = yd mod n = xed mod n = x mod n.
Its hardness follows from RSA assumption.

More Information#

There might be more information for this subject on one of the following: