Joël Alwen

Efficient lattice (H)IBE in the standard model continued

S. Agrawal, D. Boneh, and X. Boyen
X. Boyen

We construct an efficient identity based encryption system based on the
standard learning with errors (LWE) problem. Our security proof holds in
the standard model. The key step in the construction is a family of
lattices for which there are two distinct trapdoors for finding short
vectors. One trapdoor enables the real system to generate short vectors
in all lattices in the family. The other trapdoor enables the simulator
to generate short vectors for all lattices in the family except for one.
We extend this basic technique to an adaptively-secure IBE and a
Hierarchical IBE.

Time permiting, we will also cover the results in "Lattice Mixing and 
Vanishing Trapdoors" by Xavier Boyen which appeared in PKC 2010.

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.