Compacting privacy-preserving k-nearest neighbor search using logic synthesis

TitleCompacting privacy-preserving k-nearest neighbor search using logic synthesis
Publication TypeConference Paper
Year of Publication2015
AuthorsSonghori, E., S. U. Hussain, A. - R. Sadeghi, and F. Koushanfar
Conference NameDesign Automation Conference (DAC)
Date PublishedJune, 2015
KeywordsData Mining, Garbled Circuit, k-NN, Logic Design, Logic Synthesis, Nearest Neighbor, Privacy-Preserving, Secure Function Evaluation

This paper introduces the first efficient, scalable, and practical method for privacy-preserving k-nearest neighbors (kNN) search. The approach enables performing the widely used k-NN search in sensitive scenarios where none of the parties reveal their information while they can still cooperatively find the nearest matches. The privacy preservation is based on the Yao’s garbled circuit (GC) protocol. In contrast with the existing GC approaches that only accept function descriptions as combinational circuits, we suggest using sequential circuits. This work introduces novel transformations, such that the sequential description can be evaluated by interfacing with the existing GC schemes that only accept combinational circuits. We demonstrate a great effi- ciency in the memory required for realizing the secure k-NN search. The first-of-a-kind implementation of privacy preserving k-NN, utilizing the Synopsys Design Compiler on a conventional Intel processor demonstrates the applicability, efficiency, and scalability of the suggested methods.

secure-knn.pdf342.51 KB


Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer