Private Information Retrieval with a Trusted Hardware Unit -- Revisited

    Lukasz Krzywiecki, Miroslaw Kutylowski, Hubert Misztela, Tomasz Struminski
                                      Wroclaw University of Technology

 During ISC'2008 Yanjiang Yang, Xuhua Ding, Robert H. Deng, and Feng Bao presented 
a construction for holding an encrypted database in a cloud so that the access pattern 
remains hidden. The scheme is based on a trusted hardware unit.  The unit serves as  
an interface between the owner of the database and the untrusted environment where the 
encrypted database is stored. The scheme is relatively efficient and has 
some provable privacy properties. 

In this paper we analyze the idealized version of the above protocol and prove rigorously
strong privacy conditions in a model with a powerful adversary observing all operations 
occurring in the cloud. On the other hand, we show that the full version of the protocol (with some 
implementation details),  as proposed at ISC'2008,  leaks some information about the access pattern. 
This shows that the protocol does not fulfil the property of ideally private information retrieval.
At some specific situations,   information leakage presented might have practical value for the adversary.