Paper 2016/523

Programmable Hash Functions from Lattices: Short Signatures and IBEs with Small Key Sizes

Jiang Zhang, Yu Chen, and Zhenfeng Zhang


Driven by the open problem raised by Hofheinz and Kiltz (Journal of Cryptology, 2012), we study the formalization of lattice-based programmable hash function (PHF), and give two types of constructions by using several techniques such as a novel combination of cover-free sets and lattice trapdoors. Under the Inhomogeneous Small Integer Solution (ISIS) assumption, we show that any (non-trivial) lattice-based PHF is collision-resistant, which gives a direct application of this new primitive. We further demonstrate the power of lattice-based PHF by giving generic constructions of signature and identity-based encryption (IBE) in the standard model, which not only provide a way to unify several previous lattice-based schemes using the partitioning proof techniques, but also allow us to obtain a new short signature scheme and a new fully secure IBE scheme with keys consisting of a logarithmic number of matrices/vectors in the security parameter $\kappa$. Besides, we also give a refined way of combining two concrete PHFs to construct an improved short signature scheme with short verification keys from weaker assumptions. In particular, our methods depart from the confined guessing technique of Böhl et al. (Eurocrypt'13) that was used to construct previous standard model short signature schemes with short verification keys by Ducas and Micciancio (Crypto'14) and by Alperin-Sheriff (PKC'15), and allow us to achieve existential unforgeability against chosen message attacks (EUF-CMA) without resorting to chameleon hash functions.

Note: Fixed some typos.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2016
Contact author(s)
jiangzhang09 @ gmail com
2016-09-05: last of 2 revisions
2016-05-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jiang Zhang and Yu Chen and Zhenfeng Zhang},
      title = {Programmable Hash Functions from Lattices: Short Signatures and IBEs with Small Key Sizes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/523},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.