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

This paper introduces a novel adaptation of counting sort that enables 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 leverages some basic operations on TFHE's Look-Up-Tables (LUT). We have integrated these operations into RevoLUT, a comprehensive open-source library built upon tfhe-rs, which can be of independent interest for oblivious algorithms. 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 5x faster than current 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-11-22: approved; 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}
}