Cryptanalysis of a Fast Private Information Retrieval Protocol

A private information retrieval (abbreviated as PIR) protocol deals with the schemes that allow a user to retrieve privately an element of a non-replicated database. The security of PIR protocol is that the user wants to retrieve information in a database without the database knowing which information has being retrieved. This is widely applied in medical files, video or songs databases or even stock exchanges share prices. At ISIT 2008, Carlos Aguilar Melchor and Philippe Gaborit presented a lattice-based PIR protocol, whose security based on problems close to coding theory problems known to be NP-complete. In this paper, we present a practical attack on this PIR protocol when the number of elements in the database is not big. More specifically, we can firstly uncover the hidden linear relationship between the public matrices and noisy matrices, and then propose an efficient dimension-reduced attack to locate the index of the element which the user retrieved.