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.
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). Recently, an alternative solution was proposed by Katz in [K07], suggesting that one may rely on physical assumptions rather than trusted third parties. Concretely, the solution assumed it physically possible to construct tamper proof hardware tokens which can be run in complete isolation from the surrounding environment. Here we improve upon the work of [K07] by constructing a scheme in which the tokens only need to be partially isolated and may have some limited communication with the environment. In addition we improve on Katz’s work by presenting a scheme which is secure against adaptive adversaries and is based on general cryptographic assumptions. We also consider an alternative scenario, in which there are some trusted third parties but no single such party is trusted by all of the players. This compromise allows us to limit the use of the physical set-up and hence might be preferred in practice.
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.
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 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.
Abstract. In the setting of secure multiparty computation, a set of parties wish to jointly compute some function of their inputs. Such a computation must preserve certain security properties, like privacy and correctness, even if some of the participating parties or an external adversary collude to attack the honest parties. Until this paper, all protocols for general secure computation assumed that the parties can communicate reliably via authenticated channels. In this paper, we consider the feasibility of secure computation without any setup assumption. 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. In particular, we define a relaxed notion of what it means to “securely compute ” a function in the unauthenticated setting. Then, we construct protocols for securely realizing any functionality in the stand-alone model, with no setup assumptions whatsoever. In addition, we construct universally composable protocols for securely realizing any functionality in the common reference string model (while still in an unauthenticated network). We also show that 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. 1