Programmable Hash Functions in the Multilinear Setting

Eduarda S. V.  Freire; Dennis Hofheinz; Kenneth G.  Paterson; Christoph Striecks

Paper 2013/354

Programmable Hash Functions in the Multilinear Setting

Eduarda S. V. Freire, Dennis Hofheinz, Kenneth G. Paterson, and Christoph Striecks

Abstract

We adapt the concept of a programmable hash function (PHF, Crypto 2008) to a setting in which a multilinear map is available. This enables new PHFs with previously unachieved parameters. To demonstrate their usefulness, we show how our (standard-model) PHFs can replace random oracles in several well-known cryptographic constructions. Namely, we obtain standard-model versions of the Boneh-Franklin identity-based encryption scheme, the Boneh-Lynn-Shacham signature scheme, and the Sakai-Ohgishi-Kasahara identity-based non-interactive key exchange (ID-NIKE) scheme. The ID-NIKE scheme is the first scheme of its kind in the standard model. Our abstraction also allows to derive hierarchical versions of the above schemes in settings with multilinear maps. This in particular yields simple and efficient hierarchical generalizations of the BF, BLS, and SOK schemes. In the case of hierarchical ID-NIKE, ours is the first such scheme with full security, in either the random oracle model or the standard model. While our constructions are formulated with respect to a generic multilinear map, we also outline the necessary adaptations required for the recent ``noisy'' multilinear map candidate due to Garg, Gentry, and Halevi.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. This is the full version of a paper with the same title accepted to CRYPTO 2013.
Keywords: programmable hash functions multilinear maps identity-based encryption identity-based non-interactive key exchange digital signatures
Contact author(s): Christoph Striecks @ kit edu
History: 2013-06-10: received
Short URL: https://ia.cr/2013/354
License: CC BY

BibTeX

@misc{cryptoeprint:2013/354,
      author = {Eduarda S. V.  Freire and Dennis Hofheinz and Kenneth G.  Paterson and Christoph Striecks},
      title = {Programmable Hash Functions in the Multilinear Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2013/354},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/354}},
      url = {https://eprint.iacr.org/2013/354}
}