Title: Efficient lattice-based signature scheme

Authors: Thomas Plantard, Willy Susilo, Khin Than Win, Qiong Huang

Addresses: Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong NSW 2522, Australia. ' Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong NSW 2522, Australia. ' School of Information Systems and Technology, University of Wollongong, Wollongong NSW 2522, Australia. ' Department of Computer Science, City University of Hong Kong, Hong Kong, China

Abstract: In Crypto 1997, Goldreich, Goldwasser and Halevi (GGH) proposed a lattice analogue of McEliece public key cryptosystem, in which security is related to the hardness of approximating the Closest Vector Problem in a lattice. Furthermore, they also described how to use the same principle of their encryption scheme to provide a signature scheme. Practically, this cryptosystem uses the Euclidean norm, l₂-norm, which has been used in many algorithms based on lattice theory. Nonetheless, many drawbacks have been studied and these could lead to cryptanalysis of the scheme. In this article, we present a novel method of reducing a vector under the l_∞-norm and propose a digital signature scheme based on it. Our scheme takes advantage of the l_∞-norm to increase the resistance of the GGH scheme and to decrease the signature length. Furthermore, after some other improvements, we obtain a very efficient signature scheme, that trades the security level, speed and space.

Keywords: closest vector problem; digital signature; Goldreich, Goldwasser and Halevi; GGH; lattice theory; public key cryptography; security.

DOI: 10.1504/IJACT.2008.021085

International Journal of Applied Cryptography, 2008 Vol.1 No.2, pp.120 - 132

Published online: 03 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article