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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Private information retrieval (PIR) enables a user to retrieve a specific data item from a database, replicated among one or more servers, while hiding from each server the identity of the retrieved item. This problem was suggested by Chor et al., and since then efficient protocols with sub-linear communication were suggested. However, in all these protocols the servers' computation for each retrievalis at least linear in the size of entire database, even if the user requires just one bit.  In this paper, we study the computational complexity of PIR. We show that in the standard PIR model, where the servers hold only the database, linear computation cannot be avoided. To overcome this problem we propose the modelof PIR with preprocessing: Before the execution of the protocol each server may compute and store polynomially-many information bits regarding the database; later on, this information should enable the servers to answer each query of the user with more efficient computation. We demonstrate that preprocessing can save work. In particular, we construct, for any constant k ≥ 2, a k-server protocolwith O(n1/(2k-1)) communication and O(n/log2k-2n) work, and for any constants k ≥ 2 and Ɛ > 0 a k-server protocol with O(n1/k+Ɛ) communication and work. We also prove some lower bounds on the work of the servers when they are only allowed to store a small number of extra bits. Finally, we present some alternative approaches to saving computation, by batching queries or by moving most of the computation to an off-line stage.

Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing