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
Within Cryptography · Search all subjects
Minimum Circuit Size Problem
Given every output of a Boolean function, how hard is it to decide whether a small circuit can produce that table?
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?
Public-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?