Paper 2018/1205

Cryptanalysis of a code-based one-time signature

Jean-Christophe Deneuville and Philippe Gaborit

Abstract

In 2012, Lyubashevsky introduced a new framework for building lattice-based signature schemes without resorting to any trapdoor (such as GPV [6] or NTRU [7]). The idea is to sample a set of short lattice elements and construct the public key as a Short Integer Solution (SIS for short) instance. Signatures are obtained using a small subset sum of the secret key, hidden by a (large) Gaussian mask. (Information leakage is dealt with using rejection sampling.) Recently, Persichetti proposed an efficient adaptation of this framework to coding theory [12]. In this paper, we show that this adaptation cannot be secure, even for one-time signatures (OTS), due to an inherent difference between bounds in Hamming and Euclidean metrics. The attack consists in rewriting a signature as a noisy syndrome decoding problem, which can be handled efficiently using the extended bit flipping decoding algorithm. We illustrate our results by breaking Persichetti’s OTS scheme built upon this approach [12]: using a single signature, we recover the secret (signing) key in about the same amount of time as required for a couple of signature verifications.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. WCC 2019: The Eleventh International Workshop on Coding and Cryptography
Keywords
Post-Quantum CryptographyCoding TheoryDigital SignatureOne-timeCryptanalysis
Contact author(s)
jean-christophe deneuville @ insa-cvl fr
History
2019-03-20: last of 2 revisions
2018-12-19: received
See all versions
Short URL
https://ia.cr/2018/1205
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1205,
      author = {Jean-Christophe Deneuville and Philippe Gaborit},
      title = {Cryptanalysis of a code-based one-time signature},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1205},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1205}},
      url = {https://eprint.iacr.org/2018/1205}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.