Lattice Mixing and Vanishing Trapdoors
A Framework for Fully Secure Short Signatures and More

By Xavier Boyen.

In Public Key Cryptography (PKC 2010), volume 6056 of Lecture Notes in Computer Science, pages 499-517. Springer, 2010.

Abstract

We propose a framework for adaptive security from hard random lattices in the standard model. Our approach borrows from the recent Agrawal-Boneh-Boyen families of lattices, which can admit reliable and punctured trapdoors, respectively used in reality and in simulation. We extend this idea to make the simulation trapdoors cancel not for a specific target but on a non-negligible subset of the possible challenges. Conceptually, we build a compactly representable, large family of input-dependent ``mixture'' lattices, set up with trapdoors that ``vanish'' for a secret subset wherein we hope the attack occurs. Technically, we tweak the lattice structure to achieve ``naturally nice'' distributions for arbitrary choices of subset size. The framework is very general. Here we obtain fully secure signatures, and also IBE, that are compact, simple, and elegant.

Material

- published paper (PS) (PDF) (also accessible from the publisher) © IACR
- author's version (PS) (PDF)
- full version (PS) (PDF)
- presentation slides (HTML)

Reference

@InProceedings{Boyen:PKC-2010:lattice,
  author = {Xavier Boyen},
  title = {Lattice Mixing and Vanishing Trapdoors -- A Framework for Fully Secure Short Signatures and More},
  booktitle = {Public Key Cryptography---PKC 2010},
  series = {Lecture Notes in Computer Science},
  volume = {6056},
  pages = {499--517},
  publisher = {Berlin: Springer-Verlag},
  year = {2010},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/pkc10b/}}
}