Sommaire

  • Cet exposé a été présenté le 20 juin 2025 (11:00 - 12:00).

Description

  • Orateur

    Sofiane Azogagh - UQÀM

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

  • Users Pay Twice: The Hidden Energy Cost of Web Advertising

    • 04 décembre 2026 (11:00 - 12:00)

    • Inria Center of the University of Rennes - Room Petri/Turing

    Orateur : Samuel Pélissier - CentraleSupélec

    Advertisements are everywhere on the Web: search engines promote results, most websites display ads, some require users to accept ads as a condition for access, video streaming services fund their infrastructure through an increasing volume of ads, and much of the gaming industry has adopted ad-based revenue models. In exchange for free access to a wide range of content, web users sacrifice their[…]
    • Privacy

Voir les exposés passés