Degree- D Reverse Multiplication-Friendly Embeddings

Abstract

Reverse multiplication-friendly embeddings have played a crucial role in secure multiparty computation and zero-knowledge proofs. In this work, we generalize the notion of RMFEs todegree-DRMFEs. We present a general construction of degree-DRMFEs by generalizing the ideas on algebraic geometry used to construct traditional degree-2 RMFEs. Furthermore, our theory is given in a unified manner for general Galois rings, which include both rings of the form Zpkand fields like Fpk, which have been treated separately in prior works. We present multiple concrete sets of parameters for degree-DRMFEs (includingD= 2), which can be useful for future works. In the recent work of (Cheon & Lee, Eurocrypt’22), the concept of adegree-D packing methodwas formally introduced, which captures the idea of embedding multiple elements of a smaller ring into a larger ring. We show that the generalized notion of RMFEs todegree-D RMFEswhich, in spite of being “more algebraic” than packing methods, turn out to be essentially equivalent. Thus, our constructions of degree-DRMFEs are also degree-Dpacking methods.