Description
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.
Next sessions
-
CHERIoT RTOS: An OS for Fine-Grained Memory-Safe Compartments on Low-Cost Embedded Devices
Speaker : Hugo Lefeuvre - The University of British Columbia
Embedded systems do not benefit from strong memory protection, because they are designed to minimize cost. At the same time, there is increasing pressure to connect embedded devices to the internet, where their vulnerable nature makes them routinely subject to compromise. This fundamental tension leads to the current status-quo where exploitable devices put individuals and critical infrastructure[…]-
SoSysec
-
Compartmentalization
-
Operating system and virtualization
-
Hardware/software co-design
-
Hardware architecture
-