L3 · FUNCTIONALMEASURED

Encrypted Substring Search

encrypted-substring-search · spec v0.1.0 · 0 implementations · 6 runners

Create implementationSpecification

DESCRIPTION

Reports where an encrypted pattern occurs in a text.

The asymmetry is the point: the text is typically public and large, the pattern is small and secret. Nothing about the pattern — not its contents, not the positions it matched — may be observable, which rules out every classical string algorithm, since all of them skip ahead based on what they have just compared.

What remains is to evaluate a match predicate at every position and combine the results, so the work is proportional to the text regardless of whether the pattern occurs at all. That is not a weakness of a particular realization; it is what privacy costs here.

INTERFACE

encrypted_substring_search(
  in  ct     : Ciphertext  // the encrypted pattern to look for
  out ct     : Ciphertext  // the encrypted match result — positions, or a count
  ...               // anything else the realization needs — keys, context, encoding — is its own concern
)

PARAMETER SCHEMA

NAMETYPERANGE

text_lengthinteger1 – 2^24

pattern_lengthinteger1 – 2^12

alphabet_sizeinteger2 – 2^16

text_encryptedbooleantrue, false

target_precisionnumber0.5 – 1

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

CORRECTNESS

01Every occurrence of the pattern is reported, and nothing else is.

02Overlapping occurrences are handled as declared, and the declaration is part of the answer.

03A pattern that does not occur produces an answer indistinguishable in cost from one that does.

SECURITY PROPERTIES

Neither the pattern nor the matched positions may be observable, including through how long the search takes. Work proportional to the text is therefore a requirement, not an inefficiency.

ASSUMPTIONS

The length of the text is public; the length of the pattern may or may not be.

REFERENCES

repoFHERMA participation guide

otherChallenge contributed by IBM Research