We consider the problems arising from the presence of Byzantine servers in a quantum private information retrieval (QPIR) setting. This is the first work to precisely define what the capabilities of Byzantine servers could be in a QPIR context. We show that quantum Byzantine servers have more capabilities than their classical counterparts due to the possibilities created by quantum encoding procedures. We focus on quantum Byzantine servers that can apply any reversible operation on their individual qudits. In this case, Byzantine servers can generate any error, i.e., this covers all possible single qudit operations that can be applied by Byzantine servers on their qudits. We design a scheme based on cross-subspace alignment (CSA) and we show that this scheme achieves superdense coding gain in some cases.
Quantum X-Secure B-Byzantine T-Colluding Private Information Retrieval
We consider the problems arising from the presence of Byzantine servers in a quantum private information retrieval (QPIR) setting. This is the first work to precisely define what the capabilities of Byzantine servers could be in a QPIR context. We show that quantum Byzantine servers have more capabilities than their classical counterparts due to the possibilities created by quantum encoding procedures. We focus on quantum Byzantine servers that can apply any reversible operation on their individual qudits. In this case, Byzantine servers can generate any error, i.e., this covers all possible single qudit operations that can be applied by Byzantine servers on their qudits. We design a scheme based on cross-subspace alignment (CSA) and we show that this scheme achieves superdense coding gain in some cases.
A communication-efficient protocol is introduced over a many-to-one quantum network for Q-E-B-MDS-X-TPIR, i.e., quantum private information retrieval with MDS-X-secure storage andT-private queries. The protocol is resilient to any set of up toEunresponsive servers (erased servers or stragglers) and any set of up toBByzantine servers. The underlying coding scheme incorporates an enhanced version of a Cross Subspace Alignment (CSA) code, namely a Modified CSA (MCSA) code, into the framework of CSS codes. The error-correcting capabilities of CSS codes are leveraged to encode the dimensions that carry desired computation results from the MCSA code into the error space of the CSS code, while the undesired interference terms are aligned into the stabilized code space. The challenge is to do this efficiently while also correcting quantum erasures and Byzantine errors. The protocol achieves superdense coding gain over comparable classical baselines for Q-E-B-MDS-X-TPIR, recovers as special cases the state of art results for various other quantum PIR settings previously studied in the literature, and paves the way for applications in quantum coded distributed computation, where CSA code structures are important for communication efficiency, while security and resilience to stragglers and Byzantine servers are critical.
We consider both the classical and quantum variations of X-secure, E-eavesdropped andT-colluding symmetric private information retrieval (SPIR). This is the first work to study SPIR with X-security in classical or quantum variations. We first develop a scheme for classical X-secure, E-eavesdropped andT-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate ofR=1−NX+max(T,E). The modified scheme achieves the same rate as the scheme used for X-secure PIR with the extra benefit of symmetric privacy. Next, we extend this scheme to its quantum counterpart based on theN-sum box abstraction. This is the first work to consider the presence of eavesdroppers in quantum private information retrieval (QPIR). In the quantum variation, the eavesdroppers have better access to information over the quantum channel compared to the classical channel due to the over-the-air decodability. To that end, we develop another scheme specialized to combat eavesdroppers over quantum channels. The scheme proposed for X-secure, E-eavesdropped and T-colluding quantum SPIR (XSETQSPIR) in this work maintains the super-dense coding gain from the shared entanglement between the databases, i.e., achieves a rate ofRQ=min{1,2(1−NX+max(T,E))}.
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 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.
Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum X-Secure B-Byzantine E-Eavesdropped U-Unresponsive T-Colluding PIR?
We consider the quantum \emph{symmetric} private information retrieval (QSPIR) problem in a system with N databases and K messages, with U unresponsive servers, T-colluding servers, and X-security parameter, under several fundamental threat models. In the first model, there are E1 eavesdropped links in the uplink direction (the direction from the user to the N servers), E2 eavesdropped links in the downlink direction (the direction from the servers to the user), where ∣E1∣,∣E2∣≤E; we coin this eavesdropper setting as \emph{dynamic} eavesdroppers. We show that super-dense coding gain can be achieved for some regimes. In the second model, we consider the case with Byzantine servers, i.e., servers that can coordinate to devise a plan to harm the privacy and security of the system together with static eavesdroppers, by listening to the same links in both uplink and downlink directions. It is important to note the considerable difference between the two threat models, since the eavesdroppers can take huge advantage of the presence of the Byzantine servers. Unlike the previous works in SPIR with Byzantine servers, that assume that the Byzantine servers can send only random symbols independent of the stored messages, we follow the definition of Byzantine servers in \cite{byzantine_tpir}, where the Byzantine servers can send symbols that can be functions of the storage, queries, as well as the random symbols in a way that can produce worse harm to the system. In the third and the most novel threat model, we consider the presence of Byzantine servers and dynamic eavesdroppers together. We show that having dynamic eavesdroppers along with Byzantine servers in the same system model creates more threats to the system than having static eavesdroppers with Byzantine servers.
We consider both classical and quantum variations ofX-secure,E-eavesdropped andT-colluding symmetric private information retrieval (SPIR). This is the first work to study SPIR withX-security in classical or quantum variations. We first develop a scheme for classicalX-secure,E-eavesdropped andT-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate ofR=1−NX+max(T,E). The modified scheme achieves the same rate as the scheme used forX-secure PIR with the extra benefit of symmetric privacy, i.e., user-privacy as well as database-privacy. Next, we extend this scheme to its quantum counterpart based on theN-sum box abstraction. This is the first work to consider the presence of eavesdroppers in quantum private information retrieval (QPIR). In the quantum variation, the eavesdroppers have better access to information over the quantum channel compared to the classical channel due to the over-the-air decodability. To that end, we develop two different schemes for quantumX-secure,E-eavesdropped andT-colluding SPIR (QXSETSPIR) with secure over-the-air decoding. The first scheme achieves the highest possible super-dense coding gain, i.e.,RQ=min{1,2(1−NX+max(T,E))}, which requires additional uploads from the user. The second scheme on the other hand requires no extra uploads. However, it does not achieve the super-dense coding gain in some cases based on the relation between the number of eavesdropped links and the number of interference terms. The second scheme is based on the idea that there exist some special entanglement states that can be used to hide the contents of the user-required messages from the eavesdroppers using the interference symbols.
We consider the quantumsymmetricprivate information retrieval (QSPIR) problem in a system withNdatabases andKmessages, withUunresponsive servers,T-colluding servers, andX-security parameter, under several fundamental threat models. In the first model, there areE1eavesdropped links in the uplink direction (the direction from the user to theNservers),E2eavesdropped links in the downlink direction (the direction from the servers to the user), where |E1|, |E2| ≤E; we coin this eavesdropper setting asdynamiceavesdroppers. We show that super-dense coding gain can be achieved for some regimes. In the second model, we consider the case with Byzantine servers, i.e., servers that can coordinate to devise a plan to harm the privacy and security of the system together with static eavesdroppers, by listening to the same links in both uplink and downlink directions. It is important to note the considerable difference between the two threat models, since the eavesdroppers can take huge advantage of the presence of the Byzantine servers. Unlike the previous works in SPIR with Byzantine servers, that assume that the Byzantine servers can send only random symbols independent of the stored messages, we follow the definition of Byzantine servers in [1], where the Byzantine servers can send symbols that can be functions of the storage, queries, as well as the random symbols in a way that can produce worse harm to the system. In the third and the most novel threat model, we consider the presence of Byzantine servers and dynamic eavesdroppers together. We show that having dynamic eavesdroppers along with Byzantine servers in the same system model creates more threats to the system than having static eavesdroppers with Byzantine servers. This is the first work that considers the quantum version of unresponsive and eavesdropped threat model. In addition, this is the first work, classical or quantum, that considers the presence of Byzantine servers together with eavesdroppers in the same system model (static or dynamic eavesdroppers). Another layer of difficulty that we handle in this work stems from the symmetric privacy requirement in the presence of Byzantine servers, which by itself has never been studied before in classical or quantum variations; here the Byzantine servers may attempt to leak information about undesired messages to the user, which is not allowed in SPIR.