Abstract
In the recent work of (Cheon & Lee, Eurocrypt'22), the concept of a degree-$D$ packing method was formally introduced, capturing the idea of embedding multiple elements of a smaller ring into a larger ring such that element-wise multiplication is compatible with the product in the larger ring. This work generalizes the notion of Reverse Multiplication-Friendly Embeddings (RMFEs) to degree-$D$ RMFEs. We show that these algebraic structures are essentially equivalent to packing methods and present a general construction using algebraic geometry over Galois rings. Finally, we apply these embeddings to the non-interactive generation of high-degree correlations for secure multiparty computation (MPC), enabling efficient preprocessing over small rings without the multiplicative overhead of large-degree extensions.
Introduction
In cryptographic protocols like Secure Multiparty Computation (MPC) and Zero-Knowledge Proofs (ZKPs), arithmetic is often performed over small rings such as $\mathbb{Z}_{2^{64}}$. However, these rings frequently lack the algebraic properties required for security—specifically, a sufficiently large Lenstra constant. To address this, researchers employ Galois ring extensions, which provide the necessary properties but introduce significant computational and communication overhead.
Reverse Multiplication-Friendly Embeddings (RMFEs) were designed to mitigate this overhead by "packing" multiple small ring elements into a single large extension element. This allows a single multiplication in the large ring to correspond to element-wise multiplications in the small ring. However, traditional RMFEs only support a single multiplication (degree-2). Computing high-degree polynomials requires repeated decoding and re-encoding, which is computationally expensive. This paper addresses this gap by extending the theory of RMFEs to degree-$D$.
Generalizing RMFEs to Degree-D
The authors formally define degree-$D$ RMFEs, which allow for $D-1$ sequential multiplications before a decoding step is necessary. A key theoretical contribution is the proof of equivalence between these algebraic RMFEs and the "packing methods" recently introduced in the literature. Specifically, any deterministic and linear packing method is shown to be a degree-$D$ RMFE. This equivalence allows the application of known lower bounds from packing methods directly to RMFEs.
Algebraic Geometry Constructions
Using the theory of algebraic function fields, specifically function field towers, the paper provides explicit constructions for asymptotically good degree-$D$ RMFEs. By embedding data into the Riemann-Roch spaces of these fields, the authors achieve constructions where the "rate" (the efficiency of the packing) remains constant even as the number of packed elements grows.
Furthermore, the theory is presented in a unified manner for general Galois rings. This includes both finite fields ($\mathbb{F}_{p^k}$) and rings of the form $\mathbb{Z}_{p^k}$, which were previously treated as separate cases in the literature.
Applications in Secure Multiparty Computation
The primary application of degree-$D$ RMFEs presented is the non-interactive generation of high-degree correlations for MPC. Generating "multiplication triples" or higher-degree correlations typically requires significant communication between parties.
By utilizing degree-$D$ RMFEs and a new Pseudo-Random Secret Sharing (PRSS) solution tailored for Galois rings, the authors enable a committee to generate these correlations with zero communication. Each member computes their share locally using PRSS seeds. This approach effectively eliminates the "penalty" of using a large ring extension for security; the overhead becomes a constant factor rather than growing logarithmically with the number of parties.
Results and Concrete Parameters
The paper provides concrete parameter sets for degree-$D$ RMFEs. For example, over $\mathbb{Z}_{2^\ell}$, they achieve a rate of approximately $\frac{3}{D(1+2D)}$. In the degree-2 case, the ratio of the extension degree to the number of packed elements is shown to be approximately 4.92. These results demonstrate that RMFEs can provide the security of large rings with the amortized cost of small rings.
Limitations and Future Directions
While this work marks a significant advancement, several challenges remain:
- Active Security: The current application for non-interactive correlation generation is proven secure only against passive (honest-but-curious) adversaries. Extending this to active (malicious) security is a major open problem.
- Storage Overhead: The PRSS phase requires each party to store a number of seeds that can grow exponentially based on the underlying "covering design." Optimizing these designs is a subject for future research.
- Rate Optimization: The constant factors in the achieved rates could potentially be improved through the selection of more sophisticated function fields.
Summary updated