Cryptology ePrint Archive: Report 2018/294

Learning strikes again: the case of the DRS signature scheme

Yang Yu and Léo Ducas

Abstract: Lattice signature schemes generally require particular care when it comes to preventing secret information from leaking through signature transcript. For example, the Goldreich-Goldwasser-Halevi (GGH) signature scheme and the NTRUSign scheme were completely broken by the parallelepiped-learning attack of Nguyen and Regev (Eurocrypt 2006). Several heuristic countermeasures were also shown vulnerable to similar statistical attacks.

At PKC 2008, Plantard, Susilo and Win proposed a new variant of GGH, informally arguing resistance to such attacks. Based on this variant, Plantard, Sipasseuth, Dumondelle and Susilo proposed a concrete signature scheme, called DRS, that has been accepted in the round 1 of the NIST post-quantum cryptography project.

In this work, we propose yet another statistical attack and demonstrate a weakness of the DRS scheme: one can recover some partial information of the secret key from sufficiently many signatures. One difficulty is that, due to the DRS reduction algorithm, the relation between the statistical leak and the secret seems more intricate. We work around this difficulty by training a statistical model, using a few features that we designed according to a simple heuristic analysis.

While we only recover partial information on the secret key, this information is easily exploited by lattice attacks, significantly decreasing their complexity. Concretely, we claim that, provided that 100,000 signatures are available, the secret key may be recovered using BKZ-138 for the first set of DRS parameters submitted to the NIST. This puts the security level of this parameter set below 80-bits (maybe even 70-bits), to be compared to an original claim of 128-bits.

Category / Keywords: public-key cryptography / Cryptanalysis, Lattice based signature, Statistical attack, Learning, BDD

Original Publication (in the same form): IACR-ASIACRYPT-2018

Date: received 27 Mar 2018, last revised 16 Aug 2018

Contact author: ducas at cwi nl

Available format(s): PDF | BibTeX Citation

Note: Update note (19 April 2018): Added link to source code. Editorial updates.

Version: 20180816:153231 (All versions of this report)

Short URL: ia.cr/2018/294


[ Cryptology ePrint archive ]