Efficient hardware-based private information retrieval using partial reshuffle

The paper proposes a novel hardware-based private information retrieval(HWPIR)protocol.By partially reshuffling previously accessed items in each round,instead of frequently reshuffling the whole database,the scheme makes better use of shuffled data copies and achieves the computation overhead at O(√N/k),where N and k are the sizes of the database and secure storage respectively.For.secure storage with moderate size,e.g.k=O(√N),the overhead is O(4√N).The result is much better than the state-of-art schemes(as compared to e.g.O(log2N)).Without increasing response time and communication cost,the proposed protocol is truly practicable regardless of the database size.The security and preformance of the protocol is formally analyzed.