Studies on the quantum private query primitive in the device-independent paradigm/ Jyotirmoy Basak

Thesis (Ph.D) - Indian Statistical Institute, 2023

Includes bibliography

Introduction -- Preliminaries and Background -- Quantum Private Query -- Improved and Formal Proposal for Fully Device
Independent QPQ using EPR Pairs -- Proposal For Fully Device Independent QPQ using Non-maximally Entangled States -- Finite Sample Analysis in Device Independent QPQ -- Proposal For Multi-User Semi Device Independent QPQ -- Conclusion

Guided by Prof. Subhamoy Maitra

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.