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

Constructions of Truly Practical Secure Protocols using Standard Smartcards.

Carmit Hazay, Yehuda Lindell

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full simulation-based security in the presence of malicious adversaries, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other. This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.

Related papers

Constructions of truly practical secure protocols using standardsmartcards

Carmit Hazay, Yehuda Lindell

In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full simulation-based security in the presence of malicious adversaries, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other (where the latter can be parallelized to further reduce the time). This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.

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

Efficient Set Operations in the Presence of Malicious Adversaries.

Carmit Hazay, Kobbi Nissim B

We revisit the problem of constructing efficient secure two-party protocols for the problems of setintersection and set-union, focusing on the model of malicious parties. Our main results are constantround protocols that exhibit linear communication and a (practically) linear number of exponentiations with simulation based security. In the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC-secure, and we discuss how to perform these transformations. Keywords: Secure two-party computation, Simulation-based security, Set-intersection, Set-union, Oblivious pseudorandom function evaluation.

•Jan 1, 2009•2 citations

Efficient Oblivious Polynomial Evaluation with Simulation-Based Security.

Carmit Hazay, Yehuda Lindell

The study of secure multiparty computation has yielded powerful feasibility results showing that any efficient functionality can be securely computed in the presence of malicious adversaries. Despite this, there are few problems of specific interest for which we have highly efficient protocols that are secure in the presence of malicious adversaries under full simulation based definitions (following the ideal/real model paradigm). Due to the difficulties of constructing such protocols, many researchers have resorted to weaker definitions of security and weaker adversary models. In this paper, we construct highly efficient protocols for the well-studied problem of oblivious polynomial evaluation. Our protocol is secure under standard cryptographic assumptions for the settings of malicious adversaries, and readily transform to protocols that are secure under universal composability and in the presence of covert adversaries. Our protocol is constant round and requires O(d · s) exponentiations, where d is the degree of the polynomial and s is a statistical security parameter (that should equal about 160 in practice).

•Jan 1, 2009•26 citations

Private set intersection: New generic constructions and feasibility results

Paolo D’Arco, María Isabel González Vasco, Ángel Luis Pérez del Pozo +2 more

In this paper we focus on protocols for private set intersection (PSI), through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage.In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.

Advances in Mathematics of Communications•Jan 1, 2017•3 citations

Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries.

Carmit Hazay, Yehuda Lindell

Abstract. 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. 1

•Jan 1, 2009•4 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
In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full simulation-based security in the presence of malicious adversaries, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other. This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.
In this paper we show that using standard smartcards it is possible to construct truly practical secure protocols for a variety of tasks. Our protocols achieve full simulation-based security in the presence of malicious adversaries, and can be run on very large inputs. We present protocols for secure set intersection, oblivious database search and more. We have also implemented our set intersection protocol in order to show that it is truly practical: on sets of size 30,000 elements takes 20 seconds for one party and 30 minutes for the other (where the latter can be parallelized to further reduce the time). This demonstrates that in settings where physical smartcards can be sent between parties (as in the case of private data mining tasks between security and governmental agencies), it is possible to use secure protocols with proven simulation-based security.
We revisit the problem of constructing efficient secure two-party protocols for the problems of setintersection and set-union, focusing on the model of malicious parties. Our main results are constantround protocols that exhibit linear communication and a (practically) linear number of exponentiations with simulation based security. In the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC-secure, and we discuss how to perform these transformations. Keywords: Secure two-party computation, Simulation-based security, Set-intersection, Set-union, Oblivious pseudorandom function evaluation.
The study of secure multiparty computation has yielded powerful feasibility results showing that any efficient functionality can be securely computed in the presence of malicious adversaries. Despite this, there are few problems of specific interest for which we have highly efficient protocols that are secure in the presence of malicious adversaries under full simulation based definitions (following the ideal/real model paradigm). Due to the difficulties of constructing such protocols, many researchers have resorted to weaker definitions of security and weaker adversary models. In this paper, we construct highly efficient protocols for the well-studied problem of oblivious polynomial evaluation. Our protocol is secure under standard cryptographic assumptions for the settings of malicious adversaries, and readily transform to protocols that are secure under universal composability and in the presence of covert adversaries. Our protocol is constant round and requires O(d · s) exponentiations, where d is the degree of the polynomial and s is a statistical security parameter (that should equal about 160 in practice).
In this paper we focus on protocols for private set intersection (PSI), through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage.In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.
Abstract. 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. 1
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