Attacking a privacy preserving music matching algorithm

Secure multi-party computation based techniques are often used to perform audio database search tasks, such as music matching, with privacy. However, in spite of the security of individual components of the matching schemes, the overall scheme may still not be secure. This paper explains how such flaws may occur, using a privacy preserving music matching problem as a template, and provides a solution, and analyzes the resulting tradeoff between privacy and computational complexity. Although the paper focus on a music matching application, the principles can be easily adapted to perform other tasks, such as speaker verification and keyword spotting.