Welcome to the resource topic for 2024/1885
Title:
Improved PIR Schemes using Matching Vectors and Derivatives
Authors: Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
Abstract:In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector based PIRs of Yekhanin and Efremenko. Previously such a combination was achieved in an ingenious way by Dvir and Gopi, using polynomials and derivatives over certain exotic rings, en route to their fundamental result giving the first 2-server PIR with subpolynomial communication.
Our improved PIRs are based on two ingredients:
• We develop a new and direct approach to combine derivatives with Matching Vector based PIRs.
This approach is much simpler than that of Dvir-Gopi: it works over the same field as the original PIRs, and only uses elementary properties of polynomials and derivatives.
• A key subproblem that arises in the above approach is a higher-order polynomial interpolation problem. We show how “sparse S-decoding polynomials”, a powerful tool from the original constructions of Matching Vector PIRs, can be used to solve this higher-order polynomial interpolation problem using surprisingly few higer-order evaluations.
Using the known sparse S-decoding polynomials in combination with our
ideas leads to our improved PIRs. Notably, we get a 3-server PIR scheme with communication 2^{O^\sim( (\log n)^{1/3}) }, improving upon the previously best known communication of 2^{O^\sim( \sqrt{\log n})} due to Efremenko.
ePrint: https://eprint.iacr.org/2024/1885
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .