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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Have you read the associated Wikipedia Article? If so, what parts of it are you having difficulty with? $\endgroup$
    – Reid
    Aug 30, 2013 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, 2013 at 20:27

2 Answers 2

Reset to default
27
$\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.

Improve this answer
$\endgroup$
2
  • 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, 2015 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, 2016 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$ .

Improve this answer
$\endgroup$

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.