## CryptoDB

### Abhi Shelat

#### Publications

**Year**

**Venue**

**Title**

2022

EUROCRYPT

Guaranteed Output in O(sqrt(n)) Rounds for Round-Robin Sampling Protocols
📺
Abstract

We introduce a notion of round-robin secure sampling that captures several protocols in the literature, such as the "powers-of-tau" setup protocol for pairing-based polynomial commitments and zk-SNARKs, and certain verifiable mixnets.
Due to their round-robin structure, protocols of this class inherently require n sequential broadcast rounds, where n is the number of participants.
We describe how to compile them generically into protocols that require only O(sqrt(n)) broadcast rounds. Our compiled protocols guarantee output delivery against any dishonest majority. This stands in contrast to prior techniques, which require Omega(n) sequential broadcasts in most cases (and sometimes many more). Our compiled protocols permit a certain amount of adversarial bias in the output, as all sampling protocols with guaranteed output must, due to Cleve's impossibility result (STOC'86). We show that in the context of the aforementioned applications, this bias is harmless.

2022

ASIACRYPT

Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation
📺
Abstract

The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover P*(x) on some theorem x, is able to produce a witness w for x with roughly the same probability that P* produces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable computation where the goal is compressing a proof.
Pass (CRYPTO '03) first showed how to achieve this property for NP using a cut-and-choose technique which incurred a \lambda^2-bit overhead in communication where \lambda is a security parameter. Fischlin (CRYPTO '05) presented a more efficient technique based on ``proofs of work'' that sheds this \lambda^2 cost, but only applies to a limited class of Sigma Protocols with a ``quasi-unique response'' property, which for example, does not necessarily include the standard OR composition for Sigma protocols.
With Schnorr/EdDSA signature aggregation as a motivating application, we develop new techniques to improve the computation cost of straight-line extractable proofs. Our improvements to the state of the art range from 70x--200x for the best compression parameters. This is due to a uniquely suited polynomial evaluation algorithm, and the insight that a proof-of-work that relies on multicollisions and the birthday paradox is faster to solve than inverting a fixed target.
Our collision based proof-of-work more generally improves the Prover's random oracle query complexity when applied in the NIZK setting as well. In addition to reducing the query complexity of Fischlin's Prover, for a special class of Sigma protocols we can for the first time closely match a new lower bound we present.
Finally we extend Fischlin's technique so that it applies to a more general class of strongly-sound Sigma protocols, which includes the OR composition. We achieve this by carefully randomizing Fischlin's technique---we show that its current deterministic nature prevents its application to certain multi-witness languages.

2020

PKC

Going Beyond Dual Execution: MPC for Functions with Efficient Verification
📺
Abstract

The dual execution paradigm of Mohassel and Franklin (PKC’06) and Huang, Katz and Evans (IEEE ’12) shows how to achieve the notion of 1-bit leakage security at roughly twice the cost of semi-honest security for the special case of two-party secure computation . To date, there are no multi-party computation (MPC) protocols that offer such a strong trade-off between security and semi-honest performance. Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function f ( x , y ) is efficiently verifiable by g if the running time of g is always smaller than f and $$g(x,y,z)=1$$ if and only if $$f(x,y)=z$$ . In the two-party setting, we first improve dual execution by observing that the “second execution” can be an evaluation of g instead of f , and that by definition, the evaluation of g is asymptotically more efficient. Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for f that is secure up to additive errors and any active protocol for g . An important result by Genkin et al. (STOC ’14) shows how the classic protocols by Goldreich et al. (STOC ’87) and Ben-Or et al. (STOC ’88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols. A key technical result we prove is that the passive protocol for distributed garbling due to Beaver et al. (STOC ’90) is in fact secure up to additive errors against malicious adversaries, thereby, yielding another powerful instantiation of our paradigm in the constant-round multi-party setting. As another concrete example of instantiating our approach, we present a novel protocol for computing perfect matching that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.

2020

CRYPTO

Multiparty Generation of an RSA Modulus
📺
Abstract

We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring.
Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto'18), and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt'19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime, and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.

2019

CRYPTO

Adaptively Secure MPC with Sublinear Communication Complexity
📺
Abstract

A central challenge in the study of MPC is to balance between security guarantees, hardness assumptions, and resources required for the protocol. In this work, we study the cost of tolerating adaptive corruptions in MPC protocols under various corruption thresholds. In the strongest setting, we consider adaptive corruptions of an arbitrary number of parties (potentially all) and achieve the following results:A two-round secure function evaluation (SFE) protocol in the CRS model, assuming LWE and indistinguishability obfuscation (iO). The communication, the CRS size, and the online-computation are sublinear in the size of the function. The iO assumption can be replaced by secure erasures. Previous results required either the communication or the CRS size to be polynomial in the function size.Under the same assumptions, we construct a “Bob-optimized” 2PC (where Alice talks first, Bob second, and Alice learns the output). That is, the communication complexity and total computation of Bob are sublinear in the function size and in Alice’s input size. We prove impossibility of “Alice-optimized” protocols.Assuming LWE, we bootstrap adaptively secure NIZK arguments to achieve proof size sublinear in the circuit size of the NP-relation.
On a technical level, our results are based on laconic function evaluation (LFE) (Quach, Wee, and Wichs, FOCS’18) and shed light on an interesting duality between LFE and FHE.Next, we analyze adaptive corruptions of all-but-one of the parties and show a two-round SFE protocol in the threshold PKI model (where keys of a threshold FHE scheme are pre-shared among the parties) with communication complexity sublinear in the circuit size, assuming LWE and NIZK. Finally, we consider the honest-majority setting, and show a two-round SFE protocol with guaranteed output delivery under the same constraints.

2018

PKC

Multi-Key Searchable Encryption, Revisited
Abstract

We consider a setting where users store their encrypted documents on a remote server and can selectively share documents with each other. A user should be able to perform keyword searches over all the documents she has access to, including the ones that others shared with her. The contents of the documents, and the search queries, should remain private from the server.This setting was considered by Popa et al. (NSDI ’14) who developed a new cryptographic primitive called Multi-Key Searchable Encryption (MKSE), together with an instantiation and an implementation within a system called Mylar, to address this goal. Unfortunately, Grubbs et al. (CCS ’16) showed that the proposed MKSE definition fails to provide basic security guarantees, and that the Mylar system is susceptible to simple attacks. Most notably, if a malicious Alice colludes with the server and shares a document with an honest Bob then the privacy of all of Bob’s search queries is lost.In this work we revisit the notion of MKSE and propose a new strengthened definition that rules out the above attacks. We then construct MKSE schemes meeting our definition. We first give a simple and efficient construction using only pseudorandom functions. This construction achieves our strong security definition at the cost of increasing the server storage overhead relative to Mylar, essentially replicating the document each time it is shared. We also show that high server storage overhead is not inherent, by giving an alternate (albeit impractical) construction that manages to avoid it using obfuscation.

2013

TCC

#### Program Committees

- Crypto 2021
- TCC 2020
- Eurocrypt 2019
- Crypto 2018
- Eurocrypt 2017
- Crypto 2016
- TCC 2015
- Asiacrypt 2014
- TCC 2013
- Eurocrypt 2013
- Crypto 2010
- PKC 2008
- TCC 2008

#### Coauthors

- Jae Hyun Ahn (2)
- Joël Alwen (2)
- Dan Boneh (2)
- Jan Camenisch (4)
- Rafik Chaabouni (1)
- Megan Chen (1)
- Ran Cohen (3)
- Ronald Cramer (1)
- Jack Doerner (2)
- Ariel Hamlin (1)
- Goichiro Hanaoka (1)
- Carmit Hazay (1)
- Dennis Hofheinz (1)
- Susan Hohenberger (4)
- Hideki Imai (1)
- Jonathan Katz (1)
- Eike Kiltz (1)
- Yashvanth Kondi (3)
- Eysa Lee (1)
- Matt Lepinski (1)
- Yehuda Lindell (1)
- Mohammad Mahmoody (1)
- Silvio Micali (2)
- Ameer Mohammed (1)
- Steven Myers (1)
- Soheil Nematihaji (1)
- Gregory Neven (1)
- Rafael Pass (7)
- Giuseppe Persiano (1)
- Schuyler Rosefield (1)
- Alon Rosen (1)
- Guy N. Rothblum (2)
- Lior Seeman (1)
- Mona Sergi (1)
- Chih-hao Shen (1)
- Vinod Vaikuntanathan (5)
- Muthuramakrishnan Venkitasubramaniam (2)
- Ivan Visconti (2)
- Brent Waters (2)
- Mor Weiss (1)
- Daniel Wichs (2)