Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials

Aparna Gupte, Seyoon Ragavan

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database…