Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Communications

A Coding Scheme for Straggler Resilient Quantum X-Secure T-Private Information Retrieval

Yuxiang Lu, Syed A. Jafar

Published Jun 9, 2024• 4 citations
Publisher

Abstract

Building on recent constructions of Quantum Cross Subspace Alignment (QCSA) codes, this work develops a coding scheme for QEXSTPIR, i.e., classical private information retrieval with X -secure storage and$T$-private queries, over a quantum multiple access channel, that is resilient to any set of up to$E$erased servers (equivalently known as unresponsive servers, or stragglers). The scheme is accordingly labeled QECSA, with the ‘$\mathbf{E}$,indicating resilience to erased servers. The novelty of QECSA lies in achieving efficient E-straggler resilience on top of existing QCSA codes that already achieve X-secure storage, T- private queries, and distributed superdense coding gains for communication efficient decoding. The QECSA code structure may be broadly useful for problems such as quantum coded secure distributed computation, where security, straggler resilience, and distributed superdense coding gains are simultaneously required.

DOI
10.1109/icc51166.2024.10622594

Related papers

Quantum X-Secure T-Private Information Retrieval From MDS Coded Storage With Unresponsive and Byzantine Servers

Yuxiang Lu, Syed A. Jafar

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.

arXiv:2311.07829•IEEE Journal on Selected Areas in Information Theory•Jan 1, 2025•4 citations

Quantum X-Secure E-Eavesdropped T-Colluding Symmetric Private Information Retrieval

Alptug Aytekin, Mohamed W. Nomeir, Sajani Vithana +1 more

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 of$R= 1 - \frac {X+\max (T,E)}{N}$. 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.,$R_{Q} = \min \left \{{{ 1, 2\left ({{1-\frac {X+\max (T,E)}{N}}}\right)}}\right \}$, 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.

IEEE Transactions on Information Theory•Mar 17, 2025•2 citations

Quantum Symmetric Private Information Retrieval with Secure Storage and Eavesdroppers

Alptug Aytekin, Mohamed W. Nomeir, Sajani Vithana +1 more

We consider both the classical and quantum variations of X-secure, E-eavesdropped and$T$-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 and$T$-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate of$R=1-\displaystyle \frac{X+\overline{\max}(T,E)}{N}$. 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 the$N$-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 of$R_{Q}=\displaystyle \min\{1,2(1-\frac{X+\max(T,E)}{N})\}$.

arXiv:2308.10883•IEEE Globecom Workshops (GC Wkshps)•Dec 4, 2023•13 citations

Quantum Private Information Retrieval from Coded Storage Systems

Matteo Allaix

In the era of extensive data growth, robust and efficient mechanisms are needed to store and manage vast amounts of digital information, such as Data Storage Systems (DSSs). Concurrently, privacy concerns have arisen, leading to the development of techniques like Private Information Retrieval (PIR) to enable data access while preserving privacy. A PIR protocol allows users to retrieve information from a database without revealing the specifics of their query or the data they are accessing. With the advent of quantum computing, researchers have explored the potential of using quantum systems to enhance privacy in information retrieval. In a Quantum Private Information Retrieval (QPIR) protocol, a user can retrieve information from a database by downloading quantum systems from multiple servers, while ensuring that the servers remain oblivious to the specific information being accessed. This scenario offers a unique advantage by leveraging the inherent properties of quantum systems to provide enhanced privacy guarantees and improved communication rates compared to classical PIR protocols. In this thesis we consider the QPIR setting where the queries and the coded storage systems are classical, while the responses from the servers are quantum. This problem was treated by Song et al. for replicated storage and different collusion patterns. This thesis aims to develop QPIR protocols for coded storage by combining known classical PIR protocols with quantum communication algorithms, achieving enhanced privacy and communication costs. We consider different storage codes and robustness assumptions, and we prove that the achieved communication cost is always lower than the classical counterparts.

arXiv:2312.07570•Dec 10, 2023•0 citations

Quantum $X$-Secure $B$-Byzantine $T$-Colluding Private Information Retrieval

Mohamed W. Nomeir, Alptug Aytekin, Şennur Ulukuş

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.

arXiv:2401.17252•IEEE Information Theory Workshop (ITW)•Nov 24, 2024•5 citations

On the Storage–Communication Trade-Off in Graph-Based X-Secure T-Private Linear Computation

Yueyang Liu, Haobo Jia, Zhuqing Jia

The problem of graph-based X-secure T-private linear computation (GXSTPLC) is to allow a user to retrieve a linear combination of K messages from a set of N distributed servers that store the messages in a graph-based fashion, i.e., each message is restricted to be distributed among a subset of servers. T-privacy requires that the coefficients of the linear combination are not revealed to any group of up to T colluding servers, and X-security guarantees that any set of up to X colluding servers learns nothing about the messages. In this paper, we propose an achievability scheme for GXSTPLC that enables a storage–communication trade-off by exploiting non-replicated storage codes. Novel aspects of our achievability scheme include the usage of the idea of cross-subspace alignment null shaper that addresses various challenges posed by the graph-based storage structure. In addition, unlike previous works, our scheme allows a direct transformation into a quantum one to achieve a superdense coding gain by leveraging the idea of N-Sum Box abstraction of quantum “over-the-air” computing.

Entropy•Sep 18, 2025•1 citation
Building on recent constructions of Quantum Cross Subspace Alignment (QCSA) codes, this work develops a coding scheme for QEXSTPIR, i.e., classical private information retrieval with X -secure storage andTTT-private queries, over a quantum multiple access channel, that is resilient to any set of up toEEEerased servers (equivalently known as unresponsive servers, or stragglers). The scheme is accordingly labeled QECSA, with the ‘E\mathbf{E}E,indicating resilience to erased servers. The novelty of QECSA lies in achieving efficient E-straggler resilience on top of existing QCSA codes that already achieve X-secure storage, T- private queries, and distributed superdense coding gains for communication efficient decoding. The QECSA code structure may be broadly useful for problems such as quantum coded secure distributed computation, where security, straggler resilience, and distributed superdense coding gains are simultaneously required.
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 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−X+max⁡(T,E)NR= 1 - \frac {X+\max (T,E)}{N}R=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−X+max⁡(T,E)N)}R_{Q} = \min \left \{{{ 1, 2\left ({{1-\frac {X+\max (T,E)}{N}}}\right)}}\right \}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 both the classical and quantum variations of X-secure, E-eavesdropped andTTT-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 andTTT-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate ofR=1−X+max⁡‾(T,E)NR=1-\displaystyle \frac{X+\overline{\max}(T,E)}{N}R=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 theNNN-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−X+max⁡(T,E)N)}R_{Q}=\displaystyle \min\{1,2(1-\frac{X+\max(T,E)}{N})\}RQ​=min{1,2(1−NX+max(T,E)​)}.
In the era of extensive data growth, robust and efficient mechanisms are needed to store and manage vast amounts of digital information, such as Data Storage Systems (DSSs). Concurrently, privacy concerns have arisen, leading to the development of techniques like Private Information Retrieval (PIR) to enable data access while preserving privacy. A PIR protocol allows users to retrieve information from a database without revealing the specifics of their query or the data they are accessing. With the advent of quantum computing, researchers have explored the potential of using quantum systems to enhance privacy in information retrieval. In a Quantum Private Information Retrieval (QPIR) protocol, a user can retrieve information from a database by downloading quantum systems from multiple servers, while ensuring that the servers remain oblivious to the specific information being accessed. This scenario offers a unique advantage by leveraging the inherent properties of quantum systems to provide enhanced privacy guarantees and improved communication rates compared to classical PIR protocols. In this thesis we consider the QPIR setting where the queries and the coded storage systems are classical, while the responses from the servers are quantum. This problem was treated by Song et al. for replicated storage and different collusion patterns. This thesis aims to develop QPIR protocols for coded storage by combining known classical PIR protocols with quantum communication algorithms, achieving enhanced privacy and communication costs. We consider different storage codes and robustness assumptions, and we prove that the achieved communication cost is always lower than the classical counterparts.
Quantum XXX-Secure BBB-Byzantine TTT-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.
The problem of graph-based X-secure T-private linear computation (GXSTPLC) is to allow a user to retrieve a linear combination of K messages from a set of N distributed servers that store the messages in a graph-based fashion, i.e., each message is restricted to be distributed among a subset of servers. T-privacy requires that the coefficients of the linear combination are not revealed to any group of up to T colluding servers, and X-security guarantees that any set of up to X colluding servers learns nothing about the messages. In this paper, we propose an achievability scheme for GXSTPLC that enables a storage–communication trade-off by exploiting non-replicated storage codes. Novel aspects of our achievability scheme include the usage of the idea of cross-subspace alignment null shaper that addresses various challenges posed by the graph-based storage structure. In addition, unlike previous works, our scheme allows a direct transformation into a quantum one to achieve a superdense coding gain by leveraging the idea of N-Sum Box abstraction of quantum “over-the-air” computing.