Optimizing Leaky Private Information Retrieval Codes to Achieve O(log K) Leakage Ratio Exponent

Summary

This paper studies leaky private information retrieval (L-PIR), where privacy leakage is measured by a pure differential privacy parameter called the leakage ratio exponent. The authors show that the active pure-DP constraints couple adjacent Hamming-weight layers of the random key, so the problem reduces to a layered optimization whose optimum is geometric across layers, requiring only cyclic permutations and assigning higher probabilities to lower-Hamming-weight keys. This yields an O(log K) leakage ratio exponent at fixed download cost D, improving on the previous Θ(K) exponent from prior work.