IACR News item: 26 June 2014
Léo Ducas, Daniele Micciancio
ePrint Reportworst-case complexity of approximating the Shortest Vector Problem in ideal lattices within polynomial
factors. The distinguishing feature of our scheme is that it achieves short signatures (consisting of a
single lattice vector), and relatively short public keys (consisting of O(log n) vectors.) Previous lattice
schemes in the standard model with similarly short signatures, due to Boyen (PKC 2010) and Micciancio
and Peikert (Eurocrypt 2012), had substantially longer public keys consisting of Ω(n) vectors (even when
implemented with ideal lattices). We also present a variant of our scheme that further reduces the public
key size to just O(log log n) vectors and allows for a tighther security proof by making the signer stateful.
Additional news items may be found on the IACR news page.