Non-quantum cryptanalysis of the noisy version of Aaronson–Christiano's quantum money scheme - Archive ouverte HAL Access content directly
Journal Articles IET Information Security Year : 2019

Non-quantum cryptanalysis of the noisy version of Aaronson–Christiano's quantum money scheme

(1) , (2) , (3) , (1) , (3)
1
2
3

Abstract

At STOC 2012, Aaronson and Christiano proposed a noisy and a noiseless version of the first public-key quantum money scheme endowed with a security proof. This paper addresses the so-called noisy hidden subspaces problem, on which the noisy version of their scheme is based. The first contribution of this work is a non-quantum cryptanalysis of the above-mentioned noisy quantum money scheme extended to prime fields F, with |F| ≠ 2, that runs in randomised polynomial time. This finding is supported with experimental results showing that, in practice, the algorithm presented is efficient and succeeds with overwhelming probability. The second contribution is a non-quantum randomised polynomial-time cryptanalysis of the noisy quantum money scheme over F2 succeeding with a certain probability for values of the noise lying within a certain range. This result disproves a conjecture made by Aaronson and Christiano about the non-existence of an algorithm that solves the noisy hidden subspaces problem over F2 and succeeds with such probability.
Not file

Dates and versions

hal-02395072 , version 1 (05-12-2019)

Identifiers

Cite

Marta Conde Pena, Raul Durán Díaz, Jean-Charles Faugère, Luis Hernández Encinas, Ludovic Perret. Non-quantum cryptanalysis of the noisy version of Aaronson–Christiano's quantum money scheme. IET Information Security, 2019, 13 (4), pp.362-366. ⟨10.1049/iet-ifs.2018.5307⟩. ⟨hal-02395072⟩
57 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More