<figure><img src="image_1.png" /><figcaption>Fig. 1. Pseudorandom $\mathcal{Y}$-correlated outputs of a PCF.</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 2. Security of a PCF. Here, RSample is the algorithm for reverse sampling $\mathcal{Y}$ as in Definition 24.</figcaption></figure>

for all sufficiently large $\lambda$, where $\text{Exp}_{A,N,b}^{\text{pr}}(\lambda)$ for $b \in \{0,1\}$ is as defined in Figure 1. In particular, the adversary is given access to $N(\lambda)$ samples.

- **Security.** For each $\sigma \in \{0,1\}$ and non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds

$$|\Pr[\text{Exp}_{A,N,\sigma,0}^{\text{sec}}(\lambda) = 1] - \Pr[\text{Exp}_{A,N,\sigma,1}^{\text{sec}}(\lambda) = 1]| \le \varepsilon(\lambda)$$

for all sufficiently large $\lambda$, where $\text{Exp}_{A,N,\sigma,b}^{\text{sec}}(\lambda)$ for $b \in \{0,1\}$ is as defined in Figure 2 (again, with $N(\lambda)$ samples).

We say that (PCF Gibb's, PCF Eval) is a PCF for $\mathcal{Y}$ if it is a $(p, 1/p, p)$-secure PCF for $\mathcal{Y}$ for every polynomial $p$. If $B = N$, we will write $(B, \varepsilon)$-secure PCF for short.

The above definition captures a notion of weak pseudorandom function, where security is only required to hold given random adversarial queries. As for PRFs, one can also strengthen the definition to strong PCFs, which allow arbitrary adversarial queries; a formal definition is given in [BCG+20a]. As shown in [BCG+20a], any weak PCF can be turned into a strong PCF in the random oracle model, by hashing the input before feeding it to the function.
<figure><img src="image_3.png" /><figcaption>Fig. 1. Pseudorandom $\mathcal{Y}$-correlated outputs of a PCF.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. Security of a PCF. Here, RSample is the algorithm for reverse sampling $\mathcal{Y}$ as in Definition 24.</figcaption></figure>

for all sufficiently large $\lambda$, where $\text{Exp}_{\mathcal{A},N,b}^{\text{pr}}(\lambda)$ for $b \in \{0,1\}$ is as defined in Figure 1. In particular, the adversary is given access to $N(\lambda)$ samples.

- **Security.** For each $\sigma \in \{0,1\}$ and non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds

$$|\text{Pr}[\text{Exp}_{\mathcal{A},N,\sigma,0}^{\text{sec}}(\lambda) = 1] - \text{Pr}[\text{Exp}_{\mathcal{A},N,\sigma,1}^{\text{sec}}(\lambda) = 1]| \le \varepsilon(\lambda)$$

for all sufficiently large $\lambda$, where $\text{Exp}_{\mathcal{A},N,\sigma,b}^{\text{sec}}(\lambda)$ for $b \in \{0,1\}$ is as defined in Figure 2 (again, with $N(\lambda)$ samples).

We say that (PCF Gibb's, PCF Eval) is a PCF for $\mathcal{Y}$ if it is a $(p, 1/p, p)$-secure PCF for $\mathcal{Y}$ for every polynomial $p$. If $B = N$, we will write $(B, \varepsilon)$-secure PCF for short.

The above definition captures a notion of weak pseudorandom function, where security is only required to hold given random adversarial queries. As for PRFs, one can also strengthen the definition to strong PCFs, which allow arbitrary adversarial queries; a formal definition is given in [BCG+20a]. As shown in [BCG+20a], any weak PCF can be turned into a strong PCF in the random oracle model, by hashing the input before feeding it to the function.
## B Missing Proofs

In this section we present the proofs of the lemmas stated in section 4.1. We start with Lemma 21:

*Proof.* We assume that $B_{\delta,v} \ge \alpha \cdot w$. This translates to a lower bound of the sum of the $Z_{l,k}$:

$$ \sum_{k=1}^{w} Z_{l,k} \ge \alpha \cdot w \cdot \left(\frac{1}{2} - \delta\right) \cdot 2^i, $$

and finally an upper bound on $\Phi$.

$$ \Phi(X_{1,1}, \dots, X_{l,w}) \le 2^{i-1} \cdot w - \alpha \cdot w \cdot \left(\frac{1}{2} - \delta\right) \cdot 2^i = 2^i \cdot w \cdot \left(\frac{1}{2} - \alpha \left(\frac{1}{2} - \delta\right)\right). $$

Setting $\gamma = \frac{1}{2} - \alpha(\frac{1}{2} - \delta)$ we get $\Phi(X_{1,1}, \dots, X_{l,w}) < \gamma \cdot w \cdot 2^i$, which proves that

$$ \Pr[B_{\delta} \ge \alpha \cdot w] \le \Pr[\Phi(X_{1,1}, \dots, X_{l,w}) < \gamma \cdot w \cdot 2^i]. $$

□

We continue with the proof of Lemma 22.

*Proof.* We first rewrite $\mathbb{E}[Z_{l,k}]$ using the standard fact that $\mathbb{E}[Z] = \sum_j \Pr[Z > j]$:

$$ \begin{aligned} \mathbb{E}[Z_{l,k}] &= \mathbb{E}[|R_{l,k} - 2^{i-1}|] = \sum_{j=0}^{2^{i-1}-1} \Pr(|R_{l,k} - 2^{i-1}| > j) \\ &= \sum_{j=0}^{2^{i-1}-1} \Pr(R_{l,k} \ge j + 1 + 2^{i-1}) + \sum_{j=0}^{2^{i-1}-1} \Pr(R_{l,k} \le 2^{i-1} - j - 1). \end{aligned} $$

While we can bound $\Pr[R_{l,k} \ge j + 1 + 2^{i-1}] + \Pr[R_{l,k} \le 2^{i-1} - j - 1]$ by 1 (for every $j$ the two events are disjoint), this only proves that $\mathbb{E}[Z_{l,k}] \le 0.5 \cdot n$. Therefore, we are looking for better bounds on these two probabilities. Both bounds come from the Lemma 8; we prove each of them separately below.

**Lemma 26.** Let $\frac{1}{2} < p < 1$. Let $\theta$ such that $(1-p) \cdot n = \mu \cdot (1-\theta)$. Then,

$$ \Pr[R_{l,k} \ge pn] \le 2 \exp \left( - \frac{\theta^2 \mu^2 (n - \frac{1}{2})}{n^2 - \mu^2} \right). $$

*Proof.* Let $E$ be the random variable equal to the number of empty bins. Remark that when $E > x$ then $R_{l,k} < 2^i - x$. Then, it appears necessarily that

$$ \Pr[R_{l,k} \ge pn] \le \Pr[E \le (1-p)n]. $$

We can then use lemma 8, and establish the following
## B Missing Proofs

In this section we present the proofs of the lemmas stated in section 4.1. We start with Lemma 21:

*Proof.* We assume that $B_{\delta,v} \ge \alpha \cdot w$. This translates to a lower bound of the sum of the $Z_{l,k}$:

$$ \sum_{k=1}^{w} Z_{l,k} \ge \alpha \cdot w \cdot \left(\frac{1}{2} - \delta\right) \cdot 2^i, $$

and finally an upper bound on $\Phi$.

$$ \Phi(X_{1,1}, \dots, X_{l,w}) \le 2^{i-1} \cdot w - \alpha \cdot w \cdot \left(\frac{1}{2} - \delta\right) \cdot 2^i = 2^i \cdot w \cdot \left(\frac{1}{2} - \alpha \left(\frac{1}{2} - \delta\right)\right). $$

Setting $\gamma = \frac{1}{2} - \alpha(\frac{1}{2} - \delta)$ we get $\Phi(X_{1,1}, \dots, X_{l,w}) < \gamma \cdot w \cdot 2^i$, which proves that

$$ \Pr[B_{\delta} \ge \alpha \cdot w] \le \Pr[\Phi(X_{1,1}, \dots, X_{l,w}) < \gamma \cdot w \cdot 2^i]. $$

□

We continue with the proof of Lemma 22.

*Proof.* We first rewrite $\mathbb{E}[Z_{l,k}]$ using the standard fact that $\mathbb{E}[Z] = \sum_j \Pr[Z > j]$:

$$ \begin{aligned} \mathbb{E}[Z_{l,k}] &= \mathbb{E}[|R_{l,k} - 2^{i-1}|] = \sum_{j=0}^{2^{i-1}-1} \Pr(|R_{l,k} - 2^{i-1}| > j) \\ &= \sum_{j=0}^{2^{i-1}-1} \Pr(R_{l,k} \ge j + 1 + 2^{i-1}) + \sum_{j=0}^{2^{i-1}-1} \Pr(R_{l,k} \le 2^{i-1} - j - 1). \end{aligned} $$

While we can bound $\Pr[R_{l,k} \ge j + 1 + 2^{i-1}] + \Pr[R_{l,k} \le 2^{i-1} - j - 1]$ by 1 (for every $j$ the two events are disjoint), this only proves that $\mathbb{E}[Z_{l,k}] \le 0.5 \cdot n$. Therefore, we are looking for better bounds on these two probabilities. Both bounds come from the Lemma 8; we prove each of them separately below.

**Lemma 26.** Let $\frac{1}{2} < p < 1$. Let $\theta$ such that $(1-p) \cdot n = \mu \cdot (1-\theta)$. Then,

$$ \Pr[R_{l,k} \ge pn] \le 2 \exp \left( - \frac{\theta^2 \mu^2 (n - \frac{1}{2})}{n^2 - \mu^2} \right). $$

*Proof.* Let $E$ be the random variable equal to the number of empty bins. Remark that when $E > x$ then $R_{l,k} < 2^i - x$. Then, it appears necessarily that

$$ \Pr[R_{l,k} \ge pn] \le \Pr[E \le (1-p)n]. $$

We can then use lemma 8, and establish the following
$$ \Pr[R_{l,k} \ge pn] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right), $$

where we chose $\theta$ is chosen such that $(1-p)n = \mu \cdot (1 - \theta)$. This proves the first bound we need. □

Let's focus now on the second bound.

**Lemma 27.** Let $p$ such that $\frac{1}{2} < p < 1$. Let $\theta$ such that $(1-p) \cdot n = n - \mu(\theta + 1) - \frac{1}{2}$. Then

$$ \Pr[R_{l,k} \le (1-p)n] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right). $$

*Proof.* First, we state a simple but interesting result:

**Lemma 28.** Let $U$ be the number of bins that contain exactly one ball. Then

$$ U/2 \ge n - E - \frac{l}{2}. $$

*Proof.* If there are $E$ bins empty, and $U$ bins with one ball only, then the remaining $l - U$ balls are contained in at most $(l - U)/2$ bins, and so

$$ E + U + (l - U)/2 \ge \sum_{i} \text{number of bins containing i balls} = n. $$

and thus, $U/2 \ge n - E - \frac{l}{2}$. □

From there using once again lemma 8

$$ \Pr[E \ge \mu(\theta + 1)] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right) $$

$$ \Pr[n - E - \frac{l}{2} \le n - \mu(\theta + 1) - \frac{l}{2}] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right). $$

From there we obtain

$$ \Pr[U/2 \le n - \mu(\theta + 1) - \frac{l}{2}] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right), $$

because $n - E - l/2 \le U/2$. Finally from $U/2 \le R_{l,k}$ we get the desired bound

$$ \Pr[R_{l,k} \le n - \mu(\theta + 1) - \frac{l}{2}] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right) $$

$$ \Pr[R_{l,k} \le (1-p)n] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right), $$

by choosing $\theta$ such that $(1-p) \cdot n = n - \mu(\theta + 1) - \frac{l}{2}$

This proves the second bound we need. □
$$ \Pr[R_{l,k} \ge pn] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right), $$

where we chose $\theta$ is chosen such that $(1-p)n = \mu \cdot (1-\theta)$. This proves the first bound we need. □

Let's focus now on the second bound.

**Lemma 27.** Let $p$ such that $\frac{1}{2} < p < 1$. Let $\theta$ such that $(1-p) \cdot n = n - \mu(\theta + 1) - \frac{1}{2}$. Then

$$ \Pr[R_{l,k} \le (1-p)n] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right). $$

*Proof.* First, we state a simple but interesting result:

**Lemma 28.** Let $U$ be the number of bins that contain exactly one ball. Then

$$ U/2 \ge n - E - \frac{l}{2}. $$

*Proof.* If there are $E$ bins empty, and $U$ bins with one ball only, then the remaining $l - U$ balls are contained in at most $(l - U)/2$ bins, and so

$$ E + U + (l - U)/2 \ge \sum_{i} \text{number of bins containing i balls} = n. $$

and thus, $U/2 \ge n - E - \frac{l}{2}$. □

From there using once again lemma 8

$$ \Pr[E \ge \mu(\theta + 1)] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right) $$

$$ \Pr[n - E - \frac{l}{2} \le n - \mu(\theta + 1) - \frac{l}{2}] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right). $$

From there we obtain

$$ \Pr[U/2 \le n - \mu(\theta + 1) - \frac{l}{2}] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right), $$

because $n - E - l/2 \le U/2$. Finally from $U/2 \le R_{l,k}$ we get the desired bound

$$ \Pr[R_{l,k} \le n - \mu(\theta + 1) - \frac{l}{2}] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right) $$

$$ \Pr[R_{l,k} \le (1-p)n] \le 2 \exp \left( -\frac{\theta^2 \mu^2(n - \frac{1}{2})}{n^2 - \mu^2} \right), $$

by choosing $\theta$ such that $(1-p) \cdot n = n - \mu(\theta + 1) - \frac{l}{2}$

This proves the second bound we need. □
Now we have upper bounds for $\Pr[R_{l,k} \ge pn]$ and $\Pr[R_{l,k} \le (1-p)n]$ for $1/2 < p < 1$. It remains to carefully choose when to start applying these bounds, i.e., when these bounds become better than the naive $\Pr[R_{l,k} \ge pn] + \Pr[R_{l,k} \le (1-p)n] \le 1$.

Thus we want to find the lowest $n$ for which there exists a proportion $1/2 \le p \le 1$ such that the following equation stands

$$ \Pr[R_{l,k} \ge pn] + \Pr[R_{l,k} \le (1-p)n] < 1. \quad (3) $$

Remark that we have the same formula for both bounds, but with different values for $\theta$. Let us call them $\theta_1$ and $\theta_2$. For the first one (lemma 26) we should have $\theta_1$ such that $(1-p) \cdot n = \mu \cdot (1-\theta_1)$; for the second one (lemma 27) should have a $\theta_2$ such that $(1-p) \cdot n = n - \mu(\theta_2 + 1) - \frac{l}{2}$

We remark that $\theta_1 > \theta_2$, thus the value of $n$ we are looking for is coming the second inequality.

The smallest $n$ such that there exists $1/2 < p < 1$ verifying $\Pr[R_{l,k} \le (1-p)n] < 1$ is $n = 2^7$. Then, using Table 3 we can conclude that $n = 2^7$ is enough to find a proportion $p$, as we wanted.

<table><caption>**Table 3.** Rounded value of $2 \exp(-\frac{\theta^2 \mu^2 (n-\frac{1}{2})}{n^2 - \mu^2})$; for the two different $\theta$, with $n = 128$ and $l = n$.</caption><thead><tr><th>1 - p</th><th>0.92</th><th>0.94</th><th>0.96</th><th>0.98</th></tr></thead><tbody><tr><td>θ = θ<sub>1</sub></td><td>5 × 10<sup>-5</sup></td><td>2 × 10<sup>-6</sup></td><td>3 × 10<sup>-7</sup></td><td>4 × 10<sup>-8</sup></td></tr><tr><td>θ = θ<sub>2</sub></td><td>1.31</td><td>0.90</td><td>0.55</td><td>0.3</td></tr></tbody></table>

From these calculations we can also show that $\beta < 0.47$, when $n > 2^7$.

At this stage, we have shown that $\mathbb{E}[\phi(X_{1,1}, \dots, X_{l,w})] \ge 2^i \cdot w \cdot (1/2 - \beta)$, for some positive constant $\beta < 0.5$. Therefore,

$$ \Pr[\phi(X_{1,1}, \dots, X_{l,w}) \le 2^i \cdot w \cdot (1/2 - \beta) - t] \le \exp\left(-\frac{t^2}{2lw}\right). $$

Let us define $\zeta = t/(2^i \cdot w)$. Then, the condition $2^i \cdot w \cdot (\frac{1}{2} - \beta) - t = 2^i \cdot w \cdot \gamma$ rewrites to $\gamma = (1/2 - \beta) - \zeta = 1/2 - \alpha(1/2 - \delta)$. Let us pick a concrete choice of value for $n \ge 2^7$: set $\alpha = 48/49$, $\delta = 1/100$. This gives us a value for $\gamma = 0.02$. As soon as $n \ge 2^7$, we know that $\beta \le 0.47$, and thus $\zeta \ge 0.01$. Hence, there exists a constant $C$ such that

$$ \Pr[B_{\delta,v} \ge \alpha \cdot w] \le 2^{-C \cdot 2^i \cdot w}. $$

This concludes the proof of Lemma 20. □

<figure><img src="image_3.png" /></figure>
Now we have upper bounds for $\Pr[R_{l,k} \ge pn]$ and $\Pr[R_{l,k} \le (1-p)n]$ for $1/2 < p < 1$. It remains to carefully choose when to start applying these bounds, i.e., when these bounds become better than the naive $\Pr[R_{l,k} \ge pn] + \Pr[R_{l,k} \le (1-p)n] \le 1$.

Thus we want to find the lowest $n$ for which there exists a proportion $1/2 \le p \le 1$ such that the following equation stands

$$ \Pr[R_{l,k} \ge pn] + \Pr[R_{l,k} \le (1-p)n] < 1. \quad (3) $$

Remark that we have the same formula for both bounds, but with different values for $\theta$. Let us call them $\theta_1$ and $\theta_2$. For the first one (lemma 26) we should have $\theta_1$ such that $(1-p) \cdot n = \mu \cdot (1-\theta_1)$; for the second one (lemma 27) should have a $\theta_2$ such that $(1-p) \cdot n = n - \mu(\theta_2 + 1) - \frac{l}{2}$

We remark that $\theta_1 > \theta_2$, thus the value of $n$ we are looking for is coming the second inequality.

The smallest $n$ such that there exists $1/2 < p < 1$ verifying $\Pr[R_{l,k} \le (1-p)n] < 1$ is $n = 2^7$. Then, using Table 3 we can conclude that $n = 2^7$ is enough to find a proportion $p$, as we wanted.

<table><caption>**Table 3.** Rounded value of $2 \exp(-\frac{\theta^2 \mu^2 (n-\frac{1}{2})}{n^2 - \mu^2})$; for the two different $\theta$, with $n = 128$ and $l = n$.</caption><thead><tr><th>1 - p</th><th>0.92</th><th>0.94</th><th>0.96</th><th>0.98</th></tr></thead><tbody><tr><td>θ = θ<sub>1</sub></td><td>5 × 10<sup>-5</sup></td><td>2 × 10<sup>-6</sup></td><td>3 × 10<sup>-7</sup></td><td>4 × 10<sup>-8</sup></td></tr><tr><td>θ = θ<sub>2</sub></td><td>1.31</td><td>0.90</td><td>0.55</td><td>0.3</td></tr></tbody></table>

From these calculations we can also show that $\beta < 0.47$, when $n > 2^7$.

At this stage, we have shown that $\mathbb{E}[\phi(X_{1,1}, \dots, X_{l,w})] \ge 2^i \cdot w \cdot (1/2 - \beta)$, for some positive constant $\beta < 0.5$. Therefore,

$$ \Pr[\phi(X_{1,1}, \dots, X_{l,w}) \le 2^i \cdot w \cdot (1/2 - \beta) - t] \le \exp\left(-\frac{t^2}{2lw}\right). $$

Let us define $\zeta = t/(2^i \cdot w)$. Then, the condition $2^i \cdot w \cdot (\frac{1}{2} - \beta) - t = 2^i \cdot w \cdot \gamma$ rewrites to $\gamma = (1/2 - \beta) - \zeta = 1/2 - \alpha(1/2 - \delta)$. Let us pick a concrete choice of value for $n \ge 2^7$: set $\alpha = 48/49$, $\delta = 1/100$. This gives us a value for $\gamma = 0.02$. As soon as $n \ge 2^7$, we know that $\beta \le 0.47$, and thus $\zeta \ge 0.01$. Hence, there exists a constant $C$ such that

$$ \Pr[B_{\delta,v} \ge \alpha \cdot w] \le 2^{-C \cdot 2^i \cdot w}. $$

This concludes the proof of Lemma 20. □
C Handling the Corner Cases

In the proof, we have made two assumptions: $l \in [2^{i-1}, 2^i]$, and $n = 2^i \ge 2^7$ (recall that $l$ is the Hamming weight of the test vector). Therefore, there is some corner cases that are not covered by the proof, the cases when the adversary attempts an attack with a vector of hamming weight $l \in [1, 63]$.

**Case 1: $l$ is odd.** We focus on the first submatrix of our matrix $H$. The matrix has the following shape:

$$H_1 = \begin{bmatrix} u_{1,1}^1 & \cdots & u_{1,w}^1 \\ \vdots & \ddots & \vdots \\ u_{N,1}^1 & \cdots & u_{N,w}^1 \end{bmatrix}$$

where $(u_{k,j}^1)_{1 \le k \le N, 1 \le j \le w}$ are unit vector over $F_2^2$. Each row uniquely corresponds to a uniform $w$-bit vector (we say that it encodes this vector), where each bit indicates the position of the 1 in the 2-bit vector $u_{k,j}^1$ (0 being left, and 1 being right). We denote the $w$-bit string encoded by the $i$-th row by $x_i$. Recall that $e_1$ is distributed as a row of $H_1$. We let $K$ denote the string obtained by flipping all bits in the $w$-bit string that encodes $e_1$. Observe that the inner product between the $i$-th row of $H_1$ and $e_1$ is equal to $\bigoplus_{j=1}^w (x_{i,j} \oplus K_j)$. Given $v$, the vector $v \cdot H_1$ is the XOR of the $l$ rows of $H_1$ corresponding to nonzero entries in $v$. Therefore, whenever $l$ is odd, the value $v \cdot H_1 \cdot e_1$ is of the form $f(H_1) \oplus (\bigoplus_{j=1}^w K_j)$, where $f$ is some appropriate function. That is, value of $v \cdot H_1 \cdot e_1$ is masked by a uniformly random bit equal to $(\bigoplus_{j=1}^w K_j)$: it is therefore perfectly unbiased.

**Case 2: $l$ is even.** Let now focus on the second submatrix $H_2$ of our matrix $H$. It has the following shape:

$$H_2 = \begin{bmatrix} u_{1,1}^2 & \cdots & u_{1,w}^2 \\ \vdots & \ddots & \vdots \\ u_{N,1}^2 & \cdots & u_{N,w}^2 \end{bmatrix}$$

where $(u_{k,j}^2)_{1 \le k \le N, 1 \le j \le w}$ are unit vector over $F_2^4$. This time, each row can be seen as encoding a *pair* of $w$-bits vector: the two bits at position $i$ in both vectors encode together the position of the 1 in the unit length-four vector $u_{k,j}^2$, in binary. For the $i$-th line, let us denote these vectors as $\mathbf{x}_{i,0}$ and $\mathbf{x}_{i,1}$. For the noise vector $e_1$, who has the same structure, we also define two vectors $\mathbf{K}_0$ and $\mathbf{K}_1$, as before by flipping all bits of the two vectors encoded by $e_2$. Now, given a test vector $v$ with even Hamming weight $l$, the value $v \cdot H_2 \cdot e_2$ is equal to
## C Handling the Corner Cases

In the proof, we have made two assumptions: $l \in [2^{i-1}, 2^i]$, and $n = 2^i \ge 2^7$ (recall that $l$ is the Hamming weight of the test vector). Therefore, there is some corner cases that are not covered by the proof, the cases when the adversary attempts an attack with a vector of hamming weight $l \in [1, 63]$.

**Case 1: $l$ is odd.** We focus on the first submatrix of our matrix $H$. The matrix has the following shape:

$$H_1 = \begin{bmatrix} u_{1,1}^1 & \cdots & u_{1,w}^1 \\ \vdots & \ddots & \vdots \\ u_{N,1}^1 & \cdots & u_{N,w}^1 \end{bmatrix}$$

where $(u_{k,j}^1)_{1 \le k \le N, 1 \le j \le w}$ are unit vector over $F_2^2$. Each row uniquely corresponds to a uniform $w$-bit vector (we say that it encodes this vector), where each bit indicates the position of the 1 in the 2-bit vector $u_{k,j}^1$ (0 being left, and 1 being right). We denote the $w$-bit string encoded by the $i$-th row by $x_i$. Recall that $e_1$ is distributed as a row of $H_1$. We let $K$ denote the string obtained by flipping all bits in the $w$-bit string that encodes $e_1$. Observe that the inner product between the $i$-th row of $H_1$ and $e_1$ is equal to $\bigoplus_{j=1}^w (x_{i,j} \oplus K_j)$. Given $v$, the vector $v \cdot H_1$ is the XOR of the $l$ rows of $H_1$ corresponding to nonzero entries in $v$. Therefore, whenever $l$ is odd, the value $v \cdot H_1 \cdot e_1$ is of the form $f(H_1) \oplus (\bigoplus_{j=1}^w K_j)$, where $f$ is some appropriate function. That is, value of $v \cdot H_1 \cdot e_1$ is masked by a uniformly random bit equal to $(\bigoplus_{j=1}^w K_j)$: it is therefore perfectly unbiased.

**Case 2: $l$ is even.** Let now focus on the second submatrix $H_2$ of our matrix $H$. It has the following shape:

$$H_2 = \begin{bmatrix} u_{1,1}^2 & \cdots & u_{1,w}^2 \\ \vdots & \ddots & \vdots \\ u_{N,1}^2 & \cdots & u_{N,w}^2 \end{bmatrix}$$

where $(u_{k,j}^2)_{1 \le k \le N, 1 \le j \le w}$ are unit vector over $F_2^4$. This time, each row can be seen as encoding a pair of $w$-bits vector: the two bits at position $i$ in both vectors encode together the position of the 1 in the unit length-four vector $u_{k,j}^2$, in binary. For the $i$-th line, let us denote these vectors as $\mathbf{x}_{i,0}$ and $\mathbf{x}_{i,1}$. For the noise vector $e_1$, who has the same structure, we also define two vectors $\mathbf{K}_0$ and $\mathbf{K}_1$, as before by flipping all bits of the two vectors encoded by $e_2$. Now, given a test vector $v$ with even Hamming weight $l$, the value $v \cdot H_2 \cdot e_2$ is equal to
$\bigoplus_{i \in S} (\mathbf{x}_{i,0} \oplus \mathbf{K}_0) \cdot (\mathbf{x}_{i,1} \oplus \mathbf{K}_1)$, where $S$ is the subset of nonzero entries in $\mathbf{v}$. Let $g(\mathbf{x}_0, \mathbf{x}_1) = \bigoplus_{j=1}^w x_{i,0,j} \cdot x_{i,1,j}$. With this notation, we can rewrite $\mathbf{v} \cdot H_2 \cdot \mathbf{e}_2$ as

$$ \bigoplus_{i \in S} g(\mathbf{x}_{i,0}, \mathbf{x}_{i,1}) \oplus \left\langle \bigoplus_{i \in S} \mathbf{x}_{i,0}, \mathbf{K}_1 \right\rangle \oplus \left\langle \bigoplus_{i \in S} \mathbf{x}_{i,1}, \mathbf{K}_0 \right\rangle. $$

The leftmost term is independent of the secret noise vector. The above equation implies that if $\bigoplus_{i \in S} \mathbf{x}_{i,0}$ is not the all zero vector, then the above value is additively masked by one of the entries in $\mathbf{K}_1$, which is a uniformly random bit; hence, it is uniformly distributed (the above is a sufficient condition; the same condition with respect to $\mathbf{x}_{i,1}$ and $\mathbf{K}_0$ would also suffice). Furthermore, we can bound the probability that $\bigoplus_{i \in S} \mathbf{x}_{i,0} = 0$: let us call $E_0$ this event. For any fixed choice of the size-$l$ subset $S$, the probability that $\bigoplus_{i \in S} \mathbf{x}_{i,0} = 0$ holds over a random choice of the vectors $\mathbf{x}_{i,0}$ is exactly $2^{-w}$. By a straightforward union bound over all subsets $S$ of size $l$,

$$ \Pr[E_0] \le 2^{-w} \cdot \binom{N}{l} \le 2^{-w} \cdot N^l \le 2^{l \cdot D - w}. $$

Where $N = 2^D$ is the number of rows in $H$. Whenever $l$ is a constant (recall that we assume here $l \le 63$), the above probability is bounded by $2^{-\alpha_0 w}$ as soon as $w > \alpha_1 D$ for an appropriate choice of the constants $\alpha_0, \alpha_1$ (a quick calculation shows that these constants are much better than the ones involved in the case of large $l$, hence the final constants involved in our theorem remain the same as the constants achieved in the previous proof). This concludes the analysis of the corner cases.

## D Script used for simulations

Hereinafter the script written in python used to obtain simulated value of $\beta$. The number of simulations is chosen in order to reach a 99% confidence interval.

import math
import random
import statistics

n = 2048 \# Number of bins

l = 1024 \# Number of balls

T = 100000 \# Number of simulations

List_Z = []

for j in range(T):
    #Repeat for each simulation
    Bins = [0 for k in range(n)]
    countOdd = 0
    #We throw the l balls
$\bigoplus_{i \in S} (\mathbf{x}_{i,0} \oplus \mathbf{K}_0) \cdot (\mathbf{x}_{i,1} \oplus \mathbf{K}_1)$, where $S$ is the subset of nonzero entries in $\mathbf{v}$. Let $g(\mathbf{x}_0, \mathbf{x}_1) = \bigoplus_{j=1}^w x_{i,0,j} \cdot x_{i,1,j}$. With this notation, we can rewrite $\mathbf{v} \cdot H_2 \cdot \mathbf{e}_2$ as

$$ \bigoplus_{i \in S} g(\mathbf{x}_{i,0}, \mathbf{x}_{i,1}) \oplus \left\langle \bigoplus_{i \in S} \mathbf{x}_{i,0}, \mathbf{K}_1 \right\rangle \oplus \left\langle \bigoplus_{i \in S} \mathbf{x}_{i,1}, \mathbf{K}_0 \right\rangle. $$

The leftmost term is independent of the secret noise vector. The above equation implies that if $\bigoplus_{i \in S} \mathbf{x}_{i,0}$ is not the all zero vector, then the above value is additively masked by one of the entries in $\mathbf{K}_1$, which is a uniformly random bit; hence, it is uniformly distributed (the above is a sufficient condition; the same condition with respect to $\mathbf{x}_{i,1}$ and $\mathbf{K}_0$ would also suffice). Furthermore, we can bound the probability that $\bigoplus_{i \in S} \mathbf{x}_{i,0} = 0$: let us call $E_0$ this event. For any fixed choice of the size-$l$ subset $S$, the probability that $\bigoplus_{i \in S} \mathbf{x}_{i,0} = 0$ holds over a random choice of the vectors $\mathbf{x}_{i,0}$ is exactly $2^{-w}$. By a straightforward union bound over all subsets $S$ of size $l$,

$$ \Pr[E_0] \le 2^{-w} \cdot \binom{N}{l} \le 2^{-w} \cdot N^l \le 2^{l \cdot D - w}. $$

Where $N = 2^D$ is the number of rows in $H$. Whenever $l$ is a constant (recall that we assume here $l \le 63$), the above probability is bounded by $2^{-\alpha_0 w}$ as soon as $w > \alpha_1 D$ for an appropriate choice of the constants $\alpha_0, \alpha_1$ (a quick calculation shows that these constants are much better than the ones involved in the case of large $l$, hence the final constants involved in our theorem remain the same as the constants achieved in the previous proof). This concludes the analysis of the corner cases.

## D Script used for simulations

Hereinafter the script written in python used to obtain simulated value of $\beta$. The number of simulations is chosen in order to reach a 99% confidence interval.

import math
import random
import statistics

n = 2048 \# Number of bins

l = 1024 \# Number of balls

T = 100000 \# Number of simulations

List_Z = []

for j in range(T):
    #Repeat for each simulation
    Bins = [0 for k in range(n)]
    countOdd = 0
    #We throw the l balls
for k in range(1):

```
#Choice of the bin among the n
r = random.random(0,n-1)
countOdd += (1-2*Bins[r])
Bins[r] = (Bins[r] +1) % 2
List_Z.append(abs(1/2-countOdd/n))
#Z = n/2 - E[R], and R = countOdd/n.
mean_Z = statistics.mean(List_Z)
# To determine a confidence interval
stdev_Z = statistics.stdev(List_Z)
```

```python
print("The confidence interval at 99% is
: [{}, {}], [{}, {}]".format(
mean_Z, 3*stdev_Z/math.T),
mean_Z, 3*stdev_Z/mathematics.t
```
for k in range(1):

```
#Choice of the bin among the n
r = random.random(0,n-1)
countOdd += (1-2*Bins[r])
Bins[r] = (Bins[r] +1) % 2
List_Z.append(abs(1/2-countOdd/n))
#Z = n/2 - E[R], and R = countOdd/n.
mean_Z = statistics.mean(List_Z)
# To determine a confidence interval
stdev_Z = statistics.stdev(List_Z)
```

```python
print("The confidence interval at 99% is
: [{}, {}], [{}, {}]".format(
mean_Z, 3*stdev_Z/math.T),
mean_Z, 3*stdev_Z/mathematics.T))
```