Double Blind T-Private Information Retrieval
share
Double blind T-private information retrieval (DB-TPIR) enables two users, each of whom privately generates a random 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(k_1,k_2), k_1∈{1,2,⋯,K_1}, k_2∈{1,2,⋯,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-XSTPIR) with multiple (M) indices, each generated privately by a different user, arbitrary privacy levels for each index (T_1, T_2,⋯, T_M), 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 m^th user's index is private against collusion among up to T_m servers, and each user's index θ_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+⋯+T_M)/N bits of desired message per bit of download.
READ FULL TEXT