|
{0,1}m(n) s. t. it
is a one-way-functionfixed public key (PL) y e {0,1}I(n), f(x,y)
fy(x) acts
as map n
m(n) in bits (PL). If so, an
algorithm exists s. t. {y, fy(x), z}
x'
s. t. fy(x') = fy(x) for some trapdoor
key (PL), z e {0,1}k(n). A
hash function (PL) is a one-way hash function if, also, given messages M, f(M), it is difficult to discover a message M'
M s. t. (by transmission) f(M') = f(M. Open
problem: Can a trapdoor one-way function be constructed from any one-way function?
Example of trapdoor one-way function: the factoring of the product of two large primes
, as in RSA encryption (PL), conjectured to be trapfoor one-way.