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

DOI10.1016/J.TCS.2019.12.008MaRDI QIDQ2286752zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 22 January 2020

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Quantum Private Queries
• Quantum private query with perfect user privacy against a joint-measurement attack
• A new protocol for quantum private query against joint-measurement attack
• Multi-user quantum private query protocol
• An efficient quantum private query protocol based on oracle and Grover iteration

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• scientific article; zbMATH DE number 486467 (Why is no real title available?)
• Protecting data privacy in private information retrieval schemes
• Quantum private information retrieval has linear communication complexity
• Quantum Private Queries
• Quantum random access memory
• Quantum symmetrically-private information retrieval
• Upper bound on the communication complexity of private information retrieval

Cited in

(10)

• Semi-quantum secure direct communication using entanglement
• Multi-user quantum private query protocol
• An efficient quantum private query protocol based on oracle and Grover iteration
• Relativistic quantum private database queries
• Quantum private query with perfect user privacy against a joint-measurement attack
• Quantum private information retrieval with sublinear communication complexity
• Efficient query protocol for database's privacy
• Decoy-state quantum private query protocol with two-way communication
• Cryptanalysis and improvement to the quantum private query protocol for enhancing database privacy
• Enhancing user privacy in SARG04-based private database query protocols

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)