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 Z2k at the cost of a single secure multiplication in R. We present three CAFE instantiations, which we apply to the protocol for MPC over Z2k 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 Z2k 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).
Original language
English
Title of host publication
Advances in Cryptology – ASIACRYPT 2020 : 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings
Editors
Shiho Moriai, Huaxiong Wang
Volume
III
Publisher
Springer
Publication year
2020
ISBN (print)
978-3-030-64839-8
ISBN (Electronic)
978-3-030-64840-4
Publication status
Published - 2020
Event
26th International Conference on the Theory and Application of Cryptology and Information Security - Daejeon, Korea, Republic of Duration: 7 Dec 2020 → 11 Nov 2021 Conference number: 26
Conference
Conference
26th International Conference on the Theory and Application of Cryptology and Information Security