Improvement of preprocessing complexity in private information retrieval

Abstract

The increasing model of e-commerce infrastructure opens the door for secure transaction of information over Internet, keeping some records private as users' choice within a few seconds. A user while frequently retrieves his records seldom wish to hide the identity of the record to the database server. Private Information Retrieval (PIR) protocols are such protocols that allow users to retrieve information from a database while keeping their query private. In many e-commerce applications, such as e-commerce, patent database, pharmaceuticals database, media database, ethical hacking, bioinformatics and digital library are vastly used fields of PIR protocol. The performance of existing protocols depends on communication and computational complexities. In some PIRs the computational complexity is reduced to 0(1), and optimal, but still holds high communication complexity O(NJ. Where N; is the total number of records in the database server. This research introduces a new PIR protocol namely PIR with p-cache based on the concept of database caching technology. A client is assigned a private account called P-cache account protected by his private key, holding the recently accessed query records. The P-cache is hash indexed and updated using the Least Recently Used (LRU) algorithm. In average case, whenever a client requests a query in the system, there is high probability to satisfy it from the p-cache instead to access in the main database server that contains huge amounts of records. As the cache is hash indexed the complexity is significantly reduced from O(Ns) tQ 0(1) in average. The protocol has been evaluated by using randomly generated three schemas (Stdlnfo joined with Books in Digital Library System, CustInfo joined with Products in PIR based Electronic Payment System and Voterlnfo schema in the PIR based voting system) and compared with the existing protocols. Experimental results show that the proposed protocol is more realistic and faster then the previous protocols in terms on computational and communication complexity.