Paper 2023/173

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

Daniel Escudero, J.P. Morgan
Cheng Hong, Ant Group
Hongqing Liu, Shanghai Jiao Tong University
Chaoping Xing, Shanghai Jiao Tong University
Chen Yuan, Shanghai Jiao Tong University

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).

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
RMFEMultiparty ComputationPacking
Contact author(s)
daniel escudero @ protonmail com
vince hc @ antgroup com
liu hong qing @ sjtu edu cn
xingcp @ sjtu edu cn
chen_yuan @ sjtu edu cn
2023-11-22: last of 2 revisions
2023-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Escudero and Cheng Hong and Hongqing Liu and Chaoping Xing and Chen Yuan},
      title = {Degree-$D$ Reverse Multiplication-Friendly Embeddings: Constructions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/173},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.