TOPICS
Search

Trapdoor One-Way Function


Informally, a function f:{0,1}^(l(n))×{0,1}^n->{0,1}^(m(n)) is a trapdoor one-way function if

1. It is a one-way function, and

2. For fixed public key y in {0,1}^(l(n)), f(x,y) is viewed as a function f_y(x) of x that maps n bits to m(n) bits. Then there is an efficient algorithm that, on input <y,f_y(x),z> produces x^' such that f_y(x^')=f_y(x), for some trapdoor key z in {0,1}^(k(n)).

f is a trapdoor one-way hash function if f is also a one-way hash function, i.e., if additionally

3. Given M and f(M), it is hard to find a message M^'!=M such that f(M^')=f(M).

It is not known if a trapdoor one-way function can be constructed from any one-way function.

An example of a trapdoor one-way function is factorization of a product of two large primes. While selecting and verifying two large primes and multiplying them together is easy, factoring the resulting product is (as far as is known) very difficult. This is the basis for RSA encryption, which is conjectured to be trapdoor one-way.


See also

One-Way Function, RSA Encryption, Trapdoor One-Way Hash Function

Explore with Wolfram|Alpha

References

Gardner, M. "Trapdoor Ciphers" and "Trapdoor Ciphers II." Chs. 13-14 in Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman, pp. 183-204, 1989.Luby, M. Pseudorandomness and Cryptographic Applications. Princeton, NJ: Princeton University Press, 1996.RSA Laboratories.® "What Is a One-Way Function?" http://www.rsasecurity.com/rsalabs/faq/2-3-2.html.

Referenced on Wolfram|Alpha

Trapdoor One-Way Function

Cite this as:

Weisstein, Eric W. "Trapdoor One-Way Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TrapdoorOne-WayFunction.html

Subject classifications