Do one-way functions exist?
A one-way function is a function that can be computed in polynomial time, but such that every probabilistic polynomial-time algorithm, given for a uniformly random , finds some preimage of only with negligible probability. Prove or disprove that one-way functions exist.
History and references
Still open as of 2026.
Diffie and Hellman put one-way functions at the center of modern cryptography in their 1976 paper New Directions in Cryptography, noting that R. M. Needham had already used the idea to protect stored passwords. Nearly all of practical cryptography assumes that some function of this kind exists. Their existence would imply that P is not equal to NP, so a proof is at least as hard as that problem, while P different from NP alone is not known to be enough. Standard candidates include multiplying two large primes, whose inverse is factoring, and modular exponentiation, whose inverse is the discrete logarithm.
References
Solutions 0
Sign in or create an account to publish a solution