Fair multi-party computation (MPC) requires that either all parties learn the output or none do. Existing fair protocols either rely on a trusted third party, impose high round complexity, or lack post-quantum security. We propose a new fairness mechanism based on cut elimination in multiplicative linear logic (MLL) proof nets. Our key insight is that proof nets naturally encode partial orders among input revelations, enabling efficient handling of arbitrary dependencies while guaranteeing atomic release. We combine proof nets with post-quantum lattice-based equivocal commitments in the common reference string (CRS) model toachieve privacy. A malicious party who aborts before eliminating its cut node leaves the final cut locked; honest parties detect the abort and output nothing. We provide a rigorous security analysis that includes a formal real/ideal simulation-based definition of fairness and privacy, explicit simulator constructions, and a hybrid argument for indistinguishability. The privacy proof works for any function representable as a Boolean circuit: the simulator, given the output and the corrupted parties’ inputs, can compute a consistent input for each honest party via reverse propagation (back-propagation) on the circuit. This yields a polynomial-time simulator without any additional assumptions. We present a full Python implementation of the three-party conditional computation y = (x1 ∧x2)∨x3, demonstrating explicit proof-net construction, real cut elimination, andfairness enforcement. The scheme requires no trusted third party, has O(k) rounds where k ≤ n is the number of actually eliminated cuts, and is post-quantum secure when instantiated with lattice-based commitments
Fair multi-party computation (MPC) requires that either all parties learn the output or none do. Existing fair protocols either rely on a trusted third party, impose high round complexity, or lack post-quantum security. We propose a new fairness mechanism based on cut elimination in multiplicative linear logic (MLL) proof nets. Our key insight is that proof nets naturally encode partial orders among input revelations, enabling efficient handling of arbitrary dependencies while guaranteeing atomic release. We combine proof nets with post-quantum lattice-based equivocal commitments in the common reference string (CRS) model toachieve privacy. A malicious party who aborts before eliminating its cut node leaves the final cut locked; honest parties detect the abort and output nothing. We provide a rigorous security analysis that includes a formal real/ideal simulation-based definition of fairness and privacy, explicit simulator constructions, and a hybrid argument for indistinguishability. The privacy proof works for any function representable as a Boolean circuit: the simulator, given the output and the corrupted parties’ inputs, can compute a consistent input for each honest party via reverse propagation (back-propagation) on the circuit. This yields a polynomial-time simulator without any additional assumptions. We present a full Python implementation of the three-party conditional computation y = (x1 ∧x2)∨x3, demonstrating explicit proof-net construction, real cut elimination, andfairness enforcement. The scheme requires no trusted third party, has O(k) rounds where k ≤ n is the number of actually eliminated cuts, and is post-quantum secure when instantiated with lattice-based commitments
Proof-theoretic cryptography is an emerging paradigm that grounds cryptographic security in the metatheory of linear logic proof nets, specifically the cut-elimination theorem. To enable modular construction and analysis of complex protocols in this paradigm, a compositional security framework is essential. In this paper, we propose such a framework, inspired by the Universal Composability (UC) framework but tailored to the algebraic structure of Multiplicative Linear Logic (MLL). We define a proof-net protocol as an MLL proof net with designated input/output interfaces and a partial order on its cut nodes. Two composition operators are naturally given by the logic: tensor product (⊗) for parallel composition and cut-elimination connection (◦) for sequential composition. We define an ideal functionality as a cut-free proof net together with a specification of its input/output behavior. We adopt a simulation-based security definition where the environment is an arbitrary PPT interactive Turingmachine (not restricted to proof nets), while the protocol and the adversary are described as proof-net protocols. This allows us to inherit the full power of the UC environment while keeping the protocol analysis within the proof-net framework. We then prove two composition theorems: if two protocols securely realize their respective ideal functionalities, then both their tensor product and their cut-elimination connection securely realize the corresponding compositions of the ideal functionalities. Theproofs rely on the confluence and strong normalization of cut elimination in MLL, which simplifies the analysis compared to general UC proofs, while still handling arbitrary environments. Finally, we discuss the relationship between our framework and the UC framework, clarifying that our framework is a specialization that exploits the algebraic structure of proof nets but does not sacrifice environmental generality. We also discuss the limitations of the current framework (static corruption, synchronousbroadcast) and outline directions for future generalization.
Secure Multi-party Computation (MPC) considers the problem where a set of mutually distrusting parties want to jointly compute a function over their private inputs, without revealing any extra information about these inputs other than what it can be inferred from the output of the function. This setting is well-motivated, and it has many real-world applications such as auction, voting, etc. MPC can be also seen as a generalization of many natural cryptographic primitives. For example, zero-knowledge (ZK) can be viewed as a special case of two-party secure computation. In ZK, a party, called prover aims to convince a second party, called verifier, that the prover’s private input witness w and a public input statement x belong to a relation R. An important research direction in secure computation is to find the trade-off between the required setup (e.g., the use of the broadcast channel, the use of common reference string (CRS) / public key infrastructure (PKI), the upper bound of the parties that can be corrupted, etc.), and the security guarantees that can be achieved. The setups can be viewed as some general assumptions that the protocol needs to satisfy, and they influence the usability of the protocol in real-world scenarios. In principle, having simpler (or no) setups mean that the protocol is more general and can be more useful in real-world scenarios. At the same time, having simpler setups may lead to weaker security guarantees. Therefore, finding the trade-off between setup and security guarantees is important and meaningful. In this thesis, we target MPC and ZK, and we focus on how to minimize the setup for MPC and ZK while still providing meaningful levels of security. More specifically: Regarding MPC, we focus on the dishonest majority (i.e., the adversary can corrupt all but one party), and we aim at 1) minimizing the use of broadcast channels. 2) studying the MPC with pre-processing when no setup is available. • Informally, a broadcast channel guarantees that when a message is sent, this reaches all the parties, without ambiguity. It also guarantees that if an honest party receives a message from a corrupted party, then it is guaranteed that all the honest parties have received the message. To realize broadcast, parties in the protocol could run the broadcast protocol, which may require many rounds of peer-to-peer communications. An alternative way is to rely on physical or external infrastructure such as blockchain. In both cases, broadcast is expensive, as such, we want to minimize its use. In particular, this thesis presents the following results: – When assuming no setup, we give a complete characterization with respect to the use of broadcast channels, and we obtain the optimal results. – We consider the same problem for the case that we only want to allow the black-box use (i.e., do not have access to the code of the algorithm) of the oblivious transfer protocol. We also give a characterization. • In the standard definition of MPC, the parties’ private inputs are fixed before the start of the protocol. However, there is another type of MPC named MPC with pre-processing, where the protocol can pre-compute some messages without using parties’ inputs, and these messages can accelerate computations in the online phase (i.e., other computations that require parties’ inputs). Since some expensive computations can be pre-computed, the online phase could be more lightweight. Therefore, we want to remove the dependency of the input from as many rounds as possible, so that we can do some pre-processing. In this direction, we explore the protocol with no setup. We provide a compiler that can turn a big class of MPC protocol that may require the inputs already to compute the first round, into a new protocol that needs the inputs only in the last two rounds. We also propose new MPC definitions that capture this delayed-input features. Regarding ZK, we do the following: • In standard single-theorem ZK definition, the security of the ZK protocol is guaranteed to hold only when one proof is issued. In the case where multiple zero-knowledge proofs need to be issued (i.e., to prove multiple NP statements), each new zero-knowledge proof requires a freshly generated setup. In the multi-theorem ZK definition, instead, one setup is sufficient for generating multiple zero-knowledge proofs for multiple instances. We propose a multi-theorem protocol (in the format of a compiler) that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Prior works could achieve this adaptive security only inefficiently via NP reductions. • ZK protocols are secure only when all setups are correctly generated, but in real-world scenarios, some of the setups may not be correctly generated. For instance, to run a non-interactive zero-knowledge (NIZK) protocol, the setup CRS could be chosen with bias. In this case, the security of the NIZK protocol does not hold anymore. Instead of finding a secure ZK candidate, one alternative solution is to have multiple instantiations of ZK candidates and assume that only for a subset of them the setup is generated correctly. More formally, we consider the case where only a subset of the instances are secure. In more detail, given access to n candidate instantiations of a NIZK for some language, we want to have a construction that itself implements a NIZK for the same language without relying on any additional computational assumptions. We refer to this type of construction as combiner, and the combiner is secure assuming at least t of the given candidates are secure. In this work, we provide three different constructions of robust NIZK combiners and show that combiners are impossible to realize unless the majority of the input candidates are secure.
Effective multi-party computation protocols have been developed, but concerns regarding privacy and correctness persist. Classic results demonstrate that guaranteed output delivery can be achieved by assuming fairness and identifiable abort. However, if the majority is malicious, it is still challenging to design an efficient implementation that can deliver correct outputs while maintaining robustness and fairness. To address this issue, we have redesigned the secret-sharing mechanism and employed a semi-trusted third party (TTP) as the key manager to provide optimistic backup for output delivery. The verification and delivery procedures prevent the malicious parties from “stealing” the output, when there is at least one honest party. Furthermore, the TTP has no knowledge of output, so even if he is malicious and colluding, we only lose fairness. The decryption is needed only when misconduct is detected. Our scheme also enables identified abort for offline preprocessing, and the audit of the offline sub-protocols can be publicly performed, holding corrupted parties accountable before receiving private inputs. With fairness and identifiable abort, output delivery is guaranteed by excluding the cheaters.
We consider the problem of constructing secure multi-party computation (MPC) protocols that are completely fair — meaning that either all the parties learn the output of the function, or nobody does — even when a majority of the parties are corrupted. We first propose a framework for fair multi-party computation (FMPC), within which we formulate a definition of secure and fair protocols. The definition follows the standard simulation paradigm, but is modified to allow the protocol to depend on the runing time of the adversary. In this way, we avoid a well-known impossibility result for fair MPC with corrupted majority; in particular, our definition admits constructions that tolerate up to (n− 1) corruptions, where n is the total number of parties. Next, we define a “commit-prove-fair-open” functionality and construct an efficient protocol that realizes it, using a new variant of a cryptographic primitive known as “time-lines.” With this functionality, we show that some of the existing secure MPC protocols can be easily transformed into fair protocols while preserving their security. Furthermore, these protocols remain secure when arbitrarily composed with any protocols, which means, in particular, that they are concurrently composable and non-malleable. This is joint work with Phil MacKenzie and Ke Yang.
Multi-party fair exchange (MFE) and fair secure multi-party computation (fair SMPC) are under-studied fields of research, with practical importance. In particular, we consider MFE scenarios where at the end of the protocol, either every participant receives every other participant’s item, or no participant receives anything. We analyze the case where a trusted third party (TTP) is optimistically available, although we emphasize that the trust put on the TTP is only regarding the fairness , and our protocols preserve the privacy of the exchanged items against the TTP. In the fair SMPC case, we prove that a malicious TTP can only harm fairness, but not security . We construct an asymptotically optimal multi-party fair exchange protocol that requires a constant number of rounds (in comparison to linear) and O(n 2 ) messages (in comparison to cubic), where n is the number of participating parties. In our protocol, we enable the parties to efficiently exchange any item that can be efficiently put into a verifiable encryption (e.g., signatures on a contract). We show how to apply this protocol on top of any SMPC protocol to achieve fairness with very little overhead (independent of the circuit size). We then generalize our protocol to efficiently handle any exchange topology (participants exchange items with arbitrary other participants). Our protocol guarantees fairness in its strongest sense: even if all n-1 other participants are malicious and colluding with each other, the fairness is still guaranteed.
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.