Optimizing Confidential Database Queries on the Cloud

Abstract

The authors consider the PIR (Private Information Retrieval) problem to ensure secure requests to a database hosted on the cloud in the presence of an active adversary who does not interfere with the PIR protocol, but can carry out an attack with known open requests. To represent the bit number i as a number, all digits of which are different, the proposed algorithms use a base l number system with the number of digits d. The permutations of the digits of the requested bit number which are regarded as secret encryption keys were used. To reduce the communication complexity the bits of the source database stored on the cloud are grouped as arrays. A pseudorandom number sensor is used to replace the bit value depending on the number i requested by the client. This makes it difficult to match the bit value to a specific number in the case of collusion between a passive adversary located on the cloud and an active adversary outside the cloud. The communication complexity and the probability of guessing the bit number in a single attack with a known open query for bit number i, as well as in an attack with an unlimited number of known open queries, are estimated.