IQC Math and CS seminar featuring John Bostanci

Quantum money from non-Abelian group actions

John Bostanci | Columbia University

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 much 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.

Location

• QNC 1201

• Online on Zoom

  • Meeting ID: 933 8352 2434
  • Passcode: 900921