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.
Type de document :
Communication dans un congrès
IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC'15), Mar 2015, Maryland, United States
Liste complète des métadonnées

https://hal.inria.fr/hal-01098223
Contributeur : Ludovic Perret <>
Soumis le : mardi 23 décembre 2014 - 20:39:36
Dernière modification le : mardi 13 décembre 2016 - 15:43:48
Document(s) archivé(s) le : mardi 24 mars 2015 - 10:21:35

Fichier

hidd_subs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01098223, version 1

Collections

Citation

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>

Partager

Métriques

Consultations de
la notice

413

Téléchargements du document

1394