Sorting is one of the most studied problems in computer science. Every language ships a built-in sort, and for most applications, picking the right one is a matter of performance. Quicksort, mergesort, pdqsort. They all produce the correct output. The main question is how fast they get there.
But there’s a class of applications where correctness and speed aren’t enough. When the data being sorted is sensitive, the sort itself can become a security vulnerability. Not because it produces the wrong result, but because an attacker who observes execution time can learn something about the data.
This is not theoretical. Post-quantum cryptosystems like Classic McEliece and NTRU Prime use sorting as a core subroutine, and if the sort leaks timing information, the entire cryptosystem is compromised.
There is, however, a family of algorithms that eliminates this problem entirely, and when implemented well, can even outperform traditional sorts.
Why sorting leaks information
Consider quicksort.
It picks a pivot, partitions the array around it, and recurses. Which pivot gets chosen, how the partitioning plays out, and how deep the recursion goes all depend on the values in the array. Different inputs produce different branch patterns, different memory access sequences, and different execution times.
An attacker who can measure execution time, even remotely over a network, can use those timing differences to deduce information about what’s being sorted. This is a timing side-channel attack.
The problem isn’t specific to quicksort. Any sort whose control flow depends on the data is vulnerable. Mergesort’s merge step branches on comparisons. Insertion sort’s inner loop length depends on how far each element needs to move. Even pdqsort, which combines several strategies, makes data-dependent decisions at every level.
What we need is a sort where the sequence of operations is completely fixed: determined only by the array length, never by the values. The same comparisons, the same memory accesses, the same number of instructions, regardless of whether the array contains [1, 2, 3] or [3, 1, 2] .
... continue reading