<p>You can't say anything useful.</p>
<p>Let <span class="math-container">$E$</span> be a pseudorandom permutation on <span class="math-container">$\{0,1\}^m$</span> with <span class="math-container">$n$</span>-bit key, <span class="math-container">$m$</span> be large (at least twice the security parameter), <span class="math-container">$S=\{0,1\}^m$</span>, and define <span class="math-container">$F$</span> by</p>
<p><span class="math-container">$$F(v,w) = E_v(w) + \delta(w),$$</span></p>
<p>where either <span class="math-container">$\delta(w)=0$</span> for all <span class="math-container">$w$</span>, or <span class="math-container">$\delta(1^m)=1$</span> and <span class="math-container">$\delta(w)=0$</span> for all <span class="math-container">$w \ne 1^m$</span>.  Then <span class="math-container">$F$</span> is a PRF for both choices of <span class="math-container">$\delta$</span>, yet the probability you list is either 0 or 1 according to the choice of <span class="math-container">$\delta$</span>.</p>
<p>Why?  Well, <span class="math-container">$F$</span> is a good PRF, because the best attack is to use a birthday-style attack, but when <span class="math-container">$m$</span> is large, this requires an intractably large number of queries (something like <span class="math-container">$2^{m/2}$</span> queries to achieve a constant distinguishing advantage).  Also, because <span class="math-container">$E_k(w)$</span> is a permutation of <span class="math-container">$w$</span> and <span class="math-container">$S=\{0,1\}^m$</span>, we have
<span class="math-container">$$\sum_{w \in S} F(v,w) = \delta(1^m) + \sum_{y \in \{0,1\}^m} y = \delta(1^m).$$</span></p>
<hr />
<p>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 <span class="math-container">$G_0$</span> be a pseudorandom generator, <span class="math-container">$m=1$</span>, <span class="math-container">$S=\{0,1\}$</span>, <span class="math-container">$c \in \{0,1\}$</span> be a constant, and define <span class="math-container">$G$</span> by <span class="math-container">$G(v,w)=G_0(v) \oplus c \cdot w$</span> where <span class="math-container">$w \in \{0,1\}$</span>.  Then the probability you list is 0 or 1 according to the value of <span class="math-container">$c$</span>, yet <span class="math-container">$G$</span> 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.</p>

CC BY-SA 4.0
2024-04-28T19:21:27.253Z
2024-05-01T07:44:49.343Z
2024-05-01T07:44:49.343Z
D.W.
<p>Suppose I have a pseudorandom function (in the theoretical sense) <span class="math-container">$X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$</span> (where <span class="math-container">$m$</span> is polynomial in <span class="math-container">$n$</span>) and a non-empty set <span class="math-container">$S\subseteq\{0,1\}^m$</span> (<span class="math-container">$S$</span> is not sparse, and is a nice set, like say, the set of all strings with <span class="math-container">$m/2$</span> <span class="math-container">$1$</span>s). What can be said of
<span class="math-container">$$\mathbf{Pr}_{\mathbf{v}\in\{0,1\}^n}\Bigl[\sum_{\mathbf{w}\in S}X(\mathbf{v},\mathbf{w})\equiv 0\pmod2 \Bigr]\:?$$</span></p>
<p>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 <span class="math-container">$1/2$</span> — at least as close as “computationally indistinguishable” requires it to be.</p>
<p>However, since <span class="math-container">$|S|$</span> is not polynomial in <span class="math-container">$n$</span> (or <span class="math-container">$m$</span>), 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 <em>probably</em> is some paper in analysis dealing with something like this, although I am not sure what to Google to find it.</p>

<pr.probability><randomness><pseudorandomness><pseudorandom-generators>
Parity of the sum of pseudorandom bits over a non-sparse set of inputs
Tejas
# Parity of the sum of pseudorandom bits over a non-sparse set of inputs

(Asked by: username_0 on 2024-04-28)

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.

**Tags:** pr.probability, randomness, pseudorandomness, pseudorandom-generators

---

## 1 answers

### Answer by username_1 on 2024-04-28. Score: 2 | Accepted answer

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.


---

