Quantum Seminar Speaker: Eli Goldin, NYU Date: Monday, Nov. 10 Time: 2:00 pm Location: Computer Science Building, CS105 Host: Prof. Alex Lombardi, CS Title: One-Way Puzzles: A Central Primitive for Quantum Cryptography" Abstract: One-way functions are generally seen as a fundamental (or "central") primitive for classical cryptography. The existence of nearly any cryptography implies the existence of one-way functions, and one-way functions satisfy a number of useful properties which make them easy to work with. In the quantum setting, we give evidence that a recently introduced primitive, the one-way puzzle, is a natural analogue of one-way functions in the quantum regime. In particular, they are a useful tool for understanding the fundamental hardness behind quantum cryptography. Towards this end, we show that one-way puzzles satisfy nearly all the "nice properties" of one-way functions. We present a one-way puzzle combiner, a universal construction, a security amplification theorem, and show that one-way puzzles are equivalent to many natural variants. As a result of these nice properties, we demonstrate that one-way puzzles can be constructed from a large class of quantum cryptographic primitives (in particular, those broken by a #P oracle). Furthermore, we show a number of interesting connections between one-way puzzles and the fields of meta-complexity and (efficiently verifiable) quantum advantage, and discuss black-box separations between one-way puzzles and other primitives.