Paper 2015/554

An Algebraic Framework for Pseudorandom Functions and Applications to Related-Key Security

Michel Abdalla, Fabrice Benhamouda, and Alain Passelègue

Abstract

In this work, we provide a new algebraic framework for pseudorandom functions which encompasses many of the existing algebraic constructions, including the ones by Naor and Reingold (FOCS'97), by Lewko and Waters (CCS'09), and by Boneh, Montgomery, and Raghunathan (CCS'10), as well as the related-key-secure pseudorandom functions by Bellare and Cash (Crypto'10) and by Abdalla et al. (Crypto'14). To achieve this goal, we introduce two versions of our framework. The first, termed linearly independent polynomial security, states that the values $(g^{P_1(\vec{a})}, \ldots, g^{P_q(\vec{a})})$ are indistinguishable from a random tuple of the same size, when $P_1, \ldots, P_q$ are linearly independent multivariate polynomials of the secret key vector $\vec{a}$. The second, which is a natural generalization of the first framework, additionally deals with constructions based on the decision linear and matrix Diffie-Hellman assumptions. In addition to unifying and simplifying proofs for existing schemes, our framework also yields new results, such as related-key security with respect to arbitrary permutations of polynomials. Our constructions are in the standard model and do not require the existence of multilinear maps.

Note: 2015-06-15: final version submitted by the authors to the IACR and to Springer-Verlag on June 5th, 2015. 2015-09-07: full version.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
Related-Key SecurityPseudorandom Functions
Contact author(s)
fabrice ben hamouda @ ens fr
History
2015-09-07: revised
2015-06-15: received
See all versions
Short URL
https://ia.cr/2015/554
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/554,
      author = {Michel Abdalla and Fabrice Benhamouda and Alain Passelègue},
      title = {An Algebraic Framework for Pseudorandom Functions and Applications to Related-Key Security},
      howpublished = {Cryptology ePrint Archive, Paper 2015/554},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/554}},
      url = {https://eprint.iacr.org/2015/554}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.