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

IEEE Transactions on Information Theory

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

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

Published Mar 17, 2025• 2 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2025.3551697

Related papers

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

Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum $X$-Secure $B$-Byzantine $E$-Eavesdropped $U$-Unresponsive $T$-Colluding PIR?

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

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 $\mathcal{E}_1$ eavesdropped links in the uplink direction (the direction from the user to the $N$ servers), $\mathcal{E}_2$ eavesdropped links in the downlink direction (the direction from the servers to the user), where $|\mathcal{E}_1|, |\mathcal{E}_2| \leq 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.

arXiv:2412.06728•Dec 9, 2024•0 citations

Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum X -Secure B -Byzantine E -Eavesdropped U -Unresponsive T -Colluding PIR?

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

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.

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

Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography

Wen Yu Kon, Charles Ci Wen Lim

Private information retrieval (PIR) is a database query protocol that provides user privacy in that the user can learn a particular entry of the database of his interest but his query would be hidden from the data centre. Symmetric private information retrieval (SPIR) takes PIR further by additionally offering database privacy, where the user cannot learn any additional entries of the database. Unconditionally secure SPIR solutions with multiple databases are known classically, but are unrealistic because they require long shared secret keys between the parties for secure communication and shared randomness in the protocol. Here, we propose using quantum key distribution (QKD) instead for a practical implementation, which can realise both the secure communication and shared randomness requirements. We prove that QKD maintains the security of the SPIR protocol and that it is also secure against any external eavesdropper. We also show how such a classical-quantum system could be implemented practically, using the example of a two-database SPIR protocol with keys generated by measurement device-independent QKD. Through key rate calculations, we show that such an implementation is feasible at the metropolitan level with current QKD technology.

arXiv:2004.13921•Entropy•Dec 31, 2020•25 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 PIR and SPIR Over Gaussian MAC

Or Elimelech, Asaf Cohen

This paper revisits the problems of Private Information Retrieval (PIR) and Symmetric PIR (SPIR). In PIR, a user retrieves a desired message fromNreplicated, non-communicating databases, each storing the sameMmessages, while preserving the privacy of the requested message index. SPIR extends this notion further by additionally protecting the privacy of the databases, ensuring that the user learns no information beyond the requested message. In this paper, we assume a block-fading Additive White Gaussian Noise Multiple Access Channel (AWGN MAC) linking the user and the databases. Previous work presented a joint channel-PIR scheme utilizing the Compute and Forward (C&F) protocol, demonstrating the potential of a joint PIR-channel coding scheme over a separated one, yet still lagging behind the channel capacity and requiring significant computational complexity. We propose an improved scheme that offers reduced computational complexity while improving the achievable rate for finite parameters, as well as its scaling laws. Specifically, the achievable rate outperforms the C&F-based approach and scales with the number of databasesNand the powerPsimilarly to the channel capacitywithout the privacy constraint. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from this unconstrained channel capacity –$1~bit/sec/Hz$asNincreases. Finally, we provide two SPIR schemes. The first is a modification for our PIR scheme to attain SPIR with no rate loss, which is accomplished by introducing shared common randomness among databases. The second is a novel joint channel-SPIR scheme that utilizes the channel and lattice codes characteristics to nontrivially achieve SPIR without requiring common randomness, at the price of a loss in the achievable rate.

arXiv:2401.15912•IEEE Transactions on Communications•Aug 11, 2025•2 citations
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)​)}.
Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum XXX-Secure BBB-Byzantine EEE-Eavesdropped UUU-Unresponsive TTT-Colluding PIR?
We consider the quantum \emph{symmetric} private information retrieval (QSPIR) problem in a system with NNN databases and KKK messages, with UUU unresponsive servers, TTT-colluding servers, and XXX-security parameter, under several fundamental threat models. In the first model, there are E1\mathcal{E}_1E1​ eavesdropped links in the uplink direction (the direction from the user to the NNN servers), E2\mathcal{E}_2E2​ eavesdropped links in the downlink direction (the direction from the servers to the user), where ∣E1∣,∣E2∣≤E|\mathcal{E}_1|, |\mathcal{E}_2| \leq E∣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 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.
Private information retrieval (PIR) is a database query protocol that provides user privacy in that the user can learn a particular entry of the database of his interest but his query would be hidden from the data centre. Symmetric private information retrieval (SPIR) takes PIR further by additionally offering database privacy, where the user cannot learn any additional entries of the database. Unconditionally secure SPIR solutions with multiple databases are known classically, but are unrealistic because they require long shared secret keys between the parties for secure communication and shared randomness in the protocol. Here, we propose using quantum key distribution (QKD) instead for a practical implementation, which can realise both the secure communication and shared randomness requirements. We prove that QKD maintains the security of the SPIR protocol and that it is also secure against any external eavesdropper. We also show how such a classical-quantum system could be implemented practically, using the example of a two-database SPIR protocol with keys generated by measurement device-independent QKD. Through key rate calculations, we show that such an implementation is feasible at the metropolitan level with current QKD technology.
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.
This paper revisits the problems of Private Information Retrieval (PIR) and Symmetric PIR (SPIR). In PIR, a user retrieves a desired message fromNreplicated, non-communicating databases, each storing the sameMmessages, while preserving the privacy of the requested message index. SPIR extends this notion further by additionally protecting the privacy of the databases, ensuring that the user learns no information beyond the requested message. In this paper, we assume a block-fading Additive White Gaussian Noise Multiple Access Channel (AWGN MAC) linking the user and the databases. Previous work presented a joint channel-PIR scheme utilizing the Compute and Forward (C&F) protocol, demonstrating the potential of a joint PIR-channel coding scheme over a separated one, yet still lagging behind the channel capacity and requiring significant computational complexity. We propose an improved scheme that offers reduced computational complexity while improving the achievable rate for finite parameters, as well as its scaling laws. Specifically, the achievable rate outperforms the C&F-based approach and scales with the number of databasesNand the powerPsimilarly to the channel capacitywithout the privacy constraint. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from this unconstrained channel capacity –1 bit/sec/Hz1~bit/sec/Hz1 bit/sec/HzasNincreases. Finally, we provide two SPIR schemes. The first is a modification for our PIR scheme to attain SPIR with no rate loss, which is accomplished by introducing shared common randomness among databases. The second is a novel joint channel-SPIR scheme that utilizes the channel and lattice codes characteristics to nontrivially achieve SPIR without requiring common randomness, at the price of a loss in the achievable rate.