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

This paper investigates reducing sub-packetization of capacity-achievingschemes for uncoded Storage Constrained Private Information Retrieval (SC-PIR)systems. In the SC-PIR system, a user aims to retrieve one out of $K$ filesfrom $N$ servers while revealing nothing about its identity to any individualserver, in which the $K$ files are stored at the $N$ servers in an uncoded formand each server can store up to $\mu K$ equivalent files, where $\mu$ is thenormalized storage capacity of each server. We first prove that there exists acapacity-achieving SC-PIR scheme for a given storage design if and only if allthe packets are stored exactly at $M\triangleq \mu N$ servers for $\mu$ suchthat $M=\mu N\in\{2,3,\ldots,N\}$. Then, the optimal sub-packetization forcapacity-achieving linear SC-PIR schemes is characterized as the solution to anoptimization problem, which is typically hard to solve because of involvingindicator functions. Moreover, a new notion of array called Storage DesignArray (SDA) is introduced for the SC-PIR system. With any given SDA, anassociated capacity-achieving SC-PIR scheme is constructed. Next, the SC-PIRschemes that have equal-size packets are investigated. Furthermore, the optimalequal-size sub-packetization among all capacity-achieving linear SC-PIR schemescharacterized by Woolsey et al. is proved to be $\frac{N(M-1)}{\gcd(N,M)}$.Finally, by allowing unequal size of packets, a greedy SDA construction isproposed, where the sub-packetization of the associated SC-PIR scheme is upperbounded by $\frac{N(M-1)}{\gcd(N,M)}$. Among all capacity-achieving linearSC-PIR schemes, the sub-packetization is optimal when $\min\{M,N-M\}|N$ or$M=N$, and within a multiplicative gap $\frac{\min\{M,N-M\}}{\gcd(N,M)}$ of theoptimal one otherwise. In particular, for the case $N=d\cdot M\pm1$ where$d\geq 2$, another SDA is constructed to obtain lower sub-packetization.

Capacity-Achieving Private Information Retrieval Schemes from Uncoded Storage Constrained Servers with Low Sub-packetization