Breaking two PSI-CA protocols in polynomial time

Yang Tan; Bo Lv

Paper 2023/1706

Breaking two PSI-CA protocols in polynomial time

Yang Tan

Bo Lv, Huizhou University

Abstract

Private Set Intersection Cardinality(PSI-CA) is a type of secure two-party computation. It enables two parties, each holding a private set, to jointly compute the cardinality of their intersection without revealing any other private information about their respective sets. In this paper, we manage to break two PSI-CA protocols by recovering the specific intersection items in polynomial time. Among them, the PSI-CA protocol proposed by De Cristofaro et al. in 2012 is the most popular PSI-CA protocol based on the Google Scholar search results and it is still deemed one of the most efficient PSI-CA protocols. In this paper, we also propose several solutions to these protocols' security problems.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: PSI-CA PSI DDH Bloom Filter
Contact author(s): 7853yang @ gmail com
lvbo @ hzu edu cn
History: 2023-11-06: approved; 2023-11-03: received; See all versions
Short URL: https://ia.cr/2023/1706
License: CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2023/1706,
      author = {Yang Tan and Bo Lv},
      title = {Breaking two {PSI}-{CA} protocols in polynomial time},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1706},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1706}
}