Degree-D Reverse Multiplication-Friendly Embeddings: Constructions and Applications

Daniel Escudero, Hongqing Liu, Chaoping Xing, Chen Yuan

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

Abstract

In the recent work of (Cheon & Lee, Eurocrypt'22), the concept of a degree-$D$ packing method was formally introduced, which captures the idea of embedding multiple elements of a smaller ring into a larger ring, so that element-wise multiplication in the former is somewhat "compatible" with the product in the latter. Then, several optimal bounds and results are presented, and furthermore, the concept is generalized from one multiplication to degrees larger than two. These packing methods encompass several constructions seen in the literature in contexts like secure multiparty computation and fully homomorphic encryption. One such construction is the concept of reverse multiplication-friendly embeddings (RMFEs), which are essentially degree-2 packing methods. In this work we generalize the notion of RMFEs to \emph{degree-$D$ RMFEs} which, in spite of being "more algebraic" than packing methods, turn out to be essentially equivalent. Then, we present a general construction of degree-$D$ RMFEs by generalizing the ideas on algebraic geometry used to construct traditional degree-$2$ RMFEs which, by the aforementioned equivalence, leads to explicit constructions of packing methods. Furthermore, our theory is given in an unified manner for general Galois rings, which include both rings of the form $\mathbb{Z}_{p^k}$ and fields like $\mathbb{F}_{p^k}$, which have been treated separately in prior works. We present multiple concrete sets of parameters for degree-$D$ RMFEs (including $D=2$), which can be useful for future works. Finally, we apply our RMFEs to the task of non-interactively generating high degree correlations for secure multiparty computation protocols. This requires the use of Shamir secret sharing for a large number of parties, which is known to require large-degree Galois ring extensions. Our RMFE enables the generation of such preprocessing data over small rings, without paying for the multiplicative overhead incurred by using Galois ring extensions of large degree. For our application we also construct along the way, as a side contribution of potential independent interest, a pseudo-random secret-sharing solution for non-interactive generation of packed Shamir-sharings over Galois rings with structured secrets, inspired by the PRSS solutions from (Benhamouda et al, TCC 2021).
BibTeX
@article{escudero2023degree,
  author = {Daniel Escudero and Hongqing Liu and Chaoping Xing and Chen Yuan},
  title = {{Degree-D Reverse Multiplication-Friendly Embeddings: Constructions and Applications}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
  url = {https://openreview.net/forum?id=GAtWgbx7N5},
}
Figure