# Safely sorting secret data

Suppose you have a secret list of n distinct integers. How would you sort this list in a way that is not vulnerable to timing attacks? I tried looking up "constant time sorting" and other related queries but that expectedly lead nowhere.

• Why not randomize the list before sorting? This way, you spoil the data which the attacker needs to do a timing attack. – workoverflow Jul 10 at 20:35
• @workoverflow That still presents the same problem. The naive algorithm for shuffling a list is not constant time but you can use the Fisher-Yates shuffle which would always have n swaps for a list of length n. However, since you are indexing into the list with some value, that value can be inferred by cache timing attacks. This would allow an attacker to extract the pre-order and therefore get information about the content of the list. – Kai Arakawa Jul 11 at 21:04
• @workoverflow the implementation of such an attack is very difficult (two timing attacks simultaneously) and AFAIK it would be unexplored territory. However, it is still important to minimize attack surfaces. – Kai Arakawa Jul 11 at 21:05

This takes $$O(n (\log n)^2)$$ time, which makes it not quite as fast as other sort algorithms; however if you want constant time/memory accesses, that's about the best we have.
The code on Wikipedia assumes that $$n$$ is a power of two; it is not hard to extend it to arbitrary $$n$$...
• Note that there are sorting networks that have size $O(n\log n)$, it is practically far preferable to use these $O(n\log^2 n)$ constructions because they're much simpler, much more readily available and don't have a gigantic constant hidden behind their $O$-notation. – SEJPM Jul 9 at 22:04