TPMPC 2022 Invited Talks
Below are the abstracts of all the invited talks.
Currencies, Crypto and Policy: the Good, the Bad and the Ugly
Ran Canetti (Boston University)
New MPC Techniques for Secure Machine Learning
Nishanth Chandran (Microsoft Research)
Machine learning algorithms typically operate over floating-point arithmetic, while MPC is more efficient when emulating fixed-point arithmetic. State-of-the-art converters that transform floating-point ML algorithms into fixed-point ones rely on various types of underlying computations. Examples of these include those that work with varied bitlength and scale, as well as precise representations of math functions such as tanh and sigmoid. In this talk, I will provide an overview of recent work that provides cryptographic protocols for these computations thus allowing for a much wider class of ML algorithms to be executed efficiently using MPC.
Dew: Transparent Constant-sized zkSNARKs
Chaya Ganesh (IISc Bangalore)
We construct polynomial commitment schemes with constant sized evaluation proofs and logarithmic verification time in the transparent setting. Our starting point is a transparent inner product commitment scheme with constant-sized proofs and linear verification. We build on this to construct a polynomial commitment scheme with constant size evaluation proofs and logarithmic (in the degree of the polynomial) verification time. Our constructions make use of groups of unknown order instantiated by class groups. We prove security of our construction in the Generic Group Model (GGM). Using our polynomial commitment scheme to compile an information-theoretic proof system yields Dew - a transparent and constant-sized zkSNARK (Zero-knowledge Succinct Non-interactive ARguments of Knowledge) with logarithmic verification.Finally, we show how to recover the result of DARK (Bünz et al., Eurocrypt 2020). DARK presented a succinct transparent polynomial commitment scheme with logarithmic proof size and verification. However, it was recently discovered to have a gap in its security proof (Block et al, CRYPTO 2021). We recover its extractability based on our polynomial commitment construction, thus obtaining a transparent polynomial commitment scheme with logarithmic proof size and verification under same assumptions as DARK.
Based on joint work with Arasu Arun, Satya Lokam, Tushar Mopuri and Sriram Sridhar.
Communication Efficient MPC using Packed Secret Sharing
Vipul Goyal (Carnegie Mellon University)
Private Computing on Public Blockchains
Shai Halevi (Algorand Foundation)
Public blockchains have emerged over the last decade as a promising architecture for distributed computing, touted by some as "the world's computer". Using "smart contracts" with public execution backed by agreement protocol, public blockchains provide a compute environment with highly dependable results. However, the public nature of this architecture also makes is challenging to use secret data in the computations.
Our main tool is a new style of cryptographic protocols, that we term YOSO - "You Only Speak Once". These protocols use ephemeral stateless roles that operate locally for a while, then conclude their participation by broadcasting a single message. We demonstrate the usefulness of such protocols in the context of open systems, and design YOSO protocols that remain feasible even with thousands of nodes.
Based on works with Fabrice Benhamouda, Craig Gentry, Sergey Gorbunov, Hugo Krawczyk, Chengyu Lin, Vadim Lyubashevsky, Bernardo Magri, Alex Miao, Jesper Buus Nielsen, Tal Rabin, Leonid Reyzin, and Sophia Yakoubov.
New Directions in Garbled Circuits
David Heath (Georgia Tech)
Yao’s Garbled Circuit (GC) is one of our core primitives for achieving MPC. Traditionally, GC required that computations be expressed as simple Boolean circuits composed of fan-in two gates. While circuits can express any computation, efficiency is often a problem: many interesting computations compile to huge circuits that are expensive to evaluate.
The tradition of circuits is giving way to a more powerful paradigm. Over the past few years, we have seen the advent of GC techniques that handle interesting computations directly, without compiling to a circuit and without sacrificing GC’s important constant-round property. Today, we have techniques that directly handle finite field arithmetic, vector operations, conditional control flow, and even RAM access. For many applications, these new techniques asymptotically reduce cost. Even better, these techniques will continue to improve, and completely new techniques will likely emerge. Today, the state of the art in GC is not circuits, but rather a paradigm where we mix and match powerful techniques, using the right tool for the job: a full language of garbled computation.
In this talk, I will present these new directions and the evolution from garbled circuits to garbled computation. I will discuss how these new directions are achieved, how they differ from the tradition of Boolean gates, and how we can seek further improvement. My focus will be on our recent improvement to Garbled RAM access (Heath et al., Eurocrypt 2022) which combines many important high-level ideas that underlie this new paradigm.
Correlated Pseudorandomness from Expand-Accumulate Codes
Lisa Kohl (CWI Amsterdam)
A pseudorandom correlation generator (PCG) is a recent tool for securely generating useful sources of correlated randomness, such as random oblivious transfers (OT) and vector oblivious linear evaluations (VOLE), with low communication cost.
We introduce a simple new design for PCGs based on so-called expand-accumulate codes, which first apply a sparse random expander graph to replicate each message entry, and then accumulate the entries by computing the sum of each prefix. Our design offers the following advantages compared to state-of-the-art PCG constructions:
- Competitive concrete efficiency backed by provable security against relevant classes of attacks;
- An offline-online mode that combines near-optimal cache-friendliness with simple parallelization;
- Concretely efficient extensions to pseudorandom correlation functions, which enable incremental generation of new correlation instances on demand, and to new kinds of correlated randomness that include circuit-dependent correlations.
To further improve the concrete computational cost, we propose a method for speeding up a full-domain evaluation of a puncturable pseudorandom function (PPRF). This is independently motivated by other cryptographic applications of PPRFs.
This is joint work with Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Nicolas Resch and Peter Scholl.
OMG! People are Actually Implementing my MPC Papers!
Yehuda Lindell (Coinbase)
In this talk, I will talk about about some of the dangers occurring due to a major shift in the MPC space related to the fact that MPC is now being deployed globally. Academic papers are written for the purpose of advancing science, and often not with the awareness that people are now actually implementing them. It is clear to us that papers are not specifications, and cannot be implemented without expertise. However, the way papers are often written actually make them especially hard for implementation, even for people with cryptographic expertise. In this talk, we will show real-world examples of what goes wrong and discuss how papers can be written to minimize the damage. In addition, we will discuss how a different mindset when designing protocols can sometimes be of benefit. We will also describe a new construction of a multiparty protocol for generating Schnorr signatures and demonstrate some of the principles in its presentation.
Can We Obfuscate Quantum Circuits?
Giulio Malavolta (Max Planck Institute)
In this talk we investigate the following questions: Can we obfuscate quantum circuits? We discuss definitions, opportunities and barriers towards achieving this new “holy grail” of quantum cryptography. We present a construction for null quantum circuits (i.e., quantum circuits that always reject) assuming:
- The quantum hardness of learning with errors (LWE).
- Post-quantum indistinguishability obfuscation for classical circuits.
- A notion of ''dual-mode'' classical verification of quantum computation (CVQC).
Then we show how quantum null-iO enables a series of new cryptographic primitives that were not know to exist prior to our work. If time permits, we will also survey the state of the art in post-quantum obfuscation for classical circuits.
Based on a joint work with James Bartusek (presented at QIP’22 and ITCS’22)
From ATLAS to TurboPack: Efficient Honest Majority MPC
Antigoni Polychroniadou (JP Morgan)
In this talk, I'll talk about our recent results in the honest majority setting which improve the seminal work of Damgard and Nielsen from 2007 (ATLAS) and achieve constant online communication in the preprocessing model (TurboPack).
ATLAS: Efficient and Scalable MPC in the Honest Majority Setting. Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, and Yifan Song.
https://eprint.iacr.org/2021/833
TurboPack: Honest Majority MPC with Constant Online Communication. Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, and Yifan Song.
Carbyne Stack – Open-source cloud-native Secure Multiparty Computation
Sven Trieflinger (Robert Bosch GmbH)
Data has become a strategic asset that is pooled with others for joint processing, monetized on data platforms, and used to fuel the AI revolution. As the ability to leverage internal and external data is becoming a major factor for business success, protecting valuable data is more important than ever. Computing on Encrypted Data technologies in general and Secure Multiparty Computation (MPC) in particular pave the way for strong end-to-end protection of data by enabling encryption in use.
One roadblock for the wider adoption of MPC so far has been the lack of integration with state-of-the-art cloud technology to enable resilient, observable, and manageable MPC deployments at scale. The Carbyne Stack open-source project has set out to close this gap by lifting MPC into the cloud.
This talk will shed light on various aspects of Carbyne Stack: Why did Bosch Research start this initiative? How does the architecture and design of Carbyne Stack reflect the special characteristics of MPC? How can cloud-native technologies help in solving the challenges of scaling MPC workloads? In addition, the audience will get an outlook on what's next for Carbyne Stack and how interested individuals, institutions, and companies can contribute to the Carbyne Stack open-source project.
Broadcast-Optimal Two-Round MPC with an Honest Majority
Sophia Yakoubov, Divya Ravi , Luisa Sinischalchi (Aarhus University)