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 6 Sep 2015

Contact author: kvenkata at cs utexas edu

Available format(s): PDF | BibTeX Citation

Note: Fixed some typos, and added note about admissible hash functions

Version: 20150906:215905 (All versions of this report)

Short URL: ia.cr/2014/521

Discussion forum: Show discussion | Start new discussion