Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.

Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like privacy and correctness. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited. In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers Z2n, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of Z2n (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods. We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.

Protocols for secure multiparty computation enable a set of parties to compute a joint function of their inputs, while preserving privacy, correctness and more. In theory, secure computation has broad applicability and can be used to solve many of the modern concerns around utilization of data and privacy. Huge steps have been made towards this vision in the past few years, and we now have protocols that can carry out large computations extremely efficiently, especially in the setting of an honest majority. However, in practice, there are still major barriers to widely deploying secure computation, especially in a decentralized manner. In this paper, we present the first end-to-end automated system for deploying large-scale MPC protocols between end users, called MPSaaS (for MPC system-as-a-service ). Our system enables parties to pre-enroll in an upcoming MPC computation, and then participate by either running software on a VM instance (e.g., in Amazon), or by running the protocol on a mobile app, in Javascript in their browser, or even on an IoT device. Our system includes an automation system for deploying MPC protocols, an administration component for setting up an MPC computation and inviting participants, and an end-user component for running the MPC protocol in realistic end-user environments. We demonstrate our system for a specific application of running secure polls and surveys, where the secure computation is run end-to-end with each party actually running the protocol (i.e., without relying on a set of servers to run the protocol for them). This is the first such system constructed, and is a big step forward to the goal of commoditizing MPC. One of the cryptographic difficulties that arise in this type of setting is due to the fact that end users may have low bandwidth connections, making it a challenge to run an MPC protocol with high bandwidth. We therefore present a protocol based on Beerliova-Trubiniova and Hirt (TCC 2008) with many optimizations, that has very low concrete communication, and the lowest published for small fields. Our protocol is secure as long as less than a third of the parties are malicious, and is well suited for computing both arithmetic and Boolean circuits. We call our protocol HyperMPC and show that it has impressive performance. In particular, 150 parties can compute statistics---mean, standard deviation and regression---on 4,000,000 inputs (with a circuit of size 16,000,000 gates of which 6,000,000 are multiplication) in just 45 seconds, and 150 parties can compute a circuit over GF[28] (which can be used for a Boolean computation) with 1,000,000 multiplication gates and depth-20 in just 2 seconds. Although our end-to-end system can be used to run any MPC protocol (and we have incorporated numerous protocols already), we demonstrate it for our new protocol that is optimized for end-users without~high~bandwidth.

ECDSA is a standardized signing algorithm that is widely used in TLS, code signing, cryptocurrency and more. Due to its importance, the problem of securely computing ECDSA in a distributed manner (known as threshold signing) has received considerable interest. However, despite this interest, there is still no full threshold solution for more than 2 parties (meaning that any t -out-of- n parties can sign, security is preserved for any t-1 or fewer corrupted parties, and tłeq n can be any value thus supporting an honest minority) that has practical key distribution. This is due to the fact that all previous solutions for this utilize Paillier homomorphic encryption, and efficient distributed Paillier key generation for more than two parties is not known. In this paper, we present the first truly practical full threshold ECDSA signing protocol that has both fast signing and fast key distribution. This solves a years-old open problem, and opens the door to practical uses of threshold ECDSA signing that are in demand today. One of these applications is the construction of secure cryptocurrency wallets (where key shares are spread over multiple devices and so are hard to steal) and cryptocurrency custody solutions (where large sums of invested cryptocurrency are strongly protected by splitting the key between a bank/financial institution, the customer who owns the currency, and possibly a third-party trustee, in multiple shares at each). There is growing practical interest in such solutions, but prior to our work these could not be deployed today due to the need for distributed key generation.

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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We discuss the widely increasing range of applications of a cryptographic technique called multi-party computation. For many decades, this was perceived to be of purely theoretical interest, but now it has started to find application in a number of use cases. We highlight in this paper a number of these, ranging from securing small high-value items such as cryptographic keys, through to securing an entire database.

Abstract The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his/her patient may try to find other individuals with “close” genomic data, and use the data of these individuals to help diagnose and find effective treatment for that patient’s conditions. This is clearly a desirable mode of operation. However, the privacy exposure implications are considerable, and so we would like to carry out the above “closeness” computation in a privacy preserving manner. In this work we put forward a new approach for highly efficient secure computation for computing an approximation of the Similar Patient Query problem. We present contributions on two fronts. First, an approximation method that is designed with the goal of achieving efficient private computation. Second, further optimizations of the two-party protocol. Our tests indicate that the approximation method works well, it returns the exact closest records in 98% of the queries and very good approximation otherwise. As for speed, our protocol implementation takes just a few seconds to run on databases with thousands of records, each of length thousands of alleles, and it scales almost linearly with both the database size and the length of the sequences in it. As an example, in the datasets of the recent iDASH competition, after a one-time preprocessing of around 12 seconds, it takes around a second to find the nearest five records to a query, in a size-500 dataset of length- 3500 sequences. This is 2-3 orders of magnitude faster than using state-of-the-art secure protocols with existing edit distance algorithms.

Block cipher modes of operation provide a way to securely encrypt using a block cipher. The main factors in analyzing modes of operation are the \emph{level of security} achieved (chosen-plaintext security, authenticated encryption, nonce-misuse resistance, and so on) and \textit{performance}. When measuring the security level of a mode of operation, it does not suffice to consider asymptotics, and a concrete analysis is necessary. This is especially the case today, when encryption rates can be very high, and so birthday bounds may be approached or even reached. In this paper, we show that key-derivation at every encryption significantly improves the security bounds in many cases. We present a new key-derivation method that utilizes a \emph{truncated block cipher}, and show that this is far better than standard block-cipher based key derivation. We prove that by using our key derivation method, we obtain greatly improved bounds for many modes of operation, with a result that the lifetime of a key can be significantly extended. We demonstrate this for AES-CTR (CPA-security), AES-GCM (authenticated encryption) and AES-GCM-SIV (nonce-misuse resistance). Finally, we demonstrate that when using modern hardware with AES instructions (AES-NI), the performance penalty of deriving keys at each encryption is insignificant for most uses.

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.

Secure multiparty computation enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. In the past few years, the efficiency of secure computation protocols has increased in leaps and bounds. However, when considering the case of security in the presence of malicious adversaries (who may arbitrarily deviate from the protocol specification), we are still very far from achieving high efficiency. In this paper, we consider the specific case of three parties and an honest majority. We provide general techniques for improving efficiency of cut-and-choose protocols on multiplication triples and utilize them to significantly improve the recently published protocol of Furukawa et al. (ePrint 2016/944). We reduce the bandwidth of their protocol down from 10 bits per AND gate to 7 bits per AND gate, and show how to improve some computationally expensive parts of their protocol. Most notably, we design cache-efficient shuffling techniques for implementing cut-and-choose without randomly permuting large arrays (which is very slow due to continual cache misses). We provide a combinatorial analysis of our techniques, bounding the cheating probability of the adversary. Our implementation achieves a rate of approximately 1.15 billion AND gates per second on a cluster of three 20-core machines with a 10Gbps network. Thus, we can securely compute 212,000 AES encryptions per second (which is hundreds of times faster than previous work for this setting). Our results demonstrate that high-throughput secure computation for malicious adversaries is possible.

Secure multi-party computation (SMPC) is a cryptographic tool that enables a set of parties to jointly compute any function of their inputs while keeping the privacy of inputs. The paper "High Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority" in this ACM CCS 2016 [4] presents a new protocol which its implementation carried out over 1,300,000 AESs per second and was able to support 35,000 login queries of Kerberos authentication per second. This poster/demo presents the design of the implementation and demonstrates the Kerberos authentication over here. The design will show how this high-throughput three-party computation can be done using simple servers. The demonstration proves that secure multiparty computation of Kerberos authentications in large organizations is now practical.

In this paper, we describe a new information-theoretic protocol (and a computationally-secure variant) for secure three-party computation with an honest majority. The protocol has very minimal computation and communication; for Boolean circuits, each party sends only a single bit for every AND gate (and nothing is sent for XOR gates). Our protocol is (simulation-based) secure in the presence of semi-honest adversaries, and achieves privacy in the client/server model in the presence of malicious adversaries. On a cluster of three 20-core servers with a 10Gbps connection, the implementation of our protocol carries out over 1.3 million AES computations per second, which involves processing over 7 billion gates per second. In addition, we developed a Kerberos extension that replaces the ticket-granting-ticket encryption on the Key Distribution Center (KDC) in MIT-Kerberos with our protocol, using keys/ passwords that are shared between the servers. This enables the use of Kerberos while protecting passwords. Our implementation is able to support a login storm of over 35,000 logins per second, which suffices even for very large organizations. Our work demonstrates that high-throughput secure computation is possible on standard hardware.

In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low. In this paper, we construct highly efficient constant-round protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.

Attribute-based methods provide authorization to parties based on whether their set of attributes (e.g., age, organization, etc.) fulfills a policy. In attribute-based encryption (ABE), authorized parties can decrypt, and in attribute-based credentials (ABCs), authorized parties can authenticate themselves. In this paper, we combine elements of ABE and ABCs together with garbled circuits to construct attribute-based key exchange (ABKE). Our focus is on an interactive solution involving a client that holds a certificate (issued by an authority) vouching for that client's attributes and a server that holds a policy computable on such a set of attributes. The goal is for the server to establish a shared key with the client but only if the client's certified attributes satisfy the policy. Our solution enjoys strong privacy guarantees for both the client and the server, including attribute privacy and unlinkability of client sessions.

Authenticated encryption schemes guarantee both privacy and integrity, and have become the default level of encryption in modern protocols. One of the most popular authenticated encryption schemes today is AES-GCM due to its impressive speed. The current CAESAR competition is considering new modes for authenticated encryption that will improve on existing methods. One property of importance that is being considered more today -- due to multiple real-life cases of faulty sources of randomness -- is that repeating nonces and IVs can have disastrous effects on security. A (full) nonce misuse-resistant authenticated encryption scheme has the property that if the same nonce is used to encrypt the same message twice, then the same ciphertext is obtained and so the fact that the same message was encrypted is detected. Otherwise, full security is obtained -- even if the same nonce is used for different messages. In this paper, we present a new fully nonce misuse-resistant authenticated encryption scheme that is based on carefully combining the GCM building blocks into the SIV paradigm of Rogaway and Shrimpton. We provide a full proof of security of our scheme, and an optimized implementation using the AES-NI and PCLMULQDQ instruction sets. We compare our performance to the highly optimized OpenSSL 1.0.2 implementation of GCM and show that our nonce misuse-resistant scheme is only 14% slower on Haswell architecture and 19% slower on Broadwell architecture. On Broadwell, GCM-SIV encryption takes only 0.92 cycles per byte, and GCM-SIV decryption is exactly the same as GCM decryption taking only 0.77 cycles per byte. In addition, we compare to other optimized authenticated-encryption implementations carried out by Bogdanov et al., and conclude that our mode is very competitive. Beyond being very fast, our new mode of operation uses the same building blocks as GCM and so existing hardware and software can be utilized to easily deploy GCM-SIV. We conclude that GCM-SIV is a viable alternative to GCM, providing full nonce misuse-resistance at little cost.

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled circuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al. 13, Lindell and Riva 14, Huang et al. 14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat~13). We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over previous methods.

Adaptive security is a strong corruption model that captures "hacking" attacks where an external attacker breaks into parties' machines in the midst of a protocol execution. There are two types of adaptively-secure protocols: adaptive with erasures and adaptive without erasures. Achieving adaptivity without erasures is preferable, since secure erasures are not always trivial. However, it seems far harder. We introduce a new model of adaptive security called adaptive security with partial erasures that allows erasures, but only assumes them in a minimal sense. Specifically, if all parties are corrupted then security holds as long as any single party successfully erases. In addition, security holds if any proper subset of the parties is corrupted without erasures. We initiate a theoretical study of this new notion and demonstrate that secure computation in this setting is as efficient as static secure computation. In addition, we study the relations between semi-adaptive security [GWZ09], adaptive security with partial erasures, and adaptive security without any erasures. We prove that the existence of semi-adaptive OT implies secure computation in all these settings.

Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography.

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 fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [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. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial 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, though we 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.

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way.

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a 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) and show some positive results regarding what can be achieved.

We investigate the question of whether the security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

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 simulation-based security in the presence of 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.

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 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 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 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.

It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, 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 present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies security under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

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. [1982] showed that in order to achieve Byzantine Agreement in the plain model, more than two thirds 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 article, we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols with a single common setup. We present surprising impossibility results showing that:(1) Authenticated Byzantine Agreement protocols that remain secure under parallel or concurrent composition (even for just two executions) and tolerate a third or more corrupted parties, do not exist.(2) Deterministic authenticated Byzantine Agreement protocols that run for r rounds and tolerate a third or more corrupted parties, can remain secure for at most 2 r − 1 sequential executions.In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for any polynomial number of executions. We exhibit two such protocols. In the first protocol, an honest majority is required. In the second protocol, any number of parties may be corrupted; however, the complexity of the protocol is in the order of 2 n · n ! for n parties. In order to have this polynomial in the security parameter k (used for the signature scheme in the protocol), this requires the overall number of parties to be limited to O (log k /log log k ). The above results are achieved due to a new protocol for authenticated Byzantine Generals for three parties that can tolerate any number of faulty parties and composes sequentially.Finally, we show that when the model is further augmented so that in each session, all the participating parties receive a common session identifier that is unique to that session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.

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 analogs 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.

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to jointly compute some function of their input (i.e., they wish to securely carry out some distributed task). %The joint computation should be such that even In the stand-alone case, it has been shown that every efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case where there is no honest majority (or trusted setup).In this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. Specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not "drift" too much (i.e., it is assumed that they proceed at approximately the same rate). We show that under this mild timing assumption, it is possible to securely compute any functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).

The notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic polynomial-time. However, until recently, in order to obtain \emph{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 nonblack-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 nonblack-box techniques are essential for both strict polynomial-time simulation and extraction. That is, we show that no (nontrivial) constant-round zero-knowledge proof or argument can have a strict polynomial-time black-box simulator. Similarly, we show that no (nontrivial) constant-round zero-knowledge proof or argument of knowledge can have a strict polynomial-time black-box knowledge extractor.

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 constant-round zero-knowledge strong proof (or argument) of knowledge (as defined by Goldreich, 2001) for a nontrivial language; 2. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete 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 contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) argument system that is bounded-resettable zero knowledge.

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. Our main result is a proof that security under concurrent general composition is equivalent to a relaxed variant of universal composability (where the only difference relates to the order of quantifiers in the definition). An important corollary of this theorem is that existing impossibility results for universal composability (or actually its relaxed variant) are inherent in any definition achieving security 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 (almost) implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive.

No abstract available.

In this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (A general protocol can be used for obtaining secure computation of any functionality.) We consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". We present both negative and positive results for this model. Specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. An important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). On the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). Our protocol has O(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. We note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.

The question of the composition of protocols is an important and heavily researched one. In this paper we consider the problem of sequential composition of synchronous protocols that do not have simultaneous termination; i.e., the parties do not necessarily conclude a protocol execution in the same round. A problem arises becauses such protocols must begin in synchrony; therefore a second execution cannot follow from the first in a straightforward manner. An important example of a protocol with this property is that of randomized Byzantine Agreement with an expected constant number of rounds (such as the one due to Feldman and Micali). We note that expected constant-round Byzantine Agreement cannot have simultaneous termination and thus this (problematic) property is inherent.Given that the termination of the parties is not simultaneous, a natural question to consider is how to synchronize the parties so that such protocols can be sequentially composed. Furthermore, such a composition should preserve the original running-time of the protocol, i.e. running the protocol ℓ times sequentially should take in the order of ℓ times the running-time of the protocol. In this paper, we present a method for sequentially composing any protocol in which the players do not terminate in the same round, while preserving the original round complexity. An important application of this result is the sequential composition of parallel Byzantine Agreement. Such a composition can be used by parties connected in a point-to-point network to run protocols designed for the broadcast model, while maintaining the original round complexity.

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP), one had to allow simulators and knowledge-extractors to run in time which is only polynomial on the average (i.e., expected polynomial time). Whether or not allowing expected polynomial-time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected polynomial time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected polynomial time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected polynomial-time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) polynomial-time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected polynomial-time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict polynomial-time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict polynomial-time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict polynomial-time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected polynomial-time.

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a 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 make general intractability assumptions.

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 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, it is possible to obtain secure protocols for any number of faulty parties. This augmented problem 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:

Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge arguments for NP exist if collision-free hash functions exist. In contrast, resettably-sound zero-knowledge 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 proof 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-free 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 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.

data-mining tool and as such have been well researched.