Repudiative information retrieval
Dmitri Asonov, Johann-Christoph Freytag · 2002
Privacy is preserved while retrieving an i-th record from the database of N records if no information is revealed about i, not even to the database server. Repudiation is preserved in the same model if no one can prove, even in cooperation with the server, that a record retrieved is or is not the j-th record for any 1 ≤ j ≤ N. The first problem is called PIR, and we call the second problem the RIR problem.State of the art PIR protocols with optimal query response time and optimal communication require heavy periodical preprocessing. O(N log N) I/O's are required for preprocessing before answering a query.In this paper, we reduce preprocessing complexity by weakening PIR to RIR. In particular, we propose a RIR protocol with optimal query response time and communication, and O (√N) preprocessing per query.