3
$\begingroup$

Trapdoor is a function taking as input $x$ and givings us output $y$ where it is hard to convert $y\rightarrow x $ back without knowing a secret $s$.

I think that $y$ is an encryption of $x$ under a some certain key($s$ or its associated public key).

So is trapdoor encryption?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ There's another answer at crypto.stackexchange.com/questions/7881/… $\endgroup$ – Paul Uszak Jun 17 '17 at 21:07
  • $\begingroup$ @PaulUszak That question & answer mainly focuses on the difference between trapdoor based algorithms such as RSA and AES (in case somebody decides this could be duplicate - I don't think it is). It is certainly a related Q/A though. $\endgroup$ – Maarten Bodewes♦ Jun 18 '17 at 12:14
  • $\begingroup$ Trapdoor functions can also be used for creating other algorithms such as RSA signature generation (which also relies on modular exponentiation but it certainly doesn't perform encryption or describe a cipher). $\endgroup$ – Maarten Bodewes♦ Jun 18 '17 at 12:18
  • $\begingroup$ Is it encryption? Yes. Is it secure encryption? Depends on your security definition (but for all useful purposes, no, because it is deterministic). $\endgroup$ – fkraiem Jun 20 '17 at 10:52
5
$\begingroup$

A trapdoor function doesn't have the security requirements of an encryption function. If you directly use a trapdoor for encryption you open yourself up to related key attacks, known plaintext attacks, malleability attacks and a whole host of other attacks.

Trapdoor functions are used as a single piece of a larger encryption function that handles all these issues.

|improve this answer
$\endgroup$
2
$\begingroup$

Trapdoor functions are a special kind of one-way function, where it is possible to calculate the reverse function with the knowledge of some secret value, which is called the trapdoor. If a trapdoor function is also a permutation (bijective, from a set to itself), then it's called a trapdoor permutation.

When considering encryption, we need an encryption algorithm $E_k(m)$ with message $m$ and key $k$ and a decryption algorithm $D_{k'}(c)$ with ciphertext $c$ and key $k'$, where $D_{k'}(E_k(m)) = m$ holds (most often it has to hold for all values, sometimes it is acceptable if this doesn't hold for a negligible amount of messages).

So in order to fullfill the definition of an encryption scheme, the trapdoor has to be injective for almost all values. This is similar to the term statistically injective (e.g. in How to Use Indistinguishability Obfuscation: Deniable Encryption, and More by Sahai and Waters, 2013). Otherwise it would be impossible to decrypt again and get back the input message. So for encryption schemes, trapdoor permutations are more interesting than trapdoor functions in general.

But as @Daffy correctly pointed out: Security definitions for encryption schemes, e.g. IND-CPA or IND-CCA, do not directly apply to trapdoor functions or trapdoor permutations. But those can be used to construct encryption schemes, e.g. public-key encryption schemes insolve some kind of trapdoor function.

But the trapdoor function itself does not necessarily fullfill the necessary security definitions. Here's an example:

  • In RSA the modular exponentiation is a trapdoor oneway function.
  • RSA is not IND-CPA secure.
  • With the padding scheme OAEP we get an IND-CCA secure encryption scheme in the random oracle model
|improve this answer
$\endgroup$
0
$\begingroup$

Let $f$ be hard to invert. Given $y=f(x)$, the value $x$ is unknown to an adversary (who cannot invert $f$).

This is why one might assume that "$y$ is an encryption of $x$".

However, this is not the case in general: Define $g(x_1,x_2)=(f(x_1),x_2)$. Then $g$ is hard to invert if $f$ is, but $y=g(x)$ reveals information about $x=(x_1,x_2)$.

|improve this answer
$\endgroup$
  • $\begingroup$ This answer does not adress the question about trapdoors and encryption at all. The example is related to oneway functions in their basic form. $\endgroup$ – tylo Jun 20 '17 at 10:49
  • $\begingroup$ The example shows that one-way functions in general reveal information about their inputs and thus cannot meet any meaningful security definition for encryption schemes. This carries over to trapdoor functions: In the above example it does not matter if f is invertible with the knowledge of some secret s. $\endgroup$ – p-steuer Jun 20 '17 at 12:56

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.