Capacity of Quantum Private Information Retrieval With Colluding Servers

被引:14
作者
Song, Seunghoan [1 ]
Hayashi, Masahito [1 ,2 ,3 ,4 ]
机构
[1] Nagoya Univ, Grad Sch Math, Nagoya, Aichi 4648602, Japan
[2] Southern Univ Sci & Technol, Shenzhen Inst Quantum Sci & Engn, Shenzhen 518055, Peoples R China
[3] Southern Univ Sci & Technol, Guangdong Prov Key Lab Quantum Sci & Engn, Shenzhen 518055, Peoples R China
[4] Southern Univ Sci & Technol, Shenzhen Key Lab Quantum Sci & Engn, Shenzhen 518055, Peoples R China
基金
日本学术振兴会;
关键词
Private information retrieval (PIR); symmetric information retrieval; quantum PIR (QPIR); capacity; collusion; information-theoretic security; CODES; COMMUNICATION;
D O I
10.1109/TIT.2021.3077269
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min{1, 2(n - t)/n} 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 greater than the classical counterpart.
引用
收藏
页码:5491 / 5508
页数:18
相关论文
共 50 条
[21]   Multi-value private information retrieval with colluding databases via trace functions [J].
Li, Yueting ;
Chang, Yanxun ;
Cheng, Minquan ;
Feng, Tao .
INFORMATION SCIENCES, 2021, 543 :426-436
[22]   Multiround Private Information Retrieval: Capacity and Storage Overhead [J].
Sun, Hua ;
Jafar, Syed Ali .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2018, 64 (08) :5743-5754
[23]   Bounds on the Capacity of Private Information Retrieval Over Graphs [J].
Sadeh, Bar ;
Gu, Yujie ;
Tamo, Itzhak .
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, 2023, 18 :261-273
[24]   The Capacity of Private Information Retrieval From Coded Databases [J].
Banawan, Karim ;
Ulukus, Sennur .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2018, 64 (03) :1945-1956
[25]   Quantum Anonymous Private Information Retrieval for Distributed Networks [J].
Khan, Awais ;
Khalid, Uman ;
Ur Rehman, Junaid ;
Shin, Hyundong .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2022, 70 (06) :4026-4037
[26]   Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography [J].
Kon, Wen Yu ;
Lim, Charles Ci Wen .
ENTROPY, 2021, 23 (01) :1-27
[27]   Prior entanglement exponentially improves one-server quantum private information retrieval for quantum messages [J].
Song, Seunghoan ;
Gall, Francois Le ;
Hayashi, Masahito .
EPJ QUANTUM TECHNOLOGY, 2024, 11 (01)
[28]   On the Storage Cost of Private Information Retrieval [J].
Tian, Chao .
2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2020, :1012-1017
[29]   The capacity of single-server weakly-private information retrieval [J].
Lin H.-Y. ;
Kumar S. ;
Rosnes E. ;
Graell I Amat A. ;
Yaakobi E. .
IEEE Journal on Selected Areas in Information Theory, 2021, 2 (01) :415-427
[30]   The Capacity of Private Information Retrieval From Heterogeneous Uncoded Caching Databases [J].
Banawan, Karim ;
Arasli, Batuhan ;
Wei, Yi-Peng ;
Ulukus, Sennur .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (06) :3407-3416