×

Improvement and efficient implementation of a lattice-based signature scheme. (English) Zbl 1321.94107

Lange, Tanja (ed.) et al., Selected areas in cryptography – SAC 2013. 20th international conference, Burnaby, BC, Canada, August 14–16, 2013. Revised selected papers. Berlin: Springer (ISBN 978-3-662-43413-0/pbk; 978-3-662-43414-7/ebook). Lecture Notes in Computer Science 8282, 48-67 (2014).
Summary: Lattice-based signature schemes constitute an interesting alternative to RSA and discrete logarithm based systems which may become insecure in the future, for example due to the possibility of quantum attacks. A particularly interesting scheme in this context is the GPV signature scheme [C. Gentry et al., STOC 2008. New York, NY: ACM, 197–206 (2008; Zbl 1231.68124)], combined with the trapdoor construction from D. Micciancio and C. Peikert [Eurocrypt 2012, Lect. Notes Comput. Sci. 7237, 700–718 (2012; Zbl 1297.94090)] as it admits strong security proofs and is believed to be very efficient in practice. This paper confirms this belief and shows how to improve the GPV scheme in terms of space and running time and presents an implementation of the optimized scheme. A ring variant of this scheme is also introduced which leads to a more efficient construction. Experimental results show that GPV with the new trapdoor construction is competitive to the signature schemes that are currently used in practice.
For the entire collection see [Zbl 1321.94008].

MSC:

94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI