Emerging Trends in ICT Security: Chapter 15. Algebraic Approaches to a Network-Type Private Information Retrieval (Emerging Trends in Computer Science and Applied Computing)

We propose a network-type scheme of private information retrieval, presented as a modification of the conventional setup, where the user is replaced with two users, the user-sender and the user-receiver. As a result of communication, the user-receiver becomes informed about the bit located at a certain position of the database, owned by the servers. Each server receives a query from the user-sender that contains information about the position in a hidden form and the server cannot disclose this position. On the basis of the query and the database, each server forms the replica, which is then transmitted to the user-receiver. By combining replicas, the user-receiver decodes the retrieved bit. We present a simple algebraic scheme where the communication complexity and the computational complexity are expressed as functions of the logarithm of the database size. The approaches allow extensions to the one-server scheme, the multi-scheme with noisy replicas of a fixed number of servers, and the authentication of a certain fragment of the database.