Cryptanalysis of a code-based one-time signature (Q2200516)

In [\textit{V. Lyubashevsky}, Eurocrypt 2012, Lect. Notes Comput. Sci. 7237, 738--755 (2012; Zbl 1239.94002)] a new method for obtaining digital signatures from lattice assumptions was proposed, that does not require the use of a trapdoor. Recently, \textit{E. Persichetti} proposed an efficient adaptation of this method based on quasi-cyclic codes [``Efficient one-time signatures from quasi-cyclic codes: a full treatment'', Cryptography 2, No. 4, 30 (2018; \url{doi:10.3390/cryptography2040030})]. The paper under review provides evidences that a direct translation of Lyubashevsky's framework to build signatures without trapdoors from lattice assumptions to coding theory assumptions can only yield insecure signatures. It presents a general adaptation of Lyubashevsky's framework to coding theory, not restricted to specific codes. It express the key recovery from a single signature as a decoding problem, and arguing that this problem is efficiently solvable, and an algorithm to solve this problem is presented. Furthermore, a full cryptanalysis of all the parameters of Persichetti's one-time signature scheme based upon an adaptation of Lyubashevsky's framework is given. It is also shown that the attack recovers the signing key of the most secure instance (\(n = 9857\), 128 bits of security) in \(\approx 450ms\) (versus \(100ms\) for signature verification).