Skip to section
Foundationsfor rotation-free search
Section 17 of 5233% of course
Contents
Chapter 3 Section 3.4 65 min

Part II · The problem and its constraints

What must remain private—and from whom

Draw the trust boundary before selecting cryptographic machinery.

Privacy begins with a clear threat model

“Private search” is dangerously incomplete until we ask: private from whom, at which time, and for which data? A threat model is simply an explicit, written answer to those exact questions. Our design has a client, a scoring server, stored corpus material, and returned score material.

For each asset, ask who may see it in plaintext. The query expresses the user’s sensitive interest. The corpus may contain highly proprietary or personal records. Scores can reveal which records align with the query. The secret key can reveal absolutely every protected value under that key. These assets are definitely not interchangeable, so saying “the data is encrypted” is far too vague to be useful.

trusted clientquery · secret key · decrypted scores · ranking
encrypted request ⇄ encrypted response
untrusted scoring serverevaluation data · ciphertext arithmetic · no secret key

The two modes solve very different problems

Query-private mode protects the user’s request from a server that is fully allowed to know the corpus. Encrypted-corpus mode additionally protects the corpus values during scoring, but it absolutely requires the corpus and query to be compatible under one single keying arrangement. The second mode is not merely “more private”; it completely changes storage, multiplication, key management, and operational trust.

Worked example

Name the observer

“The query is private” could mean private from the network, from the scoring operator, from other tenants, or even from the client machine’s administrator. FHE specifically addresses the scoring operator’s inability to read protected values during evaluation. Transport security, tenant isolation, endpoint security, and organizational policy still have to address the other observers.

Why the result list stays client-side

If the server learned which item ultimately won, access patterns could easily reveal the query even when the query ciphertext remained entirely opaque. Returning encrypted scores lets the client decrypt, rank, and choose the winners completely outside the scoring server's view.

Check your understanding

Why not just ask the scoring server to return only the winning plaintext identifier?

Threat-model check

Does encrypting the query automatically hide how often one client sends requests?

Section summary

  • The client strictly owns the secret key and final ranking.
  • The server evaluates without ever reading protected values.
  • Query-private and encrypted-corpus modes have entirely different multiplication shapes.
  • Encryption is only one part of a much larger privacy story.

Repository layer · second pass

Which party may learn which value at each boundary?

Privacy is a data-flow property. Name the client, corpus owner, scoring service, accelerator, and any observer; then list what each party receives, computes, retains, and returns. “Encrypted” is not a complete threat model because sizes, access frequency, timing, and final winners may still be visible.

In the intended boundary, the scoring side operates on encrypted query material and does not receive the secret key. The client decrypts scores and ranks locally, preventing the server from learning the winning corpus identifiers from plaintext results.

Reasoning chain

  1. 1

    Inventory assets: query, corpus vectors, scores, identifiers, keys.

  2. 2

    Assign an owner and authorized readers.

  3. 3

    Draw every transfer.

  4. 4

    Mark metadata that encryption does not hide.

  5. 5

    State collusion and compromise assumptions explicitly.

Worked trace

The result can be sensitive too

  1. A private query is encrypted.
  2. The server computes all scores without decryption.
  3. If the server learns the winning medical document ID, it may infer the topic.
  4. Returning encrypted scores lets the client rank privately.

Result. Protecting inputs alone does not necessarily protect access results.

Executable lens · Python

Make the hidden state visible

assets = {
  "query": {"client"},
  "secret_key": {"client"},
  "plaintext_scores": {"client"},
  "ciphertext_scores": {"client", "server"},
}
assert "server" not in assets["secret_key"]

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Equating transport encryption with computation privacy.
  • Ignoring identifiers and traffic patterns because vector values are encrypted.

Retrieval and transfer

Close the book first

  1. Draw a boundary for outsourced search with a separate corpus owner.
  2. Name three metadata channels left visible.
  3. Explain what changes if client and corpus owner are different parties.