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 6 Jun 2014 Contact author: Dennis Hofheinz at kit edu Available format(s): PDF | BibTeX Citation Note: 2014-06-06: several typos fixed Version: 20140606:195310 (All versions of this report) Discussion forum: Show discussion | Start new discussion