Paper 2024/1785

A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire

John Bostanci, Columbia University
Barak Nehoran, Princeton University
Mark Zhandry, NTT Research
Abstract

Aaronson, Atia, and Susskind [Aaronson et al., 2020] established that efficiently mapping between quantum states $\ket{\psi}$ and $\ket{\phi}$ is computationally equivalent to distinguishing their superpositions $\frac{1}{\sqrt{2}}(|\psi\rangle + |\phi\rangle)$ and $\frac{1}{\sqrt{2}}(|\psi\rangle - |\phi\rangle)$. We generalize this insight into a broader duality principle in quantum computation, wherein manipulating quantum states in one basis is equivalent to extracting their value in a complementary basis. In its most general form, this duality principle states that for a given group, the ability to implement a unitary representation of the group is computationally equivalent to the ability to perform a Fourier subspace extraction from the invariant subspaces corresponding to its irreducible representations. Building on our duality principle, we present the following applications: * Quantum money, which captures quantum states that are verifiable but unclonable, and its stronger variant, quantum lightning, have long resisted constructions based on concrete cryptographic assumptions. While (public-key) quantum money has been constructed from indistinguishability obfuscation (iO)—an assumption widely considered too strong—quantum lightning has not been constructed from any such assumptions, with previous attempts based on assumptions that were later broken. We present the first construction of quantum lightning with a rigorous security proof, grounded in a plausible and well-founded cryptographic assumption. We extend Zhandry's construction from Abelian group actions [Zhandry, 2024] to non-Abelian group actions, and eliminate Zhandry's reliance on a black-box model for justifying security. Instead, we prove a direct reduction to a computational assumption—the pre-action security of cryptographic group actions. We show how these group actions can be realized with various instantiations, including with the group actions of the symmetric group implicit in the McEliece cryptosystem. * We provide an alternative quantum money and lightning construction from one-way homomorphisms, showing that security holds under specific conditions on the homomorphism. Notably, our scheme exhibits the remarkable property that four distinct security notions—quantum lightning security, security against both worst-case cloning and average-case cloning, and security against preparing a specific canonical state—are all equivalent. * Quantum fire captures the notion of a samplable distribution on quantum states that are efficiently clonable, but not efficiently telegraphable, meaning they cannot be efficiently encoded as classical information. These states can be spread like fire, provided they are kept alive quantumly and do not decohere. The only previously known construction relied on a unitary quantum oracle, whereas we present the first candidate construction of quantum fire in the plain model.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
quantum moneyquantum lightninggroup representationsnon-Abelian group actionsquantum fireduality
Contact author(s)
chb2154 @ columbia edu
bnehoran @ princeton edu
mzhandry @ gmail com
History
2024-11-04: approved
2024-11-01: received
See all versions
Short URL
https://ia.cr/2024/1785
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1785,
      author = {John Bostanci and Barak Nehoran and Mark Zhandry},
      title = {A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1785},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1785}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.