Cryptology ePrint Archive: Report 2014/372

Fully secure constrained pseudorandom functions using random oracles

Dennis Hofheinz

Abstract: A constrained pseudorandom function (CPRF) PRF allows to derive constrained evaluation keys that only allow to evaluate PRF on a subset of inputs. CPRFs have only recently been introduced independently by three groups of researchers. However, somewhat curiously, all of them could only achieve a comparatively weak, selective-challenge form of security (except for small input spaces, very limited forms of constrained keys, or with superpolynomial security reductions).

In this paper, we construct the first fully secure CPRF without any of the above restrictions. Concretely, we support ``bit-fixing'' constrained keys that hardwire an arbitrary subset of the input bits to fixed values, we support exponentially large input spaces, and our security reduction is polynomial. We require very heavyweight tools: we assume multilinear maps, indistinguishability obfuscation, and our proof is in the random oracle model. Still, our analysis is far from tautological, and even with these strong building blocks, we need to develop additional techniques and tools.

As a simple application, we obtain the first adaptively secure non-interactive key exchange protocols for large user groups.

Category / Keywords: foundations / constrained pseudorandom functions, adaptive security, non-interactive key exchange

Date: received 27 May 2014, last revised 17 Sep 2014

Contact author: Dennis Hofheinz at kit edu

Available format(s): PDF | BibTeX Citation

Note: This is an out of date draft and here for reference only. This paper has been superseded and replaced by the paper “Adaptively Secure Constrained Pseudorandom Functions” (eprint report 2014/720) which proves a more general result under weaker assumptions.

Version: 20140917:071026 (All versions of this report)

Short URL: ia.cr/2014/372

Discussion forum: Show discussion | Start new discussion