リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

大学・研究所にある論文を検索できる 「Information-Theoretic Aspects of Quantum Private Information Retrieval」の論文概要。リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。
リケラボ

コピーが完了しました

URLをコピーしました

論文の公開元へ論文の公開元へ
書き出し

Information-Theoretic Aspects of Quantum Private Information Retrieval

SONG, Seunghoan 名古屋大学

2021.01.14

概要

When a user retrieves information from databases, it is often required to protect the privacy of the user. Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of 𝑓 messages from non-communicating 𝑛 servers by downloading quantum systems without revealing the identity of the retrieved message to any individual server. Symmetric QPIR is a QPIR with server secrecy in which the user obtains no information of non-targeted messages.

This thesis investigates the fundamental communication limit of the symmetric and non-symmetric QPIR and constructs the optimal QPIR protocols achieving the communication limit. The communication cost of a QPIR protocol is evaluated by the QPIR rate defined as the ratio of the size of one message to the whole dimension of the downloaded quantum systems. The supremum of the QPIR rate, called the QPIR capacity, characterizes the communication limit of QPIR.

Assuming that the servers share prior entanglement, we prove that the symmetric and non-symmetric QPIR capacities are 1 regardless of the number of servers and messages. We construct a rate-one protocol only with two servers. This capacityachieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using any secrecy condition. We also prove that the capacity of multi-round QPIR is 1.

As a variant of the QPIR with stronger security requirements, the 𝑡-private QPIR is a protocol in which the identity of the retrieved message is kept secret even if at most 𝑡 servers may collude to reveal the identity. We prove that the symmetric and non-symmetric 𝑡-private QPIR capacities are min{1,  2(n − t)} for any 1  ≤ t < n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is also greater than the classical counterpart.

Finally, we give a symmetric (𝑛 − 1) -private QPIR protocol with bipartite entangled states. The protocol has the QPIR rate ⌊n/2⌋ −1 , which implies that it is capacity-achieving for even number of servers 𝑛. The protocol is practical since the bipartite entangled states are reliably generated with current quantum technology compared to the other entangled states.

論文の公開元へ

関連論文

関連論文をもっと見る

参考文献

[1] S. Song and M. Hayashi, “Capacity of Quantum Private Information Retrieval with Multiple Servers,” IEEE Transactions on Information Theory, DOI:10.1109/TIT.2020.3022515, accepted.

[2] S. Song and M. Hayashi, “Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers,” Proceedings of 2019 IEEE Information Theory Workshop (ITW), pp. 1–5, 2019 (submitted to Journal on Selected Areas in Information Theory).

[3] S. Song and M. Hayashi, “Capacity of Quantum Private Information Retrieval with Colluding Servers,” Proceedings of 2020 IEEE International Symposium on Information Theory (ISIT), pp. 1077–1082, 2020 (submitted to IEEE Transactions on Information Theory).

[4] S. Song, “Secure quantum network code,” Master’s thesis, Nagoya University, 2019.

[5] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” Journal of the ACM, 45(6):965-981, 1998. Earlier version in FOCS’95.

[6] M. O. Rabin, “How to exchange secrets with oblivious transfer,” Technical Report TR-81, Harvard University, 1981.

[7] S. Even, O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts,” Communications of the ACM, vol. 28, no. 6, pp. 637–647, 1985.

[8] J. Kilian, “Founding crytpography on oblivious transfer,” Proc. 1988 ACM Annual Symposium on Theory of Computing, p. 20.

[9] Y. Ishai, M. Prabhakaran, and A. Sahai, “Founding Cryptography on Oblivious Transfer - Efficiently,” CRYPTO, pp. 572–591, 2008.

[10] A. Shamir, “How to share a secret,” Communications of the ACM, 22:612–613, 1979.

[11] A. Beimel, Y. Ishai, E. Kushilevitz, and I. Orlov, “Share Conversion and Private Information Retrieval,” Proceedings of the 27th Annual Conference on Computational Complexity, pp. 258–268, 2012.

[12] O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan, “Lower bounds for linear locally decodable codes and private information retrieval,” Proceedings of 17th IEEE Conference on Computational Complexity, pp. 175–183, 2002.

[13] J. Katz and L. Trevisan, “On the efficiency of local decoding procedures for error-correcting codes,” Proceedings of 32nd ACM STOC, pp. 80–86, 2000.

[14] O. Barkol, Y. Ishai, and E. Weinreb, “On locally decodable codes, selfcorrectable codes, and t-private PIR,” Algorithmica, vol. 58, no. 4, pp. 831–859, 2010.

[15] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” 39th STOC, 2007, pp. 266–274.

[16] E. Kushilevitz, R. Ostrovsky “Replication is not needed: single database, computationally-private information retrieval,” Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, USA: IEEE Computer Society, pp. 364–373, 1997.

[17] C. Cachin, S. Micali, and M. Stadler, “Computationally Private Information Retrieval with Polylogarithmic Communication,” Stern J. (eds) Advances in Cryptology - EUROCRYPT 1999, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, vol 1592, pp. 402–414, 1999.

[18] H. Lipmaa, “First CPIR Protocol with Data-Dependent Computation,” Proceedings of the 12th International Conference on Information Security and Cryptology, pp. 193–210, 2010.

[19] A. Beimel and Y. Stahl, “Robust information-theoretic private information retrieval,” Proceedings of the 3rd International Conference on Security in Communication Networks (SCN’02), pp. 326–341, 2003.

[20] C. Devet, I. Goldberg, and N. Heninger, “Optimally Robust Private Information Retrieval,” 21st USENIX Security Symposium, August 2012.

[21] Y. Ishai and E. Kushilevitz, “Improved upper bounds on information theoretic private information retrieval,” Proc. of the 31th STOC, pp. 79–88. 1999.

[22] A. Beimel, Y. Ishai “Information-Theoretic Private Information Retrieval: A Unified Construction,” In: Orejas F., Spirakis P.G., van Leeuwen J. (eds) Automata, Languages and Programming. ICALP 2001, 2001.

[23] Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. “Protecting data privacy in private information retrieval schemes,” Journal of Computer and Systems Sciences, 60(3):592–629, 2000. Earlier version in STOC 98.

[24] C. E. Shannon, “A mathematical theory of communication,” Bell Syst. Tech. J., 27, 623–656 (1948).

[25] T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private Information Retrieval for Coded Storage,” Proceedings of IEEE International Symposium on Information Theory (ISIT), pp. 2842–2846, 2015.

[26] H. Sun and S. Jafar, “The Capacity of Private Information Retrieval,” IEEE Transactions on Information Theory, vol. 63, no. 7, 2017.

[27] C. Tian, H. Sun, and J. Chen, “Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost,” IEEE Transactions on Information Theory, vol. 65, no. 11, pp. 7613-7627, 2019.

[28] H. Sun and S. Jafar, “The Capacity of Symmetric Private Information Retrieval,” 2016 IEEE Globecom Workshops (GC Wkshps), Washington, DC, 2016, pp. 1–5.

[29] H. Sun and S. Jafar, “The capacity of robust private information retrieval with colluding databases,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2018.

[30] Q. Wang and M. Skoglund, “Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries,” 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1083–1090, 2017.

[31] K. Banawan and S. Ulukus, “The Capacity of Private Information Retrieval from Coded Databases,” IEEE Transactions on Information Theory, vol. 64, no. 3, 2018.

[32] R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk, “Private information retrieval from coded databases with colluding servers,” SIAM J. Appl. Algebra Geometry, vol. 1, no. 1, pp. 647–664, 2017.

[33] S. Kumar, H.-Y. Lin, E. Rosnes, and A. Graell i Amat, “Achieving maximum distance separable private information retrieval capacity with linear codes,” IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 4243–4273, 2019.

[34] H.-Y. Lin, S. Kumar, E. Rosnes, and A. Graell i Amat, “An MDSPIR capacity-achieving protocol for distributed storage using non-MDS linear codes,” Proc. IEEE Int. Symp. Inf. Theory, Vail, CO, USA, Jun. 17-22, 2018.

[35] L. Holzbaur, R. Freij-Hollanti, C. Hollanti “On the Capacity of Private Information Retrieval from Coded, Colluding, and Adversarial Servers,” Proceedings of IEEE Information Theory Workshop, 2019.

[36] Q. Wang and M. Skoglund, “Symmetric private information retrieval for MDS coded distributed storage,” Proceedings of 2017 IEEE International Conference on Communications (ICC), pp. 1–6, May 2017.

[37] L. Holzbaur, R. Freij-Hollanti, J. Li, C. Hollanti, “Towards the Capacity of Private Information Retrieval from Coded and Colluding Servers,” arXiv:1903.12552 [cs.IT], 2019.

[38] H. Sun and S. A. Jafar, “Multiround Private Information Retrieval: Capacity and Storage Overhead,” IEEE Transactions on Information Theory, vol. 64, no. 8, pp. 5743–5754, 2018.

[39] R. Tandon, “The capacity of cache aided private information retrieval,” Proceedings of 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1078–1082, 2017.

[40] K. Banawan and S. Ulukus, “The capacity of private information retrieval from byzantine and colluding databases,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1206–1219, 2019.

[41] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, vol. 175, pp. 8, 1984.

[42] A. Ekert “Quantum cryptography based on Bell’s theorem,” Physical Review Letters, 67: 661–663, 1991.

[43] J. Watrous, “Zero-Knowledge against Quantum Attacks,” SIAM Journal on Computing, 39 (1): 25–58, 2009.

[44] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, “Quantum Fingerprinting.” Physical Review Letters, 87 (16): 167902, 2001.

[45] C. Crepeau, D. Gottesman, and A. Smith, “Approximate quantum errorcorrecting codes and secret sharing schemes,” in Proc. Eurocrypt 2005, pp. 285-301. Springer-Verlag, 2005.

[46] T. Lunghi, J. Kaniewski, F. Bussières, R. Houlmann, M. Tomamichel, A. Kent, N. Gisin, S. Wehner, and H. Zbinden, “Experimental Bit Commitment Based on Quantum Communication and Special Relativity,” Physical Review Letters, 111 (18): 180504, 2013.

[47] L. Olejnik, “Secure quantum private information retrieval using phaseencoded queries,” Physical Review A 84, 022313, 2011.

[48] F. Le Gall, “Quantum Private Information Retrieval with Sublinear Communication Complexity,” Theory of Computing, 8(16):369–374, 2012.

[49] I. Kerenidis, M. Laurière, F. Le Gall, and M. Rennela, “Information cost of quantum communication protocols,” Quantum information & computation, 16(3-4):181–196, 2016.

[50] Ä. Baumeler and A. Broadbent, “Quantum Private Information Retrieval has linear communication complexity,” Journal of Cryptology, vol. 28, issue 1, pp. 161–175, 2015.

[51] I. Kerenidis and R. de Wolf. “Exponential lower bound for 2-query locally decodable codes via a quantum argument,” Proceedings of 35th ACM STOC, pp. 106–115, 2003.

[52] I. Kerenidis and R. de Wolf, “Quantum symmetrically-private information retrieval,” Information Processing Letters, vol. 90, pp. 109–114, 2004.

[53] D. Aharonov, Z. Brakerski, K.-M. Chung, A. Green, C.-Y. Lai, O. Sattath, “On Quantum Advantage in Information Theoretic Single-Server PIR,” Ishai Y., Rijmen V. (eds) Advances in Cryptology – EUROCRYPT 2019. EUROCRYPT 2019. Lecture Notes in Computer Science, vol 11478. Springer, Cham, 2019.

[54] W. Kon and C. Lim, “Provably-secure symmetric private information retrieval with quantum cryptography,” arXiv:2004.13921 [quant-ph], 2020.

[55] M. Allaix, L. Holzbaur, T. Pllaha, and C. Hollanti, “Quantum Private Information Retrieval from MDS-coded and Colluding Servers,” IEEE Journal on Selected Areas in Information Theory, doi: 10.1109/JSAIT.2020.3015089.

[56] R. M. Fano, Transmission of Information: A Statistical Theory of Communication, the M.I.T. Press and John Wiley and Sons, New York & London, 1961.

[57] M. S. Pinsker, Information and Information Stability of Random Variables and Processes, San Francisco: Holden-Day, CA, 1964. (Originally published in Russian in 1960.)

[58] M. Fannes, “A continuity property of the entropy density for spin lattice systems,” Communications in Mathematical Physics, 31, 291–294, 1973.

[59] R. Alicki and M. Fannes, “Continuity of quantum mutual information,” J. of Phys. A: Math. and Gen., 37(5):L55–L57, 2004.

[60] D. Petz. “Quasi-entropies for finite quantum systems,” Reports on Mathematical Physics, 23.1, pp. 57–65, 1986.

[61] G.M. D’Ariano and P. Lo Presti and M.F. Sacchi, “Bell Measurements and Observables,” Physics Letters A 272, 32 (2000).

[62] C. E. Shannon, “The zero error capacity of a noisy channel,” IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8–19, 1956.

[63] D. Ding, Y. Quek, P. W. Shor, M. M. Wilde “Entropy Bound for the Classical Capacity of a Quantum Channel Assisted by Classical Feedback,” Proceedings of the 2019 IEEE International Symposium on Information Theory, Paris, France, pp. 250–254, 2019.

[64] N. Cai and M. Hayashi, “Secure Network Code for Adaptive and Active Attacks with No-Randomness in Intermediate Nodes,” IEEE Transactions on Information Theory, vol. 66, 1428–1448, 2020.

[65] M. Hayashi, Quantum Information Theory: Mathematical Foundation, Graduate Texts in Physics, Springer, (Second edition of Quantum Information: An Introduction Springer), 2017.

[66] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge: Cambridge University Press, 2000.

[67] M. M. Wilde, Quantum Information Theory, Cambridge: Cambridge University Press, 2013.

[68] M. Ozawa, “Quantum measuring processes of continuous observables,” J. Math. Phys., 25: 79–87, 1984.

[69] M. Ozawa, “Uncertainty Relations for Noise and Disturbance in Generalized Quantum Measurements,” Annals of Physics, 311 (2), 350-416, 2004.

[70] F. Buscemi, M. Hall, M. Ozawa, M. Wilde, “Noise and disturbance in quantum measurements: an information-theoretic approach,” Physical review letters, 112 (5), 050401

[71] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, “Quantum error correction via codes over gf (4),” IEEE Transactions on Information Theory, vol. 44, no. 4, pp. 1369–1387, 1998.

[72] A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 3065–3072, 2001.

[73] A. Ketkar, A. Klappenecker, S. Kumar and P. Sarvepalli, “Nonbinary stablizer codes over finite fields,” IEEE Transactions on Information Theory, vol. 52, no. 11, pp. 4892–4914, 2006.

[74] M. Hayashi, Group Representation for Quantum Theory, Cham, Switzerland: Springer, 2017.

[75] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977.

[76] R. Lidl and H. Niederreiter, Finite Fields (2nd ed., Encyclopedia of Mathematics and its Applications), Cambridge: Cambridge University Press, 1996.

[77] R. C. Singleton, “Maximum distance q-nary codes,” IEEE Transactions on Information Theory, 10 (2): 116–118.

[78] L. H. Ozarow and A. D. Wyner, “Wire-tap channel II,” AT & T Bell Labs. Tech. J., vol. 63, pp. 2135 – 2157, 1984.

[79] N. Cai and R. W. Yeung, “Secure Network Coding on a Wiretap Network,” IEEE Trans. Inform. Theory, vol. 57, no. 1, 424–435, 2011.

[80] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels,” Physical Review Letters, 70(13):1895–1899, 1993.

[81] C. Bennett and S. Wiesner, “Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states,” Physical Review Letters, 69 (20): 2881, 1992.

[82] D. Boschi, S. Branca, F. De Martini, L. Hardy, and S. Popescu, “Experimental Realization of Teleporting an Unknown Pure Quantum State via Dual Classical and Einstein-Podolsky-Rosen Channels,” Physical Review Letters, 80 (6): 1121–1125, 1998.

[83] H. Krauter, D. Salart, C. A. Muschik, J. M. Petersen, Heng Shen, T. Fernholz, and E. S. Polzik, “Deterministic quantum teleportation between distant atomic objects,” Nature Physics, vol. 9, issue 7, pp. 400– 404, 2013.

[84] K. Mattle, H. Weinfurter, P. G. Kwiat, and A. Zeilinger, “Dense Coding in Experimental Quantum Communication,” Physical Review Letters, 76, 4656, 1996.

[85] B. P. Williams, R. J. Sadlier, and T. S. Humble, “Superdense Coding over Optical Fiber Links with Complete Bell-State Measurements,” Physical Review Letters, 118(5), 2017.

[86] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, “Entanglement-assisted classical capacity of noisy quantum channels,” Physical Review Letters, vol. 83, no. 15, p. 3081, 1999.

[87] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,” IEEE Transactions on Information Theory, vol. 48, no. 10, pp. 2637–2655, 2002.

[88] K. Wang and M. Hayashi, “Permutation Enhances Classical Communication Assisted by Entangled States,” Proc. 2020 IEEE Int. Symp. Information Theory (ISIT 2020), Los Angeles, California, USA, 2020.

[89] K. Banawan, B. Arasli and S. Ulukus, “Improved Storage for Efficient Private Information Retrieval,” 2019 IEEE Information Theory Workshop (ITW), Visby, Sweden, 2019.

[90] H. Lin, S. Kumar, E. Rosnes, A. G. i. Amat and E. Yaakobi, “The Capacity of Single-Server Weakly-Private Information Retrieval,” 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020.

[91] F. Kazemi, E. Karimi, A. Heidarzadeh and A. Sprintson, “Single-Server Single-Message Online Private Information Retrieval with Side Information,” 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019.

[92] S. Li, “Single-server Multi-message Private Information Retrieval with Side Information: the General Cases,” 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020.

[93] W. Chang and R. Tandon, “On the Upload versus Download Cost for Secure and Private Matrix Multiplication,” 2019 IEEE Information Theory Workshop (ITW), Visby, Sweden, 2019.

[94] Z. Wang, K. Banawan and S. Ulukus, “Private Set Intersection Using Multi-Message Symmetric Private Information Retrieval,” 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020.

参考文献をもっと見る

全国の大学の
卒論・修論・学位論文
を
一発検索！

この論文の関連論文を見る