A non-comparison oblivious sort and its application to private k-NN

Sofiane Azogagh; Marc-Olivier Killijian; Félix Larose-Gervais

Paper 2024/1894

A non-comparison oblivious sort and its application to private k-NN

Sofiane Azogagh, University of Quebec at Montreal

Marc-Olivier Killijian

, University of Quebec at Montreal

Félix Larose-Gervais, University of Quebec at Montreal

Abstract

In this paper, we introduce an adaptation of the counting sort algorithm that leverages the data obliviousness of the algorithm to enable the sorting of encrypted data using Fully Homomorphic Encryption (FHE). Our approach represents the first known sorting algorithm for encrypted data that does not rely on comparisons. The implementation takes advantage of some basic operations on TFHE's Look-Up-Tables (LUT). We have integrated these operations into RevoLUT, a comprehensive open-source library built on tfhe-rs. We demonstrate the effectiveness of our Blind Counting Sort algorithm by developing a top-k selection algorithm and applying it to privacy-preserving k-Nearest Neighbors classification. This proves to be approximately 5 times faster than state-of-the-art methods.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: Privacy Homomorphic encryption TFHE Oblivious algorithm Sort k-Nearest Neighbors Look-Up-Table
Contact author(s): azogagh sofiane @ courrier uqam ca
killijian marc-olivier 2 @ uqam ca
larose-gervais felix @ courrier uqam ca
History: 2024-12-05: last of 2 revisions; 2024-11-21: received; See all versions
Short URL: https://ia.cr/2024/1894
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1894,
      author = {Sofiane Azogagh and Marc-Olivier Killijian and Félix Larose-Gervais},
      title = {A non-comparison oblivious sort and its application to private k-{NN}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1894},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1894}
}