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 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.

Automated summary

In this work, we consider the problem of Private Information Retrieval with Private Side Information (PIR-PSI) and propose XOR-based PIR-PSI codes as an alternative to MDS-based codes, offering lower complexity but slightly lower rate than the capacity setting. Nevertheless, we show that our code-rate is strictly higher than that of XOR-based codes for PIR with no side information, making it particularly useful when downloading a file privately after having downloaded other messages from the same database earlier.