Degree Tables for Private Information Retrieval
Fatemeh Kazemi, Ningze Wang, Rafael G. L. D’Oliveira, Alex Sprintson · 2022
We present a general technique for constructing schemes for a broad class of private information retrieval (PIR) problems. Our technique is inspired by polynomial code constructions utilized for secure distributed matrix multiplication and is applicable to a broad range of PIR problems. We showcase our technique by reducing the problem of scheme constructions for PIR from coded storage and colluding servers to a combinatorial problem of designing a degree table that needs to satisfy certain properties. We then present simple schemes for PIR from coded storage and colluding servers which, for certain cases, achieve the best known rates in the asymptotic regime. Our results show that the degree table is a powerful tool for constructing PIR codes for a variety of settings of practical interest.