L3 · FUNCTIONALMEASURED

Encrypted Lookup

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

Create implementationSpecification

DESCRIPTION

Returns A[i] where the array A and the index i are both encrypted.

There is no addressing under encryption: nothing can jump to a slot chosen by data nobody can read. A realization therefore touches every element and combines them so that only the selected one survives — a selection vector, a polynomial that vanishes everywhere else, or a programmable bootstrap. The cost is linear in the array by construction, and the competition is over the constant.

This is the primitive behind encrypted table lookup, and by extension behind evaluating arbitrary functions of small integers by tabulating them.

INTERFACE

encrypted_lookup(
  in  ct     : Ciphertext  // the encrypted array A
  in  ct_i   : Ciphertext  // the encrypted index i
  out ct     : Ciphertext  // the encrypted value at the selected position
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

array_lengthinteger1 – 2^20

max_valueinteger1 – 2^32

index_encryptedbooleantrue, false

target_precisionnumber0.5 – 1

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

CORRECTNESS

01The output encodes the element at the requested position, for every position in range.

02The answer is correct for all indices, not only the ones a test happens to sample.

03Out-of-range indices have defined behaviour, stated by the implementation.

SECURITY PROPERTIES

The requested position must not be observable — not through timing, not through which memory is touched. An implementation that reads only the selected element has leaked it.

ASSUMPTIONS

The array is packed contiguously and its length is public.

REFERENCES

repoFHERMA participation guide