Paper 2016/140

Adaptively Secure Identity-Based Encryption from Lattices with Asymptotically Shorter Public Parameters

Shota Yamada


In this paper, we present two new adaptively secure identity-based encryption (IBE) schemes from lattices. The size of the public parameters, ciphertexts, and private keys are $\tilde{O}(n^2 \kappa^{1/d})$, $\tilde{O}(n)$, and $\tilde{O}(n)$ respectively. Here, $n$ is the security parameter, $\kappa$ is the length of the identity, and $d$ is a flexible constant that can be set arbitrary (but will affect the reduction cost). Ignoring the poly-logarithmic factors hidden in the asymptotic notation, our schemes achieve the best efficiency among existing adaptively secure IBE schemes from lattices. In more detail, our first scheme is anonymous, but proven secure under the LWE assumption with approximation factor $n^{\omega(1)}$. Our second scheme is not anonymous, but proven adaptively secure assuming the LWE assumption for all polynomial approximation factors. As a side result, based on a similar idea, we construct an attribute-based encryption scheme for branching programs that simultaneously satisfies the following properties for the first time: Our scheme achieves compact secret keys, the security is proven under the LWE assumption with polynomial approximation factors, and the scheme can deal with unbounded length branching programs.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Contact author(s)
yamada-shota @ aist go jp
2016-02-16: received
Short URL
Creative Commons Attribution


      author = {Shota Yamada},
      title = {Adaptively Secure Identity-Based Encryption from Lattices with Asymptotically Shorter Public Parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2016/140},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.