Open AccessNon‐quantum cryptanalysis of the noisy version of Aaronson–Christiano's quantum money scheme
Author(s) -
Conde Pena Marta,
Durán Díaz Raul,
Faugère JeanCharles,
Hernández Encinas Luis,
Perret Ludovic
Publication year - 2019
Publication title -
iet information security
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.308
H-Index - 34
eISSN - 1751-8717
pISSN - 1751-8709
DOI - 10.1049/iet-ifs.2018.5307
Subject(s) - cryptanalysis , scheme (mathematics) , quantum , mathematics , algorithm , computer science , cryptography , physics , quantum mechanics , mathematical analysis
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 fieldsF , 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 overF 2 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 overF 2 and succeeds with such probability.