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

Date: received 3 Jul 2014

Contact author: kvenkata at cs utexas edu

Available format(s): PDF | BibTeX Citation

Version: 20140707:064128 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]