Paper 2014/521

Adaptively Secure Puncturable Pseudorandom Functions in the Standard Model

Susan Hohenberger, Venkata Koppula, and Brent Waters

Abstract

We study the adaptive security of constrained PRFs in the standard model. We initiate our exploration with puncturable PRFs. A puncturable PRF family is a special class of constrained PRFs, where the constrained key is associated with an element $x'$ in the input domain. The key allows evaluation at all points $x\neq x'$. We show how to build puncturable PRFs with adaptive security proofs in the standard model that involve only polynomial loss to the underlying assumptions. Prior work had either super-polynomial loss or applied the random oracle heuristic. Our construction uses indistinguishability obfuscation and DDH-hard algebraic groups of composite order.

Note: The artificial abort step was missing in the analysis. It is included in the description of Game 1 (page 10).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in Asiacrypt 2015
Keywords
puncturable pseudorandom functionsadaptive security
Contact author(s)
kvenkata @ cs utexas edu
History
2015-11-26: last of 2 revisions
2014-07-07: received
See all versions
Short URL
https://ia.cr/2014/521
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/521,
      author = {Susan Hohenberger and Venkata Koppula and Brent Waters},
      title = {Adaptively Secure Puncturable Pseudorandom Functions in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2014/521},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/521}},
      url = {https://eprint.iacr.org/2014/521}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.