At CRYPTO 2018, Cascudo et al. introduced Reverse Multiplication Friendly Embeddings (RMFEs). These are a mechanism to compute 6 parallel evaluations of the same arithmetic circuit over a field F_q at the cost of a single evaluation of that circuit in F_(q~d), where δ ＜ d. Due to this inequality, RMFEs are a useful tool when protocols require to work over F_(q~d) but one is only interested in computing over F_q. In this work we introduce Circuit Amortization Friendly Encodings (CAFEs), which generalize RMFEs while having concrete efficiency in mind. For a Galois Ring R = GR(2~k,d), CAFEs allow to compute certain circuits over Z_(2~k) at the cost of a single secure multiplication in R. We present three CAFE instantiations, which we apply to the protocol for MPC over Z_(2~k) via Galois Rings by Abspoel et al. (TCC 2019). Our protocols allow for efficient switching between the different CAFEs, as well as between computation over GR(2~k, d) and F_2~d in a way that preserves the CAFE in both rings. This adaptability leads to efficiency gains for e.g. Machine Learning applications, which can be represented as highly parallel circuits over Z_(2~k)＜ followed by bit-wise operations. From an implementation of our techniques, we estimate that an SVM can be evaluated on 250 images in parallel up to ×7 more efficiently using our techniques, compared to the protocol from Abspoel et al. (TCC 2019).
展开▼
