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)

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)