Paper 2024/969

Probabilistic Attacks and Enhanced Security for "Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF"

Zhuang Shan, School of Mathematics and Statistics, Xidian University, Xi’an 710126, China
Leyou Zhang, School of Mathematics and Statistics, Xidian University, Xi’an 710126, China
Qing Wu, School of Automation, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
Qiqi Lai, School of Computer Science, Shaanxi Normal University, Xi’an, China
Abstract

Privacy Set Intersection (PSI) has been an important research topic within privacy computation. Its main function is to allow two parties to compute the intersection of their private sets without revealing any other private information. Therefore, PSI can be applied to various real-world scenarios. Chase and Miao presented an impressive construction ``Private set intersection in the Internet setting from lightweight oblivious prf'' (CM20 for short) at Crypto 2020, highlighting its convenient structure and optimal communication cost. However, it does have some security vulnerabilities. Let be the privacy set of user , be the privacy set of user . The CM20 protocol uses a pseudorandom function (PRF) to encrypt the privacy of into and the privacy of into , as . It then sends random data to user and random data to user using a random oblivious transfer technique. User computes and sends to user , and user uses and to re-encrypt . Repeat this until re-encrypts all the privacy in all the privacy sets , packages them up and sends them to , who completes the privacy set intersection. However, if an adversary obtains and by any means, they can recover the PRF's encryption of the user's privacy, and the recovery process is non-trivial. This significantly weakens the security of the CM20 protocol. In this paper, we make three main contributions. First, based on the above analysis, we present a method for attacking CM20, called {\em probabilistic attacks}. This attack is based on estimating and analysing the frequency distribution of the encrypted data from the PRF and the probability distribution of the original private data, and determining the relationship between the two. Although not 100\% effective, this method of attack poses a significant threat to the security of user data. Secondly, we introduce a new tool called the {\em perturbed pseudorandom generator} (PPRG). We show that the PPRG can overcome probabilistic attacks by replacing the random oblivious transfer and one of the hash functions (originally there were two) in CM20. Finally, we provide a dedicated indistinguishability against chosen-plaintext attack (IND-CPA) security model for this PSI protocol. The efficiency analysis shows that the proposed PSI is comparable to CM20's PSI, whether on a PC, MAC, pad or mobile phone.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
MPC; PSI; Pseudorandom generator
Contact author(s)
arcsec30 @ 163 com
lyzhang @ mail xidian edu cn
History
2025-01-05: revised
2024-06-16: received
See all versions
Short URL
https://ia.cr/2024/969
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/969,
      author = {Zhuang Shan and Leyou Zhang and Qing Wu and Qiqi Lai},
      title = {Probabilistic Attacks and Enhanced Security for "Private Set Intersection in the Internet Setting from Lightweight Oblivious {PRF}"},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/969},
      year = {2024},
      url = {https://eprint.iacr.org/2024/969}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.