English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Private information retrieval (PIR) protocols allow a user to retrieve a dataitem from a database without revealing any information about the identity ofthe item being retrieved. Specifically, in information-theoretic $k$-serverPIR, the database is replicated among $k$ non-communicating servers, and eachserver learns nothing about the item retrieved by the user. The cost of PIRprotocols is usually measured in terms of their communication complexity, whichis the total number of bits exchanged between the user and the servers, andstorage overhead, which is the ratio between the total number of bits stored onall the servers and the number of bits in the database. Since single-serverinformation-theoretic PIR is impossible, the storage overhead of all existingPIR protocols is at least $2$.  In this work, we show that information-theoretic PIR can be achieved withstorage overhead arbitrarily close to the optimal value of $1$, withoutsacrificing the communication complexity. Specifically, we prove that all known$k$-server PIR protocols can be efficiently emulated, while preserving bothprivacy and communication complexity but significantly reducing the storageoverhead. To this end, we distribute the $n$ bits of the database among $s+r$servers, each storing $n/s$ coded bits (rather than replicas). For every fixed$k$, the resulting storage overhead $(s+r)/s$ approaches $1$ as $s$ grows;explicitly we have $r\le k\sqrt{s}(1+o(1))$. Moreover, in the special case $k =2$, the storage overhead is only $1 + \frac{1}{s}$. In order to achieve theseresults, we introduce and study a new kind of binary linear codes, called here$k$-server PIR codes. We then show how such codes can be constructed, and weestablish several bounds on the parameters of $k$-server PIR codes. Finally, webriefly discuss extensions of our results to nonbinary alphabets, to robustPIR, and to $t$-private PIR.

PIR with Low Storage Overhead: Coding instead of Replication