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

IEEE Symposium on Security and Privacy (S&P)

Efficient Actively Secure DPF and RAM-based 2PC with One-Bit Leakage

Wenhao Zhang, Xiaojie Guo, Kang Yang, Ruiyu Zhu, Yu Yu, Xiao Wang

Published May 19, 2024• 8 citations
Publisher

Abstract

Secure two-party computation (2PC) in the RAM model has attracted huge attention in recent years. Most existing results only support semi-honest security, with the exception of Keller and Yanai (Eurocrypt 2018) with very high cost. In this paper, we propose an efficient RAM-based 2PC protocol with active security and one-bit leakage.1)We propose an actively secure protocol for distributed point function (DPF), with one-bit leakage, that is essentially as efficient as the state-of-the-art semi-honest protocol. Compared with previous work, our protocol takes about 50× less communication for a domain with 220entries, and no longer requires actively secure generic 2PC.2)We extend the dual-execution protocol to allow reactive computation, and then build a RAM-based 2PC protocol with active security on top of our new building blocks. The protocol follows the paradigm of Doerner and shelat (CCS 2017). We are able to prove that the protocol has end-to-end one-bit leakage.3)Our implementation shows that our protocol is almost as efficient as the state-of-the-art semi-honest RAM-based 2PC protocol, and is at least two orders of magnitude faster than prior actively secure RAM-based 2PC without leakage, providing a realistic trade-off in practice.

DOI
10.1109/sp54263.2024.00205

Related papers

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

2PC Memory-Manipulating Programs with Constant Overhead

David Heath

General-purpose secure multiparty computation (MPC) remains bottlenecked in large part by a lack of efficient techniques for handling memory access. We demonstrate a remarkably simple and efficient 2PC instantiation of random access memory (RAM), based on distributed point functions (DPFs, Gilboa and Ishai, Eurocrypt'14). Our semi-honest 2PC protocol can be achieved from oblivious transfer (OT) and a black-box pseudorandom generator (PRG). For a memory storing large enough data words, our 2PC RAM incurs constant communication overhead per access. Like prior works using DPFs to achieve memory access, our work incurs linear computation per access, but per-access communication is lean. Our 2PC RAM is built on top of an obliviousness-friendly model of computation called the single access machine model (SAM, Appan et al., CCS'24). In the SAM model, each memory slot can be read at most once. We present a simple 2PC SAM protocol, where each single-access memory operation incurs at most O(w + λ lg n) bits of communication, where w is the word size, n is the number of memory words, and ?ambda is a security parameter. Of this cost, only 2w + 2lg n bits are incurred in the online phase. There are now many oblivious algorithms that compile directly to SAM more efficiently than via a compilation to RAM, and our 2PC SAM can instantiate these algorithms. As one example, we can use our 2PC SAM to implement privacy-preserving graph traversal (DFS or BFS) over a secret-shared size- n graph while revealing nothing beyond the runtime of the SAM program. Our construction achieves online communication O(n lg n) bits, asymptotically matching the number of bits touched in a corresponding cleartext graph traversal.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2026•0 citations

Highly Efficient Actively Secure Two-Party Computation with One-Bit Advantage Bound

Yi Liu, Junzuo Lai, Peng Yang +4 more

Secure two-party computation (2PC) enables two parties to jointly evaluate a function while maintaining input privacy. Despite recent significant progress, a notable efficiency gap remains between actively secure and passively secure protocols. In S&P'12, Huang, Katz, and Evans formalized the notion of active security with one-bit leakage, providing a promising approach to bridging this gap. Protocols derived from this notion have become foundational in designing highly efficient actively secure 2PC protocols. However, a critical challenge identified by Huang, Katz, and Evans remains unexplored: these protocols face significant weaknesses in ensuring fairness for honest parties when employed in standalone settings rather than as components within larger protocols. While the authors proposed two potential solutions to mitigate this issue, both approaches are prohibitively expensive and lack formalization of security guarantees. In this paper, we first formally define an enhanced notion called active security with one-bit-advantage bound, in which the adversaries' advantages are strictly bounded to at most one bit beyond what honest parties obtain. This bound is enforced through a progressive revelation mechanism, where the evaluation result is disclosed incrementally bit by bit. In addition, we propose a novel approach leveraging label structures within garbled circuits to design a highly efficient constant-round 2PC protocol that achieves active security with one-bit advantage bound. Our protocol demonstrates runtime performance nearly identical to that of passively secure garbled-circuit counterparts in duplex networks (e.g., 1.033 × for the SHA256 circuit in LAN), with low overhead for output progressive revelation (only 80 communicated bytes per bit release). With its strengthened security guarantees and minimal overhead, our protocol is highly suitable for practical 2PC applications.

IEEE Symposium on Security and Privacy (S&P)•May 12, 2025•1 citation

Actively Secure Half-Gates with Minimum Overhead under Duplex Networks

Hongrui Cui, Xiao Shaun Wang, Kang Yang +1 more

Abstract Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of $$2\kappa +5$$ 2 κ + 5 bits per AND gate (for $$\kappa $$ κ -bit computational security and any statistical security) and one with total communication of $$2\kappa +\rho +5$$ 2 κ + ρ + 5 bits per AND gate (for $$\rho $$ ρ -bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: The recent compression technique by Dittmer et al. (Crypto 13510:57–87, 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $$5\rho +1$$ 5 ρ + 1 bits to 2 bits per AND gate for $$\rho $$ ρ -bit statistical security. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $$2\kappa +3\rho $$ 2 κ + 3 ρ bits per AND gate. We designed a new authenticated garbling that does not use information-theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $$2\kappa +1$$ 2 κ + 1 bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $$2\kappa +5$$ 2 κ + 5 bits per AND gate. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 13510:57–87, 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from $$2\kappa +3\rho $$ 2 κ + 3 ρ bits down to $$2\kappa +\rho +1$$ 2 κ + ρ + 1 bits per AND gate. Combined with our first contribution, this yields total amortized communication of $$2\kappa +\rho +5$$ 2 κ + ρ + 5 bits.

Journal of Cryptology•Feb 26, 2025•0 citations

How to Efficiently Evaluate RAM Programs with Malicious Security.

Arash Afshar, Zhangxiang Hu, Payman Mohassel +1 more

Secure 2-party computation (2PC) is becoming practical for some applications. However, most ap-proaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, random-access machines (RAM programs) have recently been investigated as a promising alternative representation. In this work, we present the first practical protocols for evaluating RAM programs with security against malicious adversaries. A useful efficiency measure is to divide the cost of malicious-secure evalu-ation of f by the cost of semi-honest-secure evaluation of f. Our RAM protocols achieve ratios matching the state of the art for circuit-based 2PC. For statistical security 2−s, our protocol without preprocessing achieves a ratio of s; our online-offline protocol has a pre-processing phase and achieves online ratio ∼ 2s / log T, where T is the total execution time of the RAM program. To summarize, our solutions show that the “extra overhead ” of obtaining malicious security for RAM programs (beyond what is needed for circuits) is minimal and does not grow with the running time of the program. 1

•Jan 1, 2014•2 citations

Faster Malicious 2-Party Secure Computation with Online/Offline Dual Execution

Peter Rindal, Mike Rosulek

We describe a highly optimized protocol for generalpurpose secure two-party computation (2PC) in the presence of malicious adversaries. Our starting point is a protocol of Kolesnikov et al. (TCC 2015). We adapt that protocol to the online/offline setting, where two parties repeatedly evaluate the same function (on possibly different inputs each time) and perform as much of the computation as possible in an offline preprocessing phase before their inputs are known. Along the way we develop several significant simplifications and optimizations to the protocol. We have implemented a prototype of our protocol and report on its performance. When two parties on Amazon servers in the same region use our implementation to securely evaluate the AES circuit 1024 times, the amortized cost per evaluation is 5.1ms offline + 1.3ms online. The total offline+online cost of our protocol is in fact less than the online cost of any reported protocol with malicious security. For comparison, our protocol’s closest competitor (Lindell & Riva, CCS 2015) uses 74ms offline + 7ms online in an identical setup. Our protocol can be further tuned to trade performance for leakage. As an example, the performance in the above scenario improves to 2.4ms offline + 1.0ms online if we allow an adversary to learn a single bit about the honest party’s input with probability 2−20 (but not violate any other security property, e.g. correctness).

USENIX Security Symposium•Jan 1, 2016•40 citations
Secure two-party computation (2PC) in the RAM model has attracted huge attention in recent years. Most existing results only support semi-honest security, with the exception of Keller and Yanai (Eurocrypt 2018) with very high cost. In this paper, we propose an efficient RAM-based 2PC protocol with active security and one-bit leakage.1)We propose an actively secure protocol for distributed point function (DPF), with one-bit leakage, that is essentially as efficient as the state-of-the-art semi-honest protocol. Compared with previous work, our protocol takes about 50× less communication for a domain with 220entries, and no longer requires actively secure generic 2PC.2)We extend the dual-execution protocol to allow reactive computation, and then build a RAM-based 2PC protocol with active security on top of our new building blocks. The protocol follows the paradigm of Doerner and shelat (CCS 2017). We are able to prove that the protocol has end-to-end one-bit leakage.3)Our implementation shows that our protocol is almost as efficient as the state-of-the-art semi-honest RAM-based 2PC protocol, and is at least two orders of magnitude faster than prior actively secure RAM-based 2PC without leakage, providing a realistic trade-off in practice.
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.
General-purpose secure multiparty computation (MPC) remains bottlenecked in large part by a lack of efficient techniques for handling memory access. We demonstrate a remarkably simple and efficient 2PC instantiation of random access memory (RAM), based on distributed point functions (DPFs, Gilboa and Ishai, Eurocrypt'14). Our semi-honest 2PC protocol can be achieved from oblivious transfer (OT) and a black-box pseudorandom generator (PRG). For a memory storing large enough data words, our 2PC RAM incurs constant communication overhead per access. Like prior works using DPFs to achieve memory access, our work incurs linear computation per access, but per-access communication is lean. Our 2PC RAM is built on top of an obliviousness-friendly model of computation called the single access machine model (SAM, Appan et al., CCS'24). In the SAM model, each memory slot can be read at most once. We present a simple 2PC SAM protocol, where each single-access memory operation incurs at most O(w + λ lg n) bits of communication, where w is the word size, n is the number of memory words, and ?ambda is a security parameter. Of this cost, only 2w + 2lg n bits are incurred in the online phase. There are now many oblivious algorithms that compile directly to SAM more efficiently than via a compilation to RAM, and our 2PC SAM can instantiate these algorithms. As one example, we can use our 2PC SAM to implement privacy-preserving graph traversal (DFS or BFS) over a secret-shared size- n graph while revealing nothing beyond the runtime of the SAM program. Our construction achieves online communication O(n lg n) bits, asymptotically matching the number of bits touched in a corresponding cleartext graph traversal.
Secure two-party computation (2PC) enables two parties to jointly evaluate a function while maintaining input privacy. Despite recent significant progress, a notable efficiency gap remains between actively secure and passively secure protocols. In S&P'12, Huang, Katz, and Evans formalized the notion of active security with one-bit leakage, providing a promising approach to bridging this gap. Protocols derived from this notion have become foundational in designing highly efficient actively secure 2PC protocols. However, a critical challenge identified by Huang, Katz, and Evans remains unexplored: these protocols face significant weaknesses in ensuring fairness for honest parties when employed in standalone settings rather than as components within larger protocols. While the authors proposed two potential solutions to mitigate this issue, both approaches are prohibitively expensive and lack formalization of security guarantees. In this paper, we first formally define an enhanced notion called active security with one-bit-advantage bound, in which the adversaries' advantages are strictly bounded to at most one bit beyond what honest parties obtain. This bound is enforced through a progressive revelation mechanism, where the evaluation result is disclosed incrementally bit by bit. In addition, we propose a novel approach leveraging label structures within garbled circuits to design a highly efficient constant-round 2PC protocol that achieves active security with one-bit advantage bound. Our protocol demonstrates runtime performance nearly identical to that of passively secure garbled-circuit counterparts in duplex networks (e.g., 1.033 × for the SHA256 circuit in LAN), with low overhead for output progressive revelation (only 80 communicated bytes per bit release). With its strengthened security guarantees and minimal overhead, our protocol is highly suitable for practical 2PC applications.
Abstract Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of 2κ+52\kappa +52κ+5 2 κ + 5 bits per AND gate (for κ\kappa κ κ -bit computational security and any statistical security) and one with total communication of 2κ+ρ+52\kappa +\rho +52κ+ρ+5 2 κ + ρ + 5 bits per AND gate (for ρ\rho ρ ρ -bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: The recent compression technique by Dittmer et al. (Crypto 13510:57–87, 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from 5ρ+15\rho +15ρ+1 5 ρ + 1 bits to 2 bits per AND gate for ρ\rho ρ ρ -bit statistical security. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size 2κ+3ρ2\kappa +3\rho 2κ+3ρ 2 κ + 3 ρ bits per AND gate. We designed a new authenticated garbling that does not use information-theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size 2κ+12\kappa +12κ+1 2 κ + 1 bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of 2κ+52\kappa +52κ+5 2 κ + 5 bits per AND gate. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 13510:57–87, 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from 2κ+3ρ2\kappa +3\rho 2κ+3ρ 2 κ + 3 ρ bits down to 2κ+ρ+12\kappa +\rho +12κ+ρ+1 2 κ + ρ + 1 bits per AND gate. Combined with our first contribution, this yields total amortized communication of 2κ+ρ+52\kappa +\rho +52κ+ρ+5 2 κ + ρ + 5 bits.
Secure 2-party computation (2PC) is becoming practical for some applications. However, most ap-proaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, random-access machines (RAM programs) have recently been investigated as a promising alternative representation. In this work, we present the first practical protocols for evaluating RAM programs with security against malicious adversaries. A useful efficiency measure is to divide the cost of malicious-secure evalu-ation of f by the cost of semi-honest-secure evaluation of f. Our RAM protocols achieve ratios matching the state of the art for circuit-based 2PC. For statistical security 2−s, our protocol without preprocessing achieves a ratio of s; our online-offline protocol has a pre-processing phase and achieves online ratio ∼ 2s / log T, where T is the total execution time of the RAM program. To summarize, our solutions show that the “extra overhead ” of obtaining malicious security for RAM programs (beyond what is needed for circuits) is minimal and does not grow with the running time of the program. 1
We describe a highly optimized protocol for generalpurpose secure two-party computation (2PC) in the presence of malicious adversaries. Our starting point is a protocol of Kolesnikov et al. (TCC 2015). We adapt that protocol to the online/offline setting, where two parties repeatedly evaluate the same function (on possibly different inputs each time) and perform as much of the computation as possible in an offline preprocessing phase before their inputs are known. Along the way we develop several significant simplifications and optimizations to the protocol. We have implemented a prototype of our protocol and report on its performance. When two parties on Amazon servers in the same region use our implementation to securely evaluate the AES circuit 1024 times, the amortized cost per evaluation is 5.1ms offline + 1.3ms online. The total offline+online cost of our protocol is in fact less than the online cost of any reported protocol with malicious security. For comparison, our protocol’s closest competitor (Lindell & Riva, CCS 2015) uses 74ms offline + 7ms online in an identical setup. Our protocol can be further tuned to trade performance for leakage. As an example, the performance in the above scenario improves to 2.4ms offline + 1.0ms online if we allow an adversary to learn a single bit about the honest party’s input with probability 2−20 (but not violate any other security property, e.g. correctness).