Talk:Trapdoor function
From Wikipedia, the free encyclopedia
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.
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||
|
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)