IQIM Postdoctoral and Graduate Student Seminar

Abstract: Quantum money is a system of money where bank-notes are quantum states that can not be counterfeited by any efficient adversary. Constructing publicly-verifiable quantum money (where anyone can verify the validity of a purported bank-note) has been a fundamental challenge in the field of quantum cryptography for the past 16 years. Despite lots of effort, convincing constructions remain elusive, with the most plausible constructions relying on black-box proofs of security, or conjectured constructions of even more powerful cryptography (post-quantum indistinguishability obfuscation). I will present a construction of quantum money (and quantum lightning, a collision-resistant variant of quantum money) from non-Abelian group actions, which can be instantiated with well-known cryptosystems like the McEliece cryptosystem, and prove its security in the plain model from a (non-standard) computational assumption. Important to our security proof is a new computational duality between implementing a representation of a group and performing a form of coherent measurement in the Fourier basis of said group, which we call a Fourier subspace extraction. This talk is based on joint work with Barak Nehoran and Mark Zhandry.