## CryptoDB

### Yehuda Lindell

#### Affiliation: Bar Ilan University, Israel

#### Publications

**Year**

**Venue**

**Title**

2019

JOFC

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ
Abstract

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present a constant-round multi-party secure computation protocol that is fully secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round protocol of Beaver et al. (the BMR protocol) and is the first version of that protocol that is concretely efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase, we present both a generic construction (using any underlying MPC protocol) and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully secure multi-party protocols.

2018

CRYPTO

Fast Large-Scale Honest-Majority MPC for Malicious Adversaries
📺
Abstract

Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.In this paper, we present new protocols for securely computing any functionality represented by an arithmetic circuit. We utilize a new method for verifying that the adversary does not cheat, that yields a cost of just twice that of semi-honest protocols in some settings. Our protocols are information-theoretically secure in the presence of a malicious adversaries, assuming an honest majority. We present protocol variants for small and large fields, and show how to efficiently instantiate them based on replicated secret sharing and Shamir sharing. As with previous works in this area aiming to achieve high efficiency, our protocol is secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not.We implemented our protocol and ran experiments for different numbers of parties, different network configurations and different circuit depths. Our protocol significantly outperforms the previous best for this setting (Lindell and Nof, CCS 2017); for a large number of parties, our implementation runs almost an order of magnitude faster than theirs.

2018

CRYPTO

Fast Distributed RSA Key Generation for Semi-honest and Malicious Adversaries
📺
Abstract

We present two new, highly efficient, protocols for securely generating a distributed RSA key pair in the two-party setting. One protocol is semi-honestly secure and the other maliciously secure. Both are constant round and do not rely on any specific number-theoretic assumptions and improve significantly over the state-of-the-art by allowing a slight leakage (which we show to not affect security).For our maliciously secure protocol our most significant improvement comes from executing most of the protocol in a “strong” semi-honest manner and then doing a single, light, zero-knowledge argument of correct execution. We introduce other significant improvements as well. One such improvement arrives in showing that certain, limited leakage does not compromise security, which allows us to use lightweight subprotocols. Another improvement, which may be of independent interest, comes in our approach for multiplying two large integers using OT, in the malicious setting, without being susceptible to a selective-failure attack.Finally, we implement our malicious protocol and show that its performance is an order of magnitude better than the best previous protocol, which provided only semi-honest security.

2018

PKC

Fast Garbling of Circuits over 3-Valued Logic
Abstract

In the setting of secure computation, a set of parties wish to compute a joint function of their private inputs without revealing anything but the output. Garbled circuits, first introduced by Yao, are a central tool in the construction of protocols for secure two-party computation (and other tasks like secure outsourced computation), and are the fastest known method for constant-round protocols. In this paper, we initiate a study of garbling multivalent-logic circuits, which are circuits whose wires may carry values from some finite/infinite set of values (rather than only $$\mathsf {True}$$True and $$\mathsf {False}$$False). In particular, we focus on the three-valued logic system of Kleene, in which the admissible values are $$\mathsf {True}$$True, $$\mathsf {False}$$False, and $$\mathsf {Unknown}$$Unknown. This logic system is used in practice in SQL where some of the values may be missing. Thus, efficient constant-round secure computation of SQL over a distributed database requires the ability to efficiently garble circuits over 3-valued logic. However, as we show, the two natural (naive) methods of garbling 3-valued logic are very expensive.In this paper, we present a general approach for garbling three-valued logic, which is based on first encoding the 3-value logic into Boolean logic, then using standard garbling techniques, and final decoding back into 3-value logic. Interestingly, we find that the specific encoding chosen can have a significant impact on efficiency. Accordingly, the aim is to find Boolean encodings of 3-value logic that enable efficient Boolean garbling (i.e., minimize the number of AND gates). We also show that Boolean AND gates can be garbled at the same cost of garbling XOR gates in the 3-value logic setting. Thus, it is unlikely that an analogue of free-XOR exists for 3-value logic garbling (since this would imply free-AND in the Boolean setting).

2017

EUROCRYPT

2015

JOFC

2015

EPRINT

2015

TCC

2015

CRYPTO

2014

EPRINT

2013

TCC

2013

JOFC

A Note on Constant-Round Zero-Knowledge Proofs of Knowledge
Abstract

In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all $\mathcal {NP}$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO, 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all $\mathcal {NP}$ is folklore, to the best of our knowledge, since no proof of this fact has been published.

2012

JOFC

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer
Abstract

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao’s protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

2011

CRYPTO

2011

JOFC

2010

EPRINT

On Achieving the "Best of Both Worlds" in Secure Multiparty Computation
Abstract

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide ``full security'' (and, in particular, guarantee output delivery and fairness) when this assumption holds; unfortunately, these protocols are completely insecure if this assumption is violated. On the other hand, protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a \emph{single} party is dishonest.
It is natural to wonder whether it is possible to achieve the ``best of both worlds'': namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) but show some positive results regarding what \emph{can} be achieved.

2010

EPRINT

Black-Box Constructions of Protocols for Secure Computation
Abstract

It is well known that secure computation without an honest majority requires computational assumptions. An interesting question that therefore arises relates to the way such computational assumptions are used. Specifically, can the secure protocol use the underlying primitive (e.g., a one-way trapdoor permutation) in a {\em black-box} way, treating it as an oracle, or must it be {\em nonblack-box} (by referring to the code that computes the primitive)? Despite the fact that many general constructions of cryptographic schemes refer to the underlying primitive in a black-box wayonly, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).
In this paper, we study whether such nonblack-box use is essential. We answer this question in the negative. Concretely, we present a \emph{fully black-box reduction} from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we get the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a {\em black-box} use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption.

2010

EPRINT

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer
Abstract

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven secure under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao's protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

2009

EPRINT

Comparison-Based Key Exchange and the Security of the Numeric Comparison Mode in Bluetooth v2.1
Abstract

In this paper we study key exchange protocols in a model where the key exchange takes place between devices with limited displays that can be compared by a human user. If the devices display the same value then the human user is convinced that the key exchange terminated successfully and securely, and if they do not then the user knows that it came under attack. The main result of this paper is a rigorous proof that the numeric comparison mode for device pairing in Bluetooth version 2.1 is secure, under appropriate assumptions regarding the cryptographic functions used. Our proof is in the standard model and in particular does not model any of the functions as random oracles. In order to prove our main result, we present formal definitions for key exchange in this model and show our definition to be equivalent to a simpler definition. This is a useful result of independent interest that facilitates an easier security analysis of protocols in this model.

2009

EPRINT

Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries
Abstract

In this paper we construct efficient secure protocols for \emph{set intersection} and \emph{pattern matching}. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that are based on polynomials. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency.
Our results are presented in two adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against \emph{malicious adversaries} under a relaxed definition where one corruption case is simulatable and for the other only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a malicious adversary can cheat, but will then be caught with good probability.

2009

EPRINT

Constructions of Truly Practical Secure Protocols using Standard Smartcards
Abstract

In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full \emph{simulation-based security} in the presence of \emph{malicious adversaries}, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other (where the latter can be parallelized to further reduce the time). This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.

2009

EPRINT

Adaptively Secure Two-Party Computation with Erasures
Abstract

In the setting of multiparty computation a set of parties with private inputs wish to compute some joint function of their inputs, whilst preserving certain security properties (like privacy and correctness). An adaptively secure protocol is one in which the security properties are preserved even if an adversary can adaptively and dynamically corrupt parties during a computation. This provides a high level of security, that is arguably necessary in today's world of active computer break-ins. Until now, the work on adaptively secure multiparty computation has focused almost exclusively on the setting of an honest majority, and very few works have considered the honest minority and two-party cases. In addition, significant computational and communication costs are incurred by most protocols that achieve adaptive security.
In this work, we consider the two-party setting and assume that honest parties may \emph{erase} data. We show that in this model it is possible to securely compute any two-party functionality in the presence of \emph{adaptive semi-honest adversaries}. Furthermore, our protocol remains secure under concurrent general composition (meaning that it remains secure irrespective of the other protocols running together with it). Our protocol is based on Yao's garbled-circuit construction and, importantly, is as efficient as the analogous protocol for static corruptions. We argue that the model of adaptive corruptions with erasures has been unjustifiably neglected and that it deserves much more attention.

2008

EPRINT

Secure Multiparty Computation for Privacy-Preserving Data Mining
Abstract

In this paper, we survey the basic paradigms and notions of secure multiparty computation and discuss their relevance to the field of privacy-preserving data mining. In addition to reviewing definitions and constructions for secure multiparty computation, we discuss the issue of efficiency and demonstrate the difficulties involved in constructing highly efficient protocols. We also present common errors that are prevalent in the literature when secure multiparty computation techniques are applied to privacy-preserving data mining. Finally, we discuss the relationship between secure multiparty computation and privacy-preserving data mining, and show which problems it solves and which problems it does not.

2008

EPRINT

Efficient Fully-Simulatable Oblivious Transfer
Abstract

Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryptographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of \emph{malicious adversaries} under the \emph{real/ideal model simulation paradigm} (without using general zero-knowledge proofs). Thus, \emph{efficient protocols} that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, $N$th residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists.

2008

EPRINT

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries
Abstract

We show an efficient secure two-party protocol, based on Yao's construction, which provides security against malicious adversaries. Yao's original protocol is only secure in the presence of semi-honest adversaries, and can be transformed into a protocol that achieves security against malicious adversaries by applying the compiler of Goldreich, Micali and Wigderson (the ``GMW compiler''). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs.
Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the {\sf ideal/real simulation paradigm}, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running $O(1)$ oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao's protocol does \emph{not} yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security.
Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party computation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a statistical security parameter. These two reductions are comparable to Kilian's reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit~\cite{Kil}.

2008

EPRINT

Complete Fairness in Secure Two-Party Computation
Abstract

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, security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved, in general, without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late '80s.
In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an ``embedded XOR''; this class of functions includes boolean AND/OR as
well as Yao's ``millionaires' problem''. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

2008

EPRINT

Collusion-Free Multiparty Computation in the Mediated Model
Abstract

Collusion-free protocols prevent subliminal communication (i.e., covert channels) between parties running the protocol. In the standard communication model (and assuming the existence of one-way functions), protocols satisfying any reasonable degree of privacy cannot be collusion-free. To circumvent this impossibility result, Alwen et al. recently suggested the mediated model where all communication passes through a mediator; the goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees continue to hold if the mediator is dishonest. In this model, they gave constructions of collusion-free protocols for commitments and zero-knowledge proofs in the two-party setting.
We strengthen the definition of Alwen et al. in several ways, and resolve the key open questions in this area by showing a collusion-free protocol (in the mediated model) for computing any multi-party functionality.

2007

EUROCRYPT

2007

EPRINT

Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries
Abstract

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that no coalition of corrupted parties should be able to learn more than specified or somehow cause the result to be ``incorrect''. Typically, corrupted parties are either assumed to be semi-honest (meaning that they follow the protocol specification) or malicious (meaning that they may deviate arbitrarily from the protocol). However, in many settings, the assumption regarding semi-honest behavior does not suffice and security in the presence of malicious adversaries is excessive and expensive to achieve.
In this paper, we introduce the notion of {\em covert adversaries}, which we believe faithfully models the adversarial behavior in many commercial, political, and social settings. Covert adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be ``caught'' doing so. We provide a definition of security for covert adversaries and show that it is possible to obtain highly efficient protocols that are secure against such adversaries. We stress that in our definition, we quantify over all (possibly malicious) adversaries and do not assume that the adversary behaves in any particular way. Rather, we guarantee that if an adversary deviates from the protocol in a way that would enable it to ``cheat'' (meaning that it can achieve something that is impossible in an ideal model where a trusted party is used to compute the function), then the honest parties are guaranteed to detect this cheating with good probability. We argue that this level of security is sufficient in many settings.

2007

EPRINT

Secure Computation Without Authentication
Abstract

Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where all
messages sent by the parties may be tampered with and modified by the
adversary without the honest parties being able to detect this
fact. In this model, it is not possible to achieve the same level
of security as in the authenticated-channel setting. Nevertheless,
we show that meaningful security guarantees can be provided:
Essentially, all the adversary can do is to partition the network into
disjoint sets, where in each set the computation is secure in itself,
and also independent of the computation in the other sets. In the basic setting our construction provides, for the first time,
non-trivial security guarantees in a model with no set-up assumptions whatsoever. We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems
that were studied separately in the past, including password-based authenticated key exchange and non-malleable commitments. As an application of our results, we study the question of constructing secure protocols in partially-authenticated networks, where some of the links are authenticated and some are not (as is the case in most networks today).

2006

JOFC

2005

EPRINT

Concurrent Composition of Secure Protocols in the Timing Model
Abstract

In the setting of secure multiparty computation, a set of mutually
distrustful parties wish to securely compute some joint function
of their inputs. In the stand-alone case, it has been shown that
{\em every} efficient function can be securely computed.
However, in the setting of concurrent composition, broad
impossibility results have been proven for the case of no honest
majority and no trusted setup phase. These results hold both for
the case of general composition (where a secure protocol is run
many times concurrently with arbitrary other protocols) and self
composition (where a single secure protocol is run many times
concurrently).
In this paper, we investigate the feasibility of obtaining
security in the concurrent setting, assuming that each party has a
local clock and that these clocks proceed at approximately the
same rate. We show that under this mild timing assumption, it is
possible to securely compute {\em any} multiparty functionality
under concurrent \emph{self} composition. We also show that it
is possible to securely compute {\em any} multiparty
functionality under concurrent {\em general} composition, as
long as the secure protocol is run only with protocols whose
messages are delayed by a specified amount of time. On the
negative side, we show that it is impossible to achieve security
under concurrent general composition with no restrictions
whatsoever on the network (like the aforementioned delays), even
in the timing model.

2005

EPRINT

Universally Composable Password-Based Key Exchange
Abstract

We propose and realize a definition of security for password-based key exchange within the framework of universal composability (UC), thus providing security guarantees under arbitrary composition with other protocols. In addition, our definition captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, our definition does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen by different parties. We also formulate a definition of password-based secure channels, and show how to realize such channels given any password-based key exchange protocol.
The password-based key exchange protocol shown here is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that it is impossible to satisfy our definition in the "plain" model (e.g., without a common reference string).

2005

EPRINT

Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs
Abstract

The standard class of adversaries considered in cryptography is that of {\em strict} polynomial-time probabilistic machines. However, {\em expected} polynomial-time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) polynomial time. In addition, it has been shown that expected polynomial-time simulation is {\em essential} for achieving constant-round black-box zero-knowledge protocols. This reliance on expected polynomial-time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected polynomial-time adversaries in simulation-based security proofs.

2004

EPRINT

A Proof of Yao's Protocol for Secure Two-Party Computation
Abstract

In the mid 1980's, Yao presented a constant-round protocol for
securely computing any two-party functionality in the presence of
semi-honest adversaries (FOCS 1986). In this paper, we provide a
complete description of Yao's protocol, along with a rigorous
proof of security. Despite the importance of Yao's protocol to the
field of secure computation, to the best of our knowledge, this is
the first time that a proof of security has been published.

2004

EPRINT

Protocol Initialization for the Framework of Universal Composability
Abstract

Universally composable protocols (Canetti, FOCS 2000) are cryptographic protocols that remain secure even when run concurrently with arbitrary other protocols. Thus, universally composable protocols can be run in modern networks, like the Internet, and their security is guaranteed. However, the definition of universal composition actually assumes that each execution of the protocol is assigned a unique session identifier, and furthermore, that this identifier is known to all the participating parties. In addition, all universally composable protocols assume that the set of participating parties and the specification of the protocol to be run are a-priori agreed upon and known to all parties. In a decentralized network like the Internet, this setup information must be securely generated by the parties themselves. In this note we formalize the setup problem and show how to securely realize it with a simple and highly efficient protocol.

2004

EPRINT

Lower Bounds and Impossibility Results for Concurrent Self Composition
Abstract

In the setting of concurrent self composition, a single protocol is executed many times concurrently by a single set of parties. In this paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove that there exist large classes of functionalities that {\em cannot} be securely computed under concurrent self composition, by any protocol. We also prove a {\em communication complexity} lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that any protocol that computes a functionality from this class and remains secure for $m$ concurrent executions, must have bandwidth of at least $m$ bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation). In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for $m$ concurrent executions, where security is proven via {\em black-box simulation}, must have at least $m$ rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our impossibility results, we also show that for many functionalities, security under concurrent {\em self} composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent {\em general} composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance beyond the impossibility results that are derived by it for concurrent self composition.

2004

EPRINT

On the Limitations of Universally Composable Two-Party Computation Without Set-up Assumptions
Abstract

The recently proposed {\em universally composable {\em (UC)} security} framework for analyzing security of cryptographic protocols provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when run concurrently with arbitrary other protocols. It has been shown that if a majority of the parties are honest, then universally composable protocols exist for essentially any cryptographic task in the {\em plain model} (i.e., with no setup assumptions beyond that of authenticated communication). When honest majority is not guaranteed, general feasibility results are known only given trusted set-up, such as in the common reference string model. Only little was known regarding the existence of universally composable protocols in the plain model without honest majority, and in particular regarding the important special case of two-party protocols.
We study the feasibility of universally composable two-party {\em function evaluation} in the plain model. Our results show that in this setting, very few functions can be securely computed in the
framework of universal composability. We demonstrate this by providing broad impossibility results that apply to large classes of deterministic and probabilistic functions. For some of these classes, we also present full characterizations of what can and cannot be securely realized in the framework of universal composability. Specifically, our characterizations are for the classes of deterministic functions in which (a) both parties receive the same output, (b) only one party receives output, and (c) only one party has input.

2004

EPRINT

On the Composition of Authenticated Byzantine Agreement
Abstract

A fundamental problem of distributed computing is that of
simulating a secure broadcast channel, within the setting of a
point-to-point network. This problem is known as Byzantine
Agreement (or Generals) and has been the focus of much research.
Lamport et al. showed that in order to achieve Byzantine Agreement
in the standard model, more than 2/3 of the participating
parties must be honest. They further showed that by augmenting the
network with a public-key infrastructure for digital signatures,
it is possible to obtain protocols that are secure for any number
of corrupted parties. The problem in this augmented model is
called "authenticated Byzantine Agreement".
In this paper we consider the question of concurrent, parallel and
sequential composition of authenticated Byzantine Agreement
protocols. We present surprising impossibility results showing
that:
* If an authenticated Byzantine Agreement protocol remains
secure under parallel or concurrent composition (even for just two
executions), then more than 2/3 of the participating parties
must be honest.
* Deterministic authenticated Byzantine Agreement protocols that
run for $r$ rounds and tolerate 1/3 or more corrupted parties,
can remain secure for at most $2r-1$ sequential executions.
In contrast, we present randomized protocols for authenticated
Byzantine Agreement that remain secure under sequential
composition, for {\em any}\/ polynomial number of executions. We
exhibit two such protocols. In the first protocol, the number of
corrupted parties may be any number less than 1/2 (i.e., an
honest majority is required). In the second protocol, any number
of parties may be corrupted; however, the overall number of
parties must be limited to $O(\log k/\log\log k)$, where $k$ is
the security parameter (and so all parties run in time that is
polynomial in $k$). Finally, we show that when the model is
further augmented so that unique and common session identifiers
are assigned to each concurrent session, then any polynomial
number of authenticated Byzantine agreement protocols can be
concurrently executed, while tolerating any number of corrupted
parties.

2004

EPRINT

Lower Bounds for Non-Black-Box Zero Knowledge
Abstract

We show new lower bounds and impossibility results for general (possibly *non-black-box*) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:
1. There does not exist a two-round zero-knowledge *proof* system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of *auxiliary-input* zero-knowledge proofs and arguments.
2. There does not exist a constant-round zero-knowledge *strong* proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language.
3. There does not exist a constant-round public-coin *proof* system for a nontrivial language that is *resettable zero knowledge*. This result also extends to "bounded-resettable" zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) *argument* system that is bounded-resettable zero knowledge.
The complexity assumptions we use are not commonly used in cryptography. However, in all cases, we show that assumptions similar to ours are necessary for the above results.
Most previously known lower bounds, such as those of Goldreich and Krawczyk (SIAM J. Computing, 1996), were only for *black-box* zero knowledge. However, a result of Barak (FOCS 2001) shows that many (or even most) of these black-box lower bounds do *not* extend to the case of general zero knowledge.

2003

EUROCRYPT

2003

EUROCRYPT

2003

EPRINT

A Framework for Password-Based Authenticated Key Exchange
Abstract

In this paper we present a general framework for password-based
authenticated key exchange protocols, in the common reference
string model. Our protocol is actually an abstraction of the key
exchange protocol of Katz et al.\ and is based on the recently
introduced notion of smooth projective hashing by Cramer and
Shoup. We gain a number of benefits from this abstraction. First,
we obtain a modular protocol that can be described using just
three high-level cryptographic tools. This allows a simple and
intuitive understanding of its security. Second, our proof of
security is significantly simpler and more modular. Third, we are
able to derive analogues to the Katz et al.\ protocol under
additional cryptographic assumptions. Specifically, in addition to
the DDH assumption used by Katz et al., we obtain protocols under
both the Quadratic and $N$-Residuosity assumptions. In order to
achieve this, we construct new smooth projective hash functions.

2003

EPRINT

Protocols for Bounded-Concurrent Secure Two-Party Computation in the Plain Model
Abstract

Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of {\em bounded-concurrent self composition}, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that {\em any} two-party functionality can be securely computed under bounded-concurrent self composition, in the {\sf plain model} (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, {\em for any model of concurrency}. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient
protocols for this task.

2003

EPRINT

General Composition and Universal Composability in Secure Multiparty Computation
Abstract

\emph{Concurrent general composition} relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed concurrently. Canetti (FOCS 2001) introduced the notion of \emph{universal composability}, and showed that security under this definition is sufficient for achieving concurrent general composition. However, it is not known whether or not the opposite direction also holds.
Our main result is a proof that security under concurrent general composition, when interpreted in the natural way under the simulation paradigm, is equivalent to a variant of universal composability, where the only difference relates to the order of quantifiers in the definition. (In newer versions of universal composability, these variants are equivalent.) An important corollary of this theorem is that existing impossibility results for universal composability (for all its variants) are inherent for definitions that imply security under concurrent general composition, as formulated here. In particular, there are large classes of two-party functionalities for which \emph{it is impossible} to obtain protocols (in the plain model) that remain secure under concurrent general composition. We stress that the impossibility results obtained are not ``black-box'', and apply even to non-black-box simulation.
Our main result also demonstrates that the definition of universal composability is somewhat ``minimal'', in that the composition guarantee provided by universal composability implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive.

2002

EPRINT

A Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions
Abstract

In this paper we present a simpler construction of an encryption scheme that achieves adaptive chosen ciphertext security (CCA2), assuming the existence of trapdoor permutations. We build on previous works of Sahai and De Santis et al. and construct a scheme that we believe is the easiest to understand to date. In particular, it is only slightly more involved than the Naor-Yung encryption scheme that is secure against passive chosen-ciphertext attacks (CCA1). We stress that the focus of this paper is on simplicity only.

2002

EPRINT

Secure Computation Without Agreement
Abstract

It has recently been shown that authenticated Byzantine agreement,
in which more than a third of the parties are corrupted, cannot be
securely realized under concurrent or parallel (stateless)
composition. This result puts into question any usage of
authenticated Byzantine agreement in a setting where many
executions take place. In particular, this is true for the whole
body of work of secure multi-party protocols in the case that a
third or more of the parties are corrupted. This is because these
protocols strongly rely on the extensive use of a broadcast
channel, which is in turn realized using authenticated Byzantine
agreement. We remark that it was accepted folklore that the use of
a broadcast channel (or authenticated Byzantine agreement) is
actually essential for achieving meaningful secure multi-party
computation whenever a third or more of the parties are corrupted.
In this paper we show that this folklore is false. We present a
mild relaxation of the definition of secure computation allowing
abort. Our new definition captures all the central security issues
of secure computation, including privacy, correctness and
independence of inputs. However, the novelty of the definition is
in {\em decoupling} the issue of agreement from these issues. We
then show that this relaxation suffices for achieving secure
computation in a point-to-point network. That is, we show that
secure multi-party computation for this definition can be achieved
for {\em any} number of corrupted parties and {\em without} a
broadcast channel (or trusted preprocessing phase as required for
running authenticated Byzantine agreement). Furthermore, this is
achieved by just replacing the broadcast channel in known
protocols with a very simple and efficient echo-broadcast
protocol. An important corollary of our result is the ability to
obtain multi-party protocols that remain secure under composition,
without assuming a broadcast channel.

2002

EPRINT

Strict Polynomial-time in Simulation and Extraction
Abstract

The notion of efficient computation is
usually identified in cryptography and complexity with (strict)
probabilistic polynomial time. However, until recently, in order
to obtain *constant-round* zero-knowledge proofs and proofs
of knowledge, one had to allow simulators and knowledge-extractors
to run in time that is only polynomial *on the average*
(i.e., *expected* polynomial time). Recently Barak gave the
first constant-round zero-knowledge argument with a
*strict* (in contrast to expected) polynomial-time
simulator. The simulator in his protocol is a
*non-black-box* simulator (i.e., it makes inherent use of
the description of the *code* of the verifier).
In this paper, we further address the question of strict
polynomial-time in constant-round zero-knowledge proofs and
arguments of knowledge. First, we show that there exists a
constant-round zero-knowledge *argument of knowledge* with
a *strict* polynomial-time *knowledge extractor*. As in
the simulator of Barak's zero-knowledge protocol, the extractor
for our argument of knowledge is not black-box and makes inherent
use of the code of the prover. On the negative side, we show that
non-black-box techniques are *essential* for both strict
polynomial-time simulation and extraction. That is, we show that
no (non-trivial) constant-round zero-knowledge proof or argument
can have a strict polynomial-time *black-box* simulator.
Similarly, we show that no (non-trivial) constant-round
zero-knowledge proof or argument of knowledge can have a strict
polynomial-time *black-box* knowledge extractor.

2002

EPRINT

Universally Composable Two-Party and Multi-Party Secure Computation
Abstract

We show how to securely realize any two-party and multi-party functionality in a {\em universally composable} way, regardless of the number of corrupted participants. That is, we consider an asynchronous multi-party network with open communication and an
adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and rely on standard intractability assumptions.

2001

EPRINT

Resettably-Sound Zero-Knowledge and its Applications
Abstract

Resettably-sound proofs and arguments remain sound even when the
prover can reset the verifier, and so force it to use the same
random coins in repeated executions of the protocol. We show that
resettably-sound zero-knowledge {\em arguments} for NP exist
if collision-resistant hash functions exist. In contrast,
resettably-sound zero-knowledge {\em proofs} are possible only
for languages in P/poly.
We present two applications of resettably-sound zero-knowledge
arguments. First, we construct resettable zero-knowledge arguments
of knowledge for NP, using a natural relaxation of the
definition of arguments (and proofs) of knowledge. We note that,
under the standard definition of proofs of knowledge, it is
impossible to obtain resettable zero-knowledge arguments of
knowledge for languages outside BPP. Second, we construct a
constant-round resettable zero-knowledge argument for NP in the
public-key model, under the assumption that collision-resistant
hash functions exist. This improves upon the sub-exponential
hardness assumption required by previous constructions.
We emphasize that our results use non-black-box zero-knowledge
simulations. Indeed, we show that some of the results are {\em
impossible} to achieve using black-box simulations. In
particular, only languages in BPP have resettably-sound
arguments that are zero-knowledge with respect to black-box
simulation.

2001

EPRINT

Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation
Abstract

In this paper we show that any {\em two-party} functionality can be securely computed in a {\em constant number of rounds}, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao's constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds.
In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round {\em perfect} coin-tossing protocol, where by ``perfect'' we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom).

2000

EPRINT

Session-Key Generation using Human Passwords Only
Abstract

We present session-key generation protocols in a model where the
legitimate parties share {\em only} a human-memorizable
password, and there is no additional setup assumption in the
network. Our protocol is proven secure under the assumption that
trapdoor permutations exist. The security guarantee holds with
respect to probabilistic polynomial-time adversaries that control
the communication channel (between the parties), and may omit,
insert and modify messages at their choice. Loosely speaking, the
effect of such an adversary that attacks an execution of our
protocol is comparable to an attack in which an adversary is only
allowed to make a constant number of queries of the form ``is $w$
the password of Party $A$''. We stress that the result holds also
in case the passwords are selected at random from a small
dictionary so that it is feasible (for the adversary) to scan the
entire directory. We note that prior to our result, it was not
known whether or not such protocols were attainable without the
use of random oracles or additional setup assumptions.

#### Program Committees

- Eurocrypt 2018
- Eurocrypt 2015
- TCC 2014
- Crypto 2013
- Eurocrypt 2012
- PKC 2011
- Crypto 2010
- Crypto 2008
- TCC 2008
- Crypto 2006
- TCC 2006
- Crypto 2005
- Eurocrypt 2004

#### Coauthors

- Joël Alwen (1)
- Gilad Asharov (9)
- Yonatan Aumann (3)
- Boaz Barak (7)
- Amos Beimel (1)
- Aner Ben-Efraim (1)
- Ran Canetti (11)
- Koji Chida (1)
- Asaf Cohen (1)
- Ran Cohen (2)
- Asaf Cohen (1)
- Dana Dachman-Soled (1)
- Tore Kasper Frederiksen (1)
- Jun Furukawa (1)
- Daniel Genkin (1)
- Rosario Gennaro (2)
- Oded Goldreich (4)
- Shafi Goldwasser (3)
- S. Dov Gordon (1)
- Shay Gueron (3)
- Iftach Haitner (1)
- Shai Halevi (3)
- Koki Hamada (1)
- Carmit Hazay (7)
- Dai Ikarashi (1)
- Yuval Ishai (3)
- Yael Tauman Kalai (1)
- Jonathan Katz (10)
- Dafna Kidron (1)
- Ryo Kikuchi (1)
- Chiu-Yuen Koo (1)
- Eyal Kushilevitz (6)
- Anna Lysyanskaya (1)
- Philip D. MacKenzie (2)
- Mohammad Mahmoody (1)
- Tal Malkin (1)
- Kobbi Nissim (1)
- Ariel Nof (4)
- Eran Omri (5)
- Claudio Orlandi (1)
- Ilan Orlov (1)
- Valery Osheter (1)
- Rafail Ostrovsky (1)
- Eli Oxman (1)
- Rafael Pass (3)
- Arpita Patra (1)
- Giuseppe Persiano (1)
- Erez Petrank (3)
- Benny Pinkas (19)
- Manoj Prabhakaran (1)
- Tal Rabin (8)
- Ben Riva (2)
- Amit Sahai (1)
- Thomas Schneider (3)
- Abhi Shelat (1)
- Nigel P. Smart (4)
- Eduardo Soria-Vazquez (1)
- Salil P. Vadhan (1)
- Ivan Visconti (1)
- Or Weinstein (1)
- Avishay Yanai (4)
- Hila Zarosim (8)
- Michael Zohner (3)