L3 · FUNCTIONALMEASURED

Encrypted Nearest Neighbour Search

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

Create implementationSpecification

DESCRIPTION

Returns the indices of the k entries of a dataset closest to an encrypted query vector.

It combines two hard things. Distances are cheap — cosine similarity is a dot product, and encrypted arithmetic does dot products well. Selecting the smallest k is not: it is a partial sort, and every comparison inside it is an approximation of a discontinuous function.

The answer is a set of indices, which makes correctness discrete: a neighbour is either in the returned set or it is not, and no amount of numeric closeness rescues a wrong membership. Where two candidates are nearly equidistant, either may legitimately be returned, and a benchmark case has to say so.

INTERFACE

encrypted_knn(
  in  ct     : Ciphertext  // the encrypted query vector
  out ct     : Ciphertext  // the encrypted indices of the k nearest entries
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

dataset_sizeinteger1 – 2^24

dimensionsinteger1 – 2^12

kinteger1 – 2^10

metric_familyenumcosine, euclidean, inner-product

target_precisionnumber0.5 – 1

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

CORRECTNESS

01The returned indices are the k closest entries under the declared distance.

02Where candidates are equidistant within the declared precision, either may be returned and the case must say so.

03Exactly k indices come back, without repetition.

SECURITY PROPERTIES

The query stays hidden, and so does the result: which entries were returned must not be observable to the party holding the dataset.

ASSUMPTIONS

The dataset size, the dimensionality and k are public.

REFERENCES

repoFHERMA participation guide