Collusion-free (CF) and collusion-preserving (CP) protocols enrich the standard security offered by multi-party computation (MPC), to tackle settings where subliminal communication is undesirable. However, all existing solutions make arguably unrealistic assumptions on setups, such as physical presence of the parties, access to physical envelopes, or extreme isolation, where the only means of communication is a star-topology network. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic scenarios. Motivated also by the increasing interest in using hardware tokens for cryptographic applications, in this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the state of the art, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving (in short, CP) secure as long as no parties abort. In the case of an aborting adversary, our protocol still achieves standard (G)UC security with identifiable (and unanimous) abort. Leveraging the above identifiability property, we augment our protocol with a penalization scheme which ensures that it is not profitable to abort, thereby obtaining CP security against incentive-driven attackers. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing CP/CF solutions, our protocol preserves, as a fallback, security against monolithic adversaries, even when the setup (i.e., the hardware tokens) is compromised or corrupted. In addition, our fallback solution achieves identifiable and unanimous abort, which we prove are impossible in previous CP solutions.
Collusion-free (CF) and collusion-preserving (CP) protocols enrich the standard security offered by multi-party computation (MPC), to tackle settings where subliminal communication is undesirable. However, all existing solutions make arguably unrealistic assumptions on setups, such as physical presence of the parties, access to physical envelopes, or extreme isolation, where the only means of communication is a star-topology network. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic scenarios. Motivated also by the increasing interest in using hardware tokens for cryptographic applications, in this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the state of the art, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving (in short, CP) secure as long as no parties abort. In the case of an aborting adversary, our protocol still achieves standard (G)UC security with identifiable (and unanimous) abort. Leveraging the above identifiability property, we augment our protocol with a penalization scheme which ensures that it is not profitable to abort, thereby obtaining CP security against incentive-driven attackers. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing CP/CF solutions, our protocol preserves, as a fallback, security against monolithic adversaries, even when the setup (i.e., the hardware tokens) is compromised or corrupted. In addition, our fallback solution achieves identifiable and unanimous abort, which we prove are impossible in previous CP solutions.
Secure Multi-party Computation (MPC) with small population and honest majority has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. In this work, we investigate a wide range of security notions in the five-party setting, tolerating two active corruptions. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet. In a minimal setting of pairwise-private channels, we present efficient instantiations with unanimous abort (where either all honest parties obtain the output or none of them do) and fairness (where the adversary obtains its output only if all honest parties also receive it). With the presence of an additional broadcast channel (known to be necessary), we present a construction with guaranteed output delivery (where any adversarial behaviour cannot prevent the honest parties from receiving the output). The broadcast communication is minimal and independent of circuit size. In terms of performance (communication and run time), our protocols incur minimal overhead over the best known protocol of Chandran et al. (ACM CCS 2016) that achieves the least security of selective abort. Further, our protocols for fairness and unanimous abort can be extended to n-parties with at most √n corruptions, similar to Chandran et al. Going beyond the most popular honest-majority setting of three parties with one corruption, our results demonstrate feasibility of attaining stronger security notions for more than one active corruption at an expense not too far from the least desired security of selective abort.
Most proposed protocols for multi-party computation are designed to be secure either against information-theoretic or against computational adversaries.Each setting has its known advantages and disadvantages.In the computational setting we can achieve nonrobust MPC for up to t < n corrupted parties, but relying on unproven intractability assumptions.In the information-theoretic setting we do not have any unproven assumptions, but only t < n/2 corrupted parties can be tolerated.In [Cha89] Chaum sketches a hybrid protocol that brings together the best of both worlds: Information-theoretic security with abort (i.e.privacy and correctness, but no fairness or robustness) is achieved for t < n/2 corrupted parties.Beyond this threshold, for t < n corrupted parties, the protocol achieves computational security with abort.In this work, we first formalize the protocol idea described in [Cha89] and prove its security.In a second step, we extend the protocol to provide fairness and robustness.Whereas fairness comes "for free", robustness requires a trade-off similar to the one in [IKLP06].Then, we describe a construction for realizing the protocol in the universallycomposable setting as proposed in [Can01].For his protocol, Chaum assumed that a broadcast channel is given.In the last part of this work we discuss the implications of dropping this assumption, and obtain an interesting new result: It is possible to achieve the same bounds as in [Cha89], extended with fairness, without a broadcast channel.
Abstract. It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). The recent work of Katz shows that we may instead rely on physical assumptions, and in particular tamper-proof hardware tokens. In this paper, we consider a similar but strictly weaker physical assumption. We assume that a player (Alice) can partially isolate another player (Bob) for a brief portion of the computation and prevent Bob from communicating more than some limited number of bits with the environment. For example, isolation might be achieved by asking Bob to put his functionality on a tamper-proof hardware token and assuming that Alice can prevent this token from communicating to the outside world. Alternatively, Alice may interact with Bob directly but in a special office which she administers and where there are no high-bandwidth communication channels to the outside world. We show that, under standard cryptographic assumptions, such physical setup can be used to UC-realize any two party and multiparty computation in the presence of an active and adaptive adversary corrupting any number of players. We also consider an alternative scenario, in which there are some trusted third parties but
Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.
Secure Multi-Party Computation (MPC) is a widely acknowledged framework enabling the design of multi-party protocols that preserve the privacy of parties' inputs while ensuring the correct evaluation of the desired functionality. Crucially, these security guarantees should hold even in the presence of external entities who are empowered with some adversarial capabilities, such as controlling the communication channels used throughout the protocol run or forcing a subset of the parties to behave arbitrarily (so-called ``malicious" or ``byzantine" corruptions). Concretely, a user can instantiate secure MPC protocols on a device to carry out computations involving sensitive information with other untrusted parties. Despite capturing very general classes of real-world threats, one limitation of ``traditional" MPC lies in assuming at least one ``honest" party who, throughout the protocol run, behaves exactly as per the theoretical specification of the protocol itself. For several practical settings this may be unrealistic, as the devices used to run the protocol are themselves exposed to a plethora of threats, such as attacks on software or hardware components. Moreover, the security guarantees provided by secure MPC could be voided if a protocol is found to be faulty, be it from cryptographic assumptions falling short or from an incorrect formalization of the protocol itself. In this composition, we explore more expressive frameworks that enable the design of secure MPC protocols and cryptographic primitives even in the presence of untrusted devices. We first consider cryptographic reverse firewalls: lightweight devices that sanitize a party's traffic while preserving the correctness of the protocol. These objects were originally introduced by Mironov and Stephens-Davidowitz (EUROCRYPT'15) and later embedded in the framework of subversion-resilient Universal Composability (srUC) due to Chakraborty et al. (EUROCRYPT'22). Under the srUC framework, it is possible to design protocols that provide meaningful security guarantees even if the devices of honest parties have been tampered with in an undetectable manner with the goal of exfiltrating information (so-called ``specious subversion attacks"). In particular, we focus on the design of protocols for Password-Authenticated Key Exchange (PAKE): a cryptographic primitive that enables two parties to mutually authenticate by establishing a shared high-entropy key leveraging exclusively some (possibly low-entropy) pre-shared password. (1) Our first contribution focuses on sanitizing the PAKE protocol from Oblivious Transfer (OT) due to Canetti et al. (PKC'12). For that, we design and instantiate novel cryptographic primitives with sanitation-friendly properties that may be of independent interest, including sanitizable variants of oblivious transfer, dual-mode cryptosystems, and signature schemes. As an additional contribution, we formalize the unauthenticated setting in the srUC framework by extending the framework of split-authentication due to Barak et al. (CRYPTO'05, JoC'07). This is the first PAKE protocol ever designed in the srUC framework. (2) Our second contribution consists of sanitizing the PAKE protocol from trapdoor smooth-projective hashing due to Benhamouda and Pointcheval (CRYPTO'13). The sanitation requires non-trivial modifications to the original protocol, whose security relies on a CCA-secure encryption scheme - an inherently non-malleable primitive. Along the way, we bring advances to the field of malleable smooth-projective hash functions, originally introduced by Chen et al. (ASIACRYPT'16), and coin the notion of malleable trapdoor smooth-projective hashing. Our resulting PAKE protocol has better communication and round complexity compared to the aforementioned PAKE-from-OT. We then shift our attention to t-out-of-n robust combiners: constructions that take as input n candidate instantiations of some cryptographic primitive to securely realize the same primitive, as long as at least t of the candidates are secure. These objects were first formalized by Harnik et al. (EUROCRYPT'05), where robustness is characterized by explicitly forbidding combiners from re-implementing the desired primitive from scratch. Here, we focus on Non-Interactive Zero-Knowledge (NIZK): a cryptographic primitive that allows a prover to convince a verifier of the veracity of some NP-statement by using a single message (commonly referred to as a ``proof"). (3) Our third contribution provides a comprehensive characterization of robust combiners for NIZK. We show the first formal definition of these objects, and prove that no robust NIZK combiner exists for t ≤ n/2 unless the polynomial hierarchy collapses. To complement our negative results, we provide three incomparable constructions: (i) A black-box combiner for {\em homomorphic} NP languages, where n,t are polynomial and t > n/2; (ii) A non-black-box combiner for any NP language, where n,t are constant and t > n/2; (iii) A non-black-box combiner for any NP language, where n,t are polynomial and t > 2n/3.
Secure multi-party computation (MPC) protocols that are resilient to a dishonest majority allow the adversary to get the output of the computation while, at the same time, forcing the honest parties to abort. Aumann and Lindell introduced the enhanced notion of security with identifiable abort , which still allows the adversary to trigger an abort but, at the same time, it enables the honest parties to agree on the identity of the party that led to the abort. More recently, in Eurocrypt 2016, Garg et al. showed that, assuming access to a simultaneous message exchange channel for all the parties, at least four rounds of communication are required to securely realize non-trivial functionalities in the plain model. Following Garg et al., a sequence of works has matched this lower bound, but none of them achieved security with identifiable abort. In this work, we close this gap and show that four rounds of communication are also sufficient to securely realize any functionality with identifiable abort using standard and generic polynomial-time assumptions. To achieve this result we introduce the new notion of bounded-rewind secure MPC that guarantees security even against an adversary that performs a mild form of reset attacks. We show how to instantiate this primitive starting from any MPC protocol and by assuming trapdoor-permutations. The notion of bounded-rewind secure MPC allows for easier parallel composition of MPC protocols with other (interactive) cryptographic primitives. Therefore, we believe that this primitive can be useful in other contexts in which it is crucial to combine multiple primitives with MPC protocols while keeping the round complexity of the final protocol low.