International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation

Authors:
Anders Dalskov
Eysa Lee
Eduardo Soria-Vazquez
Download:
DOI: 10.1007/978-3-030-64840-4_8
Search ePrint
Search Google
Abstract: At CRYPTO 2018, Cascudo et al. introduced Reverse Multiplication Friendly Embeddings (RMFEs). These are a mechanism to compute δ parallel evaluations of the same arithmetic circuit over a field Fq at the cost of a single evaluation of that circuit in Fqd, where δ<d. Due to this inequality, RMFEs are a useful tool when protocols require to work over Fqd but one is only interested in computing over Fq. 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(2k,d), CAFEs allow to compute certain circuits over Extra close brace or missing open brace at the cost of a single secure multiplication in R. We present three CAFE instantiations, which we apply to the protocol for MPC over Extra close brace or missing open brace 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(2k,d) and F2d 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 Extra close brace or missing open brace 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 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
}