2
$\begingroup$

I have recently been reading "Constrained Pseudorandom Functions" by Boneh and Waters, and "Constrained Verifiable Random Functions" by Fuchsbauer. One of the claimed results is that, for any circuit $C$, you can constrain a PRF key $k$ into a key $k_C$ such that someone holding $k_C$ will only be able to evaluate the PRF under key $k$ on inputs $x$ such that $C(x)=1$. What the authors definitely show is that you can constrain a PRF to an arbitrary layered, monotone circuit, and then they claim that the result follows for arbitrary circuits. Here is an excerpt from the BW paper:

In addition, like [17] we also build our construction for monotone circuits (limiting ourselves to AND and OR gates); however, we make the standard observation that by pushing NOT gates to the input wires using De Morgan’s law we obtain the same result for general circuits.

There is also the following confusing footnote:

These restrictions are mostly useful for exposition and do not impact functionality. General circuits can be built from non-monotonic circuits. In addition, given a circuit an equivalent layered exists that is larger by at most a polynomial factor

Is the statement "General circuits can be built from non-monotonic circuits" not practically a tautology?

And from the Fuchsbauer one:

Our treatment of circuits follows that by Boneh and Waters [BW13], who adapt the model of Bellare et al. [BHR12]. They consider boolean circuits with a single output gate and require that circuits are layered (where a gate at level j receives its inputs from wires at level j − 1) and monotonic in that they only contain AND and OR gates. This is without loss of generality, since an arbitrary circuit can be transformed into a layered monotonic circuit of polynomially related size.

But anyways, following the reference in the first excerpt to "Attribute-based encryption for circuits from multilinear maps" from Garg, Gentry, Sahai, and Waters, they claim:

We begin by observing that there is a folklore transformation that uses De Mor- gan’s rule to transform any general Boolean circuit into an equivalent monotone Boolean circuit, with negation gates only allowed at the inputs. For complete- ness, we sketch the construction here. Given a Boolean circuit C, consider the Boolean circuit ˜C that computes the negation of C. Note that such a circuit can be generated by simply recursively applying De Morgan’s rule to each gate of C starting at the output gate. The cru- cial property of this transformation is that in this circuit ˜C each wire computes the negation of the corresponding original wire in C. Now, we can construct a monotone circuit M by combining C and ˜C as follows: take each negation gate inside C, eliminate it, and replace the output of the negation gate by the corresponding wire in ˜C. Do the same for negation gates in ˜C, using the wires from C. In the end, this will yield a monotone circuit M with negation gates remaining only at the input level, as desired. The size of M will be no more than twice the original size of C, and the depth of M will be identical to the depth of C, where depth is computed ignoring negation gates. The correctness of this transformation follows trivially from De Morgan’s rule. As a result, we can focus our attention on monotone circuits. Note that inputs to the circuit correspond to boolean variables xi, and we can simply introduce explicit separate attributes corresponding to xi = 0 and xi = 1. Honest encryptors are instructed to only set one of these two attributes for each variable xi. Because of this simple transformation, in the sequel we will only consider ABE for monotone circuits

In the context of ABE, I can buy this argument. But I do not see how this makes any sense for the constrained PRF setting.

So I don't see how the claim that it suffices to build constrained PRFs for monotone circuits is true. The authors don't describe how to make NOT gates, even for just the first level of the circuit. Perhaps I am missing some context in which this restriction is without loss of generality, or I have some misunderstanding of the relationship between monotone circuits and general circuits.

Thanks in advance for your reply,

Franklin

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Here's the answer, thanks to Brent Waters for the discussion:

While it is not true that an arbitrary circuit can be transformed into a layered monotonic circuit that computes the same function, it is true that an arbitrary circuit can be transformed into a circuit which is monotone after the first layer that computes the same function. Or, put another way, let $map(x=x_1 ... x_n) := x_1 ... x_n (1-x_1) ... (1-x_n)$, so e.g. $map(0110)=01101001$. Then for every circuit $C$ there is a layered monotone circuit $C'$ of polynomial-related size such that $C(x)=C'(map(x))$ for all $x$. This can be seen by applying DeMorgan's laws recursively.

Why does this suffice for constrained PRFs?

Even though the constrained PRF is not "forcing" a user with the constrained key to first apply $map$ to their input, in some sense we just don't care about the "illegal" inputs which don't satisfy $x_{i+n}=1-x_i$ for all $i \in [n]$, and the users' ability to evaluate the PRF on ilegal inputs that $C'$ still accepts doesn't matter.

More concretely:

Let's suppose $n=2$ and $C(x=x_1 x_2) = \neg (x_1 \land x_2)$. Then $map(x)$ is defined as explained, and $C'(x_1 x_2 x_3 x_4) = x_3 \lor x_4$.

We issue a user the constrained key for $C'$. Clearly they can evaluate the PRF on all inputs $00,01,10$, as desired, just by first applying $map(x)$ and then using the constrained key honestly.

But what happens if the user tries to evaluate the constrained PRF on an input like $0001$, which nothing is stopping them from doing? Clearly $C'$ is going to let them. There should be exactly three inputs for which the user can evaluate the constrained PRF, but now there are... 12?

Still, this doesn't effect security of the PRF. Pseudorandomness on the inputs that we care about (legal inputs) still holds.

If a user that was issued a constrained key wants to share a evaluation with the server holding the original, unconstrained key, they can reveal e.g. $(x,F_k(map(x))$ and the server will recompute the second component on their own, including computing $map(x)$, to check correctness. Note that simply accepting $(y, F_k(y))$ (and not checking $y_{n+i} = 1-y_i$) could lead to some unintended consequences.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.