YU, Fang, Daowen QIU, Xiaominf WANG, Qin LI, Lvzhou LI and Jozef GRUSKA. Security improvements of several basic quantum private query protocols with O(log N) communication complexity. Theoretical Computer Science. Amsterdam: Elsevier, 2020, vol. 807, 6 February 2020, p. 330-340. ISSN 0304-3975. Available from: https://dx.doi.org/10.1016/j.tcs.2019.12.008.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Security improvements of several basic quantum private query protocols with O(log N) communication complexity
Authors YU, Fang (156 China, belonging to the institution), Daowen QIU, Xiaominf WANG, Qin LI, Lvzhou LI and Jozef GRUSKA (703 Slovakia, belonging to the institution).
Edition Theoretical Computer Science, Amsterdam, Elsevier, 2020, 0304-3975.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 0.827
RIV identification code RIV/00216224:14330/20:00115600
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1016/j.tcs.2019.12.008
UT WoS 000512219400021
Keywords in English Private database query protocol; O (log N) communication complexity; Cheat-sensitivity; Rhetoric query; Dishonest database; Privacy
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 20/9/2022 11:09.
Abstract
New quantum private database (with N elements) query protocols are presented and analyzed. Protocols preserve O (log N) 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 [6,7] 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 (log N) communication complexity, at most half of the user privacy could leak to such a database in our protocol, while in the QPQ protocol [5], 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(root 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.
PrintDisplayed: 21/5/2024 00:15