Talk:Trapdoor function

Anyone able to sort out trapdoor one way function? What precisely is the difference between trapdoor function and one way function? I feel we should be told.

Charles Matthews 17:58, 4 Apr 2004 (UTC)

---

Perhaps not much ordinary usage, but considerable in theory and practice. Let's say we find a function which can be computed in one way only. Some of the large class of NP algorithms can be used as a starting point. More simple, we can just consider large integer multiplication.

Take (p)(n) = m. If m is large enough, it will be impossible (in practice) to recover p or n. If p and n were prime, their values would be unique, but still unavailable in practice. On the other hand, if a one-way function has a trapdoor (to continue the example or something similar to it, consider RSA) then only those who have been told about the trapdoor (ie, who have the key) can recover p and n.

Merkle proposed a one way function (trapdoor type) about '77 which turned out to not be a one way function after all, trapdoor or not. Adi Shamir found a way of reversing it (on an Apple II, no less) in almost no time. It was one of the knapsack group, which more or less explains why problems in this group aren't being investigated much any more.

So, some one-way functions are known which have trapdoors (some of which are provably so in some sense -- ie the one-time pad algorithm), some one-way functions are known which are non-reversible in current practice (sufficienty large interger factorization) and thus may have no trapdoors, and some which used to be thought to be one-way functions are known to not be so.

Does this help? ww 15:38, 5 Apr 2004 (UTC)

Yes. If I take it correctly, it says these are 'jargon' rather than very rigorous terms; and that in this case it matters. So perhaps all three topics belong in an article like one way functions and trapdoors, dishing the dirt.

Charles Matthews 16:47, 5 Apr 2004 (UTC)

The distinction is indeed somewhat informal, if not jargon. The problem is that the field of interest (usually crypto or something similar) has few proofs (of existence or any other sort) prompting/requiring the use of rigorous language. Crypto is an odd field in that few engineering disciplines are required to produce designs which can withstand attack by intelligent malevolent Opposition, and furthermore using methods and techniques not now known (at least publicly) to anyone.

I like the idea of an article on one-way functions and in such an article the trapdoor subset would naturally be discussed. The problem is that I can't even begin to put one together given my limited range of maths expertise. Perhaps you could have a go at an initial dish? ww 20:09, 8 Apr 2004 (UTC)

---

Fifteen years later...

A trapdoor function is what's talked about on this page. It's easy to multiply two huge primes together, and takes a very long time to do the reverse. But it is possible to do the reverse.

A true one way function CANNOT be reversed. Take a work of Shakespeare and replace every letter with "X". Now take your result, and using only it, recover the original work. Cryptographic hashes are an example of a one way function. Any binary object can be hashed, but you cannot recover the original object from just a hash, even if you have infinite computing power. 192.189.128.13 (talk) 17:18, 10 September 2019 (UTC)

Corrections needed about candidate trapdoor functions

Hey all, "discrete log" and "prime factorization" are not known to be trapdoor functions, and probably aren't. There is no known way to efficiently compute discrete logs, and there is no (known) single "trapdoor" which will help you factor integers.

A candidate example of a trapdoor function (though "permutation" is more accurate than "function") is RSA, where (n,e) allows one to compute the function f(x)=x^e mod n, and the trapdoor is d = e^{-1} mod phi(n) which allows one to compute f^{-1}(y) = y^d mod n.

Another candidate trapdoor permutation is squaring mod n, taken over the domain of quadratic residues mod n, where n is a Blum integer (i.e., the product of two primes that are both 3 mod 4). The public information is simply n, which allows one to compute f(x) = x^2 mod n. The secret information is the factorization of n, which can be used to find all four square roots of any y mod n. Exactly one of these square roots is itself a square, and this can also be found using the factorization of n.

These two are really the best-known and only tested candidate trapdoor permutations of which I'm aware. --Chris Peikert 02:59, 17 Nov 2004 (UTC)

Definition?

There is no mathematical definition here, though there is a good intuitive definition. Not being strictly a cryptographer, I'd be more comfortable if someone else offered one. Any ideas guys? 71.194.163.223 20:50, 10 July 2007 (UTC)

Here is what I have come up with:

Let F be a family of one-way functions, indexed by I such that $g(i)=f(i)$ may be easily computed, as well as $g'(i)=f^{-1}(i)$. A party randomly selects i and likewise obtains f_i. f_i is the trapdoor function, i is the trapdoor.

Diffie-Hellman problem does not give rise to trapdoor permutation

The article states "However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie-Hellman problem (CDH) and/or its decisional variant are used." I am not aware of any trapdoor permutation that can be constructed using CDH. Of course, one can use it to construct the DH encryption scheme, but that is not a trapdoor permutation (technically, the difference is that an encryption scheme may be randomized while a trapdoor permutation must be deterministic).

Dominique Unruh (talk) 13:44, 5 February 2008 (UTC)

Elliptic Curve / logarithm stuff confusing to layfolk

Hi. The article seems to my far-from-expert reading to imply (state?) that Elliptic Curve 'crypto stuff' isn't a 'proper' trapdoor function (because something about discrete logarithms). That's a wishy-washy sentence because it's not clear to me. I'm confused because many sites refer (improperly?) to ECC implementing a trapdoor function, and my intuitive (but wrong?) sense that that must be true, unless 'trapdoor function' has a more esoteric definition than is 'commonly understood' -- in which case this article needs to explain that distinction more simply and clearly. Cheers. 92.27.136.85 (talk) 11:41, 14 July 2016 (UTC)