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

Daniel Escudero, Hongqing Liu, Chaoping Xing, Chen Yuan

TL;DR

This paper introduces "Degree-D Reverse Multiplication-Friendly Embeddings" (Degree-D RMFEs), a generalization of existing cryptographic tools that allows for more than two multiplications before needing to "decode" intermediate results. This advancement is crucial for building more efficient and practical cryptographic protocols, particularly in secure multi-party computation (MPC), by reducing communication overhead when dealing with higher-degree computations.

What Problem Does This Paper Address?

Modern cryptography, especially in areas like fully homomorphic encryption (FHE) and secure multi-party computation (MPC), often relies on algebraic structures like finite rings and fields. Many advanced cryptographic primitives require computations over these structures, and sometimes, these computations involve multiple multiplications. However, existing tools like "Reverse Multiplication-Friendly Embeddings" (RMFEs) are limited to handling only a single multiplication before requiring a costly "decoding" step. This limitation becomes a bottleneck when protocols need to perform computations involving products of three or more elements. The paper addresses this by generalizing RMFEs to "Degree-D RMFEs," enabling the handling of up to D multiplications, thereby paving the way for more efficient protocols that require higher-degree computations.

Methods

The core of this paper is the introduction and construction of Degree-D RMFEs. The authors generalize the concept of RMFEs, which were previously defined for degree-2 multiplications, to handle D multiplications. They achieve this by:

  • Generalizing the RMFE Definition: They formally define a Degree-D RMFE as a pair of homomorphisms that allow for D multiplications before decoding.
  • Leveraging Algebraic Geometry and Function Fields: Similar to prior work on degree-2 RMFEs, the authors utilize techniques from algebraic geometry and function fields to construct these new embeddings. They present explicit constructions for both bounded and unbounded dimensions.
  • Relating RMFEs to Packing Methods: The paper establishes a formal relationship between Degree-D RMFEs and a more general concept called "packing methods" introduced in prior work. They show that Degree-D RMFEs are a specific type of packing method and that certain packing methods can be converted into Degree-D RMFEs.
  • Developing Pseudo-Random Secret Sharing (PRSS): As a key application, the paper develops a new PRSS scheme tailored for Galois rings. This scheme is crucial for enabling non-interactive generation of correlated randomness for MPC protocols, overcoming limitations of previous PRSS constructions.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and their properties over abstract algebraic structures (Galois rings, function fields) rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Power of Generalization: The paper demonstrates that extending the concept of RMFEs from degree-2 to degree-D is not just a theoretical exercise but unlocks practical benefits for cryptographic protocols requiring higher-degree computations.
  • Bridging Theory and Practice: By providing explicit constructions of Degree-D RMFEs over Galois rings, the paper moves these advanced cryptographic tools closer to practical implementation.
  • Unified Framework: The work unifies and generalizes existing notions of packing methods and RMFEs, offering a more coherent understanding of these cryptographic primitives.
  • Enabling Non-Interactive Correlation Generation: The development of a specialized PRSS scheme for Galois rings, combined with Degree-D RMFEs, is a significant step towards efficient, non-interactive generation of correlated randomness for MPC, a critical component for secure computation.

Key Results

  • Formal Definition and Construction of Degree-D RMFEs: The paper introduces and formally defines Degree-D RMFEs and provides explicit constructions for them over Galois rings.
  • Relationship to Packing Methods: It establishes that Degree-D RMFEs are a special case of packing methods and shows how to convert certain packing methods into Degree-D RMFEs.
  • Application to Non-Interactive Correlation Generation: The paper presents a concrete application of Degree-D RMFEs in enabling non-interactive generation of correlated randomness for MPC protocols, significantly reducing communication overhead.
  • Explicit Parameters: The paper provides concrete sets of parameters for Degree-2 RMFEs and discusses how these can be generalized for higher degrees, offering practical options for future cryptographic designs.

Limitations and Future Work

  • Complexity of Constructions: While explicit constructions are provided, they can still be complex, especially for very high degrees D.
  • Parameter Choices: The efficiency of the constructions often depends on the specific parameters of the Galois rings and function fields used, requiring careful selection for optimal performance.
  • Passive Security in Application: The described application for non-interactive correlation generation offers passive security against adversaries corrupting a limited number of parties. Extending this to active security would be a significant future direction.
  • Exploration of Further Applications: The authors suggest that Degree-D RMFEs could find applications in other areas beyond MPC, such as in more advanced FHE schemes or zero-knowledge proofs, which warrants further investigation.
  • Improving Packing Density: While the paper achieves constant packing density, further research could focus on optimizing this density for specific applications.

Summary updated

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