Beyond Privacy: Deception in Information Retrieval

We introduce the problem of deceptive information retrieval (DIR) which is a conceptual extension of private information retrieval (PIR). In DIR, the user downloads a required file out of multiple files stored in a system of databases and reveals information about a different file as what was required, to the databases. In other words, the user deceives the databases in an information retrieval system by making the databases' prediction on the user-required file index incorrect with high probability. The metric of deception is defined as the prediction error probability at the databases minus the corresponding error probability of PIR. We propose a scheme to perform DIR on a system of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> non-colluding databases storing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> time-sensitive files, that achieves a given level of deception required, with the goal of minimizing the download cost. This scheme utilizes the time dimension present in time-sensitive (constantly updating) files to send both real and dummy queries at distinct time instances to download the required file correctly while also deceiving the databases. The proposed scheme incurs higher download costs compared to PIR for positive levels of deception required, and achieves the PIR capacity when the level of deception specified is zero.