Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography
Open Access
Abstract
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.Keywords
All Related Versions
Funding Information
- National Research Foundation Singapore (NRF11-2019-0001, QEP-P2)
This publication has 39 references indexed in Scilit:
- Private database queries based on counterfactual quantum key distributionPhysical Review A, 2013
- Quantum Private QueriesPhysical Review Letters, 2008
- Towards 3-query locally decodable codes of subexponential lengthJournal of the ACM, 2008
- Quantum symmetrically-private information retrievalInformation Processing Letters, 2004
- Two-step quantum direct communication protocol using the Einstein-Podolsky-Rosen pair blockPhysical Review A, 2003
- Quantum cryptographyReviews of Modern Physics, 2002
- Protecting Data Privacy in Private Information Retrieval SchemesJournal of Computer and System Sciences, 2000
- Private information retrievalJournal of the ACM, 1998
- Insecurity of quantum secure computationsPhysical Review A, 1997
- New directions in cryptographyIEEE Transactions on Information Theory, 1976