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.
Prochains exposés
-
Opening Pandora's Box: White-Box Attacks on Microsoft's PhotoDNA Perceptual Hash Function
Orateur : Diane Leblanc-Albarel - KU Leuven
PhotoDNA is a widely deployed perceptual hash function used for the detection of illicit content such as Child Sexual Abuse Material (CSAM). In this talk, I will present our paper introducing the first mathematical description of Alleged PhotoDNA, a function that reproduces the outputs of PhotoDNA. Our analysis reveals several structural weaknesses: the function is piece-wise linear and[…]-
Cryptography
-
Privacy
-
-
Towards More Secure Large Language Models
Orateur : Raouf Kerkouche - Inria Lille
Large Language Models (LLMs) have achieved considerable success and are now widely used across multiple domains, highlighting their transformative impact on both technology and society. However, this widespread adoption also exposes LLMs to numerous security threats that can alter model behavior or degrade overall performance. To mitigate these threats, most research has focused on alignment[…]-
Machine learning
-