Journal of Discrete Mathematical Sciences and Cryptography

Secure Set Intersection in the Presence of a Rational Adversary

Zhonghong Sun, Lirong Qiu

Published Jul 4, 2014• 0 citations

Abstract

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.

DOI: 10.1080/09720529.2014.950063

Related papers

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, 20094 citations

Rational Secret Sharing Information -- Theoretically Secure against Adaptive Adversaries

Yang Yu, Zhanfei Zhou

Most rational secret sharing protocols aim to achieve a more appealing equilibrium or resist adversaries. However, all previous protocols achieve resilience against irrational adversaries at the cost of inducing a weak guarantee of Nash equilibrium surviving iterated deletion, which has been proved weaker than strict Nash equilibrium. Moreover, they achieve equilibrium in a computational way based on the computational limitations of adversaries. In this paper, we design two unconditionally secure rational (t, n) secret sharing protocols. Contrary to prior works, our protocols induce an enhanced notion of strict equilibrium with respect to adversary structure A, and resist the computationally unbounded and adaptive adversary without using cryptographic primitives. Our protocols achieve stronger stability, since rational players have an incentive not to deviate no matter how the adversary behaves, and they are immune to the backward induction. Our protocols are secure against the adversary corrupting less than [n/3] players and the adversary corrupting less than [n/2]-1 players respectively. Both of them achieve utility independence.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)Jul 1, 20130 citations

Rational Multiparty Computation

John Ross Wallrabenstein

The field of rational cryptography considers the design of cryptographic protocols in the presence of rational agents seeking to maximize local utility functions. This departs from the standard secure multiparty computation setting, where players are assumed to be either honest or malicious. We detail the construction of both a two-party and a multiparty game theoretic framework for constructing rational cryptographic protocols. Our framework specifies the utility function assumptions necessary to realize the privacy, correctness, and fairness guarantees for protocols. We demonstrate that our framework correctly models cryptographic protocols, such as rational secret sharing, where existing work considers equilibrium concepts that yield unreasonable equilibria. Similarly, we demonstrate that cryptography may be applied to the game theoretic domain, constructing an auction market not realizable in the original formulation. Additionally, we demonstrate that modeling players as rational agents allows us to design a protocol that destabilizes coalitions. Thus, we establish a mutual benefit from combining the two fields, while demonstrating the applicability of our framework to real-world market environments. We also give an application of game theory to adversarial interactions where cryptography is not necessary. Specifically, we consider adversarial machine learning, where the adversary is rational and reacts to the presence of a data miner. We give a general extension to classification algorithms that returns greater expected utility for the data miner than existing classification methods.

Jan 1, 20141 citation

Rational Protocol Design: Cryptography Against Incentive-driven Adversaries

Juan A. Garay, Björn Tackmann, Jonathan Katz +2 more

Existing work on “rational cryptographic protocols ” treats each party (or coalition of parties) running the protocol as a selfish agent trying to maximize its utility. In this work we propose a fundamentally different approach that is better suited to modeling a protocol under attack from an external entity. Specifically, we consider a two-party game between an protocol designer and an external attacker. The goal of the attacker is to break security properties such as correctness or privacy, possibly by corrupting protocol participants; the goal of the protocol designer is to prevent the attacker from succeeding. We lay the theoretical groundwork for a study of cryptographic protocol design in this setting by providing a methodology for defining the problem within the traditional simulation paradigm. Our framework provides ways of reasoning about important cryptographic concepts (e.g., adaptive corruptions or attacks on communication resources) not handled by previous game-theoretic treatments of cryptography. We also prove composition theorems that—for the first time—provide a sound way to design rational protocols assuming “ideal communication resources ” (e.g., broadcast or authenticated channels) and then instantiate these resources using standard cryptographic tools. Finally, we investigate the problem of secure function evaluation in our framework, where the attacker has to pay for each party it corrupts. Our results demonstrate how knowledge of the attacker’s incentives can be used to circumvent known impossibility results in this setting. 1

Oct 28, 20134 citations

Constructions of Truly Practical Secure Protocols using Standard Smartcards.

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

Jan 1, 20090 citations

Rational Protocol Design: Cryptography against Incentive-Driven Adversaries

Juan A. Garay, Jonathan I. Katz, Ueli M. Maurer +2 more

Existing work on "rational cryptographic protocols" treats each party (or coalition of parties) running the protocol as a selfish agent trying to maximize its utility. In this work we propose a fundamentally different approach that is better suited to modeling a protocol under attack from an external entity. Specifically, we consider a two-party game between an protocol designer and an external attacker. The goal of the attacker is to break security properties such as correctness or privacy, possibly by corrupting protocol participants; the goal of the protocol designer is to prevent the attacker from succeeding. We lay the theoretical groundwork for a study of cryptographic protocol design in this setting by providing a methodology for defining the problem within the traditional simulation paradigm. Our framework provides ways of reasoning about important cryptographic concepts (e.g., adaptive corruptions or attacks on communication resources) not handled by previous game-theoretic treatments of cryptography. We also prove composition theorems that-for the first time-provide a sound way to design rational protocols assuming "ideal communication resources" (such as broadcast or authenticated channels) and then instantiate these resources using standard cryptographic tools. Finally, we investigate the problem of secure function evaluation in our framework, where the attacker has to pay for each party it corrupts. Our results demonstrate how knowledge of the attacker's incentives can be used to circumvent known impossibility results in this setting.

Annual Symposium on Foundations of Computer ScienceOct 1, 201385 citations