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

In this paper we show that any two-party functionality can be securely computed in a constant number of rounds , where security is obtained against (polynomial-time) 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 almost perfect coin-tossing protocol, where by ``almost perfect' we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom).     

Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries

In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao’s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao’s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called cut-and-choose, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating. In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most \(2^{-40}\), the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of \(2^{-s}\) where \(s\) is the number of garbled circuits, in contrast to the previous best of \(2^{-0.32s}\). We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, all of the evaluated circuits must be incorrect, and not just the majority as in previous works. The security of our protocol relies on the decisional Diffie–Hellman assumption.     

Resilient Network Coding in the Presence of Byzantine Adversaries

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introduces distributed polynomial-time rate-optimal network codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam links, our first algorithm achieves a rate of , where is the network capacity. In contrast, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of . Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial time. Furthermore, only the source and destination need to be modified; nonmalicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.     

More Efficient Oblivious Transfer Extensions

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT protocols is becoming more evident. OT extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (Advances in cryptology—CRYPTO’03, vol 2729 of LNCS, Springer, 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (Advances in cryptology—CRYPTO’12, vol 7417 of LNCS, Springer, 2012) presented an efficient OT extension protocol for the setting of malicious adversaries that is secure in a random oracle model. In this work, we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich–Micali–Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.     

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

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.     

Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer

In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this paper, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems:

Efficient Set Intersection with Simulation-Based Security

We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. In this work, we present protocols based on the use of homomorphic encryption and different hashing schemes for both the semi-honest and malicious environments. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. Our protocols obtain linear communication and computation overhead. We further implement different variants of our semi-honest protocol. Our experiments show that the asymptotic overhead of the protocol is affected by different constants. (In particular, the degree of the polynomials evaluated by the protocol matters less than the number of polynomials that are evaluated.) As a result, the protocol variant with the best asymptotic overhead is not necessarily preferable for inputs of reasonable size.     

Efficient Set Operations in the Presence of Malicious Adversaries

We revisit the problem of constructing efficient secure two-party protocols for the problems of set intersection and set union, focusing on the model of malicious parties. Our main results are constant-round protocols that exhibit linear communication and a (practically) linear number of exponentiations with simulation-based security. At the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC secure, and we discuss how to perform these transformations.     

Session-Key Generation Using Human Passwords Only

We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password, and there is no additional set-up assumption in the network. Our protocol is proven secure under the assumption that enhanced 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 with 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 set-up assumptions.     

Parallel and Concurrent Security of the HB and HB+ Protocols

Hopper and Blum (Asiacrypt 2001) and Juels and Weis (Crypto 2005) recently proposed two shared-key authentication protocols—HB and HB⁺, respectively—whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. The security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem, which is equivalent to the problem of decoding random binary linear codes. The HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB⁺ protocol is proven secure against active attacks.     

SecMR – a secure multipath routing protocol for ad hoc networks

Multipath routing in ad hoc networks increases the resiliency against security attacks of collaborating malicious nodes, by maximizing the number of nodes that an adversary must compromise in order to take control of the communication. In this paper, we identify several attacks that render multipath routing protocols vulnerable to collaborating malicious nodes. We propose an on-demand multipath routing protocol, the secure multipath routing protocol (SecMR), and we analyze its security properties. Finally, through simulations, we evaluate the performance of the SecMR protocol in comparison with existing secure multipath routing protocols.     

Non-interactive Timestamping in the Bounded-Storage Model

A timestamping scheme is non-interactive if a stamper can stamp a document without communicating with any other player. The only communication done is at validation time. Non-Interactive timestamping has many advantages, such as information theoretic privacy and enhanced robustness. Non-Interactive timestamping, however, is not possible against polynomial-time adversaries that have unbounded storage at their disposal. As a result, no non-interactive timestamping schemes were constructed up to date. In this paper we show that non-interactive timestamping is possible in the bounded-storage model, i.e., if the adversary has bounded storage, and a long random string is broadcast to all players. To the best of our knowledge, this is the first example of a cryptographic task that is possible in the bounded-storage model but is impossible in the “standard cryptographic setting,” even when assuming “standard” cryptographic assumptions. We give an explicit construction that is secure against all bounded storage adversaries and a significantly more efficient construction secure against all bounded storage adversaries that run in polynomial time. A preliminary version of this paper appeared in CRYPTO 2004 [24]. Tal Moran: Some of this work was done while at Tel-Aviv University. Ronen Shaltiel: Some of this work was done while at the Weizmann Institute of Science and supported by the Koshland Scholarship. This research was also supported by Grant No 2004329 from the United States-Israel Binational Science Foundation (BSF) and by ISF grant 686/07. Amnon Ta-Shma: Supported by the Binational Science Foundation, by the Israel Science Foundation, and by the EU Integrated Project QAP.     

Long-Term Security and Universal Composability

Algorithmic progress and future technological advances threaten today’s cryptographic protocols. This may allow adversaries to break a protocol retrospectively by breaking the underlying complexity assumptions long after the execution of the protocol. Long-term secure protocols, protocols that after the end of the execution do not reveal any information to a then possibly unlimited adversary, could meet this threat. On the other hand, in many applications, it is necessary that a protocol is secure not only when executed alone, but within arbitrary contexts. The established notion of universal composability (UC) captures this requirement.     

Adaptive versus Non-Adaptive Security of Multi-Party Protocols

Security analysis of multi-party cryptographic protocols distinguishes between two types of adversarial settings: In the non-adaptive setting the set of corrupted parties is chosen in advance, before the interaction begins. In the adaptive setting the adversary chooses who to corrupt during the course of the computation. We study the relations between adaptive security (i.e., security in the adaptive setting) and nonadaptive security, according to two definitions and in several models of computation.     

Threshold cryptography in mobile ad hoc networks under minimal topology and setup assumptions

Mobile Ad Hoc Networks (MANET), due to their lack of physical infrastructures or centralized online authorities, pose a number of security challenges to a protocol designer. In particular, several typical application scenarios demand the design of protocols that cannot base their security on the existence of trusted parties or setup information, but rather need to leverage uniquely on assumptions limiting the corrupting power of the adversaries. This naturally defines security design and analysis paradigms similar to those of the threshold cryptography area, where it is typically assumed that an adversary can corrupt up to a limited amount of entities or resources. Therefore a secure realization of primitives from threshold cryptography in MANET promises to be applicable to several MANET protocols. However, directly applying known threshold cryptography solutions for wired network into MANETs faces serious challenges. In particular, we noted a major design difficulty due to the lack of full network connectivity that significantly constrained the network topology assumptions under which a MANET threshold signature scheme can be proved secure. In this paper we formalize, investigate and present a new MANET threshold signature scheme that is secure under significantly improved topology and setup assumptions. Surprisingly, we break through an apparent barrier due to well-known results from the distributed computing area.     

Secure Computation of the Median (and Other Elements of Specified Ranks)

We consider the problem of securely computing the kth-ranked element of the union of two or more large, confidential data sets. This is a fundamental question motivated by many practical contexts. For example, two competitive companies may wish to compute the median salary of their combined employee populations without revealing to each other the exact salaries of their employees. While protocols do exist for computing the kth-ranked element, they require time that is at least linear in the sum of the sizes of their combined inputs. This paper investigates two-party and multi-party protocols for both the semi-honest and malicious cases. In the two-party setting, we prove that the problem can be solved in a number of rounds that is logarithmic in k, where each round requires communication and computation cost that is linear in b, the number of bits needed to describe each element of the input data. In the multi-party setting, we prove that the number of rounds is linear in b, where each round has overhead proportional to b multiplied by the number of parties. The multi-party protocol can be used in the two-party case. The overhead introduced by our protocols closely match the communication complexity lower bound. Our protocols can handle a malicious adversary via simple consistency checks.     

Player Simulation and General Adversary Structures in Perfect Multiparty Computation

The goal of secure multiparty computation is to transform a given protocol involving a trusted party into a protocol without need for the trusted party, by simulating the party among the players. Indeed, by the same means, one can simulate an arbitrary player in any given protocol. We formally define what it means to simulate a player by a multiparty protocol among a set of (new) players, and we derive the resilience of the new protocol as a function of the resiliences of the original protocol and the protocol used for the simulation. In contrast to all previous protocols that specify the tolerable adversaries by the number of corruptible players (a threshold), we consider general adversaries characterized by an adversary structure, a set of subsets of the player set, where the adversary may corrupt the players of one set in the structure. Recursively applying the simulation technique to standard threshold multiparty protocols results in protocols secure against general adversaries. The classical results in unconditional multiparty computation among a set of n players state that, in the passive model, any adversary that corrupts less than n/2 players can be tolerated, and in the active model, any adversary that corrupts less than n/3 players can be tolerated. Strictly generalizing these results we prove that, in the passive model, every function (more generally, every cooperation specified by involving a trusted party) can be computed securely with respect to a given adversary structure if and only if no two sets in the adversary structure cover the full set of players, and, in the active model, if and only if no three sets cover the full set of players. The complexities of the protocols are polynomial in the number of maximal adverse player sets in the adversary structure. Received 31 December 1997 and revised 26 February 1999     

Scalable Protocols for Authenticated Group Key Exchange

We consider the problem of authenticated group key exchange among n parties communicating over an insecure public network. A number of solutions to this problem have been proposed; however, all prior provably secure solutions do not scale well and, in particular, require O(n) rounds. Our main contribution is the first scalable protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only O(1) "full" modular exponentiations per user. Toward this goal (and adapting work of Bellare, Canetti, and Krawczyk), we first present an efficient compiler that transforms any group key-exchange protocol secure against a passive eavesdropper to an authenticated protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and O(1) communication (per user) to the original scheme. We then prove secure—against a passive adversary—a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably secure three-round protocol for authenticated group key exchange which also achieves forward secrecy.