Paper 2024/215

Batch PIR and Labeled PSI with Oblivious Ciphertext Compression

Alexander Bienstock, New York University
Sarvar Patel, Google (United States)
Joon Young Seo, Google (United States)
Kevin Yeo, Google (United States), Columbia University
Abstract

In this paper, we study two problems: oblivious compression and decompression of ciphertexts. In oblivious compression, a server holds a set of ciphertexts with a subset of encryptions of zeroes whose positions are only known to the client. The goal is for the server to effectively compress the ciphertexts obliviously, while preserving the non-zero plaintexts and without learning the plaintext values. For oblivious decompression, the client, instead, succinctly encodes a sequence of plaintexts such that the server may decode encryptions of all plaintexts value, but the zeroes may be replaced with arbitrary values. We present solutions to both problems that construct lossless compressions only 5% more than the optimal minimum using only additive homomorphism. The crux of both algorithms involve embedding ciphertexts as random linear systems that are efficiently solvable. Using our compression schemes, we obtain state-of-the-art schemes for batch private information retrieval (PIR) where a client wishes to privately retrieve multiple entries from a server-held database in one query. We show that our compression schemes may be used to reduce communication by up to 30% for batch PIR in both the single- and two-server settings. Additionally, we study labeled private set intersection (PSI) in the unbalanced setting where one party's set is significantly smaller than the other party's set and each entry has associated data. By utilizing our novel compression algorithm, we present a protocol with 65-88% reduction in communication with comparable computation compared to prior works.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2024
Keywords
Private Information RetrievalCiphertext CompressionPrivate Set Intersection
Contact author(s)
abienstock @ cs nyu edu
sarvar @ google com
jyseo @ google com
kwlyeo @ google com
History
2024-04-30: revised
2024-02-12: received
See all versions
Short URL
https://ia.cr/2024/215
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/215,
      author = {Alexander Bienstock and Sarvar Patel and Joon Young Seo and Kevin Yeo},
      title = {Batch {PIR} and Labeled {PSI} with Oblivious Ciphertext Compression},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/215},
      year = {2024},
      url = {https://eprint.iacr.org/2024/215}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.