{"id":"arxiv/2609.11901","url":"https://arxiv.org/abs/2609.11901","tags":["quant-ph","cs.CR"],"score":0,"title":"EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity","domain":"quant-ph","source":"arxiv","authors":["Atul Mantri"],"reviews":0,"subject":"quant-ph","summary":"EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography. The first are efficiently preparable quantum states, statistically far yet computationally indistinguishable; the second are classical puzzles, easy to sample and hard to solve. One-way puzzles imply EFI pairs, and whether the converse holds is open. We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}