Enhancing user privacy in SARG04-based private database query protocols. (English) Zbl 1327.81177

Summary: The well-known SARG04 protocol can be used in a private query application to generate an oblivious key. By usage of the key, the user can retrieve one out of \(N\) items from a database without revealing which one he/she is interested in. However, the existing SARG04-based private query protocols are vulnerable to the attacks of faked data from the database since in its canonical form, the SARG04 protocol lacks means for one party to defend attacks from the other. While such attacks can cause significant loss of user privacy, a variant of the SARG04 protocol is proposed in this paper with new mechanisms designed to help the user protect its privacy in private query applications. In the protocol, it is the user who starts the session with the database, trying to learn from it bits of a raw key in an oblivious way. An honesty test is used to detect a cheating database who had transmitted faked data. The whole private query protocol has \(O(N)\) communication complexity for conveying at least \(N\) encrypted items. Compared with the existing SARG04-based protocols, it is efficient in communication for per-bit learning.


81P94 Quantum cryptography (quantum-theoretic aspects)
94A60 Cryptography
Full Text: DOI


[1] Gertner, Y; Ishai, Y; Kushilevitz, E; Malkin, T, Protecting data privacy in private information retrieval schemes, J. Comput. Syst. Sci., 60, 592-629, (2000) · Zbl 0958.68059
[2] Giovannetti, V; Lloyd, S; Maccone, L, Quantum private queries, Phys. Rev. Lett., 100, 230502, (2008) · Zbl 1228.81143
[3] Olejnik, L, Secure quantum private information retrieval using phase-encoded queries, Phys. Rev. A, 84, 022313, (2011)
[4] Yu, F; Qiu, DW, Coding-based quantum private database query using entanglement, Quantum Inf. Comput., 14, 0091-0106, (2014)
[5] Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proceedings of the 36rd IEEE Symposium on Foundations of Computer Science, pp. 41-50. Also, in Journal of the ACM, vol. 45, 1998 (1995) · Zbl 0938.68625
[6] Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.: Breaking the \(\text{ O }(n^{1/(2k-1)})\) barrier for information-theoretic private information retrieval. In: Proceedings of 43rd IEEE FOCS, pp. 261-270 (2002)
[7] Ambainis, A.: Upper bound on the communication complexity of private information retrieval. In: 24th ICALP, LNCS 1256, pp. 401-407 (1997) · Zbl 1401.68065
[8] Hogg, T; Zhang, L, Private database queries using quantum states with limited coherence times, Int. J. Quantum Inf., 7, 459c474, (2009) · Zbl 1170.81324
[9] Jakobi, M; etal., Practical private database queries based on a quantum-key-distribution protocol, Phys. Rev. A, 83, 022301, (2011)
[10] Zhang, JL; Guo, FZ; Gao, F; Liu, B; Wen, QY, Private database queries based on counterfactual quantum key distribution, Phys. Rev. A, 88, 022334, (2013)
[11] Yang, Y.G., Zhang, M.O., Yang, R.: Private database queries using one quantum state. Quantum Inf. Process. (2014). doi:10.1007/s11128-014-0902-z · Zbl 1311.81104
[12] Scarani, V; Acin, A; Ribordy, G; etal., Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations, Phys. Rev. Lett., 92, 057901, (2004)
[13] Rao, MVP; Jakobi, M, Towards communication-efficient quantum oblivious key distribution, Phys. Rev. A, 87, 012331, (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.