HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Algebraic Cryptanalysis of a Quantum Money Scheme The Noise-Free Case

Marta Conde Pena 1 Jean-Charles Faugère 2 Ludovic Perret 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We investigate the Hidden Subspace Problem (HSPq) over Fq: Input : p1, . . . , pm, q1, . . . , qm ∈ Fq[x1, . . . , xn] of degree d ≥ 3 (and n ≤ m ≤ 2n). Find : a subspace A ⊂ Fq n of dimension n/2 (n is even) such that pi(A) = 0 ∀i ∈ {1, . . . , m} and qj(A ⊥) = 0 ∀j ∈ {1, . . . , m}, where A ⊥ denotes the orthogonal complement of A with respect to the usual scalar product in Fq. This problem underlies the security of the first public-key quantum money scheme that is proved to be cryptographically secure under a non quantum but classic hardness assumption. This scheme was proposed by S. Aaronson and P. Christiano [1] at STOC'12. In particular, it depends upon the hardness of HSP. More generally, Aaronson and Christiano left as an open problem to study the security of the scheme for a general field Fq. We present a randomized polynomial-time algorithm that solves the HSPq for q > 2 with success probability ≈ 1 − 1/q. So, the quantum money scheme extended to Fq is not secure. Finally, based on experimental results and a structural property of the polynomials that we prove, we conjecture that there is also a randomized polynomial-time algorithm solving the HSP2 with high probability. To support our theoretical results, we also present several experimental results confirming that our algorithms are very efficient in practice. We emphasize that [1] proposes a non-noisy and a noisy version of the public-key quantum money scheme. The noisy version of the quantum money scheme remains secure.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

Contributor : Ludovic Perret Connect in order to contact the contributor
Submitted on : Tuesday, December 23, 2014 - 8:39:36 PM
Last modification on : Friday, January 21, 2022 - 3:21:16 AM
Long-term archiving on: : Tuesday, March 24, 2015 - 10:21:35 AM


Files produced by the author(s)


  • HAL Id : hal-01098223, version 1


Marta Conde Pena, Jean-Charles Faugère, Ludovic Perret. Algebraic Cryptanalysis of a Quantum Money Scheme The Noise-Free Case. IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC'15), Mar 2015, Maryland, United States. ⟨hal-01098223⟩



Record views


Files downloads