H. Seo, H. Lee and W. Choi, "Fundamental Limits of Private Information Retrieval With Unknown Cache Prefetching," in IEEE Transactions on Communications, vol. 69, no. 12, pp. 8132-8144, Dec. 2021, doi: 10.1109/TCOMM.2021.3117936
Fundamental limits of private information retrieval with unknown cache prefetching
|Author:||Seo, Hyowoon1; Lee, Hojung2; Choi, Wan3|
1Centre for Wireless Communications, University of Oulu, 90014 Oulu, Finland
2chool of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon 34141, South Korea
3Department of Electrical and Computer Engineering, Institute of New Media and Communications, Seoul National University (SNU), Seoul 08826, South Korea
|Online Access:||PDF Full Text (PDF, 0.9 MB)|
|Persistent link:|| http://urn.fi/urn:nbn:fi-fe2022012811131
Institute of Electrical and Electronics Engineers,
|Publish Date:|| 2022-01-28
The fundamental limits of private information retrieval (PIR) with unknown cache prefetching at the user are investigated in this paper. To this end, a novel random linear combination (RLC)-based PIR scheme that can solve the basic PIR problem and its variation is proposed. The proposed scheme is based on random coding approach and achieves the capacity of the basic PIR asymptotically. Then, we investigate PIR with unknown cache prefetching (PIRC) problem at different cache-to-file size ratio. Specifically, we propose RLC-based PIRC method, which prefetches RLC-based side information and leverages them to retrieve desired information at small download cost. Furthermore, by applying time and memory sharing on the proposed RLC-based PIRC, RLC-based basic PIR and some other known approach in literature, we derive the achievable normalized download cost bound of PIRC. The derived achievable bound outperforms the existing bound in literature and the case study provides numerical results that verifies it.
IEEE transactions on communications
|Pages:||8132 - 8144|
|Type of Publication:||
A1 Journal article – refereed
|Field of Science:||
113 Computer and information sciences
This research was supported in part by the Ministry of Science and ICT (MSIT), Korea, under the Information Technology Research Center (ITRC) support program (IITP-2020-0-01787) supervised by the Institute of Information & Communications Technology Planning & Evaluation (IITP) and in part by the Ministry of Science and ICT (MSIT), Korea, under the Information Technology Research Center (ITRC) support program (IITP 2021-0-02048) supervised by the Institute of Information & Communications Technology Planning & Evaluation (IITP). This article was presented at the IEEE Wireless Communications and Networking Conference (WCNC), Barcelona, Spain, April 2018 [DOI: 10.1109/WCNC.2018.8377372].
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.