This paper presents an efficient identity-based encryption (IBE) system based on the standard learning with errors (LWE) problem, with security proven in the standard model. The system uses 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 IBE system processes identities as a single chunk rather than bit-by-bit, resulting in lattices with dimensions similar to those in the random-oracle system. The system uses two types of lattices: "left" and "right" lattices. The left lattice's trapdoor is used as the master secret, enabling private key generation for all identities. The right lattice's trapdoor is used only in the proof of selective security, enabling the simulator to generate private keys for all identities except one.
In pairing-based IBE systems, identities are encoded as integers in the range 1 to |G|. In contrast, lattice systems are typically defined over a small field Z_q, and identities are represented as matrices in Z_q^{n×n}. The system uses an encoding function H that maps identities to matrices, ensuring that the difference between any two encoded identities is invertible.
The system is secure under the LWE assumption, which is as hard as the worst-case SIVP and GapSVP problems. The system's security is proven using a series of games that show that an adversary cannot distinguish between the real system and a simulation. The system is efficient, with parameters chosen to ensure correctness and security.
The paper also presents a construction of a hierarchical IBE system, where identities are represented as vectors, and the system uses basis delegation to assign matrices to each level of the hierarchy. The resulting lattice dimension is linear in the recipient identity's depth, making the system efficient.
The system uses statistical distance and Gram-Schmidt norm to ensure security. The system's security is reduced to the LWE problem, which is as hard as the worst-case SIVP and GapSVP problems. The system is efficient, with parameters chosen to ensure correctness and security. The system is secure under the LWE assumption, which is as hard as the worst-case SIVP and GapSVP problems.This paper presents an efficient identity-based encryption (IBE) system based on the standard learning with errors (LWE) problem, with security proven in the standard model. The system uses 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 IBE system processes identities as a single chunk rather than bit-by-bit, resulting in lattices with dimensions similar to those in the random-oracle system. The system uses two types of lattices: "left" and "right" lattices. The left lattice's trapdoor is used as the master secret, enabling private key generation for all identities. The right lattice's trapdoor is used only in the proof of selective security, enabling the simulator to generate private keys for all identities except one.
In pairing-based IBE systems, identities are encoded as integers in the range 1 to |G|. In contrast, lattice systems are typically defined over a small field Z_q, and identities are represented as matrices in Z_q^{n×n}. The system uses an encoding function H that maps identities to matrices, ensuring that the difference between any two encoded identities is invertible.
The system is secure under the LWE assumption, which is as hard as the worst-case SIVP and GapSVP problems. The system's security is proven using a series of games that show that an adversary cannot distinguish between the real system and a simulation. The system is efficient, with parameters chosen to ensure correctness and security.
The paper also presents a construction of a hierarchical IBE system, where identities are represented as vectors, and the system uses basis delegation to assign matrices to each level of the hierarchy. The resulting lattice dimension is linear in the recipient identity's depth, making the system efficient.
The system uses statistical distance and Gram-Schmidt norm to ensure security. The system's security is reduced to the LWE problem, which is as hard as the worst-case SIVP and GapSVP problems. The system is efficient, with parameters chosen to ensure correctness and security. The system is secure under the LWE assumption, which is as hard as the worst-case SIVP and GapSVP problems.