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

A Note on the Relation between the Definitions of Security for Semi-Honest and Malicious Adversaries.

Carmit Hazay, Yehuda Lindell

Published Jan 1, 2010• 12 citations
OpenAlex

Abstract

In secure computation, a set of parties wish to jointly compute some function of their private inputs while preserving security properties like privacy, correctness and more. The two main adversary models that have been considered are semi-honest adversaries who follow the prescribed protocol but try to glean more information than allowed from the protocol transcript, and malicious adversaries who can run any efficient strategy in order to carry out their attack. As such they can deviate at will from the prescribed protocol. One would naturally expect that any protocol that is secure in the presence of malicious adversaries will automatically be secure in the presence of semi-honest adversaries. However, due to a technicality in the definition, this is not necessarily true. In this brief note, we explain why this is the case, and show that a slight modification to the definition of semi-honest adversaries (specifically, allowing a semi-honest adversary to change its received input) suffices for fixing this anomaly. Our aim in publishing this note is to make this curious fact more known to the wider cryptographic community. 1 Malicious Versus Semi-honest Adversaries

Related papers

A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority

Yehuda Lindell, Ariel Nof

Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 27, 2017•96 citations

Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution

Yan Huang, Jonathan Katz, David Evans

Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party's input. Correctness of the honest party's output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some heuristic enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing dramatically stronger security guarantees.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2012•104 citations

Secure Two Party Computation

Kannan Balasubramanian

The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.

Advances in information security, privacy, and ethics book series•Aug 16, 2017•2 citations

Black-Box Constructions of Protocols for Secure Computation.

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz Z +2 more

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-blackbox since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a black-box use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make

•Jan 1, 2010•2 citations

Adversarial Level Agreements for Two-Party Protocols

Marilyn George, Seny Kamara

Adversaries in cryptography have traditionally been modeled as either semi-honest or malicious. Over the years, however, several works have investigated the design of cryptographic protocols against rational adversaries. The most well-known example are covert adversaries in secure computation (Aumann & Lindell, TCC '07) which are adversaries that wish to deviate from the protocol but without being detected. Protocols secure against such covert adversaries guarantee that deviations are detected with probability at least - which is known as the deterrence factor.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)•May 24, 2022•4 citations

New frontiers in secure computation

Rafail Ostrovsky, Amit Sahai, Abhishek Jain

The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation. In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results. The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation. The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.

•Jan 1, 2012•0 citations
In secure computation, a set of parties wish to jointly compute some function of their private inputs while preserving security properties like privacy, correctness and more. The two main adversary models that have been considered are semi-honest adversaries who follow the prescribed protocol but try to glean more information than allowed from the protocol transcript, and malicious adversaries who can run any efficient strategy in order to carry out their attack. As such they can deviate at will from the prescribed protocol. One would naturally expect that any protocol that is secure in the presence of malicious adversaries will automatically be secure in the presence of semi-honest adversaries. However, due to a technicality in the definition, this is not necessarily true. In this brief note, we explain why this is the case, and show that a slight modification to the definition of semi-honest adversaries (specifically, allowing a semi-honest adversary to change its received input) suffices for fixing this anomaly. Our aim in publishing this note is to make this curious fact more known to the wider cryptographic community. 1 Malicious Versus Semi-honest Adversaries
Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.
Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party's input. Correctness of the honest party's output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some heuristic enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing dramatically stronger security guarantees.
The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-blackbox since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a black-box use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make
Adversaries in cryptography have traditionally been modeled as either semi-honest or malicious. Over the years, however, several works have investigated the design of cryptographic protocols against rational adversaries. The most well-known example are covert adversaries in secure computation (Aumann & Lindell, TCC '07) which are adversaries that wish to deviate from the protocol but without being detected. Protocols secure against such covert adversaries guarantee that deviations are detected with probability at least - which is known as the deterrence factor.
The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation. In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results. The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation. The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.