Cryptology ePrint Archive: Report 2016/216

Fair mPSI and mPSI-CA: Efficient Constructions in Prime Order Groups with Security in the Standard Model against Malicious Adversary

Sumit Kumar Debnath and Ratna Dutta

Abstract: In this paper, we propose a construction of fair and efficient mutual Private Set Intersection (mPSI) with linear communication and computation complexities, where the underlying group is of prime order. The main tools in our approach include: (i) ElGamal and Distributed ElGamal Cryptosystems as multiplicatively Homomorphic encryptions, (ii) Cramer-Shoup Cryptosystem as Verifiable encryption. Our mPSI is secure in standard model against malicious parties under Decisional Diffie-Hellman (DDH) assumption. Fairness is achieved using an off-line semi-trusted arbiter. Further, we extend our mPSI to mutual Private Set Intersection Cardinality (mPSI-CA) retaining all the security properties of mPSI. More interestingly, our mPSI-CA is the first fair mPSI-CA with linear complexity.

Category / Keywords: public-key cryptography / mPSI, mPSI-CA, malicious adversary, fairness, semi-trusted arbiter

Date: received 29 Feb 2016

Contact author: sd iitkgp at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160229:213311 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]