6
$\begingroup$

I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions:

  • What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in cryptography?
  • Is a hash function considered to be a trapdoor function, or is a trapdoor function some kind of encryption?
  • What is the result of trapdoor function, a numeric or a string result?
  • What does trapdoor itself mean? Does it mean a private key is used in a trapdoor function or does it point to the string after transmission?

It would be nice if you could explain with examples.

$\endgroup$
  • 4
    $\begingroup$ Have you read the associated Wikipedia Article? If so, what parts of it are you having difficulty with? $\endgroup$ – Reid Aug 30 '13 at 18:17
  • $\begingroup$ yes I did, but I want to know if this function type of encryption mechanisms, and if I want to convert word(string) using trapdoor function what is the result? , and Is hash function consider trapdoor function? $\endgroup$ – shsa Aug 30 '13 at 20:27
21
$\begingroup$

A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently. That is, if $f$ is a trapdoor function, then $y = f(x)$ is easy to compute, but $x = f^{-1}(y)$ is hard to compute without some special knowledge $k$. Given $k$, then it is easy to compute $y = f^{-1}(x, k)$. The Wikipedia article also contains a straight-forward explanation.

The analogy to a "trapdoor" is something like this: It's easy to fall through a trapdoor, but it's very hard to climb back out and get to where you started unless you have a ladder.

A hash function is not a trapdoor function because it is not reversible. Instead, it's called a one-way function. A one-way function is similar to a trapdoor function in that it's easy to compute both and it's very hard to reverse both, but there is no special key that allows you to reverse the one-way function.

To compare the definitions of one-way and trapdoor functions, I double-checked teaching sources I'm familiar with, including:

They all categorize (sometimes implicitly) trapdoor functions as a subset of one-way functions: Trapdoors are a one-way function with the extra restriction that they have a secret for calculating the inverse.

For example: RSA is a one-way trapdoor function, but SHA-1 is just a one-way hash function. Discrete exponentiation is also (supposedly) just a one-way function, since there's no key information about the group that can be used to calculate the discrete logarithm efficiently.

That said, on a pragmatic note I have noticed that common Internet usage often mixes the terms "one-way" and "trapdoor" interchangeably, which no doubt causes confusion.

$\endgroup$
  • 2
    $\begingroup$ In you explanantion of a One-way function, shouldn't it be: x=f^-1 (y,k) instead of y=f^-1(y,k) ? $\endgroup$ – user29705 Dec 8 '15 at 13:12
  • $\begingroup$ From Wikipedia: difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". So, I think trapdoor is actually a secret way to finding the inverse. $\endgroup$ – Ujjwal Ojha Jul 25 '16 at 5:55
2
$\begingroup$

As far as we know, both one-way and pseudorandom permutations do not help us to get public key encryption schemes. The way we obtain these is by using trapdoor functions (also known as trapdoor permutations). These are keyed collections with the following property: there are two keys for each function: one to compute it in the forward direction and one to compute it in the reverse direction (invert it). Now the key for the forward direction can be given to the adversary (not inside a black box but really given to him) and still this will not help him invert the function (that is, the function is a one-way permutation to someone not knowing the invertion key or “trapdoor”).

Definition 1 (Trapdoor functions.). A trapdoor function collection is a collection F of finite functions such that every $f \in F$ is a one-to-one function from some set $S_f$ to a set $T_f$ .

$\endgroup$

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.