Cryptology ePrint Archive: Report 2014/521

Adaptively Secure Puncturable Pseudorandom Functions in the Standard Model

Susan Hohenberger and 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.

Category / Keywords: foundations/puncturable pseudorandom functions, adaptive security

Original Publication (with minor differences): IACR-ASIACRYPT-2015

Date: received 3 Jul 2014, last revised 26 Nov 2015

Contact author: kvenkata at cs utexas edu

Available format(s): PDF | BibTeX Citation

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

Version: 20151126:203527 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]