2010 | Shweta Agrawal, Dan Boneh, and Xavier Boyen
The paper presents an efficient identity-based encryption (IBE) system based on the standard learning with errors (LWE) problem. The security of the system is proven in the standard model. The key innovation is a family of lattices with two distinct trapdoors: one for generating short vectors in all lattices, and another for generating short vectors in all lattices except one. This technique is extended to construct adaptively secure IBE and hierarchical IBE (HIBE). The system processes identities as one chunk rather than bit-by-bit, resulting in lattices with dimensions comparable to those in random-oracle systems. The construction uses "right" and "left" lattices, with the left lattice's trapdoor serving as the master secret and enabling the generation of private keys for all identities. The paper also introduces an encoding function that maps identities to matrices in $\mathbb{Z}_q^{n \times n}$, ensuring injectivity and full-rank differences. The security reduction to the LWE problem is detailed, showing that the basic IBE system is IND-CPA secure under the LWE assumption.The paper presents an efficient identity-based encryption (IBE) system based on the standard learning with errors (LWE) problem. The security of the system is proven in the standard model. The key innovation is a family of lattices with two distinct trapdoors: one for generating short vectors in all lattices, and another for generating short vectors in all lattices except one. This technique is extended to construct adaptively secure IBE and hierarchical IBE (HIBE). The system processes identities as one chunk rather than bit-by-bit, resulting in lattices with dimensions comparable to those in random-oracle systems. The construction uses "right" and "left" lattices, with the left lattice's trapdoor serving as the master secret and enabling the generation of private keys for all identities. The paper also introduces an encoding function that maps identities to matrices in $\mathbb{Z}_q^{n \times n}$, ensuring injectivity and full-rank differences. The security reduction to the LWE problem is detailed, showing that the basic IBE system is IND-CPA secure under the LWE assumption.