Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download
Contributor : Abderrahmane Nitaj <>
Submitted on : Saturday, October 19, 2019 - 1:58:07 PM
Last modification on : Monday, April 27, 2020 - 4:14:03 PM
Long-term archiving on: : Monday, January 20, 2020 - 12:45:51 PM


Files produced by the author(s)


  • HAL Id : hal-02320770, version 1



Haoyu 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⟩



Record views


Files downloads