Paper 2020/1053
Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation
Anders Dalskov, Eysa Lee, and Eduardo SoriaVazquez
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 bitwise operations. From an implementation of our techniques, we estimate that an SVM can be evaluated on 250 images in parallel up to $\times 7$ more efficiently using our techniques, compared to the protocol from Abspoel et al. (TCC 2019).
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 MPCGalois Ringsinformationtheoretic security
 Contact author(s)

anderspkd @ cs au dk
eduardo @ cs au dk
eysa @ ccs neu edu  History
 20200901: received
 Short URL
 https://ia.cr/2020/1053
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1053, author = {Anders Dalskov and Eysa Lee and Eduardo SoriaVazquez}, title = {Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1053}, year = {2020}, url = {https://eprint.iacr.org/2020/1053} }