Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Computational Irrelevancy: Bridging the Gap Between Pseudo- and Real Randomness in MPC Protocols

Nariyasu Heseri, Koji Nuida

Published Jan 1, 2022• 1 citation
Publisher
DOI
10.1007/978-3-031-15255-9_11

Related papers

Concretely Efficient MPC Protocols for Real-world Applications

Nan Cheng

•May 11, 2026•0 citations

MPC in de echte wereld: praktische aspecten van meerpartijrekenen

Botelho da Gama, Mariana

In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.

•Feb 10, 2025•0 citations

Information-Theoretic Robust MPC Protocols

Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen

Cambridge University Press eBooks•Jun 30, 2015•0 citations

Efficient Actively Secure Multi-Party Computation for RAM Programs

Kun Xiong, Wenfang Zhang, Muhammad Khurram Khan

Cloud platforms offer innovative solutions for data processing, and privacy concerns arising from this can be addressed through secure multi-party computation (MPC). MPC in the random access machine (RAM) model leverages Oblivious RAM (ORAM) to conceal memory access patterns, rendering it more suitable for data storage and aggregation in cloud environments, where cloud servers can infer user privacy based on observed access patterns. However, most existing RAM-based MPC protocols only ensure semi-honest security; the few actively secure alternatives have limitations in efficiency or input leakage. To address this gap, this paper proposes an efficient active-secure RAM-based MPC protocol without input leakage. Specifically, we first present a new actively secure, reactive MPC protocol with communication of 2(n−1) bits per gate. As the building blocks, we design the (i) multi-party distributed BitGC garbling scheme and (ii) multi-party somewhat homomorphic encryption (SWHE) scheme with distributed decryption. In particular, we then build a RAM-based MPC protocol on top of the above new building blocks with Circuit ORAM and present the check mechanism to achieve secure memory accesses. The implementation shows that our protocol outperforms the prior actively secure RAM-based MPC without leakage by one to two orders of magnitude in both LAN and WAN networks. Compared with the state-of-the-art actively secure RAM-based 2PC with one bit leakage, ours is slightly less efficient in most cases (not all), but supports the multi-party setting and offers a superior alternative for highly confidential environments.

IEEE Transactions on Cloud Computing•Jan 1, 2026•0 citations

On the Bottleneck Complexity of MPC with Correlated Randomness

Claudio Orlandi, Divya Ravi, Peter Schöll

Lecture notes in computer science•Jan 1, 2022•2 citations

Dishonest Majority Passive-to-Active Compiler Over Rings for MPC With Constant Online Communication

Jiandong Zhang, Han Jiang, Chenkai Zeng +5 more

Secure multiparty computation (MPC) over Z2kis more efficient than computations over fields, and studying MPC protocols under malicious security has practical application value. Malicious security with a dishonest majority over rings remains challenging. The most popular approach is SPDZ2k, however, this is a specific protocol that does not support the transformation of any existing semi-honest MPC protocols into malicious security protocols. The zero knowledge proof (ZKP)-based compiler satisfies this requirement. Existing state-of-the-art protocols have logarithmic online communication overhead in terms of the circuit size |C|, and their direct application to rings is nontrivial as they were originally designed for finite fields. In this work, we investigate the communication overhead to develop malicious security protocols. We bridge the gap between malicious security with abort and semi-honest security, by constructing a “GMW-style” verification protocol to achieve malicious security in a dishonest majority setting. This approach incurs a constant online communication overhead by enhancing the machinery of zero-knowledge fully linear interactive oracle proof (zk-FLIOP). Additionally, we extend the zk-FLIOP to work over any ring by invoking reverse multiplication friendly embeddings (RMFEs). Our results show that the online communication complexity of the verification process depends on only the security parameter, the number of parties, and the ring size. Furthermore, for small-scale circuits over Z2, we designed a distributed lookup table argument where both the total communication complexity and the computational cost are independent of the circuit size but of the input wires.

IEEE Transactions on Information Forensics and Security•Jan 1, 2026•1 citation
In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.
Cloud platforms offer innovative solutions for data processing, and privacy concerns arising from this can be addressed through secure multi-party computation (MPC). MPC in the random access machine (RAM) model leverages Oblivious RAM (ORAM) to conceal memory access patterns, rendering it more suitable for data storage and aggregation in cloud environments, where cloud servers can infer user privacy based on observed access patterns. However, most existing RAM-based MPC protocols only ensure semi-honest security; the few actively secure alternatives have limitations in efficiency or input leakage. To address this gap, this paper proposes an efficient active-secure RAM-based MPC protocol without input leakage. Specifically, we first present a new actively secure, reactive MPC protocol with communication of 2(n−1) bits per gate. As the building blocks, we design the (i) multi-party distributed BitGC garbling scheme and (ii) multi-party somewhat homomorphic encryption (SWHE) scheme with distributed decryption. In particular, we then build a RAM-based MPC protocol on top of the above new building blocks with Circuit ORAM and present the check mechanism to achieve secure memory accesses. The implementation shows that our protocol outperforms the prior actively secure RAM-based MPC without leakage by one to two orders of magnitude in both LAN and WAN networks. Compared with the state-of-the-art actively secure RAM-based 2PC with one bit leakage, ours is slightly less efficient in most cases (not all), but supports the multi-party setting and offers a superior alternative for highly confidential environments.
Secure multiparty computation (MPC) over Z2kis more efficient than computations over fields, and studying MPC protocols under malicious security has practical application value. Malicious security with a dishonest majority over rings remains challenging. The most popular approach is SPDZ2k, however, this is a specific protocol that does not support the transformation of any existing semi-honest MPC protocols into malicious security protocols. The zero knowledge proof (ZKP)-based compiler satisfies this requirement. Existing state-of-the-art protocols have logarithmic online communication overhead in terms of the circuit size |C|, and their direct application to rings is nontrivial as they were originally designed for finite fields. In this work, we investigate the communication overhead to develop malicious security protocols. We bridge the gap between malicious security with abort and semi-honest security, by constructing a “GMW-style” verification protocol to achieve malicious security in a dishonest majority setting. This approach incurs a constant online communication overhead by enhancing the machinery of zero-knowledge fully linear interactive oracle proof (zk-FLIOP). Additionally, we extend the zk-FLIOP to work over any ring by invoking reverse multiplication friendly embeddings (RMFEs). Our results show that the online communication complexity of the verification process depends on only the security parameter, the number of parties, and the ring size. Furthermore, for small-scale circuits over Z2, we designed a distributed lookup table argument where both the total communication complexity and the computational cost are independent of the circuit size but of the input wires.