Quantum <i>X</i>-Secure <i>E</i>-Eavesdropped <i>T</i>-Colluding Symmetric Private Information Retrieval

We consider both classical and quantum variations of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-secure, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i>-eavesdropped and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i>-colluding symmetric private information retrieval (SPIR). This is the first work to study SPIR with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-security in classical or quantum variations. We first develop a scheme for classical <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-secure, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i>-eavesdropped and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i>-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA), which achieves a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$R= 1 - \frac {X+\max (T,E)}{N}$ </tex-math></inline-formula>. The modified scheme achieves the same rate as the scheme used for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-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 the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>-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 quantum <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-secure, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i>-eavesdropped and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i>-colluding SPIR (QXSETSPIR) with secure over-the-air decoding. The first scheme achieves the highest possible super-dense coding gain, i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$R_{Q} = \min \left \{{{ 1, 2\left ({{1-\frac {X+\max (T,E)}{N}}}\right)}}\right \}$ </tex-math></inline-formula>, 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.