Informally, a function is a trapdoor one-way
function if
1. It is a one-way function, and
2. For fixed public key ,
is viewed as a function
of
that maps
bits to
bits. Then there is an efficient algorithm that, on input
produces
such that
,
for some trapdoor key
.
is a trapdoor one-way hash function
if
is also a one-way hash function, i.e., if
additionally
3. Given
and
,
it is hard to find a message
such that
.
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.