zbMATH — the first resource for mathematics

Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more. (English) Zbl 1281.94074
Nguyen, Phong Q. (ed.) et al., Public key cryptography – PKC 2010. 13th international conference on practice and theory in public key cryptography, Paris, France, May 26–28, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13012-0/pbk). Lecture Notes in Computer Science 6056, 499-517 (2010).
Summary: 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 [S. Agrawal, D. Boneh and X. Boyen, Eurocrypt 2010, Lect. Notes Comput. Sci. 6110, 553–572 (2010; Zbl 1227.94022)], 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 forgery 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 which we hope the forger will target. 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.
For the entire collection see [Zbl 1188.94010].

94A60 Cryptography
Full Text: DOI