Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective

2019/12/31 by Wang, Zhusheng, Banawan, Karim, Ulukus, Sennur · 3 citations
#Cryptography and Security (cs.CR) #Databases (cs.DB) #FOS: Computer and information sciences #FOS: Electrical engineering #Information Theory (cs.IT) #Signal Processing (eess.SP) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.1912.13501

Abstract

We study the problem of private set intersection (PSI). In this problem, there are two entities E_i, for i=1, 2, each storing a set P_i, whose elements are picked from a finite field \mathbbF_K, on N_i replicated and non-colluding databases. It is required to determine the set intersection P₁ ∩ P₂ without leaking any information about the remaining elements to the other entity with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR, C_MM-SPIR. We show that with K messages, N databases, and the size of the desired message set P, the exact capacity of MM-SPIR is C_MM-SPIR = 1 - (1)/(N) when P ≤ K-1, provided that the entropy of the common randomness S satisfies H(S) ≥ (P)/(N-1) per desired symbol. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme that builds on the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any P, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for MM-SPIR, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is min\\lceil(P₁ N₂)/(N₂-1)\rceil, \lceil(P₂ N₁)/(N₁-1)\rceil\, where P_i is the cardinality of set P_i

Cited by

• Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems
• Multi-Agent Distributed Optimization With Feasible Set Privacy
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems

Related

• Multi-Party Private Set Intersection: An Information-Theoretic Approach
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• The Capacity of Symmetric Private Information Retrieval
• Symmetric Private Information Retrieval with User-Side Common Randomness
• The Capacity of Symmetric Private Information Retrieval under Arbitrary Collusion and Eavesdropping Patterns