Dov Gordon

Paper will be available for download soon.
Secure multi-party computation (MPC) allows multiple par-ties to perform secure joint computations on their private inputs. To-day, applications for MPC are growing with thousands of parties wish-ing to build federated machine learning models or trusted setups forblockchains. To address such scenarios we propose a novel MPC proto-col that maximizes throughput when run with large numbers of parties.In particular, our protocol has both communication and computationcomplexity that decrease with the number of parties. In particular, weshow that when used as a triple-generating service to produce offlinematerial for general MPC protocols, our construction achieves a totalthroughput of 320 million triples per second when run with approxi-mately 1 million parties. Our protocol builds on prior protocols based onpacked secret-sharing, introducing new approaches to optimally leveragepacked sharing for general (unpacked) computation.

Download.
We revisit the problem of performing secure computation of graph-parallel algorithms, focusing on the applications of securely outsourcing matrix factorization, and histograms. Leveraging recent results in low-communication secure multiparty computation, and a security relaxation that allows the computation servers to learn some differentially private leakage about user inputs, we construct a new protocol that reduces overall runtime by 320X, reduces the number of AES calls by 750X, and reduces the total communication by 200X. Our system can securely compute histograms over 300 million items in about 4 minutes, and it can perform sparse matrix factorization, which is commonly used in recommendation systems, on 20 million records in about 6 minutes.1 Furthermore, in contrast to prior work, our system is secure against a malicious adversary that corrupts one of the computing servers.

Download.
Tor is a tool for Internet privacy with millions of daily users. The Tor system benefits in many ways from information gathered about the operation of its network. Measurements guide operators in diagnosing problems, direct the efforts of developers, educate users about the level of privacy they obtain, and inform policymakers about Tor's impact. However, data collection and reporting can degrade user privacy, contradicting Tor's goals. Existing approaches to measuring Tor have limited capabilities and security weaknesses. We present Stormy, a general-purpose, privacy-preserving measurement system that overcomes these limitations. Stormy uses secure multiparty computation (MPC) to compute any function of the observations made by Tor relays, while keeping those observations secret. Stormy makes use of existing efficient MPC protocols that are secure in the malicious model, and in addition it includes a novel input-sharing protocol that is secure, efficient, and fault tolerant. The protocol is non-interactive, which is consistent with how relays currently submit measurements, and it allows the relays to go offline after input submission, even while ensuring that an honest relay will not have its input excluded or modified. The input-sharing protocol is compatible with MPC protocols computing on authenticated values and may be of independent interest. We show how Stormy can be deployed in two realistic models: (1) run primarily by a small set of dedicated authorities, or (2) run decentralized across the relays in the Tor network. Stormy scales efficiently to Tor's thousands of relays, tolerates network churn, and provides security depending only on either Tor's existing trust assumption that at least one authority is honest (in the first model) or the existing assumption that a large fraction of relay bandwidth is honest (in the second model). We demonstrate how to use the system to compute two broadly-applicable statistics: the median of relay inputs and the cardinality of set-union across relays. We implement Stormy and experimentally evaluate system performance. When Stormy is run among authorities we can perform 151 median computations or 533 set-union cardinalities over 7,000 relay inputs in a single day. When run among the relays themselves, Stormy can perform 36 median computations or 134 set union cardinalities per day. Thus, both deployments enable non-trivial analytics to be securely computed in the Tor network.

Download.
We construct new protocols for two parties to securely compute on the items in their intersection. Our protocols make use of an untrusted third party that has no input. The use of this party allows us to construct highly efficient protocols that are secure against a single malicious corruption.

Download.
When performing a secure multiparty computation with a few hundred parties, using the best protocols known today, bandwidth constraints are the primary bottleneck. A long line of work demonstrates that n parties can compute a circuit C of depth d while communicating O(|C| log |C| + poly(d, n) field elements per party, as long as a majority of parties are honest. However, in the malicious majority setting, a lot less is known. The work of Nielsen and Ranellucci is the first to provide constant-overhead in the communication complexity when a majority of parties are malicious; their result demonstrates feasibility, but is quite complex and impractical. In this work, we construct a new MPC protocol in the pre-processing model. We introduce a new middle-ground: our protocol has low communication and provides robustness when a majority of parties are honest, and gives security with abort (possibly with higher communication cost) when a majority of players are malicious. Robustness is impossible when a majority of parties are malicious; viewing the increased communication complexity as a form of denial of service, similar to an abort, we view our result as providing the “best of both worlds”.

Download.
We construct new four-party protocols for secure computation that are secure against a single malicious corruption. Our protocols can perform computations over a binary ring, and require sending just 1.5 ring elements per party, per gate. In the special case of Boolean circuits, this amounts to sending 1.5 bits per party, per gate. One of our protocols is robust, yet requires almost no additional communication. Our key technique can be viewed as a variant of the “dual execution” approach, but, because we rely on four parties instead of two, we can avoid any leakage, achieving the standard notion of security.

Download.
We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations. A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter λ, the servers each store 4N encrypted blocks, the client stores λ+2logN blocks, and the total communication per logical access is roughly 10logN encrypted blocks.

Download.
We explore a new security model for secure com- putation on large datasets. We assume that two servers have been employed to compute on private data that was collected from many users, and, in order to improve the efficiency of their computation, we establish a new tradeoff with privacy. Specifically, instead of claiming that the servers learn nothing about the input values, we claim that what they do learn from the computation preserves the differential privacy of the input. Leveraging this relaxation of the security model allows us to build a protocol that leaks some information in the form of access patterns to memory, while also providing a formal bound on what is learned from the leakage. We then demonstrate that this leakage is useful in a broad class of computations. We show that computations such as histograms, PageRank and matrix factorization, which can be performed in common graph-parallel frameworks such as MapReduce or Pregel, benefit from our relaxation. We implement a protocol for securely executing graph-parallel computations, and evaluate the performance on the three examples just mentioned above. We demonstrate marked improvement over prior implementations for these computations.

Download.
Existing systems for secure computation require programmers to express the program to be securely computed as a circuit, or in some domain-specific language that can be compiled to a form suitable for applying known protocols. We propose a new system that can securely execute native MIPS code with no special annotations. Our system has the advantage of allowing programmers to use a language of their choice to express their programs, together with any off-the-shelf compiler to MIPS; it can be used for secure computation of existing “legacy” MIPS code as well. Our system uses oblivious RAM for fetching instructions and performing load/store operations in memory, and garbled universal circuits for the execution of a MIPS ALU in each instruction step. We also explore various optimizations based on an offline analysis of the MIPS code to be executed, in order to minimize the overhead of executing each instruction while still maintaining security.

Download.
The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In this work, we consider the \emph{bounded leakage} and the \emph{continual leakage} models. In the bounded leakage model (Akavia et al. -- TCC 2009), it is assumed that there is a fixed upper bound LL on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al. -- FOCS 2010, Dodis et al. -- FOCS 2010), the lifetime of a cryptographic scheme is divided into ``time periods'' between which the scheme's secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period. In the continual leakage model, a challenging problem has been to provide security against \emph{leakage on key updates}, that is, leakage that is a function not only of the current secret key but also the \emph{randomness used to update it}. We propose a new, modular approach to overcome this problem. Namely, we present a compiler that transforms any public-key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call \emph{consecutive} continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming \emph{indistinguishability obfuscation} (Barak et al. --- CRYPTO 2001, Garg et al. -- FOCS 2013). Under the stronger assumption of \emph{public-coin differing-inputs obfuscation} (Ishai et al. -- TCC 2015) the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is obtained by making a new connection between the problems of leakage on key updates and so-called ``sender-deniable'' encryption (Canetti et al. -- CRYPTO 1997), which was recently realized for the first time by Sahai and Waters (STOC 2014). In the bounded leakage model, we develop a new approach to constructing leakage-resilient encryption from obfuscation, based upon the public-key encryption scheme from \iO\iO and punctured pseudorandom functions due to Sahai and Waters (STOC 2014). In particular, we achieve leakage-resilient public key encryption tolerating LL bits of leakage for any LL from \iO\iO and one-way functions. We build on this to achieve leakage-resilient public key encryption with optimal leakage rate of 1−o(1)1−o(1) based on public-coin differing-inputs obfuscation and collision-resistant hash functions. Such a leakage rate is not known to be achievable in a generic way based on public-key encryption alone. We then develop entirely new techniques to construct a new public key encryption scheme that is secure under (consecutive) continual leakage resilience (under appropriate assumptions), which we believe is of independent interest.

Download.
We study the round complexity of multiparty computation with fairness and guaranteed output delivery, assuming existence of an honest majority. We demonstrate a new lower bound and a matching upper bound. Our lower bound rules out any two-round fair protocols in the standalone model, even when the parties are given access to a common reference string (CRS). The lower bound follows by a reduction to the impossibility result of virtual black box obfuscation of arbitrary circuits. Then we demonstrate a three-round protocol with guarantee of output delivery, which in general is harder than achieving fairness (since the latter allows the adversary to force a fair abort). We develop a new construction of a threshold fully homomorphic encryption scheme, with a new property that we call ``flexible'' ciphertexts. Roughly, our threshold encryption scheme allows parties to adapt flexible ciphertexts to the public keys of the non-aborting parties, which provides a way of handling aborts without adding any communication.

Download.
Functional encryption (FE) is a powerful primitive enabling fine-grained access to encrypted data. In an FE scheme, secret keys (“tokens”) correspond to functions; a user in possession of a ciphertext ct = Enc(x) and a token TKf for the function f can compute f(x) but learn nothing else about x. An active area of research over the past few years has focused on the development of ever more expressive FE schemes. In this work we introduce the notion of multi-input functional encryption. Here, informally, a user in possession of a token TKf for an n-ary function f and multiple ciphertexts ct1 = Enc(x1 ),... , ct_n = Enc(x_n) can compute f(x1,...,xn) but nothing else about the {xi}. Besides introducing the notion, we explore the feasibility of multi-input FE in the public-key and symmetric-key settings, with respect to both indistinguishability-based and simulation-based definitions of security. Download the paper here.

Download.
At TCC 2013, Choi et al. introduced the notion of multi-client verifiable computation in which a set of clients outsource to an untrusted server the computation of a function f over their collective inputs in a sequence of time periods. In that work, the authors defined and realized multi-client verifiable computation satisfying soundness against a malicious server and privacy against the semi-honest corruption of a single client.

We explore the possibility of achieving stronger security guarantees in this setting, in several respects. We begin by introducing a simulation-based notion of security in the universal com- posability framework, which provides a clean way of defining soundness and privacy in a single definition. We show the notion is impossible to achieve, even in the semi-honest case, if client- server collusion is allowed. Faced with this result, we explore several meaningful relaxations and give constructions realizing them.

Download.
We investigate the relationship between Functional Encryption (FE) and Fully Homomorphic Encryption (FHE), demonstrating that, under certain assumptions, a Functional Encryption scheme supporting evaluation on two ci- phertexts implies Fully Homomorphic Encryption. We first introduce the notion of Randomized Functional Encryption (RFE), a generalization of Functional En- cryption dealing with randomized functionalities of interest in its own right, and show how to construct an RFE from a (standard) semantically secure FE. For this we define the notion of entropically secure FE and use it as an intermediary step in the construction. Finally we show that RFEs constructed in this way can be used to construct FHE schemes thereby establishing a relation between the FHE and FE primitives. We conclude the paper by recasting the construction of RFE schemes in the context of obfuscation.

Halevi, Lindell, and Pinkas (CRYPTO 2011) recently proposed a model for secure computation that captures communication patterns that arise in many practical settings, such as secure computation on the web. In their model, each party interacts only once, with a single centralized server. Parties do not interact with each other; in fact, the parties need not even be online simultaneously.

In this work we present a suite of new, simple and efficient protocols for secure computation in this "one-pass" model. We give protocols that obtain optimal privacy for the following general tasks: -- Evaluating any multivariate polynomial $F(x_1, \ldots ,x_n)$ (modulo a large RSA modulus N), where the parties each hold an input $x_i$. -- Evaluating any read once branching program over the parties' inputs.

As a special case, these function classes include all previous functions for which an optimally private, one-pass computation was known, as well as many new functions, including variance and other statistical functions, string matching, second-price auctions, classification algorithms and some classes of finite automata and decision trees. Download the paper here.

Download. (Note that this proceedings version is considerably different from the ePrint version.)

Traditional approaches to generic secure computation begin by representing the function f being computed as a circuit. If f depends on each of its input bits, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for non-trivial functions since each party must “touch” every bit of their input lest information about the other party’s input be leaked. This seems to rule out many applications of secure computation (e.g., database search) in scenarios where inputs are huge.
Adapting and extending an idea of Ostrovsky and Shoup, we present an approach to secure two-party computation that yields protocols running in sublinear time, in an amortized sense, for functions that can be computed in sublinear time on a random-access machine (RAM). Moreover, each party is required to maintain state that is only (essentially) linear in its own input size. Our protocol applies generic secure two-party computation on top of oblivious RAM (ORAM). We present an optimized version of our protocol using Yao's garbled-circuit approach and a recent ORAM construction of Shi et al.
We describe an implementation of this protocol, and evaluate its performance for the task of obliviously searching a database with over 1 million entries. Because of the cost of our basic steps, our solution is slower than Yao on small inputs. However, our implementation outperforms Yao already on DB sizes of 2^18 entries (a quite small DB by today's standards).

Download.
Group signature schemes allow users to sign messages on behalf of a group while (1) main- taining anonymity (within that group) with respect to an observer, yet (2) ensuring traceability of a signer (by the group manager) when needed. In this work we give the first construction of a group signature scheme based on lattices (more precisely, the learning with errors assump- tion), in the random oracle model. Toward our goal, we construct a new algorithm for sampling a random superlattice of a given modular lattice together with a short basis, that may be of independent interest.

Download.
A seminal result of Cleve (STOC '86) is that, in general, \emph{complete} fairness is impossible to achieve in two-party computation. In light of this, various techniques for obtaining \emph{partial} fairness have been suggested in the literature. We propose a definition of partial fairness within the standard real-/ideal-world paradigm that addresses deficiencies of prior definitions. We also show broad feasibility results with respect to our definition:~partial fairness is possible for any (randomized) functionality $f:X \times Y \rightarrow Z_1 \times Z_2$ at least one of whose domains or ranges is polynomial in size. Our protocols are always private, and when one of the domains has polynomial size our protocols also simultaneously achieve the usual notion of security with abort. In contrast to some prior work, we rely on standard assumptions only. We also show that, as far as general feasibility is concerned, our results are \emph{optimal} (with respect to our definition). Specifically, there exist functions with super-polynomial domain and range for which it is impossible to achieve our definition.

For secure two-party and multi-party computation with abort, classification of which primitives are {\em complete} has been extensively studied in the literature. However, for \emph{fair} secure computation, where (roughly speaking) either all parties learn the output or none do, the question of complete primitives has remained largely unstudied. In this work, we initiate a rigorous study of completeness for primitives that allow fair computation.  We show the following results: - \textbf{No ``short'' primitive is complete for fairness.} In surprising contrast to other notions of security for secure two-party computation, we show that for fair secure two-party computation, no primitive of size $O(\log k)$ is complete, where $k$ is a security parameter.  This is the case even if we can enforce parallelism in calls to the primitives (i.e., the adversary does not get output from any primitive in a parallel call until it sends input to all of them).  This negative result holds regardless of any computational assumptions. - \textbf{Coin Flipping and Simultaneous Broadcast are not complete for fairness.}  The above result rules out the completeness of two natural candidates: coin flipping (for any number of coins) and simultaneous broadcast (for messages of arbitrary length). - \textbf{Positive results.}  To complement the negative results, we exhibit a $k$-bit primitive that \emph{is} complete for two-party fair secure computation.  This primitive implements a ``fair reconstruction'' procedure for a secret sharing scheme with some robustness properties.  We show how to generalize this result to the multi-party setting. - \textbf{Fairness combiners.}  We also introduce the question of constructing a protocol for fair secure computation from primitives that may be faulty.  We show a simple functionality that is complete for two-party fair computation when the majority of its instances are honest. On the flip side, we show that this result is tight: no functionality is complete for fairness if half (or more) of the instances can be malicious.

 We consider the following problem: can we construct constant-round  zero-knowledge proofs (with negligible soundness) for $\NP$ assuming  only the existence of one-way permutations? We answer the question  in the negative for fully black-box constructions (using only  black-box access to both the underlying primitive and the cheating  verifier) that satisfy a natural restriction on the ``adaptivity''  of the simulator's queries.  Specifically, we show that only languages in $\coAM$ have  constant-round zero-knowledge proofs of this kind.

Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. Almost all existing protocols, however, do not distinguish between \emph{corrupted} parties (who do not follow the protocol), and \emph{honest} parties whose secret (signing) keys have been compromised (but who continue to behave honestly). We explore conditions under which it is possible to construct broadcast protocols that still provide the usual guarantees (i.e., validity/agreement) to the latter. Consider a network of $n$ parties, where an adversary has compromised the secret keys of up to $t_c$ honest parties and, in addition, fully controls the behavior of up to $t_a$ other parties. We show that for any fixed $t_c > 0$, and any fixed $t_a$, there exists an efficient protocol for broadcast if and only if $2t_a + \min(t_a, t_c) < n$. (When $t_c = 0$, standard results imply feasibility.) We also show that if $t_c, t_a$ are not fixed, but are only guaranteed to satisfy the bound above, then broadcast is impossible to achieve except for a few specific values of~$n$; for these ``exceptional'' values of~$n$, we demonstrate a broadcast protocol. Taken together, our results give a complete characterization of this problem. Invited for a special issue in Elsevier's Information and Computation journal.

Gordon et al.\ recently showed that certain (non-trivial) functions can be computed with complete fairness in the \emph{two-party} setting. Motivated by their results, we initiate a study of complete fairness in the \emph{multi-party} case and demonstrate the first completely-fair protocols for non-trivial functions in this setting. We also provide evidence that achieving fairness is "harder" in the multi-party setting, at least with regard to round complexity.

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is \emph{fairness}, which guarantees that if either party receives its output, then the other party does too. Cleve (STOC~1986) showed that complete fairness cannot be achieved \emph{in general} in the two-party setting; specifically, he showed (essentially) that it is impossible to compute Boolean XOR with complete fairness. Since his work, the accepted folklore has been that \emph{nothing} non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s. In this paper, we demonstrate that this widely held folklore belief is \emph{false} by showing completely-fair secure protocols for various non-trivial two-party functions including Boolean AND/OR as well as Yao's ``millionaires' problem''. Surprisingly, we show that it is even possible to construct completely-fair protocols for certain functions containing an ``embedded XOR'', although in this case we also prove a lower bound showing that a super-logarithmic number of rounds are necessary. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

We consider the problem of secret sharing among $n$ rational players. This problem was introduced by Halpern and Teague (STOC 2004), who claim that a solution is \emph{impossible} for $n=2$ but show a solution for the case $n\geq 3$. Contrary to their claim, we show a protocol for rational secret sharing among $n=2$ players; our protocol extends to the case $n\geq 3$, where it is simpler than the Halpern-Teague solution and also offers a number of other advantages.  We also show how to avoid the continual involvement of the dealer, in either our own protocol or that of Halpern and Teague. Our techniques extend to the case of rational players trying to securely compute an arbitrary function, under certain assumptions on the utilities of the players.

Download.
Secure computation is a fundamental problem in modern cryptography in which mul- tiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980’s demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their out- put. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties.
The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guaran- tee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impos- sibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the pres- ence of rational adversaries, and, finally, we further study the difficulty of achieving fairness by exploring how much external help is necessary for enabling fair secure computation.