Cryptanalysis of the Randomized Version of a Lattice-Based Signature Scheme from PKC'08

Haoyu Lirenzhang Liu (1) , Abderrahmane Nitaj (2) , Yanbin Pan (1)

1 RCSDS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
2 LMNO - Laboratoire de Mathématiques Nicolas Oresme

In PKC'08, Plantard, Susilo and Win proposed a lattice-based signature scheme, whose security is based on the hardness of the closest vector problem with the infinity norm (CVP∞). This signature scheme was proposed as a countermeasure against the Nguyen-Regev attack, which improves the security and the efficiency of the Goldreich, Goldwasser and Halevi scheme (GGH). Furthermore, to resist potential side channel attacks, the authors suggested modifying the determinis-tic signing algorithm to be randomized. In this paper, we propose a chosen message attack against the randomized version. Note that the randomized signing algorithm will generate different signature vectors in a relatively small cube for the same message, so the difference of any two signature vectors will be relatively short lattice vector. Once collecting enough such short difference vectors, we can recover the whole or the partial secret key by lattice reduction algorithms, which implies that the randomized version is insecure under the chosen message attack.

Mots clés: Lattice reduction; Lattice-based cryptography; Signature schemes

Domaines: Cryptographie et sécurité [cs.CR]

Haoyu Lirenzhang Liu, Abderrahmane Nitaj, Yanbin Pan. Cryptanalysis of the Randomized Version of a Lattice-Based Signature Scheme from PKC'08. Information Security and Privacy (ACISP 2018), 2018, Sydney, Australia. ⟨hal-02320770⟩