Paper 2022/624
Cryptanalysis of Three Quantum Money Schemes
Andriyan Bilyk, Javad Doliskani, and Zhiyong Gong
Abstract
We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a random point in the hidden subspace. Zhandry proposed a scheme based on multivariate hash functions in 2017. We give a polynomial time quantum algorithm for cloning a money state with high probability. Our algorithm uses the verification circuit of the scheme to produce a banknote from a given serial number. Kane proposed a scheme based on modular forms in 2018. The underlying hard problem in Kane's scheme is cloning a quantum state that represents an eigenvector of a set of Hecke operators. We give a polynomial time quantum reduction from this hard problem to a linear algebra problem. The latter problem is much easier to understand, and we hope that our reduction opens new avenues to future cryptanalyses of this scheme.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Quantum CryptographyQuantum MoneyCryptanalysis
- Contact author(s)
- javad doliskani @ ryerson ca
- History
- 2022-05-23: received
- Short URL
- https://ia.cr/2022/624
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/624, author = {Andriyan Bilyk and Javad Doliskani and Zhiyong Gong}, title = {Cryptanalysis of Three Quantum Money Schemes}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/624}, year = {2022}, url = {https://eprint.iacr.org/2022/624} }