PIR array codes: the optimality of Blackburn-Etzion construction
Chen Wang, Yiwei Zhang · 2023
The PIR (Private information retrieval) array code is as an array version of the PIR codes proposed by Fazeli et al., and both codes aim at designing distributed storage systems with m servers which can implement classical k-PIR protocols while reducing the storage overhead. The central problem in PIR array codes is to maximize k/m, known as the virtual server rate. Blackburn and Etzion provided an asymptotically optimal construction and it has been conjectured to be exactly optimal. We provide a new upper bound of the virtual server rate by linear programming, indicating the optimality of Blackburn-Etzion construction for a wide range of parameters. Besides, we give a general construction of PIR array codes with much fewer servers, with a slight sacrifice on the virtual server rate.