FOLEAGE: F 4 OLE-Based Multi-Party Computation
for Boolean Circuits

Maxime Bombar, Dung Bui, Geoffroy Couteau, Alain Couvreur, Clément Ducros, Sacha Servan-Schreiber

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

To cite this version:

Maxime Bombar, Dung Bui, Geoffroy Couteau, Alain Couvreur, Clément Ducros, et al. FOLEAGE: F 4 OLE-Based Multi-Party Computation for Boolean Circuits. ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Chung, K.M.; Sazaki, Y., Dec 2024, Kolkata, India. pp.69-101, 10.1007/978-981-96-0938-3_3. hal-04770551v2

HAL Id: hal-04770551

https://hal.science/hal-04770551v2

Submitted on 2 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
FOLEAGE: $F_4$OLE-Based Multi-Party Computation for
Boolean Circuits

Maxime Bombar¹, Dung Bui², Geoffroy Couteau³,², Alain Couvreur⁴,⁵, Clément Ducros²,⁴, and
Sacha Servan-Schreiber⁶

1 Cryptology Group, CWI, Amsterdam, The Netherlands

² IRIF, Université Paris Cité, Paris, France

³ CNRS, France

⁴ INRIA, France

⁵ Laboratoire LIX, École Polytechnique, Institut Polytechnique de Paris, France

⁶ MIT, USA

maxime.bombar@cwi.nl

{bui, couteau, cducros}@irif.fr

alain.couvreur@inria.fr

3s@mit.edu

**Abstract.** Secure Multi-party Computation (MPC) allows two or more parties to compute any public function over their privately-held inputs, without revealing any information beyond the result of the computation. Modern protocols for MPC generate a large amount of input-independent preprocessing material called *multiplication triples*, in an offline phase. This preprocessing can later be used by the parties to efficiently instantiate an input-dependent online phase computing the function.

To date, the state-of-the-art secure multi-party computation protocols in the preprocessing
model are tailored to secure computation of *arithmetic* circuits over large fields and require
little communication in the preprocessing phase, typically $O(N \cdot m)$ to generate $m$ triples among
$N$ parties. In contrast, when it comes to computing preprocessing for computations that are
naturally represented as *Boolean* circuits, the state-of-the-art techniques have not evolved since
the 1980s, and in particular, require every pair of parties to execute a large number of oblivious
transfers before interacting to convert them to $N$-party triples, which induces an $\Omega(N^2 \cdot m)$
communication overhead.

In this paper, we introduce FOLEAGE, which addresses this gap by introducing an efficient
preprocessing protocol tailored to Boolean circuits, with semi-honest security and tolerating
$N-1$ corruptions. FOLEAGE has excellent concrete performance: It generates $m$ multiplication
triples over $F_2$ using only $N \cdot m + O(N^2 \cdot \log m)$ bits of communication for $N$-parties, and can
concretely produce over 12 million triples per second in the 2-party setting on one core of a
commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator
(PCG) for multiplication triples over the field $F_4$. Roughly speaking, a PCG enables parties to
stretch a short seed into a large number of pseudorandom correlations *non-interactively*, which
greatly improves the efficiency of the offline phase in MPC protocols. This is achieved by intro-
ducing a number of protocol-level, algorithmic-level, and implementation-level optimizations on
the recent PCG construction of Bombar et al. (Crypto 2023) from the Quasi-Abelian Syndrome
Decoding assumption.
Table of Contents

<table><tbody><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>1.1</td><td>Our focus and contributions</td><td>4</td></tr><tr><td>1.2</td><td>Organization</td><td>6</td></tr><tr><td>2</td><td>Technical Overview</td><td>6</td></tr><tr><td>2.1</td><td>Background: Secure MPC from PCGs</td><td>7</td></tr><tr><td>2.2</td><td>Constructing programmable PCGs</td><td>8</td></tr><tr><td>2.3</td><td>F<sub>2</sub>-triples from F<sub>4</sub>-triples</td><td>9</td></tr><tr><td>2.4</td><td>An improved protocol from F<sub>4</sub>-OLEs for N = 2</td><td>10</td></tr><tr><td>2.5</td><td>A fast programmable PCG for F<sub>4</sub>-OLEs</td><td>10</td></tr><tr><td>2.6</td><td>Distributed seed generation</td><td>12</td></tr><tr><td>2.7</td><td>Concrete cryptanalysis of F<sub>4</sub>OLEAGE</td><td>14</td></tr><tr><td>3</td><td>Preliminaries</td><td>15</td></tr><tr><td>3.1</td><td>Function secret sharing</td><td>16</td></tr><tr><td>3.2</td><td>The Quasi-Abelian Syndrome Decoding Problem</td><td>16</td></tr><tr><td>4</td><td>A Fast PCG for F<sub>4</sub>-OLEs</td><td>18</td></tr><tr><td>4.1</td><td>PCGs over F<sub>4</sub> from the QA-SD assumption</td><td>18</td></tr><tr><td>4.2</td><td>Optimizing the FSS evaluation via early termination</td><td>19</td></tr><tr><td>4.3</td><td>Fast evaluation over F<sub>4</sub>[X<sub>1</sub>,..., X<sub>n</sub>]/(X<sub>1</sub><sup>3</sup> - 1,..., X<sub>n</sub><sup>3</sup> - 1)</td><td>21</td></tr><tr><td>5</td><td>Distributed Seed Generation</td><td>22</td></tr><tr><td>5.1</td><td>A ternary distributed point function</td><td>22</td></tr><tr><td>5.2</td><td>Distributed DPF key generation</td><td>23</td></tr><tr><td>6</td><td>Cryptanalysis and Parameter Selection</td><td>26</td></tr><tr><td>6.1</td><td>Model of attack</td><td>28</td></tr><tr><td>6.2</td><td>Generic decoding algorithms</td><td>29</td></tr><tr><td>6.3</td><td>Analysis of Folding attacks</td><td>30</td></tr><tr><td>6.4</td><td>Improving the attack: Folding for several subgroups</td><td>32</td></tr><tr><td>7</td><td>Implementation and Evaluation</td><td>32</td></tr><tr><td>A</td><td>PCGs from the QA-SD assumption</td><td>39</td></tr><tr><td>B</td><td>N-party MPC with Preprocessing from F<sub>4</sub>-OLEs</td><td>39</td></tr><tr><td>B.1</td><td>Secure computation in the F<sub>4</sub>-hybrid model</td><td>39</td></tr><tr><td>B.2</td><td>An improved protocol for N = 2 parties</td><td>42</td></tr><tr><td>C</td><td>Complexity of Informations Set Decoding algorithms over F<sub>q</sub></td><td>43</td></tr><tr><td>C.1</td><td>Stern/Dumer</td><td>44</td></tr><tr><td>C.2</td><td>MMT</td><td>45</td></tr><tr><td>C.3</td><td>BJMM</td><td>47</td></tr><tr><td>D</td><td>Faster seed expansion from hashing (application to silent OT)</td><td>48</td></tr><tr><td>D.1</td><td>Faster seed expansion</td><td>49</td></tr><tr><td>D.2</td><td>Application of OLE over F<sub>4</sub> to silent OT extension</td><td>52</td></tr><tr><td>E</td><td>Deferred Proofs</td><td>53</td></tr><tr><td>E.1</td><td>Proof of Proposition 10</td><td>53</td></tr><tr><td>E.2</td><td>Proof of Lemma 11</td><td>55</td></tr><tr><td>E.3</td><td>Proof of Proposition 12</td><td>56</td></tr><tr><td>E.4</td><td>Proof of Proposition 13</td><td>57</td></tr></tbody></table>
# 1 Introduction

A secure multiparty computation (MPC) protocol for a public functionality $f$ allows $N$ parties with private inputs $(x_1, \cdots, x_N)$ to securely compute $f(x_1, \cdots, x_N)$, while concealing all other information about their private inputs to coalitions of corrupted parties. MPC was introduced in the seminal work of Goldreich, Micali, and Wigderson [GMW87] (GMW), and has since led to a rich body of work developing the foundations of MPC, and even practical open-source libraries [Kel20].

Two of the leading paradigms in secure computation are garbled circuits [Yao86] and secret-sharing-based secure computation [GMW87]. The seminal GMW protocol is of the latter type. In a secret-sharing-based MPC protocol, the parties hold shares of the inputs and iteratively compute the circuit representing the function, gate-by-gate. Because addition gates can be computed locally by the parties holding the input shares, only multiplication gates require interaction between the parties to evaluate. As such, the major bottleneck of MPC protocols is due to the communication required to evaluate the multiplication gates in a circuit. (Note that this is also true of the garbled circuit approach where addition gates are “free” and only multiplication gates need to be garbled [KS08].)

However, a core advantage of secret-sharing-based MPC, first identified in the work of Beaver [Bea92], is that secure multiplications can be *preprocessed* in an *input-independent* precomputation phase. In particular, the parties can securely generate additive shares of many “Beaver triples” $(a, b, a \cdot b) \in \mathbb{F}^3$. Then, for each multiplication gate that needs to be computed in the online phase, the parties can run a fast information-theoretically secure multiplication protocol that consumes one Beaver triple and involves communicating just two elements of $\mathbb{F}$ per party. This model of secure computation with preprocessing forms the basis for modern MPC protocols due to the efficiency of the online phase. However, this preprocessing paradigm only serves to push the inefficiency bottleneck of MPC to the offline phase that consists of generating many Beaver triples. We briefly survey the different techniques that have been developed in the last couple of decades for the efficient generation of Beaver triples in an MPC setting.

**Modern secure computation protocols.** The traditional approach for securely generating Beaver triples relies on Oblivious Transfers (OT) [Rab81, EGL82]: an $N$-party Beaver triple over $\mathbb{F}$ is generated by letting each *pair* of parties execute $\log |\mathbb{F}|$ oblivious transfers [Gil99], and thanks to OT *extension protocols* [Bea96, IKNP03], generating a large number of OTs requires only cheap symmetric-key operations. This OT-based approach is very competitive with a small number of parties, but becomes very inefficient with many parties. Specifically, because *each pair* of parties needs to perform OTs, the communication and computation costs are on the order of $\Omega(N^2)$, which quickly becomes impractical as $N$ grows large.

Over the past decade, the practicality of secure computation has increased tremendously [DPSZ12, KOS16, DNNR17, HOSS18a, KPR18, Kel20]. This is especially true in the setting of secure computation of *arithmetic circuits over large fields*. Starting with the celebrated SPDZ protocol [DPSZ12], a sequence of works has developed fast protocols that use Ring-LWE-based somewhat homomorphic encryption, or even linearly homomorphic encryption, to generate $m$ Beaver triples with only $O(m \cdot N)$ communication and computation per triple. These approaches significantly improve over the “naïve” $\Omega(m \cdot N^2)$ cost of the OT-based approach. Over sufficiently large fields (e.g., larger than $2^\lambda$), when generating many triples, state-of-the-art protocols such as Overdrive [KPR18] achieve very good concrete efficiency.

More recently, following the line of work on silent secure computation initiated in [BCGI18, BCG$^+$19b, BCG$^+$19a], Boyle et al. [BCG$^+$20b] have shown how to generate a large number $m$ of *pseudorandom* (as opposed to truly random) Beaver triples under the Ring-LPN assumption. Their approach uses $O(\log m \cdot N^2)$ communication, followed solely by *local* computation, with good concrete efficiency (the authors estimated a throughput of around $10^5$ triples per second on one core of a standard laptop). For sufficiently large values of $m$, this is highly competitive with Overdrive. However, both Overdrive and the existing PCG-based approach share a common restriction: they are only usable over large fields.

**Secure computation of Boolean circuits.** In contrast to the secure computation of arithmetic circuits over large fields, the fastest way to run $N$-party MPC protocols for Boolean circuits remains the “naïve” method of generating many pairwise OTs, at a cost of $\Omega(m \cdot N^2)$ bits for $m$ Beaver triples. This is in contrast to the *two-party* setting, where two-party Beaver triples can be generated very efficiently thanks to a recent line of work [BCGI18, BCG$^+$19a, BCG$^+$19b] on silent OT extension. In
silent OT extension, two parties can generate *m* Beaver triples using only *O*(log *m*) communication. The state-of-the-art protocols in this area [CRR21, BCG$^{+22}$, RRT23] achieve impressive throughputs of several million Beaver triples per second on one core of a standard laptop. Furthermore, the recent SoftSpoken OT extension protocol [Roy22] yields even faster OTs at the cost of increasing communication. For example, SoftSpoken can generate nearly 30M OT/s on localhost at the cost of increasing the communication to 64m bits to generate *m* Beaver triples; other communication/computation tradeoffs are possible [Roy22, Table 1].<fnref n="7" />

The situation, however, is much less satisfying for the setting of secure computation of Boolean circuits with a larger number of parties. Protocols such as SPDZ [DPSZ12] and Overdrive [KPR18] do not perform well when generating Beaver triples for Boolean circuits, even in the passive setting. This is due to the high overhead of embedding $\mathbb{F}_2$ in an extension field compatible with the number theoretic-transform used in efficient instantiations of the BGV encryption scheme [BGV14]. Furthermore, silent OT extension techniques build on Pseudorandom Correlation Generators (PCGs), which typically work only in the two-party setting [BCG$^{+19b}$]. To handle more parties, one needs the stronger notion of programmable PCG [BCG$^{+20b}$], which, informally, allows partially specifying parts of the generated correlation. Unfortunately, while efficient programmable PCGs over large fields were introduced in [BCG$^{+20b}$], building concretely efficient, programmable PCGs over $\mathbb{F}_2$ has remained elusive thus far, making *N*-party PCGs for $\mathbb{F}_2$ primarily of theoretical interest. The state-of-the-art is the recent work of Bombar et al. [BCCD23], which generates Beaver triples over any field $\mathbb{F}_q$ with $q \ge 3$. However, Bombar et al. [BCCD23] leave analyzing the concrete efficiency for future work.

In light of this state of affairs, to the best of our knowledge, the current most efficient approach for *N*-party secure computation of Boolean circuits remains the classical OT-based approach. In a little more detail, to generate each Beaver triple, each party $P_i$ samples a random pair $(a_i, b_i)$ of bits, and each pair $(P_i, P_j)$ of parties executes two oblivious transfer protocols to generate additive shares of $a_i b_j$ and $a_j b_i$. Then, all parties aggregate their shares to obtain shares of $\sum_{i,j} a_i b_j = (\sum_i a_i) \cdot (\sum_j b_j)$. When generating *m* Beaver triples, this approach requires $N \cdot (N-1) \cdot m$ oblivious transfers in total (to be compared with the $O(N^2 \cdot \log m)$ communication of [BCG$^{+20b}$], or the $O(N \cdot m)$ communication of Overdrive [KPR18], for the case of arithmetic circuits over large fields). While there has been tremendous progress in constructing efficient OT protocols [IKNP03, Roy22], even using silent OT extension (which has the lower communication overhead) requires $3N \cdot (N-1) \cdot m$ bits of communication (ignoring some $o(m)$ terms). Using SoftSpoken OT [Roy22] instead, which appears to be the most computationally efficient solution, and setting the “communication/computation tradeoff” parameter $k$ to $k=5$, the communication increases to $32N \cdot (N-1) \cdot m$ bits. When the number of parties grows, this soon becomes very inefficient.<fnref n="8" />

## 1.1 Our focus and contributions

In this paper, we focus on secure computation of general Boolean circuits with multiple parties in the semi-honest setting. Our main contribution is $\mathbb{F}_4$OLEAGE, a novel $\mathbb{F}_4$-OLE-based protocol for secure computation in the preprocessing model that significantly outperforms the state-of-the-art approach in both the two-party and multi-party setting. In particular, $\mathbb{F}_4$OLEAGE enjoys much lower communication in the preprocessing phase than all known alternatives and has a very low computational overhead. We expect $\mathbb{F}_4$OLEAGE to be the fastest alternative for large enough circuits on almost any realistic network setting, for any number of parties between two and several hundred. $\mathbb{F}_4$OLEAGE builds upon recent results constructing efficient PCGs and introduces several protocol-level, algorithmic-level, and implementation-level optimizations to make these PCG constructions blazing fast (see Section 7 for a performance evaluation).

In the two-party setting ($N = 2$), $\mathbb{F}_4$OLEAGE enjoys a silent preprocessing (generating *m* multiplication triples requires $O(\log m)$ communication), and significantly outperforms all previous silent protocols. In particular, our implementation generates around 12.3 million Beaver triples per second on one core of an Amazon c5.metal server. Compare this to the state-of-the-art silent OT protocol RRT [RRT23] which generates 3.4 million Beaver triples per second with the same setup. This

<footnote n="7">⁷ Note that we need two calls to the OT functionality to generate one Beaver triple.</footnote>

<footnote n="8">⁸ For a very large number of parties, the linear scaling in *N* of Overdrive should become favorable. However, after private communication with the authors of Overdrive, the break-even point for communication seems to happen only for values of *N* in the range of 400+, due to the high overhead of using BGV and embedding $\mathbb{F}_2$ elements.</footnote>
makes RRT more than 3.5 times slower compared to $\mathbb{F}_4$OLEAGE. The fastest non-silent OT protocol, SoftSpoken OT, generates around 26 million multiplication triples per second on localhost in its fastest regime (using $k = 2$ [Roy22, Table 1]), while requiring around $128 \cdot m$ bits of total communication. However, while our approach does achieve a blazing-fast throughput, it has some limitations. In particular, the preprocessing phase of $\mathbb{F}_4$OLEAGE requires more rounds (16 rounds instead of 3 for generating 26M triples compared to [Roy22]). Additionally, our seed size is roughly 130× larger compared to [RRT23], and 2× larger compared to [BCG$^{+}$20b]. This makes $\mathbb{F}_4$OLEAGE less suitable for generating a small number of triples. Eventually, our protocols are tailored to the generation of multiplication triples over $\mathbb{F}_2$ in the semi-honest setting: their efficiency scales less favorably in other settings, such as generating string OTs or authenticated triples.

**In the multi-party setting** ($N > 2$), $\mathbb{F}_4$OLEAGE achieves almost-silent preprocessing: to securely compute a circuit with $m$ AND gates, following a silent phase with $O(N^2 \cdot \log m)$ communication, our preprocessing phase requires a single broadcast of $N \cdot m$ bits (one bit per AND gate and per party), and the online phase is the standard GMW protocol. As $N$ grows, this represents a drastic reduction in communication compared to the $\sim 3 \cdot N^2 m$ communication obtained when using silent OT extension, or the $\sim 32 \cdot N^2 m$ communication obtained with SoftSpoken OT, while remaining highly competitive in terms of computation.

**Comparison with the state of the art.** In Table 1, we provide a comparison between $\mathbb{F}_4$OLEAGE, SoftSpoken, and RRT, for $N = 10$ and $N = 2$ parties. In the multiparty setting, due to the very low bandwidth requirement of $\mathbb{F}_4$OLEAGE, we observe that computation is systematically the bottleneck when evaluated on one core of a commodity server. This indicates that $\mathbb{F}_4$OLEAGE is likely to stand out even more whenever more computational power is available, e.g., when evaluated in parallel on multiple cores.

The numbers in Table 1 have been computed using the running time $T$ measured for generating $3^{16}$ OLEs (Table 5, using the noise parameter $t = 27$ and $c = 3$) on one core of AWS c5.metal, and estimating the per-party cost to generate $10^9$ N-party Beaver triples as $2 \cdot (N - 1) \cdot T \cdot (10^9/3^{16})$. When $N = 2$, the cost is estimated as $T \cdot (10^9/3^{16})$, accounting for the factor-2 saving tailored to the 2-party setting. For communication, we computed an estimate of $C = 13MB$ of communication for our distributed protocol for generating a seed for $3^{18}$ OLEs. While one could in principle directly generate a seed that stretches to $10^9$ OLEs, this would significantly slow down the computation as the $10^9$ OLEs must be expanded all at once, and would not fit in memory. Hence, we estimate the communication as $2 \cdot (N-1) \cdot (3^{18}/10^9) \cdot C$ for generating $10^9$ N-party Beaver triples (as $3^{18}$ OLEs is the maximum expansion size we could fit in the memory), and an additional $10^9$ bits of communication per party (in the setting $N > 2$).

**Security.** The security of $\mathbb{F}_4$OLEAGE relies on the Quasi-Abelian Syndrome Decoding (QA-SD) assumption, a variant of the syndrome decoding assumption that was recently introduced in [BCCD23]. QA-SD is a generalization of the standard quasi-cyclic syndrome decoding assumption (used in many previous works [ABD$^{+}$16, AMBD$^{+}$18, BCG$^{+}$19a, AAB$^{+}$22b]) which was shown to asymptotically resist all known attacks against LPN and syndrome decoding in [BCCD23]. As a contribution of independent interest, we complement their preliminary analysis with thorough concrete cryptanalysis of the security of QA-SD against all state-of-the-art attacks. Our analysis covers in full detail the distribution of the noisy coordinates under folding attacks and the cost of attacking folded QA-SD instances using tailored Information Set Decoding (ISD) algorithms over $\mathbb{F}_4$. We include the SageMath script used to select our parameters from this analysis. As a byproduct, our precise analysis yields an attack undermining the claimed security of the parameters from [BCCD23]. Specifically, with our attack and a set of parameters $c = 4, t = 16$ (see Section 6.4.1 for details), [BCCD23] can only achieve a security level of 118 bits instead of 128 bits. This could probably be improved.

**Implementation.** We provide an open-source prototype implementation of our PCG construction in C. Our implementation is covered in detail in Section 7. It includes, in particular, a new implementation of distributed point functions that work with a ternary input domain (providing faster evaluation at a slightly increased key size), and optimized FFT over $\mathbb{F}_4$. We cover all these contributions in more detail in Section 2.
<table><caption>**Table 1:** Comparison of state-of-the-art protocols to generate N-party Beaver triples over $\mathbb{F}_2$ for $N = 10$ and $N = 2$ parties. The `localhost` column reports the runtimes (ignoring communication) for generating $10^9$ triples. All protocols run on one core of AWS `c5.metal` (3.4GHz CPU); all runtimes averaged across ten trials. “Communication” denotes the number of bits communicated per party for $10^9$ triples. LAN and WAN refer to the theoretical time required to generate $10^9$ triples over a 1 Gbps and 100 Mbps network respectively, with respective delays 1ms and 40ms. Numbers in **bold red** indicate that the bottleneck cost is the local computation. *Maximum theoretical throughput with more computational power (e.g., using multiple cores). Since each party computes $2 \cdot (N - 1)$ expansions for the PCG in parallel for an N-party Beaver triple, the running time is divided by C when using C cores whenever $C \le 2 \cdot (N - 1)$.</caption><thead><tr><th></th><th>Communication</th><th>localhost</th><th>LAN</th><th>WAN</th></tr></thead><tbody><tr><td colspan="5"><strong>Multi-party setting (N = 10)</strong></td></tr><tr><td>SoftSpoken (k = 2)</td><td>134 GB</td><td>342s</td><td>1192s</td><td>12207s</td></tr><tr><td>SoftSpoken (k = 4)</td><td>67 GB</td><td>405s</td><td>596s</td><td>6104s</td></tr><tr><td>SoftSpoken (k = 8)</td><td>34 GB</td><td>1900s</td><td><span style="color:red;">1900s</span></td><td>3052s</td></tr><tr><td></td><td></td><td></td><td>*298s</td><td></td></tr><tr><td>RRT</td><td>6.3 GB</td><td>2619s</td><td><span style="color:red;">2619s</span></td><td><span style="color:red;">2619s</span></td></tr><tr><td></td><td></td><td></td><td>*50.3s</td><td>*515s</td></tr><tr><td><span style="color:yellow;">F<sub>4</sub>OLEAGE</span></td><td>0.7 GB</td><td>1463s</td><td><span style="color:red;">1463s</span></td><td><span style="color:red;">1463s</span></td></tr><tr><td></td><td></td><td></td><td>*5.6s</td><td>*57.9s</td></tr><tr><td colspan="5"><strong>Two-party setting (N = 2)</strong></td></tr><tr><td>SoftSpoken (k = 2)</td><td>15 GB</td><td>38s</td><td>119s</td><td>1221s</td></tr><tr><td>SoftSpoken (k = 4)</td><td>7.5 GB</td><td>45s</td><td>60s</td><td>610s</td></tr><tr><td>SoftSpoken (k = 8)</td><td>3.7 GB</td><td>211s</td><td><span style="color:red;">211s</span></td><td><span style="color:red;">211s</span></td></tr><tr><td>RRT</td><td>258 KB</td><td>292s</td><td><span style="color:red;">292s</span></td><td><span style="color:red;">292s</span></td></tr><tr><td><span style="color:yellow;">F<sub>4</sub>OLEAGE</span></td><td>33.5 MB</td><td>81s</td><td><span style="color:red;">81s</span></td><td><span style="color:red;">81s</span></td></tr></tbody></table>

## 1.2 Organization

We provide a detailed technical overview of our results in Section 2. We introduce necessary preliminaries in Section 3, and describe our optimized PCG for OLEs over $\mathbb{F}_4$ in Section 4. In Section 5, we describe our distributed seed generation protocol. In Section 6, we describe our cryptanalysis of the QA-SD assumption and our parameter selection algorithm. In Section 7, we report on our implementation and evaluate the performance of our scheme.

**Appendices.** We defer most of the technical details to the appendices. Appendix A contains additional preliminaries on PCGs. Appendix B covers the formal statement of our information-theoretic MPC protocols given access to a functionality for $\mathbb{F}_4$-OLEs.

The full technical details of our analysis are provided in C. Eventually, Appendix D covers an even faster PCG for generating OLEs using Cuckoo hashing, suitable in contexts where a trusted entity generates and distributes the PCG shares, and Appendix E contains all deferred proofs.

## 2 Technical Overview

In this section, we provide a detailed description of our results and the main technical ideas underlying them. In Section 2.1, we provide background on secure multi-party computation realized from PCGs for OLE correlations. In Section 2.2 we describe the PCG construction of [BCCD23], which forms the basis for our preprocessing protocol. In Section 2.3, we describe our idea for converting $\mathbb{F}_4$ triples into $\mathbb{F}_2$ triples, which we tailor to the two-party case in Section 2.4. In Section 2.5, we describe our optimized PCG construction. In Section 2.6, we explain how we can obtain an efficient distributed seed generation protocol for our PCG construction. Finally, in Section 2.7, we overview our improved analysis of the QA-SD assumption.
**Notations.** Unless otherwise stated, an $N$-party linear secret shares of a value $v$ is denoted $\llbracket v \rrbracket = (\llbracket v \rrbracket_1, \dots, \llbracket v \rrbracket_N)$, where the $i$-th party obtains share $\llbracket v \rrbracket_i$. To disambiguate shares over $\mathbb{F}_4$ and shares over $\mathbb{F}_2$, we denote the field size with a superscript, i.e., $\llbracket \cdot \rrbracket^4$ and $\llbracket \cdot \rrbracket^2$, respectively. We identify $\mathbb{F}_4$ with $\mathbb{F}_2[X]/(X^2 + X + 1)$ and let $\theta$ denote a primitive root of $X^2 + X + 1$. Given an element $x \in \mathbb{F}_4$, we write $x(0)$ and $x(1)$ to denote the $\mathbb{F}_2$-coefficients of $x$ viewed as a polynomial over $\mathbb{F}_2[X]/(X^2+X+1)$; that is, $x = x(0) + \theta \cdot x(1)$. Additional notation can be found in Section 3.

## 2.1 Background: Secure MPC from PCGs

We start by describing prior approaches to realizing MPC in the preprocessing model from PCGs for OLE correlations.

**PCGs for the OLE correlation.** Our starting point is the template for generating $N$-party pseudorandom Beaver triples put forth by Boyle et al. [BCG$^{+20b}$]. At the heart of their framework is the use of a programmable PCG [BCG$^{+20b}$] for the OLE correlation. Concretely, a PCG for a target correlation $C$ (i.e., a distribution over pairs of strings) is a pair of algorithms (PCG.Gen, PCG.Eval) such that

- PCG.Gen generates a pair of succinct keys $(k_0, k_1)$ jointly encoding the target correlation, and

- PCG.Expand($\sigma, k_\sigma$) produces a string $R_\sigma$ corresponding to party $\sigma$'s secret share of the target correlation.

At a high level, a PCG must satisfy two properties: (1) pseudorandomness (or correctness) which states that $(R_0, R_1)$ must be indistinguishable from a random sample from $C$, and (2) security which states that $R_\sigma$ should appear random conditioned on satisfying the target correlation with $R_{1-\sigma} = \text{PCG.Expand}(1-\sigma, k_{1-\sigma})$ even given $k_{1-\sigma}$, for $\sigma \in \{0, 1\}$.

We focus on the OLE correlation over a finite field $\mathbb{F}$. For a length-$m$ OLE correlation, the string $R_0$ (which we call the sender output) is a list of $m$ tuples $(u_i, v_i)_{i \le m} \in (\mathbb{F}^2)^m$, and the string $R_1$ (which we call the receiver output) is a list of $m$ pairs $(x_i, w_i)_{i \le m} \in (\mathbb{F}^2)^m$ such that $w_i = u_i \cdot x_i + v_i$ for every $i$. Observe that, we can equivalently view $v_i$ and $-w_i$ as additive shares of $u_i \cdot x_i$, which we will denote as $\llbracket u_i \cdot x_i \rrbracket$. Informally, security for the OLE correlation amounts to showing that the following two properties hold:

- **Sender security:** from the viewpoint of the receiver (who has $k_1$ and generates $(x_i, w_i)$), the distribution of $(u_i, v_i)$ is computationally indistinguishable from the distribution of $(u_i, w_i - u_i \cdot x_i)$, for a uniformly random $u_i \leftarrow_R \mathbb{F}$.

- **Receiver security:** from the viewpoint of the sender (who has $k_0$), the distribution of each $x_i$ is computationally indistinguishable from a random field element.

**Going from OLE to Beaver triples.** As shown in [BCG$^{+19b}$], given a PCG for the OLE correlation (or a PCG for OLE for short), two parties can generate many pseudorandom Beaver triples over $\mathbb{F}$ as follows. First, the parties compute PCG.Gen via a two-party secure computation protocol to obtain PCG keys $k_0$ and $k_1$, respectively. Then, using PCG.Expand, the two parties locally obtain many correlations of the form $(u_i, \llbracket u_i x_i \rrbracket_0)$ and $(x_i, \llbracket u_i x_i \rrbracket_1)$, respectively. Given two such OLE correlations, where one party has $(u_0, u_1, \llbracket u_0 x_0 \rrbracket_0, \llbracket u_1 x_1 \rrbracket_0)$ and the other party has $(x_0, x_1, \llbracket u_0 x_0 \rrbracket_1, \llbracket u_1 x_1 \rrbracket_1)$, the two parties can locally derive one Beaver triple of the form $(\llbracket a \rrbracket, \llbracket b \rrbracket, \llbracket ab \rrbracket)$ by computing:

$$ \underbrace{(\llbracket u_0 + x_1 \rrbracket, \llbracket u_1 + x_0 \rrbracket, \llbracket u_0 x_0 + u_1 x_1 \rrbracket)}_{\llbracket a \rrbracket}, \underbrace{(u_0 u_1 + x_0 x_1)}_{\llbracket b \rrbracket} = \underbrace{(\llbracket (u_0 + x_1) \cdot (u_1 + x_0) \rrbracket)}_{\llbracket ab \rrbracket}. $$

In a little more detail, the sender computes their share of the Beaver triple as $(u_0, u_1, \llbracket u_0 x_0 \rrbracket_0 + \llbracket u_1 x_1 \rrbracket_0 + u_0 u_1)$ and the receiver computes their share as $(x_1, x_0, \llbracket u_0 x_0 \rrbracket_1 + \llbracket u_1 x_1 \rrbracket_1 + x_0 x_1)$. While this technique works well in the two-party setting, in the multi-party setting, things are not so simple.

**Going from two parties to many parties.** As first discussed by Boyle et al. [BCG$^{+20b}$], to generate $N$-party Beaver triples using a PCG for OLE, the parties need to ensure consistency among the OLE correlations generated by each pair of parties. That is, to generate one multiplication triple $(\llbracket a \rrbracket, \llbracket b \rrbracket, \llbracket ab \rrbracket)$, we need each pair of parties $(P_i, P_j)$ to hold respective values $(a_i, b_i)$ and $(a_j, b_j)$ (viewed as an individual share of $a$ and $b$), together with two-party shares $\llbracket a_i b_j \rrbracket$ and $\llbracket a_j b_i \rrbracket$. Then, all parties can combine their shares to get

$$ \llbracket (\sum_i a_i) \cdot (\sum_j b_j) \rrbracket = \sum_{i \neq j} \llbracket a_i b_j \rrbracket + \sum_i a_i b_i. $$
Observe that this requires party $P_i$ to have OLEs of the form $(a_i, [[a_i a_j]]_i)$, with every other party $P_j$ (who in turn has share $(a_j, [[a_i a_j]]_j)$), where $P_j$'s value $a_i$ remains the same across all OLEs. This is precisely what the notion of a programmable PCG for OLE achieves: it allows the parties to specify seeds $(\rho_0, \rho_1)$ such that PCG.Gen$(\rho_0, \rho_1)$ outputs keys $k_0, k_1$ that, informally speaking, have all the pseudorandom $(a_i, b_i)$ deterministically generated from the seeds $\rho_0$ and $\rho_1$ respectively (while still maintaining the required security properties). By reusing the same seeds across executions with multiple parties, the parties can ensure the required consistency across their outputs.

## 2.2 Constructing programmable PCGs

In addition to defining the notion of programmable PCGs, the work of Boyle et al. [BCG+19b, BCG+20b] introduced a construction from a variant of the LPN assumption over rings. At a high level, the ring-LPN assumption they introduce states that $(a, as + e)$ is hard to distinguish from $(a, b)$, where $a, b$ are random polynomials from a suitable ring $\mathcal{R} = \mathbb{F}_q[X]/(P(X))$, where $P$ splits into $\deg(P)$ linear factors and $s, e$ are random sparse polynomials from $\mathcal{R}$. The construction of Boyle et al. proceeds by generating a single large pseudorandom OLE correlation over a polynomial ring $\mathcal{R} = \mathbb{F}_q[X]/(P(X))$, assuming the hardness of the ring-LPN assumption over $\mathcal{R}$. When $P$ splits into $D = \deg(P)$ linear factors, the Chinese Remainder Theorem makes it possible to convert this large OLE correlation over $\mathcal{R}$ into $D$ OLE correlations over $\mathbb{F}_q$ (by reducing it modulo each of the factors of $P$). Unfortunately, the condition that $P$ splits requires $|\mathbb{F}_q| \ge D$, which restricts the construction to only work over large fields. This makes the resulting OLE correlations only suitable for generating Beaver triples over $\mathbb{F}_q$, which limits their applications. Moreover, other existing efficient (non-PCG-based) protocols for generating Beaver triples are also restricted to large fields [DPSZ12, KPR18]. However, for the Boolean circuit case, the state-of-the-art remains the basic OT-based approach originally proposed in the GMW protocol.

**A programmable PCG for $\mathbb{F}_4$-OLE.** The large-field restriction of the Boyle et al.'s PCG construction was recently overcome by Bombar et al. [BCCD23]. At a high-level, the authors of [BCCD23] manage to replace the polynomial ring $\mathcal{R}$ by a suitable Abelian group algebra $\mathbb{F}[\mathcal{G}]$ (that is, the set of formal sums $\sum_{g \in \mathcal{G}} a_g g$ for $a_g \in \mathbb{F}$, where $\mathcal{G}$ is an Abelian group; endowed with the convolution product), which identifies to some ring of multivariate polynomials. Moreover, they show that an appropriate choice of Abelian group algebra can simultaneously satisfy the following properties, for almost every choice of finite field $\mathbb{F}$:

1. $\mathbb{F}[\mathcal{G}]$ is isomorphic to many copies of $\mathbb{F}$ (note that this property is necessary to convert an OLE correlation over $\mathbb{F}[\mathcal{G}]$ into many OLEs over $\mathbb{F}$),

2. The assumption that $(a, as + e)$ is indistinguishable from random over $\mathbb{F}[\mathcal{G}] \times \mathbb{F}[\mathcal{G}]$, with $a \stackrel{\$}{\leftarrow} \mathbb{F}[\mathcal{G}]$ and $(s, e)$ two random sparse elements of $\mathbb{F}[\mathcal{G}]$ (with respect to the canonical notion of sparsity over the group algebra, i.e., sparse formal sums $\sum_{g \in \mathcal{G}} a_g g$) is a plausible assumption,

3. Operations over $\mathbb{F}[\mathcal{G}]$ can be computed efficiently using a Fast Fourier Transform (FFT) algorithm [Obe07, BCCD23].

The second property is a new variant of the syndrome decoding (or LPN) assumption which the authors called *Quasi-Abelian Syndrome Decoding*. It naturally extends to a "module"-variant, i.e., the indistinguishability of pairs $(\mathbf{a}, \langle\mathbf{a}, \mathbf{s}\rangle + e)$ where $\mathbf{s}$ and $e$ are drawn from a sparse distribution, and generalizes both the quasi-cyclic syndrome decoding (when $\mathcal{G}$ is a cyclic group), and the LPN or syndrome decoding assumption (when $\mathcal{G} = \{1\}$). The work of Bombar et al. [BCCD23] also provides extensive support for this assumption by showing that it resists all linear attacks, a class of attacks capturing the most known attacks on the LPN assumption and its variants, and proposes a set of parameters resisting all concrete attacks known at that time. The combination of these three properties allowed them to build an efficient programmable PCG for OLEs over $\mathbb{F}$.

Despite the progress made in [BCCD23], their programmable PCG construction is limited in that it applies only to generating OLE correlations over all finite fields $\mathbb{F}$ except for $\mathbb{F}_2$. This stems from the fact that there does not exist any group $\mathcal{G}$ such that $\mathbb{F}_2[\mathcal{G}]$ is isomorphic to $\mathbb{F}_2^n$ for $n > 1$ (see [BCCD23, Theorem 47]). In contrast, the case of $\mathbb{F}_2$, is precisely the case that we are interested in when considering Boolean circuits, which require generating Beaver triples over $\mathbb{F}_2$.

Additionally, the concrete efficiency of an FFT computed over the group algebra remains unclear, since Bombar et al. left estimating the performance of FFTs on $\mathbb{F}[\mathcal{G}]$ for future work. As such,
the concrete efficiency of their programmable PCG construction is unknown, making it difficult to determine whether or not it is sufficiently efficient to be applied in practical applications (all other components of their construction consist of standard tools used in the PCG literature, which are known to have concretely efficient implementations).

**Our contribution.** Looking ahead, our main contribution is to build upon the work of Bombar et al. through a number of simple yet powerful observations that allow us to arrive at an efficient PCG for Beaver triples, suitable for use in secure multi-party computation of Boolean circuits.

- First, we show that we can use their programmable PCG for generating OLEs over $\mathbb{F}_4$ to generate multiplication triples over $\mathbb{F}_2$, sidestepping the “$\mathbb{F}_2$ barrier” of their PCG construction, at the cost of a single bit of communication per triple and per party in the preprocessing phase, or even without any communication when $N = 2$.

- Second, we introduce a number of concrete optimizations to the PCG construction of Bombar et al. [BCCD23] that are tailored to the special case of $\mathbb{F} = \mathbb{F}_4$, which gives us a very efficient programmable PCG over $\mathbb{F}_4$. Compared with the fastest previous programmable PCGs of [BCG$^+$20b], our optimized implementation shows that our construction is two orders of magnitude faster.

- Third, we give a much more in-depth cryptanalysis of the QA-SD assumption, closely analyzing all known attacks in the literature, and showing that the set of parameters proposed in [BCCD23] should be reduced by at least 10 bits. To facilitate future cryptanalysis of the QA-SD assumption, in Section 6 we carefully overview all known attacks and assumptions, and provide a script for automatically calculating parameters.

In the next few subsections, we provide more details on the above contributions.

## 2.3 $\mathbb{F}_2$-triples from $\mathbb{F}_4$-triples

Since $\mathbb{F}_4$ is an extension field of $\mathbb{F}_2$, a Boolean circuit can be viewed as an $\mathbb{F}_4$-arithmetic circuit. Hence, using an OLE correlation over $\mathbb{F}_4$ to construct $N$-party Beaver triples over $\mathbb{F}_4$ directly yields an MPC protocol for Boolean circuits in the preprocessing model via the GMW template [GMW87]. Unfortunately, compared to using $\mathbb{F}_2$-Beaver triples, the communication in the online phase is doubled, because each party has to send two elements of $\mathbb{F}_4$ per AND gate, hence 4 bits instead of 2 with GMW.

Our core observation is that one can make much better use of these $N$-party multiplication triples over $\mathbb{F}_4$: we show how to convert an $\mathbb{F}_4$-multiplication triple into an $\mathbb{F}_2$-multiplication triple using a single bit of communication per party. Once converted into $\mathbb{F}_2$-triples, these triples can be used within the standard GMW protocol that communicates two bits per party and per AND gate in the online phase. To explain the observation, let ($\llbracket a \rrbracket^4, \llbracket b \rrbracket^4, \llbracket ab \rrbracket^4$) be a Beaver triple over $\mathbb{F}_4$. Writing $x = x(0) + \theta \cdot x(1)$ for any $x \in \mathbb{F}_4$, with $\theta$ a root of the polynomial $X^2 + X + 1$ (hence $\theta^2 = \theta + 1$), we have

$$ 
\begin{aligned}
a \cdot b &= a(0)b(0) + a(1)b(1) + \theta \cdot (a(0)b(1) + a(1)b(0) + a(1)b(1)) \\
&\implies (ab)(0) = a(0)b(0) + a(1)b(1).
\end{aligned}
$$

Now, assume that the parties reconstruct $b(1)$, which can be done using a single bit of communication per party from their shares $\llbracket b \rrbracket^4 = \llbracket b(0) \rrbracket^2 + \theta \cdot \llbracket b(1) \rrbracket^2$. Given $b(1)$, the parties can locally compute shares of $a(0)b(0)$ as follows:

$$ \llbracket a(0)b(0) \rrbracket^2 = \llbracket ab \rrbracket^4(0) + b(1) \cdot \llbracket a \rrbracket^4(1). $$

Therefore, all parties output $(\llbracket a(0) \rrbracket^2, \llbracket b(0) \rrbracket^2, \llbracket ab \rrbracket^4(0) + b(1) \cdot \llbracket a \rrbracket^4(1))$, which forms a valid Beaver triple over $\mathbb{F}_2$. Security is straightforward: the only communication between the parties is the reconstruction of $b(1)$, which is a uniformly random bit independent of $a(0), b(0)$. From there, one immediately gets an improved protocol in the preprocessing model: in the preprocessing phase, given one $\mathbb{F}_4$-Beaver triple for each AND gate of the circuit, the parties broadcast one bit per gate, and then locally derive the $\mathbb{F}_2$-Beaver triples. In the online phase, the parties run the standard GMW protocol.
## 2.4 An improved protocol from $\mathbb{F}_4$-OLEs for $N = 2$

In the setting of $N = 2$ parties, we obtain a much more efficient alternative: we observe that two parties can directly convert a single OLE over $\mathbb{F}_4$ into a Beaver triple over $\mathbb{F}_2$. (In contrast, recall that the standard approach requires two oblivious transfers for each triple.) We 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 ab \rrbracket_A^4(0) + \llbracket ab \rrbracket_B^4(0) + \theta \cdot (\llbracket ab \rrbracket_A^4(1) + \llbracket ab \rrbracket_B^4(1)) \\
&= (a(0)b(0) + a(1)b(1)) + \theta \cdot (a(0)b(1) + a(1)b(0) + a(1)b(1)),
\end{aligned}
$$

where $\theta$ is the primitive root of $X^2 + X + 1$. Considering only the $(a \cdot b)(0)$ term from the above equation (i.e., the parts not multiplied by $\theta$), we get that

$$ (a \cdot b)(0) = \llbracket ab \rrbracket_A^4(0) + \llbracket ab \rrbracket_B^4(0) = a(0)b(0) + a(1)b(1), \text{ and therefore,} $$

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

Above, the values $a(0)a(1) + \llbracket ab \rrbracket_A^4(0)$ (known by Alice) and $b(0)b(1) + \llbracket ab \rrbracket_B^4(0)$ (known by Bob) form additive shares of the product $(a(0)+b(1)) \cdot (a(1)+b(0))$, which Alice and Bob hold additive shares of. It is also easy to check that if the input is a random $\mathbb{F}_4$-OLE, the output is a random multiplication triple over $\mathbb{F}_2$. Therefore, following the local conversion procedure outlined above, Alice and Bob can transform a random $\mathbb{F}_4$-OLE instance into a random Beaver over $\mathbb{F}_2$ without having to communicate.

## 2.5 A fast programmable PCG for $\mathbb{F}_4$-OLEs

In light of the above observations, the only missing piece of the puzzle is an efficient way of generating a large number of $\mathbb{F}_4$-OLEs. In the $N > 2$ setting, if the OLEs are additionally programmable, the parties can afterward locally convert $N \cdot (N - 1) \mathbb{F}_4$-OLE instances into an $\mathbb{F}_4$-Beaver triples.

Here, we build on the recent general programmable PCG construction of [BCCD23]. Because we are targeting OLEs over $\mathbb{F}_4$, we set the group $\mathbb{G}$ to $\mathbb{F}_3^n$, and the underlying group algebra becomes isomorphic to

$$ \mathbb{F}_4[\mathbb{G}] \simeq \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1) \simeq \mathbb{F}_4^{3n}. $$

Before delving into the optimizations we develop for their construction, we describe the high-level ideas and main building blocks behind the PCG construction of Bombar et al. [BCCD23] when instantiated over $\mathbb{F}_4$.

**The PCG construction of Bombar et al.** As with previous constructions of PCGs [BCGI18, BCG$^{+19b}$], the construction of Bombar et al. uses Distributed Point Functions (DPF) [GI14, BGI15, BGI16] as a core building block. Informally, a DPF with domain $[D]$ allows a dealer to succinctly secret share a unit vector over $[D]$. The most efficient DPFs have shares of size roughly $\lambda \cdot \log D$ [BGI16], for some security parameter $\lambda$, and the cost of decompressing the shares is dominated by $D$ calls to a length-doubling pseudorandom generator.

*Public parameters.* For a fixed compression factor $c$ (typically a small constant, e.g., $c = 3$) and noise parameter $t$ (e.g., $t = 27$), the public parameters contain a length-$c$ vector $\mathbf{a}$ of $n$-variate polynomials.

*Distributing PCG seeds.* In their construction, PCG.Gen does the following:

- it samples two length-$c$ vectors $(\mathbf{e}_0, \mathbf{e}_1)$ of $t$-sparse polynomials over $\mathbb{F}_4[\mathbb{G}]$;

- outputs keys $(\mathbf{k}_0, \mathbf{k}_1)$ that contain $\mathbf{e}_0$ and $\mathbf{e}_1$, respectively, as well as succinct shares of $\mathbf{e}_0 \otimes \mathbf{e}_1$, encoded using a DPF.

The tensor product $\mathbf{e}_0 \otimes \mathbf{e}_1$ contains $c^2$ polynomials, each with at most $t^2$ nonzero coordinates. Hence, the vectors of coefficients of all polynomials in $\mathbf{e}_0 \otimes \mathbf{e}_1$ can be succinctly secret shared using $(ct)^2$ DPFs with domain $3^n$, which requires roughly $(ct)^2 \cdot \lambda \log(3^n)$ bits using the state-of-the-art DPF constructions [BGI15, BGI16].$^9$

*Generating correlations.* To output a vector of OLE correlations, PCG.Eval proceeds as follows for party 0 (the evaluation for party 1 is similar):

<footnote>$^9$ Using noise vector with a regular structure, the domain size of the DPFs can be reduced to $3^n/t$.</footnote>
- evaluate all the DPFs to obtain a secret share of $[[e_0 \otimes e_1]]_0$;

- set $x_0 \leftarrow \langle \mathbf{a}, e_0 \rangle$ and $z_0 \leftarrow \langle \mathbf{a} \otimes \mathbf{a}, [[e_0 \otimes e_1]]_0 \rangle$; ▷ Note: $z_0 = [[\langle \mathbf{a} \otimes \mathbf{a}, e_0 \otimes e_1 \rangle]]_0$

- using the isomorphism $\mathbb{F}_4[\mathbb{G}] \simeq \mathbb{F}_4^{3^n}$, project $(x_0, z_0) \in \mathbb{F}_4[\mathbb{G}]^2$ onto $3^n$ pairs $(x_0^i, z_0^i)$ of elements of $\mathbb{F}_4$.

Above, the projection amounts to evaluating the multivariate polynomials over $\mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$ on the $3^n$ tuples of elements of $(\mathbb{F}_4^\times)^n$. Observe that

$$z_0 + z_1 = \langle \mathbf{a} \otimes \mathbf{a}, [[e_0 \otimes e_1]]_0 \rangle + \langle \mathbf{a} \otimes \mathbf{a}, [[e_0 \otimes e_1]]_1 \rangle \\ = \langle \mathbf{a} \otimes \mathbf{a}, e_0 \otimes e_1 \rangle = \langle \mathbf{a}, e_0 \rangle \cdot \langle \mathbf{a}, e_1 \rangle = x_0 \cdot x_1.$$

Since the isomorphism preserves additions and multiplications, it follows that all pairs $(x_0^i, z_0^i)$ and $(x_1^i, z_1^i)$ form OLEs over $\mathbb{F}_4$. Security boils down to the Quasi-Abelian Syndrome Decoding assumption (QA-SD) [BCCD23], which states (informally) that given the random vector $\mathbf{a}$, the element $\langle \mathbf{a}, \mathbf{e} \rangle + e_0$ (where $(e_0, \mathbf{e})$ are formed by random sparse polynomials) is indistinguishable from a random element of $\mathbb{F}_4[\mathbb{G}]$.

We now describe several observations that we make about their construction and how these observations allow us to significantly optimize the concrete efficiency of the PCG. While simple in retrospect, these observations allow us to turn a theoretical construction into a concretely efficient PCG for $\mathbb{F}_4$-OLEs (see Section 7 for our implementation and evaluation).

**Early termination.** The DPF construction of [BGI16] generates shares of a unit vector using a construction $\hat{a}$ la GGM [GGM19], generating a full binary tree of PRG evaluations starting from a root seed. The children of each node are computed by evaluating a length-doubling PRG on the node, and then adding some correction words. In this construction, each leaf of the tree is a $\lambda$-bit string (where typically $\lambda = 128$). In contrast, we wish to share unit vectors over $\mathbb{F}_4$. Hence, we can apply the *early termination* technique from [BGI16] that shaves several levels of PRG expansions. With early termination, to obtain a $D = 2^d$-long vector over $\mathbb{F}_4$, we use a tree of depth $2D/\lambda = 2^{d-6}$ (using $\lambda = 128$) and parse each of the 128-bit leaves as a 64-tuple of $\mathbb{F}_4$-elements. This immediately yields a 64-fold runtime improvement for each of the DPFs required in the PCG construction.

We note that while other constructions share a similar blueprint to the construction of Bombar et al., and in particular also require evaluating many DPFs under-the-hood, this early termination technique does not apply to them. The reason is that in silent OT extension protocols [BCG$^{+}$19a, BCG$^{+}$19b, CRR21, BCG$^{+}$22, RRT23], the DPFs are used to compress secret shares of $\Delta \cdot \mathbf{e}$, where $\Delta$ is a 128-bit element from a suitable extension field, and in the previous PCG construction of [BCG$^{+}$20b], the OLEs can only be generated over a large field $\mathbb{F}$ (chosen equal to $|\mathbb{F}| \approx 2^\lambda$ in their implementation). As such, early termination optimization appears to apply exclusively when specializing the PCG of [BCCD23] to work over small fields.

**Using a single multi-evaluation step.** Computing $\langle \mathbf{a} \otimes \mathbf{a}, [[e_0 \otimes e_1]]_b \rangle$ (for $b = 0, 1$) requires $c^2$ polynomial multiplications. Fast polynomial multiplication is typically done using a multi-evaluation (i.e., an FFT) followed by a local product and an interpolation (i.e., an inverse FFT).

The above produces a single OLE over $\mathbb{F}_4[\mathbb{G}]$. When the end goal is to obtain OLEs over $\mathbb{F}_4$, the result is projected back onto $\mathbb{F}_4^n$ using a multi-evaluation. In this case, we show that we can reduce the sequence multi-evaluation $\rightarrow$ interpolation $\rightarrow$ multi-evaluation down to just a single multi-evaluation step. Concretely:

- Given that $\mathbf{a}$ is a random vector of polynomials (and part of the public parameters), it can directly be generated as $c$ random length-$3^n$ vectors over $\mathbb{F}_4^n$, corresponding to the vectors of the multi-evaluations of $\mathbf{a}$ over all $n$-tuples in $(\mathbb{F}_4^\times)^n$.

- The multi-evaluation of $\mathbf{a} \otimes \mathbf{a}$ can be computed once for all using pairwise products of elements of (the multi-evaluation of) $\mathbf{a}$, and included in the public parameters.

- Computing the multi-evaluation of $\langle \mathbf{a} \otimes \mathbf{a}, [[e_0 \otimes e_1]]_b \rangle$ amounts to computing the multi-evaluation of $[[e_0 \otimes e_1]]_b$ followed by component-wise inner products.

It follows that after expanding the shares $[[e_0 \otimes e_1]]_b$, the cost of PCG.Expand is then dominated by $c^2$ instances of a multi-evaluation (i.e., an FFT). However, upon slightly closer inspection, we observe that it actually suffices to compute $c(c+1)/2$ FFTs (since the terms $e_0^i e_1^j$ and $e_0^j e_1^i$ share the same “coefficient” $a_i a_j$ in $\langle \mathbf{a} \otimes \mathbf{a}, e_0 \otimes e_1 \rangle$, hence the FFT can be evaluated on terms $e_0^i e_1^j + e_0^j e_1^i$ directly).
**Blazing fast FFT.** Our next observation is that the FFT over the group algebra $\mathbb{F}_4[\mathbb{G}]$ is actually extremely efficient. Indeed, given a polynomial $P(X_1, \dots, X_n)$, one can rewrite $P$ as

$$P_0(X_1, \dots, X_{n-1}) + X_n P_1(X_1, \dots, X_{n-1}) + X_n^2 P_2(X_1, \dots, X_{n-1}).$$

Let us denote FFT$(P, n)$ the functionality that evaluates $P$ on all $n$-tuples over $(\mathbb{F}_4^\times)^n$, and outputs a multi-evaluation vector $\mathbf{v}$. By the above formula, computing FFT$(P, n)$ reduces to

- computing $\mathbf{v}_i \leftarrow \text{FFT}(P_i, n-1)$ for each $i \in \{0, 1, 2\}$, and

- setting $\mathbf{v} \leftarrow (\mathbf{v}_0 + \mathbf{v}_1 + \mathbf{v}_2) \parallel \mathbf{v}_0 + \theta\mathbf{v}_1 + (\theta+1)\mathbf{v}_2 \parallel \mathbf{v}_0 + (\theta+1)\mathbf{v}_1 + \theta\mathbf{v}_2$.

Denoting $C(n)$ the cost of running FFT$(P, n)$, we therefore have $C(n) = 3 \cdot C(n-1) + \ell \cdot 3^{n-1}$, where $\ell$ denotes the number of vector operations (naïvely, 6 additions of vectors and 4 scalar-vector products—but some additions and products can be reused). This yields a cost of $C(n) = n \cdot \ell \cdot 3^{n-1}$, where all operations are very fast: either additions of $\mathbb{F}_4$-vectors or multiplications by $\theta$. Looking ahead, our implementation and evaluation (Section 7) confirm that, even with the straightforward recursive algorithm, the FFT results in minimal overhead compared to the cost of the DPFs.$^{10}$

**Stepping back: comparison with silent OT extension.** To give an intuition about the efficiency of this construction, we provide a brief comparison with constructions of silent OT extension. In short, to get (say) $3^n$ OTs, these constructions run $c \cdot t$ DPFs on a domain of size $3^n/t$, followed by a multiplication with a compressive mapping. In the most efficient silent OT extension protocol to date [RRT23], this compressive mapping requires computing $21 \cdot c \cdot 3^n$ XORs, followed by $3^n$ XORs of random size-21 subsets of the bits of the resulting vector. Due to the overhead of many random memory accesses, the cost of computing this mapping dominates the overall runtime.

In contrast, we need $(c \cdot t)^2$ DPFs with domain size $3^n/t$, but get a $64 \times$ speedup from the early termination optimization. The cost of our DPFs should be essentially on par with that of [RRT23]. However, the FFT cost in our construction is largely dominated by the cost of the DPFs. Therefore, we expect (and this is confirmed by our implementation) that this PCG should produce $\mathbb{F}_4$-OLEs at a much faster rate compared with the rate at which [RRT23] produces OTs. In the two-party setting, when the goal is to generate Beaver triples over $\mathbb{F}_2$, we get an additional $2 \times$ speedup from the technique of Section 2.4, as we generate one triple from one $\mathbb{F}_4$-OLE (whereas [RRT23] requires two OTs). We provide an optimized implementation of our scheme and evaluate how it compares to previous works in Section 7. Our implementation is about $6 \times$ faster than the state of the art [RRT23].

## 2.6 Distributed seed generation

So far, we have only discussed the cost of expanding the PCG keys $(k_0, k_1)$. To obtain a full-fledged secure computation protocol, we need an efficient way for the parties to securely evaluate PCG.Gen procedure in a distributed fashion. In the following, as in all previous works on PCGs [BCG+19a, BCG+19b, BCG+20b, BCG+20a, CRR21, BCG+22, BCCD23, CD23], we assume that the noise follows a regular distribution. That is, a noise vector $\mathbf{e}$ is a vector of $c$ polynomials $(e^1, \dots, e^c)$, where each polynomial $e^i$ is regular: its coordinates are divided into $t$ block of (approximately) equal length $3^n/t$, and it has a single nonzero coefficient in each block. For any integer $h$, let $[h]$ denote the set $\{1, \dots, h\}$. The previous work of [BCG+20b] outlined the following methodology to securely distribute PCG seeds for generating $D$ OLEs (in our context, $D = 3^n$):

- **Sampling the noise vectors.** Each party $P_b$ generates its noise vector $\mathbf{e}_b$ locally, by sampling $c$ $t$-sparse regular polynomials. We write $\mathbf{e}_b = (e_b^1, \dots, e_b^c)$. For each $i \in [c]$, we let $(\mathbf{p}_{b,1}^i, \dots, \mathbf{p}_{b,t}^i) \in [3^n/t]^t$ denote the $t$ positions of the nonzero entries in $e_b^i$, and $(v_{b,1}^i, \dots, v_{b,t}^i) \in \mathbb{F}_4^t$ denote the value of these nonzero coefficients.

- **Sharing the positions and values.** For every $i_0, i_1 \in [c]$, for every $j_0, j_1 \in [t]$, the parties run a distributed protocol with respective inputs $\mathbf{p}_{0,j_0}^{i_0}$ and $\mathbf{p}_{1,j_1}^{i_1}$ (i.e., the position of the $j_0$-th and $j_1$-th nonzero coefficients in $e_0^{i_0}$ and $e_1^{i_1}$, respectively) which securely computes bitwise shares of the $(j_0 + j_1)$-th nonzero coefficient of $e_0^{i_0} e_1^{i_1}$. In parallel, they also run a distributed protocol with respective inputs $v_{0,j_0}^{i_0}$ and $v_{1,j_1}^{i_1}$ (the corresponding values of the nonzero coefficients) and securely compute bitwise shares of $v_{0,j_0}^{i_0} \cdot v_{1,j_1}^{i_1}$ (the value of the $(j_0 + j_1)$-th nonzero coefficient of $e_0^{i_0} e_1^{i_1}$).

<footnote>$^{10}$ Our implementation also exploits vectorized operations to perform a batch of multiple FFTs for essentially the cost of one, which further reduces the impact of FFTs on the overall runtime.</footnote>
- **Distributing the DPF keys.** For every $i_0, i_1 \in [c]$, for every $j_0, j_1 \in [t]$, the parties run the Doerner-shelat protocol [Ds17] with their bitwise shares of the position and value to securely obtain DPF keys forming succinct shares of the point function $f_{\alpha,\beta}$ which evaluates to $\beta := v_{0,j_0}^{i_0} \cdot v_{1,j_1}^{i_1}$ on the index $\alpha$ of the $(j_0 + j_1)$-th nonzero coefficient of $e_0^{i_0} e_1^{i_1}$, and to 0 on all other inputs.

Communication-wise, the Doerner-shelat protocol requires $2 \cdot \log(D/t)$ oblivious transfers for each DPF, for a total of $2(ct)^2 \log(D/t)$ oblivious transfers. Distributing the shares of the coefficients $v_{0,j_0}^{i_0} \cdot v_{1,j_1}^{i_1}$ is relatively straightforward: it involves two OLEs over $\mathbb{F}_4$ for each of the $(ct^2)$ coefficients. As in [BCG$^+$20b], these OLEs can be obtained at a minimal cost by running the PCG in a “bootstrapping mode”: whenever two parties use the PCG to generate $D \mathbb{F}_4$-OLEs, they can instead use a marginally larger instance to generate $D + (ct)^2 \mathbb{F}_4$-OLE, and store the $(ct)^2$ extra OLEs for use in the next distributed PCG seed generation.

In the work of Boyle et al. [BCG$^+$20b], an important overhead comes from the $(ct)^2$ instances of a distributed protocol to generate bitwise shares of the noise positions: each such instance requires securely running a Boolean adder to compute, from the bit decomposition of $p_{0,j_0}^{i_0}$ and $p_{1,j_1}^{i_1}$, the bit decomposition of the position of the corresponding entry in $e_0^{i_0} e_1^{i_1}$. In the construction of [BCG$^+$20b], this contributes to a large portion of the (communication and computation) overhead of the seed distribution procedure: about half of the communication, computation, and rounds of the full protocol.

**An improved seed distribution from ternary DPFs.** We now introduce an optimization that removes the need to distribute shares of noise positions altogether by working directly in the ternary basis. Our improved protocol is tailored to the setting of noise vectors with components over $\mathbb{F}_4[\mathbb{G}] = \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$. Observe that every monomial over $\mathbb{F}_4[\mathbb{G}]$ can be written as $\mathbf{X}^\mathbf{p} := \prod_{i=1}^n X_i^{p_i}$, where $\mathbf{p} = (p_1, \dots, p_n) \in \mathbb{F}_3^n$. Therefore, we can uniquely identify the position of the coefficient $c_\mathbf{p}$ of a monomial $\mathbf{X}^\mathbf{p}$ with the $\mathbb{F}_3$-vector $\mathbf{p} \in \mathbb{F}_3^n$. Now, consider the product of two polynomials $e_0, e_1$ known by $P_0$ and $P_1$, respectively. Let $\mathbf{p}_0 \in \mathbb{F}_3^n$ be the position of a nonzero entry in $e_0$, and $\mathbf{p}_1 \in \mathbb{F}_3^n$ be the position of a nonzero entry in $e_1$. Then, the corresponding nonzero entry in $e_0 \cdot e_1$ is the coefficient of the monomial $\mathbf{X}^{P_0} \cdot \mathbf{X}^{P_1} = \mathbf{X}^{P_0+P_1 \bmod 3}$. That is, the corresponding nonzero position in $e_0 e_1$ is exactly $\mathbf{p}_0 + \mathbf{p}_1$ (where the sum is taken modulo 3). In other words, the two parties already hold shares of the noise position in $e_0 e_1$—but over the ternary basis!

Unfortunately, the Doerner-shelat protocol requires the parties to hold binary shares of the position, because its binary decomposition corresponds to the path from the root to the leaf in the (binary) GGM tree underlying the DPF construction of [BGI15, BGI16]. To remedy this situation, we modify the underlying DPF construction to use a ternary tree. That is, the full tree is obtained by computing the three children of a node by evaluating a length-tripling PRG $G: \{0,1\}^\lambda \to \{0,1\}^{3\lambda}$ on the node value. Adapting the DPF construction of [BGI15, BGI16] to this setting is relatively simple (though the security analysis becomes slightly more tedious, especially when adapting the Doerner-shelat protocol to work over a ternary basis), and requires increasing the number of correction words from 1 to 3 per level of the tree.<fnref n="11" /> With this change, the path to a leaf is given directly by the leaf position written as a $\mathbb{F}_3$-vector. To securely generate the keys of this modified DPF, we adapt the Doerner-shelat protocol. Our adaptation requires two 1-out-of-3 oblivious transfers per level (instead of two 1-out-of-2 OTs as in [Ds17]), for the $\log_3(D/t)$ levels of the ternary DPF tree. In summary, we obtain a distributed seed generation protocol with the following pros-and-cons when compared to the original approach of [BCG$^+$20b]:

+ The parties “natively” hold shares of the nonzero positions and do not have to run a secure protocol to compute them. In the protocol of Boyle et al. [BCG$^+$20b], this step required $2(ct)^2 \log(D/t)$ oblivious transfers in $\log(D/t)$ rounds (i.e., half of the total number of rounds and OTs).

- The modified Doerner-shelat requires $2(ct)^2 \log_3(D/t)$ 1-out-of-3 OTs of 3λ-bit strings instead of $2(ct)^2 \log_2(D/t)$ 1-out-of-2 OTs of 2λ-bit strings, which represents slightly more communication and computation.

- Due to the use of a ternary DPF, which has more correction words, the PCG seed size is slightly increased, by a factor ≈ 1.5.

<footnote n="11">¹¹ Unfortunately, in the ternary tree construction, using the optimization described in [BGI16] for removing one extra correction word does not immediately apply. We leave open the problem of finding a similar optimization in the ternary case.</footnote>
+ Expanding the PCG seeds becomes about 20% faster because the total number of PRG evaluations is reduced when computing a full ternary tree compared to a full binary tree with a similar number of leaves.

+ The number of rounds of the Doerner-shelat protocol is also reduced, from $log_2(D/t)$ to $log_3(D/t)$, by having a more shallow tree.

## 2.7 Concrete cryptanalysis of $\mathbb{F}_4$OLEAGE

The security of $\mathbb{F}_4$OLEAGE is based on the QA-SD assumption, as explained in Section 2.2. To derive our parameters, we conduct a precise analysis of attacks on QA-SD(c, t, $\mathbb{G}$) over the finite field $\mathbb{F}_q$. The goal of the QA-SD assumption is to distinguish pairs $(a, \langle a, e \rangle + e_0) = ((a_1, \dots, a_{c-1}), e_0 + a_1 e_1 + \dots + a_{c-1} e_{c-1})$ from random elements of $\mathbb{F}_q[\mathbb{G}]^c$ where $a_i \leftarrow \mathbb{F}_q[\mathbb{G}]$, and $e_i$ are sparse elements of $\mathbb{F}_q[\mathbb{G}]$, with Hamming weight $t$. In its search version, QA-SD is equivalent to solving the following decoding problem:

$$ (\mathbf{I} \mathbf{A}_1 \dots \mathbf{A}_{c-1}) \begin{pmatrix} \mathbf{e}_0 \\ \vdots \\ \mathbf{e}_{c-1} \end{pmatrix} = \mathbf{s} $$

where the matrix $\mathbf{A}_i$ represents the multiplication by an element $a_i$, with respect to the basis given by $\mathbb{G}$ (for any ordering), and $\mathbf{e}_i$ are sparse vectors of weight $t$. To attack our instance, we consider state-of-the-art generic decoding algorithms, as well as structural attacks.

**Specificity of our instance.** In $\mathbb{F}_4$OLEAGE, we use very particular parameters: we consider the parity-check matrix of a code of length $c|\mathbb{G}|$, and dimension $(c-1)|\mathbb{G}|$, with $|\mathbb{G}| = (q-1)^n = 3^n$ in the millions, together with a sparse vector of errors (typically, there are $ct < 100$ errors). The problem of decoding when the number of errors is sublinear in the size of the code was studied in [CTS16], and the authors showed that in this case, the costs of the best generic algorithm for decoding, namely the ISD algorithm, are all of the form $2^{a(ct)(1+o(1))}$, with $a$ depending only of the code rate $1-1/c$, even the seminal ISD algorithm by Prange [Pra62]. Consequently, any additional optimizations developed based on the Prange algorithm proved to be futile within this specific context.

However, this instance of the decoding problem is far from being generic, and there are known ways in which an attacker can exploit the internal structure. First, since the code is by definition kept invariant under the action of $\mathbb{G}$, they can use the Decoding One Out of Many (DOOM) strategy from [Sen11] to get a $\sqrt{|\mathbb{G}|}$ speed-up in any decoding algorithm. Beyond this approach, an attacker can try to reduce their sample modulo some ideal of $\mathbb{F}_q[\mathbb{G}]$, yielding a new instance of the decoding problem with smaller parameters. In general, this action can significantly increase the noise rate which may render the problem intractable. Nevertheless, this growth can be mitigated by considering reductions arising from quotients of $\mathbb{G}$ by some subgroup $\mathbb{H}$. The key observation here is that this operation, known as folding with respect to $\mathbb{H}$, maps a code of length $c|\mathbb{G}|$ onto a code of length $c|\mathbb{G}/\mathbb{H}|$, while keeping the code-rate invariant. It was first introduced in the context of the cryptanalysis of highly structured variants of McEliece's code-based encryption scheme [FOP+16, CT19], and later considered in [BCCD23] for the analysis of QA-SD. It works as follows: upon receiving a sample of QA-SD, an attacker can pick some sufficiently large subgroup $\mathbb{H}$ and compute the folding of both the received code and the syndrome to get a smaller instance of QA-SD, with respect to the subgroup $\mathbb{G}/\mathbb{H}$. On the folded instance, the noise is upper bounded by the original noise, but might be slightly decreased due to the existence of some collisions. The attacker can then run a generic decoder on this smaller instance. If they want to actually decode the original instance, they need to lift all the putative solutions back to the initial decoding problem. In short, this folding process may be compared to a sub-ISD routine inside a generic decoding algorithm. However, $\mathbb{F}_4$OLEAGE only relies on the decisional variant of QA-SD, and therefore getting a solution on the folded instance is enough to break the security. There is a caveat, though. Indeed, for the folded instance to be meaningful, its length should not be too small relative to the noise level. More precisely, if the target decoding distance is beyond the Gilbert-Varshamov (GV) bound, the folded instance will typically have exponentially many solutions, even when the original sample came from the uniform distribution [Deb23]. This does not provide the attacker with any distinguishing advantage.

**Improvement over the previous approach.** In Section 6, we provide a precise analysis of the probability distribution of the error weight on the folded instance. This allows us to give a more
powerful attack than that of [BCCD23], taking more advantage of our specific QA-SD instance. Indeed, the group used in our construction, namely $\mathbb{G} := (\mathbb{Z}/(q-1)\mathbb{Z})^n$, has a huge number of subgroups of any given order. For example, in $\mathbb{F}_4$OLEAGE we set $q = 4$, and the subgroups of $\mathbb{G}$ of order $3^k$ are in bijection with the $k$-dimensional vector subspaces of $\mathbb{F}_3^n$. Their number is given by the Gaussian binomial coefficient $\binom{n}{k}_3$. At a high level, our attack strategy that makes use of this fact is the following:

1. Pick some subgroup $\mathbb{H}$ and compute the folding with respect to $\mathbb{H}$;

2. Guess that the folded error actually has a Hamming weight $\omega$ much smaller than expected;

3. Apply the best decoding algorithm corresponding to the size and level of noise;

4. Abort if the number of operations is greater than would be required for the pair (level of noise, algorithm), and return to Step 1.

The success probability of this procedure is given by the probability that the weight of the error meets the attacker's guess. In other words, this attack would cost, on average over the uniform choice of subgroups $\mathbb{H}$ of a given order,

$$ \frac{\text{Cost}_{\text{Decoding}}(\omega) + \text{Cost}_{\text{Folding}}}{\text{Pr}[w_H(\text{Fold}_{\mathbb{H}}(x)) = \omega]}, $$

where $\text{Cost}_{\text{Decoding}}(\omega)$ indicates the complexity of the best decoding algorithm, for a noise level of $\omega$, and $\text{Cost}_{\text{Folding}}$ is the cost of the folding operator (which is in fact the length of the original code). In order to get the most out of this attack, it suffices to choose $\omega$ which minimizes this ratio.

**Concrete Parameters.** We provide a SageMath [S+24] script to determine a set of concrete parameters. It is available on GitHub.<fnref n="12" /> Using the script, we estimate that taking $c = 3, t = 27$ offers about 128 bits of security, and taking $c = 4, t = 27$ provides a significant security margin (in both cases, the script is being quite conservative on the power afforded to the adversary).

**Update on the parameters given by Bombar et al. [BCCD23].** In [BCCD23], the authors propose choosing $c = 4, t = 16$ when generating $2^{25}$ OLEs. We find that these parameters are too optimistic, as the attack described above manages to downgrade the security to about 100 bits as opposed to the claimed 128 bits of security. Refer to Section 6.4 for the full attack description. To use the same compression factor $c = 4$ (as suggested in [BCCD23]), we need to increase the noise to $t = 20$, leading to an overall noise equal to $ct = 80$. Such a noise level is somewhat larger than the $ct = 64$ given in the previous work. Taking $c = 5$ leads to a total weight of 70, notably lowering this gap. However, increasing $c$ has a disproportionate impact on the computational performance (see Section 7) due to a requirement for a matrix transpose of size $O(c^2)$.

## 3 Preliminaries

**Notations.** We use $\mathbb{F}_4$ to denote the Galois field of order 4. For $\mathbb{G}$ an Abelian group, we denote by $\mathbb{F}_q[\mathbb{G}]$ the corresponding group algebra. For an integer $n$ and a polynomial $f \in \mathbb{F}_q[\mathbb{G}]$ with $n$ variables, $\text{Eval}_n(f)$ denote the full evaluations of $f$ over $(\mathbb{F}_q^\times)^n$. We let $[N]$ denote the set $\{1, 2, \dots, N\}$. Divisibility is denoted as $a | b$, to mean $a$ divides $b$. The number of elements in a list $L$ is denoted as $|L|$. For a vector $e \in \mathbb{F}_q^n$, we denote by $w_H(e)$ its Hamming weight. More generally, the Hamming weight of an element of a finite-dimensional $\mathbb{F}_q$-algebra $\mathcal{R}$ is the weight of the vector formed by its coefficients in some basis (in general, $\mathcal{R} = \mathbb{F}_q[\mathbb{G}]$ and we consider a basis given by an arbitrary ordering of the elements of $\mathbb{G}$.<fnref n="13" />). For an integer $t$, we denote by $\mathcal{R}_t$ the subset of elements of Hamming weight $t$. We denote by $\text{poly}(\cdot)$ any polynomial and by $\text{negl}(\cdot)$ any negligible function. We use $x \leftarrow_R S$ to denote a uniformly random sample drawn from $S$, and $x \leftarrow \mathcal{A}$ to denote assignment from a possibly randomized algorithm $\text{Adv}$. We use $x := y$ to denote the initialization of a value $x$ to the value of $y$. We use $\mathcal{A} \simeq \mathcal{B}$ to indicate that two sets are isomorphic. By an efficient algorithm $\mathcal{A}$ we mean that $\text{Adv}$ is modeled by a (possibly non-uniform) Turing Machine that runs in probabilistic polynomial time. We write $D_0 \approx_c D_1$ to mean that two distributions $D_0$ and $D_1$ are computationally indistinguishable to all efficient distinguishers $\mathcal{D}$ and $D_0 \approx_s D_1$ to mean that $D_0$ and $D_1$ are statistically indistinguishable.

<footnote n="12">¹² The code is available at https://github.com/mbombar/estimator_folding.</footnote>

<footnote n="13">¹³ The Hamming weight does not depend on the ordering of the elements of $\mathbb{G}$.</footnote>
**Vectors and tensor products.** We denote vectors using bold lowercase letters. For two vector $\mathbf{u} = (u_1, \dots, u_t)$, $\mathbf{v} = (v_1, \dots, v_t) \in \mathbb{R}^t$ for some ring $R$, their tensor product $\mathbf{u} \otimes \mathbf{v}$ is defined by $\mathbf{u} \otimes \mathbf{v} = (u_i \cdot v_j)_{i,j \le t} = (v_1 \cdot \mathbf{u}, \dots, v_t \cdot \mathbf{u})$ and we denote by $\langle \mathbf{u}, \mathbf{v} \rangle$ their inner product. Similarly, we write $\mathbf{u} \boxplus \mathbf{v}$ to denote the outer sum of a vector, equal to $\mathbf{u} \boxplus \mathbf{v} = (u_i + v_j)_{i,j \le t} = (v_1 + \mathbf{u}, \dots, v_t + \mathbf{u})$. We let $\mathbf{u}[i]$ denote the value of index $i$ in $\mathbf{u}$.

## 3.1 Function secret sharing

Function secret sharing (FSS), introduced in [BGI15, BGI16], allows a dealer to succinctly secret share a function with two parties. An FSS scheme splits a secret function $f: \mathcal{D} \to \mathbb{G}$, where $\mathbb{G}$ is some Abelian group into keys $K_0, K_1$ that can be used by party $\sigma \in \{0, 1\}$ to evaluate the function on an input $x \in \mathcal{D}$ and obtain the share $[[f(x)]]_{\sigma}$ of the result. We focus on FSS for point functions which are known as Distributed Point Functions (DPFs).

**Distributed Point Functions.** Let $\mathcal{D}$ be an input domain and $\mathbb{G}$ be an Abelian group. A point function $P_{\alpha, \beta}: \mathcal{D} \to \mathbb{G}$ is a function that evaluates to message $\beta \in \mathbb{G}$ on a single input $\alpha \in \mathcal{D}$, and evaluates to $0 \in \mathbb{G}$ on all other inputs $x \ne \alpha \in \mathcal{D}$. A distributed point function (Definition 1) is a point function that is encoded into a pair of keys. Each key can be used to obtain an additive secret-share of the point function $P_{\alpha}(x)$, for any input $x \in \mathcal{D}$.

**Definition 1 (Distributed Point Function (DPF) [GI14, BGI16]).** Let $\lambda$ be the security parameter, $\mathcal{D}$ be an input domain, and $\mathbb{G}$ be an Abelian group. A DPF scheme (with a full-domain evaluation procedure) consists of a tuple of efficient algorithms DPF = (Gen, FullEval) with the following syntax.

- DPF.Gen$(1^{\lambda}, 1^n, \alpha, \beta) \to (K_0, K_1)$. Takes as input a security parameter, a domain size $n$, and index $\alpha \in \mathcal{D}$ and a payload $\beta \in \mathbb{G}$. Outputs two evaluation keys $K_0$ and $K_1$.

- DPF.FullEval$(\sigma, K_{\sigma}) \to \mathbf{v}_{\sigma}$. Takes as input the party index $\sigma$ and an evaluation key $K_{\sigma}$. Outputs a vector $\mathbf{v}_{\sigma}$.

These algorithms must satisfy correctness, security, and efficiency:

**Correctness.** A DPF is said to be correct if for all $\alpha \in \mathcal{D}$, all $\beta \in \mathbb{G}$, and all pairs of keys generated according to DPF.Gen$(1^{\lambda}, 1^n, \alpha, \beta)$, the sum of the individual outputs from DPF.FullEval result in the one-hot basis vector scaled by the message $\beta$,

$$ \Pr[\text{FullEval}(0, K_0) + \text{FullEval}(1, K_1) = \beta \cdot \mathbf{e}_{\alpha}] = 1, $$

where $\mathbf{e}_{\alpha} \in \mathbb{G}^{|\mathcal{D}|}$ is the $\alpha$-th basis vector.

**Security.** A DPF is said to be secure if each individual evaluation key output by DPF.Gen leaks nothing about $(\alpha, \beta)$ to a computationally bounded adversary. Formally, there exists an efficient simulator $S$ such that $\{K_{\sigma}\} \approx_c S(1^{\lambda}, 1^n, \sigma)$, where $\approx_c$ denotes the computational indistinguishability of distributions.

**Efficiency.** A DPF is said to be efficient if the size of each key is sublinear in the domain size. That is, for all $\sigma \in \{0, 1\}$, $|K_{\sigma}| = |\mathcal{D}|^{\epsilon}$ for some $\epsilon < 1$.

**FSS for the sum of point functions.** We let SPFSS be an FSS scheme for the class of sums of point functions: Functions of the form $f(x) = \sum_i f_{s_i, y_i}(x)$, where each $f_{s_i, y_i}(\cdot)$ evaluates to $y_i$ on $s_i$, and to 0 everywhere else. As in previous works, we will use efficient constructions of SPFSS in our constructions of PCGs.

## 3.2 The Quasi-Abelian Syndrome Decoding Problem

In this section, we recall the Quasi-Abelian Syndrome Decoding assumption (QA-SD) which was introduced in [BCCD23]. It can be seen as a generalization of both the plain Syndrome Decoding (SD) assumption, when the group is $\{1\}$, as well as the quasi-cyclic syndrome decoding assumption. Let $\mathbb{G}$ be a finite Abelian group. The group algebra of $\mathbb{G}$ with coefficients in the finite field $\mathbb{F}_q$ is the
set of formal linear combinations $\{\sum_{g \in \mathbb{G}} a_g g \mid a_g \in \mathbb{F}_q\}$, which is an $\mathbb{F}_q$-vector space of dimension $|\mathbb{G}|$, endowed with the convolution product:

$$ \left( \sum_{g \in \mathbb{G}} a_g g \right) \left( \sum_{g \in \mathbb{G}} b_g g \right) := \sum_{g \in \mathbb{G}} \left( \sum_{h \in \mathbb{G}} a_h b_{hg^{-1}} \right) g. $$

It can be seen that this product is commutative. The Hamming weight $w_H(a)$ of an element $a \in \mathbb{F}_q[\mathbb{G}]$ is the number of its non zero coordinates in the basis $(g)_{g \in \mathbb{G}}$. This is a well-defined notion since it does not depend on the ordering of the elements of $\mathbb{G}$.

Recall that a finite Abelian group is nothing more than a direct product of cyclic groups:

$$ \mathbb{G} \simeq \mathbb{Z}/d_1\mathbb{Z} \times \cdots \times \mathbb{Z}/d_r\mathbb{Z}, $$

where the $d_i$'s can be equal. Then, the group algebra $\mathbb{F}_q[\mathbb{G}]$ admits an explicit description as some particular multivariate polynomial ring:

$$ \mathbb{F}_q[\mathbb{G}] \simeq \mathbb{F}_q[X_1, \dots, X_r]/(X_1^{d_1} - 1, \dots, X_r^{d_r} - 1), $$

where the isomorphism is given by $(k_1, \dots, k_r) \mapsto X_1^{k_1} \cdots X_r^{k_r}$, and extended by linearity. We are now ready to define the main hard problem, which can be stated as a search and a decisional variant.

**Definition 2 (Search) QA-SD(q, c, t, G).** Let $\mathbb{G}$ be a finite Abelian group, $\mathbb{F}_q[\mathbb{G}]$ its algebra with coefficients in the finite field $\mathbb{F}_q$, and let $c \ge 2$ be some constant integer called the compression factor. Given a target Hamming weight $t \in \{1, \dots, |\mathbb{G}|\}$ and a probability distribution $\Phi_t$ which outputs elements $x \in \mathbb{F}_q[\mathbb{G}]$ such that $\mathbb{E}(w_H(x)) = t$. Given access to a pair of the form $(\mathbf{a}, \langle \mathbf{a}, \mathbf{e} \rangle + e_0)$ where $\mathbf{a}$ is uniformly distributed over $\mathbb{F}_q[\mathbb{G}]^{c-1}$ and $\mathbf{e}' := (e_0, \mathbf{e}) \in \mathbb{F}_q[\mathbb{G}]^c$ is formed by independent elements distributed according to $\Phi_t$, the goal is to recover the error term $\mathbf{e}'$.

**Definition 3 (Decisional) QA-SD(q, c, t, G).** Let $\mathbb{G}$ be a finite Abelian group, $\mathbb{F}_q[\mathbb{G}]$ its algebra with coefficients in the finite field $\mathbb{F}_q$, and let $c \ge 2$ be some constant integer called the compression factor. Given a target Hamming weight $t \in \{1, \dots, |\mathbb{G}|\}$ and a probability distribution $\Phi_t$ which outputs elements $x \in \mathbb{F}_q[\mathbb{G}]$ such that $\mathbb{E}(w_H(x)) = t$, the Quasi-Abelian Syndrome Decoding problem asks to distinguish, with a non-negligible advantage, between the distributions:

$$ D_0: \left( (a^{(i)})_{i \in \{1, \dots, c-1\}}, u \right) \quad \text{where } a^{(i)}, u \stackrel{s}{\leftarrow} \mathbb{F}_q[\mathbb{G}] $$

$$ D_1: \left( (a^{(i)})_{i \in \{1, \dots, c-1\}}, \sum_{i=1}^{c-1} a^{(i)} e_i + e_0 \right) \quad \text{where } a^{(i)} \stackrel{s}{\leftarrow} \mathbb{F}_q[\mathbb{G}] \text{ and } e_i \stackrel{s}{\leftarrow} \Phi_t. $$

We say that the QA-SD(q, c, t, G) assumption holds when this problem is hard for every non-uniform polynomial time distinguisher.

**Remark 4.** When it is clear from the context, we might drop the dependency in q and simply write QA-SD(c, t, G).

In general we consider $\Phi_t$ to output uniform elements of Hamming weight $t$, or a regular variant where the basis $(g)_{g \in \mathbb{G}}$ is split into $t$ blocks of size $|\mathbb{G}|/t$ (except maybe the last one) such that each block contains exactly one $t$.

**Relation to linear codes.** Fix an ordering of the elements of $\mathbb{G}$ and for every element $a \in \mathbb{F}_q[\mathbb{G}]$, denote by $M_a$ the $|\mathbb{G}| \times |\mathbb{G}|$ matrix representing the multiplication by $a$. A code having a parity-check matrix formed by multiple blocks of the form $M_a$ is known as a Quasi-Abelian code of group $\mathbb{G}$ (or a quasi-$\mathbb{G}$ code). Formally, it is an $\mathbb{F}_q[\mathbb{G}]$-submodule of the free module $\mathbb{F}_q[\mathbb{G}]^\ell$ for some integer $\ell > 0$. When $\mathbb{G} = \{1\}$, then $\mathbb{F}_q[\mathbb{G}]$ is nothing but the finite field $\mathbb{F}_q$, and therefore a quasi-$\{1\}$ code is simply an $\mathbb{F}_q$-linear code. On the other hand, when $\mathbb{G} = \mathbb{Z}/n\mathbb{Z}$ is cyclic, then $\mathbb{F}_q[\mathbb{G}] \simeq \mathbb{F}_q[X]/(X^n - 1)$. Therefore, quasi-$\mathbb{Z}/n\mathbb{Z}$ codes are exactly quasi-cyclic codes, at the core of many code-based cryptosystems such as Nist Round 4 candidates BIKE [AAB$^{+22a}$] and HQC [AAB$^{+22b}$]. We refer to [BCCD23, Section 4] for more information on Quasi-Abelian codes.
Now, a sample $(\mathbf{a}, \langle \mathbf{a}, \mathbf{e} \rangle) + e_0$ corresponds to a pair $(\mathbf{H}, \mathbf{He}')$ where

$$ \mathbf{H} = [\mathbf{I}_{|\mathbb{G}|} \mathbf{M}_{a_1} \cdots \mathbf{M}_{a_{c-1}}] $$

is by definition, a parity-check matrix of some random quasi-Abelian code of rate $1-1/c$, in systematic form, and $\mathbf{e}' = (e_0, \mathbf{e})$ is an error vector of length $c|\mathbb{G}|$ and weight $ct$, with a $c$-split structure (which is standard when dealing with structured variants of the decoding problem). In other words, the search version of QA-SD corresponds to a structured variant of the decoding problem of random Quasi-Abelian codes.

# 4 A Fast PCG for $\mathbb{F}_4$-OLEs

In this section, we present the construction of QA-SD$_{OLE}$ over $\mathbb{F}_4$ (Figure 1) following optimizations via early termination and fast evaluation of polynomials for FFT.

## 4.1 PCGs over $\mathbb{F}_4$ from the QA-SD assumption

The general description of the framework based on it can be found in Appendix A. In [BCCD23], the authors point out that their QA-SD$_{OLE}$ construction is the first to produce a large number of OLE correlations over $\mathbb{F}_q$, for any $q \ge 3$. They propose using $\mathbb{G} = \prod_{i=1}^n \mathbb{Z}/(q-1)\mathbb{Z}$, $q \ge 3$. The direct consequence of this is that $\mathbb{F}_q[\mathbb{G}] \simeq \mathbb{F}_q[X_1, \dots, X_n]/(X_1^{q-1} - 1, \dots, X_n^{q-1} - 1) \simeq \prod_{i=1}^D \mathbb{F}_q$, where the last isomorphism equivalence comes from the Chinese Remainder Theorem. Above, $D = (q-1)^n$ is the number of elements in the group, and the number of OLE's we can get over $\mathbb{F}_q$ by applying this isomorphism. Looking closely, we instantiate our particular PCG over $\mathcal{R} \simeq \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$, by setting $q = 4$. At the end of the protocol QA-SD$_{OLE}$, the parties obtain one OLE over $\mathcal{R}$, the parties obtain one OLE over $\mathcal{R}$; a general description of the construction is given in Figure 14. Let us denote $(x_\sigma, z_\sigma)$ the output of party $\sigma$. To obtain many OLE's over $\mathbb{F}_4$, the parties have to evaluate $x_\sigma, z_\sigma \in \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$ over the full domain $(\mathbb{F}_4^\times)^n$. The standard approach is to use a Fast Fourier Evaluation to efficiently obtain this result. Here, we remark that, in our group algebra, fast multiplication also requires FFT, first in a multi-evaluation form, and then in the interpolation form. Therefore, doing the interpolation again is wasteful as in the end we will evaluate again after interpolating. As such, we can avoid the intermediate steps of multi-evaluation-then-interpolation and work directly with the evaluations, without coming back to $\mathcal{R}$. That is, we do not construct the polynomials $x_\sigma, z_\sigma$ over $\mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$ but instead, we focus directly on the polynomials evaluations.

Let $\text{Eval}_n(f) = \{f(x_1, \dots, x_n), (x_1, \dots, x_n) \in \{1, \theta, \theta+1\}^n\}$ be the set of all the possible evaluations. Instead of giving the parties the description of the coefficients of the polynomials $a_i \in \mathbf{a}$, we can give them the vectors of all the evaluations of all the polynomials, that is giving them $\text{Eval}_n(a_i)$, for all $i$. Because we can write $x_\sigma = e_\sigma^0 + e_\sigma^1 a_1 + \dots + e_\sigma^{c-1} a_{c-1}$, it follows that all the evaluations of $x_\sigma$ can be obtained from $\text{Eval}_n(e_\sigma^i)$ and $\text{Eval}_n(a_i)$. All that remains is to evaluate the $e_\sigma^i$ polynomials. They are sparse polynomials, and therefore their evaluations can be computed very efficiently i.e., if the polynomials have $t$ non-zero coefficients, then the cost of the evaluation is linear in $t \cdot 3^n$. As a result, we can obtain $\text{Eval}_n(x_\sigma)$ for a cost linear in $3^n$.

The computation of $\text{Eval}_n(z_\sigma)$ is a little trickier. As mentioned above, $x_0 \cdot x_1$ can be seen as a function of degree 2 in $(\mathbf{e}_0, \mathbf{e}_1)$, with constant coefficients depending solely from $\mathbf{a} \otimes \mathbf{a}$. Because $\text{Eval}_n(a_i)$ is already given to the parties, the evaluation of the coefficient from $\mathbf{a} \otimes \mathbf{a}$ can be obtained using only $c^2$ multiplications. It remains to compute the evaluations of the additive shares of the polynomials $e_0^i \cdot e_1^j$. There are $c^2$ such polynomials shared among the parties, and we can view each share as a random polynomial. Therefore, each party has to compute the evaluation of $c^2$ random polynomials. This is a crucial part of the scheme and we devote the next section to it. Figure 1 represents the PCG framework of [BCCD23] tailored to our setting, its correctness and security are implied by Theorem 20.

**Remark 5.** Let $t = 3^k$ be a power of 3, and 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)$. Let $\mathbf{e}_0$ and $\mathbf{e}_1$ be sampled from a $t$-regular noise distribution over $\mathcal{R}$. In other words, the coordinates of $\mathbf{e}_i$ can be divided into $t$ consecutive blocks $B_0, \dots, B_{t-1}$ of size $3^n/t$, each block having a single nonzero coordinate. More precisely, considering the lexicographic ordering of the monomials, and since $t = 3^k$,
block $B_i$ is formed by all monomials $\mathbf{X}^p$ such that the first $k$ coordinates of $\mathbf{p}$ represent the ternary decomposition of the integer $i$ (over $k$ trits). For example, if $n = 4$ and $t = 9$, the $3^4 = 81$ monomials are split into 9 blocks $B_0, \dots, B_8$ of size 9, and a monomial $\mathbf{X}^p$ lies in $B_6$ if and only if $\mathbf{p}$ is of the form $(2, 0, \star, \star)$ with $\star \in \{0, 1, 2\}$, where $[2|0]$ is the ternary decomposition of the integer 6.

We now show that the product $\mathbf{e} = \mathbf{e}_0 \cdot \mathbf{e}_1$ has at most $t$ nonzero monomials in each block.<fnref n="14" /> Indeed, let $i \in \{0, \dots, 3^k - 1\}$ and let $\mathbf{X}^p$ be a monomial appearing in $\mathbf{e}$ with a nonzero coefficient. In particular, the first $k$ entries of $\mathbf{p}$ can be parsed as the ternary decomposition of $i$, which we denote by $[i]_3$. It is clear that $\mathbf{X}^p$ is of the form $\mathbf{X}^{p_0+p_1}$ where $p_0$ (resp. $p_1$) identifies one of the $t$ nonzero monomials in $\mathbf{e}_0$ (resp. $\mathbf{e}_1$), and the sum is taken modulo 3 component-wise. In particular, there are at most $t^2$ such monomials, and for each nonzero monomial $\mathbf{X}^{p_0}$ of $\mathbf{e}_0$, with first $k$ entries $[i_0]_3$, there corresponds at most one nonzero monomial in $\mathbf{e}_1$ contributing to $\mathbf{X}^p$, namely $\mathbf{X}^{p-p_0}$.<fnref n="15" /> In other words, the monomial $\mathbf{X}^p$ can be produced by at most $t$ possible pairs of monomials $(\mathbf{X}^{p_0}, \mathbf{X}^{p_1})$, whose first $k$ entries are $([i_0]_3, [i]_3 - [i_0]_3)$, with $i_0$ ranging over $\{0, \dots, t-1\}$.

**Example.** Let $n = 3$ and $t = 3$. Set $\mathbf{e}_0 := X_3^2 + X_1X_2X_3 + X_1^2$ (which corresponds to positions $(0, 0, 2)$, $(1, 1, 1)$, and $(2, 0, 0)$) and $\mathbf{e}_1 := 1+X_1+X_1^2$ (which corresponds to positions $(0, 0, 0)$, $(1, 0, 0)$, and $(2, 0, 0)$). Then,

$$ \mathbf{e}_0 \cdot \mathbf{e}_1 = \underbrace{(1 + X_3^2 + X_2X_3)}_{\in B_0} + \underbrace{(X_1 + X_1X_3^2 + X_1X_2X_3)}_{\in B_1} + \underbrace{(X_1^2 + X_1^2X_3^2 + X_1^2X_2X_3)}_{\in B_2}. $$

**Proposition 6.** 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}$ is an Abelian group. Assume that SPFSS is a secure FSS scheme for sums of point functions and that the QA-SD($q, c, t, \mathbb{G}$) assumption holds for regular noise distribution. Then there exists a generic scheme to construct a PCG to produce one OLE correlation (described on Figure 1). If the SPFSS is based on a PRG: $\{0, 1\}^\lambda \to \{0, 1\}^{2\lambda+2}$ via the PRG-based construction from [BGI16], we obtain:

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

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

The proof follows immediately from Theorem 20 (in Appendix A) and the analysis of [BCCD23].

## 4.2 Optimizing the FSS evaluation via early termination

We remark that we can use a very simple trick that enables the parties to obtain the evaluation of their MPFSS shares 64 times faster than with the standard construction (and at a slight reduction in communication). The trick comes from the fact that the standard construction of the DPF based on the GGM tree implies that each leaf is of size $\lambda = 128$ bits. It was pointed out in [BGI16] that we can consider early termination in the case of small outputs. In our case, we would like a single leaf to encode a value in $\mathbb{F}_4$. This only requires 2 bits instead of the 128 bits we get as output, making the naïve evaluation “waste” 126 bits of the output. Instead, we can avoid wasting computation by truncating the tree 6 levels earlier and setting the value of the new 128-bit leaf on the special path to encode a unit vector consisting of zeroes except on the exact 2 bits where it equals to the correct value of $\mathbb{F}_4$ element. This essentially involves “hard-coding” the end of the path into the leaf directly, as illustrated in Section 4.2. Using this idea, we reduce the computational cost of evaluating the DPF by $64 \times$ and reduce the communication costs (key size of the DPF) by roughly $6 \cdot 128$ bits [BGI16]. This simple trick was initially introduced in the context of PIR applications [BGI16], but could not be applied to prior PCG constructions until now since all PCG constructions (except for the recent PCG construction of Bombar et al. [BCCD23]) required the DPF output to be encode elements of a large field. Similarly, in silent OT extension protocols [BCG$^{+}$19a, BCG$^{+}$19b, CRR21, BCG$^{+}$22, RRT23], which are also bottlenecked by DPF evaluations, this optimization could not be applied because there, the DPF is used to output “authenticated” shares of a (potentially small) field element with a (large) MAC, which requires the leaves to encode 128 bit output value.

<footnote n="14">¹⁴ This crucially relies on the fact that since $t$ is a power of 3, we can uniquely identify the block corresponding to a given monomial by looking at the first $k$ entries of its exponent. When $t$ is not a power of 3, this is not true anymore.</footnote>

<footnote n="15">¹⁵ Note that the corresponding monomial $\mathbf{X}^{p_1}$ might not appear in $\mathbf{e}_1$.</footnote>
Specific construction of QA-SD<sub>OLE</sub> for <sub>F</sub><sub>4</sub>O<sub>LEAGE</sub>

PARAMETERS: Noise weight $t = t(\lambda)$, compression factor $c$, ring $\mathcal{R} = \mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$. A SPFSS scheme SPFSS = (SPFSS.Gen, SPFSS.FullEval) for sums of $t^2$ point functions, with domain $[0 \dots 3^n)$ and range $\mathbb{F}_4$.

PUBLIC INPUT: $c-1$ vectors of length $3^n$ over $\mathbb{F}_4$, corresponding to the result of $\text{Eval}_n(a_i)$, for uniformly random $a_1, \dots, a_{c-1} \in \mathcal{R}$, therefore the full evaluation of the $c$ elements $a_i$.

PCG.Gen(1<sup>λ</sup>):

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

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

▷ [Optimization]: $\mathbf{p}_{\sigma}^{i}$ can be sampled from regular noise distribution. See Remark 5.

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

2.1: Sample FSS keys $(K_0^{i,j}, K_1^{i,j}) \leftarrow \text{SPFSS.Gen}(1^{\lambda}, 1^n, \mathbf{p}_0^i \boxplus \mathbf{p}_1^j, \mathbf{v}_0^i \otimes \mathbf{v}_1^j)$.

▷ If using regular noise as an optimization, then

▷ SPFSS is for the sum of $t$ point functions with domain $[0, \dots, 3^n/t)$.

3: Let $\mathbf{k}_{\sigma} = ((K_{\sigma}^{i,j})_{i,j \in [0 \dots c)}$, $(\mathbf{p}_{\sigma}^{i}, \mathbf{v}_{\sigma}^{i})_{i \in [0 \dots c)}$.

4: Output $(\mathbf{k}_0, \mathbf{k}_1)$.

PCG.Expand(σ, κ<sub>σ</sub>):

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

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

2.1: Define over $\mathbb{F}_4$ the polynomial:

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

2.2: Compute $\text{Eval}_n(e_{\sigma}^i)$.

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: From $\text{Eval}_n(e_{\sigma}^i)$ and $\text{Eval}_n(a_i)$, compute $\text{Eval}_n(x_{\sigma})$.

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

5.1: Compute $u_{\sigma, i+c_j} \leftarrow \text{SPFSS.FullEval}(\sigma, K_{\sigma}^{i,j})$ and view it as a $c^2$ vector $\mathbf{u}_{\sigma}$ of elements in $\mathcal{R}$.

6: **foreach** $j \in [0 \dots c^2):$

6.1: Compute $\text{Eval}_n(u_{\sigma,j})$.

▷ [Optimization]: only need to perform $c(c+1)/2$ FFTs, see Section 2.5.

7: Compute $\text{Eval}_n(z_{\sigma})$, with $z_{\sigma} = \langle \mathbf{a} \otimes \mathbf{a}, \mathbf{u}_{\sigma} \rangle$.

8: Output $(\text{Eval}_n(x_{\sigma}), \text{Eval}_n(z_{\sigma}))$.

<caption>Fig. 1: QA-SD-based PCG for OLE over $\mathcal{R}$ from evaluations of functions.</caption>
<figure><img src="image_3.png" /><figcaption>Fig. 2: Early termination example in the case we truncate only two steps earlier. Solid black nodes represent “zero” leaves, whereas solid red leaves can take on any value.</figcaption></figure>

## 4.3 Fast evaluation over $\mathbb{F}_4[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$

**The high-level idea.** Given a polynomial $P$ with $n$ variables, the party wants to compute $\text{Eval}_n(P)$, that is, to evaluate $P$ over $(\mathbb{F}_4^\times)^n$ where $\mathbb{F}_4^\times = \{1, \theta, \theta+1\}$. Here, we adapt the standard divide-and-conquer style algorithm to our case, see for example the seminal work of [CT65]. Remark that

$$P(X_1, \dots, X_n) = P_0(X_1, \dots, X_{n-1}) + X_n P_1(X_1, \dots, X_{n-1}) + X_n^2 P_2(X_1, \dots, X_{n-1}).$$

Instead of classically dividing our problem into 2 sub-problems, we divide it into 3 sub-problems. This is a ternary generalization of a standard FFT algorithm adapted to our case. Then,

$$\text{Eval}_n(P) = \text{Eval}_{n-1}(P_0) \cup X_n \text{Eval}_{n-1}(P_1) \cup X_n^2 \text{Eval}_{n-1}(P_2). \quad (1)$$

Denote by $\mathcal{C}(\text{Eval}_n(P))$ the number of operations carried out to obtain all the $3^n$ evaluations on the set $\mathbb{F}_4^\times$. Then we have $\mathcal{C}(\text{Eval}_n(P)) = 3\mathcal{C}(\text{Eval}_n(P)) + 2 \cdot 3^n$, which leads us to $\mathcal{C}(\text{Eval}_n(P)) = 4 \cdot n \cdot 3^n$. The concrete number of additions or multiplications is $2 \cdot n \cdot 3^n$. This quick back-of-the-envelope calculation captures the essence of the technique, even if it does not accurately count the cost of the various operations and does not take into account what is implemented in practice. We now turn to a concrete implementation of this idea:

**Concrete implementation.** An element of $\mathbb{F}_4$ has a direct canonical representation using 2 bits. Given an element $x \in \mathbb{F}_4$, we write $x(0)$ and $x(1)$ to denote the $\mathbb{F}_2$-coefficients of $x$ viewed as a polynomial over $\mathbb{F}_2[X]/(X^2 + X + 1)$; that is, $x = x(0) + \theta \cdot x(1)$. Using a given machine word of 64 bits we represent a vector of size 32 over $\mathbb{F}_4$, such that the even indexed bits are high order and the odd indexed bits are low order. This is illustrated in Figure 3.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Representation of a vector of $\mathbb{F}_4$ elements. Red blocks represent the high-order bits while the blue blocks represent low-order bits.</figcaption></figure>

As stated before, we use a recursive algorithm to compute all the evaluations, displayed in algorithm Figure 4. We considered using a non-recursive approach but no significant efficiency gains were observed, so we instead decided to use the recursive algorithm due to its conceptual simplicity.

**Actual cost of the computation.** A step in the algorithm of Figure 4 is to evaluate a polynomial of degree 2, with coefficient in $\mathbb{F}_4$, for the values $\{1, \theta, \theta+1\}$. Let the polynomial be $a + bX_i + cX_i^2$.

- in the case $X_i = 1$, then the evaluation of the polynomial becomes $a + b + c$.

- in the case $X_i = \theta$, the evaluation becomes $(a + c) + \theta \cdot (b + c)$.

- in the case $X_i = \theta + 1$, the evaluation becomes $(a + b) + \theta \cdot (b + c)$.

Note that we want to compute all the different evaluations, and therefore we can try to reduce the overall costs by reusing several of the intermediate calculations. We can obtain the three evaluations
via the following steps: (1)compute $a+b, a+c, b+c$; (2) compute $\theta \cdot (b+c)$; (3) compute $a+b+c$; (4) Compute $(a+c)+\theta \cdot (b+c)$, and $(a+b)+\theta \cdot (b+c)$. Therefore, we count 12 classical bit-by-bit XOR over $\mathbb{F}_2$, and a multiplication by $\theta$ to obtain the three needed evaluations of the polynomial.

### Fast-Evaluation algorithm

PARAMETERS: $n > 0$ an integer, $P \in \mathbb{F}_3[X_1, \dots, X_n]/(X_1^3 - 1, \dots, X_n^3 - 1)$, a polynomial with $n$ variables.

FastEval(n, P):

1. if $n = 1$ then

1.1. return $\{P(1), P(\theta), P(\theta + 1)\}$

2. else

2.1. Write $P(X_1, \dots, X_n) = P_0(X_1, \dots, X_{n-1}) + X_n P_1(X_1, \dots, X_{n-1}) + X_n^2 P_2(X_1, \dots, X_{n-1})$.

2.2. $S := \{\}$.

2.3. $\forall i \in \{0, 1, 2\}, S_i \leftarrow \text{FastEval}(n-1, P_i)$.

2.4. **foreach** $i \in [|S_0|]$:

2.4.1. $f_j(X) := S_0[j] + S_1[j]X + S_2[j]X^2$.

2.4.2. $S \leftarrow S \cup \{f_j(1), f_j(\theta), f_j(\theta + 1)\}$.

2.5. return $S$.

<caption>Fig. 4: Fast evaluation of a polynomial in $n$ variables.</caption>

**4.3.1 Taking advantage of the computer words.** Today's processors offer XOR operations for machine words of size 64 bits. We take advantage of this parallelism to run multiple FFTs in parallel with a small overhead compared to running a single FFT. With 64-bit machine words, we can perform up to 32 FFT in parallel. We pack the $c^2$ FFTs required by our PCG as follows: we let each machine word contain a single coefficient of the same monomial for each of the $c^2$ polynomials that we are trying to compute. This saves a factor of $c^2$, at no extra cost.<fnref n="16" /> Therefore, the cost of the evaluation of a single polynomial being of $16n \cdot 3^{n-1}$ XOR, the optimization entails the cost of obtaining the full evaluation of the $c^2$ polynomials to be $16\lceil c^2/64 \rceil n \cdot 3^{n-1}$.

# 5 Distributed Seed Generation

In this section, we build a distributed point function that works over ternary indices. This generalization of the standard DPF construction allows us to cleanly work on a ternary basis. In particular, this makes the distributed seed generation protocol for our PCG construction in Figure 14 much more efficient by avoiding the use of expensive secure binary decomposition protocols when working over ternary secret shares.

## 5.1 A ternary distributed point function

In prior constructions [GI14, BGI15, BGI16], the domain of DPF was set to $\mathcal{D} = \{0, 1\}^n$. In contrast, we will use a ternary domain $\{0, 1, 2\}^n$. While this change may appear conceptually straightforward, the constructions of [GI14, BGI15] do not immediately generalize to non-binary input domains. We therefore construct a ternary DPF using the main ideas behind the two state-of-the-art constructions [BGI15, BGI16].

**Definition 7 (Random Distributed Point Function (rDPF)).** We say a DPF scheme is a random DPF (rDPF) scheme if DPF.Gen does not take the parameter $\beta$ as input, and the output value at index $\alpha$ is a secret share of a value ($s \parallel 1 \in \{0, 1\}^{\lambda+1}$, where $s$ pseudorandom conditioned on $K_\sigma$, for $\sigma \in \{0, 1\}$.

<footnote n="16">¹⁶ In practice, using larger machine words has an impact by increasing stack usage, but this is only observed when performing an FFT over very large polynomials.</footnote>
**Lemma 8 (Adapted from [BGI16]).** Any random DPF scheme with output group $\{0, 1\}^{\lambda+1}$ can be transformed into a DPF scheme for any choice of $\beta \in \mathbb{G}$ a the cost of increasing the key size by $\log |\mathbb{G}|$ bits.

*Remark 9.* Looking ahead to Section 5.2, using a random DPF makes our protocols and analysis simpler. In particular, describing a distributed key generation protocol for a random DPF eliminates edge cases associated with the output value $\beta$. Separately, we show how to generate an “output correction word” that can be used to go from the $s\parallel1$ output of an rDPF to an arbitrary output $\beta$.

We present our construction for a ternary rDPF in Figure 5 and analyze security in Proposition 10. The construction follows a similar template to the DPF construction of [BGI15].

**Proposition 10 (Ternary rDPF security).** *Figure 5 satisfies the correctness and security properties of Definition 7.*

*Proof.* Deferred to Appendix E.1. □

## 5.2 Distributed DPF key generation

In this section, we describe how two parties can generate DPF keys using secret-shares of the index $\alpha$ (i.e., the index at which the point function evaluates to a non-zero value). Our approach is inspired by the protocol of Doerner-shelat [Ds17], which makes only black-box use of OT to select the appropriate correction word at each level. While formally constructing such a protocol requires multiple functionalities and is quite tedious, conceptually, the core idea is very simple. At a high level, each party evaluates the DPF tree, layer-by-layer, and computes the correction word $CW_i$ for layer $i$ using a secure protocol that takes as input shares of the $i$-th trit $\alpha_i \in \{0, 1, 2\}$ and the “shares” of the left, middle, and right node labels $(s_{i,0}\|t_{i,0}, s_{i,1}\|t_{i,1}, s_{i,2}\|t_{i,2})$. The protocol then outputs $CW_i$ exactly as computed in Figure 5 to both parties. However, this only results in the parties getting rDPF keys. To make the output consist of a chosen value $\beta \in \mathbb{F}_4$, we construct a separate protocol that outputs a special “output” correction word, denoted $CW_{\text{out}}$, that can be used to go from an rDPF output to a chosen output $\beta$ (which the parties hold shares of). Conceptually, $CW_{\text{out}}$ is the last-layer correction word that encodes the “early termination” output in addition to $\beta$.

**Overview of functionalities and instantiations.** The main ideal functionality, $\mathcal{F}_{\text{rDPF-DKG}}$, for computing the full rDPF keys (matching the distribution of rDPF.Gen in Figure 5) is presented in Figure 8. It is followed by an instantiation, $\Pi_{\text{rDPF-DKG}}$, in Figure 9 where we show how to (1) compute the correction words in each $i$-th layer by executing the sub-protocol $\Pi_{\text{rDPF-CW}}$, (2) define the input of $\Pi_{\text{rDPF-CW}}$ for each $i$-th layer that maintains the correctness of rDPF.FullEval (indicator bits and constraints between correction words) and the rDPF.Gen can be distributed recursively. Since we are using a sub-protocol $\Pi_{\text{rDPF-CW}}$, we construct its instantiation in Figure 7 and define its ideal functionality in $\mathcal{F}_{\text{rDPF-CW}}$ Figure 6. $\Pi_{\text{rDPF-CW}}$ shows how to securely compute the correction words for each $i$-th layer based on $\binom{1}{3}$-OT (note that our protocol $\Pi_{\text{rDPF-CW}}$ only outputs $CW_i$, it does not handle the correctness of indicator bits and the constraints between correction words in two consecutive layers).

Then, in $\Pi_{\text{Output-CW}}$ Figure 11, we show how to handle computing the “output” correction word that allows us to go from a random output (as computed by the rDPF) to a chosen output, by computing a final correction word $CW_{\text{out}}$ and satisfies the ideal functionality $\mathcal{F}_{\text{Output-CW}}$ defined in Figure 10. The output of PCG-OLE is formed by the multiple shares of each party so an extra OLE over $\mathbb{F}_4$ is used to convert from multiple shares to additive shares before being the input of Figure 11.

We show that all of our instantiations are secure in the semi-honest setting and we prove security in the UC model, where we only make use of the standard ideal functionality 1-out-of-3 chosen OT $\binom{1}{3}$-OT (Figure 22). Due to limited space, the security proofs for security of $\Pi_{\text{rDPF-CW}}$, $\Pi_{\text{rDPF-DKG}}$, $\Pi_{\text{Output-CW}}$ are provided in Appendix E.2, Appendix E.3, and Appendix E.4, respectively.

**Lemma 11 (Ternary rDPF-CW security).** *The construction $\Pi_{\text{rDPF-CW}}$ in Figure 7 securely realizes the ideal functionality $\mathcal{F}_{\text{rDPF-CW}}$ (Figure 6) against semi-honest adversaries in the $\binom{1}{3}$-OT hybrid model.*
Construction of Ternary rDPF

PARAMETERS: Pseudorandom generator $G: \{0, 1\}^{\lambda} \to \{0, 1\}^{3(\lambda+1)}$.

rDPF.Gen($1^{\lambda}$, $1^n$, $\alpha$):

1: **parse** $\alpha = \alpha_1 \| \dots \| \| \alpha_n$ where $\alpha_i \in \{0, 1, 2\}$ for all $i \in [n]$.

2: $s_0^0, s_0^1 \leftarrow_R \{0, 1\}^{\lambda}$, $t_0^0 \leftarrow 0$, $t_0^1 \leftarrow 1$.

3: **foreach** $i \in [n]$:

3.1: $(s_{i,0}^0 \| t_{i,0}^0 \| s_{i,1}^0 \| t_{i,1}^0 \| s_{i,2}^0 \| t_{i,2}^0) \leftarrow G(s_{i-1}^0)$.

3.2: $(s_{i,0}^1 \| t_{i,0}^1 \| s_{i,1}^1 \| t_{i,1}^1 \| s_{i,2}^1 \| t_{i,2}^1) \leftarrow G(s_{i-1}^1)$.

3.3: $s_{i,0} \| t_{i,0} \leftarrow (s_{i,0}^0 \| t_{i,0}^0) \oplus (s_{i,0}^1 \| t_{i,0}^1)$.

3.4: $s_{i,1} \| t_{i,1} \leftarrow (s_{i,1}^0 \| t_{i,1}^0) \oplus (s_{i,1}^1 \| t_{i,1}^1)$.

3.5: $s_{i,2} \| t_{i,2} \leftarrow (s_{i,2}^0 \| t_{i,2}^0) \oplus (s_{i,2}^1 \| t_{i,2}^1)$.

3.6: $CW_{i,j} \leftarrow s_{i,j} \| t_{i,j}$ for all $j \in \{0, 1, 2\} \setminus \{\alpha_i\}$.

3.7: $r_i \leftarrow_R \{0, 1\}^{\lambda}$.

3.8: $CW_{i,\alpha_i} \leftarrow (s_{i,\alpha_i} \oplus r_i) \|(t_{i,\alpha_i} \oplus 1)$.

3.9: $CW_i \leftarrow CW_{i,0} \| CW_{i,1} \| CW_{i,2}$.

3.10: $s_i^0 \| t_i^0 \leftarrow s_{i,\alpha_i}^0 \| t_{i,\alpha_i}^0 \oplus (t_{i-1}^0 \cdot CW_{i,\alpha_i})$.

3.11: $s_i^1 \| t_i^1 \leftarrow s_{i,\alpha_i}^1 \| t_{i,\alpha_i}^1 \oplus (t_{i-1}^1 \cdot CW_{i,\alpha_i})$.

4: **pp** $\leftarrow (CW_1, \dots, CW_n)$.

5: $K_A \leftarrow (\text{pp}, s_0^0 \| t_0^0)$, $K_B \leftarrow (\text{pp}, s_0^1 \| t_0^1)$.

6: **return** $(K_A, K_B)$.

rDPF.FullEval($\sigma$, $K_\sigma$):

1: **parse** $K_\sigma = (\text{pp}, s_0^\sigma \| t_0^\sigma)$.

2: **out** $\leftarrow$ Traverse($\sigma$, **pp**, $s_0^\sigma$, $t_0^\sigma$, 1), $\gamma \leftarrow 3^n$.

3: **parse out** = $(v_1, \dots, v_\gamma) \in (\{0, 1\}^\lambda)^\gamma$.

4: **return** $(v_1, \dots, v_\gamma)$.

Traverse($\sigma$, **pp**, $s_{i-1}^\sigma$, $t_{i-1}^\sigma$, $i$):

1: **parse** **pp** = $(CW_1, \dots, CW_n)$.

2: **if** $i = n + 1$ **then**

2.1: **return** $s_{i-1}^\sigma \| t_{i-1}^\sigma$.

3: **else**

3.1: $\tau_i^\sigma \leftarrow G(s_{i-1}^\sigma)$, $\gamma_i^\sigma \leftarrow \tau_i^\sigma \oplus (t_{i-1}^\sigma \cdot CW_i)$.

3.2: **parse** $\gamma_i^\sigma = s_{i,0}^\sigma \| t_{i,0}^\sigma \| s_{i,1}^\sigma \| t_{i,1}^\sigma \| s_{i,2}^\sigma \| t_{i,2}^\sigma \in \{0, 1\}^{3(\lambda+1)}$.

3.3: **return** Traverse($\sigma$, **pp**, $s_0^\sigma$, $t_0^\sigma$, $i+1$) || Traverse($\sigma$, **pp**, $s_1^\sigma$, $t_1^\sigma$, $i+1$) || Traverse($\sigma$, **pp**, $s_2^\sigma$, $t_2^\sigma$, $i+1$).

<caption>**Fig. 5:** Ternary DPF construction with full-evaluation optimization. All $s$ values are $\{0, 1\}^{\lambda}$ bit strings and $t$ values are bits. Superscripts 0 and 1 represent a party identifier which we write as $\sigma \in \{0, 1\}$ when referring to a value held by party $\sigma \in \{0, 1\}$.</caption>
Ideal Functionality $\mathcal{F}_{\text{rDPF-CW}}$

The functionality interacts with a party $P_{\sigma}$ and an adversary $\mathcal{A}$.

PARAMETERS: Pseudorandom generator $G: \{0, 1\}^{\lambda} \to \{0, 1\}^{3(\lambda+1)}$.

FUNCTIONALITY:

1: Wait for input $([\alpha_i]_{\bar{\sigma}}, r_i^{\bar{\sigma}}, (s_{i,j}^{\bar{\sigma}}\|t_{i,j}^{\bar{\sigma}})_{j \in \{0,1,2\}}) \in \mathbb{F}_3 \times \{0,1\}^{\lambda} \times \{0,1\}^{3(\lambda+1)}$ from $\mathcal{A}$.

2: Wait for input $([\alpha_i]_{\sigma}, r_i^{\sigma}, (s_{i,j}^{\sigma}\|t_{i,j}^{\sigma})_{j \in \{0,1,2\}}) \in \mathbb{F}_3 \times \{0,1\}^{\lambda} \times \{0,1\}^{3(\lambda+1)}$ from party $P_{\sigma}$.

3: Set $\alpha_i := [\alpha_i]_0 + [\alpha_i]_1 \in \mathbb{F}_3$, $r_i := r_i^0 \oplus r_i^1$.

4: Compute $s_{i,j}\|t_{i,j} := (s_{i,j}^0\|t_{i,j}^0) \oplus (s_{i,j}^1\|t_{i,j}^1)$ for $j \in \{0, 1, 2\}$.

5: $\text{CW}_{i,j} := s_{i,j}\|t_{i,j}$ for all $j \in \{0, 1, 2\} \setminus \{\alpha_i\}$, $\text{CW}_{i,\alpha_i} := (s_{i,\alpha_i} \oplus r_i)\|(t_{i,\alpha_i} \oplus 1)$.

6: $\text{CW}_i := \text{CW}_{i,0}\|\text{CW}_{i,1}\|\text{CW}_{i,2}$.

7: Output $\text{CW}_i$ to both $P_{\sigma}$ and $\mathcal{A}$.

<caption>Fig. 6: Ideal functionality $\mathcal{F}_{\text{rDPF-CW}}$ for computing the correction words</caption>

Protocol $\Pi_{\text{rDPF-CW}}$

PARAMETERS:

- Party $\sigma \in \{0,1\}$ has input $[\alpha_i]_{\sigma} \in \mathbb{F}_3$, $r_i^{\sigma} \in \{0,1\}^{\lambda}, (s_{i,j}^{\sigma}\|t_{i,j}^{\sigma})_{j \in \{0,1,2\}} \in \{0,1\}^{3(\lambda+1)}$.

- An instantiation of chosen $\binom{1}{3}$-OT.

PROTOCOL:

For each party $\sigma \in \{0,1\}$:

1: Sample $z^{\sigma} \leftarrow_R \{0,1\}^{3(\lambda+1)}$.

2: Define

$$ \mathbf{C}_0^{\sigma} := (r_i^{\sigma} \oplus s_{i,0}^{\sigma} \|(t_{i,0}^{\sigma} \oplus \sigma), s_{i,1}^{\sigma} \|t_{i,1}^{\sigma}, s_{i,2}^{\sigma} \|t_{i,2}^{\sigma}) \oplus z^{\sigma} \triangleright [\text{CW}_i]_{\sigma} \text{ when } \alpha_i = 0 $$

$$ \mathbf{C}_1^{\sigma} := (s_{i,0}^{\sigma}\|t_{i,0}^{\sigma}, r_i^{\sigma} \oplus s_{i,1}^{\sigma} \|(t_{i,1}^{\sigma} \oplus \sigma), s_{i,2}^{\sigma}\|t_{i,2}^{\sigma}) \oplus z^{\sigma} \triangleright [\text{CW}_i]_{\sigma} \text{ when } \alpha_i = 1 $$

$$ \mathbf{C}_2^{\sigma} := (s_{i,0}^{\sigma}\|t_{i,0}^{\sigma}, s_{i,1}^{\sigma}\|t_{i,1}^{\sigma}, r_i^{\sigma} \oplus s_{i,2}^{\sigma}\|(t_{i,2}^{\sigma} \oplus \sigma)) \oplus z^{\sigma} \triangleright [\text{CW}_i]_{\sigma} \text{ when } \alpha_i = 2 $$

$$ \mathbf{M}_0^{\sigma} := (\mathbf{C}_0^{\sigma}, \mathbf{C}_1^{\sigma}, \mathbf{C}_2^{\sigma}), \quad \mathbf{M}_1^{\sigma} := (\mathbf{C}_1^{\sigma}, \mathbf{C}_2^{\sigma}, \mathbf{C}_0^{\sigma}), \quad \mathbf{M}_2^{\sigma} := (\mathbf{C}_2^{\sigma}, \mathbf{C}_0^{\sigma}, \mathbf{C}_1^{\sigma}) $$

3: Invoke $\binom{1}{3}$-OT with party $\bar{\sigma}$ as follows:

- Party $\bar{\sigma}$ plays the role of the sender with inputs $\mathbf{M}_{[\alpha_i]_{\bar{\sigma}}}^{\bar{\sigma}}$.

- Party $\sigma$ plays the role of the receiver and inputs $[\alpha_i]_{\sigma} \in \mathbb{F}_3$.

- Party $\sigma$ gets $\mathbf{M}_{[\alpha_i]_{\sigma}}^{\bar{\sigma}}$ $[ [\alpha_i]_{\sigma} ] \in \{0,1\}^{3(\lambda+1)} $ while party $\bar{\sigma}$ gets nothing.

4: Define $[\text{CW}_i]_{\sigma} := \mathbf{M}_{[\alpha_i]_{\sigma}}^{\bar{\sigma}}$ $[ [\alpha_i]_{\sigma} ] \oplus z^{\sigma}$ and broadcast $[\text{CW}_i]_{\sigma}$.

5: Construct $\text{CW}_i := [\text{CW}_i]_{\sigma} \oplus [\text{CW}_i]_{\bar{\sigma}} \in \{0,1\}^{3(\lambda+1)}$.

6: Output $(\text{CW}_{i,0}, \text{CW}_{i,1}, \text{CW}_{i,2})$.

<caption>Fig. 7: Instantiation of $\mathcal{F}_{\text{rDPF-CW}}$ for computing the correction words.</caption>

**Proposition 12 (Ternary rDPF-DKG security).** The construction in Figure 9 securely realizes the ideal functionality $\mathcal{F}_{\text{rDPF-DKG}}$ (Figure 8) against semi-honest adversaries in the $\mathcal{F}_{\text{rDPF-CW}}$ hybrid model.

**Proposition 13 (Ternary Output-CW security).** The construction $\Pi_{\text{Output-CW}}$ in Figure 11 securely realizes the ideal functionality $\mathcal{F}_{\text{Output-CW}}$ (Figure 10) against semi-honest adversaries in the $\binom{1}{3}$-OT hybrid model.
Ideal Functionality $\mathcal{F}_{\text{rDPF-DKG}}$

The functionality interacts with a party $P_{\sigma}$ and an adversary $\mathcal{A}$.

PARAMETERS: $\text{rDPF} = (\text{rDPF.Gen}, \text{rDPF.FullEval})$ as constructed in Figure 5.

FUNCTIONALITY:

1: Wait for input $([\alpha_i]_{\bar{\sigma}})_{i \in [n]} \in \mathbb{F}_3^n$, $(r_i^{\bar{\sigma}})_{i \in [n]} \in (\{0, 1\}^{\lambda})^n$, and $s_0^{\bar{\sigma}} \in \{0, 1\}^{\lambda}$ from $\mathcal{A}$.

2: Wait for input $([\alpha_i]_{\sigma})_{i \in [n]} \in \mathbb{F}_3^n$, $(r_i^{\sigma})_{i \in [n]} \in (\{0, 1\}^{\lambda})^n$, and $s_0^{\sigma} \in \{0, 1\}^{\lambda}$ from party $P_{\sigma}$.

3: Set $t_0^0 = 0, t_0^1 = 1$.

4: Set $\alpha_i := [\alpha_i]_0 + [\alpha_i]_1 \in \mathbb{F}_3$ and $r_i := r_i^0 + r_i^1 \in \{0, 1\}^{\lambda}$ for each $i \in [n]$.

5: For each $i \in [n]$:
Compute $\text{CW}_i$ as done in Step 3 of rDPF.Gen($1^{\lambda}, 1^n, \alpha$) in Figure 5.

6: Set $\text{pp} := (\text{CW}_1, \dots, \text{CW}_n)$, $K_0 := (\text{pp}, s_0^0 \| t_0^0)$, and $K_1 := (\text{pp}, s_0^1 \| t_0^1)$.

7: Output $K_{\sigma}$ to $P_{\sigma}$ and $K_{\bar{\sigma}}$ to $\mathcal{A}$.

**Fig. 8:** Ideal functionality $\mathcal{F}_{\text{rDPF-DKG}}$ for distributed key generation of the ternary rDPF construction from Figure 5.

Protocol $\Pi_{\text{rDPF-DKG}}$

PARAMETERS:

- Pseudorandom generator $G: \{0, 1\}^{\lambda} \to \{0, 1\}^{3(\lambda+1)}$.

- There are two parties $\sigma, \bar{\sigma} \in \{0, 1\}$ with input $([\alpha_i]_{\sigma})_{i \in [n]} \in \mathbb{F}_3^n$, $(r_i^{\sigma})_{i \in [n]} \in (\{0, 1\}^{\lambda})^n$, $s_{0,0}^{\sigma} \in \{0, 1\}^{\lambda}$.

PROTOCOL:

For each party $\sigma \in \{0, 1\}$:

1: Set $\hat{t}_{0,1}^{\sigma} := \sigma$ and $\hat{s}_{0,1} := s_{0,0}$.

2: **foreach** $i \in [n]$:

3.1: Set $d := 3^i$.

3.2: **foreach** $j \in [d-1]$:

3.1.1: $(s_{i,3j}^{\sigma} \| t_{i,3j}^{\sigma} \| s_{i,3j+1}^{\sigma} \| t_{i,3j+1}^{\sigma} \| s_{i,3j+2}^{\sigma} \| t_{i,3j+2}^{\sigma}) \leftarrow G(\hat{s}_{i-1,j}^{\sigma})$.

3.3: $s_{i,0}^{\sigma} \| t_{i,0}^{\sigma} := \bigoplus_{j=1}^{d} (s_{i,3j}^{\sigma} \| t_{i,3j}^{\sigma})$.

3.4: $s_{i,1}^{\sigma} \| t_{i,1}^{\sigma} := \bigoplus_{j=1}^{d} (s_{i,3j+1}^{\sigma} \| t_{i,3j+1}^{\sigma})$.

3.5: $s_{i,2}^{\sigma} \| t_{i,2}^{\sigma} := \bigoplus_{j=1}^{d} (s_{i,3j+2}^{\sigma} \| t_{i,3j+2}^{\sigma})$.

3.6: Invoke $\Pi_{\text{rDPF-CW}}$ with party $\bar{\sigma}$:
$\text{CW}_i \leftarrow \Pi_{\text{rDPF-CW}}(i, [\alpha_i]_{\bar{\sigma}}, r_i^{\bar{\sigma}}, (s_{i,j}^{\bar{\sigma}} \| t_{i,j}^{\bar{\sigma}})_{j \in \{0,1,2\}})$.

3.7: **foreach** $j \in [d-1]$:

3.7.1: $(s_{i,3j}^{\sigma} \| \hat{t}_{i,3j}^{\sigma} \| \hat{s}_{i,3j+1}^{\sigma} \| \hat{t}_{i,3j+1}^{\sigma} \| \hat{s}_{i,3j+2}^{\sigma} \| \hat{t}_{i,3j+2}^{\sigma}) := (s_{i,3j}^{\sigma} \| \hat{t}_{i,3j}^{\sigma} \| s_{i,3j+1}^{\sigma} \| \hat{t}_{i,3j+1}^{\sigma} \| s_{i,3j+2}^{\sigma} \| \hat{t}_{i,3j+2}^{\sigma}) \oplus (\hat{t}_{i-1,j}^{\sigma} \cdot \text{CW}_i)$.

3: $\text{pp} := (\text{CW}_1, \dots, \text{CW}_n)$.

4: $K_A := (\text{pp}, s_{0,0}^0 \| 0), K_B := (\text{pp}, s_{0,0}^1 \| 1)$.

5: **return** $(K_A, K_B)$.

**Fig. 9:** Instantiation of rDPF Distributed Key Generation Protocol.

6 Cryptanalysis and Parameter Selection

In this section, we discuss attacks against our instantiation of QA-SD(c, t, G). We provide a Sage-Math [S+24] script to help select a concrete choice of parameters based on our analysis. In practice,
Ideal Functionality $\mathcal{F}_{\text{Output-CW}}$

PARAMETERS:

- The functionality interacts with a party $P_\sigma$ and an adversary $\mathcal{A}$.

- Pseudorandom generator $G: \{0, 1\}^\lambda \to (\mathbb{F}_4)^{3^t}$.

FUNCTIONALITY:

1. Wait for input $((\llbracket \alpha_i \rrbracket_{\bar{\sigma}})_{i \in [t]}, \llbracket \beta \rrbracket_{\bar{\sigma}}, s^{\bar{\sigma}}) \in (\mathbb{F}_3)^t \times \mathbb{F}_4 \times \{0, 1\}^{\lambda}$ from $\mathcal{A}$.

2. Wait for input $((\llbracket \alpha_i \rrbracket_{\sigma})_{i \in [t]}, \llbracket \beta \rrbracket_{\sigma}, s^{\sigma}) \in (\mathbb{F}_3)^t \times \mathbb{F}_4 \times \{0, 1\}^{\lambda}$ from party $P_\sigma$.

3. Set $\alpha_i := [\alpha_i]_0 + [\alpha_i]_1 \in \mathbb{F}_3$, $\alpha := \sum_{i=1}^t \alpha_i 3^{i-1} \in [3^t]$, $\beta := [\beta]_0 + [\beta]_1 \in \mathbb{F}_4$.

4. $\text{CW}_t \leftarrow e_\alpha \cdot \beta \oplus G(s^0) \oplus G(s^1)$, where $e_\alpha \in (\mathbb{F}_4)^{3^t}$ is the $\alpha$-th indicator vector.

5. Output $\text{CW}_t$ to $P_\sigma$ and $\mathcal{A}$.

<caption>Fig. 10: Ideal functionality $\mathcal{F}_{\text{Output-CW}}$ for computing the output correct word with message $\beta$.</caption>

Protocol $\Pi_{\text{Output-CW}}$

PARAMETERS:

- There are two parties $\sigma, \bar{\sigma} \in \{0, 1\}$ with input $((\llbracket \alpha_i \rrbracket_\sigma)_{i \in [t]} \in (\mathbb{F}_3)^t, \llbracket \beta \rrbracket_\sigma \in \mathbb{F}_4, s^\sigma \in \{0, 1\}^\lambda)$.

- An instantiation of chosen $(\binom{1}{3})$-OT.

- Pseudorandom generator $G: \{0, 1\}^\lambda \to (\mathbb{F}_4)^{3^t}$.

PROTOCOL:

For each party $\sigma \in \{0, 1\}$, for $i \in [t]$:

1. Sample $z_i^\sigma \leftarrow_R (\mathbb{F}_4)^{3^i}$.

2. Define

$$C_{i,0}^{\sigma} = (\llbracket \beta \rrbracket_{\sigma}, 0, 0) \oplus z_{i}^{\sigma} \in (\mathbb{F}_4)^{3^i},$$

$$C_{i,1}^{\sigma} = (0, \llbracket \beta \rrbracket_{\sigma}, 0) \oplus z_{i}^{\sigma} \in (\mathbb{F}_4)^{3^i},$$

$$C_{i,2}^{\sigma} = (0, 0, \llbracket \beta \rrbracket_{\sigma}) \oplus z_{i}^{\sigma} \in (\mathbb{F}_4)^{3^i},$$

$$M_0^{\sigma} = (C_{i,0}^{\sigma}, C_{i,1}^{\sigma}, C_{i,2}^{\sigma}), \quad M_1^{\sigma} = (C_{i,1}^{\sigma}, C_{i,2}^{\sigma}, C_0^{\sigma}), \quad M_2^{\sigma} = (C_{i,2}^{\sigma}, C_{i,0}^{\sigma}, C_{i,1}^{\sigma})$$

3. Invoke $(\binom{1}{3})$-OT with party $\bar{\sigma}$ as follows:

- Party $\bar{\sigma}$ plays the role of the sender with inputs $M_{\llbracket \alpha_i \rrbracket_{\bar{\sigma}}}^{\bar{\sigma}}$.

- Party $\sigma$ plays the role of the receiver and inputs $[\alpha_i]_\sigma \in \mathbb{F}_3$.

- Party $\sigma$ gets $M_{\llbracket \alpha_i \rrbracket_{\sigma}}^{\bar{\sigma}} [\llbracket \alpha_i \rrbracket_{\sigma}] \in (\mathbb{F}_4)^{3^i}$ while party $\bar{\sigma}$ gets nothing.

4. Define $[\beta]_\sigma := M_i^{\bar{\sigma}} [\llbracket \alpha_i \rrbracket_\sigma] \oplus z_i^\sigma \in (\mathbb{F}_4)^{3^i}$.

Output $[\text{CW}]_t := [\beta]_\sigma \oplus G(s^\sigma)$.

<caption>Fig. 11: Instantiation of $\mathcal{F}_{\text{Output-CW}}$ for computing the last correction words with constraint $\beta$.</caption>

we consider $c = 4, t = 27$ to achieve way more than 128 bits of security.<fnref n="17" /> The spirit of the attack which we describe here was already described in [BCCD23], but we give a more in-depth analysis. As a result of this deeper analysis, we show that the parameters considered in [BCCD23] do not achieve the claimed 128 bits of security, and instead achieve closer to 100 bits of security in practice.

<footnote n="17">¹⁷ For $c = 4, t = 27$ our script estimates 203 bits of security.</footnote>
## 6.1 Model of attack

In the following, we focus on attacks on QA-SD(c, t, G) over the finite field $F_q$. Everything that we describe applies to any $q$, but we will focus on $q = 4$ when deriving parameters. Our goal is to distinguish pairs $((a_1, \dots, a_{c-1}), s := e_0 + a_1e_1 + \dots + aCe_c)$ from the uniform distribution over $F_q[G]^c \times F_q[G]$, where $a_i \leftarrow \mathbb{F}_q[G]$, and $e_i$ are sparse elements of $F_q[G]$ with Hamming weight $t$. As mentioned in Section 3.2, the search version of QA-SD is equivalent to solving a decoding problem of the form

$$ (I \mathbf{A}_1 \dots \mathbf{A}_{c-1}) \begin{pmatrix} \mathbf{e}_0 \\ \vdots \\ \mathbf{e}_{c-1} \end{pmatrix} = \mathbf{s}, $$

where $\mathbf{A}_i$ is the matrix representation of the multiplication by element $a_i$ with respect to the basis given by $G$, for some arbitrary ordering of $G$, and $e_i$ are sparse vectors of Hamming weight $t$. In particular, the error vector is split into $c$ blocks of weight $t$. This is standard when dealing with structured variants of the decoding problem. This $c$-split structure has recently received renewed attention since it is also used in the NIST submission SDitH [AMFG+23] (for unstructured codes). The hardness of this variant can be estimated using the following theorem from [FJR22].

**Theorem 14 ([FJR22, Theorem 1]).** Let $n, k, w$ be positive integers such that $n > k, n > w$, and $c$ divides both $w$ and $n$. If there is an algorithm solving a random instance of the $c$-split decoding problem with code length $n$, dimension $k$ and $w$ errors, in time $T$ and with probability $\varepsilon_c$, then there exists an algorithm which solves a random instance of the standard decoding problem with the same parameters, in time $T$, and with probability $\varepsilon_1$ with

$$ \varepsilon_1 \ge \frac{\binom{n/c}{w/c}^c}{\binom{n}{w}} \cdot \varepsilon_c. $$

With Theorem 14 in hand, one might contend that the complexity of solving a $c$-split variant of the decoding problem cannot be lower than the best complexity for solving the usual syndrome decoding problem, times $(\binom{n/c}{w/c})^c / (\binom{n}{w})$. When choosing parameters, we make sure that this lower bound is beyond the targeted security level.

**Remark 15.** This lower bound has been updated in [CHT23] when taking the number of solutions into account. However, in our low noise regime, there is only one solution to the decoding problem with overwhelming probability, and in this situation, the two bounds coincide.

**Remark 16.** In practice, no decoding algorithm currently makes use of the $c$-split structure, and taking into account the penalty given by Theorem 14 gives overly conservative parameters. Note also that according to [ES23], we are on a high rate regime which seems to be harder for this kind of regular or split structure.

In our setting, the code rate is $1 - 1/c$ which is always bounded away from $1/2$. Therefore, generic attacks on LPN such as Arora-Ge [AG11] or BKW [BKW03], which require a very low code-rate, do not apply. In other words, we will only consider attacks against the decoding problem. Nevertheless, our instance is far from being generic. Indeed, the quasi-abelian structure gives more power to the adversary. First, the adversary can apply the DOOM strategy from [Sen11] to get a $\sqrt{|G|}$ speed-up over any decoding algorithm. Second, the additional structure allows an attacker to reduce their sample modulo some ideal of $F_q[G]$ to obtain a smaller instance of the decoding problem, with the hope that the noise rate does not grow too much. As already observed in [BCCD23], the best possible choices arise from quotients of $G$ and are known as folding attacks. They will be precisely analyzed in Section 6.3. In short, the folding operator with respect to a subgroup $H$ will send a code of length $c|G|$ to a code of length $c|G/H|$, while keeping the code-rate constant. On the other hand, the noisy vector will still be $c$-split (with blocks of size $|G/H|$), but the number of error coordinates in each block might decrease due to collisions. In other words, the noise is upper bounded by $t$ on each block.

**Attack Strategy.** The general idea of folding attacks to solve QA-SD(c, t, G) consists in picking some subgroup $H$, applying the folding operator with respect to $H$ and run a generic decoding algorithm on this smaller instance. Therefore, we need to choose the parameters such that generic
decoding algorithms against all folded instances remain beyond the targeted security parameter, even considering the loss induced by the c-split structure, and the $\sqrt{|G|/|H|}$ speed-up from the DOOM strategy. In general, this folding strategy will only be helpful for large enough subgroups $H$ (yielding small instances of the decoding problem). Nevertheless, for this approach to be relevant, we also need the number of errors to remain below the Gilbert-Varshamov (GV) bound of the folded instance, which ensures on average the uniqueness of the solution. Recall that for a code of rate $R$, the GV bound is defined as $\delta_{GV} = h_q^{-1}(1-R)$ where $h_q(x) := -x \log_q\left(\frac{x}{q-1}\right) - (1-x)\log_q(1-x)$ for $x \in (0, 1-1/q)$, is the q-ary entropy function. It is well-known that this provides a threshold for the number of solutions on a random instance $(H, s)$ of the decoding problem of a code of length $n$ and at distance $w$: when $w < n\delta_{GV}$, then there will be at most one solution with overwhelming probability over the choices of $H$, while when $w > n\delta_{GV}$ there will be exponentially many solutions, even when $s$ was picked uniformly at random (see [Deb23, Chapter 2]). In particular, if the number of errors in the folded instance is beyond the GV bound, then we need to lift each of those exponentially many putative solutions back to the original decoding problem to see whether it is an actual solution, or not. Doing so is equivalent to specifying a small number of unknowns in the linear system coming from the original syndrome decoding instance (see [CT19, Section IV]), and this strategy is far less efficient than solving a single decoding problem for a larger code-length. Note that finding a solution to a folded instance below the GV bound is enough to provide a distinguisher between an instance of QA-SD and a uniformly random vector, thus breaking the security of $\mathbb{F}_4$OLEAGE, since we only need to solve the decisional variant of QA-SD.

**Improvement.** In Section 6.3 we give a precise analysis of the probability distribution of the weight of the folded error. Since the initial error is extremely sparse, the weight of the folded error will be very close to that of the initial error with overwhelming probability (since there will be very few collisions). However, we show how an attacker can bet that the folded error has a much smaller weight $w_0$ than expected, which happens with some exponentially small probability $p_{w_0}$. They can then benefit from the fact that our instantiation has an extremely large number of potential subgroups $H$ to run $\frac{1}{p_{w_0}}$ algorithms tailored for decoding $w_0$ errors, resulting in an attack which brings the security of the parameters chosen in [BCCD23] down to roughly 100 bits instead of the targeted 128.

*Remark 17 (Regular noise).* For the optimized variants of our PCG, we also put an additional structure on the error term. Beyond being *c*-split, it is in fact *regular*, namely it is the concatenation of $t$ unit vectors. This variant has been introduced for building the hash function FSB [AFS03] which was submitted to the SHA-3 competition and was subsequently analyzed in [FGS07, BLPS11]. In general, it is not known to induce a significant weakness, however, it has not undergone the same thorough analysis that the standard syndrome decoding problem has gone through. This regular variant has recently become more popular due to many works on signatures and secure computation [HOSS18b, BCGI18, BCG+19b, BCG+20b, BCG+22, CCJ23, BCCD23]. We note that Theorem 14 is not tight in the regular case, and it would be overly conservative to consider this loss here. More precisely, every work that really targets the regular variant of syndrome decoding shows that the code rate needs to be rather small for this variant to have an impact on the security [BØ23, ES23]. The latter reference even argues that regular syndrome decoding is *harder* than standard syndrome decoding for in the high code-rate regime (see [ES23, Figure 1]), which is precisely our setting.

## 6.2 Generic decoding algorithms

Generic attacks against the decoding problem are divided into two families, which we summarize here.

**Information Set Decoders (ISD).** Starting from Prange's seminal work [Pra62], Information Set Decoding represents the main technique to solve the decoding problem. They have been extensively studied over the past 60 years [Pra62, Ste89, Wag02, MMT11, BJMM12, MO15, BM18, DEEK24], and in general their complexity is exponential in the number of error coordinates. However, most analyses were conducted over the binary field, in order to improve on the exponent. In particular, as far as we know, there is no precise analysis of the concrete, non asymptotic, efficiency over larger fields $\mathbb{F}_q$. We note though that the most recent algorithms (starting from [MO15]), have prohibitive hidden constants, which make them less practical [Hir16]. We give an overview of ISD algorithms in Appendix C.
**Dual attacks.** Up until recently, Information Set Decoding algorithms were considered to be the best algorithms to solve the generic decoding problem. However, another strategy known as statistical decoding or dual attacks, has been introduced in [Jab01, Ove06] and were greatly improved in the past few years [DT17, CDMT22, MT23, CDMT24]. Most recent dual attacks even outperform ISD algorithms in some regimes. Nevertheless, those improvements are only apparent for codes of the rate below 1/2 [CDMT24, Figure 1]. In particular, we will not consider them in our high code-rate regime.

## 6.3 Analysis of Folding attacks

In general, there are very few known ways in which an attacker can exploit the structure of variants of the decoding problem to get a significant advantage. In fact, it is a longstanding open problem in algebraic coding theory to design a generic decoder for quasi-abelian codes [Wil21]. Moreover, the authors of [BCCD23] proved that our particular instantiation of QA-SD comes with a search-to-decision reduction. All of that argues in favor of the hardness of QA-SD(c, t, G). Nevertheless, in the case of QA-SD, an attacker can use one of the many subgroups of G to get a smaller instance, with the hope of getting an easier decoding problem. In this section, we give a precise analysis of such folding attacks.

### 6.3.1 The Folding Operation

Let $\mathbb{H}$ be a subgroup of $\mathbb{G}$. The canonical projection $\mathbb{G} \to \mathbb{G}/\mathbb{H}$ induces a morphism of algebras

$$ \pi_{\mathbb{H}}: \left\{ \sum_{g \in \mathbb{G}} a_g g \mapsto \sum_{\bar{g} \in \mathbb{G}/\mathbb{H}} \left( \sum_{h \in \mathbb{H}} a_{g+h} \right) \bar{g}. \right\} $$

Represented as a vector of length $|\mathbb{G}|$, an element $x \in \mathbb{F}_q[\mathbb{G}]$ can also be seen as a collection of $|\mathbb{G}/\mathbb{H}|$ interleaved subvectors of length $|\mathbb{H}|$ indexed by each coset of $\mathbb{H}$. The operation $\pi_{\mathbb{H}}$ simply consists of summing up all the entries of each subvector. An illustration is given on Figure 12.

<figure><img src="image_5.png" /><figcaption>**Fig. 12:** Example representation of $\pi_{\mathbb{H}}$ for a group $\mathbb{G}$ of size 9 and a subgroup $\mathbb{H}$ of size 3. Each coset of $\mathbb{H}$ is represented by a different color. Note that in general, there is no reason to have this regular pattern.</figcaption></figure>

Given an element $\mathbf{y} := (y_1, \dots, y_c) \in \mathbb{F}_q[\mathbb{G}]^c$, we define the folding with respect to $\mathbb{H}$ as $\text{Fold}_{\mathbb{H}}(\mathbf{y}) := (\pi_{\mathbb{H}}(y_1), \dots, \pi_{\mathbb{H}}(y_c)) \in \mathbb{F}_q[\mathbb{G}/\mathbb{H}]^c$. Now, consider an instance $(\mathbf{a}, (\langle \mathbf{a}, \mathbf{e} \rangle + e_0))$ of QA-SD(c, t, G). Applying $\pi_{\mathbb{H}}$ on the syndrome yields

$$ \pi_{\mathbb{H}} \left( e_0 + \sum_{i=1}^{c-1} a_i e_i \right) = \pi_{\mathbb{H}}(e_0) + \sum_{i=1}^{c-1} \pi_{\mathbb{H}}(a_i) \pi_{\mathbb{H}}(e_i) \in \mathbb{F}_q[\mathbb{G}/\mathbb{H}], $$

which is nothing but the syndrome of Fold$_{\mathbb{H}}(\mathbf{e})$ with respect to the matrix represented by Fold$_{\mathbb{H}}(1, \mathbf{a})$. In other words, starting from a decoding problem with code-length $c|\mathbb{G}|$ and dimension $(c-1)|\mathbb{G}|$, we build a smaller decoding problem with code-length $c|\mathbb{G}/\mathbb{H}|$. The main observation is that, doing so, we did not change the code-rate, which remains equal to $1 - 1/c$. On the other hand, the Hamming weight of the folded error might be slightly below the original one. The goal of this section is to carefully estimate this weight. To do so, we will give a precise analysis of the probability distribution
of $w_H(\text{Fold}_{\mathbb{H}}(\mathbf{x}))$ when $\mathbf{x} := (x_1, \dots, x_c) \in \mathbb{F}_q[\mathbb{G}]^c$ is such that the $x_i$'s are independent and uniformly distributed over the elements of Hamming weight $t$. This distribution is nothing but the $c$-fold convolution of the probability distribution of the weights of a single component, which we derive in Section 6.3.2. Our analysis is similar to that of [CT19], written in the language of group algebras.<fnref n="18" />

### 6.3.2 Weight distribution of the image of the folding

For $u \in \{0, \dots, t\}$ and $\mathbb{H}$ a subgroup of $\mathbb{G}$, denote by

$$A_{\mathbb{H}}(t, u) := \left| \left\{ x \in \mathbb{F}_q[\mathbb{G}] \mid w_H(x) = t \text{ and } w_H(\pi_{\mathbb{H}}(x)) = u \right\} \right|.$$

When $x$ is uniformly chosen amongst the elements of the group algebra $\mathbb{F}_q[\mathbb{G}]$ of Hamming weight $t$, then $\text{Pr}_x[w_H(\pi_{\mathbb{H}}(x)) = u] = \frac{A_{\mathbb{H}}(t, u)}{\binom{|\mathbb{G}|}{t} (q-1)^t}$. In other words, the goal is to compute $A_{\mathbb{H}}(t, u)$.

Let $x \in \mathbb{F}_q[\mathbb{G}]$ of Hamming weight $t$ and let $\ell := |\mathbb{H}|$. We can view $x$ as an interleaving of $|\mathbb{G}/\mathbb{H}|$ subvectors of length $\ell$ corresponding to the different cosets of $\mathbb{H}$, such that the weights of the subvectors form a partition of $t$ into parts of size at most $\ell$. For a given element $x$ of weight $t$, we call the corresponding partition of $t$ the signature of $x$. By definition, a coordinate of $\pi_{\mathbb{H}}(x)$, indexed by some coset $g_0 + \mathbb{H}$, is zero if and only if the corresponding entries of $x$ sum up to 0, i.e., if and only if the word $(x_{g_0+h})_{h \in \mathbb{H}} \in \mathbb{F}_q^\ell$ belongs to the $[\ell, \ell-1]_q$-parity code denoted by $\mathcal{C}_\ell$. In particular, $A_{\mathbb{H}}(t, u)$ does not depend on the specific subgroup $\mathbb{H}$, but rather on its order $\ell$.

For $\omega \in \{0, \dots, \ell\}$, let $\nu(\omega, \ell)$ be the number of codewords of $\mathcal{C}_\ell$ of Hamming weight $\omega$ and let $P_{\nu, \ell} := \sum_{\omega=0}^\ell \nu(\omega, \ell) X^\omega$ be the weight enumerator of $\mathcal{C}_\ell$. Similarly, we denote by $P_{\theta, \ell} := \sum_{\omega=0}^\ell \theta(\omega, \ell) X^\omega$ the weight enumerator of the complement $\mathbb{F}_q^\ell \setminus \mathcal{C}_\ell$. Let $a \in \mathbb{F}_q[\mathbb{G}/\mathbb{H}]$ be of weight $u$. Without loss of generality, we assume that the $u$ nonzero positions of $a$ correspond to its first $u$ entries. Then, given a partition $(i_1, \dots, i_{|\mathbb{G}/\mathbb{H}|})$ of $t$ into parts of size at most $\ell$, the number of elements $x \in \mathbb{F}_q[\mathbb{G}]$ having this signature and which are mapped to $a$ is exactly

$$\prod_{j=1}^{|\mathbb{G}/\mathbb{H}|} \left( \theta(i_j, \ell) \mathbb{1}_{a_{i_j} \neq 0} + \nu(i_j, \ell) \mathbb{1}_{a_{i_j}=0} \right) = \prod_{j=1}^u \theta(i_j, \ell) \prod_{j=u+1}^{|\mathbb{G}/\mathbb{H}|} \nu(i_j, \ell).$$

In other words, we have

$$A_{\mathbb{H}}(t, u) = \binom{|\mathbb{G}/\mathbb{H}|}{u} \sum_{\substack{i_1 + \dots + i_{|\mathbb{G}/\mathbb{H}|} = t \\ 0 \le i_j \le \ell}} \left( \prod_{j=1}^{u} \theta(i_j, \ell) \prod_{j=u+1}^{|\mathbb{G}/\mathbb{H}|} \nu(i_j, \ell) \right),$$

which is nothing but the coefficient of $X^t$ in the polynomial $\binom{|\mathbb{G}/\mathbb{H}|}{u} P_{\theta, \ell}^u(X) P_{\nu, \ell}^{|\mathbb{G}/\mathbb{H}|-u}(X)$, which we denote by $[X^t] (\binom{|\mathbb{G}/\mathbb{H}|}{u} P_{\theta, \ell}^u(X) P_{\nu, \ell}^{|\mathbb{G}/\mathbb{H}|-u}(X))$. We can then deduce the following proposition.

**Proposition 18.** Let $0 \le t \le |\mathbb{G}|$ and $0 \le u \le \min(t, |\mathbb{G}/\mathbb{H}|)$. When $x$ is uniformly distributed over the elements of $\mathbb{F}_q[\mathbb{G}]$ of Hamming weight $t$, then

$$\text{Pr}_x[w_H(\pi_{\mathbb{H}}(x)) = u] = \frac{\binom{|\mathbb{G}/\mathbb{H}|}{u} [X^t] (P_{\theta, \ell}^u(X) P_{\nu, \ell}^{|\mathbb{G}/\mathbb{H}|-u}(X))}{\binom{|\mathbb{G}|}{t} (q-1)^t}.$$

The following lemma, a corollary of MacWilliam's identity (see [MS86]), gives the closed formulas of $P_{\nu, \ell}$ and $P_{\theta, \ell}$.

**Lemma 19 ([CT19, Lemma 1]).** We have

$$P_{\nu, \ell}(X) = \frac{1}{q} \left( (1 + (q-1)X)^\ell + (q-1)(1-X)^\ell \right),$$

and

$$P_{\theta, \ell}(X) = \frac{q-1}{q} \left( (1 + (q-1)X)^\ell - (1-X)^\ell \right).$$

<footnote n="18">¹⁸ In [CT19, Proposition 3], the authors forgot a $q-1$ factor, which we fix in our analysis. Note that this does not impact the results of [CT19] since their actual setting was for $q=2$.</footnote>
### 6.3.3 Choice of the folding subgroup

The choice of the subgroup $\mathbb{H}$ is motivated by the targeted length $c|\mathbb{G}/\mathbb{H}|$ of the folded code (we discuss in Section 6.4 folding with respect to several subgroups). As mentioned above, we need $t < \delta_{GV}|\mathbb{G}/\mathbb{H}|$ for this procedure to be relevant, where $\delta_{GV}$ is the GV bound at rate $1-1/c$. In our setting, $\mathbb{G}$ is of the form $(\mathbb{Z}/3\mathbb{Z})^n$ and therefore $\mathbb{H}$ will be of the form $(\mathbb{Z}/3\mathbb{Z})^{n'}$. In particular, $|\mathbb{G}/\mathbb{H}| = 3^{n-n'}$ should be such that $c \cdot t \le c \cdot \delta_{GV}3^{n-n'}$. In practice, choosing $n' = n - \lceil \log_3 (t/\delta_{GV}) \rceil$, or $n - \lceil \log_3 (t/\delta_{GV}) \rceil - 1$ when $t$ is particularly small, yields the best complexity.

## 6.4 Improving the attack: Folding for several subgroups

Since we chose $\mathbb{G}$ of the form $(\mathbb{Z}/3\mathbb{Z})^n$, there are many different subgroups of given order $3^{n'}$. More precisely, they are in one-to-one correspondence with the $n'$-dimensional subspaces of $\mathbb{F}_3^n$: there are $(\binom{n}{n'})_3$ of them. Instead of picking one particular subgroup and running the best generic decoding algorithm on the folded instance, an attacker could bet that the error has a much smaller weight $\omega_0$. They could then run the best decoding algorithm, aborting the procedure when the number of iterations exceeds that required to decode $\omega_0$ errors, and then pick another subgroup. On average, this procedure will allow to decode in time $\frac{\text{Cost}_{\text{Decoding}}(\omega_0) + \text{Cost}_{\text{Folding}}}{\text{Pr}[w_H(\text{Fold}_{\mathbb{H}}(x)) = \omega_0]}$, where $\text{Cost}_{\text{Decoding}}$ is the complexity of the best decoding algorithm for the target weight $\omega_0$ in the folded code, and $\text{Cost}_{\text{Folding}}$ is the cost of computing the folding operation, i.e., $\text{Cost}_{\text{Folding}}$ is exactly the length of the initial code. In order to run the attack, it suffices to choose the best $\omega_0$ which minimizes this ratio to get the best complexity. This attack is much more efficient for small values of $c$, that is why we chose $c = 5$ in our setting. This allows us to maintain small parameters while achieving more than 128 bits of security (while still keeping some security margin).

### 6.4.1 Parameter Estimation and Revaluation of [BCCD23]

We provide a SageMath [S+24] script to help choose a set of concrete parameters for QA-SD. It computes the probability distribution of the weight of the folded error and computes the cost of the best attack. It also takes into account the previous attack.

As a by-product, we can use it to give a new estimation of the security of [BCCD23]. Results are given in Section 6.4.1. It shows that we would need to significantly increase the value of $t$ in order to achieve 128 bits of security.

<table><caption>**Table 2:** Reestimation of the security for the parameters given in [BCCD23]. They were considered to yield more than 128 bits of security, they were even considered to be conservative. Note that in [BCCD23], all the parameters were for $q = 3$. Here $t$ is the number of errors per block, while in [BCCD23] it was the total number of errors. $n_{fold}$ and $k_{fold}$ are respectively the length and dimension of the folded code. $N_{iter}$ is the number of different foldings necessary to run the attack, and $\omega_0$ is the optimal target weight.</caption><thead><tr><th>n</th><th>c</th><th>t</th><th>(n<sub>fold</sub>, k<sub>fold</sub>, ω<sub>0</sub>)</th><th>(N<sub>iter</sub>, Cost<sub>Decoding</sub>)</th><th>Number of subgroups</th><th>Actual security</th></tr></thead><tbody><tr><td>25</td><td>4</td><td>16</td><td>(2048, 1536, 54)</td><td>(2<sup>14</sup>, 2<sup>89</sup>)</td><td>2<sup>145</sup></td><td>118</td></tr><tr><td>30</td><td>4</td><td>16</td><td>(2048, 1536, 54)</td><td>(2<sup>14</sup>, 2<sup>89</sup>)</td><td>2<sup>190</sup></td><td>118</td></tr><tr><td>35</td><td>4</td><td>16</td><td>(2048, 1536, 54)</td><td>(2<sup>14</sup>, 2<sup>89</sup>)</td><td>2<sup>235</sup></td><td>118</td></tr></tbody></table>

# 7 Implementation and Evaluation

We implement $\mathbb{F}_4$OLEAGE in C (v15.0.0) as a library that consists of two main components: (1) an optimized implementation of the ternary DPF construction and (2) an implementation of the FFT over $\mathbb{F}_4$. The open-source code for our $\mathbb{F}_4$OLEAGE PCG benchmarks is available online.<fnref n="19" />

<footnote n="19">¹⁹ https://github.com/sachaservan/FOLEAGE-PCG.</footnote>
**Implementation details.** Our DPF implementation takes advantage of the AES-NI instruction to implement a fast PRG $G$ using fixed-key AES (from the OpenSSL library [Ope]) and the Davies-Meyer transform. We experimented with using the half-tree optimization of $[GYW^{+23}]$. However, we observed a minimal performance gains (2-4%) from this optimization when applied to a ternary tree. This is because the half-tree optimization is tailored to the binary tree DPF construction where it can shave a larger fraction of total AES calls.<fnref n="20" /> We implement the recursive FFT over $\mathbb{F}_4$ described in Section 4.3 and perform the FFT in parallel by packing all the coefficients into one machine word (for our parameters, we will require 16 FFTs, so we can perform them in parallel using a `uint32` type for packing). While the FFT could possibly be optimized further using an iterative algorithm and taking advantage of AVX instructions, the simplicity of the recursive algorithm coupled with the parallel packing makes it sufficiently fast for $\mathbb{F}_4$OLEAGE. This is especially true given that the DPF evaluations end up being the dominant cost (roughly 70% of the total computation). We do not implement the distributed seed generation protocol given that it consists of black-box invocations of any one-out-of-three OT. However, we do estimate the concrete performance and communication costs of distributed seed generation by benchmarking the `libOTe` library on state-of-the-art OT protocols [RR].

**Benchmarks.** We perform our benchmarks using AWS `c5.metal` (3.4GHz CPU) and `t2.large` instances. All experiments are averaged across ten trials and evaluated on a single core. To gain a better understanding of the overhead involved with each component, we start by benchmarking the SPFSS (sum of many DPFs) and FFT implementation separately and report the results in Tables 3 and 4. Concretely, if we are packing $3^n$ coefficients over $\mathbb{F}_4$, we want the output of the DPF to be close to a power of 3. To achieve this, we terminate 5 levels early and pack 512 elements of $\mathbb{F}_4$ in the virtual leaves by having the DPF output be a 1024 bit block. Therefore, the key size of each DPF is $3 \cdot 128 \cdot (n-5) + 128 + 2 \cdot 512$ when using AES with 128-bit keys. We report the SPFSS benchmarks in Table 3 when evaluating the sum of 730 DPFs (this corresponds to the $t = 27$ regime in Figure 1, since the SPFSS needs to be instantiated with $t^2 = 729$ DPFs). When evaluating the SPFSS, we observe a roughly $1.8 \times$ reduction in computation time over evaluating just one DPF. This is due to better cache performance when evaluating many DPFs and working over the same memory allocation to evaluate consecutive DPFs. Our choice of DPF range $3^{11}$, $3^{13}$, and $3^{15}$ correspond to the size of a regular noise block when $D = 3^{14}$, $D = 3^{16}$, and $D = 3^{18}$, respectively (see Table 5).

<table><caption>**Table 3:** Performance of our SPFSS (for the sum of 730 DPFs) on two EC2 instances and comparison to the raw AES computation time required for the PRG evaluations.</caption><thead><tr><th>Range<br>(elements of F<sub>4</sub>)</th><th>SPFSS.Gen<br>(c5.metal | t2.large)</th><th>SPFSS.FullEval<br>(c5.metal | t2.large)</th><th>AES<br>(c5.metal | t2.large)</th><th>Key Size<br>(per party)</th></tr></thead><tbody><tr><td>3<sup>11</sup></td><td>5 ms | 11 ms</td><td>26 ms | 39 ms</td><td>18 ms | 27 ms</td><td>315 kB</td></tr><tr><td>3<sup>13</sup></td><td>7 ms | 13 ms</td><td>260 ms | 364 ms</td><td>174 ms | 253 ms</td><td>385 kB</td></tr><tr><td>3<sup>15</sup></td><td>8 ms | 16 ms</td><td>2357 ms | 3272 ms</td><td>1526 ms | 2229 ms</td><td>456 kB</td></tr></tbody></table>

**Benchmarking our PCG.** Next, we benchmark the performance of the PCG from Figure 1 on various parameters. The parameter $D = 3^n$ determines the number of Beaver triples we generate in total. In contrast, the parameters $c$ (compression factor) and $t$ (noise weight) influence the size of the PCG key and evaluation time. Specifically, evaluating the PCG requires $(c \cdot t)^2$ calls to the DPF on domain size $D/t$ (due to regular noise) and $c(c+1)/2$ calls to the FFT (which we can parallelize by a factor of up to 32 using packing on 64-bit architectures). The DPF evaluation cost ends up being the dominant factor (approximately 70%) in the total computation. The FFT accounts for less than 5% of the total computation. Interestingly, *packing* the FFT (which requires computing a matrix transpose of dimension $c(c+1)/2 \times 3^n$ to translate from $c(c+1)/2$ polynomials to a packed representation suitable

<footnote n="20">²⁰ Since there are roughly $1/3$ nodes for which we can hope to shave AES calls in the ternary tree, but we can only shave one-out-of-three AES calls using the “half-tree” optimization in the ternary-tree case, we can only hope to save $1/3 \cdot 1/3 \approx 10\%$ of the AES computation time. However, given that AES calls are dominant but not the entire cost of the DPF (we also need to compute many XORs), we end up with roughly 2-4% savings. This could perhaps be optimized a bit further, but the performance savings would plateau at roughly 6%.</footnote>
<table><caption>**Table 4:** Performance of our FFT implementation over $\mathbb{F}_4$ on two different EC2 instances. Packing increases throughput almost linearly with the packing size. However, with a large number of variables (> 16), it is more efficient to use smaller packing values to avoid the increased memory usage from the recursive FFT function calls.</caption><thead><tr><th rowspan="2">Number of<br>Variables</th><th colspan="2">Packed FFT (4×)</th><th colspan="2">Packed FFT (16×)</th><th colspan="2">Packed FFT (32×)</th></tr><tr><th>(c5.metal | t2.large)</th><th></th><th>(c5.metal | t2.large)</th><th></th><th>(c5.metal | t2.large)</th><th></th></tr></thead><tbody><tr><td>14</td><td>20 ms</td><td>30 ms</td><td>21 ms</td><td>33 ms</td><td>28 ms</td><td>45 ms</td></tr><tr><td>16</td><td>180 ms</td><td>280 ms</td><td>213 ms</td><td>329 ms</td><td>312 ms</td><td>475 ms</td></tr><tr><td>18</td><td>1682 ms</td><td>2608 ms</td><td>2165 ms</td><td>3280 ms</td><td>4913 ms</td><td>7478 ms</td></tr></tbody></table>

for computing the FFT in parallel) accounts for 15% of the total computation! This motivates using small values of $c$, such as $c = 4$, as otherwise this transpose becomes the dominant cost in the entire PCG expansion. We leave exploring the possibility of implementing fast SIMD-based matrix-transpose algorithms (e.g., [TE76, AS20]) as a promising direction for future work, since it may allow using a smaller noise weight (e.g., $t = 9$) and larger $c$.

We set $t = 27$ since we need it to be a power of 3 (see Remark 5), and report the computational costs of the PCG for different values of $D$ in Table 5 and $c$. The choice of ($c = 4, t = 27$) corresponds to a conservative parameter choice based on our calculations in Section 6. To show the influence of $c$ on the performance, we also evaluate our PCG construction on $c = 3$, which corresponds to a more aggressive parameter choice. We observe a much smaller PCG seeds and better concrete performance with $c = 3$ compared to $c = 4$.

(a) Parameters: ($c = 4, t = 27$)

<table><thead><tr><th rowspan="2">D</th><th colspan="2">PCG.Expand</th><th>Key Size</th></tr><tr><th>(c5.metal | t2.large)</th><th></th><th>(per party)</th></tr></thead><tbody><tr><td>3<sup>14</sup></td><td>579 ms</td><td>890 ms</td><td>5.0 MB</td></tr><tr><td>3<sup>16</sup></td><td>5.9 s</td><td>8.4 s</td><td>6.2 MB</td></tr><tr><td>3<sup>18</sup></td><td>54.3 s</td><td>-</td><td>7.3 MB</td></tr></tbody></table>

(b) Parameters: ($c = 3, t = 27$)

<table><caption>**Table 5:** Performance of our PCG implementation on two different EC2 instances. We set the noise parameter to $t = 27$ and let $c = 4$ in the left table (our conservative parameter choice) and $c = 3$ in the right table (our aggressive parameter choice); these parameters are computed in Section 6. $D = 3^{18}$ ran out of memory on the t2.large.</caption><thead><tr><th rowspan="2">D</th><th colspan="2">PCG.Expand</th><th>Key Size</th></tr><tr><th>(c5.metal | t2.large)</th><th></th><th>(per party)</th></tr></thead><tbody><tr><td>3<sup>14</sup></td><td>346 ms</td><td>534 ms</td><td>2.8 MB</td></tr><tr><td>3<sup>16</sup></td><td>3.5 s</td><td>5.2 s</td><td>3.5 MB</td></tr><tr><td>3<sup>18</sup></td><td>32.1 s</td><td>-</td><td>4.1 MB</td></tr></tbody></table>

**Estimating setup costs.** We use the libOTe library [RR] to benchmark the state-of-the-art OT protocols. We run libOTe on localhost and evaluated both SoftSpoken OT [Roy22] and the RRT' silent OT [RRT23]. For SoftSpoken, we measured roughly 50,000,000 OT/s on the c5.metal machine and roughly 32,000,000 OT/s on the t2.large. For the RRT, we measure a throughput of nearly 7,000,000 on c5.metal and 4,000,000 on the t2.large. To run our distributed DPF key generation protocol, we require $n = 14$ (at $D = 3^{14}$) and $n = 18$ (at $D = 3^{18}$) rounds per DPF. All the $(ct)^2$ DPF keys can be computed in parallel. Therefore, in total, using our conservative parameters of $c = 4$ and $t = 27$, we require roughly 11,600 parallel calls to an OT functionality in $n$ rounds. Our aggressive parameters of $c = 3$ and $t = 27$ only require 6,561 parallel OT calls.
Acknowledgements

We thank the anonymous reviewers for helpful suggestions. We thank Peter Rindal for help with running the libOTe [RR] library, and Marcel Keller for answering our questions about Overdrive [KPR18]. We thank Elette Boyle and Matan Hamilis for several comments that helped us improve the presentation of the paper. Geoffroy Couteau, Clément Ducros, and Dung Bui were supported by the French *Agence Nationale de la Recherche* (ANR), under grant ANR-20-CE39-0001 (project SCENE), by the France 2030 ANR Project ANR22-PECY-003 SecureCompute, and by ERC grant OBELiSC (101115790). Dung Bui was supported by DIM Math Innovation 2021 (N°IRIS: 21003816) from the Paris Mathematical Sciences Foundation (FSMP) funded by the Paris Île-de-France Region. Clément Ducros was supported by the program "Investissement d'Avenir" launched by the French Government and implemented by ANR, with the ANR-21-CMAQ-0001, FQPS. Maxime Bombar was supported by the NWO Gravitation Project QSC. Alain Couvreur was supported by the French *Agence Nationale de la Recherche* (ANR) under grant ANR-21-CE39-0009-BARRACUDA, by the *plan France 2030* under the project ANR-22-PETQ-0008 and by Horizon-Europe MSCA-DN project *Encode*.

References

AAB<sup>+22a</sup>. C. Aguilar Melchor, N. Aragon, P. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Ghosh, S. Gueron, T. Güneysu, R. Misoczki, E. Persichetti, J. Richter-Brockmann, N. Sendrier, J.-P. Tillich, V. Vasseur, and G. Zémor. BIKE. Round 4 Submission to the NIST Post-Quantum Cryptography Call, v. 5.1, October 2022.

AAB<sup>+22b</sup>. C. Aguilar Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. Bos, J.-C. Deneuville, A. Dion, P. Gaborit, J. Lacan, E. Persichetti, J.-M. Robert, P. Véron, G. Zémor, and J. Bos. HQC. Round 4 Submission to the NIST Post-Quantum Cryptography Call, October 2022. https://pqc-hqc.org/.

ABD<sup>+16</sup>. C. Aguilar, O. Blazy, J.-C. Deneuville, P. Gaborit, and G. Zémor. Efficient encryption from random quasi-cyclic codes. Cryptology ePrint Archive, Report 2016/1194, 2016. https://eprint.iacr.org/2016/1194.

AFS03. D. Augot, M. Finiasz, and N. Sendrier. A fast provably secure cryptographic hash function. IACR Cryptology ePrint Archive, Report2003/230, 2003. http://eprint.iacr.org/.

AG11. S. Arora and R. Ge. New algorithms for learning in presence of errors. In *Automata, Languages and Programming, LNCS* 6755, pages 403–415. Springer Berlin Heidelberg, 2011.

AMBD<sup>+18</sup>. C. Aguilar-Melchor, O. Blazy, J.-C. Deneuville, P. Gaborit, and G. Zémor. Efficient encryption from random quasi-cyclic codes. *IEEE Transactions on Information Theory*, 64(5):3927–3943, 2018.

AMFG<sup>+23</sup>. C. Aguilar Melchor, T. Feneuil, N. Gama, S. Gueron, J. Howe, D. Joseph, A. Joux, E. Persichetti, T. Randrianarisoa, M. Rivain, and D. Yue. SDitH. Round 1 Additional Signatures to the NIST Post-Quantum Cryptography: Digital Signature Schemes Call, May 2023.

AS20. H. Amiri and A. Shahbahrami. SIMD programming using Intel vector extensions. *J. Parallel Distrib. Comput.*, 135(C):83–100, Jan 2020.

BC23. D. Bui and G. Couteau. Improved private set intersection for sets with small entries. In *PKC 2023, Part II, LNCS* 13941, pages 190–220. Springer, Heidelberg, May 2023.

BCCD23. M. Bombar, G. Couteau, A. Couvreur, and C. Ducros. Correlated pseudorandomness from the hardness of quasi-abelian decoding. In *CRYPTO 2023, Part IV, LNCS*, pages 567–601. Springer, Heidelberg, August 2023.

BCDL19. R. Bricout, A. Chailloux, T. Debris-Alazard, and M. Lequesne. Ternary syndrome decoding with large weight. In *SAC 2019, LNCS* 11959, pages 437–466. Springer, Heidelberg, August 2019.

BCG<sup>+19a</sup>. E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, P. Rindal, and P. Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In *ACM CCS 2019*, pages 291–308. ACM Press, November 2019.

BCG<sup>+19b</sup>. E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In *CRYPTO 2019, Part III, LNCS* 11694, pages 489–518. Springer, Heidelberg, August 2019.

BCG<sup>+20a</sup>. E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Correlated pseudorandom functions from variable-density LPN. In *61st FOCS*, pages 1069–1080. IEEE Computer Society Press, November 2020.

BCG<sup>+20b</sup>. E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl. Efficient pseudorandom correlation generators from ring-LPN. In *CRYPTO 2020, Part II, LNCS* 12171, pages 387–416. Springer, Heidelberg, August 2020.
BCG<sup>+</sup>22. E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, N. Resch, and P. Scholl. Correlated pseudorandomness from expand-accumulate codes. In *CRYPTO 2022, Part II*, LNCS 13508, pages 603–633. Springer, Heidelberg, August 2022.

BCGI18. E. Boyle, G. Couteau, N. Gilboa, and Y. Ishai. Compressing vector OLE. In *ACM CCS 2018*, pages 896–912. ACM Press, October 2018.

Bea92. D. Beaver. Efficient multiparty protocols using circuit randomization. In *CRYPTO'91*, LNCS 576, pages 420–432. Springer, Heidelberg, August 1992.

Bea96. D. Beaver. Correlated pseudorandomness and the complexity of private computations. In *28th ACM STOC*, pages 479–488. ACM Press, May 1996.

BGI15. E. Boyle, N. Gilboa, and Y. Ishai. Function secret sharing. In *Annual international conference on the theory and applications of cryptographic techniques*, pages 337–367. Springer, 2015.

BGI16. E. Boyle, N. Gilboa, and Y. Ishai. Function secret sharing: Improvements and extensions. In *ACM CCS 2016*, pages 1292–1303. ACM Press, October 2016.

BGV14. Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. New York, NY, USA, jul 2014. Association for Computing Machinery.

BJMM12. A. Becker, A. Joux, A. May, and A. Meurer. Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding. In *EUROCRYPT 2012*, LNCS 7237, pages 520–536. Springer, Heidelberg, April 2012.

BKW03. A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. *Journal of the ACM (JACM)*, 50(4):506–519, 2003.

BLPS11. D. J. Bernstein, T. Lange, C. Peters, and P. Schwabe. Faster 2-regular information-set decoding. In *Coding and Cryptology, Proceedings of IWCC, LNCS* 6639, pages 81–98. Springer, 2011.

BM18. L. Both and A. May. Decoding linear codes with high error rate and its impact for LPN security. In *Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018*, pages 25–46. Springer, Heidelberg, 2018.

BØ23. P. Briaud and M. Øygarden. A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions. In *EUROCRYPT 2023, Part V*, LNCS 14008, pages 391–422. Springer, Heidelberg, April 2023.

CCJ23. E. Carozza, G. Couteau, and A. Joux. Short signatures from regular syndrome decoding in the head. In *EUROCRYPT 2023, Part V*, LNCS 14008, pages 532–563. Springer, Heidelberg, April 2023.

CD23. G. Couteau and C. Ducros. Pseudorandom correlation functions from variable-density LPN, revisited. In *PKC 2023, Part II*, LNCS 13941, pages 221–250. Springer, Heidelberg, May 2023.

CDMT22. K. Carrier, T. Debris-Alazard, C. Meyer-Hilfiger, and J. Tillich. Statistical decoding 2.0: Reducing decoding to LPN. In *Advances in Cryptology - ASIACRYPT 2022*, LNCS. Springer, 2022.

CDMT24. K. Carrier, T. Debris-Alazard, C. Meyer-Hilfiger, and J. Tillich. Reduction from sparse lpn to lpn, dual attack 3.0. In *Advances in Cryptology - EUROCRYPT 2024*, LNCS. Springer, 2024.

CHT23. K. Carrier, V. Hatey, and J.-P. Tillich. Projective space stern decoding and application to sdith. *Cryptology ePrint Archive*, 2023.

CRR21. G. Couteau, P. Rindal, and S. Raghuraman. Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In *CRYPTO 2021, Part III*, LNCS 12827, pages 502–534, Virtual Event, August 2021. Springer, Heidelberg.

CT65. J. W. Cooley and J. W. Tukey. An Algorithm for the Machine Calculation of Complex Fourier Series. *Math. Comput.*, 19:297–301, 1965.

CT19. R. Canto-Torres and J. Tillich. Speeding up decoding a code with a non-trivial automorphism group up to an exponential factor. In *Proc. IEEE Int. Symposium Inf. Theory - ISIT 2019*, pages 1927–1931, 2019.

CTS16. R. Canto Torres and N. Sendrier. Analysis of Information Set Decoding for a Sub-linear Error Weight. In *Post-Quantum Cryptography - PQCrypto 2016*, Fukuoka, Japan, February 2016.

DA23. T. Debris-Alazard. Code-based cryptography: Lecture notes. arxiv:2304.03541, 2023.

Deb23. T. Debris-Alazard. Code-based cryptography: Lecture notes, 2023. https://arxiv.org/abs/2304.03541.

DEEK24. L. Ducas, A. Esser, S. Etinski, and E. Kirshanova. Asymptotics and improvements of sieving for codes. 2024.

DNNR17. I. Damgård, J. B. Nielsen, M. Nielsen, and S. Ranellucci. The TinyTable protocol for 2-party secure computation, or: Gate-scrambling revisited. In *CRYPTO 2017, Part I*, LNCS 10401, pages 167–187. Springer, Heidelberg, August 2017.

DPSZ12. I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In *CRYPTO 2012, LNCS* 7417, pages 643–662. Springer, Heidelberg, August 2012.

Ds17. J. Doerner and a. shelat. Scaling ORAM for secure computation. In *ACM CCS 2017*, pages 523–535. ACM Press, October / November 2017.
DT17. T. Debris-Alazard and J.-P. Tillich. Statistical decoding. In Proc. IEEE Int. Symposium Inf. Theory - ISIT 2017, pages 1798-1802, Aachen, Germany, June 2017.

Dum89. I. Dumer. Two decoding algorithms for linear codes. Probl. Inf. Transm., 25(1):17-23, 1989.

EGL82. S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. In CRYPTO'82, pages 205-210. Plenum Press, New York, USA, 1982.

ES23. A. Esser and P. Santini. Not just regular decoding: Asymptotics and improvements of regular syndrome decoding attacks. Cryptology ePrint Archive, 2023.

FGS07. M. Finiasz, P. Gaborit, and N. Sendrier. Improved Fast Syndrome Based Cryptographic Hash Functions. In ECRYPT Hash Workshop 2007, 2007.

FJR22. T. Feneuil, A. Joux, and M. Rivain. Syndrome decoding in the head: Shorter signatures from zero-knowledge proofs. In CRYPTO 2022, Part II, LNCS 13508, pages 541-572. Springer, Heidelberg, August 2022.

FOP<sup>+</sup>16. J.-C. Faugère, A. Otmani, L. Perret, F. de Portzamparc, and J.-P. Tillich. Folding alternant and Goppa Codes with non-trivial automorphism groups. IEEE Trans. Inform. Theory, 62(1):184-198, 2016.

GGM19. O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions, page 241-264. Association for Computing Machinery, New York, NY, USA, 2019.

GI14. N. Gilboa and Y. Ishai. Distributed point functions and their applications. In Advances in Cryptology-EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings 33, pages 640-658. Springer, 2014.

Gil99. N. Gilboa. Two party RSA key generation. In CRYPTO'99, LNCS 1666, pages 116-129. Springer, Heidelberg, August 1999.

GMW87. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In 19th ACM STOC, pages 218-229. ACM Press, May 1987.

GYW<sup>+</sup>23. X. Guo, K. Yang, X. Wang, W. Zhang, X. Xie, J. Zhang, and Z. Liu. Half-tree: Halving the cost of tree expansion in COT and DPF. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 330-362. Springer, 2023.

Hir16. S. Hirose. May-Ozerov Algorithm for Nearest-Neighbor Problem over $\mathcal{U}_q$ and Its Application to Information Set Decoding. In Innovative Security Solutions for Information Technology and Communications - 9th International Conference, SECITC 2016, Bucharest, Romania, June 9-10, 2016, Revised Selected Papers, Lecture Notes in Computer Science 10006, pages 115-126, 2016.

HOSS18a. C. Hazay, E. Orsini, P. Scholl, and E. Soria-Vazquez. Concretely efficient large-scale MPC with active security (or, TinyKeys for TinyOT). In ASIACRYPT 2018, Part III, LNCS 11274, pages 86-117. Springer, Heidelberg, December 2018.

HOSS18b. C. Hazay, E. Orsini, P. Scholl, and E. Soria-Vazquez. TinyKeys: A new approach to efficient multi-party computation. In CRYPTO 2018, Part III, LNCS 10993, pages 3-33. Springer, Heidelberg, August 2018.

IKNP03. Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In CRYPTO 2003, LNCS 2729, pages 145-161. Springer, Heidelberg, August 2003.

Jab01. A. A. Jabri. A statistical decoding algorithm for general linear block codes. In Cryptography and coding. Proceedings of the 8th IMA International Conference, LNCS 2260, pages 1-8, Cirencester, UK, December 2001. Springer.

KD08. R. Kutzelnigg and M. Drmota. Random bipartite graphs and their application to Cuckoo Hashing. na, 2008.

Kel20. M. Keller. MP-SPDZ: A versatile framework for multi-party computation. In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, pages 1575-1590, 2020.

KKRT16. V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. Efficient batched oblivious PRF with applications to private set intersection. In ACM CCS 2016, pages 818-829. ACM Press, October 2016.

KOS16. M. Keller, E. Orsini, and P. Scholl. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. In ACM CCS 2016, pages 830-842. ACM Press, October 2016.

KPR18. M. Keller, V. Pastro, and D. Rotaru. Overdrive: Making SPDZ great again. In EUROCRYPT 2018, Part III, LNCS 10822, pages 158-189. Springer, Heidelberg, April / May 2018.

KS08. V. Kolesnikov and T. Schneider. Improved garbled circuit: Free xor gates and applications. In Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II 35, pages 486-498. Springer, 2008.

LB88. P. J. Lee and E. F. Brickell. An observation on the security of McEliece's public-key cryptosystem. In EUROCRYPT'88, LNCS 330, pages 275-280. Springer, Heidelberg, May 1988.

MMT11. A. May, A. Meurer, and E. Thomae. Decoding random linear codes in $\mathcal{O}(2^{0.054n})$. In ASIACRYPT 2011, LNCS 7073, pages 107-124. Springer, Heidelberg, December 2011.
MO15. A. May and I. Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. In *Advances in Cryptology - EUROCRYPT 2015*, LNCS 9056, pages 203–228. Springer, 2015.

MS86. F. J. MacWilliams and N. J. A. Sloane. *The Theory of Error-Correcting Codes*. North-Holland, Amsterdam, fifth edition, 1986.

MT23. C. Meyer-Hilfiger and J.-P. Tillich. Rigorous foundations for dual attacks in coding theory. In *Theory of Cryptography Conference, TCC 2023*, LNCS. Springer Verlag, December 2023. to appear.

Obe07. U. Oberst. The fast fourier transform. *SIAM journal on control and optimization*, 46(2):496–540, 2007.

Ope. OpenSSL Project. OpenSSL cryptography and SSL/TLS toolkit. https://www.openssl.org/. Accessed: 2024-02-12.

Ove06. R. Overbeck. Statistical decoding revisited. In *Information security and privacy : 11th Australasian conference, ACISP 2006*, LNCS 4058, pages 283–294. Springer, 2006.

Pet10. C. Peters. Information-set decoding for linear codes over $F_q$. In *The Third International Workshop on Post-Quantum Cryptography, PQCRYPTO 2010*, pages 81–94. Springer, Heidelberg, May 2010.

Pra62. E. Prange. The use of information sets in decoding cyclic codes. *IRE Transactions on Information Theory*, 8(5):5–9, 1962.

PSWW18. B. Pinkas, T. Schneider, C. Weinert, and U. Wieder. Efficient circuit-based PSI via cuckoo hashing. In *EUROCRYPT 2018, Part III*, LNCS 10822, pages 125–157. Springer, Heidelberg, April / May 2018.

Rab81. M. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard University, 1981.

Roy22. L. Roy. SoftSpokenOT: Quieter OT extension from small-field silent VOLE in the minicrypt model. In *CRYPTO 2022, Part I*, LNCS 13507, pages 657–687. Springer, Heidelberg, August 2022.

RR. P. Rindal and L. Roy. libOTe: an efficient, portable, and easy to use oblivious transfer library. https://github.com/osu-crypto/libOTe.

RRT23. S. Raghuraman, P. Rindal, and T. Tanguy. Expand-convolute codes for pseudorandom correlation generators from LPN. In *Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part IV, Lecture Notes in Computer Science* 14084, pages 602–632. Springer, 2023.

RS21. P. Rindal and P. Schoppmann. VOLE-PSI: Fast OPRF and circuit-PSI from vector-OLE. In *EUROCRYPT 2021, Part II*, LNCS 12697, pages 901–930. Springer, Heidelberg, October 2021.

S+24. W. Stein et al. *Sage Mathematics Software (Version 10.2)*. The Sage Development Team, 2024. http://www.sagemath.org.

Sen11. N. Sendrier. Decoding one out of many. In *Post-Quantum Cryptography 2011*, LNCS 7071, pages 51–67, 2011.

Sen23. N. Sendrier. Wave parameter selection. In *Post-Quantum Cryptography*, pages 91–110, Cham, 2023. Springer Nature Switzerland.

SGRR19. P. Schoppmann, A. Gascón, L. Reichert, and M. Raykova. Distributed vector-OLE: Improved constructions and implementation. In *ACM CCS 2019*, pages 1055–1072. ACM Press, November 2019.

Ste89. J. Stern. A method for finding codewords of small weight. *Coding Theory and Applications*, 388(10):106–113, 1989.

TE76. R. E. Twogood and M. P. Ekstrom. An extension of Eklundh's matrix transposition algorithm and its application in digital image processing. *IEEE Trans. Comput.*, 25(9):950–952, sep 1976.

Tor17a. R. C. Torres. Asymptotic analysis of isd algorithms for the q-ary case. *Proceedings of the Tenth International Workshop on Coding and Cryptography WCC 2017*, 2017.

Tor17b. R. C. Torres. Optimizing bjmm with nearest neighbors: full decoding in $2^{2/21n}$ and mceliece security. *WCC Workshop on Coding and Cryptography WCC 2017*, 2017.

Wag02. D. Wagner. A generalized birthday problem. In *Advances in Cryptology - CRYPTO 2002*, LNCS 2442, pages 288–303. Springer, 2002.

Wil21. W. Willems. *Codes in group algebras*, chapter 16. Chapman and Hall/CRC, 2021.

Yao86. A. C.-C. Yao. How to generate and exchange secrets (extended abstract). In *27th FOCS*, pages 162–167. IEEE Computer Society Press, October 1986.
# Appendix

## A PCGs from the QA-SD assumption

In this section, we recall the construction of PCGs from the Quasi-Abelian Syndrome Decoding assumption (QA-SD) which was introduced in [BCCD23], and properly defined in Appendix A. We start with a short overview of the PCG construction over $F_q$ of Bombar et al. [BCCD23]. Let $\mathcal{R} = F_q[\mathbb{G}] = \{\sum_{g \in \mathbb{G}} a_g g \mid a_g \in F_q\}$, with $\mathbb{G}$ an abelian group. We refer to $\mathcal{R}_t$ as the set of ring elements of $\mathcal{R}$ of weight at most $t$. The goal is to construct a PCG that would achieve the functionality described in Figure 13.

### Ideal Functionality QA-SD<sub>OLE-Setup</sub>

PARAMETERS: Security parameter $1^{\lambda}$, PCG<sub>OLE</sub> = (PCG<sub>OLE</sub>.Gen, PCG<sub>OLE</sub>.Expand) as per Figure 14.

FUNCTIONALITY:

1. Sample $(k_0, k_1) \leftarrow PCG_{\text{OLE}}.\text{Gen}(1^{\lambda})$.

2. Output $k_{\sigma}$ to party $P_{\sigma}$ for $\sigma \in \{0, 1\}$.

<caption>**Fig. 13: Functionality QA-SD<sub>OLE-Setup</sub>.**</caption>

The protocol is described in Figure 14. The goal of the OLE correlation is to give the two parties a pseudorandom $x_{\sigma} \in \mathcal{R}$, as well as an additive sharing of the product $x_0 \cdot x_1$. To achieve this, the authors constructed the framework on the Quasi-Abelian Syndrome Decoding assumption. The players first have access to a vector $\mathbf{a} = (1, a_1, \dots, a_{c-1})$ of elements in $\mathcal{R}$, publicly. Taking advantage of the canonical notion of the sparseness of $\mathcal{R}$, players can define $x_{\sigma} = \langle \mathbf{a}, \mathbf{e}_{\sigma} \rangle$, where $e_{\sigma} = (e_{\sigma}^0, \dots, e_{\sigma}^{c-1})$ is a vector of $t$-sparse elements of $\mathcal{R}$, for a given $t$. Because of the QA-SD assumption, $x_{\sigma}$ is pseudorandom. Giving the parties additive sharing of $x_0 \cdot x_1$ can be achieved via Function Secret Sharing. Indeed, $x_0 \cdot x_1 = \langle \mathbf{a}, \mathbf{e}_0 \rangle + \langle \mathbf{a}, \mathbf{e}_1 \rangle$ can be fully expressed via the elements in $(\mathbf{e}_0 \otimes \mathbf{e}_1)$, and the public elements in the expression $\mathbf{a} \otimes \mathbf{a}$. Therefore we want to obtain an additive sharing of $(\mathbf{e}_0 \otimes \mathbf{e}_1)$. Because each $e_{\sigma}^i$ are $t$-sparse element in $\mathcal{R}$, all the products $e_0^i \cdot e_1^j$ are $t^2$-sparse element. Therefore they can easily be concisely shared using $t^2$ Single Point Function Secret Sharing (SPFSS). This enables the parties to obtain a short seed $k_{\sigma}$ which contains their FSS keys to obtain the full evaluation and recover the additive sharing of $\mathbf{e}_0 \otimes \mathbf{e}_1$, as well as the descriptions of $\mathbf{e}_{\sigma}$. Later on, the parties can use their seed to recover $x_{\sigma}$ and their additive share $z_{\sigma}$ of $x_0 \cdot x_1$.

**Theorem 20 ([BCCD23])**. Let $\mathbb{G}$ be an Abelian group. Assume that SPFSS is a secure FSS scheme for sums of point functions and that the QA-SD$(q, c, t, \mathbb{G})$ assumption holds. Then there exists a generic scheme to construct a PCG to produce one OLE correlation (described on Figure 14). If the SPFSS is based on a PRG: $\{0, 1\}^{\lambda} \rightarrow \{0, 1\}^{2\lambda+2}$ via the PRG-based construction from [BGI16], we obtain:

* Each party's seed has maximum size around: $(ct)^2 \cdot ((\log |\mathbb{G}| - \log t + 1) \cdot (\lambda + 2) + \lambda + \log q) + ct(\log |\mathbb{G}| + \log q)$ bits.

* The computation of Expand can be done with at most $(2 + \lceil (\log q)/\lambda \rceil) |\mathbb{G}| c^2 t$ PRG operations, and $O(c^2|\mathbb{G}| \log |\mathbb{G}|)$ operations in $F_q$.

## B N-party MPC with Preprocessing from $F_4$-OLEs

### B.1 Secure computation in the $\mathcal{F}_{\text{CBT}}$-hybrid model

In this section, we show how to securely compute arbitrary Boolean circuits in the preprocessing model, given access to an ideal functionality generating Beaver triples over $F_4$. Because $F_4$ is an
General construction of QA-SD<sub>OLE</sub>

PARAMETERS: Security parameter $\lambda$, noise weight $t = t(\lambda)$, compression factor $c \ge 2$, $\mathbb{G}$ a finite abelian group, $\mathcal{R} = \mathbb{F}_q[\mathbb{G}]$. An FSS scheme (SPFSS.Gen, SPFSS.FullEval) for sums of $t^2$ point functions, with domain $[0...|\mathbb{G}|)$ and range $\mathbb{F}_q$.

PUBLIC INPUT: $c - 1$ random ring elements $a_1, \dots, a_{c-1} \in \mathcal{R}$.

PCG.Gen(1<sup>λ</sup>):

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

1.1: $\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}_{q}^{\times})^{t}$.

2: **foreach** i, j ∈ [0... c):

2.1: Sample FSS keys $(K_0^{i,j}, K_1^{i,j}) \stackrel{\$}{\leftarrow} \text{SPFSS.Gen}(1^{\lambda}, 1^n, \mathbf{p}_0^i \otimes \mathbf{p}_1^j, \mathbf{v}_0^i \otimes \mathbf{v}_1^j)$.

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

4: Output $(k_0, k_1)$.

PCG.Expand(σ, K<sub>σ</sub>):

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

2: **foreach** i ∈ [0... c):

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

$$e_{\sigma}^{i} = \sum_{j \in [0 \dots t)} \mathbf{b}_{\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 ∈ [0... c):

4.1: Compute $u_{\sigma, i+c_j} \leftarrow \text{SPFSS.FullEval}(\sigma, K_{\sigma}^{i,j})$ and view it as a $c^2$ vector $\mathbf{u}_{\sigma}$ of elements in $\mathcal{R}_{t+2}$.

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

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

<caption>Fig. 14: PCG for OLE over $\mathcal{R}$, based on QA-SD.</caption>
Ideal Functionality $\mathcal{F}_{\text{CBT}}(\mathbb{F})$

The functionality interacts with $N$ parties $P_1, \dots, P_N$ and an adversary $\mathcal{A}$.

FUNCTIONALITY:

1. Wait for the input $\text{Corr} \subset [N]$ from $\mathcal{A}$ consisting of the set of corrupted parties and a list $((\llbracket a \rrbracket_i, \llbracket b \rrbracket_i, \llbracket c \rrbracket_i)_{i \in \text{Corr}}$ of triples in $\mathbb{F}$.

2. Wait for the command init from each party $P_i$ for $i \notin \text{Corr}$.

3. Sample $((\llbracket a \rrbracket_i, \llbracket b \rrbracket_i, \llbracket c \rrbracket_i)_{i \in [N] \setminus \text{Corr}} \in \mathbb{F}^3$ uniformly at random conditioned on

$$a \cdot b = \left( \sum_{i=1}^{N} \llbracket a \rrbracket_i \right) \cdot \left( \sum_{i=1}^{N} \llbracket b \rrbracket_i \right) = \sum_{i=1}^{N} \llbracket c \rrbracket_i.$$

4. Output $((\llbracket a \rrbracket_i, \llbracket b \rrbracket_i, \llbracket c \rrbracket_i)$ to each party $P_i$ for $i \notin \text{Corr}$.

<caption>Fig. 15: Ideal corruptible functionality $\mathcal{F}_{\text{CBT}}$ for sampling $N$-party Beaver triples over a field $\mathbb{F}$.</caption>

extension field of $\mathbb{F}_2$, we note that simply replacing the $\mathbb{F}_2$-Beaver triples with $\mathbb{F}_4$-Beaver triples in the classical instantiation of the GMW protocol in the preprocessing model works out-of-the-box. However, doing so naïvely doubles the communication during the online phase, from 2 bits per AND gate and per party to 4 bits per AND gate and per party (due to using masks over $\mathbb{F}_4$ instead of $\mathbb{F}_2$). In the technical overview, we introduced an improved strategy, which first converts each $\mathbb{F}_4$-triple into an $\mathbb{F}_2$-triple using one bit of communication per party, and then runs the standard GMW protocol over $\mathbb{F}_2$. To formally prove this result, we introduce on Figure 15 a corruptible functionality for generating an $N$-party Beaver triple over a field $\mathbb{F}$. Here, corruptible means that the adversary can freely choose the shares obtained by the corrupted parties; it is known that this functionality suffices to securely instantiate GMW [BCG$^{+19b}$] and can be securely instantiated given a programmable PCG for OLE over $\mathbb{F}$ [BCG$^{+20b}$]. That is:

**Theorem 21 (BCG$^{+19b}$, Theorem 19, Theorem 41).** Assume that there is a programmable PCG for generating $m$ OLEs over $\mathbb{F}$. Then there exists a protocol securely realizing $m$ calls to the functionality $\mathcal{F}_{\text{CBT}}(\mathbb{F})$ in Figure 15 using $N \cdot (N - 1)$ instances of a protocol to securely distribute the seeds of the PCG, and no further communication.

We formally state our construction as a protocol $\Pi_{\text{BT}}(\mathbb{F}_4 \to \mathbb{F}_2)$ that securely instantiates the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ functionality in the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$-hybrid model, using a single call to $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$ and one bit of communication per party. The protocol is represented in Figure 16.

Protocol $\Pi_{\text{BT}}(\mathbb{F}_4 \to \mathbb{F}_2)$

PROTOCOL:

1. The parties invoke the functionality $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$ with init. Each party $P_i$ receives a triple $((\llbracket a \rrbracket_i^4, \llbracket b \rrbracket_i^4, \llbracket c \rrbracket_i^4) \in \mathbb{F}_4^3$.

2. Each party $P_i$ broadcasts $\llbracket b \rrbracket_i^4(1)$. All parties reconstruct $b(1) = \sum_{i=1}^N \llbracket b \rrbracket_i^4(1)$.

OUTPUT: Each party $P_i$ outputs $((\llbracket a \rrbracket_i^4(0), \llbracket b \rrbracket_i^4(0), \llbracket c \rrbracket_i^4(0) + b(1) \cdot \llbracket a \rrbracket_i^4(1))$.

<caption>Fig. 16: An $N$-party protocol $\Pi_{\text{BT}}(\mathbb{F}_4 \to \mathbb{F}_2)$ that securely realizes the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ functionality in the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$-hybrid model.</caption>

**Lemma 22.** The protocol $\Pi_{\text{BT}}(\mathbb{F}_4 \to \mathbb{F}_2)$ of Figure 16 securely realizes the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ corruptible functionality in the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$-hybrid model, using one bit of communication per party and a single call to $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$.
Combining this lemma with the GMW protocol yields:

**Corollary 23.** There exists an N-party computation protocol that securely evaluates all Boolean circuits with m AND gates in the preprocessing model using m calls to the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$ functionality. The protocol uses $N \cdot m$ bits of communication in the preprocessing phase, and two bits of communication per AND gate and per party in the online phase.

**Proof of Lemma 22.**

*Proof.* Sim emulates the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$ functionality, and receives from $\mathcal{A}$ the set $\text{Corr} \subseteq [N]$ of corrupted parties and the list $([a]_i^4, [b]_i^4, [c]_i^4)_{i \in \text{Corr}}$ of corrupted triples over $\mathbb{F}_4$. On behalf of each honest party $P_i$ for $i \notin \text{Corr}$, Sim broadcast a uniformly random bit $[b]_i^4(1)$. Then, Sim reconstructs $b(1) \leftarrow \sum_{i=1}^N [b]_i^4(1)$ and sends $([a]_i^4(0), [b]_i^4(0), [c]_i^4(0)+b(1) \cdot [a]_i^4(1))_{i \in \text{Corr}}$ to the ideal functionality $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ on behalf of the ideal adversary. As the $[b]_i^4(1)$ are sampled uniformly and independently at random by $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$, it only remains to show that the honest parties output in an execution of $\Pi_{\text{BT}}(\mathbb{F}_4 \to \mathbb{F}_2)$ is distributed as the output of the adversaries from $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ in the simulated game. In turn, this follows immediately from the fact that from the viewpoint of $\mathcal{A}$, the shares $[a]_i^4(0), [b]_i^4(0)$ are uniformly distributed for every $i \notin \text{Corr}$, and the values $[c]_i^4(0) + b(1) \cdot [a]_i^4(1)$ for $i \notin \text{Corr}$ form uniformly random shares of

$$ \sum_{i \notin \text{Corr}} ([c]_i^4(0) + b(1) \cdot [a]_i^4(1)) = \sum_{i=1}^{N} ([c]_i^4(0) + b(1) \cdot [a]_i^4(1)) - C \\ = a(0)b(0) + a(1)b(1) + b(1) \cdot a(1) - C \\ = a(0)b(0) - C, $$

where $C \leftarrow \sum_{i \in \text{Corr}} [c]_i^4(0) + b(1) \cdot [a]_i^4(1)$ denote the sum of the corrupted parties' last output. This concludes the proof. $\square$

## B.2 An improved protocol for $N = 2$ parties

In the previous section, we described how $N$ parties can construct an $\mathbb{F}_2$-triple using one invocation to $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$ and $N$ bits of communication. Typically, the functionality $\mathcal{F}_{\text{CBT}}(\mathbb{F}_4)$ is realized by making $N \cdot (N-1)$ calls to a (programmable) OLE functionality over $\mathbb{F}_4$. When $N = 2$, this translates to using two calls to the OLE functionality, and two bits of communication. In this section, we introduce an improved construction, where $N = 2$ parties generate a Beaver triple over $\mathbb{F}_2$ using a single call to an OLE functionality over $\mathbb{F}_4$, and no communication. The corruptible functionality for generating OLEs over $\mathbb{F}_4$ is represented on Figure 17.

### Ideal Functionality $\mathcal{F}_{\text{COLE}}(\mathbb{F})$

The functionality interacts with 2 parties $A$, $B$ and an adversary $\mathcal{A}$.

**FUNCTIONALITY:**

1. Wait for an input $(\text{Corr}, u, v) \in \{A, B, \perp\} \times \mathbb{F} \times \mathbb{F}$ from $\mathcal{A}$, and for the command init from each party.

2. If $\text{Corr} = \perp$, sample $(a, b, [ab]_A) \stackrel{\$}{\leftarrow} \mathbb{F}^3$ and set $[ab]_B \leftarrow a \cdot b - [ab]_A$. If $\text{Corr} = A$, sample $b \stackrel{\$}{\leftarrow} \mathbb{F}$, set $(a, [ab]_A) \leftarrow (u, v)$ and $[ab]_B \leftarrow a \cdot b - [ab]_A$. If $\text{Corr} = B$, sample $a \stackrel{\$}{\leftarrow} \mathbb{F}$, set $(b, [ab]_B) \leftarrow (u, v)$ and $[ab]_A \leftarrow a \cdot b - [ab]_B$.

3. Output $(a, [ab]_A)$ to $A$ and $(b, [ab]_B)$ to $B$.

<caption>**Fig. 17:** Ideal corruptible functionality $\mathcal{F}_{\text{COLE}}(\mathbb{F})$ for sampling an OLE correlation over a field $\mathbb{F}$.</caption>

In Figure 18, we represent our protocol for realizing $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ when $N = 2$ in the $\mathcal{F}_{\text{COLE}}(\mathbb{F}_4)$-hybrid model.
Protocol $\Pi(\mathbb{F}_4\text{OLE} \to \mathbb{F}_2\text{BT})$

PROTOCOL:

1. The parties invoke the functionality $\mathcal{F}_{\text{COLE}}(\mathbb{F}_4)$ with init, and receive $(a, [[ab]]_A^4)$ and $(b, [[ab]]_B^4)$, respectively.

OUTPUT:

Alice outputs $(a(0), a(1), a(0)a(1) + [[ab]]_A^4(0))$ and Bob outputs $(b(1), b(0), b(0)b(1) + [[ab]]_B^4(0))$.

**Fig. 18:** A 2-party protocol $\Pi(\mathbb{F}_4\text{OLE} \to \mathbb{F}_2\text{BT})$ that securely realizes the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ functionality in the $\mathcal{F}_{\text{COLE}}(\mathbb{F}_4)$-hybrid model.

**Lemma 24.** *The protocol $\Pi(\mathbb{F}_4\text{OLE} \to \mathbb{F}_2\text{BT})$ of Figure 18 securely realizes the $\mathcal{F}_{\text{CBT}}(\mathbb{F}_2)$ corruptible functionality for $N=2$ parties in the $\mathcal{F}_{\text{COLE}}(\mathbb{F}_4)$-hybrid model, using no communication and a single call to $\mathcal{F}_{\text{COLE}}(\mathbb{F}_4)$.*

We refer the reader to the technical overview (Section 2.4) for the correctness analysis. The proof of security is straightforward and we omit it.

## C Complexity of Informations Set Decoding algorithms over $\mathbb{F}_q$

In this section, we provide a detailed framework for the ISD algorithm, discussing its primary variations. We conduct a thorough analysis of the complexity associated with each variant, aiming to determine the most suitable choice for addressing our QA-SD assumption. Deep analysis has been conveyed on these algorithms, to improve their asymptotic complexity, but this has mainly been done for ISD over $\mathbb{F}_2$. This is all the more true in our context: due to the significant size of the involved matrices, we have to take into account the polynomial factors coming from linear algebra which are usually neglected when doing asymptotic analysis. Hence, we present a comprehensive analysis that considers polynomial factors, particularly over $\mathbb{F}_q$. It's worth noting that the general case of $\mathbb{F}_q$ has been explored in some previous works [Pet10, Tor17a, BCDL19]. We will primarily describe the overarching framework provided by [DA23], along with relevant findings from [Sen23], tailored to our specific scenario.

Let us consider the syndrome decoding assumption in its search variant: given a matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$ and $\mathbf{y} \in \mathbb{F}_q^{n-k}$, find $\mathbf{e} \in \mathbb{F}_q^n$ such that the weight of $\mathbf{e}$ achieves a certain target $t$. The general idea behind all ISD algorithms is to pick randomly what is called an *information set*. For a set $\mathcal{I} \subset [0, n-1]$, we define by $\bar{\mathcal{I}}$ it's complementary in $[0, n-1]$. For a matrix $\mathbf{H}$, we denote by $\mathbf{H}_{\bar{\mathcal{I}}}$ the restriction of $\mathbf{H}$ to the columns indicated by $\mathcal{I}$, and for a vector $\mathbf{e}$, we write $e_{\bar{\mathcal{I}}}$ for the restriction of $\mathbf{e}$ to the entries indexed by $\mathcal{I}$. Given a parity check matrix $\mathbf{H}$, an information set is defined by $\mathcal{I} \subset [0, n-1]$, $|\mathcal{I}| = k + \ell$, $\ell \in \mathbb{N}$, and $\mathbf{H}_{\bar{\mathcal{I}}}$ is full rank. The upcoming discussion relies on the ISD framework outlined by [DA23]. While [Sen23] also offers a comparable general framework, it introduces a permutation matrix to denote an information set, a classic selection for clarity reasons. However, in practical applications, this approach introduced overheads due to matrix multiplication. Consequently, we have opted not to pursue it.

**General ISD framework.** Consider two parameters $0 \le \ell \le n-k$ and $0 \le p \le \min(t, k+\ell)$

1. Pick randomly a subset $\mathcal{I} \subset [0, n-1]$, $|\mathcal{I}| = k+\ell$, until $\mathbf{H}_{\bar{\mathcal{I}}}$ is full rank.

2. Perform a Gaussian elimination to compute a non-singular matrix $\mathbf{U} \in \mathbb{F}_q^{(n-k) \times (n-k)}$ such that

$$ \mathbf{U}\mathbf{H}_{\bar{\mathcal{I}}} = \begin{bmatrix} I_{n-k-\ell} \\ 0 \end{bmatrix}, \text{ and compute } \tilde{\mathbf{s}} = \mathbf{U}\mathbf{s}. \text{ Write } \mathbf{U}\mathbf{H}_{\bar{\mathcal{I}}} = \begin{bmatrix} \mathbf{H}_1 \\ \mathbf{H}_2 \end{bmatrix}. $$

3. Compute $\mathcal{L} \subset \{\mathbf{e}_2 \in \mathbb{F}_q^{k+\ell}, w_H(\mathbf{e}_2) = p, \mathbf{H}_2\mathbf{e}_2 = \tilde{s}_{\bar{\mathcal{I}}}\}$ according to a given ISD-subroutine.

4. Find a $\mathbf{e}_2 \in \mathcal{L}$ such that $\mathbf{e}_1 = \tilde{s}_{\bar{\mathcal{I}}} - \mathbf{H}_1\mathbf{e}_2$ has weight $t-p$. If no such $\mathbf{e}_2$ is found, return to Step 1.

If it is found, return the vector $\mathbf{e}$ such that $\mathbf{e} \in \mathbb{F}_q^n$ and $\mathbf{H}\mathbf{e} = \mathbf{s} \begin{bmatrix} \mathbf{e}_1 \\ \mathbf{e}_2 \end{bmatrix}$.

An ISD algorithm is an iterative algorithm that loops until it finds a solution. The algorithm is therefore probabilistic, with its iterations being independent, and its complexity is given by the
complexity of Steps 2 and 3, multiplied by the number of iterations (i.e., the inverse of the probability of finding an information set for which the procedure terminates). An instance of the general ISD algorithm is given by the choice of the parameters (ℓ, p) and of the ISD subroutine to compute $\mathcal{L}$. Next, based on the work of Sendrier [Sen23], we expose the practical complexity of the different variants of the ISD algorithm defined above and take into account some polynomial factors while being conservative.

**Remark 25.** In this analysis, we do not consider the modern and more recent attacks on syndrome decoding using nearest neighbors search [Tor17b, BM18], as they are not considered to be practical, even in the binary field case. To the best of our knowledge, there has been no work on extending these algorithms to the general case of $\mathbb{F}_q$, and we believe that it would not be practical in our range of parameters.

We denote by $T(n, k, q, *)$ the complexity of a given ISD, * indicating here the different parameters of the variant considered to be tuned. As stated before an ISD algorithm is by essence probabilistic, and its complexity can be formulated like this:

$$T(n, k, q, t, *) = \frac{T_G(n, k, q, *) + C_S(n, k, q, *)}{\mathcal{P}_S(n, k, q, t, *)},$$

where $T_G(n, k, q, *)$ counts the costs of the Gaussian elimination done at each iteration, $C_S(n, k, q, *)$ is the complexity of the subroutine chosen for this ISD, and $\mathcal{P}_S(n, k, q, t, *)$ the probability of randomly selecting an Information Set that led to a solution.

**Remark 26 (Gaussian Elimination Cost).** For our estimations, we consider the following cost

$$T_G(n, k, q, p, \ell) = (n - k - \ell)n.$$

In other words, we consider here that Gaussian elimination costs just as much as the size of the matrix, which is a very conservative lower bound.

## C.1 Stern/Dumer

The algorithm proposed by Stern [Ste89] and independently by Dummer [Dum89] corresponds to the case where we consider the following subroutine:

1. We create two lists

$$\mathcal{L}_1 = \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}{2} \right\}$$

$$\mathcal{L}_2 = \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+\ell}{2}}, w_H(\mathbf{e}') = \frac{p}{2} \right\}$$

each list is of size $|\mathcal{L}_1| = |\mathcal{L}_2| = \binom{(k+\ell)/2}{p/2}(q-1)^{p/2}$.

*Complexity: $O(|\mathcal{L}_1|)$.*

2. Search for all pairs $((\mathbf{e}_0, \mathbf{H}_2\mathbf{e}_0), (\tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0)) \in \mathcal{L}_2$ such that $\mathbf{H}_2 \cdot \mathbf{e}_0 = \tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0$, and construct the list

$$\mathcal{L} = \{\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}_1 \times \mathcal{L}_2, \mathbf{H}_2 \cdot \mathbf{e}_0 = \tilde{\mathbf{s}}_I - \mathbf{H}_2\mathbf{e}'_0\}.$$

The list $\mathcal{L}$ created like this satisfies that

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

The size of the list is $|\mathcal{L}| = \binom{(k+\ell)/2}{p/2}(q-1)^{p}q^{-l}$.

*Complexity: $O(\max(|\mathcal{L}_1|, |\mathcal{L}|))$.*

3. We perform Step 4 of the general ISD framework to find $e_1$ of weight $t-p$.