One-way functions
Can a function be easy to compute but hard to reverse on typical inputs? A rigorous unconditional example is still missing.
Cryptography
Encryption, program obfuscation and the assumptions behind computational secrecy.
Subjects: Cryptography
Problems in this collection
4 problemsPublic-key encryption from one-way functions
One-way functions support secret-key cryptography. Are they enough to let anyone encrypt a message with a public key while only its owner can decrypt it?
Indistinguishability obfuscation from LWE
A program can reveal how it was written even when its outputs reveal nothing about that choice. Can a compiler hide the choice using only the familiar Learning with Errors hardness assumption?
Classical integer factorization
77 = 7 × 11 is easy to check. Can a classical computer find the complete prime factorization of every integer efficiently as its written length grows?