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

arXiv:2412.06728

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ş

Published Dec 9, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2412.06728

Related papers

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

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

The Asymptotic Capacity of Byzantine Symmetric Private Information Retrieval and its Consequences

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

We consider the problem of finding the asymptotic capacity of symmetric private information retrieval (SPIR) with$B$Byzantine servers. Prior to finding the capacity, a definition for the Byzantine servers is needed since in the literature there are two different definitions. In [1], where it was first defined, the Byzantine servers can send any symbol from the storage, their received queries and some independent random symbols. In [2], Byzantine servers send any random symbol independently of their storage and queries. It is clear that these definitions are not identical, especially when symmetric privacy is required. To that end, we define Byzantine servers, inspired by [1], as the servers that can share everything, before and after the scheme initiation. In this setting, we find an upper bound, for an infinite number of messages case, that should be satisfied for all schemes that protect against this setting and develop a scheme that achieves this upper bound. Hence, we identify the capacity of the problem.

arXiv:2501.17124•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation

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 $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

One-Way Quantum Symmetric Private Information Retrieval Protocol From A Single Database Server Using NISQ Devices

Xiang Zou, H. F. Chau

Symmetric private information retrieval (SPIR) lets an inquirer obtain one specific bit only, without leaking any information about its index to the database owner. With a single server, this is impossible for parties with unrestricted quantum power. We show that it becomes possible, with information-theoretic security, when the server and the user hold only noisy intermediate-scale quantum (NISQ) devices without long-term quantum memory and measure each qubit on arrival, while the eavesdropper remains all-powerful; this is a stricter form of the memory restriction of the bounded- and noisy-quantum-storage models. The server sends BB84 states one way; the user discriminates them unambiguously and so knows a random subset of the bits. After a joint random permutation into blocks, the user announces the conclusive locations of one privately chosen block, and the server hashes and takes a random parity of these locations in every block; the permutation makes it exponentially unlikely that one set of locations fits two blocks. We prove secrecy against the eavesdropper, database privacy through an explicit size rule for the announced set, and user privacy against a server who prepares the prescribed BB84 states and announces truthfully, exactly for single photons and up to a small multi-photon term over a tolerated noise channel. The only addition to BB84 equipment is a passive linear-optical measurement with one ancillary mode. For a $10^{4}$-bit database and database privacy $10^{-6}$, blocks of about a thousand qubits suffice over a tolerated noise channel for a user who applies the prescribed measurement; certifying an arbitrary memoryless user and committing to the permutation need larger auxiliary transmissions, which we quantify with finite keys. Database privacy extends to decoy-state weak coherent pulses, and simulations show that the bound is nearly tight.

quant-pharXiv:2610.02093•Oct 2, 2026•0 citations
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.
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 the problem of finding the asymptotic capacity of symmetric private information retrieval (SPIR) withBBBByzantine servers. Prior to finding the capacity, a definition for the Byzantine servers is needed since in the literature there are two different definitions. In [1], where it was first defined, the Byzantine servers can send any symbol from the storage, their received queries and some independent random symbols. In [2], Byzantine servers send any random symbol independently of their storage and queries. It is clear that these definitions are not identical, especially when symmetric privacy is required. To that end, we define Byzantine servers, inspired by [1], as the servers that can share everything, before and after the scheme initiation. In this setting, we find an upper bound, for an infinite number of messages case, that should be satisfied for all schemes that protect against this setting and develop a scheme that achieves this upper bound. Hence, we identify the capacity of the problem.
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)​)}.
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.
Symmetric private information retrieval (SPIR) lets an inquirer obtain one specific bit only, without leaking any information about its index to the database owner. With a single server, this is impossible for parties with unrestricted quantum power. We show that it becomes possible, with information-theoretic security, when the server and the user hold only noisy intermediate-scale quantum (NISQ) devices without long-term quantum memory and measure each qubit on arrival, while the eavesdropper remains all-powerful; this is a stricter form of the memory restriction of the bounded- and noisy-quantum-storage models. The server sends BB84 states one way; the user discriminates them unambiguously and so knows a random subset of the bits. After a joint random permutation into blocks, the user announces the conclusive locations of one privately chosen block, and the server hashes and takes a random parity of these locations in every block; the permutation makes it exponentially unlikely that one set of locations fits two blocks. We prove secrecy against the eavesdropper, database privacy through an explicit size rule for the announced set, and user privacy against a server who prepares the prescribed BB84 states and announces truthfully, exactly for single photons and up to a small multi-photon term over a tolerated noise channel. The only addition to BB84 equipment is a passive linear-optical measurement with one ancillary mode. For a 10410^{4}104-bit database and database privacy 10−610^{-6}10−6, blocks of about a thousand qubits suffice over a tolerated noise channel for a user who applies the prescribed measurement; certifying an arbitrary memoryless user and committing to the permutation need larger auxiliary transmissions, which we quantify with finite keys. Database privacy extends to decoy-state weak coherent pulses, and simulations show that the bound is nearly tight.