{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T18:53:34Z","timestamp":1767034414891,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030176587"},{"type":"electronic","value":"9783030176594"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17659-4_8","type":"book-chapter","created":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T04:42:13Z","timestamp":1557808933000},"page":"219-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On Quantum Advantage in Information Theoretic Single-Server PIR"],"prefix":"10.1007","author":[{"given":"Dorit","family":"Aharonov","sequence":"first","affiliation":[]},{"given":"Zvika","family":"Brakerski","sequence":"additional","affiliation":[]},{"given":"Kai-Min","family":"Chung","sequence":"additional","affiliation":[]},{"given":"Ayal","family":"Green","sequence":"additional","affiliation":[]},{"given":"Ching-Yi","family":"Lai","sequence":"additional","affiliation":[]},{"given":"Or","family":"Sattath","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,24]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","unstructured":"Aaronson, S.: Limitations of quantum advice and one-way communication. In: Proceedings of the 19th IEEE Annual Conference on Computational Complexity, pp. 320\u2013332, June 2004. https:\/\/doi.org\/10.1109\/CCC.2004.1313854","DOI":"10.1109\/CCC.2004.1313854"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Brakerski, Z., Chung, K.-M., Green, A., Lai, C.-Y., Sattath, O.: On quantum advantage in information theoretic single-server PIR (2019). arXiv:1902.09768","DOI":"10.1007\/978-3-030-17659-4_8"},{"issue":"3","key":"8_CR3","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1137\/14096387X","volume":"45","author":"D Aharonov","year":"2016","unstructured":"Aharonov, D., Chailloux, A., Ganz, M., Kerenidis, I., Magnin, L.: A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias. SIAM J. Comput. 45(3), 633\u2013679 (2016). https:\/\/doi.org\/10.1137\/14096387X","journal-title":"SIAM J. Comput."},{"key":"8_CR4","doi-asserted-by":"publisher","unstructured":"Aharonov, D., Kitaev, A.Y., Nisan, N.: Quantum circuits with mixed states. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 23\u201326 May 1998, pp. 20\u201330 (1998). https:\/\/doi.org\/10.1145\/276698.276708","DOI":"10.1145\/276698.276708"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1145\/581771.581773","volume":"49","author":"A Ambainis","year":"2002","unstructured":"Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.: Dense quantum coding and quantum finite automata. JACM 49(4), 496\u2013511 (2002). https:\/\/doi.org\/10.1145\/581771.581773","journal-title":"JACM"},{"key":"8_CR6","unstructured":"Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, p. 175 (1984)"},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00145-014-9180-2","volume":"28","author":"\u00c4 Baumeler","year":"2015","unstructured":"Baumeler, \u00c4., Broadbent, A.: Quantum private information retrieval has linear communication complexity. J. Cryptol. 28(1), 161\u2013175 (2015). https:\/\/doi.org\/10.1007\/s00145-014-9180-2","journal-title":"J. Cryptol."},{"issue":"1","key":"8_CR8","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10623-015-0157-4","volume":"78","author":"A Broadbent","year":"2016","unstructured":"Broadbent, A., Schaffner, C.: Quantum cryptography beyond quantum key distribution. Des. Codes Crypt. 78(1), 351\u2013382 (2016). https:\/\/doi.org\/10.1007\/s10623-015-0157-4","journal-title":"Des. Codes Crypt."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) FOCS, pp. 97\u2013106. IEEE (2011). https:\/\/eprint.iacr.org\/2011\/344.pdf","DOI":"10.1109\/FOCS.2011.12"},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995, pp. 41\u201350. IEEE Computer Society (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492461","DOI":"10.1109\/SFCS.1995.492461"},{"key":"8_CR11","doi-asserted-by":"publisher","unstructured":"Chailloux, A., Kerenidis, I.: Optimal quantum strong coin flipping. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, 25\u201327 October 2009, pp. 527\u2013533. IEEE Computer Society (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.71","DOI":"10.1109\/FOCS.2009.71"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","volume-title":"Advances in Cryptology\u2014EUROCRYPT 1999","author":"C Cachin","year":"1999","unstructured":"Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402\u2013414. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_28"},{"key":"8_CR13","doi-asserted-by":"publisher","unstructured":"Dvir, Z., Gopi, S.: 2-Server PIR with sub-polynomial communication. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14\u201317 June 2015, pp. 577\u2013584. ACM (2015). https:\/\/doi.org\/10.1145\/2746539.2746546","DOI":"10.1145\/2746539.2746546"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1007\/978-3-642-14623-7_37","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"F Dupuis","year":"2010","unstructured":"Dupuis, F., Nielsen, J.B., Salvail, L.: Secure two-party quantum evaluation of unitaries against specious adversaries. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 685\u2013706. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_37"},{"issue":"6","key":"8_CR15","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1137\/090772721","volume":"41","author":"K Efremenko","year":"2012","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. SIAM J. Comput. 41(6), 1694\u20131703 (2012). https:\/\/doi.org\/10.1137\/090772721","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR16","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1109\/18.761271","volume":"45","author":"CA Fuchs","year":"1999","unstructured":"Fuchs, C.A., van de Graaf, J.: Cryptographic distinguishability measures for quantum-mechanical states. IEEE Trans. Inf. Theory 45(4), 1216\u20131227 (1999). https:\/\/doi.org\/10.1109\/18.761271","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR17","unstructured":"Gottesman, D., Chuang, I.: Quantum digital signatures (2001). arXiv:quant-ph\/0105032"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis. Stanford University (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"230502","DOI":"10.1103\/PhysRevLett.100.230502","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Quantum private queries. Phys. Rev. Lett. 100, 230502 (2008). https:\/\/doi.org\/10.1103\/PhysRevLett.100.230502","journal-title":"Phys. Rev. Lett."},{"key":"8_CR20","volume-title":"The Foundations of Cryptography - Volume 2, Basic Applications","author":"O Goldreich","year":"2004","unstructured":"Goldreich, O.: The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, Cambridge (2004)"},{"key":"8_CR21","doi-asserted-by":"publisher","unstructured":"Gutoski, G., Watrous, J.: Toward a general theory of quantum games. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 565\u2013574. ACM (2007). https:\/\/doi.org\/10.1145\/1250790.1250873","DOI":"10.1145\/1250790.1250873"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"3566","DOI":"10.1103\/PhysRevLett.83.3566","volume":"83","author":"D Jonathan","year":"1999","unstructured":"Jonathan, D., Plenio, M.B.: Entanglement-assisted local manipulation of pure quantum states. Phys. Rev. Lett. 83, 3566\u20133569 (1999). https:\/\/doi.org\/10.1103\/PhysRevLett.83.3566","journal-title":"Phys. Rev. Lett."},{"issue":"6","key":"8_CR23","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/1568318.1568323","volume":"56","author":"R Jain","year":"2009","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: A property of quantum relative entropy with an application to privacy in quantum communication. J. ACM 56(6), 33:1\u201333:32 (2009). https:\/\/doi.org\/10.1145\/1568318.1568323","journal-title":"J. ACM"},{"issue":"3&4","key":"8_CR24","first-page":"181","volume":"16","author":"I Kerenidis","year":"2016","unstructured":"Kerenidis, I., Lauri\u00e8re, M., Gall, F.L., Rennela, M.: Information cost of quantum communication protocols. Quantum Inf. Comput. 16(3&4), 181\u2013196 (2016). http:\/\/www.rintonpress.com\/xxqic16\/qic-16-34\/0181-0196.pdf","journal-title":"Quantum Inf. Comput."},{"key":"8_CR25","unstructured":"Klimesh, M.: Inequalities that collectively completely characterize the catalytic majorization relation (2007). arXiv:0709.3680"},{"issue":"9","key":"8_CR26","doi-asserted-by":"publisher","first-page":"4337","DOI":"10.1109\/TIT.2009.2025545","volume":"55","author":"R Konig","year":"2009","unstructured":"Konig, R., Renner, R., Schaffner, C.: The operational meaning of min- and max-entropy. IEEE Trans. Inf. Theory 55(9), 4337\u20134347 (2009). https:\/\/doi.org\/10.1109\/TIT.2009.2025545","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"3410","DOI":"10.1103\/PhysRevLett.78.3410","volume":"78","author":"H-K Lo","year":"1997","unstructured":"Lo, H.-K., Chau, H.F.: Is quantum bit commitment really possible? Phys. Rev. Lett. 78, 3410\u20133413 (1997). https:\/\/doi.org\/10.1103\/PhysRevLett.78.3410","journal-title":"Phys. Rev. Lett."},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Lai, C.-Y., Chung, K.-M.: Interactive leakage chain rule for quantum min-entropy (2018). arXiv:1809.10694","DOI":"10.1109\/ISIT.2019.8849408"},{"issue":"16","key":"8_CR29","doi-asserted-by":"publisher","first-page":"369","DOI":"10.4086\/toc.2012.v008a016","volume":"8","author":"F Le Gall","year":"2012","unstructured":"Le Gall, F.: Quantum private information retrieval with sublinear communication complexity. Theory Comput. 8(16), 369\u2013374 (2012). https:\/\/doi.org\/10.4086\/toc.2012.v008a016","journal-title":"Theory Comput."},{"issue":"2","key":"8_CR30","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1103\/PhysRevA.56.1154","volume":"56","author":"H-K Lo","year":"1997","unstructured":"Lo, H.-K.: Insecurity of quantum secure computations. Phys. Rev. A 56(2), 1154 (1997). https:\/\/doi.org\/10.1103\/PhysRevA.56.1154","journal-title":"Phys. Rev. A"},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1103\/PhysRevLett.78.3414","volume":"78","author":"D Mayers","year":"1997","unstructured":"Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78, 3414\u20133417 (1997). https:\/\/doi.org\/10.1103\/PhysRevLett.78.3414","journal-title":"Phys. Rev. Lett."},{"key":"8_CR32","unstructured":"Mochon, C.: Quantum weak coin flipping with arbitrarily small bias (2007). arXiv:0711.4114"},{"key":"8_CR33","doi-asserted-by":"publisher","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: 40th Annual Symposium on Foundations of Computer Science, pp. 369\u2013376 (1999). https:\/\/doi.org\/10.1109\/SFFCS.1999.814608","DOI":"10.1109\/SFFCS.1999.814608"},{"issue":"6","key":"8_CR34","doi-asserted-by":"publisher","first-page":"2261","DOI":"10.1109\/TIT.2007.896874","volume":"53","author":"T Ogawa","year":"2007","unstructured":"Ogawa, T., Nagaoka, H.: Making good codes for classical-quantum channel coding via quantum hypothesis testing. IEEE Trans. Inf. Theory 53(6), 2261\u20132266 (2007). https:\/\/doi.org\/10.1109\/TIT.2007.896874","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR35","doi-asserted-by":"publisher","first-page":"060302","DOI":"10.1103\/PhysRevA.67.060302","volume":"67","author":"W van Dam","year":"2003","unstructured":"van Dam, W., Hayden, P.: Universal entanglement transformations without communication. Phys. Rev. A 67, 060302 (2003). https:\/\/doi.org\/10.1103\/PhysRevA.67.060302","journal-title":"Phys. Rev. A"},{"issue":"1","key":"8_CR36","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/1008908.1008920","volume":"15","author":"S Wiesner","year":"1983","unstructured":"Wiesner, S.: Conjugate coding. SIGACT News 15(1), 78\u201388 (1983). https:\/\/doi.org\/10.1145\/1008908.1008920","journal-title":"SIGACT News"},{"key":"8_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139525343","volume-title":"Quantum Information Theory","author":"MM Wilde","year":"2013","unstructured":"Wilde, M.M.: Quantum Information Theory. Cambridge University Press, Cambridge (2013). Cambridge Books Online"},{"issue":"7","key":"8_CR38","doi-asserted-by":"publisher","first-page":"2481","DOI":"10.1109\/18.796385","volume":"45","author":"AJ Winter","year":"1999","unstructured":"Winter, A.J.: Coding theorem and strong converse for quantum channels. IEEE Trans. Inf. Theory 45(7), 2481\u20132485 (1999). https:\/\/doi.org\/10.1109\/18.796385","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR39","doi-asserted-by":"crossref","unstructured":"Yu, L., P\u00e9rez-Delgado, C.A., Fitzsimons, J.F.: Limitations on information theoretically secure quantum homomorphic encryption (2014). arXiv:1406.2456","DOI":"10.1103\/PhysRevA.90.050303"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2019"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17659-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T12:58:50Z","timestamp":1710334730000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17659-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030176587","9783030176594"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17659-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"24 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Darmstadt","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"IACR websubrev","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"327","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"76","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}