A non comparison oblivious sort and its application to k-NN
Authors: Sofiane Azogagh (University of Quebec at Montreal), Marc-Olivier Killijian (University of Quebec at Montreal), Félix Larose-Gervais (University of Quebec at Montreal)
Volume: 2025
Issue: 3
Pages: 156–169
DOI: https://doi.org/10.56553/popets-2025-0093
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 4 times faster than state-of-the-art methods.
Keywords: Privacy, Homomorphic encryption, TFHE, Oblivious algorithm, Sort, Counting sort, k-Nearest Neighbors, Look-Up-Table
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
