Double Blind T-Private Information Retrieval
Yuxiang Lu, Zhuqing Jia, Syed A. Jafar · IEEE Journal on Selected Areas in Information Theory · 2021
Double blind T-private information retrieval (DB-TPIR) enables two users, each of whom specifies an index ( θ1, θ2, resp.), to efficiently retrieve a message W(θ1,θ2) labeled by the two indices, from a set of N servers that store all messages W(k1,k2), k1∈ {1,2,..., K1}, k2∈ {1,2,..., K2}, such that the two users' indices are kept private from any set of up to T1,T2colluding 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 ( T1, T2,..., TM), and arbitrary level of security ( X) of data storage, so that the message W(θ1,θ2,..., θM) can be efficiently retrieved while the stored data is held secure against collusion among up to X colluding servers, the mthuser's index is private against collusion among up to Tmservers, and each user's index θmis private from all other users. The general scheme relies on a tensor-product based extension of cross-subspace alignment and retrieves 1-(X+T1+...+TM)/N bits of desired message per bit of download.