Double Blind $T$-Private Information Retrieval

Abstract

Double blind $T$-private information retrieval (DB-TPIR) enables two users, each of whom specifies an index (${\theta }_1,{\theta }_2$, resp.), to efficiently retrieve a message $W({\theta }_1,{\theta }_2)$ labeled by the two indices, from a set of $N$ servers that store all messages $W(k_1,k_2),k_1\in \{1,2,\cdots ,K_1\},k_2\in \{1,2,\cdots ,K_2\}$, such that the two users' indices are kept private from any set of up to $T_1,T_2$ colluding servers, respectively, as well as from each other. A DB-TPIR scheme based on cross-subspace alignment is proposed in this paper, and shown to be capacity-achieving in the asymptotic setting of large number of messages and bounded latency. The scheme is then extended to $M$-way blind $X$-secure $T$-private information retrieval (MB-XS-TPIR) with multiple ($M$) indices, each belonging to a different user, arbitrary privacy levels for each index ($T_1,T_2,\cdots ,T_M$), and arbitrary level of security ($X$) of data storage, so that the message $W({\theta }_1,{\theta }_2,\cdots ,{\theta }_M)$ can be efficiently retrieved while the stored data is held secure against collusion among up to $X$ colluding servers, the $m^{th}$ user's index is private against collusion among up to $T_m$ servers, and each user's index ${\theta }_m$ is private from all other users. The general scheme relies on a tensor-product based extension of cross-subspace alignment and retrieves $1-(X+T_1+\cdots +T_M)/N$ bits of desired message per bit of download.

arXiv commentAccepted for publication in IEEE Journal on Selected Areas in Information Theory (JSAIT)

References in corpus (17)

• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Private Information Retrieval from Coded Databases with Colluding Servers
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Private Information Retrieval for Coded Storage
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective
• The Capacity of $T$-Private Information Retrieval with Private Side Information
• The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases
• $X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers
• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• Private Function Computation for Noncolluding Coded Databases
• Multi-Server Weakly-Private Information Retrieval
• New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
• Private Information Retrieval from Heterogeneous Uncoded Storage Constrained Databases with Reduced Sub-Messages
• The Capacity of Private Information Retrieval with Eavesdroppers
• The $\epsilon$-error Capacity of Symmetric PIR with Byzantine Adversaries