Vayur Shanbhag supervised by Prof. Prasad Krishnan received his Master of Science – Dual Degree in Electronics & Communication Engineering (ECD). Here’s a summary of his research work on Minimal Subpacketization Schemes for Private Information Retrieval over Graph-based Replication Systems
The classical setting of private information retrieval (PIR) involves the retrieval of one desired message by a client, from a library of K messages stored across N distributed servers, without revealing the identity of the desired file from any particular server. In graph-based replication, the storage configuration is described by a (simple, undirected) graph with N vertices and K edges, where the edges denote the files and the nodes denote the servers. Each edge corresponds to a single distinct file, stored exactly in the two servers indexed by the vertices that are its end points. A query-response protocol between the client and the servers which enforces (a) the client is able to retrieve his desired file and (b) the identity of the desired file is not revealed to any individual server constitutes a valid PIR scheme. Such protocols involve utilizing private randomness at the client, which enables the masking of the index of the desired file from the server.
The rate of PIR for a given storage scenario is the ratio of the number of symbols in a file, to the number of symbols downloaded from all servers by the client for successful recovery of the desired file. The optimal (largest) rate of PIR for a given setting is known as the PIR capacity. Prior work in high-rate PIR for graph-based systems typically require large subpacketization (which indicates the number of parts each file has to be divided into, indicating the complexity of the scheme). A good number of these schemes are fixed-download schemes, i.e., they have the property that the number of bits downloaded from each server remains unchanged, irrespective of the query realization. In this thesis, we present four high-rate PIR schemes for graph-based storage systems.
• A unit-subpacketization (which is minimal possible) variable-download scheme on star graphs.
• A fixed-download scheme on star graphs.
• A variable-download scheme for general graphs.
• A fixed-download scheme for general graphs.
The fixed-download scheme for general graphs is obtained from the variable-download scheme, via a generic method of transformation, known from literature.
Our variable-download PIR scheme on star graphs is the first scheme in the literature that employs unit subpacketization (L = 1) while also having orderwise optimal rate. Our PIR schemes for general graphs use a decomposition of the graph via independent sets. They achieve rates lower than prior schemes for the complete graph, however they can achieve higher rates than previously known for some specific graph classes.
August 2026