The problem
A public key is something anyone can use to lock a message, while a separate secret key unlocks it. A one-way function is easy to compute but hard to reverse on a randomly chosen input. The question asks whether that basic one-way difficulty is enough to build public-key encryption.[1]
A sender can use a recipient’s public key without learning the secret decryption key. Can difficulty reversing a function on random inputs supply this split using entirely classical algorithms and communication? The barrier results restrict certain recipes; they do not rule out every use of the function’s implementation.
Formally, assume an efficiently computable classical function family for which every probabilistic polynomial-time inverter has negligible probability of finding any preimage of f(x) for uniform x. Seek classical polynomial-time key generation, encryption and decryption with correct recovery and IND-CPA security, without an extra hardness assumption or ideal random oracle. The construction may inspect the function’s circuit description.[1]
Scope
Classical probabilistic polynomial-time public-key encryption with classical keys, ciphertext and communication, correct decryption and indistinguishability under chosen-plaintext attack in the standard model, based solely on the existence of classical one-way functions. Non-black-box constructions and security proofs are permitted.
What remains open
Known constructions use additional mathematical structure. There is a proof that one broad kind of recipe cannot work, but that does not exclude all possible recipes. Researchers still lack a general construction from one-way functions alone.[1]
The garbling separation covers a specified way of accessing garbling and one-way-function gates, not arbitrary non-black-box reasoning. Recent quantum schemes can exploit quantum public keys or quantum communication; their existence or impossibility in restricted models does not answer this classical standard-model question. No unconditional separation of all OWFs from all PKE is being asserted.[1] [2]
Why it matters
This is about the foundations of secure communication. It would tell us whether making some computations hard to reverse already gives people a way to send private messages without first arranging a shared secret.[1]
The central obstacle is to convert average-case inversion hardness into the publicly usable structure needed for encryption. A public key must enable useful computation without giving away decryption. Understanding that conversion would map the boundary between private-key and public-key assumptions rather than merely improve a particular cipher.[1]
Definitions
1 term
non-black-box
Using a function’s implementation, not just calling it as an input–output oracle. The listed garbling barrier excludes one specified way of doing this; it does not exclude arbitrary non-black-box reasoning.[1]
Sources
- Limits on the Power of Garbling Techniques for Public-Key Encryption
Notes on Limits on the Power of Garbling Techniques for Public-Key Encryption
Abstract, Introduction and Theorem 1.1 state the open construction problem and identify the restricted black-box and garbling models ruled out.
- Cryptomania v.s. Minicrypt in a Quantum World
Notes on Cryptomania v.s. Minicrypt in a Quantum World
Introduction distinguishes classical black-box separation from quantum communication and quantum-key results; its classical-key QPKE theorem is not an unrestricted classical OWF-to-PKE impossibility. Revised June 1, 2026.
- Succinct Arguments for QMA from Collapsing Hash Functions
Notes on Succinct Arguments for QMA from Collapsing Hash Functions
September 2026 Abstract and Introduction explicitly say Minicrypt assumptions are not known to imply PKE. Its succinct quantum-proof result is credited as a different primitive.