EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
Theorists build a classical oracle where one-way puzzles fail yet EFI pairs survive, separating two candidate minimal assumptions of quantum cryptography.
The paper constructs a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every classical-query distinguisher holding advice, making one superposition query at the end. Security is proven by reducing adversary knowledge to communication complexity for Vector-in-Subspace, with the superposition query bounded using random matrix theory. Relative to the oracle, quantum polynomial time offers no advantage on tasks with classical inputs and outputs and there is no proof of quantumness, separating the leading minimal assumptions of quantum cryptography.