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

Sorting is a fundamental subroutine of many algorithms and as such has been studied for decades. A well-known result is the Lower Bound Theorem, which states that no comparison-based sorting algorithm can do better than O(nlog(n)) in the worst case. However, in the fifties, new sorting algorithms that do not rely on comparisons were introduced such as counting sort, which can run in linear time provided some auxiliary information, such as the domain of the data. In today’s world, where protecting sensitive data is crucial, we need algorithms that preserve privacy. Fully Homomorphic Encryption allows us to compute on encrypted data, but many classical algorithms need to be redesigned to work efficiently in this setting. We precisely address this challenge in this work by presenting the first comparison-free oblivious sorting algorithm specifically designed for encrypted data using FHE. By developing efficient blind read and write operations, built on TFHE’s Look-Up Tables (LUTs), we successfully adapt counting sort to the homomorphic setting. This removes the need for costly comparisons, which are among the most expensive operations in homomorphic computation. Using this sorting technique, we build an efficient, tournament-based, oblivious Top-k selection algorithm, and apply it to private k-Nearest Neighbors (k-NN) classification. Compared to previous works, our k-NN classifier achieves up to a 3x speedup.