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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Anders Peter Kragh Dalskov
  • ,
  • Eysa Lee, Northeastern University, Boston, United States
  • Eduardo Soria Vazquez
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 languageEnglish
Title of host publicationAdvances 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
EditorsShiho Moriai, Huaxiong Wang
VolumeIII
PublisherSpringer
Publication year2020
ISBN (print)978-3-030-64839-8
ISBN (Electronic)978-3-030-64840-4
Publication statusPublished - 2020
Event26th International Conference on the Theory and Application of Cryptology and Information Security - Daejeon, Korea, Republic of
Duration: 7 Dec 202011 Nov 2021
Conference number: 26

Conference

Conference26th International Conference on the Theory and Application of Cryptology and Information Security
Nummer26
LandKorea, Republic of
ByDaejeon
Periode07/12/202011/11/2021
SeriesLecture Notes in Computer Science
Volume12493
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 197153891