Complexity: $O(|\mathcal{L}|(n-k-\ell)(k+\ell))$.

**Proposition 27 (Stern Algorithm).** The complexity of an iteration of the Stern algorithm is given by

$$C_S(n, k, q, p, l) = O(|\mathcal{L}|(n - k - \ell)(k + \ell) + \max(|\mathcal{L}_1|, |\mathcal{L}|) + |\mathcal{L}_1|)$$

with

$$|\mathcal{L}_1| = \binom{(k+\ell)/2}{p/2} (q-1)^{p/2}$$

$$|\mathcal{L}| = \binom{(k+\ell)/2}{p/2}^2 (q-1)^p q^{-l}$$

and the probability of finding a solution is

$$\mathcal{P}_S(n, k, q, t, p, l) = \frac{\binom{k+\ell}{p} \binom{n-k-\ell}{t-p}}{\binom{n}{t}} \cdot \frac{\binom{(k+\ell)/2}{p/2}^2}{\binom{k+\ell}{p}} = \frac{\binom{(k+\ell)/2}{p/2}^2 \binom{n-k-\ell}{t-p}}{\binom{n}{t}}.$$

*Remark 28.* The probability of success is obtained as the probability of having an error vector that has exactly $p$ errors on the chosen information set (first fraction) multiplied by the probability that the error on the information set is equally distributed into the two halves of the corresponding vector $e_I$.

*Remark 29.* The complexity given at Step 1 and 2 is voluntarily given without any polynomial co-efficient, for conservative purposes. In fact, for each element of the lists, we have to perform the computation of $\tilde{s}_I - \mathbf{H}_2\mathbf{e}_0$. This costs naively $\ell(\ell + k)$ per element in the list (for a total cost of $O(\ell(\ell + k)|\mathcal{L}_1|)$. Second, we have to check for equality among vectors of size $l$, and this costs $l$ for each element in the list (for a total cost of $O(\max(|\mathcal{L}_1|, |\mathcal{L}|) \cdot \ell)$. Nevertheless, some optimization exists for these Steps (see [Pet10]). Therefore, we chose to stick with $O(|\mathcal{L}_1|)$ and $O(\max(|\mathcal{L}_1|, |\mathcal{L}|))$, as conservative lower bounds.

**Corollary 30 (Prange and Lee Brickell complexities).** The Prange [Pra62] algorithm is a very particular case of the Stern algorithm with $p = 0, \ell = 0$ and no subroutine. In the case of Prange, we have

$$C(n, k, q, t) = 0$$

$$\mathcal{P}_S(n, k, q, t) = \frac{\binom{n-k}{t}}{\binom{n}{t}}.$$

The same goes for the Lee-Brickell algorithm [LB88], by taking $\ell = 0$ with only $p$ to optimize, and no subroutine. In the case of Lee-Brickell, we therefore have:

$$C(n, k, q, t) = 0$$

$$\mathcal{P}_S(n, k, q, t) = \frac{\binom{k}{p} \binom{n-k}{t-p}}{\binom{n}{t}}.$$

## C.2 MMT

The MMT algorithm [MMT11] of May et al. introduced the representation technique. They remark that we can split a given vector $\mathbf{e}$ of weight $p$ into $R$ different sums of two vectors $\mathbf{e}_1$ and $\mathbf{e}_2$, of the same size but weight $p/2$, and disjoint support.

$$\mathbf{e} = \mathbf{e}_1 + \mathbf{e}_2, \quad w_H(\mathbf{e}_1) = p/2, \quad w_H(\mathbf{e}_2) = p/2.$$

Remark that $\mathbf{H}_2\mathbf{e} = \tilde{s}_I$ implies $\mathbf{H}_2\mathbf{e}_1 = \tilde{s}_I - \mathbf{H}_2\mathbf{e}_2$. Therefore they create $\mathcal{L}_{1,0} \subset \{\mathbf{H}_2\mathbf{e}_1, w_H(\mathbf{e}_1) = p/2\}$ and $\mathcal{L}_{1,1} \subset \{\tilde{s}_I - \mathbf{H}_2\mathbf{e}_2, w_H(\mathbf{e}_2) = p/2\}$ and look for possible collisions. $R$ is called the number of representations, and we have that

$$R = \binom{p}{p/2}.$$

Let $0 \le r = \log_q(R) \le l$. The subroutine is as follows:
1. For $0 \le i \le 1$, construct the following lists

$$ 
\begin{aligned}
\mathcal{L}_{i,0} &= \left\{ (\mathbf{e}_0 = \begin{bmatrix} \mathbf{e}' \\ \mathbf{0} \end{bmatrix}, \mathbf{H}_2 \mathbf{e}_0), \mathbf{e}' \in \mathbb{F}_q^{\frac{k+l}{2}}, w_H(\mathbf{e}') = \frac{p}{4} \right\}, \\
\mathcal{L}_{i,1} &= \left\{ (\mathbf{e}'_0 = \begin{bmatrix} \mathbf{0} \\ \mathbf{e}' \end{bmatrix}, \tilde{\mathbf{s}}_I - \mathbf{H}_2 \mathbf{e}'_0), \mathbf{e}' \in \mathbb{F}_q^{\frac{k+l}{2}}, w_H(\mathbf{e}') = \frac{p}{4} \right\}.
\end{aligned}
$$

The size of each list is $|\mathcal{L}_{0,0}| = |\mathcal{L}_{0,1}| = |\mathcal{L}_{1,0}| = |\mathcal{L}_{1,1}| = \binom{(k+l)/2}{p/4} (q-1)^{p/4}$.

Complexity: $O(|\mathcal{L}_{0,0}|)$.

2. For $0 \le i \le 1$, and given a fix set of $r$ entries, search for all pairs $((\mathbf{e}_0, \mathbf{H}_2\mathbf{e}_0), (\mathbf{e}'_0, \tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0)) \in \mathcal{L}_{i,0} \times \mathcal{L}_{i,1}$ such that $\mathbf{H}_2 \cdot \mathbf{e}_0 = \tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0$ on the $r$ entries. Construct the list

$$ \mathcal{L}_{i,2} = \{ \mathbf{e}_0 + \mathbf{e}'_0, (\mathbf{e}_0, \mathbf{H}_2\mathbf{e}_0), (\mathbf{e}'_0, \tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0) \} \in \mathcal{L}_{i,0} \times \mathcal{L}_{i,1}, \mathbf{H}_2\mathbf{e}_0 = \tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0. $$

We have that

$$ \mathcal{L}_{i,2} \subset \{\mathbf{e}_2 \in \mathbb{F}_q^{k+l}, w_H(\mathbf{e}_2) = p/2, \mathbf{H}_2\mathbf{e}_2 = \tilde{\mathbf{s}}_I\}. $$

The size of the lists resulting from the merge is $|\mathcal{L}_{0,2}| = |\mathcal{L}_{1,2}| = |\mathcal{L}_{0,0}|^2/q^r$.

Complexity: $O(\max(|\mathcal{L}_{0,0}|, |\mathcal{L}_{0,2}|))$.

3. Merge the two previous lists again, to obtain $\mathcal{L}$ which contains vectors of size $k+l$, weight $p$, and with the appropriate fixed value for the remaining $l-r$ coordinates of their syndromes. The size of the resulting list is $|\mathcal{L}| = |\mathcal{L}_{0,0}|^4/q^{l+r}$.

Complexity: $O(\max(|\mathcal{L}_{0,2}|, |\mathcal{L}|))$.

4. We perform Step 4 of the general ISD framework to find $\mathbf{e}_1$ of weight $t-p$.

Complexity: $O(|\mathcal{L}|(n-k-l)(k+l))$.

**Proposition 31 (General MMT algorithm).** The complexity of an iteration of the MMT algorithm is given by

$$ C_S(n, k, q, p, l) = O(|\mathcal{L}|(n - k - l)(k + l) + \max(|\mathcal{L}_{0,0}|, |\mathcal{L}_{0,2}|, |\mathcal{L}|) + \mathcal{L}_{0,0}) $$

with

$$ 
\begin{aligned}
|\mathcal{L}_{0,0}| &= \binom{(k+l)/2}{p/4} (q-1)^{p/4} & |\mathcal{L}_{0,2}| &= \binom{(k+l)/2}{p/4}^2 (q-1)^{p/2} q^{-r} \\
|\mathcal{L}| &= \binom{(k+l)/2}{p/4}^4 (q-1)^p q^{-l-r} & R &= \binom{p}{p/2} \\
r &= \log_q(R)
\end{aligned}
$$

and the probability of finding a solution is

$$ \mathcal{P}_S(n, k, q, t, p, l) = \frac{\binom{k+l}{p} \binom{n-k-l}{t-p}}{\binom{n}{t}} \cdot \frac{\binom{(k+l)/2}{p/4}^4}{\binom{k+l}{p/2}^2}. $$

*Remark 32.* The probability of success is obtained as the probability of having an error vector that has exactly $p$ errors on the chosen Information Set (first fraction) multiplied by the probability that $\mathbf{e}_1$ has $p/2$ errors equally distributed into its two halves, multiplied again by the probability that $\mathbf{e}_1$ has $p/2$ errors equally distributed into its two halves.
<figure><img src="image_6.png" /><figcaption>Fig. 19: BJMM representations</figcaption></figure>

### C.3 BJMM

The algorithm introduced by Becker et al. [BJMM12], proposes an improvement of the MMT algorithm, by increasing the number of representations one can get. Their idea follows the approach of MMT, except that an additional parameter $\epsilon$ is introduced. Let $p_1 = p/2 + \epsilon$. Their idea is still to write a vector $\mathbf{e} \in \mathbb{F}_q^{k+\ell}$, of weight $p$ as a sum.

$$ \mathbf{e} = \mathbf{e}_1 + \mathbf{e}_2 $$

but now we want to allow their support to coincide on a proportion $\epsilon$, and we ask that $w_H(\mathbf{e}_1) = w_H(\mathbf{e}_2) = p_1$.

The support of $\mathbf{e}_1$ and $\mathbf{e}_2$ can coincide in two different ways: either the sum of the entries vanishes, or they do not vanish. For this reason, we split $\epsilon = \epsilon_1 + \epsilon_2$. For $\mathbf{e}$ to have a support of size $p$, the support of $\mathbf{e}_1$ and $\mathbf{e}_2$ should coincide on the same $2\epsilon_1 + \epsilon_2$ entries, and be distinct on the other $p/2 - \epsilon_1$ entries, as represented in Figure 19. The number of representations is therefore given by

$$ R = \sum_{\epsilon_1+\epsilon_2=\epsilon} \binom{p}{p/2-\epsilon_1} \binom{p/2+\epsilon_1}{2\epsilon_1} \binom{k+\ell-p}{\epsilon_2} (q-1)^{2\epsilon_1+\epsilon_2}. $$

Let $r = \log_q(R)$. The subroutine is as follows:

1. For $0 \le i \le 1$ construct the following lists

$$ \mathcal{L}_{i,0} = \left\{ (\mathbf{e}_0 = \begin{bmatrix} \mathbf{e}' \\ \mathbf{0} \end{bmatrix}, \mathbf{H}_2 \mathbf{e}_0), \mathbf{e}' \in \mathbb{F}_q^{\frac{k+\ell}{2}}, w_H(\mathbf{e}') = \frac{p_1}{2} \right\}, $$

$$ \mathcal{L}_{i,1} = \left\{ (\mathbf{e}'_0 = \begin{bmatrix} \mathbf{0} \\ \mathbf{e}' \end{bmatrix}, \tilde{\mathbf{s}}_{\mathcal{I}} - \mathbf{H}_2 \mathbf{e}'_0), \mathbf{e}' \in \mathbb{F}_q^{\frac{k+\ell}{2}}, w_H(\mathbf{e}') = \frac{p_1}{2} \right\}. $$

The size of each list is $|\mathcal{L}_{0,0}| = |\mathcal{L}_{0,1}| = |\mathcal{L}_{1,0}| = |\mathcal{L}_{1,1}| = \binom{(k+\ell)/2}{p_1/2} (q-1)^{p_1/2}$.

Complexity: $O(|\mathcal{L}_{0,0}|)$.

2. For $0 \le i \le 1$, and given a fix set of $r$ entries, search for all pairs $(\mathbf{e}_0, \mathbf{e}'_0) \in \mathcal{L}_{i,0} \times \mathcal{L}_{i,1}$ such that $\mathbf{H}_2 \cdot \mathbf{e}_0 = \tilde{\mathbf{s}}_{\mathcal{I}} - \mathbf{H}_2 \mathbf{e}'_0$ on the $r$ entries. Construct the list

$$ \mathcal{L}_{i,2} = \{ \mathbf{e}_0 + \mathbf{e}'_0, (\mathbf{e}_0, \mathbf{H}_2 \mathbf{e}_0), (\mathbf{e}'_0, \tilde{\mathbf{s}}_{\mathcal{I}} - \mathbf{H}_2 \mathbf{e}'_0) \} \in \mathcal{L}_{i,0} \times \mathcal{L}_{i,1}, \mathbf{H}_2 \cdot \mathbf{e}_0 = \tilde{\mathbf{s}}_{\mathcal{I}} - \mathbf{H}_2 \mathbf{e}'_0. $$

We have that

$$ \mathcal{L}_{i,2} \subset \{\mathbf{e}_2 \in \mathbb{F}_q^{k+\ell}, w_H(\mathbf{e}_2) = p_1/2, \mathbf{H}_2 \mathbf{e}_2 = \tilde{\mathbf{s}}_{\mathcal{I}}\} $$

The size of the lists resulting from the merge is $|\mathcal{L}_{0,2}| = |\mathcal{L}_{1,2}| = |\mathcal{L}_{0,0}|^2/q^r$.

Complexity: $O(\max(|\mathcal{L}_{0,0}|, |\mathcal{L}_{0,2}|))$.

3. Merge the two previous lists again, to obtain $\mathcal{L}$ which contains vectors of size $k+\ell$, weight $p$, and with the appropriate fixed value for the remaining $\ell - r$ coordinates of their syndromes. The size of the resulting list is $|\mathcal{L}| = |\mathcal{L}_{0,0}|^4/q^{l+r}$.
Complexity: $O(\max(|\mathcal{L}_{0,2}|, |\mathcal{L}|))$.

4. We perform Step 4 of the general ISD framework to find $\mathbf{e}_1$ of weight $t - p$.

Complexity: $O(|\mathcal{L}|(n - k - \ell)(k + \ell))$.

**Proposition 33 (BJMM algorithm).** The complexity of an iteration of the BJMM algorithm is given by

$$C_S(n, k, q, p, l, \varepsilon) = O(|\mathcal{L}|(n - k - \ell)(k + \ell) + \max(|\mathcal{L}_{0,0}|, |\mathcal{L}_{0,2}|, |\mathcal{L}|) + \mathcal{L}_{0,0})$$

with

$$|\mathcal{L}_{0,0}| = \binom{(k + \ell)/2}{p_1/2} (q - 1)^{p_1/2} \qquad |\mathcal{L}_{0,2}| = \binom{(k + \ell)/2}{p_1/2}^2 (q - 1)^{p_1} q^{-r} \\ |\mathcal{L}| = \binom{(k + \ell)/2}{p_1/2}^4 (q - 1)^{2p_1} q^{-\ell - r} \qquad p_1 = p/2 + \varepsilon$$

and

$$R = \sum_{\varepsilon_1 + \varepsilon_2 = \varepsilon} \binom{p}{p/2 - \varepsilon_1} \binom{p/2 + \varepsilon_1}{2\varepsilon_1} \binom{k + \ell - p}{\varepsilon_2} (q - 1)^{2\varepsilon_1 + \varepsilon_2} \\ r = \log(R)$$

and the probability of finding a solution is

$$P_S(n, k, q, t, p, l, \varepsilon) = \frac{\binom{k+l}{p} \binom{n-k-l}{t-p}}{\binom{n}{t}} \cdot \frac{\binom{(k+l)/2}{p_1/2}^4}{\binom{k+l}{p_1}^2}.$$

*Remark 34.* The probability of success is obtained as the probability of having an error vector that has exactly $p$ errors on the chosen Information Set (first fraction) multiplied by the probability that $\mathbf{e}_1$ has $p_1$ errors equally distributed into its two halves, multiplied again by the probability that $\mathbf{e}_2$ has $p_1$ errors equally distributed into its two halves.

*Remark 35.* We want to stress the fact that in the case of the MMT and BJMM-like attacks, our estimations are quite conservative, as we do not take into account the costs implied by the memory calls. In our range of parameters, they should not be discarded in practice. Indeed, the memory size is about the size of the biggest lists computed, therefore

$$M(n, k, q, p, l) \approx \max(|\mathcal{L}_{0,2}|, |\mathcal{L}_{1,1}|, |\mathcal{L}|),$$

which can be over $2^{50}$, and entails an overhead in the computation time. This is often neglected in the literature.

## D Faster seed expansion from hashing (application to silent OT)

In this section, we describe how to combine hashing techniques with our PCG construction to reduce the number of DPFs required to share the noise vector. This has the advantage of making seed expansion faster with the number of PRGs operations being $O(2|\mathbb{G}|)$, but comes at the cost of requiring a trusted setup. As such, this optimization is primarily suited to silent-OT applications where a trusted setup process is assumed.
## D.1 Faster seed expansion

We propose a better fQA-SD<sub>OLE</sub> scheme in terms of seed expansion efficiency that is based on the DPF scheme and hashing techniques. First, we take advantage of Cuckoo hashing and simple hashing [KKRT16, PSWW18, BC23, RS21] to distribute the noise positions. After that, we use a DPF scheme for each bin to obtain the shares of value in each noise position by using a DPF for each bin. In general, using our Cuckoo hashing trick, we obtain a faster seed expansion but need to assume a trusted dealer because the Doerner-shelat protocol does not apply out-of-the-box. However, our fQA-SD<sub>OLE</sub> construction has an advantage compared to the QA-SD<sub>OLE</sub> protocol, i.e., the computation cost of Expand is smaller and independent of $t$ (number of noisy coordinates). Concretely, the number of PRG operations is reduced from $O(t|G|)$ to $O(2|G|)$. Just as with the QA-SD<sub>OLE</sub> construction, our fQA-SD<sub>OLE</sub> construction can be used to obtain OLE correlation over any finite field $\mathbb{F}$ (except for $\mathbb{F}_2$), however, to be consistent with the concept of our main contribution, we cast our fQA-SD<sub>OLE</sub> over $\mathbb{F}_3$ for concrete efficiency.

**D.1.1 Hashing technique.** We fix $K$ random hash functions $h_1, \dots, h_K$, where $h_i: G \to [m]$ and $m = O(n)$. Using these $K$ hash functions, the formal definition and parameter choices of Cuckoo hashing and simple hashing schemes (similarly as in PSI works [KD08, KKRT16, BC23, RS21]) are as follows:

1. **Cuckoo hashing schemes** with parameters $(G, K, m, n)$ enable mapping a set of $n$ item into a table $T$ of size $m$ using $K$ hash functions $(h_i)_{i \le K}$ such that each bin in $T$ has at most one item. The algorithm takes an item $x \in G$ and inserts it into the bin $T[h_1(x)]$, if this bin is occupied then evicts the item in this bin and relocates it using $h_2$, this process continues until all items are inserted in table $T$. The hashing algorithm can fail if a cycle eviction is found or a threshold number of relocations has been performed, this failure can be avoided with high probability by choosing appropriate parameters $(K, m, n)$ or using a stash to store the last item in each cycle eviction if it exists [PSWW18]. Here, we choose the parameters such that $K = 2, m = 2n$ [BC23, RS21], and do not use a stash. Looking ahead, this will imply that insertion will have a noticeable failure probability; however, we will show that in this case, the trusted dealer can simply re-sample the noise vector until insertion succeeds. This induces a small bias on the noise, but a straightforward reduction shows that it does not harm the security of the underlying syndrome decoding assumption (if the insertion fails with probability $\alpha$, then the reduction loses a factor $\alpha$ in the advantage). For $K = 2, m = 2n$, the failure probability of Cuckoo hashing is known to be $\sqrt{2/3} + o(1)$ [KD08], which translates to a small constant security loss. We note in passing that the same observation applies to the use of Cuckoo hashing in a previous work [SGRR19] and allows them to reduce the computational overhead of their LPN-based construction from 3 to 2 compared to their regular LPN-based construction.

2. **Simple hashing** with parameters $(G, K, m)$ uses $K$ hash functions $(h_i)_{i \le K}$ to insert each item $x \in G$ to the bin $B[h_i(x)]$ of a table $B$ of size $m$. With very high probability, for $m = O(n \log n)$ bins, the maximum possible items per bin is $O(\log m)$. In particular, by the randomness of hash functions, with high probability, the maximum number of items per bin (denoted as $\max\_load$) is bounded by $\frac{3 \ln m}{\ln \ln m}$. That is, $\Pr[\max\_load \ge \frac{3 \ln m}{\ln \ln m}] \le \frac{1}{m}$. To estimate our concrete efficiency, we highlight the total number of items in all bins always is $K \cdot |G|$ since each item in $G$ is mapped to $K$ bins using different $K$ hash functions.

**D.1.2 OLE from hashing techniques.** In our construction we have $G = \prod_{i=1}^n \mathbb{Z}/(q-1)\mathbb{Z}$. Because we are working over $\mathbb{F}_4$, $|G| = 3^n$. We later work on "balls and bins" where each bin has a different number of balls and is associated with a DPF to distributed shares of a point vector then we make use of notation $DPF_n$ for DPF scheme with arbitrary domain $[n]$.

We reuse all notations defined in Section 2.5, the intuition of the construction is the same as in Section 2.5 except that we provide a more efficient way to distribute the position of noise coordinates before using the DPF to give each party the shares of point vector. Briefly, to construct an OLE correlation over the ring $\mathcal{R}$, we want to give the parties shares of $x_0 \cdot x_1$. Note that $x_0 \cdot x_1$ is a degree-2 function in $(e_0, e_1)$; therefore, it suffices to share $e_0 \otimes e_1$. Since $e_0, e_0 \in \mathcal{R}_t^c$ both are sparse vectors of weight $t$ over $\mathcal{R}_t$, where the product of two sparse vectors is a sparse vector with sparsity $t^2$. So the goal here is to securely distribute the tensor $e_0 \otimes e_1$ to both parties as in other existing PCGs
(Figure 1 and Figure 14). Note that $\mathbf{e}_{\sigma} = (e_{\sigma}^0, \dots, e_{\sigma}^{c-1})$, $\sigma \in \{0,1\}$ and each random $e_{\sigma}^i \in \mathbb{R}_t$ is defined by a pair of vectors $\mathbf{p}_{\sigma}^i \in |\mathbb{G}|^t$, $\mathbf{v}_{\sigma}^i \in \mathbb{F}_3^t$ (can be considered as set of positions of non-zero entries of a vector over $\mathbb{R}_t$ and the corresponding values of these entries). Then, $\mathbf{e}_0 \otimes \mathbf{e}_1$ is defined as a vector over $\mathbb{R}_{t^2}$ where $(\mathbf{v}_0^i \otimes \mathbf{v}_1^j)[k], k \in [t^2]$ is the value of entry in position $(\mathbf{p}_0^i \otimes \mathbf{p}_1^j)[k]$.

Now, the seed generation and seed expansion are processed as follows. Simple hashing is applied to all elements in the group $\mathbb{G}$ to get a table $\mathbf{B}$ of size $m$ where each bin in this table contains elements of $\mathbb{G}$ and items in all bins are sorted in some canonical order. Then Gen uses Cuckoo hashing and distributes each entry $(\mathbf{p}_0^i \otimes \mathbf{p}_1^j)[k]$ of $\mathbf{p}_0^i \otimes \mathbf{p}_1^j$ to only one bin (denote $l_k$) of a table $\mathbf{T}$ of size $m = O(t^2)$ while in simple hashing this entry is inserted to $K$ bins $\{i_1, \dots, i_K\}$ instead of one (note that $l_k \in \{i_1, \dots, i_K\}$), then

1. For bin $l_k$, using $\text{DPF}_{|\mathbf{B}_{l_k}|}$.Gen to generate keys such that the point function is defined by position in bin $l_k$ where $(\mathbf{p}_0^i \otimes \mathbf{p}_1^j)[k]$ is inserted and the value output shared is $(\mathbf{v}_0^i \otimes \mathbf{v}_1^j)[k]$,

2. For other bins $\{i_1, \dots, i_K\} \setminus \{l_k\}$, in the position where $(\mathbf{p}_0^i \otimes \mathbf{p}_1^j)[k]$ is inserted, the value shared is 0.

The formal constructions of key generation and key expansion are shown in Figure 20 and Figure 21 respectively.

**Theorem 36.** Let $\mathcal{R} = \mathbb{F}_4[\mathbb{G}] = \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3-1, \dots, X_n^3-1)$ where $\mathbb{G} = \prod_{i=1}^n \mathbb{Z}/3\mathbb{Z}$. Assume that $\text{DPF}_n$ is a secure FSS scheme for point function with domain $n$ and that the QA-SD(c, t, G) assumption holds. Then, there exists a generic construction scheme to construct a PCG to produce one OLE correlation (described in Figure 20 and Figure 21). Using the DPF [BGI16] based on a PRG $G: \{0,1\}^{\lambda} \to \{0,1\}^{2\lambda+2}$ and Cuckoo hashing scheme parameters $(\mathbb{G}, K, m, t^2)$ then we obtain:

- Each party's seed has maximum size: $c^2 \cdot (0.9m) \cdot ((\log(3)n - \log t + 1) \cdot (\lambda+2) + \lambda+2) + 4t \cdot (\log(3)n + 2)$ bits.

- The computation of Expand can be done with at most $(2 + \lfloor 2/\lambda \rfloor) \cdot (K3^n) \cdot c^2 \text{ PRG operations,}$ and $O(c^2 \cdot (\log(3)n) \cdot 3^n)$ operations in $\mathbb{F}_4$.

*Proof sketch.* The security of our construction is based on the security of FSS scheme and is followed the same as in [BCG$^{+}$20b, BCCD23] since (1) The parameter of the simple hashing scheme is public then both parties can self-compute the table $\mathbf{B}$ obtained from this scheme (2) and $\mathbf{p}_0^i \otimes \mathbf{p}_1^j$ and $\mathbf{v}_0^i \otimes \mathbf{v}_1^j$ are mapped to the table $\mathbf{T}_{i,j}$ by using Cuckoo hashing scheme later they are inputs of DPF.

Now we argue the correctness and efficiency in turn.

**Correctness.** First, note that

$$e_0^i \cdot e_1^j = \left( \sum_{k \in [0 \dots t)} \mathbf{v}_\sigma^i[k] \cdot \mathbf{p}_\sigma^i[k] \right) \cdot \left( \sum_{l \in [0 \dots t)} \mathbf{v}_\sigma^j[l] \cdot \mathbf{p}_\sigma^j[l] \right) \\ = \sum_{k,l \in [0 \dots t)} \left( \mathbf{v}_0^i[k] \cdot \mathbf{v}_1^j[l] \right) \cdot \left( \mathbf{p}_0^i[k] \cdot \mathbf{p}_1^j[l] \right) = \sum_{k \in [0 \dots t^2)} (\mathbf{v}_0^i \otimes \mathbf{v}_1^j)[k] \cdot (\mathbf{p}_0^i \otimes \mathbf{p}_1^j)[k].$$

Observe that $\mathbf{u}_{0,i+c_j}[k] + \mathbf{u}_{1,i+c_j}[k] = \sum_{l=1}^K (\mathbf{w}_{0,l_k}[r_k] + \mathbf{w}_{1,l_k}[r_k])$ then from the correctness of DPF:

1. If $k \in \mathbf{A}_{i,j}$ i.e., $k$ is inserted to table $\mathbf{T}_{i,j}$ using Cuckoo hashing scheme, denote $t$ as the bin of $\mathbf{T}_{i,j}$ where $k$ is inserted then:

$$\mathbf{u}_{0,i+c_j}[k] + \mathbf{u}_{1,i+c_j}[k] = \mathbf{w}_{0,t}[r_k] + \mathbf{w}_{1,t}[r_k] = (\mathbf{v}_0^i \otimes \mathbf{v}_1^j)[k].$$

2. Otherwise, $k \notin \mathbf{A}_{i,j}$ then $\mathbf{u}_{0,i+c_j}[k] + \mathbf{u}_{1,i+c_j}[k] = 0$.

Therefore,

$$\mathbf{u}_0 + \mathbf{u}_1 = \langle \mathbf{a} \otimes \mathbf{a}, \mathbf{e}_0 \otimes \mathbf{e}_1 \rangle = \langle \mathbf{a}, \mathbf{e}_0 \rangle \cdot \langle \mathbf{a}, \mathbf{e}_1 \rangle = x_0 \cdot x_1.$$

**Efficiency.** We show how to obtain the party's seed size and the computation cost of Expand in Theorem 36 by using two optimizations which are tailored on the choice of Cuckoo's parameters (to reduce the number of bins) and regular noise distribution (to reduce a factor $t$ in the number of PRG calls).

The formulas we get are adapted from [BCG$^{+}$20b, BCCD23] for $|\mathbb{G}| = 3^n$ and followed by our optimizations.
Construction fQA-SD<sub>OLE</sub>

PARAMETERS: Security parameter $\lambda$, noise weight $t = t(\lambda)$, compression factor $c = 4$, ring $\mathcal{R} = \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$.

- An DPF$_n$ scheme (DPF$_n$.Gen, DPF$_n$.FullEval) with an arbitrary domain $[n]$ and range $\mathbb{F}_4$.

- $K$ hash functions $h_1, \dots, h_K: \mathbb{G} \to [m]$.

- Cuckoo hashing and simple hashing schemes with parameters $(\mathbb{G}, K, m, t^2)$ and $(\mathbb{G}, K, m)$ respectively where $m = O(t^2)$.

PUBLIC INPUT: $c-1$ vectors of length $3^n$ over $\mathbb{F}_4$, for $a_1, \dots, a_{c-1} \in \mathcal{R}$.

fQA-SD.Gen (1<sup>λ</sup>):

1: **foreach** $\sigma \in \{0, 1\}, i \in [0 \dots c):$

1.1: Sample random vectors $\mathbf{p}_{\sigma}^{i} \leftarrow (p_{\sigma,1}^{i}, \dots, p_{\sigma,t}^{i})_{p_{\sigma,j}^{i} \in \mathbb{G}}$ and $\mathbf{v}_{\sigma}^{i} \leftarrow (\mathbb{F}_{3})^{t}$.

2: Hashing algorithm:

2.1: Use simple hashing scheme $(\mathbb{G}, K, m)$ to get a table $\mathbf{B}$ having $m$ bins $(\mathbf{B}_i)_{i \le m}$ such that:

$$ \mathbf{B}_i = \{x \in \mathbb{G} \mid \exists j \in [K] \wedge h_j(x) = i\}. $$

Each bin is sorted in some canonical order.

2.2: **foreach** $i, j \in [0 \dots c):$

2.2.1: Use the Cuckoo hashing scheme $(\mathbb{G}, K, m, t^2)$ to insert $\mathbf{p}_{i,j} := \mathbf{p}_0^i \otimes \mathbf{p}_1^j$ to table $\mathbf{T}_{i,j}$.

We denote each k-th entry value $\mathbf{p}_{i,j}$[k] of vector $\mathbf{p}_{i,j}$ is inserted to the bin $l_k \in [m]$ of table $\mathbf{T}_{i,j}$ i.e. $\mathbf{T}_{i,j}[l_k] = \mathbf{p}_{i,j}[k]$ and when considering in bin $\mathbf{B}_{l_k}$ of table $\mathbf{B}$ (obtained from simple hashing), denote the position of $\mathbf{p}_{i,j}$[k] as $r_k$ i.e. $\mathbf{B}_{l_k}[r_k] = \mathbf{p}_{i,j}[k]$.

3: **foreach** $i, j \in [0 \dots c), l_k \in [m]:$

3.1: If $\mathbf{p}_{i,j}[k] = \mathbf{T}_{i,j}[l_k]$ and $\mathbf{p}_{i,j}[k] = \mathbf{B}_{l_k}[r_k]$, sample DPF keys for each bin $\mathbf{B}_{l_k}$:

$$ (K_{0,l_k}^{i,j}, K_{1,l_k}^{i,j}) \leftarrow \text{DPF}_{|\mathbf{B}_{l_k}|} \cdot \text{Gen}(1^{\lambda}, r_k, \mathbf{v}_0^i \otimes \mathbf{v}_1^j[k]). $$

3.2: Otherwise, generate randomly $r_k \leftarrow_R |\mathbf{B}_{l_k}|$ and sample DPF keys:

$$ (K_{0,l_k}^{i,j}, K_{1,l_k}^{i,j}) \leftarrow \text{DPF}_{|\mathbf{B}_{l_k}|} \cdot \text{Gen}(1^{\lambda}, r_k, 0). $$

4: Let $k_{\sigma} = ((K_{\sigma,l_k}^{i,j})_{i,j \in [0 \dots c)}, l_k \in [m])$, $((\mathbf{p}_{\sigma}^{i}, \mathbf{v}_{\sigma}^{i}))_{i \in [0 \dots c]}$.

5: Output $(k_0, k_1)$.

<caption>Fig. 20: Seed generation of fQA-SD over $\mathcal{R}$, based on QA-SD and hashing techniques</caption>
Construction fQA-SD<sub>OLE</sub>

fQA-SD.Expand $(\sigma, \kappa_{\sigma})$:

1. Parse $k_{\sigma}$ as $((K_{\sigma,l_k}^{i,j})_{i,j \in [0 \dots c)}, l_k \in [m]), ((\mathbf{p}_{\sigma}^i, \mathbf{v}_{\sigma}^i)_{i \in [0 \dots c]}).$

2. **foreach** $i \in [0 \dots c)$:

2.1. Define the element of $\mathcal{R}_t$:

$$e_{\sigma}^{i} = \sum_{j \in [0 \dots t)} \mathbf{v}_{\sigma}^{i}[j] \cdot \mathbf{p}_{\sigma}^{i}[j].$$

3. Compute $x_{\sigma} = \langle \mathbf{a}, \mathbf{e}_{\sigma} \rangle$, where $\mathbf{a} = (1, a_1, \dots, a_{c-1}), \mathbf{e}_{\sigma} = (e_{\sigma}^0, \dots, e_{\sigma}^{c-1})$.

4. **foreach** $i, j \in [0 \dots c)$:

4.1. $\forall k \in [m]$, compute $\mathbf{w}_{\sigma,k} \leftarrow \text{DPF}_{|\mathbf{B}_k|} \cdot \text{FullEval}(\sigma, K_{\sigma,k}^{i,j})$.

4.2. **foreach** $k \in |\mathcal{G}|$:

4.2.1. $\forall l \in [1, K]$, compute $h_l(k) = l_k$, then find the bin $r_k$ of $k$ in bin $\mathbf{B}_{l_k}$ i.e., $k = \mathbf{B}_{l_k}[r_k]$.

4.2.2. Define a vector $\mathbf{u}_{\sigma,i+c_j}$ over $\mathcal{R}$ such that $\mathbf{u}_{\sigma,i+c_j}[k] = \sum_{l=1}^{K} \mathbf{w}_{\sigma,l_k}[r_k]$.

4.3. View the set of $\mathbf{u}_{\sigma,i+c_j}$ as a $c^2$ vector $\mathbf{u}_{\sigma}$ of element in $\mathcal{R}$.

5. Compute $z_{\sigma} = \langle \mathbf{a} \otimes \mathbf{a}, \mathbf{u}_{\sigma} \rangle$.

6. Output $x_{\sigma}, z_{\sigma}$.

**Fig. 21:** Seed expansion of fQA-SD over $\mathcal{R}$, based on QA-SD and hashing techniques.

1. Party's seed size, since we have $m$ bins and each bin $(\mathbf{B}_i)_{i \in [m]}$ needs to use a $\text{DPF}_{|\mathbf{B}_i|}$ scheme so in total, we have $(m \cdot c^2)$ pairs of keys $(K_{\sigma,l_k}^{i,j})_{i,j \in [0 \dots c)}, l_k \in [m]$ having a size of

$$c^2 \cdot m \cdot ((\log(3)n - \log t + 1) \cdot (\lambda + 2) + \lambda + 2) + 4t \cdot (\log(3)n + 2).$$

We make an observation that since the number of bins $m$ is defined to avoid the failure of the Cuckoo hashing scheme. However, because the distributed key generation phase is honestly executed, we allow the Cuckoo hashing scheme to fail with an acceptable probability (say 90% of standard experimental failure probability [PSWW18]). In the case of failure, then we repeat the Cuckoo hashing scheme (with a new set of functions) until it succeeds (the number of repetitions is very small in expectation). This leads to an optimization for the number of bins $m$ to be reduced to $0.9m$ while the trade-off in security is reasonable (the adversary knows the distribution of noise sampled has to make sure the Cuckoo hashing succeeds while the number of bins is only $0.9m$). Then, the seed size is reduced roughly to

$$c^2 \cdot (0.9m) \cdot ((\log(3)n - \log t + 1) \cdot (\lambda + 2) + \lambda + 2) + 4t \cdot (\log(3)n + 2).$$

2. For the number of PRG calls in seed expansion, in each bin $(\mathbf{B}_i)_{i \in [m]}$, we make use of a $\text{DPF}_{|\mathbf{B}_i|}$ with domain $|\mathbf{B}_i|$ and from the property of simple hashing scheme $\sum_{i \le m} |\mathbf{B}_i| = K \cdot |\mathcal{G}|$ then the number of PRG operations is at most $(2 + \lfloor 2/\lambda \rfloor) \cdot (K3^n) \cdot c^2$ (reduced by a factor $t$ from the regular noise distribution). $\square$

## D.2 Application of OLE over $\mathbb{F}_4$ to silent OT extension

In this section, we show how to convert an $\mathbb{F}_4$-OLE into a random 1-out-of-2 OT in $\mathbb{F}_2$ using a single bit of communication. To explain the observation, let us consider two parties, Alice and Bob, holding respectively $(a, \llbracket ab \rrbracket_A^4)$ and $(b, \llbracket ab \rrbracket_B^4)$ for $a$ and $b \in \mathbb{F}_4$. We have

$$\begin{aligned} a \cdot b &= \llbracket a \cdot b \rrbracket_A^4(0) + \llbracket a \cdot b \rrbracket_B^4(0) + (\llbracket a \cdot b \rrbracket_A^4(1) + \llbracket a \cdot b \rrbracket_B^4(1))\theta \\ &= (a(0) \cdot b(0) + a(1) \cdot b(1)) + (a(0) \cdot b(1) + a(1) \cdot b(0) + a(1) \cdot b(1)) \cdot \theta, \end{aligned}$$
where $\theta$ is the primitive root of $X^2 + X + 1$. Considering only the $(a \cdot b)(1)$ term from the above equation (i.e., the parts multiplied by $\theta$, while in conversion from single OLE to Beaver triple over $\mathbb{F}_2$ the part taken is without $\theta$), we get that

$$ (a \cdot b)(1) = \llbracket a \cdot b \rrbracket_A^4(1) + \llbracket a \cdot b \rrbracket_B^4(1) = a(0) \cdot b(1) + a(1) \cdot b(0) + a(1) \cdot b(1), $$

and therefore,

$$ \underbrace{\llbracket a \cdot b \rrbracket_A^4(1) + a(1) \cdot (b(0) + b(1))}_{\text{known by A}} = a(0) \cdot b(1) + \underbrace{\llbracket a \cdot b \rrbracket_B^4(1)}_{\text{known by B}}. $$

If Bob sends $(b(0) + b(1))$ to Alice then the equation becomes

$$ \underbrace{\llbracket a \cdot b \rrbracket_A^4(1) + a(1) \cdot (b(0) + b(1))}_{\text{known by A}} = a(0) \cdot b(1) + \underbrace{\llbracket a \cdot b \rrbracket_B^4(1)}_{\text{known by B}}. $$

It turns out that if Alice as a receiver in OT sets $t = a(0)$, $m_t = \llbracket a \cdot b \rrbracket_A^4(1) + a(1) \cdot (b(0) + b(1))$ and Bob as a sender in OT sets $m_0 = \llbracket a \cdot b \rrbracket_B^4(1)$, $m_1 := b(1) + \llbracket a \cdot b \rrbracket_B^4(1)$ then we have an instantiation of 1-out-of-2 OT over $\mathbb{F}_2$. The correctness is followed by the above equation and security is straightforward: the only communication between the parties is sending $b(0) + b(1)$ from Bob to Alice, which is a uniform random bit in the view of Alice (from the randomness of OLE).

**Efficiency.** To get $3^n$ random OT, our main QA-SDOLE PCG needs $2(c^2 \cdot t)$ PRG calls (omitting some common factors) along with a factor-64 speedup from the early termination optimization while fQA-SD only needs $(K \cdot c^2)$ PRG calls where $K = 2$, $t = 27$ (see Section 6) and can be optimized by the same optimizations. Hence, we estimate to get $3^N$-OT over $\mathbb{F}_2$, fQA-SD can be about $30 \times$ faster in terms of computation compared to [RRT23], since the cost of QA-SDOLE is essentially on par with that of [RRT23] (see Section 2 for detail).

# E Deferred Proofs

## E.1 Proof of Proposition 10

*Proof.* We prove correctness and security in turn.

**Correctness.** Fix an index $\alpha = (\alpha_1, \dots, \alpha_n)$ in a ternary basis. Consider the ternary tree consisting of $3^n$ nodes. Let $L_{i,j}^\sigma$ be any node label at depth $i$ and index $j \in [3^i]$ as computed by party $\sigma$. Define $L_{i,j} = L_{i,j}^0 \oplus L_{i,j}^1$ and $\ell_i = 3^i \alpha_i + 3^{i-1}\alpha_{i-1} + \dots + \alpha_1$. To prove correctness, we start by showing that the following two invariants are maintained throughout the tree:

1. For all node labels $L_{i,j}$ where $j \neq \ell_i$, $L_{i,j} = 0^\lambda \| 0 \|$.

2. For all node labels $L_{i,j}$ where $j = \ell_i$, $L_{i,j} = L' \| 1$ where $L' \in \{0,1\}^\lambda \setminus \{0^\lambda\}$.

If we can show that the two invariants are maintained, it immediately follows that only one path along the tree contains non-zero labels. Once we've shown this, we can argue why the output at the non-zero label at the leaf is equal to $\beta$.

We first prove that all child node labels $(L_{i,3j}, L_{i,3j+1}, L_{i,3j+2})$ of parent nodes with labels $L_{i-1,j} = 0^\lambda \| 0$ are also zero. That is, $(L_{i,3j}, L_{i,3j+1}, L_{i,3j+2}) = (0^{\lambda+1})^3$. By definition, $L_{i-1,j} = L_{i-1,j}^0 \oplus L_{i-1,j}^1$, where $L_{i-1,j}^\sigma = s_{i-1}^\sigma \| t_{i-1}^\sigma$, for $\sigma \in \{0,1\}$. Since $L_{i-1,j} = 0^\lambda \| 0$, it holds that $L_{i-1,j}^0 = L_{i-1,j}^1$. Hence, $G(s_{i-1,j}^0) = G(s_{i-1,j}^1)$, which implies that both parties compute the same $\tau_i^\sigma$ in Line 3.1 of Traverse. Moreover, because $L_{i-1,j} = s_{i-1} \| t_{i-1} = 0^\lambda \| 0$, it follows that $t_{i-1}^0 \oplus t_{i-1}^1 = 0$. In turn, we have that $\gamma_i^0 \oplus \gamma_i^1 = \tau_i^0 \oplus \tau_i^1$, since the correction word is not applied (it is multiplied by $t_{i-1}^\sigma$—an XOR share of zero). This implies that (1) $L_{i,3j} = s_{i,0}^0 \| t_{i,0}^0 \oplus s_{i,0}^1 \| t_{i,0}^1 = 0^\lambda \| 0$, (2) $L_{i,3j+1} = s_{i,1}^0 \| t_{i,1}^0 \oplus s_{i,1}^1 \| t_{i,1}^1 = 0^\lambda \| 0$, and (3) $L_{i,3j+2} = s_{i,2}^0 \| t_{i,2}^0 \oplus s_{i,2}^1 \| t_{i,2}^1 = 0^\lambda \| 0$, as required.

In other words, the above proves that all child node labels that are off the “special path” described by $\alpha$ remain zero. We must now prove that all child node labels that are on the “special path” (i.e., child nodes where the parent node is non-zero) only have one non-zero sibling after the correction word is applied.

We prove this by induction starting with the root of the tree. Note that $L_0 = s_0^0 \| t_0^0 \oplus s_0^1 \| t_0^1$ and that $t_0^0 \oplus t_0^1 = 1$ by definition (Line 2 of DPF.Gen). Since the root label has no siblings, the
base case is trivially satisfied. Now consider any parent node label $L_{i-1,j}$ of the form $L_{i-1,j} = s\|1$ for some $s \neq 0^\lambda$. Consider the child node labels $(L_{i,3j}, L_{i,3j+1}, L_{i,3j+2})$ of parent node label $L_{i-1,j}$. Since $L_{i-1,j} \neq 0^\lambda\|1$, it holds that $L_{i-1,j}^0 \neq L_{i-1,j}^1$. Hence, with overwhelming probability, it holds that $G(s_{i-1,j}^0) \neq G(s_{i-1,j}^1)$, which implies that both parties compute a different $\tau_i^\sigma$ in Line 3.1 of Traverse. Moreover, because $t_i = t_i^0 \oplus t_i^1 = 1$, it holds that $\gamma_i = \gamma_i^0 \oplus \gamma_i^1 = (\tau_i^0 \oplus \tau_i^1) \oplus (CW_{i,0}\|CW_{i,1}\|CW_{i,2})$. Then, by construction of $CW_{i,0}, CW_{i,1}, CW_{i,2}$ (Lines 4.6–4.9 of DPF.Gen), we have that $\gamma_i = s_{i,0}\|t_{i,0}\|s_{i,1}\|t_{i,1}\|s_{i,2}\|t_{i,2}$ where $s_{i,k}\|t_{i,k} = 0^\lambda\|0$ for all $k \in \{0, 1, 2\} \setminus \{\alpha_i\}$. In turn, we have that two (out of the three) child labels are zero. In words, this proves that at each level of the tree, only one label is non-zero, and the non-zero label is at index $\ell_i = 3^i\alpha_i + 3^{i-1}\alpha_{i-1} + \cdots + \alpha_1$ because the $\alpha_{i-1}$-st child label of each non-zero parent label is always non-zero. This proves the second invariant.

To satisfy the rDPF definition, it remains to show that the non-zero leaf label of the tree is of the form $L_n = s\|1$ where $s$ is a pseudorandom value (from the viewpoint of either party). To see this, consider the base case of Traverse (when $i = n+1$) for the non-zero leaf label. The output of Traverse is just $s_n\|t_n$. Therefore, for the non-zero child, $(s_n^0\|t_n^0 \oplus s_n^1\|t_n^1) = s_n\|t_n \oplus CW_{n,\alpha_n} = s_n \oplus (s_n \oplus r_n)\|1 = r_n\|1$ by definition of $CW_{n,\alpha_n}$ in Line 3.8 of DPF.Gen. It follows that $r_n$ is pseudorandom since it is chosen uniformly at random and is masked by $s_n$ in $CW_{n,\alpha_n}$, which is pseudorandom conditioned on either key.

**Security.** Informally, security holds because (1) the starting labels $s_0^0$ and $s_0^1$ given to party 0 and 1, respectively, are uniformly random and (2) the correction words (i.e., pp) consist of the expanded shares of party $\sigma$ masked by the pseudorandom shares of party $1-\sigma$ which makes them computationally indistinguishable from random from the viewpoint of party $\sigma$ given $K_\sigma$.

Formally, we prove security via a sequence of hybrid distributions and reducing to the pseudorandomness of a GGM tree construction [GGM19] (generalized to have a branching factor of 3 to match our ternary tree). Fix $\alpha = \alpha_1\|\cdots\|\alpha_n$.

Hybrid $\mathcal{H}_0$. This hybrid consists of the DPF key $K_\sigma$ as defined in Figure 5. Specifically,

$$ \mathcal{H}_0 = \left\{ \left( \underbrace{\overline{\mathrm{CW}_{1,0}} \| \overline{\mathrm{CW}_{1,1}} \| \overline{\mathrm{CW}_{1,2}} \dots \overline{\mathrm{CW}_{1,n}}}_{\mathrm{pp}} \right) \middle| \overline{\mathrm{CW}_{n,0}} \| \overline{\mathrm{CW}_{n,1}} \| \overline{\mathrm{CW}_{n,2}} \right\}, s_0^\sigma \| t_0^\sigma \} $$

where $\overline{\mathrm{CW}}_{i,j}$, for $i \in [n]$ and $j \in \{0, 1, 2\}$, is defined as $\overline{\mathrm{CW}}_{i,j} = s_{i,j}^0 \| t_{i,j}^0 \oplus s_{i,j}^1 \| t_{i,j}^1$ if $j \neq \alpha_i$, $\overline{\mathrm{CW}}_{i,j} = (s_{i,\alpha_i} \oplus r_i) \|(t_{i,j}^0 \oplus t_{i,j}^1 \oplus 1) \text{ if } j = \alpha_i \wedge i \neq n$, and $\overline{\mathrm{CW}}_{n,j} = s_n \oplus \beta\|0$ if $j = \alpha_i \wedge i = n$.

Hybrid $\mathcal{H}_1$. In this hybrid, we define each correction word as being party $\sigma$'s share masked with a uniformly random mask (as opposed to being masked by a value computed by party $1-\sigma$). Specifically,

$$ \mathcal{H}_1 = \{ (\overline{\mathrm{CW}}_{1,0} \| \overline{\mathrm{CW}}_{1,1} \| \overline{\mathrm{CW}}_{1,2} \dots \overline{\mathrm{CW}}_{n,0} \| \overline{\mathrm{CW}}_{n,1} \| \overline{\mathrm{CW}}_{n,2}) , s_0^\sigma \| t_0^\sigma \} $$

where $\overline{\mathrm{CW}}_{i,j}$, for $i \in [n]$ and $j \in \{0, 1, 2\}$, is defined as $\overline{\mathrm{CW}}_{i,j} = s_{i,j}^\sigma \| t_{i,j}^\sigma \oplus \mathrm{mask}_{i,j}$ if $j \neq \alpha_i$, $\overline{\mathrm{CW}}_{i,j} = (s_{i,\alpha_i}^\sigma \oplus r_i) \|(t_{i,j}^\sigma \oplus 1) \oplus \mathrm{mask}_{i,j}$ if $j = \alpha_i \wedge i \neq n$, and $\overline{\mathrm{CW}}_{n,j} = (s_n^\sigma \oplus \beta\|0) \oplus \mathrm{mask}_{n,j}$ if $j = \alpha_i \wedge i = n$. Where for each $i, j, \mathrm{mask}_{i,j} \leftarrow_R \{0, 1\}^{\lambda+1}$.

Hybrid $\mathcal{H}_2$. In this hybrid, we define each correction word as being a uniformly random string of appropriate length. That is,

$$ \mathcal{H}_2 = \{ (\overline{\mathrm{CW}}_{1,0}, \overline{\mathrm{CW}}_{1,1} \| \overline{\mathrm{CW}}_{1,2} \| \dots \overline{\mathrm{CW}}_{n,0} \| \overline{\mathrm{CW}}_{n,1} \| \overline{\mathrm{CW}}_{n,2}) , s_0^\sigma \| t_0^\sigma \} $$

where $\overline{\mathrm{CW}}_{i,j}$, for all $i \in [n]$ and $j \in \{0, 1, 2\}$, is defined as $\overline{\mathrm{CW}}_{i,j} \leftarrow_R \{0, 1\}^{\lambda+1}$.

Claim. $\mathcal{H}_0 \approx_c \mathcal{H}_1$

*Proof.* The claim follows from the pseudorandomness of the GGM construction [GGM19] (generalized to the ternary-arity case). Specifically, each $s_{i,j}^{1-\sigma} \| t_{i,j}^{1-\sigma}$ is computed as the output of a PRG applied to a pseudorandom seed $s_{i-1,j}^{1-\sigma} \| t_{i-1,j}^{1-\sigma}$, where the starting seed $s_0^{1-\sigma}$ is sampled independently of $s_0^\sigma$. Therefore, by the pseudorandomness of the GGM construction [GGM19, Theorem 3], for all $i \in [n], j \in \{0, 1, 2\}$, it follows that $s_{i,j}^{1-\sigma} \| t_{i,j}^{1-\sigma}$ is also pseudorandom. We can therefore replace the pseudorandom strings with uniformly random strings $\mathrm{mask}_{i,j}$, which proves the claim.
Claim. $H_1 \equiv H_2$

Proof. The claim follows immediately by noticing that the uniformly random strings $M_{i,j}$ and $\text{mask}_{i,j}$ in $H_1$ act as information-theoretic masks, making the distribution identical to $H_2$.

Finally, to prove security we must prove the existence of an efficient simulator $S$ that generates a computationally indistinguishable DPF key $K_\sigma$ on input $(1^\lambda, 1^n, \sigma)$. The existence of $S$ follows trivially by the fact that $H_3$ consists of a uniformly random string of length $\{0, 1\}^{3(\lambda+1)+\lambda+1}$.

<figure><img src="image_7.png" /></figure>

## E.2 Proof of Lemma 11

### Ideal Functionality $\binom{1}{3}$-OT

There are two parties, a sender and a receiver. The sender has input $(m_0, m_1, m_2) \in \{0, 1\}^*$ while the receiver has input $b \in \{0, 1, 2\}$.

**FUNCTIONALITY:**

1. Wait for input $(m_0, m_1, m_2) \in \{0, 1\}^*$ from the sender.

2. Wait for input $b \in \{0, 1, 2\}$ from the receiver.

3. Output $m_b$ to the receiver and $\perp$ to the sender.

<caption>Fig. 22: Ideal functionality $\binom{1}{3}$-OT in the semi-honest setting.</caption>

Proof. We show correctness and security in turn.

**Correctness.** To prove the correctness, we show that in our construction $\Pi_{\text{DPF-CW}}$, $CW_i = (CW_{i,0}, CW_{i,1}, CW_{i,2})$ satisfies the following two conditions:

1. For all $j \in \{0, 1, 2\} \setminus \{\alpha_i\}$ then $CW_{i,j} = (s_{i,j}^0 \| t_{i,j}^0) \oplus (s_{i,j}^1 \| t_{i,j}^1)$.

2. Otherwise, $CW_{i,\alpha_i} = (s_{i,\alpha_i}^0 \| t_{i,\alpha_i}^0) \oplus (s_{i,\alpha_i}^1 \| t_{i,\alpha_i}^1) \oplus (r_i \| 1)$.

Observe that in our construction from the definition of $\{C_j^0, C_j^1\}_{j \in \{0, 1, 2\}}$, we have $C_{\alpha_i}^0 \oplus C_{\alpha_i}^1 = CW_i \oplus z^0 \oplus z^1$. Note that $\alpha_i = [[\alpha_i]]_0 + [[\alpha_i]]_1$. Consider,

$$M_0^\sigma = (C_0^\sigma, C_1^\sigma, C_2^\sigma), \quad M_1^\sigma = (C_1^\sigma, C_2^\sigma, C_0^\sigma), \quad M_2^\sigma = (C_2^\sigma, C_0^\sigma, C_1^\sigma),$$

for $\sigma \in \{0, 1\}$. Observe that each $M_j^\sigma = (C_j^\sigma, C_{j+1}^\sigma, C_{j+2}^\sigma)$, for $j \in \{0, 1, 2\}$, is a cyclically shifted vector defined by shifting $(C_0^\sigma, C_1^\sigma, C_2^\sigma)$ to the left $j$ times.

We show that party $\sigma = 0$ obtains the correct correction word (the case where $\sigma = 1$ is symmetric). Party 0 invokes the $\binom{1}{3}$-OT as the receiver with input $[[\alpha_i]]_0$, and party 1 plays the role of the sender with input

$$M_{[[\alpha_i]]_1}^1 = (C_{[[\alpha_i]]_1}^1, C_{[[\alpha_i]]_1+1}^1, C_{[[\alpha_i]]_1+2}^1).$$

After invoking $\binom{1}{3}$-OT, party 0 obtains $C_{[[\alpha_i]]_1+[[\alpha_i]]_0}^1 = C_{\alpha_i}^1$. (By a symmetric argument, party 1 gets $C_{\alpha_i}^0$.) It is easy to see that $C_{\alpha_i}^1 \oplus z^0$ and $C_{\alpha_i}^0 \oplus z^1$ form shares of $CW_i$, since $(C_{\alpha_i}^0 \oplus z^1) \oplus (C_{\alpha_i}^1 \oplus z^0) = (CW_i \oplus z^0 \oplus z^1) \oplus (z^0 \oplus z^1)$, where $CW_i$ is defined identically to the $i$-th iteration of Figure 5. It follows that the output of the protocol (opening of the shares of $CW_i$) is correct.

**Security.** We prove our security in the UC model. In a nutshell, the proof boils down to the security of the 1-out-of-3 oblivious transfer functionality $\binom{1}{3}$-OT. We assume $\binom{1}{3}$-OT securely realizes the ideal functionality Figure 22 in a semi-honest setting. Since the role of the two parties is symmetric, we can build a simulator that simulates the view of both parties when one of them is corrupted. Without loss of generality, assume $\sigma$ is the corrupted party, Sim interacts with $\mathcal{A}$ as in the hybrid model below.
**Hybrid $\mathcal{H}_0$.** This hybrid is identical to the real protocol, both parties are honest, and $(\begin{smallmatrix} 1 \\ 3 \end{smallmatrix})$-OT is executed honestly.

**Hybrid $\mathcal{H}_1$.** This hybrid is identical to $\mathcal{H}_0$ except that now Sim plays the role of $\mathcal{A}$ and inputs $\{[\alpha]_\sigma, r_i^\sigma, (s_{i,j}^\sigma \| t_{i,j}^\sigma)_{j \in \{0,1,2\}}\}$ to the ideal functionality $\mathcal{F}_{\text{rDPF-CW}}$ and receives $CW_i$ as output.

The distribution of this hybrid is identical to that of the previous hybrid since in this hybrid, Sim does not interact with $\mathcal{A}$.

**Hybrid $\mathcal{H}_2$.** This hybrid distribution is identical to $\mathcal{H}_1$ except now Sim emulates $(\begin{smallmatrix} 1 \\ 3 \end{smallmatrix})$-OT as follows.

- When $\mathcal{A}$ is the sender, learns the input vector $M_{[\alpha_i]_\sigma}^\sigma$ of $\mathcal{A}$. Since Sim knows $(s_{i,j}^\sigma \| t_{i,j}^\sigma)_{j \in \{0,1,2\}}$ then from $M_{[\alpha_i]_\sigma}^\sigma, [\alpha_i]_\sigma$, Sim recomputes $z^\sigma$.

- When $\mathcal{A}$ is the receiver with input $[\alpha_i]_\sigma$, Sim plays the role of $(\begin{smallmatrix} 1 \\ 3 \end{smallmatrix})$-OT and gives $\mathcal{A}$ an random string $M_{[\alpha_i]_\sigma}^\sigma$ $[\alpha_i]_\sigma$.

This hybrid is indistinguishable from $\mathcal{H}_1$ since by assumption we assume that $(\begin{smallmatrix} 1 \\ 3 \end{smallmatrix})$-OT realizes the ideal functionality of one-out-of-three OTs.

**Hybrid $\mathcal{H}_3$.** In this hybrid, Sim defines $[CW_i]_{\bar{\sigma}} := M_{[\alpha_i]_\sigma}^{\bar{\sigma}} [\alpha_i]_\sigma \oplus z^\sigma$ and $[CW_i]_{\bar{\sigma}} := CW_i - [CW_i]_\sigma \in \{0,1\}^{3(\lambda+1)}$. Sim plays the role of party $\sigma$, sends $[CW_i]_{\bar{\sigma}}$ to $\mathcal{A}$.

This hybrid is indistinguishable from the previous hybrid. First, from the definition of $[CW_i]_\sigma$ and $[CW_i]_{\bar{\sigma}}$, the output $CW_i$ of ideal world and real world are identically distributed. Second, in the view of $\mathcal{A}$ after invoking the $(\begin{smallmatrix} 1 \\ 3 \end{smallmatrix})$-OT, the message it gets $M_{[\alpha_i]_\sigma}^\sigma$ $[\alpha_i]_\sigma$ is uniformly random since $z^{\bar{\sigma}}$ used as a mask is random over $\{0,1\}^{3(\lambda+1)}$. This concludes the proof. $\square$

### E.3 Proof of Proposition 12

*Proof. Correctness.* Fix an index $\alpha^i = (\alpha_1, \dots, \alpha_i)$ in a ternary tree of $i$-th layer. The correctness follows by the correctness of $\Pi_{\text{rDPF-CW}}$ Lemma 11. Since both parties invoke $\Pi_{\text{rDPF-CW}}$ and get $CW_i \leftarrow \Pi_{\text{rDPF-CW}}(i, [\alpha_i]_\sigma, r_i^\sigma, (s_{i,j}^\sigma \| t_{i,j}^\sigma)_{j \in \{0,1,2\}})$, where $CW_i = (CW_{i,0}, CW_{i,1}, CW_{i,2})$ such that:

1. For all $j \in \{0,1,2\} \setminus \{\alpha_i\}$ then $CW_{i,j} = (s_{i,j}^0 \| t_{i,j}^0) \oplus (s_{i,j}^1 \| t_{i,j}^1)$.

2. Otherwise, $CW_{i,\alpha_i} = (s_{i,\alpha_i}^0 \| t_{i,\alpha_i}^0) \oplus (s_{i,\alpha_i}^1 \| t_{i,\alpha_i}^1) \oplus (r_i \| 1)$.

Therefore, $CW_i$ defined in $\Pi_{\text{rDPF-CW}}$ has the same properties as $CW_i$ defined in Figure 5. Let $s = [s]^{0} \oplus [s]^{1}$. To prove correctness of rDPF.FullEval when using $CW_i$ computed via $\Pi_{\text{rDPF-CW}}$, we show that for each $i \in [n]$,

$$ \hat{t}_{i-1, \alpha^i} := \hat{t}_{i-1, \alpha^i}^0 \oplus \hat{t}_{i-1, \alpha^i}^1 = 1, $$

otherwise $\hat{t}_{i-1, \alpha^i} = 0$ for $i \in [3^i - 1] \setminus \{\alpha^i\}$. This is done by induction for $i \in [n]$. For $i = 1$, this follows immediately. For $i \ge 1$, we have

$$ \begin{aligned} & (\hat{s}_{i,3j} \| \hat{t}_{i,3j} \| \hat{s}_{i,3j+1} \| \hat{t}_{i,3j+1} \| \hat{s}_{i,3j+2} \| \hat{t}_{i,3j+2}) \\ & = (s_{i,3j} \| t_{i,3j} \| s_{i,3j+1} \| t_{i,3j+1} \| s_{i,3j+2} \| t_{i,3j+2}) \oplus (\hat{t}_{i-1,j} \cdot CW_i). \end{aligned} $$

Assume $\alpha^i \in \{3j^*, 3j^*+1, 3j^*+2\}$ for some $j^* \in [3^i - 1]$, from the definition of $(s_{i,j}^\sigma \| t_{i,j}^\sigma)_{j \in \{0,1,2\}, \sigma \in \{0,1\}}$ then we have:

1. $(s_{i,3j} \| t_{i,3j} \| s_{i,3j+1} \| t_{i,3j+1} \| s_{i,3j+2} \| t_{i,3j+2}) = (0,0,0)$ for $j \ne j^*$.

2. $CW_{i,j} = s_{i,3j^*+j} \| t_{i,3j^*+j}$ for $j \ne \alpha_i$, otherwise $CW_{i,\alpha_i} = (s_{i,3j^*+\alpha_i} \| t_{i,3j^*+\alpha_i}) \oplus (r_1 \| 1)$.

then by induction $\hat{t}_{i-1,j^*} = 1 \implies \hat{t}_{i,3j^*+\alpha_{i+1}} = 1$ otherwise, $\hat{t}_{i,j} = 1$ for $i \in [3^{i+1} - 1]$.

**Security.** Since our instantiation does not have any interaction between two parties except both parties invoke to $\Pi_{\text{rDPF-CW}}$. So our security against semi-honest setting is directly achieved from the security of $\Pi_{\text{rDPF-CW}}$ Lemma 11. Note that the distribution of our $CW_i$ is indistinguishable from the distribution of $CW_i$ defined in Figure 5 and it is proved to be secure (Appendix E.1) in the view of party $\sigma$ given $K_\sigma$. $\square$
## E.4 Proof of Proposition 13

*Proof.* Informally, the construction $\Pi_{Output-CW}$ is very similar to the way we compute the intermediate CW$_i$ in Figure 7, except that (1) the inputs of the sender in each $\binom{1}{3}$-OT execution of the i-th iteration are always the share of a vector $(\mathbf{C}_{i,\alpha_i}^1 \oplus z_i^0) \oplus (\mathbf{C}_{i,\alpha_i}^0 \oplus z_i^1) \in (\mathbb{F}_4)^{3^i}$ (the entry of position $\alpha := \sum_{k=0}^i \alpha_k 3^{k-1}$ is $\beta$, all others entries are 0), and (2) $\Pi_{Output-CW}$ is computed iteratively such that the value that each party obtains (seen as $[[CW_i]]_\sigma$) is kept secret.

**Correctness.** We show that for each $i \in [t]$,

$$[[\beta]]_0 \oplus [[\beta]]_1 = \beta, \text{ where, } [[\beta]]_i \in (\mathbb{F}_4)^{3^i}$$

As shown in the correctness proof of Lemma 11, $\mathbf{M}_j^\sigma = (\mathbf{C}_j^\sigma, \mathbf{C}_{j+1}^\sigma, \mathbf{C}_{j+2}^\sigma)$ for $j \in \{0, 1, 2\}$ and $\sigma \in \{0, 1\}$ is obtained by cyclically shifting the vector $(\mathbf{C}_0^\sigma, \mathbf{C}_1^\sigma, \mathbf{C}_2^\sigma)$ to the left $j$ times. Moreover, we have that $[[\alpha_i]]_1 + [[\alpha_i]]_0 = \alpha_i$.

Consider party 0 (the case for party 1 is symmetric). Party 0 invokes the $\binom{1}{3}$-OT functionality as the receiver with input $[[\alpha_i]]_0$ and party 1 plays the role of the sender with input

$$\mathbf{M}_{[\alpha_i]_1}^1 = (\mathbf{C}_{i,[\alpha_i]_1}^1, \mathbf{C}_{[[\alpha_i]_1+1], [\alpha_i]_1}^1, \mathbf{C}_{[[\alpha_i]_1+2], [\alpha_i]_1}^1),$$

(viewed as a vector of vectors). Then, it holds that party 0 obtains as output

$$\mathbf{M}_{[[\alpha_i]_1, [\alpha_i]_0]}^1 = \mathbf{C}_{i,[[\alpha_i]_1]+[[\alpha_i]_0]}^1 = \mathbf{C}_{i,\alpha_i}^1.$$

By symmetry, party 1 then obtains $\mathbf{C}_{i,\alpha_i}^0$ by invoking the $\binom{1}{3}$-OT protocol with party 0 now playing the role of the sender. Then, letting $[[\beta]]_1 = \mathbf{C}_{i,\alpha_i}^0 \oplus z_i^1$ and $[[\beta]]_0 = \mathbf{C}_{i,\alpha_i}^1 \oplus z_i^0$ be the shares of $\beta$, because the $z_i^0$ and $z_i^1$ terms cancel out the masking terms added by each party, we get that

$$[[\beta]]_0 \oplus [[\beta]]_1 = \mathbf{C}_{i,\alpha_i}^1 \oplus z_i^1 \oplus \mathbf{C}_{i,\alpha_i}^0 \oplus z_i^0 = \begin{cases} (\beta, 0, 0)), & \text{if } \alpha_i = 0. \\ (0, \beta, 0)), & \text{if } \alpha_i = 1. \\ (0, 0, \beta)), & \text{if } \alpha_i = 2. \end{cases}$$

or in other words, $[[\beta]]_0 \oplus [[\beta]]_1 = \mathbf{e}_{\alpha_i} \cdot \beta$, where $\mathbf{e}_{\alpha_i}$ is the $\alpha_i$-th standard basis vector over $\mathbb{F}_4^i$.

To see that correctness still holds after the t-th iteration, $\{\mathbf{C}_{i+1,j}^\sigma\}_{j \in \{0,1,2\}}$ in $(i+1)$-th iteration is defined by $[[\beta]]_\sigma \in (\mathbb{F}_4)^{3^i}$ from the i-th iteration and adding 0's to make sure that $\beta$ and the position of share value in vector of size $(\mathbb{F}_4)^{3^i}$ is $\sum_{k=0}^i \alpha_k 3^{k-1}$. This leads to $\text{CW} := e_\alpha \cdot \beta \oplus G(s^0) \oplus G(s^1) \in (\mathbb{F}_4)^{3^t}$ where $\alpha = \sum_{i=0}^t \alpha_i 3^{i-1}$, as required.

**Security Analysis.** The simulator $\text{Sim}$ is constructed similarly to the simulator in the proof of Lemma 11, except that $\text{Sim}$ does not play the role of party $\sigma$ to output $[[\beta]]_\sigma$ for each iteration. Instead, it only outputs the share for the last iteration, which allows both parties to construct the output CW. $\text{Sim}$ emulates $\binom{1}{3}$-OT to learn the mask $z_i^\sigma$ and inputs of $\mathcal{A}$ that plays the role of the sender to $\binom{1}{3}$-OT in the i-th iteration. Then, using this information, $\text{Sim}$ simulates the $(i+1)$-th iteration. And for the last step, to simulate the output of the honest party, $\text{Sim}$ defines $[[\text{CW}]]_\sigma$ from $[[\text{CW}]]_\sigma$ that is constructed by emulating $\binom{1}{3}$-OT and CW the output of ideal functionality $\mathcal{F}_{Output-CW}$. $\square$