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•69 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•25 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

Two-party Private Set Intersection with an Untrusted Third Party

Phi Hung Le, Samuel Ranellucci, Steven Gordon

We construct new protocols for two parties to securely compute on the items in their intersection. Our protocols make use of an untrusted third party that has no input. The use of this party allows us to construct highly efficient protocols that are secure against a single malicious corruption.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 6, 2019•41 citations

Efficient Secure Computation for Real-world Settings and Security Models

Alex J. Malozemoff

Secure computation involves multiple parties computing a common function while keeping their inputs private, and is a growing field of cryptography due to its potential for maintaining privacy guarantees in real-world applications. However, current secure computation protocols are not yet efficient enough to be used in practice. We argue that this is due to much of the research effort being focused on generality rather than specificity. Namely, current research tends to focus on constructing and improving protocols for the strongest notions of security or for an arbitrary number of parties. However, in real-world deployments, these security notions are often too strong, or the number of parties running a protocol would be smaller. In this thesis we make several steps towards bridging the efficiency gap of secure computation by focusing on constructing efficient protocols for specific real-world settings and security models. In particular, we make the following four contributions: - We show an efficient (when amortized over multiple runs) maliciously secure two-party secure computation (2PC) protocol in the multiple-execution setting, where the same function is computed multiple times by the same pair of parties. - We improve the efficiency of 2PC protocols in the publicly verifiable covert security model, where a party can cheat with some probability but if it gets caught then the honest party obtains a certificate proving that the given party cheated. - We show how to optimize existing 2PC protocols when the function to be computed includes predicate checks on its inputs. - We demonstrate an efficient maliciously secure protocol in the three-party setting.

•Jan 1, 2016•0 citations

Secure Set Intersection in the Presence of a Rational Adversary

Zhonghong Sun, Lirong Qiu

Secure set intersection protocols confronting with covert adversary are efficient and guarantee correctness with a non-negligible probability, which is smaller than 1. However, they are not desirable when correctness is required to be achieved with probability 1, since correctness may be broken when the covert adversary successfully cheats. In order to get desirable result about correctness, we introduce a rational adversary instead of a covert adversary into the secure set-intersection protocol using smartcard tokens. The rational adversary has the same “deterrence factor” as a covert adversary but additionally has utilities defined as in the game theory. The main target of the rational adversary is to maximize his utilities by cheating in the protocol. Note that cheating does not bring him optimal utility, thus he has no incentives to cheat. We prove that given proper utilities, the strategy not to cheat induces Nash equilibrium for the rational adversary. Therefore, correctness can be guaranteed with probability 1. Furthermore, our protocol has the same round complexity as the secure setintersection protocol using smartcard tokens since the introduction of a rational adversary does not increase the round complexity.

Journal of Discrete Mathematical Sciences and Cryptography•Jul 4, 2014•0 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.
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.
Secure computation involves multiple parties computing a common function while keeping their inputs private, and is a growing field of cryptography due to its potential for maintaining privacy guarantees in real-world applications. However, current secure computation protocols are not yet efficient enough to be used in practice. We argue that this is due to much of the research effort being focused on generality rather than specificity. Namely, current research tends to focus on constructing and improving protocols for the strongest notions of security or for an arbitrary number of parties. However, in real-world deployments, these security notions are often too strong, or the number of parties running a protocol would be smaller. In this thesis we make several steps towards bridging the efficiency gap of secure computation by focusing on constructing efficient protocols for specific real-world settings and security models. In particular, we make the following four contributions: - We show an efficient (when amortized over multiple runs) maliciously secure two-party secure computation (2PC) protocol in the multiple-execution setting, where the same function is computed multiple times by the same pair of parties. - We improve the efficiency of 2PC protocols in the publicly verifiable covert security model, where a party can cheat with some probability but if it gets caught then the honest party obtains a certificate proving that the given party cheated. - We show how to optimize existing 2PC protocols when the function to be computed includes predicate checks on its inputs. - We demonstrate an efficient maliciously secure protocol in the three-party setting.
Secure set intersection protocols confronting with covert adversary are efficient and guarantee correctness with a non-negligible probability, which is smaller than 1. However, they are not desirable when correctness is required to be achieved with probability 1, since correctness may be broken when the covert adversary successfully cheats. In order to get desirable result about correctness, we introduce a rational adversary instead of a covert adversary into the secure set-intersection protocol using smartcard tokens. The rational adversary has the same “deterrence factor” as a covert adversary but additionally has utilities defined as in the game theory. The main target of the rational adversary is to maximize his utilities by cheating in the protocol. Note that cheating does not bring him optimal utility, thus he has no incentives to cheat. We prove that given proper utilities, the strategy not to cheat induces Nash equilibrium for the rational adversary. Therefore, correctness can be guaranteed with probability 1. Furthermore, our protocol has the same round complexity as the secure setintersection protocol using smartcard tokens since the introduction of a rational adversary does not increase the round complexity.