UC Irvine

Several prominent privacy laws require service providers to let consumers request access, correction, or deletion of their personal data. Compliance with such laws necessitates the verification of consumers' identities. This is not a problem for consumers who already have an account with a service provider since they can authenticate themselves via a successful account log-in, e.g., using username/password, or two-factor authentication. However, there are no such methods for accountless consumers, even though service providers (e.g., data aggregators) routinely accumulate data on consumers without accounts. Currently, accountless consumers are asked to share Personally Identifiable Information (PII) with service providers, which is privacy-invasive.

This paper proposes \textit{\piva: a \pivatextunderline} using \textit{Private List Intersection (PLI)} and its variants. First, we introduce PLI, a close relative of \textit{private set intersection (PSI)}, a well-known cryptographic primitive that allows two or more mutually distrusting parties to compute the intersection of their private input sets. PLI takes advantage of the (ordered and fixed) list structure of the parties' private sets. As a result, PLI can be made more efficient than PSI. We also explore PLI variants: PLI-cardinality (PLI-CA), threshold-PLI (t-PLI), and threshold-PLI-cardinality (t-PLI-CA), all of which yield less information than PLI. These variants are progressively better suited for addressing the accountless consumer authentication problem. We prototype \piva and evaluate its performance, using regular PSI and garbled circuits as the basis for comparison. Results show that our PLI and PLI-CA constructions are more efficient than a garbled circuit approach, in both computation and communication overheads. While the garbled circuit-based implementations of t-PLI and t-PLI-CA have a faster execution time, our constructions greatly outperform garbled circuits in terms of bandwidth, with the garbled circuit-based implementation of t-PLI requiring $16\times$ the bandwidth of our construction. Additionally, the constructed t-PLI protocol is faster than existing threshold PSI protocols, taking advantage of the ordered property of lists. All implementation and evaluation are available in \cite{anon_piva}.