**Hybrid $\mathcal{H}_0$**: This is the same as hybrid $\mathcal{H}_0$, but here, we remove the steps

$$(\mathbf{sk}_0, \mathbf{pk}_0) \leftarrow \text{PCF.Gen}(1), \text{ and } k_1 \leftarrow \text{PCF.KeyDer}(1, \mathbf{sk}_0, \mathbf{pk}_0),$$

and generate $\mathbf{pk}_0$ and $k_1$ as follows:

1. Let $(\mathbf{sk}_0, \mathbf{pk}_0) \leftarrow \text{PCF.Gen}(0)$.

2. Parse $\mathbf{sk}_0 = (h, r, t, a_{n+1})$, and $\mathbf{pk}_0 = \{(c_0, c_1), (h^{r^s})_{s \in S'}, \alpha_{n+1}\}$.

// To generate $\mathbf{pk}_1$:

3. For $i \in [n]$:

(a) Sample $s_i \stackrel{\$}{\leftarrow} \mathbb{Z}_N$.

(b) Compute $\text{com}_i = G^{s_i}$.

4. Output $\mathbf{pk}_1 = (\text{com}_1, \dots, \text{com}_n)$.

// To generate $k_1$:

5. Run $k_0 \leftarrow \text{PCF.KeyDer}(0, \mathbf{sk}_0, \mathbf{pk}_1)$.

6. parse $k_0 = (h, \mathbf{a})$.

7. Sample $\hat{\mathbf{k}} \stackrel{\$}{\leftarrow} \mathcal{K}$, and compute $\mathbf{k} = g(\hat{\mathbf{k}})$.

8. For $i \in [n]$, compute and set $\alpha_i = a_i \cdot r^{-k_i} \pmod p$.

9. Let $\alpha = (\alpha_1, \dots, \alpha_{n+1})$.

10. Set $k_1 = (\alpha, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$.

Here, differently from Hybrid $\mathcal{H}_0$, the public key $\mathbf{pk}_1$ contains random commitments that are independent of the evaluation key $k_1$. Consequently, we set the key $k_1$ with respect to $\mathbf{sk}_0$ such that for each $i \in [N(\lambda)]$, the OT correlation between $y_0^{(i)}$ and $y_1^{(i)}$ remains correct.

The public key $\mathbf{pk}_1 = (\text{com}_1, \dots, \text{com}_n)$ retains the same distribution as in $\mathcal{H}_0$, since Pedersen commitments are perfectly hiding over $\mathbb{NR}_{2N}$. As a result, Hybrid $\mathcal{H}_1$ remains indistinguishable from Hybrid $\mathcal{H}_0$.

**Hybrid $\mathcal{H}_2$**: This is the same as Hybrid $\mathcal{H}_1$ except that here, we compute $k_0 \leftarrow \text{PCF.KeyDer}(0, \mathbf{sk}_0, \mathbf{pk}_1)$, and then for each $i \in [N(\lambda)]$, we replace

$$y_1^{(i)} \leftarrow \text{PCF.Eval}(1, k_1, x^{(i)})$$

in $\text{Exp}_{\mathcal{A},N,\sigma=0,0}^{\text{sec}}(\lambda)$ with

$$y_0^{(i)} \leftarrow \text{PCF.Eval}(0, k_0, x^{(i)}), \text{ and } y_1^{(i)} \leftarrow \text{RSample}(1^{\lambda}, 0, y_0^{(i)}).$$

Regarding the correctness of the key derivation process, the security of the Naor-Reingold CPRF and Theorem 4, hybrids $\mathcal{H}_2$ and $\mathcal{H}_1$ are indistinguishable.

**Hybrid $\mathcal{H}_3$**: This is the same as hybrid $\mathcal{H}_2$ except that here, we undo the changes that we made in hybrid $\mathcal{H}_1$ and bring back the algorithm $(\mathbf{sk}_1, \mathbf{pk}_1) \leftarrow \text{PCF.Gen}(1^\lambda, \text{pp}, 1)$. The evaluation key $k_1$ is not used in hybrid $\mathcal{H}_2$ anymore, and therefore, removing it does not change the view of party 0. This hybrid remains indistinguishable to hybrid $\mathcal{H}_2$ for the same arguments explained in hybrid $\mathcal{H}_1$.

Note that hybrid $\mathcal{H}_3$ has the same distribution as $\text{Exp}_{\mathcal{A},N,\sigma=0,1}^{\text{sec}}(\lambda)$. This concludes the proof of security of our PK-PCF construction against party 0.

* For $\sigma = 1$, consider the following sequence of hybrid games:

**Hybrid $\mathcal{H}_0$**: This is the game $\text{Exp}_{\mathcal{A},N,\sigma=1,0}^{\text{sec}}(\lambda)$.

**Hybrid $\mathcal{H}_1$**: This is the same as hybrid $\mathcal{H}_0$, but here, we remove the steps

$$(\mathbf{sk}_0, \mathbf{pk}_0) \leftarrow \text{PCF.Gen}(0), \text{ and } k_0 \leftarrow \text{PCF.KeyDer}(0, \mathbf{sk}_0, \mathbf{pk}_1),$$

and generate $\mathbf{pk}_0$ and $k_0$ as explained in the following. We also have to determine a part of the randomness of the PCF.Gen(1) to generate a consistent public key $\mathbf{pk}_1$.
1. Let $(\mathbf{sk}_1, \mathbf{pk}_1) \leftarrow \text{PCF.Gen}(1)$.

2. Parse $\mathbf{sk}_1 = (\mathbf{k}, (s_i)_{i \in [n]})$, and $\mathbf{pk}_1 = (\text{com}_1, \dots, \text{com}_n)$.

// To generate $\mathbf{pk}_0$:

3. Sample $h \stackrel{\$}{\leftarrow} \mathbb{G}$.

4. Sample $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$.

5. For $s \in S'$, compute and set $h_s := h^s$.

6. Compute $(c_0, c_1) = (G^t, H^t)$, where $t \stackrel{\$}{\leftarrow} \mathbb{Z}_N$.

7. Sample $\alpha_{n+1} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$.

8. Set $\mathbf{pk}_0 = ((c_0, c_1), (h_s)_{s \in S'}, \alpha_{n+1})$.

// To generate $\mathbf{k}_0$:

9. Run $\mathbf{k}_1 \leftarrow \text{PCF.KeyDer}(1, \mathbf{sk}_1, \mathbf{pk}_0)$.

10. Parse $\mathbf{k}_1 = (\alpha, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$.

11. For $i \in [n+1]$, compute and set $a_i = \alpha_i \cdot r^{k_i}$ (mod $p$).

12. Let $\mathbf{a} = (a_1, \dots, a_{n+1})$.

13. Set $\mathbf{k}_0 = (h, \mathbf{a})$.

Here, differently from Hybrid $\mathcal{H}_0$, the public key $\mathbf{pk}_0$ contains ciphertexts that are independent from the evaluation key $\mathbf{k}_0$. Consequently, we set the key $\mathbf{k}_0$ with respect to $\mathbf{sk}_1$ such that for each $i \in [N(\lambda)]$, the OT correlation between $y_0^{(i)}$ and $y_1^{(i)}$ remains correct.

The public key $\mathbf{pk}_0 = ((c_0, c_1), (h_s)_{s \in S'}, \alpha_{n+1})$ retains the same distribution as in $\mathcal{H}_0$, since Paillier-ElGamal encryption is semantically secure over $\mathbb{NR}_{2N}$. As a result, Hybrid $\mathcal{H}_1$ remains indistinguishable from Hybrid $\mathcal{H}_0$.

**Hybrid $\mathcal{H}_2$**: This is the same as Hybrid $\mathcal{H}_1$ except that here, we compute $\mathbf{k}_1 \leftarrow \text{PCF.KeyDer}(0, \mathbf{sk}_1, \mathbf{pk}_0)$, and then replace each

$$y_0^{(i)} \leftarrow \text{PCF.Eval}(0, k_0, x^{(i)})$$

in $\text{Exp}_{\mathcal{A},N,\sigma=1,0}^{\text{sec}}(\lambda)$ with

$$y_1^{(i)} \leftarrow \text{PCF.Eval}(1, k_1, x^{(i)}), \text{ and } y_0^{(i)} \leftarrow \text{RSample}(1^{\lambda}, 1, y_1^{(i)})$$

Regarding the security of the Naor-Reingold CPRF and Theorem 4, hybrids $\mathcal{H}_2$ and $\mathcal{H}_1$ are indistinguishable.

**Hybrid $\mathcal{H}_3$**: This is the same as hybrid $\mathcal{H}_2$ except that here, we undo the changes that we made in hybrid $\mathcal{H}_1$ and bring back the algorithms

$$(\mathbf{sk}_0, \mathbf{pk}_0) \leftarrow \text{PCF.Gen}(0), \text{ and } (\mathbf{sk}_1, \mathbf{pk}_1) \leftarrow \text{PCF.Gen}(1).$$

The evaluation key $\mathbf{k}_0$ is not used in hybrid $\mathcal{H}_2$ anymore, and therefore, removing it does not change the view of the adversary (party 1). This hybrid remains indistinguishable to hybrid $\mathcal{H}_2$ for the same arguments explained in hybrid $\mathcal{H}_1$.

Note that hybrid $\mathcal{H}_3$ has the same distribution as $\text{Exp}_{\mathcal{A},N,\sigma=1,1}^{\text{sec}}(\lambda)$. This concludes the proof of security of our PK-PCF construction against party 1.

□

**Remark 5 (security in the case of semi-honest parties).** When proving the security of the PK-PCF scheme presented in Figure 19 against either of the two parties (proof of Theorem 7), we perform steps that are independent from the randomness used in the key generation algorithm of that party. Therefore, the same proof holds against a semi-honest party that can determine the randomness of the key generation algorithm.
## 6.4 Reducing The Public Keys Size to $O(n^{2/3})$

In the public-key PCF of Figure 19, the public keys are of the form

$$pk_0 = \{(c_0, c_1), (h_s)_{s \in S'}, \alpha_{n+1}\}, \text{ and } pk_1 = (\text{com}_1, \dots, \text{com}_n),$$

where $(c_0, c_1)$ is a Paillier-ElGamal ciphertext and $(\text{com}_1, \dots, \text{com}_n)$ are $n$ Pedersen commitments over $\mathbb{N}\mathbb{R}_{2N}$. Regarding the key sizes, $pk_0$ contains 2 elements of $\mathbb{N}\mathbb{R}_{2N}$, while $pk_1$ contains $n$ such elements. In this section we aim to find a better balance for the size of $pk_0$ and $pk_1$.

The key observation is that $pk_1$ that includes a list of Pedersen commitments can be easily made compact using generalized Pedersen commitments which allow committing to $n$ different values by generating a single commitment. However, this must be done while maintaining the correct correlation of derived PCF keys for both parties. In the following, we explain how we achieve the correctness by including more Paillier-ElGamal ciphertexts in $pk_0$ while reducing the total size of the public keys. Let $0 < m \le n$ be a block size. The idea is the following:

- Let $G, H_1, \dots, H_m$ be random elements of $\mathbb{N}\mathbb{R}_{2N}$.

- Party 1 divides the wPRF key $k$ into consecutive subvectors $k_1, \dots, k_\delta$, each of length $m$. It then commits to each subvector $k_u$ by generating generalized Pedersen commitments $\text{com}_u = G^{s_u} \cdot \prod_{j=1}^{m} H_j^{k_u^{(j)}},$ for all $u \in [\delta]$.

- Party 0 generates $m^2$ Paillier-ElGamal encryptions of $r'$ with randomness reuse as follows:

$$(c_1^0, c_1^1, \dots, c_1^m) = (G^{t_1}, H_1^{t_1} \cdot (1+N)^{r'}, H_2^{t_1}, \dots, H_m^{t_1})$$

$$(c_2^0, c_2^1, \dots, c_2^m) = (G^{t_2}, H_1^{t_2}, H_2^{t_2} \cdot (1+N)^{r'}, \dots, H_m^{t_2})$$

$\vdots$

$$(c_m^0, c_m^1, \dots, c_m^m) = (G^{t_m}, H_1^{t_m}, H_2^{t_m}, \dots, H_m^{t_m} \cdot (1+N)^{r'}).$$

- Party 0 publishes the $m^2$ ciphertexts $(c_i^0, c_i^j)_{i,j \in [m]}$ as a part of $pk_0$ and party 1 publishes the $n/m$ generalized commitments $\text{com}_1, \dots, \text{com}_\delta$ as a part of $pk_1$.

By inspection, one can see that for each $u \in [\delta]$ and each $v \in [m]$, it holds that

$$\text{com}_u^{tv} \cdot (1+N)^{r' \cdot k_u^{(v)}} = (c_v^0)^{s_u} \cdot \prod_{j=1}^{m} (c_v^j)^{k_u^{(j)}}.$$

Therefore, the two parties can first derive multiplicative shares of $(1+N)^{r' \cdot k_u^{(v)}}$, and as before, after applying the DDLog algorithm over their shares and mapping the result in $\mathbb{G}$, they can compute their PCF keys.

Doing as explained above yields publishing $m^2 + 2m + n/m$ elements (including $G, H_1, \dots, H_m$ elements of the public parameters), where $n$ denotes the length of the wPRF key $k$. Minimizing with respect to $m$ results in $O(n^{2/3})$ elements.

The security analysis of the construction is similar to that of the public-key PCF presented in Figure 19 (See proof of Theorem 7) where we now leverage the perfectly-hiding property of generalized Pedersen commitments and semantic security of Paillier-ElGamal ciphertexts with randomness reuse over $\mathbb{N}\mathbb{R}_{2N}$.

The construction of the resulting optimized public-key PCF is provided in Figure 20.

**Optimized PK-PCF for OT Correlations from sparse power-DDH and DCR (with compressed public keys)**

Requires:
- Let $F: \mathcal{K} \times \mathcal{X} \to \{0,1\}$ be an IPM-wPRF with respect to an IPM set $S$ and predicate functions $f,g$ (See Definition 13). We assume that $S$ is $\Delta$-antiperiodic, and consider $S' = S \cup \{-\Delta/2, \dots, -1\}$.

- Let $p$ be a safe prime, i.e., $p = 2q + 1$ for a prime $q$, and $N = PQ$ for primes $P$ and $Q$.

- Let $\text{DDLog}_N$ be the distributed discrete logarithm algorithm as in Lemma 5.

- Let Hash be a hash function modeled as a random oracle.

### PCF.setup(1^\lambda):

1. $(\mathbb{G}, g, p) \stackrel{\$}{\leftarrow} \text{GenPar}(1^\lambda)$.

2. Sample a generator $g_q$ of $QR_p$.

3. Sample $G' \stackrel{\$}{\leftarrow} \mathbb{Z}_{N^2}$, and set $G \leftarrow (G')^{2N} \pmod{N^2}$.

4. For $i \in [m]$, sample $d_i \stackrel{\$}{\leftarrow} \mathbb{Z}_{N^2}$, and set $H_i \leftarrow G^{d_i} \pmod{N^2}$.

5. Output $\mathbf{pp} = (\mathbb{G}, p, g_q, (G, H_1, \dots, H_m), F)$.

### PCF.Gen0(1^\lambda):

1. Sample $h \stackrel{\$}{\leftarrow} \mathbb{G}$.

2. Sample $r' \stackrel{\$}{\leftarrow} \mathbb{Z}_q$, and set $r := g_q^{r'} \pmod{p}$.

3. For $i \in [m]$ do:

(a) Sample $t_i \stackrel{\$}{\leftarrow} \mathbb{Z}_N$.

(b) Compute $\mathbf{c}_i = (c_i^0, c_i^1, \dots, c_i^m)$, where $c_i^0 = G^{t_i}$, and $c_i^j = H_i^{t_i} \cdot (1+N)^{r'}$, and $c_i^{j'} = H_j^{t_i}$ for all $j \neq i \in [m]$.

// $m^2$ Paillier-ElGamal encryptions of $r'$.

4. For $s \in S'$, compute and set $h_s := h^{r_s}$.

5. Sample $a_{n+1} \stackrel{\$}{\leftarrow} \mathbb{Z}_p^*$, and set $\alpha_{n+1} = a_{n+1} \cdot r^\Delta$.

6. Set $\mathbf{sk}_0 = (h, r, (t_i)_{i \in [m]}, a_{n+1})$.

7. Set $\mathbf{pk}_0 = \{(c_i^0, (c_i^j))_{i,j \in [m]}, (h_s)_{s \in S'}, \alpha_{n+1}\}$.

8. Output $(\mathbf{sk}_0, \mathbf{pk}_0)$.

### PCF.Gen1(1^\lambda):

1. Sample $\hat{k} \stackrel{\$}{\leftarrow} \mathcal{K}$.

2. Compute $k \leftarrow g(\hat{k})$.

3. Partition $k$ into $\delta$ subvectors $k_1, k_2, \dots, k_\delta$ of length $m$.

4. For $u \in [\delta]$:

(a) Parse $k_u = (k_u^{(1)}, \dots, k_u^{(m)})$.

(b) Compute $\mathbf{com}_u = G^{s_u} \cdot \prod_{j=1}^{m} H_j^{k_u^{(j)}}$,

where $s_u \stackrel{\$}{\leftarrow} \mathbb{Z}_N$.

// Generalized Pedersen commitment of $k_u$.

5. Set $\mathbf{sk}_1 = ((k_u)_{u \in [\delta]}, (s_u)_{u \in [\delta]})$.

6. Set $\mathbf{pk}_1 = (\mathbf{com}_1, \dots, \mathbf{com}_\delta)$.

7. Output $(\mathbf{sk}_1, \mathbf{pk}_1)$.

### PCF.KeyDer(\sigma, sk_\sigma, pk_{1-\sigma}):

1. If $\sigma = 0$:

(a) Parse $\mathbf{sk}_0 = (h, r, (t_i)_{i \in [m]}, a_{n+1})$.

(b) Parse $\mathbf{pk}_1 = (\mathbf{com}_1, \dots, \mathbf{com}_\delta)$.

(c) For $u \in [\delta]$, and $v \in [m]$:
set $A_i = (\mathbf{com}_u)^{t_v}$, where

$$i = m(u-1) + v.$$

$$\text{ // } A_i = G^{t_v \cdot s_u} \cdot \prod_{j=1}^{m} H_j^{k_u^{(j)} \cdot t_v}.$$

(d) For $i \in [n]$:

i. compute $\hat{a}_i \leftarrow \text{DDLog}_N(A_i)$.

ii. set $a_i := g_q^{\hat{a}_i}$.

(e) Set $\mathbf{a} = (a_1, \dots, a_{n+1})$.

(f) Set and output $k_0 = (h, \mathbf{a})$.

2. If $\sigma = 1$:

(a) Parse $\mathbf{sk}_1 = ((k_u)_{u \in [\delta]}, (s_u)_{u \in [\delta]})$.

(b) Parse $\mathbf{pk}_0 = \{(c_i^0, (c_i^j))_{i,j \in [m]}, (h_s)_{s \in S'}, \alpha_{n+1}\}$.

(c) For $u \in [\delta]$, and $v \in [m]$:

set $B_i = (c_v^0)^{s_u} \cdot \prod_{j=1}^{m} (c_v^j)^{k_u^{(j)}}$, where

$$i = m(u-1) + v.$$

$$\text{ // } B_i = G^{t_v \cdot s_u} \cdot \prod_{j=1}^{m} H_j^{k_u^{(j)} \cdot t_v} \cdot (1+N)^{r' \cdot k_u^{(v)}}.$$

(d) For $i \in [n]$:

i. compute $\hat{a}_i \leftarrow \text{DDLog}_N(B_i)$.

ii. set $\alpha_i = g_q^{\hat{a}_i} \pmod{p}$.

(e) Set $\mathbf{\alpha} = (\alpha_1, \dots, \alpha_{n+1})$.

(f) Set and output $k_1 = (\mathbf{\alpha}, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$.
PCF.Eval(1^λ, σ, k_σ, ˆx = (ˆx_1, ..., ˆx_n)):

1. If $\sigma = 0$:

(a) Parse $k_0 = (h, \mathbf{a})$.

(b) Compute $\mathbf{x} = (x_1, \dots, x_n) \leftarrow f(\hat{x})$.

(c) Compute $r_0 = h_{i=1}^{\prod_{i=1}^{n} a_i^{x_i}}$.

(d) Compute $r_1 = h_{i=1}^{\prod_{i=1}^{n} a_i^{x_i} \cdot a_{n+1}}$.

(e) Set and output $y_0 \leftarrow (\text{Hash}(r_0), \text{Hash}(r_1))$.

2. If $\sigma = 1$:

(a) Parse $k_1 = (\alpha, (h_s)_{s \in S'}, \mathbf{k}, \Delta)$.

(b) Compute $\mathbf{x} = (x_1, \dots, x_n) \leftarrow f(\hat{x})$.

(c) Let $b = F_k(\hat{x})$, and $s = \langle \mathbf{x}, \mathbf{k} \rangle - b \cdot \Delta$.

(d) Compute $r = (h_s)_{i=1}^{\prod_{i=1}^{n} \alpha_i^{x_i} \cdot \alpha_{n+1}^b}$.

(e) Set and output $y_1 \leftarrow (b, \text{Hash}(r))$.

<caption>**Fig. 20.** Public-Key PCF for OT Correlations with Public Key Size $O(n^{2/3})$.</caption>

# 7 DV-NIZKs from PK-PCFs

In this section, taking the advantage of *non-interactive* PK-PCF, we propose a new construction of *reusable* DV-NIZK argument of knowledge from a compiler that combines a sigma protocol for general NP language and a public-key PCF. Specifically, our *reusable* DV-NIZK comes from three ingredients:

- A $\Sigma$-protocol [CDS94] with 1-bit challenges for an NP-complete language $\mathcal{L}$, for example Blum's protocol for graph Hamiltonicity [Blu86].

- A *strong* public key PCF for OT correlation where the key evaluation of each party can be *silently* obtained from their own secret key and public key of the other.

- A *non-reusable* DV-NIZK with computational adaptive soundness knowledge and adaptive zero-knowledge properties.

We also show how to enhance our construction to obtain a *reusable* DV-NIZK based on a *weak* public key PCF instead of the strong one. We state the formal result below.

**Theorem 8.** If there exists a weak public-key PCF then we can construct a *reusable DV-NIZK argument of knowledge for NP language from a $\Sigma$-protocol and a non-reusable DV-NIZK scheme*.

## 7.1 Construction of reusable DVNIZK

**$\Sigma$-protocol.** A $\Sigma$-protocol is a 3-move, interactive proof (fig. 21) which consists of three algorithms $(\Sigma.P_1, \Sigma.P_2, \Sigma.V)$. While $(x, w) \in \mathbb{R}$, the prover inputs $(x, w)$ to $\Sigma.P_1$ and produces a random message $a$ to the verifier while $a$ is considered as a commitment of $x$. The verifier then samples a random challenge bit $b$ and sends it to the prover. The prover runs the algorithm $\Sigma.P_2(x, w, a, b)$ to produce a response $z_b$ corresponding to bit challenge $b$ and sends $z_b$ to the verifier. Finally, the verifier runs $\Sigma.V(x, a, b, z_b)$ to decide whether accept or reject the proof.

$\Sigma$-protocol satisfies 3 properties: perfect completeness, 2-special soundness (given two accepting transcripts $(a, 0, z_0)$, $(a, 1, z_1)$ of a statement $x$ then there exists an efficient algorithm $\Sigma.\text{Ext}(x, a, z_0, z_1)$ to extract the witness $w$) and special honest-verifier zero-knowledge (given $b$ ahead of time, there exists a simulator $\text{Sim}(x, b)$ simulating the transcript $(a, b, z_b)$ without knowing a witness). The Blum's Hamiltonicity protocol [Blu86] is an instantiation of $\Sigma$-protocol with 1-bit challenges for NP language.
### Σ-protocol

<figure><img src="image_9.png" /><figcaption>**Fig. 21.** Σ-protocol with challenge space {0,1}.</figcaption></figure>

**Public-key PCF.** To apply PK-PCF fig. 10 to our reusable DVNIZK scheme, we provide a higher security definition of PK-PCF compared to the one in fig. 17. The formal definition is shown as below:

**Strong Security.** Define Supp(PCF.Gen(1$^{λ}$, pp, σ)) be a constraint relation such that for all (sk$_{σ}$, pk$_{σ}$) ∈ Supp(PCF.Gen(1$^{λ}$, pp, σ)) then there exists a public coin ρ ∈ pp such that (sk$_{σ}$, pk$_{σ}$) = PCF.Gen(1$^{λ}$, pp, σ, ρ).

### Experiment PCF Strong Security

Exp<sub>A,N,σ,0</sub>(λ):
pp ← PCF.setup(1<sup>λ</sup>)
(sk<sub>σ</sub>, pk<sub>σ</sub>) ← PCF.Gen(1<sup>λ</sup>, pp, σ)
(sk<sub>1-σ</sub>, pk<sub>1-σ</sub>) ← PCF.Gen(1<sup>λ</sup>, pp, 1 - σ)
k<sub>1-σ</sub> ← PCF.KeyDer(1 - σ, sk<sub>1-σ</sub>, pk<sub>σ</sub>)
For i = 1, ..., N(λ):
x<sup>(i)</sup> $\leftarrow\{0, 1\}^{n(λ)}$
y<sup>(i)</sup><sub>1-σ</sub> ← PCF.Eval(1 - σ, k<sub>1-σ</sub>, x<sup>(i)</sup>)
For all i ∈ [N(λ)]:
b ← A(1<sup>λ</sup>, pk<sub>0</sub>, pk<sub>1</sub>, σ, sk<sub>σ</sub>, (x<sup>(i)</sup>, y<sup>(i)</sup><sub>1-σ</sub>))
Output b

Exp<sub>A,N,σ,1</sub>(λ):
pp ← PCF.setup(1<sup>λ</sup>)
∀pk<sub>σ</sub> such that: ∃sk<sub>σ</sub>,
(sk<sub>σ</sub>, pk<sub>σ</sub>) ∈ Supp(PCF.Gen(1<sup>λ</sup>, pp, σ))
(sk<sub>1-σ</sub>, pk<sub>1-σ</sub>) ← PCF.Gen(1<sup>λ</sup>, pp, 1 - σ)
k<sub>σ</sub> ← PCF.KeyDer(σ, sk<sub>σ</sub>, pk<sub>1-σ</sub>)
For i = 1, ..., N(λ):
x<sup>(i)</sup> $\leftarrow\{0, 1\}^{n(λ)}$
y<sup>(i)</sup><sub>σ</sub> ← PCF.Eval(σ, k<sub>σ</sub>, x<sup>(i)</sup>)
y<sup>(i)</sup><sub>1-σ</sub> ← RSample(1<sup>λ</sup>, σ, y<sup>(i)</sup><sub>σ</sub>)
For all i ∈ [N(λ)]:
b ← A(1<sup>λ</sup>, pk<sub>0</sub>, pk<sub>1</sub>, σ, sk<sub>σ</sub>, (x<sup>(i)</sup>, y<sup>(i)</sup><sub>1-σ</sub>))
Output b

**Fig. 22.** Strong security of a PK-PCF. Here, RSample is the algorithm for reverse sampling $\mathcal{Y}$ as in the definition 3.

For every $\sigma \in \{0,1\}$ and every non-uniform adversary $\mathcal{A}$ of size $B(\lambda)$, it holds that for all sufficiently large $\lambda$.

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

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

**Non-reusable DV-NIZK arguments.** Let $\mathcal{L}_P$ be an NP language associated with an NP relation $\mathcal{R}_P$. We take advantage of a (one-time) DV-NIZK scheme for $\mathcal{L}_P$ which consists of three algorithms $dv = (dv.\text{Setup}, dv.P, dv.V)$. For convenience, we define the notion of a DV-NIZK as below.

$$dv.\text{Setup}(1^{\lambda}) \rightarrow (dv.crs, dv.T).$$
$$- \mathrm{dv.P}(\mathrm{dv.crs}, x, w) \to \mathrm{dv.\pi}.$$

$$- \mathrm{dv.V}(\mathrm{dv.crs}, x, \mathrm{dv.\pi}, \mathrm{dv.}\mathcal{T}) \to \{0, 1\}.$$

The dv scheme needs to satisfy perfect completeness, computational (bounded) adaptive knowledge soundness and computational zero-knowledge properties. The non-reusable DV-NIZK can be constructed from a public-key encryption scheme [PsV06] by $\lambda$ invocations of $\Sigma$-protocol. In our construction, dv is used to prove that the prover uses the correct form of $pk_P$ to generate the proof. Specifically, for a statement $pk_P$ and a witness $sk_P$ we consider $pk_P \in \mathcal{L}_p$, $(pk_P, sk_P) \in \mathcal{R}_P$ if $(pk_P, sk_P) \in \mathrm{Supp}(\mathrm{PCF}.\mathrm{Gen}_0(1^{\lambda}, \mathrm{PCF}.\mathrm{pp}))$.

**Reusable DV-NIZK from PK-PCF.** We show how to combine a $\Sigma$-protocol (fig. 21), a non-reusable DV-NIZK, and a strong public-key PCF to obtain a reusable DV-NIZK scheme for all NP language. Let $\mathcal{R}$ be an NP language, $(x, w) \in \mathcal{R}$, then our re-usable DV-NIZK scheme (Setup, P, V) is defined as detailed in Figure 23.

**Reusable DV-NIZK: $\Pi(\mathrm{Setup}, P, V)$**

* **Setup(1^\lambda).**

- Compute PCF.pp $\leftarrow$ PCF.setup(1^\lambda), $(pk_V, sk_V) \leftarrow$ PCF.Gen_1(1^\lambda, PCF.pp) and $(\mathrm{dv.crs}, \mathrm{dv.}\mathcal{T}) \leftarrow \mathrm{dv.setup}(1^\lambda)$.

- Return crs := (PCF.pp, dv.crs, pk_V) and $\mathcal{T} := (sk_V, \mathrm{dv.}\mathcal{T})$.

* **P(crs, x, w).**

1. Compute $(pk_P, sk_P) \leftarrow$ PCF.Gen_0(1^\lambda, PCF.pp), $k_0 \leftarrow$ PCF.KeyDer(0, sk_P, pk_V)$\quad$ and generate $\mathrm{dv.\pi} = \mathrm{dv.P}(\mathrm{dv.crs}, pk_P, sk_P)$.

2. For each $i \in [1, \lambda]$ generate all $\Sigma$-protocol transcripts for both challenges $b \in [0, 1]$:

$$a_i = \Sigma.P_1(x, w)$$

$$z_{i,b} = \Sigma.P_2(x, w, a_i, j) \text{ for } b \in [0, 1]$$

3. Compute $(r_{i,0}, r_{i,1}) = \mathrm{PCF.Eval}(1^\lambda, 0, k_0, x)$ and for each $i \in [1, \lambda]$, $b \in [0, 1]$ define $m_{i,b} = z_{i,b} \oplus r_{i,b}$.

4. Define the output $\pi := (pk_P, \mathrm{dv.\pi}, \{a_i, m_{i,0}, m_{i,1}\}_{i \le \lambda})$.

* **V(crs, x, \pi, \mathcal{T}).**

1. Check if $\mathrm{dv.V}(\mathrm{dv.crs}, pk_P, \mathrm{dv.\pi}, \mathrm{dv.}\mathcal{T}) = 1$ then Compute $k_1 \leftarrow \mathrm{PCF.KeyDer}(1, sk_V, pk_P)$ and for each $i \in [1, \lambda]$, compute as follows:

$$\mathrm{PCF.Eval}(1^{\lambda}, 1, k_1, x) = (b_i, r_{i,b_i}), \quad z_{i,b_i} = m_{i,b_i} \oplus r_{i,b_i}$$

The output is defined $\mathrm{V}(\mathrm{crs}, x, \pi, \mathcal{T}) = 1$ if $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$.

2. Otherwise, $\mathrm{V}(\mathrm{crs}, x, \pi, \mathcal{T}) \to 0$.

**Fig. 23.** Reusable DV-NIZK construction.

The reusable knowledge soundness of our DV-NIZK construction (fig. 23) follows from the special soundness of $\Sigma$-protocol, knowledge soundness of DV-NIZK to extract a valid witness with high probability whenever prover outputs an accepted proof. In particular, we build a simulator can simulate the verification query without knowing the $sk_V$ and an efficient extractor Ext can extract a valid witness by using $\mathrm{dv.Ext}$ to get the $sk_P$ then later use $\Sigma.Ext$ with accepted transcripts to extract witness $w$.

Our DV-NIZK scheme (fig. 23) is zero-knowledge because there exists a simulator knowing ahead of time the challenge $b \in [0, 1]$ that can simulate the view of the verifier $(a_i, b, z_{i,b})$ without knowing the witness. Therefore, the view of the verifier in $\Pi$ can be simulated by a simulator that for each $i$-invocation of the proof defines $m_{i,b} := z_{i,b} \oplus r_{i,b}$ and picks a dummy item for $m_{i,1-b}$.

**Theorem 9 (Completeness).** If dv, $\Sigma$ are complete and PCF is correct then DV-NIZK scheme from fig. 23 is complete.
Proof. Consider $(x, w) \in \mathcal{R}$, by completeness of the non-reusable DV-NIZK, $dv.V(dv.crs, pk_P, dv.\pi, dv.T)$ accepts for all pair $(pk_P, sk_P) \in \mathcal{R}_P$ which is correctly generated and by correction of the PCF and completeness of $\Sigma$-protocol, $\Sigma.V(x, a_i, b_i, z_{i,b_i})$ also accept for all $i \in [1, \lambda]$. $\square$

**Theorem 10 (Knowledge soundness).** If $dv$ is adaptive knowledge sound, $\Sigma$ is 2-special sound and PCF for OT correlation satisfies strong PK-PCF security property then DV-NIZK scheme from fig. 23 is reusable adaptive knowledge soundness.

Proof. We describe an efficient simulator $Sim$ that correctly emulates the verifier without knowing about $sk_V$. The simulator is done as follows:

- $SimSetup(1^{\lambda})$: compute PCF. Setup(1^{\lambda}).) $\rightarrow$ PCF.pp, PCF.Gen$_1$(1^{\lambda}, PCF.pp) $\rightarrow$ (pk$_V$, sk$_V$) and $dv. Setup(1^{\lambda}) \rightarrow$ (dv.crs, dv.T), define the output (PCF.pp, dv.crs, pk$_V$) $\rightarrow$ crs, a trapdoor $T := (sk_V, dv.T)$ and erase sk$_V$.

- $Sim.V(crs, x, \pi, dv.T)$: parse $\pi = (pk_P, dv.\pi, \{a_i, m_{i,0}, m_{i,1}\}_{i \le \lambda})$, use the $dv. Ext$ to extract the $sk_P$ i.e $sk_P \leftarrow dv. Ext(crs, pk_P, dv.T)$. From $sk_P$, for each $i \in [1, \lambda]$, compute $k_0 \leftarrow PCF.KeyDer(0, sk_P, pk_V)$, $(r_{0,i}, r_{1,i}) \leftarrow PCF.Eval(1^{\lambda}, 0, k_0, x)$, $(b_i, r_{i,b_i}) \leftarrow RSample(1^{\lambda}, 0, (r_{0,i}, r_{1,i}))$ then define $(z_{0,i}, z_{1,i}) = (m_{i,0} \oplus r_{0,i}, m_{i,1} \oplus r_{1,i})$. Firstly, check that if $(pk_P, sk_P) \notin \mathcal{R}_P$ then outputs 0. Otherwise, continue to check $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$. If all checks succeeded, accept (output 1). Otherwise, reject (output 0). To extract a witness, pick $i \stackrel{\$}{\leftarrow} [1, \lambda]$ then define $w \leftarrow \Sigma. Ext(x, a_i, z_{i,0}, z_{i,1})$.

The simulator $Sim$ first calls $SimSetup(1^{\lambda})$ to generate crs, and store $dv.T$. Each time the $\mathcal{A}$ sends a query $(x, \pi)$ to the oracle $O(crs, \dots, T)$, $Sim$ simulates $O(crs, \dots, T)$ (without knowing $sk_V$) by running $Sim.V(crs, x, \pi, dv.T)$ and outputs whatever $Sim.V$ outputs. When $\mathcal{A}$ outputs a final answer $(x^*, \pi^*)$, $Sim$ computes a witness $w$ as in $Sim.V$.

We prove the following claim: for any input $(x, \pi)$, it hold that

$$ \Pr \left[ \begin{array}{l} (crs, T) \leftarrow Setup(1^{\lambda}) \\ b \leftarrow Sim.V(crs, x, \pi, dv.T) : b = b' \\ b' \leftarrow V(crs, x, \pi, T) \end{array} \right] \approx 1 $$

We show that if $b = 1$, then $b' = 1$ with overwhelming probability. Indeed, if $b = 1$ it means

- $(pk_P, sk_P) \in \mathcal{R}_P$ then $dv.V(dv.crs, pk_P, dv.\pi, dv.T) = 1$.

- $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$ where $b_i \stackrel{\$}{\leftarrow} \{0, 1\}$ (output of $RSample$) then by the soundness of $\Sigma$-protocol, we have $(x, w) \in \mathcal{R}$ with a probability of at least $1 - 1/2^{\lambda}$. This leads to $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$ and $b_i \in \{0, 1\}$ (output of PCF.Eval) with a probability of at least $1 - 1/2^{\lambda}$.

Therefore, $V(crs, x, \pi, T) = 1$ i.e if $Sim$'s checks succeeding then the verifier's checks necessarily succeed with high probability. In particular, the probability that the $Sim$ accepts the proof while the verifier rejects it is at most $\epsilon_{\Sigma} = 1/2^{\lambda}$.

We next prove that if $b' = 1$ then $b = 1$ with high probability. Assume the $Sim$ rejects the proof while the verifier accepts it. Let denote $\epsilon$ as the probability of verifier that accepts the proof. Since $Sim$ rejects the proof then at least one of checks must fail: either $(pk_P, sk_P) \notin \mathcal{R}_P$ or $\exists i \in [1, \lambda] : \Sigma.V(x, a_i, b_i, z_{i,b_i}) = 0$ ($b_i$ is output of $RSample$). Because the verifier accepts the proof then $dv.V(dv.crs, pk_P, dv.\pi, dv.T) = 1$ and $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$ and $b_i$ is output of PCF.Eval (computed honestly).

- By the knowledge soundness of $dv$ then

$$ \Pr \left[ (pk_P, sk_P) \notin \mathcal{R}_P \middle| \begin{array}{l} dv.V(dv.crs, pk_P, dv.\pi, dv.T) = 1 \\ sk_P \leftarrow dv. Ext(crs, pk_P, dv.\pi, dv.T) \end{array} \right] = \epsilon_{dv} $$
- By the security of PCF, $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$ and $b_i$ is output of PCF.Eval (computed honestly) can be simulated indistinguishable by $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1$ for all $i \in [1, \lambda]$ and $b_i$ is output of RSample i.e a random bit. After that, since $b_i$ is uniformly random then by the soundness of $\Sigma$- protocol, with high probability $(x, w) \in \mathcal{R}$.

For convenience, we denote the event $\Sigma.V(x, a_i, b_i, z_{i,b_i}) = 1 \forall i \in [1, \lambda]$ where $b_i \stackrel{\$}{\leftarrow} \{0, 1\}$ as Ver and $\exists i \in [1, \lambda]: \Sigma.V(x, a_i, b_i, z_{i,b_i}) = 0$ where $b_i \stackrel{\$}{\leftarrow} \{0, 1\}$ as Bad. Then from the security of PCF and the soundness of sigma protocol, we have:

$$ \Pr[\text{Ver}] \ge \epsilon - \epsilon_{\text{PCF}} \quad \text{and} \quad \Pr[\text{Ver} | \text{Bad}] \le \epsilon_{\Sigma} $$

Observe that:

$$ \begin{aligned} \Pr[\text{Ver}] &= \Pr[\text{Ver} \land \text{Bad}] + \Pr[\text{Ver} \land \overline{\text{Bad}}] \\ &= \Pr[\text{Ver} | \text{Bad}] \cdot \Pr[\text{Bad}] + \Pr[\text{Ver} \land \overline{\text{Bad}}] \le \epsilon_{\Sigma} + \Pr[\text{Ver} \land \overline{\text{Bad}}] \end{aligned} $$

Then we obtain $\Pr[\text{Ver} \land \overline{\text{Bad}}] \ge \epsilon - \epsilon_{\text{PCF}} - \epsilon_{\Sigma}$. Putting everything together, the verifier accepts a proof with probability of $\epsilon$ then the simulator also accept this proof with probability of at least $\epsilon - \epsilon_{\text{PCF}} - \epsilon_{\Sigma} - \epsilon_{\text{dv}}$.

In conclusion, we have:

$$ \Pr \left[ \begin{array}{l} (\text{crs}, \mathcal{T}) \leftarrow \text{Setup}(1^{\lambda}) \\ b \leftarrow \text{Sim.V}(\text{crs}, x, \pi, \text{dv.}\mathcal{T}) : b = b' \\ b' \leftarrow \text{V}(\text{crs}, x, \pi, \mathcal{T}) \end{array} \right] \ge 1 - \mu $$

where $\mu = \epsilon_{\text{dv}} + 2 \cdot \epsilon_{\Sigma} + \epsilon_{\text{PCF}} = \text{negl}(\lambda)$.

Now consider an $\mathcal{A}$ that outputs an accepting proof with probability of at least $\epsilon$ after $\mathcal{Q}$ polynomial times queries to oracle $\mathcal{O}(\text{crs}, \dots, \mathcal{T})$. By the above claim, $\mathcal{A}$ outputs an accepting proof with probability of at least $\epsilon - \mathcal{Q} \cdot \mu$ after interacting $\mathcal{Q}$ times with $\text{Sim.V}(\text{crs}, x, \pi, \text{dv.}\mathcal{T})$; moreover, with probability at least $1 - \mu'$ ($\mu' = \epsilon_{\text{dv}} + \epsilon_{\Sigma} + \epsilon_{\text{PCF}}$), this proof is also accepted by $\text{Sim}$'s verification algorithm. Overall, $\text{Sim}$ obtains a proof accepted by his verification algorithm with probability at least $\approx \epsilon - (\mathcal{Q} + 1)\mu$. In particular, this implies that $w$ extracted by $\text{Sim}$ from $\pi$ satisfies $(x, w) \in \mathcal{R}$ with probability at least $\epsilon - (\mathcal{Q} + 1)\mu$. Therefore, $\text{Sim}$ extracts a valid witness with probability at least $\epsilon - (\mathcal{Q} + 1)\mu$. As $(\mathcal{Q} + 1)\mu = \text{negl}(\lambda)$, we conclude that if $\mathcal{A}$ outputs an accepting proof with non-negligible probability, then $\text{Sim}$ extracts a valid witness with non-negligible probability.

**Theorem 11 (Zero Knowledge).** If $\text{dv}$ is adaptive single-theorem ZK, $\Sigma$ is special-honest verifier ZK and strong PCF satisfies pseudorandom $\mathcal{Y}$-output property then DV-NIZK scheme from fig. 23 is adaptive multi-theorem ZK.

*Proof.* Denote $\text{Sim}_{\Sigma}$ as the efficient simulator for $\Sigma$-protocol to prove HVZK property. Formally, given a challenger $b_i$ ahead of time, $\text{Sim}_{\Sigma}$ can output an accepting proof without knowing the witness i.e $\text{Sim}_{\Sigma}(x, b_i) \to (a, b_i, z_{b_i})$ such that $\Sigma.V(x, a, b_i, z_{b_i}) = 1$. And for (one time) DV-NIZK scheme, there exists a simulator $\text{Sim}_{\text{dv}} = (S_1^{\text{dv}}, S_2^{\text{dv}})$ which is used to prove the zero-knowledge of scheme where $(\text{dv.crs}, \text{dv.}\mathcal{T}) \leftarrow S_1^{\text{dv}}(1^{\lambda})$ outputs a simulated common reference string and a simulator trapdoor and $\text{dv.}\pi \leftarrow S_2^{\text{dv}}(\text{dv.crs}, \text{dv.}\mathcal{T}, x)$ outputs an accepted proof.

We now construct a zero-knowledge simulator $S = (S_1, S_2)$ below:

* $S_1(1^{\lambda}) \to (\text{crs}, \mathcal{T})$. On inputs $1^{\lambda}$ and outputs $\text{crs} \leftarrow (\text{PCF.pp}, \text{dv.crs}, \text{pk}_V)$ and a trapdoor $\mathcal{T} := (\text{sk}_V, \text{dv.}\mathcal{T})$ such that

- $\text{PCF.setup}(1^{\lambda}) \to \text{PCF.pp}, \text{PCF.Gen}_1(1^{\lambda}, \text{PCF.pp}) \to (\text{pk}_V, \text{sk}_V)$

- $\text{Sim}_{\text{dv}}(1^{\lambda}) \to (\text{dv.crs}, \text{dv.}\mathcal{T})$

* $S_2(\text{crs}, \mathcal{T}, x) \to \pi$. On inputs $(\text{crs}, \mathcal{T}, x)$, $S_2$ randomly chooses a pair $(\text{pk}_P, \text{sk}_P) \in \mathcal{R}_P$, computes $\text{PCF.KeyDer}(1, \text{sk}_V, \text{pk}_P) \to k_1$ and for each invocation $i \in [1, \lambda]$, computes as below:

$$ \text{PCF.Eval}(1^{\lambda}, 1, k_1, x) = (b_i, r_{i,b_i}) $$
$S_2$ uses the simulator $\text{Sim}_\Sigma(x, b_i)$ to get an accepting transcript $(a_i, b_i, z_{i,b_i})$ for each $i \in [1, \lambda]$. $S_2$ now defines the output:

$$ \pi := (\text{pk}_P, \text{dv.}\pi, \{a_i, m_{i,0}, m_{i,1}\}_{i \le \lambda}) $$

where $\text{dv.}\pi = \text{dv.}\text{P}(\text{dv.crs}, \text{pk}_P, \text{sk}_P)$ and for each $i \in [1, \lambda]$, $m_{i,b_i} = z_{i,b_i} \oplus r_{i,b_i}$ otherwise $m_{i,1-b_i}$ is picked randomly.

To complete the proof, we consider a sequence of hybrid experiments:

* **Hyb0.** Namely, at the beginning of the game, the challenger samples $\Pi.\text{Setup}(1^\lambda) \to (\text{crs}, \mathcal{T})$ and gives $\text{crs}$ to the adversary, where $\text{crs} \leftarrow (\text{PCF.pp}, \text{dv.crs}, \text{pk}_V)$ and $\mathcal{T} := (\text{sk}_V, \text{dv.}\mathcal{T})$. When the adversary makes a verification query on $(x, w) \in \mathcal{R}$, the challenger replies with $\Pi.\text{P}(\text{crs}, x, w) = (\text{pk}_P, \text{dv.}\pi, \{a_i, m_{i,0}, m_{i,1}\}_{i \le \lambda})$.

* **Hyb1.** Same as Hyb0, except we replace:

- $(\text{dv.crs}, \text{dv.}\mathcal{T}) \in \Pi.\text{Setup}(1^\lambda)$ by $(\text{dv.crs'}, \text{dv.}\mathcal{T}') \leftarrow S_1^{\text{dv}}(1^\lambda)$

- $\text{dv.}\pi \in \pi$ by $\text{dv.}\pi' \leftarrow S_2^{\text{dv}}(\text{dv.crs'}, \text{dv.}\mathcal{T}', \text{pk}_P)$

This is computational indistinguishable from Hyb0 by the zero-knowledge of dv.

* **Hyb2.** Same as Hyb1, except the challenger simulates $\{a'_i, (m'_{i,0}, m'_{i,1})_{i \le \lambda}\} \in \pi$ by the following way. For each $i \in [1, \lambda]$,

- Compute $k_1 \leftarrow \text{PCF.KeyDer}(1, \text{sk}_V, \text{pk}_P)$, $(b_i, r_{i,b_i}) \leftarrow \text{PCF.Eval}(1^\lambda, 1, k_1, x)$

- Use $\text{Sim}_\Sigma$ for simulating $(a'_i, c'_{i,b_i})$ i.e compute $(a'_i, b_i, c'_{i,b_i}) \leftarrow \text{Sim}_\Sigma(x, b_i)$

- Define $m'_{i,b_i} := c'_{i,b_i} \oplus r_{i,b_i}$ and $m'_{i,1-b_i}$ is picked randomly

This is computationally indistinguishable from Hyb1 by the pseudorandom output of PCF and HVZK of $\Sigma$-protocol. Indeed, the adversary can only compute the value of $(b_i, r_{i,b_i})$ by the PCF.Eval and from the view of adversary $r_{i,1-b_i}$ is pseudorandom then $m_{i,1-b_i}$ also for all $i \in [1, \lambda]$. Moreover, for all $(x, w) \in \mathcal{R}$, with the $\Pi.\text{Setup}(1^\lambda) := (\text{crs'}, \mathcal{T}')$ where $\text{crs'} = \text{PCF.pp}, \text{dv.crs'}, \text{pk}_V)$, $\mathcal{T}' = (\text{sk}_V, \text{dv.}\mathcal{T}')$ and prove $\pi' = (\text{pk}_P, \text{dv.}\pi', \{a'_i, m'_{i,0}, m'_{i,1}\}_{i \le \lambda})$, the adversary always accepts it i.e $\Pi.\text{V}(\text{crs'}, x, \mathcal{T}', \pi') = 1$.

□

## 7.2 Concrete Instantiation

Following our PK-PCF construction (fig. 19), we define the language $\mathcal{L}_p$ for non-reusable DV-NIZK argument as below

$$ \mathcal{L}_p := \left( G^t, H^t(1+N)^{r'}; (h^{r_s}, (h')^{r_s})_{s \in S} \right) $$

where $\text{sk}_p := (h, h', r, t)$ and $r := g_q^{r'} \mod p$.

To build a non-reusable DV-NIZK argument of knowledge, firstly we build a $\Sigma$ protocol for language $\mathcal{L}_p$ then later using the construction of [PsV06] with the trapdoor $\text{dv.}\mathcal{T}$ as the list of $\text{sk}$ which are used in public-key encryption to obtain a (non-reusable) DV-NIZK scheme that satisfies adaptive knowledge soundness, zero-knowledge.

For instantiation of strong PK-PCF, we use our PK-PCF construction (fig. 19) plus the technique [BCE+23] that can convert weak PCF to strong PCF using PRF. We highlight our PK-PCF satisfies the strong security about Supp which we showed directly from the proof security in theorem 7.

## Acknowledgments

Geoffroy Couteau and Dung Bui were supported by the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE39-0001 (project SCENE), and by the France 2030 ANR Project ANR22-PECY-003 SecureCompute. Dung Bui was supported by DIM Math Innovation 2021 (N°IRIS: 21003816) from the Paris Mathematical Sciences Foundation (FSMP) funded by the Paris Ile-deFrance Region. Pierre Meyer was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grants agreement number 852952 (HSS) and 803096 (SPEC). Alain Passelègue and Mahshid Riahinia were supported by the French ANR RAGE project (ANR-20-CE48-0011) and the France 2030 ANR Project (ANR22-PECY-003) SecureCompute.
References

ABP15. Michel Abdalla, Fabrice Benhamouda, and Alain Passelègue. An algebraic framework for pseudorandom functions and applications to related-key security. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 388–409. Springer, Heidelberg, August 2015.

ABR16. Benny Applebaum, Andrej Bogdanov, and Alon Rosen. A dichotomy for local small-bias generators. Journal of Cryptology, 29(3):577–596, July 2016.

ADDG23. Martin R. Albrecht, Alex Davidson, Amit Deo, and Daniel Gardham. Crypto dark matter on the torus: Oblivious PRFs from shallow PRFs and FHE. Cryptology ePrint Archive, Report 2023/232, 2023. https://eprint.iacr.org/2023/232.

AHI11. Benny Applebaum, Danny Harnik, and Yuval Ishai. Semantic security under related-key attacks and applications. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 45–60. Tsinghua University Press, 2011.

AK19. Benny Applebaum and Eliran Kachlon. Sampling graphs without forbidden subgraphs and unbalanced expanders with negligible error. In David Zuckerman, editor, 60th FOCS, pages 171–179. IEEE Computer Society Press, November 2019.

AKPW13. Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with rounding, revisited - new reduction, properties and applications. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 57–74. Springer, Heidelberg, August 2013.

AL16. Benny Applebaum and Shachar Lovett. Algebraic attacks against random local functions and their countermeasures. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 1087–1100. ACM Press, June 2016.

AMN+18. Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa. Constrained PRFs for NC¹ in traditional groups. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 543–574. Springer, Heidelberg, August 2018.

App12. Benny Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. In Howard J. Karloff and Toniann Pitassi, editors, 44th ACM STOC, pages 805–816. ACM Press, May 2012.

App15. Benny Applebaum. The cryptographic hardness of random local functions – survey. Cryptology ePrint Archive, Report 2015/165, 2015. https://eprint.iacr.org/2015/165.

App17. Benny Applebaum. Exponentially-hard gap-CSP and local PRG via local hardcore functions. In Chris Umans, editor, 58th FOCS, pages 836–847. IEEE Computer Society Press, October 2017.

AR16. Benny Applebaum and Pavel Raykov. Fast pseudorandom functions based on expander graphs. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part I, volume 9985 of LNCS, pages 27–56. Springer, Heidelberg, October / November 2016.

BCE+23. Chris Brzuska, Geoffroy Couteau, Christoph Egger, Pihla Karanko, and Pierre Meyer. New random oracle instantiations from extremely lossy functions. Cryptology ePrint Archive, Paper 2023/1145, 2023. https://eprint.iacr.org/2023/1145.

BCG+17. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù. Homomorphic secret sharing: Optimizations and applications. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 2105–2122. ACM Press, October / November 2017.

BCG+19a. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 291–308. ACM Press, November 2019.

BCG+19b. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 489–518. Springer, Heidelberg, August 2019.

BCG+20. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Correlated pseudorandom functions from variable-density LPN. In 61st FOCS, pages 1069–1080. IEEE Computer Society Press, November 2020.

BCG+22. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl. Correlated pseudorandomness from expand-accumulate codes. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 603–633. Springer, Heidelberg, August 2022.

BCGI18. Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 896–912. ACM Press, October 2018.
BCP03. Emmanuel Bresson, Dario Catalano, and David Pointcheval. A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications. In Chi-Sung Laih, editor, *ASIACRYPT 2003*, volume 2894 of LNCS, pages 37–54. Springer, Heidelberg, November / December 2003.

Bea92. Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum, editor, *CRYPTO'91*, volume 576 of LNCS, pages 420–432. Springer, Heidelberg, August 1992.

Bea95. Donald Beaver. Precomputing oblivious transfer. In Don Coppersmith, editor, *CRYPTO'95*, volume 963 of LNCS, pages 97–109. Springer, Heidelberg, August 1995.

Ber06. Daniel J. Bernstein. Curve25519: New Diffie-Hellman speed records. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, *PKC 2006*, volume 3958 of LNCS, pages 207–228. Springer, Heidelberg, April 2006.

BFKL94. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In Douglas R. Stinson, editor, *CRYPTO'93*, volume 773 of LNCS, pages 278–291. Springer, Heidelberg, August 1994.

BGMM20. James Bartusek, Sanjam Garg, Daniel Masny, and Pratyay Mukherjee. Reusable two-round MPC from DDH. In Rafael Pass and Krzysztof Pietrzak, editors, *TCC 2020, Part II*, volume 12551 of LNCS, pages 320–348. Springer, Heidelberg, November 2020.

BIP<sup>+</sup>18. Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. Exploring crypto dark matter: New simple PRF candidates and their applications. In Amos Beimel and Stefan Dziembowski, editors, *TCC 2018, Part II*, volume 11240 of LNCS, pages 699–729. Springer, Heidelberg, November 2018.

Blu86. Manuel Blum. How to prove a theorem so no one else can claim it, August 1986. Invited 45 minute address to the International Congress of Mathematicians, 1986. To appear in the Proceedings of ICM 86.

BM90. Mihir Bellare and Silvio Micali. Non-interactive oblivious transfer and applications. In Gilles Brassard, editor, *CRYPTO'89*, volume 435 of LNCS, pages 547–557. Springer, Heidelberg, August 1990.

BPR12. Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In David Pointcheval and Thomas Johansson, editors, *EUROCRYPT 2012*, volume 7237 of LNCS, pages 719–737. Springer, Heidelberg, April 2012.

BQ09. Andrej Bogdanov and Youming Qiao. On the security of goldreich's one-way function. In *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques*, pages 392–405. Springer, 2009.

BV15. Zvika Brakerski and Vinod Vaikuntanathan. Constrained key-homomorphic PRFs from standard lattice assumptions - or: How to secretly embed a circuit in your PRF. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, *TCC 2015, Part II*, volume 9015 of LNCS, pages 1–30. Springer, Heidelberg, March 2015.

CC18. Pyrros Chaidos and Geoffroy Couteau. Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge. In Jesper Buus Nielsen and Vincent Rijmen, editors, *EUROCRYPT 2018, Part III*, volume 10822 of LNCS, pages 193–221. Springer, Heidelberg, April / May 2018.

CCKK21. Jung Hee Cheon, Wonhee Cho, Jeong Han Kim, and Jiseung Kim. Adventures in crypto dark matter: Attacks and fixes for weak pseudorandom functions. In Juan Garay, editor, *PKC 2021, Part II*, volume 12711 of LNCS, pages 739–760. Springer, Heidelberg, May 2021.

CDM<sup>+</sup>18. Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, and Yann Rotella. On the concrete security of Goldreich's pseudorandom generator. In Thomas Peyrin and Steven Galbraith, editors, *ASIACRYPT 2018, Part II*, volume 11273 of LNCS, pages 96–124. Springer, Heidelberg, December 2018.

CDS94. Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Yvo Desmedt, editor, *CRYPTO'94*, volume 839 of LNCS, pages 174–187. Springer, Heidelberg, August 1994.

CEMT14. James Cook, Omid Etesami, Rachel Miller, and Luca Trevisan. On the one-way function candidate proposed by goldreich. *ACM Transactions on Computation Theory (TOCT)*, 6(3):14, 2014.

CH19. Geoffroy Couteau and Dennis Hofheinz. Designated-verifier pseudorandom generators, and their applications. In Yuval Ishai and Vincent Rijmen, editors, *EUROCRYPT 2019, Part II*, volume 11477 of LNCS, pages 562–592. Springer, Heidelberg, May 2019.

CH20. Geoffroy Couteau and Dominik Hartmann. Shorter non-interactive zero-knowledge arguments and ZAPs for algebraic languages. In Daniele Micciancio and Thomas Ristenpart, editors, *CRYPTO 2020, Part III*, volume 12172 of LNCS, pages 768–798. Springer, Heidelberg, August 2020.

CHH<sup>+</sup>07. Ronald Cramer, Goichiro Hanaoka, Dennis Hofheinz, Hideki Imai, Eike Kiltz, Rafael Pass, abhi shelat, and Vinod Vaikuntanathan. Bounded CCA2-secure encryption. In Kaoru Kurosawa,
editor, *ASIACRYPT 2007*, volume 4833 of LNCS, pages 502–518. Springer, Heidelberg, December 2007.

CJJQ23. Geoffroy Couteau, Abhishek Jain, Zhengzhong Jin, and Willy Quach. A note on non-interactive zero-knowledge from cdh. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023*, pages 731-764, Cham, 2023. Springer Nature Switzerland.

CKLR21. Geoffroy Couteau, Michael Klooß, Huang Lin, and Michael Reichle. Efficient range proofs with transparent setup from bounded integer commitments. In Anne Canteaut and François-Xavier Standaert, editors, *EUROCRYPT 2021, Part III*, volume 12698 of LNCS, pages 247–277. Springer, Heidelberg, October 2021.

CL15. Craig Costello and Patrick Longa. FourQ: Four-dimensional decompositions on a Q-curve over the Mersenne prime. In Tetsu Iwata and Jung Hee Cheon, editors, *ASIACRYPT 2015, Part I*, volume 9452 of LNCS, pages 214-235. Springer, Heidelberg, November / December 2015.

CM01. Mary Cryan and Peter Bro Miltersen. On pseudorandom generators in nc 0. In *International Symposium on Mathematical Foundations of Computer Science*, pages 272–284. Springer, 2001.

CMPR23. Geoffroy Couteau, Pierre Meyer, Alain Passelègue, and Mahshid Riahinia. Constrained pseudorandom functions from homomorphic secret sharing. In Carmit Hazay and Martijn Stam, editors, *EUROCRYPT 2023, Part III*, volume 14006 of LNCS, pages 194–224. Springer, Heidelberg, April 2023.

CNs07. Jan Camenisch, Gregory Neven, and abhi shelat. Simulatable adaptive oblivious transfer. In Moni Naor, editor, *EUROCRYPT 2007*, volume 4515 of LNCS, pages 573–590. Springer, Heidelberg, May 2007.

Cré88. Claude Crépeau. Equivalence between two flavours of oblivious transfers. In Carl Pomerance, editor, *CRYPTO'87*, volume 293 of LNCS, pages 350–354. Springer, Heidelberg, August 1988.

CRR21. Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In Tal Malkin and Chris Peikert, editors, *CRYPTO 2021, Part III*, volume 12827 of LNCS, pages 502–534, Virtual Event, August 2021. Springer, Heidelberg.

CS02. Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In Lars R. Knudsen, editor, *EUROCRYPT 2002*, volume 2332 of LNCS, pages 45–64. Springer, Heidelberg, April / May 2002.

DGH<sup>+21</sup>. Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmetric cryptography from alternating moduli: Candidates, protocols, and applications. In Tal Malkin and Chris Peikert, editors, *CRYPTO 2021, Part IV*, volume 12828 of LNCS, pages 517–547, Virtual Event, August 2021. Springer, Heidelberg.

DGS03. Ivan Damgård, Jens Groth, and Gorm Salomonsen. *The Theory and Implementation of an Electronic Voting System*, pages 77–99. Springer US, Boston, MA, 2003.

DILO22. Samuel Dittmer, Yuval Ishai, Steve Lu, and Rafail Ostrovsky. Authenticated garbling from simple correlations. In Yevgeniy Dodis and Thomas Shrimpton, editors, *CRYPTO 2022, Part IV*, volume 13510 of LNCS, pages 57–87. Springer, Heidelberg, August 2022.

DMMS21. Sébastien Duval, Pierrick Méaux, Charles Momin, and François-Xavier Standaert. Exploring crypto-physical dark matter and learning with physical rounding. *IACR TCHES*, 2021(1):373–401, 2021. https://tches.iacr.org/index.php/TCHES/article/view/8738.

DMR23. Aurélien Dupin, Pierrick Méaux, and Mélissa Rossi. On the algebraic immunity—resiliency trade-off, implications for goldreich’s pseudorandom generator. *Designs, Codes and Cryptography*, pages 1–45, 2023.

DNNR17. Ivan Damgård, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. The TinyTable protocol for 2-party secure computation, or: Gate-scrambling revisited. In Jonathan Katz and Hovav Shacham, editors, *CRYPTO 2017, Part I*, volume 10401 of LNCS, pages 167–187. Springer, Heidelberg, August 2017.

DPSZ12. Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, *CRYPTO 2012*, volume 7417 of LNCS, pages 643–662. Springer, Heidelberg, August 2012.

FKOS15. Tore Kasper Frederiksen, Marcel Keller, Emmanuela Orsini, and Peter Scholl. A unified approach to MPC with preprocessing using OT. In Tetsu Iwata and Jung Hee Cheon, editors, *ASIACRYPT 2015, Part I*, volume 9452 of LNCS, pages 711–735. Springer, Heidelberg, November / December 2015.

GGM84a. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions (extended abstract). In *25th FOCS*, pages 464–479. IEEE Computer Society Press, October 1984.

GGM84b. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. On the cryptographic applications of random functions. In G. R. Blakley and David Chaum, editors, *CRYPTO'84*, volume 196 of LNCS, pages 276–288. Springer, Heidelberg, August 1984.
GMW87. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, *19th ACM STOC*, pages 218–229. ACM Press, May 1987.

Gol00. Oded Goldreich. Candidate one-way functions based on expander graphs. Cryptology ePrint Archive, Report 2000/063, 2000. https://eprint.iacr.org/2000/063.

GS08. Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear groups. In Nigel P. Smart, editor, *EUROCRYPT 2008*, volume 4965 of LNCS, pages 415–432. Springer, Heidelberg, April 2008.

HSS20. Carmit Hazay, Peter Scholl, and Eduardo Soria-Vazquez. Low cost constant round MPC combining BMR and oblivious transfer. *Journal of Cryptology*, 33(4):1732–1786, October 2020.

IKNP03. Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Dan Boneh, editor, *CRYPTO 2003*, volume 2729 of LNCS, pages 145–161. Springer, Heidelberg, August 2003.

JJ21. Abhishek Jain and Zhengzhong Jin. Non-interactive zero knowledge from sub-exponential DDH. In Anne Canteaut and François-Xavier Standaert, editors, *EUROCRYPT 2021, Part I*, volume 12696 of LNCS, pages 3–32. Springer, Heidelberg, October 2021.

JLS21. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Samir Khuller and Virginia Vassilevska Williams, editors, *53rd ACM STOC*, pages 60–73. ACM Press, June 2021.

JMN23. Thomas Johansson, Willi Meier, and Vu Nguyen. Differential cryptanalysis of mod-2/mod-3 constructions of binary weak prfs. In *2023 IEEE International Symposium on Information Theory (ISIT)*, pages 477–482. IEEE, 2023.

KKRT16. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient batched oblivious PRF with applications to private set intersection. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, *ACM CCS 2016*, pages 818–829. ACM Press, October 2016.

KNYY19. Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa. Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions. In Yuval Ishai and Vincent Rijmen, editors, *EUROCRYPT 2019, Part II*, volume 11477 of LNCS, pages 622–651. Springer, Heidelberg, May 2019.

KW15. Eike Kiltz and Hoeteck Wee. Quasi-adaptive NIZK for linear subspaces revisited. In Elisabeth Oswald and Marc Fischlin, editors, *EUROCRYPT 2015, Part II*, volume 9057 of LNCS, pages 101–128. Springer, Heidelberg, April 2015.

LPSY15. Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai. Efficient constant round multi-party computation combining BMR and SPDZ. In Rosario Gennaro and Matthew J. B. Robshaw, editors, *CRYPTO 2015, Part II*, volume 9216 of LNCS, pages 319–338. Springer, Heidelberg, August 2015.

LV17. Alex Lombardi and Vinod Vaikuntanathan. Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation. In Yael Kalai and Leonid Reyzin, editors, *TCC 2017, Part I*, volume 10677 of LNCS, pages 119–137. Springer, Heidelberg, November 2017.

Méa. P Méaux. On the fast algebraic immunity of threshold functions. crypt. commun. 13 (5), 741–762 (2021).

Méa22. Pierrick Méaux. On the algebraic immunity of direct sum constructions. *Discrete Applied Mathematics*, 320:223–234, 2022.

MST03. Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On e-biased generators in NC0. In *44th FOCS*, pages 136–145. IEEE Computer Society Press, October 2003.

Nec94. V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm. *Mathematical Notes*, 55(2):165–172, 1994.

NNOB12. Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. A new approach to practical active-secure two-party computation. In Reihaneh Safavi-Naini and Ran Canetti, editors, *CRYPTO 2012*, volume 7417 of LNCS, pages 681–700. Springer, Heidelberg, August 2012.

NR95. Moni Naor and Omer Reingold. Synthesizers and their application to the parallel construction of pseudo-random functions. In *36th FOCS*, pages 170–181. IEEE Computer Society Press, October 1995.

NR97. Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. In *38th FOCS*, pages 458–467. IEEE Computer Society Press, October 1997.

OST19. Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell. Expander-based cryptography meets natural proofs. In Avrim Blum, editor, *ITCS 2019*, volume 124, pages 18:1–18:14. LIPICs, January 2019.

OSY21. Claudio Orlandi, Peter Scholl, and Sophia Yakoubov. The rise of paillier: Homomorphic secret sharing and public-key silent OT. In Anne Canteaut and François-Xavier Standaert, editors, *EUROCRYPT 2021, Part I*, volume 12696 of LNCS, pages 678–708. Springer, Heidelberg, October 2021.
OW14. Ryan ODonnell and David Witmer. Goldreich's prg: evidence for near-optimal polynomial stretch. In *Computational Complexity (CCC), 2014 IEEE 29th Conference on*, pages 1-12. IEEE, 2014.

Pai99. Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques Stern, editor, *EUROCRYPT'99*, volume 1592 of LNCS, pages 223-238. Springer, Heidelberg, May 1999.

Ped92. Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Joan Feigenbaum, editor, *CRYPTO'91*, volume 576 of LNCS, pages 129-140. Springer, Heidelberg, August 1992.

PsV06. Rafael Pass, abhi shelat, and Vinod Vaikuntanathan. Construction of a non-malleable encryption scheme from any semantically secure one. In Cynthia Dwork, editor, *CRYPTO 2006*, volume 4117 of LNCS, pages 271-289. Springer, Heidelberg, August 2006.

QRW19. Willy Quach, Ron D. Rothblum, and Daniel Wichs. Reusable designated-verifier NIZKs for all NP from CDH. In Yuval Ishai and Vincent Rijmen, editors, *EUROCRYPT 2019, Part II*, volume 11477 of LNCS, pages 593-621. Springer, Heidelberg, May 2019.

RRT23. Srinivasan Raghuraman, Peter Rindal, and Titouan Tanguy. Expand-convolute codes for pseudorandom correlation generators from lpn. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023*, pages 602-632, Cham, 2023. Springer Nature Switzerland.

Sho97. Victor Shoup. Lower bounds for discrete logarithms and related problems. In Walter Fumy, editor, *EUROCRYPT'97*, volume 1233 of LNCS, pages 256-266. Springer, Heidelberg, May 1997.

Üna23a. Akin Ünal. New baselines for local pseudorandom number generators by field extensions. *Cryptology ePrint Archive*, 2023.

Üna23b. Akin Ünal. Worst-case subexponential attacks on PRGs of constant degree or constant locality. In Carmit Hazay and Martijn Stam, editors, *EUROCRYPT 2023, Part I*, volume 14004 of LNCS, pages 25-54. Springer, Heidelberg, April 2023.

WRK17. Xiao Wang, Samuel Ranellucci, and Jonathan Katz. Global-scale secure multiparty computation. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, *ACM CCS 2017*, pages 39-56. ACM Press, October / November 2017.

YGJL21. Jing Yang, Qian Guo, Thomas Johansson, and Michael Lentmaier. Revisiting the concrete security of goldreich's pseudorandom generator. *IEEE Transactions on Information Theory*, 68(2):1329-1354, 2021.