TPMPC 2020 Program

15.00-15.50: The Price of Active Security in Cryptographic Protocols

Carmit Hazay (Bar-Ilan University)

Abstract:

We construct the first actively-secure Multi-Party Computation (MPC) protocols with an arbitrary number of parties in the dishonest majority setting, for an arbitrary field F with constant communication overhead over the ``passive-GMW'' protocol (Goldreich, Micali and Wigderson, STOC `87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC `14) or a constant number of parties (Ishai et al. CRYPTO `08).

Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality F_\mult, to an actively-secure protocol for general functionalities. Roughly, F_\mult is parameterized by a linear-secret sharing scheme S, where it takes S-shares of two secrets and returns S-shares of their product.

We show that our compilation is concretely efficient for sufficiently large fields, resulting in an overhead of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on any passive implementation of F_\mult, which, besides the standard implementation based on OT (for boolean) and OLE (for arithmetic) allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt `01); and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2.

Instantiating this compiler with an ``honest-majority'' implementation of F_\mult, we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol (Damgard and Nielsen, CRYPTO `07).

This is a joint work with Muthuramakrishnan Venkitasubramaniam and Mor Weiss.

Paper

16.00-16.25: Communication Lower Bounds for Perfect Maliciously Secure MPC

Ivan Damgård and Nikolaj Schwartzbach (Aarhus University)

Paper

16.25-16.50: Black-Box Transformations from Passive to Covert Security with Public Verifiability

Ivan Damgård, Claudio Orlandi and Mark Simkin (Aarhus University)

17.00-17.25: Stacked Garbling for Disjunctive Zero-Knowledge Proofs

David Heath and Vladimir Kolesnikov (Georgia Institute of Technology)

Paper

17.25-17.50: Full-Threshold Actively-Secure Multiparty Arithmetic Circuit Garbling

Eleftheria Makri (imec-COSIC KU Leuven and ABRR Saxion University of Applied Sciences) and Tim Wood (imec-COSIC KU Leuven and University of Bristol)

Paper

15:00-15:50: Legal Theorems of Privacy

Kobbi Nissim (Georgetown University)

Abstract:

There are significant gaps between legal and technical thinking around data privacy. Technical standards such as k-anonymity and differential privacy are described using mathematical language whereas legal standards are not rigorous from a mathematical point of view and often resort to concepts such as de-identification and anonymization which they only partially define. As a result, arguments about the adequacy of technical privacy measures for satisfying legal privacy often lack rigor, and their conclusions are uncertain. The uncertainty is exacerbated by a litany of successful privacy attacks on privacy measures thought to meet legal expectations but then shown to fall short of doing so. In this work, we ask whether it is possible to introduce mathematical rigor into such analyses to the point of making and proving formal “legal theorems” that certain technical privacy measures meet legal expectations. For that, we explore some of the gaps between these two very different approaches, and present initial strategies towards bridging these gaps considering examples from US and EU law.

16:00-16:25: Revisiting Cryptography via Anonymity for Differential Privacy in the Shuffle Model

Borja Balle (Deepmind), James Bell (The Alan Turing Institute), Adria Gascon (Google) and Kobbi Nissim (Georgetown University)

Paper

16:25-16:50: Can a Blockchain Keep a Secret?

Fabrice Benhamouda (Algorand Foundation), Craig Gentry (Algorand Foundation), Sergey Gorbunov (Algorand, University of Waterloo), Shai Halevi (Algorand Foundation), Hugo Krawczyk (Algorand Foundation), Chengyu Lin (Columbia University), Tal Rabin (Algorand Foundation) and Leonid Reyzin (Algorand, Boston University)

Paper

17:00-17:50: Optimal Oblivious Parallel RAM

Gilad Asharov (Bar-Ilan University)

Abstract:

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC~'87 and J.\ ACM~'96), is a technique for hiding RAM's access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine's secret inputs. Recent progress culminated in a work of Asharov et al.~(EUROCRYPT~'20), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal.

Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead and for highly parallel RAMs a logarithmic depth blowup (in the balls and bins model). Despite the significant recent advances, there is still a large gap: all existing OPRAM schemes incur a poly-logarithmic overhead either in total work or in depth.

Our main result closes the aforementioned gap and provides an essentially optimal OPRAM scheme. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity~$N$ can be obliviously simulated in space $O(N)$, incurring only $O(\log N)$ blowup in (amortized) total work as well as in depth.

Joint work with: Ilan Komargodski, Wei-Kai Lin, Enoch Peserico and Elaine Shi

15:00-15:50: Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs

Niv Gilboa (Ben-Gurion University)

Abstract:

A highly desirable feature of MPC protocols is guaranteed output delivery or full security, where denial-of-service attacks are not possible, and honest parties are guaranteed to receive a correct output.

We present an efficient protocol for any constant number of parties n, with t<n/2 corrupted parties, that makes a black-box use of a PRG.

Our protocol evaluates an arithmetic circuit C over a finite ring (either a finite field or the ring of integers modulo a power of 2) with communication complexity of 3tS/(2t+1) + o(S) ring-elements per party, where S is the number of multiplication gates in C (namely, less than 1.5 elements per party per gate). This matches the best known protocols for the semi-honest model up to the sublinear additive term, and improves on previous protocols in this setting by a constant factor for circuits over big fields, and by at least a log n factor for Boolean circuits or circuits over rings.

Joint work with Elette Boyle, Yuval Ishai and Ariel Nof

16:00-16:50: Post-Quantum Multiparty Computation

Dakshita Khurana (University of Illinois Urbana-Champaign)

Abstract:

This talk will describe the first constant round post-quantum MPC protocol in the plain model, for general classical functionalities.

The protocol relies on a new straight-line non-black-box simulation technique, where the simulator homomorphically evaluates the adversary’s circuit on independently encrypted transcripts. We call this technique “parallel no-cloning simulation”. The protocol also relies on other new tools, including spooky encryption for relations computable by quantum circuits, and post-quantum non-malleable commitments in constant rounds. I will describe some of these tools and how they are used to obtain post-quantum MPC. No prior background in quantum computing or quantum cryptography will be assumed.

This talk is based on joint work with Amit Agarwal, James Bartusek, Giulio Malavolta and Vipul Goyal.

17:00-17:25: Reusable Two-Round MPC from DDH

James Bartusek (UC Berkeley), Sanjam Garg (UC Berkeley), Daniel Masny (Visa Research) and Pratyay Mukherjee (Visa Research)

Paper

17:25-17:50: Candidate iO from Homomorphic Encryption Schemes

Zvika Brakerski (Weizmann Institute of Science), Nico Döttling (CISPA Helmholtz Center for Information Security), Sanjam Garg (UC Berkeley) and Giulio Malavolta (UC Berkeley & CMU)

Paper

15:00-15:50: Adversarial Level Agreements

Seny Kamara (Brown University)

16:00-16:50: MPC for thousands, or millions, of parties

Dov Gordon (George Mason University)

Abstract:

We will talk about two recent results on large scale MPC. In the first, we consider the specific application of performing MPC on more than 6,000 Tor relays. We let the application dictate both security and network parameters, which leads to several interesting constraints: 1) a majority of bandwidth is honest, rather than a majority of parties, 2) although we do not guarantee output, we take reasonable measures to prevent denial of service attacks, and honest failures, and 3) we ensure good bottleneck complexity, distributing the communication load throughout the network. Motivated by the previous solution, we then turn to a more general setting where n/2 - O(n) parties are malicious. We present a new protocol in which, for n parties and statistical security parameter k, the per-party communication per-triple is O(k/n), providing increasingly better performance as more parties join. Although ours is not the first protocol with such a property, when computing a circuit of size C, ours outperforms prior results by O(log C). It is also concretely efficient, and simple to describe.

17:00-17:25: PSI from PaXoS

Benny Pinkas (Bar-Ilan University), Mike Rosulek (Oregon State University), Ni Trieu (UC Berkeley) and Avishay Yanai (VMware Research)

Paper

17:25-17:50: Private Matching for Compute

Prasad Buddhavarapu, Andrew Knox, Payman Mohassel, Shubho Sengupta, Erik Taubeneck and Vlad Vlaskin (Facebook)

Paper

15:00-15:50: Towards Concretely Secure MPC

Xiao Wang (Northwestern University)

Abstract:

Secure multi-party computation is being gradually adopted in practice. With recent efforts from NIST on standardizing threshold cryptography, it becomes crucial to understand the exact (or concrete) level of security that an MPC protocol can provide. In this talk, I will describe some recent efforts in this direction.

1. In the first part, I will talk about our recent work on formalizing the use of fixed-key block ciphers in MPC and analyze its concrete security. (http://ia.cr/2019/074)

2. In the second part, I will talk about some caveats in concrete security when using a fixed-key block cipher and how to rescue them without sacrificing performance. (http://ia.cr/2019/1168)

16:00-16:25: Efficient Constant-Round MPC with Identifiable Abort and Public Veriability

Carsten Baum (Aarhus University), Emmanuela Orsini (KU Leuven), Peter Scholl (Aarhus University) and Eduardo Soria-Vazquez (Aarhus University)

16:25-16:50: Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits

Aner Moshe Ben-Efraim (Ariel University), Kelong Cong (imec-COSIC, KU Leuven), Eran Omri (Ariel University), Emmanuela Orsini (imec-COSIC, KU Leuven), Nigel P. Smart (imec-COSIC, KU Leuven and University of Bristol) and Eduardo Soria-Vazquez (Aarhus University)

17:00-17:50: Efficient Pseudorandom Correlation Generators From LPN and Ring-LPN

Peter Scholl (Aarhus University)

Abstract:

Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better asymptotic and concrete efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated very efficiently using a cheap, one-time interaction, followed by only "silent" local computation. This is achieved via a *pseudorandom correlation generator* (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation.

In this talk, I will present constructions of efficient PCGs based on different flavors of the *LPN* and *ring-LPN* assumptions. Concretely, these PCGs can generate vector-OLE, OLE correlations, authenticated Beaver triples, and other types of useful correlations over large fields. The constructions have good concrete efficiency and can be used to improve the preprocessing phase of many existing MPC protocols.

Based on joint work with Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai and Lisa Kohl.

15:00-15:50: TBA: The Bad Adversary - Dealing with Malice in Private Set Intersection Cardinality-Sum Problem

Moti Yung (Google)

Abstract

I am going to cover Private Set Intersection (PSI) and its extensions to PSI-cardinality and PSI-cardinality-sum. I will explain the business needs and the properties of a solutions that led to Shuffled-Distributed-Oblivious-PRF based constructions for this problem (in an actual industry setting). I will review the honest-but-curious solution, and will describe how to use it as a blueprint for designing a malicious security version, which keeps efficiency (as much as possible), and other properties as much as possible as well, for the extended adversarial setting. This gives an "Efficient Integrity by Design" methodology that securely builds protocols from components compatible with efficient ZK proofs to give malicious security.

Paper

16:00-16:25: JPMatch: Privacy Preserving Auctions for Stock Trading

Tucker Balch, Hans Buehler, Benjamin Diamond, Richard Hua, Antigoni Polychroniadou and Manuela Veloso (JPMorgan)

16:25-16:50: Putting MPC to use - challenges and opportunities in real world settings

Mads Schaarup Andersen and Laura Lynggaard Nielsen (The Alexandra Institute)

17:00-17:25: HedaX - HEalth DAta eXchange

Tore Frederiksen (The Alexandra Institute), Jonas Lindstrøm (The Alexandra Institute), Benny Pinkas (Bar-Ilan University) and Nikolaj Volgushev (Pleo)

17:25-17:50: Application of Multi-Party Computation to Biomedical Data Sharing

Hyunghoon Cho (Broad Institute of MIT and Harvard), Brian Hie (MIT), David J. Wu (University of Virginia) and Bonnie Berger (MIT)

Paper 1, Paper 2

15:00-15:25: Multiparty Generation of an RSA Modulus

Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield and abhi shelat (Northeastern University)

Paper

15:25-15:50: Efficient Protocols for Oblivious Linear Function Evaluation from Ring-LWE

Carsten Baum (Aarhus University), Daniel Escudero (Aarhus University), Alberto Pedrouzo-Ulloa (Universidad de Vigo), Peter Scholl (Aarhus University) and Juan Troncoso-Pastoriza (EPFL)

16:00-16:25: Secure parallel computation on national scale volumes of data

Sahar Mazloom (George Mason University), Phi Hung Le (George Mason University), Samuel Ranellucci (Unbound Tech) and S. Dov Gordon (George Mason University)

Paper

16:25-16:50: Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits

Daniel Escudero (Aarhus University), Satrajit Ghosh (Aarhus University), Marcel Keller (Data61), Rahul Rachuri (Aarhus University) and Peter Scholl (Aarhus University)

Paper

17:00-17:50: Endemic Oblivious Transfer ~ Constructions and Open problem

Peter Rindal (Visa Research)

Paper

Abstract:

Oblivious Transfer has played a crucial role in the design of secure multi party computation. Nevertheless, there are not many practical solutions that achieve simulation based security and at the same time instantiable based on different assumptions.

In this work, we consider a simulation based security notion that we call endemic security. We show how to construct highly efficient oblivious transfer in the random oracle model that achieves endemic security under a wide range of assumptions, among them DDH, CDH, LWE and coding based assumptions. We construct a secure oblivious transfer based on DDH that takes only a single communication round which allows significant performance gains. We also instantiate our oblivious transfer with the Crystals.Kyber key agreement. Our implementation shows that both instantiations can be computed in under one millisecond.

Further, we revisit, correct and improve existing oblivious transfer extension techniques. We provide an implementation of an oblivious transfer extension protocol in the ideal cipher model that is actively secure, processing up to 23 million OTs per second and up to 10 times faster than previous secure implementations. We also show that our framework can compute endemically secure OT extension and the base OTs in just two rounds.

15:00-15:50: SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search

Ilaria Chillotti (Zama)

Abstract:

The k-Nearest Neighbor Search (k-NNS) is the backbone of several cloud-based services such as recommender systems, face recognition, and database search on text and images. In these services, the client sends the query to the cloud server and receives the response in which case the query and response are revealed to the service provider. Such data disclosures are unacceptable in several scenarios due to the sensitivity of data and/or privacy laws. In this paper, we introduce SANNS, a system for secure k-NNS that keeps client's query and the search result confidential. SANNS comprises two protocols: an optimized linear scan and a protocol based on a novel sublinear time clustering-based algorithm. We prove the security of both protocols in the standard semi-honest model. The protocols are built upon several state-of-the-art cryptographic primitives such as lattice-based additively homomorphic encryption, distributed oblivious RAM, and garbled circuits. We provide several contributions to each of these primitives which are applicable to other secure computation tasks. Both of our protocols rely on a new circuit for the approximate top-k selection from n numbers that is built from O(n+k^2) comparators. We have implemented our proposed system and performed extensive experimental results on four datasets in two different computation environments, demonstrating more than 18-31x faster response time compared to optimally implemented protocols from the prior work. Moreover, SANNS is the first work that scales to the database of 10 million entries, pushing the limit by more than two orders of magnitude.

(Joint work with Hao Chen, Yihe Dong, Oxana Poburinnaya, Ilya Razenshteyn and M. Sadegh Riazi)

Paper

16:00-16:25: CrypTFlow: Secure TensorFlow Inference

Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, Rahul Sharma (Microsoft Research)

Paper

16:25-16:50: Stop Putting Neural Networks in Ideal Functionalities!

David Berthelot (Google), Nicholas Carlini (Google), Matthew Jagielski (Northeastern University), Alex Kurakin (Google), Ilya Mironov (Facebook) and Nicolas Papernot (University of Toronto)

Paper 1, Paper 2

17:00-17:25: CryptoSPN: Privacy-preserving Machine Learning beyond Neural Networks

Amos Treiber, Alejandro Molina, Christian Weinert, Thomas Schneider and Kristian Kersting (Technical University of Darmstadt)

Paper

17:25-17:50: DELPHI : A Cryptographic Inference Service for Neural Networks

Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng and Raluca Ada Popa (UC Berkeley)

Paper