Paper 2017/096

Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques

Shota Yamada


In this paper, we focus on the constructions of adaptively secure identity-based encryption (IBE) from lattices and verifiable random function (VRF) with large input spaces. Existing constructions of these primitives suffer from low efficiency, whereas their counterparts with weaker guarantees (IBEs with selective security and VRFs with small input spaces) are reasonably efficient. We try to fill these gaps by developing new partitioning techniques that can be performed with compact parameters and proposing new schemes based on the idea. - We propose new lattice IBEs with poly-logarithmic master public key sizes, where we count the number of the basic matrices to measure the size. Our constructions are proven secure under the LWE assumption with polynomial approximation factors. They achieve the best asymptotic space efficiency among existing schemes that depend on the same assumption and achieve the same level of security. - We also propose several new VRFs on bilinear groups. In our first scheme, the size of the proofs is poly-logarithmic in the security parameter, which is the smallest among all the existing schemes with similar properties. On the other hand, the verification keys are long. In our second scheme, the size of the verification keys is poly-logarithmic, which is the smallest among all the existing schemes. The size of the proofs is sub-linear, which is larger than our first scheme, but still smaller than all the previous schemes.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2017
identity-based encryptionverifiable random functionadaptive securitylarge input spacelatticesbilinear maps
Contact author(s)
yamada-shota @ aist go jp
2017-06-05: revised
2017-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shota Yamada},
      title = {Asymptotically Compact Adaptively Secure Lattice {IBEs} and Verifiable Random Functions via Generalized Partitioning Techniques},
      howpublished = {Cryptology ePrint Archive, Paper 2017/096},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.