Paper 2025/1108

Laconic PSI on Authenticated Inputs and Applications

James Bartusek, New York University
Sanjam Garg, University of California, Berkeley
Abhishek Jain, Johns Hopkins University, NTT Basic Research Laboratories
Guru-Vamsi Policharla, University of California, Berkeley
Abstract

A common issue with using secure computation in practice is that its security does not place any restrictions on what an adversary can use as input in the protocol. In this work, we focus on the practically-motivated setting of (two-message, labeled) private set intersection (PSI), and advocate for a clean and versatile solution to this problem: PSI on authenticated inputs. Our central contributions are summarized as follows. - We formulate a novel definition of PSI on authenticated inputs that has the potential for use in several applications, from content moderation in end-to-end encrypted systems to watchlists in anonymous e-cash systems. - We design a concretely-efficient and laconic (i.e., the size of the receiver's message is independent of its set size) protocol for PSI on authenticated inputs. - We build on our PSI protocol to obtain the first laconic set pre-constrained group signature scheme, improving on that of Bartusek et al. (Eurocrypt 23). We also explore various optimizations to our basic protocol, including reducing the receiver's concrete run time, and a tradeoff between crs size and message size.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
bartusek james @ gmail com
sanjamg @ berkeley edu
abhishek @ cs jhu edu
guruvamsi policharla @ gmail com
History
2025-06-13: approved
2025-06-12: received
See all versions
Short URL
https://ia.cr/2025/1108
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2025/1108,
      author = {James Bartusek and Sanjam Garg and Abhishek Jain and Guru-Vamsi Policharla},
      title = {Laconic {PSI} on Authenticated Inputs and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1108},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1108}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.