Efficient Ranking, Order Statistics, and Sorting under CKKS
Federico Mazzone
34th USENIX Security Symposium (USENIX Security '25) · Day 3 · Crypto 5: HE, MPC, Oblivious Computation
This talk, presented by Federico Mazzone from the University of Trento, introduces novel algorithms for efficiently performing ranking, order statistics, and sorting operations on encrypted data using the **CKKS (Cheon-Kim-Kim-Song)** homomorphic encryption scheme. In an era where privacy-sensitive data is increasingly processed in outsourced cloud environments, **homomorphic encryption (FHE)** offers a compelling solution by allowing computations to be performed directly on encrypted data without prior decryption. This eliminates the need for the server to ever see the plaintext, thereby preserving data confidentiality.
AI review
Mazzone delivers a genuine algorithmic contribution: constant comparison depth for ranking, order statistics, and sorting under CKKS, down from the prior O(log² N) state of the art. The core insight — encoding the input vector into two matrix structures so a single SIMD comparison yields all N² pairwise results simultaneously — is elegant and non-obvious. The scalability constraint (N ≤ √slots) is real and honestly disclosed.