L3 · FUNCTIONALMEASURED

Encrypted Set Membership

encrypted-set-membership · spec v0.1.0 · 0 implementations · 6 runners

Create implementationSpecification

DESCRIPTION

Returns whether an encrypted element is a member of a set.

The answer is one bit, and the entire difficulty is delivering that bit and no more. A realization that reveals which entry matched has answered a bigger question than the one asked, and in the screening use case that difference is the whole product.

The set may be public or encrypted, and the two cases have different costs but the same contract. Where the set is large, the practical shape is a polynomial that vanishes precisely on its members, or a hashed encoding that trades exactness for size — in which case the false-positive rate becomes part of correctness rather than an implementation detail.

INTERFACE

encrypted_set_membership(
  in  ct     : Ciphertext  // the encrypted element to test
  out ct     : Ciphertext  // the encrypted answer: member or not
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

set_sizeinteger1 – 2^24

universe_sizeinteger2 – 2^32

set_encryptedbooleantrue, false

false_positive_ratenumber0 – 0.5

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

CORRECTNESS

01A member is reported as a member; a non-member is reported as a non-member, within the declared false-positive rate.

02False negatives are not permitted at any rate — a missed member is a failed screening.

03The answer is a single bit; which element matched is not part of it.

SECURITY PROPERTIES

The queried element stays hidden from the party holding the set, and the set stays hidden from the querier where it is encrypted. Matching position must not leak through timing.

ASSUMPTIONS

The size of the set is public.

REFERENCES

repoFHERMA participation guide