Multi-User Blind Symmetric Private Information Retrieval From Coded Servers

The problem of Multi-user Blind X-secure T -colluding Symmetric Private Information Retrieval from Maximum Distance Separable (MDS) coded storage system with B Byzantine and U unresponsive servers (U-B-MDS-MB- XTSPIR) is studied in this paper. Specifically, a database consisting of multiple files, each labeled by M indices, is stored at the distributed system with N servers according to (N, K + X) MDS codes over F-q such that any group of up to X colluding servers learn nothing about the data files. There are M users, in which each user m, m = 1,..., M privately selects an index theta(m) and wishes to jointly retrieve the file specified by the M users' indices (theta(1),..., theta(M)) from the storage system, while keeping its index theta(m) private from any Tm colluding servers, where there exists B Byzantine servers that can send arbitrary responses maliciously to confuse the users retrieving the desired file and U unresponsive servers that will not respond any message at all. In addition, each user must not learn information about the other users' indices and the database more than the desired file. An U-B-MDS-MB-XTSPIR scheme is constructed based on Lagrange encoding. The scheme achieves a retrieval rate of 1 - K+X+T-1+...+T-M+2B-1/N-U with secrecy rate K+X+T-1+...+T-M - 1/N-( K+X+T-1+...+T-M+2B+U-1) on the finite field of size q >= N+ max{K, N-(K+X+T-1+...+T-M+2B+ U-1)} for any number of

Automated summary

This paper studies the problem of Multi-user Blind X-secure T-colluding Symmetric Private Information Retrieval from a Maximum Distance Separable (MDS) coded storage system. A scheme based on Lagrange encoding is proposed to achieve efficient retrieval and secrecy in the distributed system.