Encrypted Sort

Definition

Encrypted sort reorders a collection of encrypted values into a fixed order without revealing the individual values.

Given an encrypted vector

the result is an encrypted vector $y$ that holds the same multiset of values in non-decreasing order:

for some permutation $\pi$. The output is a rearrangement of the input — no value is created, dropped, or altered beyond the numerical error of the scheme.

Mathematical Domain

Sorting is defined over a totally ordered element domain. The comparison that defines the order, the numeric type of the elements, and the direction of the ordering are properties of the domain, not of the kernel.

Because the data is encrypted, the ordering must be produced without branching on the secret values. A specification therefore typically requires the computation to be data-oblivious: the sequence of operations (the comparison network) is fixed in advance and independent of the values being sorted, so the control flow leaks nothing about the input.

The kernel does not fix the element domain, the cryptographic scheme, the length N, the ordering direction, or the correctness tolerance. These are defined by individual specifications.

Parameters Defined by Specifications

A specification narrows the general sort into a concrete computational problem by defining, for example:

• the element domain and cryptographic scheme;
• the length N;
• the ordering direction (non-decreasing unless stated otherwise);
• the input and output representation;
• exact or approximate correctness and, when approximate, the accuracy tolerance;
• whether the comparison network must be data-oblivious.

Applications

Sorting over encrypted data underpins private ranking and leaderboards, order-statistics such as median and percentiles, top-k selection, encrypted database ORDER BY, and preprocessing steps in privacy-preserving analytics and machine learning.