Cryptanalysis of a Code-Based Signature Scheme Based on the Lyubashevsky Framework

Marco Baldi; Karan Khathuria; Edoardo Persichetti; Paolo Santini

Paper 2020/905

Cryptanalysis of a Code-Based Signature Scheme Based on the Lyubashevsky Framework

Marco Baldi, Karan Khathuria, Edoardo Persichetti, and Paolo Santini

Abstract

In this paper we cryptanalyze a recently proposed signature scheme consisting in a translation of the Lyubashevsky framework to the coding theory, whose security is based on the hardness of decoding low weight errors in the Hamming metric. We show that each produced signature leaks information about the secret key and that, after the observation of a bunch of signatures, the secret key can be fully recovered with simple linear algebra. We conservatively assess the complexity of our proposed attack and show that it grows polynomially in the scheme parameters; numerical simulations are used to confirm our analysis. Our results show that the weakness of the scheme is intrinsic by design, and that security cannot be restored by a mere change in the parameters.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Contact author(s): p santini @ staff univpm it
m baldi @ staff univpm it
karan khathuria @ math uzh ch
epersichetti @ fau edu
History: 2020-07-18: received
Short URL: https://ia.cr/2020/905
License: CC BY

BibTeX

@misc{cryptoeprint:2020/905,
      author = {Marco Baldi and Karan Khathuria and Edoardo Persichetti and Paolo Santini},
      title = {Cryptanalysis of a Code-Based Signature Scheme Based on the Lyubashevsky Framework},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/905},
      year = {2020},
      url = {https://eprint.iacr.org/2020/905}
}