CryptoDB
Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation
| Authors: | |
|---|---|
| Download: | |
| Abstract: | At CRYPTO 2018, Cascudo et al. introduced Reverse Multiplication Friendly Embeddings (RMFEs). These are a mechanism to compute $\delta$ parallel evaluations of the same arithmetic circuit over a field $\mathbb{F}_q$ at the cost of a single evaluation of that circuit in $\mathbb{F}_{q^d}$, where $\delta < d$. Due to this inequality, RMFEs are a useful tool when protocols require to work over $\mathbb{F}_{q^d}$ but one is only interested in computing over $\mathbb{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 $\mathbb{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 $\mathbb{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 $\mathbb{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 $\mathbb{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 $\times 7$ as efficient using our techniques, compared to using the protocols from Abspoel et al. (TCC 2019). |
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30724,
title={Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation},
booktitle={Advances in Cryptology - ASIACRYPT 2020},
publisher={Springer},
doi={10.1007/978-3-030-64840-4_8},
author={Anders Dalskov and Eysa Lee and Eduardo Soria-Vazquez},
year=2020
}