Private Two-Party Set Intersection Protocol in Rational Model

Atsuko Miyaji¹and Mohammad Shahriar Rahman^2*

¹School of Information Science,

Japan Advanced Institute of Science and Technology,

Ishikawa, Japan.

miyaji@jaist.ac.jp

²Department of Computer Science and Engineering,

University of Asia Pacific,

Dhaka, Bangladesh.

shahriar.rahman@uap-bd.edu

Abstract

Many data mining algorithms use privacy preserving set intersection operations. Private set operations

have considered semi-honest and malicious adversarial models in cryptographic settings.

Protocols in semi-honest model, requiring light computations, provide weak security. Protocols in

malicious model guarantee strong security at the price of expensive computations like homomorphic

encryption and zero-knowledge proof. However, practical implementations require robust and

efficient protocols. In this paper, we build efficient and private set intersection avoiding the use of

expensive tools like homomorphic encryption and zero-knowledge proof. Our proposed set intersection

protocol is constructed in game-theoretic model. In our model, the parties are viewed as rational

whereby they are assumed (only) to act in their self-interest. Our protocol satisfies computational

Nash equilibrium.

Keywords: Privacy, Set Intersection, Rational Cryptography, Computational Nash Equilibrium

*Corresponding author: Dept of Computer Science and Engineering, University of Asia Pacific,

House 52/1, Road 4/A, Dhanmondi, Dhaka-1209, Bangladesh,

Tel: +88-01742092172