Cryptology ePrint Archive: Report 2020/923

Another code-based adaptation of Lyubashevsky’s signature cryptanalysed

Nicolas Aragon and Jean-Christophe Deneuville and Philippe Gaborit

Abstract: In 2012, Lyubashevsky introduced a framework for obtaining efficient digital signatures relying on lattice assumptions. Several works attempted to make this approach compliant with the coding theory setting, unsuccessfully. Recently, Song et al. proposed another adaptation of this framework, using denser and permuted secret keys, claiming immunity against existing attacks. This paper describes an efficient attack against Song et al. signature scheme. We show that it is possible to fully recover the secret key from a very limited number of signatures. As an example, it requires 32 signatures and 2 hours to recover the secret key of the parameter set targeting 80 bits of security. The attack affects both proposed parameter sets, and discourages patching such an approach.

Category / Keywords: public-key cryptography / cryptanalysis, digital signatures, coding theory, post-quantum cryptography

Date: received 24 Jul 2020

Contact author: jean-christophe deneuville at enac fr

Available format(s): PDF | BibTeX Citation

Version: 20200726:062632 (All versions of this report)

Short URL: ia.cr/2020/923


[ Cryptology ePrint archive ]