0
$\begingroup$

Suppose I have a pseudorandom function (in the theoretical sense) $X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$ (where $m$ is polynomial in $n$) and a non-empty set $S\subseteq\{0,1\}^m$ ($S$ is not sparse, and is a nice set, like say, the set of all strings with $m/2$ $1$s). What can be said of $$\mathbf{Pr}_{\mathbf{v}\in\{0,1\}^n}\Bigl[\sum_{\mathbf{w}\in S}X(\mathbf{v},\mathbf{w})\equiv 0\pmod2 \Bigr]\:?$$

In general, if one keeps the “mental model” of pseudorandom functions being very similar to uniform random variables in mind, this probability should be very close to $1/2$ — at least as close as “computationally indistinguishable” requires it to be.

However, since $|S|$ is not polynomial in $n$ (or $m$), you cannot run polytime experiments to try to distinguish between this distribution and a similar one generated by a truly random bit generator. I feel like there probably is some paper in analysis dealing with something like this, although I am not sure what to Google to find it.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

You can't say anything useful.

Let $E$ be a pseudorandom permutation on $\{0,1\}^m$ with $n$-bit key, $m$ be large (at least twice the security parameter), $S=\{0,1\}^m$, and define $F$ by

$$F(v,w) = E_v(w) + \delta(w),$$

where either $\delta(w)=0$ for all $w$, or $\delta(1^m)=1$ and $\delta(w)=0$ for all $w \ne 1^m$. Then $F$ is a PRF for both choices of $\delta$, yet the probability you list is either 0 or 1 according to the choice of $\delta$.

Why? Well, $F$ is a good PRF, because the best attack is to use a birthday-style attack, but when $m$ is large, this requires an intractably large number of queries (something like $2^{m/2}$ queries to achieve a constant distinguishing advantage). Also, because $E_k(w)$ is a permutation of $w$ and $S=\{0,1\}^m$, we have $$\sum_{w \in S} F(v,w) = \delta(1^m) + \sum_{y \in \{0,1\}^m} y = \delta(1^m).$$


A previous version of your question asked about pseudorandom generators. The above counterexample shows that you also can't say anything if you intended to ask about PRGs, either. Also, here is another counterexample. Let $G_0$ be a pseudorandom generator, $m=1$, $S=\{0,1\}$, $c \in \{0,1\}$ be a constant, and define $G$ by $G(v,w)=G_0(v) \oplus c \cdot w$ where $w \in \{0,1\}$. Then the probability you list is 0 or 1 according to the value of $c$, yet $G$ is a PRG in both cases. Knowing that something is a PRG tells you about its behavior on a single random input. It doesn't tell you anything useful about the correlation of its values across multiple related inputs.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.