On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information
We consider the problem of Private Information Retrieval with Private Side Information (PIR-PSI), wherein the privacy of the demand and the side information are jointly preserved. Although the capacity of the PIR-PSI setting is known, we observe that the underlying capacity-achieving code constructi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-09-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/23/10/1287 |
| _version_ | 1827679600153460736 |
|---|---|
| author | Murali Krishnan K. H. Jagadeesh Harshan |
| author_facet | Murali Krishnan K. H. Jagadeesh Harshan |
| author_sort | Murali Krishnan K. H. |
| collection | DOAJ |
| description | We consider the problem of Private Information Retrieval with Private Side Information (PIR-PSI), wherein the privacy of the demand and the side information are jointly preserved. Although the capacity of the PIR-PSI setting is known, we observe that the underlying capacity-achieving code construction uses Maximum Distance Separable (MDS) codes therefore contributing to high computational complexity when retrieving the demand. Pointing at this drawback of MDS-based PIR-PSI codes, we propose XOR-based PIR-PSI codes for a simple yet non-trivial setting of two non-colluding databases and two side information files at the user. Although our codes offer substantial reduction in complexity when compared to MDS-based codes, the code-rate marginally falls short of the capacity of the PIR-PSI setting. Nevertheless, we show that our code-rate is strictly higher than that of XOR-based codes for PIR with no side information. As a result, our codes can be useful when privately downloading a file especially after having downloaded a few other messages privately from the same database at an earlier time-instant. |
| first_indexed | 2024-03-10T06:34:35Z |
| format | Article |
| id | doaj.art-4f079bbb71b74bd2a01c802ec521c1e5 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T06:34:35Z |
| publishDate | 2021-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-4f079bbb71b74bd2a01c802ec521c1e52023-11-22T18:10:41ZengMDPI AGEntropy1099-43002021-09-012310128710.3390/e23101287On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side InformationMurali Krishnan K. H.0Jagadeesh Harshan1Bharti School of Telecom Technology and Management, Indian Institute of Technology Delhi, New Delhi 110016, IndiaDepartment of Electrical Engineering, Indian Institute of Technology Delhi, New Delhi 110016, IndiaWe consider the problem of Private Information Retrieval with Private Side Information (PIR-PSI), wherein the privacy of the demand and the side information are jointly preserved. Although the capacity of the PIR-PSI setting is known, we observe that the underlying capacity-achieving code construction uses Maximum Distance Separable (MDS) codes therefore contributing to high computational complexity when retrieving the demand. Pointing at this drawback of MDS-based PIR-PSI codes, we propose XOR-based PIR-PSI codes for a simple yet non-trivial setting of two non-colluding databases and two side information files at the user. Although our codes offer substantial reduction in complexity when compared to MDS-based codes, the code-rate marginally falls short of the capacity of the PIR-PSI setting. Nevertheless, we show that our code-rate is strictly higher than that of XOR-based codes for PIR with no side information. As a result, our codes can be useful when privately downloading a file especially after having downloaded a few other messages privately from the same database at an earlier time-instant.https://www.mdpi.com/1099-4300/23/10/1287private information retrievaljoint privacyprivacy with side informationXOR-based codes |
| spellingShingle | Murali Krishnan K. H. Jagadeesh Harshan On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information Entropy private information retrieval joint privacy privacy with side information XOR-based codes |
| title | On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information |
| title_full | On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information |
| title_fullStr | On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information |
| title_full_unstemmed | On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information |
| title_short | On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information |
| title_sort | on the existence of xor based codes for private information retrieval with private side information |
| topic | private information retrieval joint privacy privacy with side information XOR-based codes |
| url | https://www.mdpi.com/1099-4300/23/10/1287 |
| work_keys_str_mv | AT muralikrishnankh ontheexistenceofxorbasedcodesforprivateinformationretrievalwithprivatesideinformation AT jagadeeshharshan ontheexistenceofxorbasedcodesforprivateinformationretrievalwithprivatesideinformation |