Fulltext

Quantum Private Information Retrieval has Linear Communication Complexity

Baumeler, Ämin ; Broadbent, Anne

In: Journal of Cryptology, 2015, vol. 28, no. 1, p. 161-175

Ajouter à la liste personnelle
    Titre
    • Quantum Private Information Retrieval has Linear Communication Complexity
    Auteur
    • Baumeler, Ämin. Faculty of Informatics, Università della Svizzera italiana, Lugano, Switzerland
    • Broadbent, Anne. Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON, Canada
    Type de document
    • Postprint
    Langue
    • Anglais
    Publié dans
    • Journal of Cryptology, 2015, vol. 28, no. 1, p. 161-175. Springer US; http://www.springer-ny.com
    Autre version électronique
    Identifiant OAI-PMH
    • oai:doc.rero.ch:332905
    Summary
    In private information retrieval (PIR), a client queries an $$n$$ n -bit database in order to retrieve an entry of her choice, while maintaining privacy of her query value. Chor et al. [J ACM 45(6):965-981, 1998] showed that, in the information-theoretical setting, a linear amount of communication is required for classical PIR protocols (thus the trivial protocol is optimal). This linear lower bound was shown by Nayak [FOCS 1999, pp. 369-376, 1999] to hold also in the quantum setting. Here, we extend Nayak's result by considering approximate privacy, and requiring security only against specious adversaries, which are, in analogy to classical honest-but-curious adversaries, the weakest reasonable quantum adversaries. We show that, even in this weakened scenario, quantum private information retrieval (QPIR) requires $$n$$ n qubits of communication. From this follows that Le Gall's recent QPIR protocol with sublinear communication complexity [Theory Comput. 8(1):369-374, 2012] is not information-theoretically private, against the weakest reasonable cryptographic adversary.