Efficient Cryptographic Primitives for Private Data Mining

Data mining is frequently obstructed by privacy concerns. In many cases data is distributed, and bringing the data together in one place for analysis is not possible due to privacy laws (e.g. HIPAA) or policies. Privacy preserving data mining techniques have been developed to address this issue by providing mechanisms to mine the data while giving certain privacy guarantees. However, when these techniques are built on cryptographic primitives, while providing strong privacy, they are often too inefficient to be used in practical settings. To this end, we address the problem of efficiency by investigating trade-offs that can be made in the trust model. By making reasonable concessions in the trust model, that is, by adding a non-collaborative third party, we can achieve great gains in efficiency. We show this by creating a novel protocol for privately computing dot product, a foundational primitive for many private data mining activities. We also investigate how to extend our protocol in the case when a third party cannot be completely trusted by both participating parties, thus reducing the amount of trust needed in the third party. We then show experimentally the gains in efficiency that can be realized in the computation of the private dot product using this model.