The Experts below are selected from a list of 4515 Experts worldwide ranked by ideXlab platform
Yehuda Lindell - One of the best experts on this subject based on the ideXlab platform.
-
EUROCRYPT (2) - High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority
Lecture Notes in Computer Science, 2017Co-Authors: Jun Furukawa, Ariel Nof, Yehuda Lindell, Or WeinsteinAbstract:In this paper, we describe a new protocol for secure three-party computation of any functionality, with an honest majority and a Malicious Adversary. Our protocol has both an information-theoretic and computational variant, and is distinguished by extremely low communication complexity and very simple computation. We start from the recent semi-honest protocol of Araki et al. (ACM CCS 2016) in which the parties communicate only a single bit per AND gate, and modify it to be secure in the presence of Malicious adversaries. Our protocol follows the paradigm of first constructing Beaver multiplication triples and then using them to verify that circuit gates are correctly computed. As in previous work (e.g., the so-called TinyOT and SPDZ protocols), we rely on the cut-and-choose paradigm to verify that triples are correctly constructed. We are able to utilize the fact that at most one of three parties is corrupted in order to construct an extremely simple and efficient method of constructing such triples. We also present an improved combinatorial analysis for this cut-and-choose which can be used to achieve improvements in other protocols using this approach.
-
High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority
Advances in Cryptology – EUROCRYPT 2017, 2017Co-Authors: Jun Furukawa, Ariel Nof, Yehuda Lindell, Or WeinsteinAbstract:In this paper, we describe a new protocol for secure three-party computation of any functionality, with an honest majority and a Malicious Adversary. Our protocol has both an information-theoretic and computational variant, and is distinguished by extremely low communication complexity and very simple computation. We start from the recent semi-honest protocol of Araki et al. (ACM CCS 2016) in which the parties communicate only a single bit per AND gate, and modify it to be secure in the presence of Malicious adversaries. Our protocol follows the paradigm of first constructing Beaver multiplication triples and then using them to verify that circuit gates are correctly computed. As in previous work (e.g., the so-called TinyOT and SPDZ protocols), we rely on the cut-and-choose paradigm to verify that triples are correctly constructed. We are able to utilize the fact that at most one of three parties is corrupted in order to construct an extremely simple and efficient method of constructing such triples. We also present an improved combinatorial analysis for this cut-and-choose which can be used to achieve improvements in other protocols using this approach.
-
Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries
Journal of Cryptology, 2010Co-Authors: Carmit Hazay, Yehuda LindellAbstract:In this paper, we construct efficient secure protocols for set intersection and pattern matching . Our protocols for secure computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that are based on polynomials. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor–Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two Adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against Malicious adversaries under a relaxed definition where one corruption case is simulatable and, for the other, only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a Malicious Adversary can cheat but will then be caught with good probability.
-
A Note on the Relation between the Definitions of Security for Semi-Honest and Malicious Adversaries.
IACR Cryptology ePrint Archive, 2010Co-Authors: Carmit Hazay, Yehuda LindellAbstract: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 In order to keep this note brief, we assume that the reader is familiar with the exact definitions of relevance. We refer to [2], [4, Chapter 7], or [5, Chapter 2] for motivation and full definitions of secure computation in the presence of semi-honest and Malicious adversaries. At first sight, it seems that any protocol that is secure in the presence of Malicious adversaries is also secure in the presence of semi-honest adversaries. This is because a semi-honest Adversary is just a “special case” of a Malicious Adversary who faithfully follows the protocol specification. Although this is what we would expect, it turns out to be false. This anomaly is due to the fact that although a real semi-honest Adversary is indeed a special case of a real Malicious Adversary, this is not true of the respective adversaries in the ideal model. Specifically, the Adversary in the ideal model for Malicious adversaries is allowed to change its input, whereas the Adversary in the ideal model for semi-honest adversaries is not. Thus, the Adversary/simulator for the case of Malicious adversaries has more power than the Adversary/simulator for the case of semi-honest adversaries. As such, it may be possible to simulate a protocol in the Malicious model, but not in the semi-honest model. We now present two examples of protocols where this occurs. ∗We thank Yuval Ishai for first pointing out this inconsistency in the definitions to us. Most of this note is an excerpt from [5]. †Dept. of Computer Science, Aarhus University, Denmark. carmit@cs.au.dk. ‡Dept. of Computer Science, Bar-Ilan University, Israel. lindell@cs.biu.ac.il.
-
efficient protocols for set intersection and pattern matching with security against Malicious and covert adversaries
Theory of Cryptography Conference, 2008Co-Authors: Carmit Hazay, Yehuda LindellAbstract:In this paper we construct efficient secure protocols for set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that used secure polynomial evaluation. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two Adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against Malicious adversaries under a relaxed definition where one corruption case is simulatable and for the other only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a Malicious Adversary can cheat, but will then be caught with good probability.
Carmit Hazay - One of the best experts on this subject based on the ideXlab platform.
-
Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries
Journal of Cryptology, 2010Co-Authors: Carmit Hazay, Yehuda LindellAbstract:In this paper, we construct efficient secure protocols for set intersection and pattern matching . Our protocols for secure computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that are based on polynomials. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor–Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two Adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against Malicious adversaries under a relaxed definition where one corruption case is simulatable and, for the other, only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a Malicious Adversary can cheat but will then be caught with good probability.
-
A Note on the Relation between the Definitions of Security for Semi-Honest and Malicious Adversaries.
IACR Cryptology ePrint Archive, 2010Co-Authors: Carmit Hazay, Yehuda LindellAbstract: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 In order to keep this note brief, we assume that the reader is familiar with the exact definitions of relevance. We refer to [2], [4, Chapter 7], or [5, Chapter 2] for motivation and full definitions of secure computation in the presence of semi-honest and Malicious adversaries. At first sight, it seems that any protocol that is secure in the presence of Malicious adversaries is also secure in the presence of semi-honest adversaries. This is because a semi-honest Adversary is just a “special case” of a Malicious Adversary who faithfully follows the protocol specification. Although this is what we would expect, it turns out to be false. This anomaly is due to the fact that although a real semi-honest Adversary is indeed a special case of a real Malicious Adversary, this is not true of the respective adversaries in the ideal model. Specifically, the Adversary in the ideal model for Malicious adversaries is allowed to change its input, whereas the Adversary in the ideal model for semi-honest adversaries is not. Thus, the Adversary/simulator for the case of Malicious adversaries has more power than the Adversary/simulator for the case of semi-honest adversaries. As such, it may be possible to simulate a protocol in the Malicious model, but not in the semi-honest model. We now present two examples of protocols where this occurs. ∗We thank Yuval Ishai for first pointing out this inconsistency in the definitions to us. Most of this note is an excerpt from [5]. †Dept. of Computer Science, Aarhus University, Denmark. carmit@cs.au.dk. ‡Dept. of Computer Science, Bar-Ilan University, Israel. lindell@cs.biu.ac.il.
-
efficient protocols for set intersection and pattern matching with security against Malicious and covert adversaries
Theory of Cryptography Conference, 2008Co-Authors: Carmit Hazay, Yehuda LindellAbstract:In this paper we construct efficient secure protocols for set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that used secure polynomial evaluation. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two Adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against Malicious adversaries under a relaxed definition where one corruption case is simulatable and for the other only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a Malicious Adversary can cheat, but will then be caught with good probability.
-
TCC - Efficient protocols for set intersection and pattern matching with security against Malicious and covert adversaries
Theory of Cryptography, 1Co-Authors: Carmit Hazay, Yehuda LindellAbstract:In this paper we construct efficient secure protocols for set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that used secure polynomial evaluation. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two Adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against Malicious adversaries under a relaxed definition where one corruption case is simulatable and for the other only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a Malicious Adversary can cheat, but will then be caught with good probability.
William Yeoh - One of the best experts on this subject based on the ideXlab platform.
-
game theoretic goal recognition models with applications to security domains
Decision and Game Theory for Security, 2017Co-Authors: Hau Chan, Albert Xin Jiang, William YeohAbstract:Motivated by the goal recognition (GR) and goal recognition design (GRD) problems in the artificial intelligence (AI) planning domain, we introduce and study two natural variants of the GR and GRD problems with strategic agents, respectively. More specifically, we consider game-theoretic (GT) scenarios where a Malicious Adversary aims to damage some target in an (physical or virtual) environment monitored by a defender. The Adversary must take a sequence of actions in order to attack the intended target. In the GTGR and GTGRD settings, the defender attempts to identify the Adversary’s intended target while observing the Adversary’s available actions so that he/she can strengthens the target’s defense against the attack. In addition, in the GTGRD setting, the defender can alter the environment (e.g., adding roadblocks) in order to better distinguish the goal/target of the Adversary.
-
GameSec - Game-Theoretic Goal Recognition Models with Applications to Security Domains
Lecture Notes in Computer Science, 2017Co-Authors: Hau Chan, Albert Xin Jiang, William YeohAbstract:Motivated by the goal recognition (GR) and goal recognition design (GRD) problems in the artificial intelligence (AI) planning domain, we introduce and study two natural variants of the GR and GRD problems with strategic agents, respectively. More specifically, we consider game-theoretic (GT) scenarios where a Malicious Adversary aims to damage some target in an (physical or virtual) environment monitored by a defender. The Adversary must take a sequence of actions in order to attack the intended target. In the GTGR and GTGRD settings, the defender attempts to identify the Adversary’s intended target while observing the Adversary’s available actions so that he/she can strengthens the target’s defense against the attack. In addition, in the GTGRD setting, the defender can alter the environment (e.g., adding roadblocks) in order to better distinguish the goal/target of the Adversary.
Sidharth Jaggi - One of the best experts on this subject based on the ideXlab platform.
-
communication efficient secret sharing in the presence of Malicious Adversary
International Symposium on Information Theory, 2020Co-Authors: Rawad Bitar, Sidharth JaggiAbstract:Consider the communication efficient secret sharing problem. A dealer wants to share a secret with n parties such that any k ≤ n parties can reconstruct the secret and any z < k parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any d, k ≤d ≤n, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of Malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the Malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e., maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from d parties, k ≤d≤ n. We construct codes that achieve capacity. In addition, the constructed codes achieve minimum read and communication costs for all possible values of d. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect the presence of a limited knowledge Adversary.
-
communication efficient secret sharing in the presence of Malicious Adversary
arXiv: Information Theory, 2020Co-Authors: Rawad Bitar, Sidharth JaggiAbstract:Consider the communication efficient secret sharing problem. A dealer wants to share a secret with $n$ parties such that any $k\leq n$ parties can reconstruct the secret and any $z
-
ISIT - Communication Efficient Secret Sharing in the Presence of Malicious Adversary
2020 IEEE International Symposium on Information Theory (ISIT), 2020Co-Authors: Rawad Bitar, Sidharth JaggiAbstract:Consider the communication efficient secret sharing problem. A dealer wants to share a secret with n parties such that any k ≤ n parties can reconstruct the secret and any z < k parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any d, k ≤d ≤n, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of Malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the Malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e., maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from d parties, k ≤d≤ n. We construct codes that achieve capacity. In addition, the constructed codes achieve minimum read and communication costs for all possible values of d. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect the presence of a limited knowledge Adversary.
Haojin Zhu - One of the best experts on this subject based on the ideXlab platform.
-
Constant-round adaptive zero-knowledge proofs for NP
Information Sciences, 2014Co-Authors: Zongyang Zhang, Zhenfu Cao, Haojin ZhuAbstract:Secure two-party computation allows two parties with private inputs to securely compute some function of their inputs, even in the presence of a Malicious Adversary. In this work, we revisit zero-knowledge proofs and focus on adaptive adversaries, which could corrupt an arbitrary number of parties and adaptively determine who and when to corrupt during the computation phase. Previous constructions could realize adaptive zero-knowledge proofs for all languages in NP (Lindell and Zarosim TCC'09) at the cost of a high round-complexity, i.e., super-constant number of rounds. In this work, assuming the existence of constant-round statistically hiding commitment schemes, we build efficient adaptive zero-knowledge proofs for all languages in NP, which only require constant number of communication rounds. The system is also a proof of knowledge. The construction relies on an adaptive instance-dependent commitment scheme, and the proof of security requires only the use of black-box techniques and is presented according to the real/ideal simulation paradigm.
-
network coding based privacy preservation against traffic analysis in multi hop wireless networks
IEEE Transactions on Wireless Communications, 2011Co-Authors: Yanfei Fan, Yixin Jiang, Haojin Zhu, Jiming Chen, Xuemin Sherman ShenAbstract:Privacy threat is one of the critical issues in multi-hop wireless networks, where attacks such as traffic analysis and flow tracing can be easily launched by a Malicious Adversary due to the open wireless medium. Network coding has the potential to thwart these attacks since the coding/mixing operation is encouraged at intermediate nodes. However, the simple deployment of network coding cannot achieve the goal once enough packets are collected by the adversaries. On the other hand, the coding/mixing nature precludes the feasibility of employing the existing privacy-preserving techniques, such as Onion Routing. In this paper, we propose a novel network coding based privacy-preserving scheme against traffic analysis in multi-hop wireless networks. With homomorphic encryption on Global Encoding Vectors (GEVs), the proposed scheme offers two significant privacy-preserving features, packet flow untraceability and message content confidentiality, for efficiently thwarting the traffic analysis attacks. Moreover, the proposed scheme keeps the random coding feature, and each sink can recover the source packets by inverting the GEVs with a very high probability. Theoretical analysis and simulative evaluation demonstrate the validity and efficiency of the proposed scheme.
-
an efficient privacy preserving scheme against traffic analysis attacks in network coding
International Conference on Computer Communications, 2009Co-Authors: Yanfei Fan, Yixin Jiang, Haojin Zhu, Xuemin ShenAbstract:Privacy threat is one of the critical issues in network coding, where attacks such as traffic analysis can be easily launched by a Malicious Adversary once enough encoded packets are collected. Furthermore, the encoding/mixing nature of net- work coding precludes the feasibility of employing the existing privacy-preserving techniques, such as Onion Routing, in network coding enabled networks. In this paper, we propose a novel pri- vacy-preserving scheme against traffic analysis in network coding. With homomorphic encryption operation on Global Encoding Vectors (GEVs), the proposed scheme offers two significant pri- vacy-preserving features, packet flow untraceability and message content confidentiality, for efficiently thwarting the traffic analysis attacks. Moreover, the proposed scheme keeps the random coding feature, and each sink can recover the source packets by inverting the GEVs with a very high probability. Theoretical analysis and simulative evaluation demonstrate the validity and efficiency of the proposed scheme.
