Improved primitives for mpc over mixed arithmetic-binary circuits

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

This work introduces novel techniques to improve the translation between arithmetic and binary data types in secure multi-party computation. We introduce a new approach to performing these conversions using what we call extended doubly-authenticated bits (edaBits), which correspond to shared integers in the arithmetic domain whose bit decomposition is shared in the binary domain. These can be used to considerably increase the efficiency of non-linear operations such as truncation, secure comparison and bit-decomposition. Our edaBits are similar to the daBits technique introduced by Rotaru et al. (Indocrypt 2019). However, we show that edaBits can be directly produced much more efficiently than daBits, with active security, while enabling the same benefits in higher-level applications. Our method for generating edaBits involves a novel cut-and-choose technique that may be of independent interest, and improves efficiency by exploiting natural, tamper-resilient properties of binary circuits that occur in our construction. We also show how edaBits can be applied to efficiently implement various non-linear protocols of interest, and we thoroughly analyze their correctness for both signed and unsigned integers. The results of this work can be applied to any corruption threshold, although they seem best suited to dishonest majority protocols such as SPDZ. We implement and benchmark our constructions, and experimentally verify that our technique yields a substantial increase in efficiency. EdaBits save in communication by a factor that lies between 2 and 60 for secure comparisons with respect to a purely arithmetic approach, and between 2 and 25 with respect to using daBits. Improvements in throughput per second slightly lower but still as high as a factor of 47. We also apply our novel machinery to the tasks of biometric matching and convolutional neural networks, obtaining a noticeable improvement as well.

Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2020
EditorsDaniele Micciancio, Thomas Ristenpart
Number of pages30
Place of publicationCham
PublisherSpringer
Publication year2020
Pages823-852
ISBN (print)9783030568795
ISBN (Electronic)978-3-030-56880-1
DOIs
Publication statusPublished - 2020
Event40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States
Duration: 17 Aug 202021 Aug 2020

Conference

Conference40th Annual International Cryptology Conference, CRYPTO 2020
LandUnited States
BySanta Barbara
Periode17/08/202021/08/2020
SeriesLecture Notes in Computer Science
Volume12171
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 195873443