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

J 2020

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

YU, Fang; Daowen QIU; Xiaominf WANG; Qin LI; Lvzhou LI et. al.

Základní údaje

Originální název

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

Autoři

YU, Fang (156 Čína, domácí); Daowen QIU; Xiaominf WANG; Qin LI; Lvzhou LI a Jozef GRUSKA (703 Slovensko, domácí)

Vydání

Theoretical Computer Science, Amsterdam, Elsevier, 2020, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.827

Kód RIV

RIV/00216224:14330/20:00115600

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/j.tcs.2019.12.008

UT WoS

000512219400021

EID Scopus

2-s2.0-85077397571

Klíčová slova anglicky

Private database query protocol; O (log N) communication complexity; Cheat-sensitivity; Rhetoric query; Dishonest database; Privacy

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 20. 9. 2022 11:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

YU, Fang; Daowen QIU; Xiaominf WANG; Qin LI; Lvzhou LI a Jozef GRUSKA. Security improvements of several basic quantum private query protocols with O(log N) communication complexity. Theoretical Computer Science. Amsterdam: Elsevier, 2020, roč. 807, 6 February 2020, s. 330-340. ISSN 0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2019.12.008.

@article{1652884,
   author = {Yu, Fang and Qiu, Daowen and Wang, Xiaominf and Li, Qin and Li, Lvzhou and Gruska, Jozef},
   article_location = {Amsterdam},
   article_number = {6 February 2020},
   doi = {https://doi.org/10.1016/j.tcs.2019.12.008},
   keywords = {Private database query protocol; O (log N) communication complexity; Cheat-sensitivity; Rhetoric query; Dishonest database; Privacy},
   language = {eng},
   issn = {0304-3975},
   journal = {Theoretical Computer Science},
   title = {Security improvements of several basic quantum private query protocols with O(log N) communication complexity},
   url = {http://dx.doi.org/10.1016/j.tcs.2019.12.008},
   volume = {807},
   year = {2020}
}

TY  - JOUR
ID  - 1652884
AU  - Yu, Fang - Qiu, Daowen - Wang, Xiaominf - Li, Qin - Li, Lvzhou - Gruska, Jozef
PY  - 2020
TI  - Security improvements of several basic quantum private query protocols with O(log N) communication complexity
JF  - Theoretical Computer Science
VL  - 807
IS  - 6 February 2020
SP  - 330-340
EP  - 330-340
PB  - Elsevier
SN  - 03043975
KW  - Private database query protocol
KW  - O (log N) communication complexity
KW  - Cheat-sensitivity
KW  - Rhetoric query
KW  - Dishonest database
KW  - Privacy
UR  - http://dx.doi.org/10.1016/j.tcs.2019.12.008
L2  - http://dx.doi.org/10.1016/j.tcs.2019.12.008
N2  - 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.
ER  -

YU, Fang; Daowen QIU; Xiaominf WANG; Qin LI; Lvzhou LI a Jozef GRUSKA. Security improvements of several basic quantum private query protocols with O(log N) communication complexity. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, 2020, roč.~807, 6 February 2020, s.~330-340. ISSN~0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2019.12.008.

Přehled o publikaci