Private Circuit Constrained PRFs from Obfuscation

We show how indistinguishability obfuscation can be used to construct a private constrained PRF for general circuit constraints.

Suppose  is a PRF with master secret key  We use  in conjunction with  to construct a private circuit-constrained PRF.

We describe the constrain algorithm. On input a circuit  the constrain algorithm samples another secret key sk  and outputs the obfuscation of the following program 

"On input  if  output  Otherwise, output 

In the above program, note that , and  are all hard-coded into the program. Let  be the obfuscated program.

Our starting point is the circuit-constrained PRF by Boneh and Zhandry [BZ14, Construction 9.1]. In the Boneh-Zhandry construction, the master secret key  is a key for a puncturable PRF, and a constrained key for a circuit  is an obfuscation of the program that outputs cPRF.Eval(msk,  ) if  and abort otherwise.

Because the program outputs abort on inputs  where , simply evaluating the PRF at different points reveals information about the underlying constraint.

We structure the program so that on an input  where  the program's output is the output of a different PRF. Intuitively, just by looking at the outputs of the program, it is difficult to distinguish between the output of the real PRF and the output of the other PRF.

We now describe our construction of a multi-key private circuit-constrained PRF.

Let  be an indistinguishability obfuscator, and let (F.Setup, F.Puncture, F.ConstrainEval,F.Eval) be any puncturable (but not necessarily private) PRF.

Our multi-key private circuitconstrained PRF  (cPRF.Setup, cPRF.Constrain, cPRF. ConstrainEval, cPRF.Eval) is given as follows:

• cPRF.Setup . The setup algorithm outputs  F.Setup .
• cPRF.Constrain . First, the constrain algorithm computes  F.Setup . Then, it outputs an obfuscated program   where  is the following program:

The program  Constants: a circuit  and master secret keys  for the puncturable PRF 

On input  : Let . Output F.Eval( .

• cPRF. ConstrainEval(sk,  ). The constrained evaluation algorithm outputs the evaluation of the obfuscated program sk on .
• cPRF.Eval(msk,  ). The evaluation algorithm outputs F.Eval(msk,  ).

Evaluation of the PRF using the constrained key corresponds to evaluating the program . We see that on all inputs  where  so correctness is immediate.

• Correctness. By definition, the program  outputs  Eval  on all where  Correctness of  immediately follows from correctness of the indistinguishability obfuscator.

At a high level, the constrain algorithm generates a "fake" PRF key , and the constrained key is just a program that either evaluates the "real" PRF or the fake PRF, depending on the value of . Since the adversary cannot distinguish between the outputs under the real PRF key from those under the fake PRF key, the adversary cannot simply use the input-output behavior of the obfuscated program to learn anything about 

We show that if the underlying PRF  is puncturable (not necessarily privately), the indistinguishability obfuscation of the program does in fact hide the constraining circuit 

• Security. We now state our security and privacy theorems.

Suppose  is an indistinguishability obfuscator and  is a selectively-secure puncturable PRF. Then,  is selectively secure.

Suppose  is a indistinguishability obfuscator, and  is a selectively-secure puncturable  both secure against subexponential adversaries. Then,  is multi-key private.

We note though that for general circuits, our security reduction requires subexponential hardness of  (and one-way functions). For restricted classes of circuits, such as puncturing, however, we can obtain security from polynomially-hard  (and one-way functions).