Welcome to the resource topic for 2020/1053
Title:
Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation
Authors: Anders Dalskov, Eysa Lee, Eduardo Soria-Vazquez
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 more efficiently using our techniques, compared to the protocol from Abspoel et al. (TCC 2019).
ePrint: https://eprint.iacr.org/2020/1053
Talk: https://www.youtube.com/watch?v=ZnSbQ56RbK0
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .