International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 20 October 2014

Hamza Abusalah, Georg Fuchsbauer, Krzysztof Pietrzak
ePrint Report ePrint Report
A constrained pseudorandom function $F: K \\times X \\to Y$ for family of subsets of $X$ is a function where for any key $k \\in K$ and set $S$ from the family one can efficiently compute a short constrained key $k_S$ which allows to evaluate $F(k,.)$ on all inputs $x\\in S$, while given this key, the outputs on all inputs $x \\notin S$ look random.

Constrained PRFs have been constructed for several families of sets, the most general being the circuit-constrained PRF by Boneh and Waters [Asiacrypt\'13]. Their construction allows for constrained keys $k_C$, where $C$ is a boolean circuit that defines the set $S = \\{ x \\in X | C(x) = 1 \\}$. In their construction the input length and the size of the circuits $C$ for which constrained keys can be computed must be fixed a priori during key generation.

In this paper we construct a constrained PRF that has an unbounded input length and constrained keys can be defined for any set that can be decided by a polynomial-time Turing machine. The only a priori bound we make is on the size of the Turing machines. We discuss applications of our CPRF, such as broadcast encryption where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties), and identity-based non-interactive key-agreement between sets of users where again there is no bound on the number of parties that can agree on a shared key.

Our CPRF is simply defined as $F(k,H(x))$ where $F$ is a puncturable PRF (e.g. the GGM construction) and $H$ is a collision-resistant hash function. A constrained key for a Turing machine $M$ is a signature on $M$. At setup we also publish an obfuscated circuit, which on input $M$, a signature $\\sigma$, a value $h$ and a short non-interactive argument of knowledge $\\pi$ outputs $F(k,h)$ if (1) $\\sigma$ is a valid signature on $M$ and (2) $\\pi$ proves knowledge of some $x$ s.t.\\ $H(x)=h$ and $M(x)=1$. For our security proof, we assume extractability obfuscation for the particular circuit just explained.

Expand

Additional news items may be found on the IACR news page.