4
$\begingroup$

From Wikipedia:

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".

What's the difference between this and encryption functions like AES? Are all encryption functions instances of trapdoor functions? Are there any situations in cryptography were we want a trapdoor function instead of an encryption function?

$\endgroup$

1 Answer 1

8
$\begingroup$

Typically, trapdoor functions are used in asymmetric cryptography. For instance, if you have a RSA public key $(n,e)$, it is easy to compute a cipher text $c = Pad(m)^e\mod n$, but hard to get back to $Pad(m)$ from $c$ even if you have the public key. In order to easily reverse the operation you need the corresponding private key $d = e^{-1}\mod\phi(n)$. The reason RSA is a trapdoor function in this sense, is because it is based on the hardness of the Integer Factorization Problem. You can't calculate the private exponent $d$ unless you know $\phi(n)$, and you can't calculate $\phi(n)$ unless you know the prime factors of $n$.

AES and other symmetric ciphers are not trapdoor functions in this sense. You are only able to compute $c = AES_k(m)$ if you got the key $k$, but if you got this key it is equally easy to compute $m = AES_k^{-1}(c)$

$\endgroup$
1
  • 1
    $\begingroup$ In fact we believe that the computation of the $eth$ root $\mod \phi{(n)}$ is equivalent to factoring. This is not a Theorem. $\endgroup$
    – 111
    Apr 22, 2015 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.