Abstract:
In this thesis, we focus on the Quantum Private Query (QPQ) primitive in the
device-independent (DI) paradigm, addressing the challenges of preserving user and database privacy without trusting the devices. Existing cryptographic primitives, such as Symmetric Private Information Retrieval (SPIR) and 1 out of N Oblivious Transfer (OT), lack unconditional security with a single server in both classical and quantum domains. The QPQ primitive addresses this limitation by allowing the client to gain probabilistic knowledge about unintended data bits while expecting the server not to cheat if a non-zero probability exists of being caught.
The contributions of this thesis include proposing and analyzing QPQ schemes
within the DI framework. We introduce a novel QPQ scheme using EPR pairs,
exploiting self-testing of shared Bell states, projective measurement operators, and a specific class of POVM operators to achieve complete device independence. We address the limitations of a semi-DI-QPQ proposal and utilize the tilted version of the actual CHSH game and self-testing of observables to enhance security and certify full device independence. Furthermore, we suggest several strategies to reduce the overall sample size required for DI testing of that semi-DI-QPQ proposal in the finite sample scenario. Moreover, we address the limitations of the existing multi-user QPQ
schemes and propose a semi-DI multi-user QPQ scheme where each user can retrieve different items simultaneously without revealing their choices to others or relying on a semi-trusted server. We formally conduct security assessments for all our DI-QPQ proposals and derive upper limits on the cheating probabilities to ensure robust DI-QPQ implementations.
Overall, in this thesis, we contribute to advancing the QPQ primitive in the DI
paradigm, offering novel schemes and addressing the challenges posed by distrustful settings and multi-user scenarios.
