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

Jiang Zhang; Yu Chen; Zhenfeng Zhang

Paper 2016/523

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

Jiang Zhang, Yu Chen, and Zhenfeng Zhang

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in CRYPTO 2016
Contact author(s): jiangzhang09 @ gmail com
History: 2016-09-05: last of 2 revisions; 2016-05-29: received; See all versions
Short URL: https://ia.cr/2016/523
License: CC BY

BibTeX

@misc{cryptoeprint:2016/523,
      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},
      url = {https://eprint.iacr.org/2016/523}
}