Helger Lipmaa's publications

On Private Similarity Search Protocols

Sven Laur and Helger Lipmaa. On Private Similarity Search Protocols. In Sanna Liimatainen and Teemupekka Virtanen, editors, Proceedings of the 9th Nordic Workshop on Secure IT Systems (NordSec 2004), pages 73--77, Espoo, Finland, November 4--5, 2004. ISBN 951-22-7348-9.

File: [.ps.bz2 (98 KB), .pdf (155 KB)] pdf recommended.


In a private similarity search (PSS) protocol, a client receives from the database the entry, closest to her query, without either the client or the database getting to know more information than necessary. PSS protocols have potentially wide application in areas like bioinformatics, where precise queries might be impossible. We show that the previously proposed PSS protocols by Du and Atallah have serious weaknesses; in particular, some of their protocols can be broken by a semi-honest third party who observes a relatively small amount of traffic. In several cases, we show that even maximally securified versions of these protocols---when used as proposed by Du and Atallah---are not private in the sense, needed in the practice. We propose a few protocols that are better from the privacy viewpoint, but none of the proposed protocols is really efficient.

Keywords: Cryptanalysis, cryptographic protocols, privacy-preserving data-mining, private similarity search.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.