Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Capacity of Quantum Private Information Retrieval from MDS-Coded and Colluding Servers
173
0
0.0
(
0
)
Added by
Matteo Allaix
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied. Two classes of QPIR, called stabilizer QPIR and dimension squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. The capacities of symmetric and non-symmetric QPIR with coded and colluding servers are proved to coincide, being double to their classical counterparts. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollanti et al. and the stabilizer QPIR scheme by Song et al. by employing (weakly) self-dual Reed--Solomon codes.
rate research
Read More
In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song emph{et al.} in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any $[n,k]$-MDS code and $t$-collusion with $t=n-k$. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts. Further, it is demonstrated how the protocol can adapted to achieve significantly higher retrieval rates from DSSs encoded with a locally repairable code (LRC) with disjoint repair groups, each of which is an MDS code.
We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from $N$ non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any $T$ databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when $K>T/textbf{gcd}(N,T)$ where $K$ is the total number of messages in the system and $textbf{gcd}(cdot,cdot)$ means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as $textbf{lcm}(N-T,T)$, where $textbf{lcm}(cdot,cdot)$ means the least common multiple. On the other hand, when $K$ is small, we show that it is in fact possible to design codes with a message size even smaller than $textbf{lcm}(N-T,T)$.
We consider information leakage to the user in private information retrieval (PIR) systems. Information leakage can be measured in terms of individual message leakage or total leakage. Individual message leakage, or simply individual leakage, is defined as the amount of information that the user can obtain on any individual message that is not being requested, and the total leakage is defined as the amount of information that the user can obtain about all the other messages except the one being requested. In this work, we characterize the tradeoff between the minimum download cost and the individual leakage, and that for the total leakage, respectively. New codes are proposed to achieve these optimal tradeoffs, which are also shown to be optimal in terms of the message size. We further characterize the optimal tradeoff between the minimum amount of common randomness and the total leakage. Moreover, we show that under individual leakage, common randomness is in fact unnecessary when there are more than two messages.
In a distributed storage system, private information retrieval (PIR) guarantees that a user retrieves one file from the system without revealing any information about the identity of its interested file to any individual server. In this paper, we investigate $(N,K,M)$ coded sever model of PIR, where each of $M$ files is distributed to the $N$ servers in the form of $(N,K)$ maximum distance separable (MDS) code for some $N>K$ and $M>1$. As a result, we propose a new capacity-achieving $(N,K,M)$ coded linear PIR scheme such that it can be implemented with file length $frac{K(N-K)}{gcd(N,K)}$, which is much smaller than the previous best result $Kbig(frac{N}{gcd(N,K)}big)^{M-1}$. Notably, among all the capacity-achieving coded linear PIR schemes, we show that the file length is optimal if $M>biglfloor frac{K}{gcd(N,K)}-frac{K}{N-K}bigrfloor+1$, and within a multiplicative gap $frac{K}{gcd(N,K)}$ of a lower bound on the minimum file length otherwise.
This work investigates a system where each user aims to retrieve a scalar linear function of the files of a library, which are Maximum Distance Separable coded and stored at multiple distributed servers. The system needs to guarantee robust decoding in the sense that each user must decode its demanded function with signals received from any subset of servers whose cardinality exceeds a threshold. In addition, (a) the content of the library must be kept secure from a wiretapper who obtains all the signals from the servers;(b) any subset of users together can not obtain any information about the demands of the remaining users; and (c) the users demands must be kept private against all the servers even if they collude. Achievable schemes are derived by modifying existing Placement Delivery Array (PDA) constructions, originally proposed for single-server single-file retrieval coded caching systems without any privacy or security or robustness constraints. It is shown that the PDAs describing the original Maddah-Ali and Niesens coded caching scheme result in a load-memory tradeoff that is optimal to within a constant multiplicative gap, except for the small memory regime when the number of file is smaller than the number of users. As by-products, improved order optimality results are derived for three less restrictive systems in all parameter regimes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
