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$
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$
  • $\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 '15 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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