L3 · FUNCTIONALMEASURED

Encrypted Sorting

encrypted-sorting · spec v0.1.0 · 0 implementations · 6 runners

Create implementationSpecification

DESCRIPTION

Returns the elements of an encrypted array in ascending order.

A plaintext sort branches: it compares, then moves. Under encryption neither step is available — the comparison yields a ciphertext, and moving an element to a position determined by that ciphertext is itself a data-dependent access.

The workable shape is to compute, for each element, how many elements are smaller than it. That count is its destination index, it is obtained from pairwise differences passed through an approximate sign, and the permutation is then applied as an arithmetic combination rather than a move. The cost is quadratic in comparisons by construction, and every comparison is an approximation, so accuracy and depth compound.

An error here is not a small numeric error. A misplaced element is a wrong answer, which is why correctness is stated as a property of the permutation.

INTERFACE

encrypted_sort(
  in  ct     : Ciphertext  // an encrypted array of values
  out ct     : Ciphertext  // the same values in ascending order
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

value_countinteger1 – 2^16

max_valueinteger1 – 2^32

target_precisionnumber0.5 – 1

duplicates_presentbooleantrue, false

The schema belongs to the kernel. Each implementation declares which part of it it supports.

CORRECTNESS

01The output is a permutation of the input: every element present, none invented.

02The order is ascending, and it is correct for elements that are close together.

03Duplicates survive as duplicates, and the count of each value is preserved.

Sorting is judged on the permutation, not on average numeric error: one element in the wrong place is a wrong answer even if every value is numerically close.

SECURITY PROPERTIES

The permutation applied must not be observable. An implementation whose data movement depends on the comparisons has revealed the ordering it was hiding.

ASSUMPTIONS

The array is packed contiguously and its length is public.

REFERENCES

repoFHERMA participation guide

otherChallenge contributed by IBM Research