Security improvements of several basic quantum private query protocols with O( N) communication complexity

DOI10.1016/J.TCS.2019.12.008zbMATH Open1436.68101arXiv2005.13382OpenAlexW2995770916WikidataQ115036478 ScholiaQ115036478MaRDI QIDQ2286752FDOQ2286752

Yanyan Li

Publication date: 22 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: New quantum private database (with N elements) query protocols are presented and analyzed. Protocols preserve O(logN) communication complexity of known protocols for the same task, but achieve several significant improvements in security, especially concerning user privacy. For example, the randomized form of our protocol has a cheat-sensitive property - it allows the user to detect a dishonest database with a nonzero probability, while the phase-encoded private query protocols for the same task do not have such a property. Moreover, when the database performs the computational basis measurement, a particular projective measurement which can cause a significant loss of user privacy in the previous private query protocols with O(logN) communication complexity, at most half of the user privacy could leak to such a database in our protocol, while in the QPQ protocol, the entire user privacy could leak out. In addition, it is proved here that for large N, the user could detect a cheating via the computational basis measurement, with a probability close to 1/2 using O(sqrt{N}) special queries. Finally, it is shown here, for both forms of our protocol, basic and randomized, how a dishonest database has to act in case it could not learn user's queries.

Full work available at URL: https://arxiv.org/abs/2005.13382

zbMATH Keywords

privacy\(\mathcal{O}(\log N)\) communication complexitycheat-sensitivitydishonest databaseprivate database query protocolrhetoric query

Mathematics Subject Classification ID

Database theory (68P15) Quantum cryptography (quantum-theoretic aspects) (81P94) Privacy of data (68P27) Communication complexity, information complexity (68Q11)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum Private Queries
• Protecting data privacy in private information retrieval schemes
• Quantum symmetrically-private information retrieval
• Quantum Random Access Memory
• Upper bound on the communication complexity of private information retrieval
• Quantum private information retrieval has linear communication complexity

Cited In (2)

• Decoy-state quantum private query protocol with two-way communication
• Semi-quantum secure direct communication using entanglement

This page was built for publication: Security improvements of several basic quantum private query protocols with \(O(\log N)\) communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286752)