The Server Reads Every Byte and Understands None of It

A server can answer a question about your encrypted data without learning what you asked. It does not manage this by skipping the parts you did not want. It reads every byte it holds, on every query — and understands none of it. The blindness is bought with the exhaustive read.

That result is a theorem, not a benchmark. Amos Beimel, Yuval Ishai and Tal Malkin proved it for private information retrieval — the problem of fetching record i without the database operator learning i. Their paper, presented at CRYPTO 2000 and published in the Journal of Cryptology in 2004, says it in one line: "We show that in the standard PIR model, where the servers hold only the database, linear computation cannot be avoided."¹

Two decades later, the authors of the fastest single-server scheme in the field repeat it as a design constraint. Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn and Vinod Vaikuntanathan write that "the server must touch every bit of the database to answer even a single client query."²

The result, stated precisely

In the standard model, where a server holds only the database, a private query cannot be answered with less than linear server work. If the server skipped a record, the skip itself would be a signal about what you wanted. Beimel, Ishai and Malkin give the reason in one sentence, and it carries the whole argument.

"if the server does not read xᵢ in response to some query, it knows that the user is not interested in xᵢ, violating the user's privacy."³

Reading everything is how the server says nothing.

The exhaustive scan is not a performance failure awaiting better engineering — it is the mechanism. A server that reads selectively has already learned something, because which bytes it chose to read is itself a message.

The alternative was known from the start, and it was absurd. Benny Chor, Oded Goldreich, Eyal Kushilevitz and Madhu Sudan opened the field in 1995 by naming the risk plainly: "a curious database operator can follow the user's queries and infer what the user is after."⁴

Their baseline for perfect privacy against a single server was to download the whole thing — "namely n bits should be communicated."⁵ Private information retrieval is the trade that replaces your download with the server's scan.

What the blindness costs, in measured numbers

The cost appears as throughput, and the ceiling is physics rather than cryptography. Because the algorithm is to read all of it, the fastest any scheme can run is the speed at which a server pulls the database out of memory. SimplePIR's authors measured that limit, then built a scheme that nearly reaches it.

Their per-query work is stated per byte of database, not per record: "the SimplePIR server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte."⁶

Every byte. Every query. That phrase is the tell.

The authors name the read itself as the limit: "a hard limit on the throughput of PIR schemes ... is the speed with which the PIR server can read the database from memory: roughly 12.4 GB/s/core on our machine."⁷

Note the third row — the client pays too. To query a 1 GB database, "the client must download a 121MB 'hint' about the database contents; thereafter, the client may make an unbounded number of queries, each requiring 242 KB of communication."⁸ Their second scheme shrinks that hint to 16 MB and raises the per-query cost to 345 KB.⁸

Why a lookup works and a conversation does not

Fetching a record is a fixed-size operation. A conversation is not. Computing on ciphertext requires the work to be expressed as a circuit of statically known shape, which rules out ordinary software machinery — variable-length data, data-dependent branching, loops sized by their input. That constraint, not the overhead, separates a caller-ID lookup from a chat with a folder of prose.

Jeremy Kun, who worked on Google's homomorphic-encryption compiler, listed the constraints in a 2023 primer. In that compiler "all loops must be fully unrolled and have statically-known bounds"; "all control flow is multiplexed, meaning that all branches of all if statements are evaluated, and only then is one chosen"; and "all data needs to have static sizes," with "pointers, and dynamic memory allocation are not supported."⁹

His sharpest illustration is a string comparison. Running it on a short input and on a long one takes the same time, because "the program processes all MAX_LENGTH characters without knowing if they are null bytes."¹⁰ That is the thesis at the scale of one function — data-independent runtime is the privacy. A program that finished early would have announced that the string was short.

The shape is the constraint. The overhead is only the bill.

One number from that primer travels badly, so state it correctly. Encrypting a 100×100 greyscale image "will cost you 218 MiB to store all the pixels in memory. It's roughly a 20,000x overhead," because in the bit-level scheme described there, "Each encryption of a single bit corresponds to a list of roughly 700 32-bit integers."¹¹ That is a storage ratio for one scheme — not a speed ratio. Repeating it as "20,000× slower" changes the claim.

What is actually shipping today

One consumer deployment is documented by its vendor as shipped, not announced. Apple's support document states that "Starting in iOS 18, iPadOS 18, and macOS Sequoia, Enhanced Visual Search lets you search your photo library for landmarks or points of interest in photos or videos" — and adds a limit in the same breath.

"Enhanced Visual Search isn't available in all countries or regions."¹²

The mechanism is the one described above, applied to a lookup. An on-device model produces "a low-fidelity mathematical representation" of the part of a photo that might contain a landmark, and Apple is precise about what travels: "This embedding — not image data — is encrypted and sent to Apple servers ... The decryption keys remain on your device, so that Apple servers can't decrypt the encrypted embedding or search result."¹³

Apple's research write-up states the same guarantee for the search itself: "the server does not learn the client's private embedding or the retrieved results."¹⁴ The library behind it is public — apple/swift-homomorphic-encryption, created on 17 June 2024 under Apache-2.0.¹⁵

What is not shipping is the thing most people picture. Google's own engineering post sets encrypted inference as a goal rather than a state: "Our vision is to make HEIR a one-click solution to enable non-experts to incorporate encrypted inference into production applications."¹⁶ A vision is not a feature. What ships is a lookup.

The guarantee is narrower than it sounds

Three qualifications belong on every claim in this piece. The cryptography covers one path, in one direction, at a cost in fidelity. Read the shipped deployment closely and each qualification appears in the vendor's own design decisions rather than in anyone's critique of them.

It is not treated as sufficient on its own. Apple layers differential privacy on top, "with ε = 0.8, δ = 10⁻⁶", has the client issue "fake queries alongside its real ones," and routes traffic through an OHTTP relay "operated by a third party — as an anonymization network."¹⁷ If encryption alone answered the question, none of those layers would need to exist.

It costs fidelity. The embedding "is quantized to 8-bit precision before being encrypted" to meet the latency and cost requirements of a large-scale production service.¹⁸ Precision is one of the currencies this is paid in.

It runs one way. Google's post frames the motivation from the provider's side: "Shipping proprietary AI to a device risks leaking the model."¹⁹ Encrypting your input is what lets the model stay on someone else's servers. The protection is real, and asymmetric by design.

The scope is a feature, not a slogan.

Encryption is not consent

A cryptographic guarantee says nothing about whether you agreed to the transaction. The clearest statement of that gap came from the developer who found the feature. Jeff Johnson wrote on 28 December 2024 that, going through his iPhone settings, he "discovered a new setting for Photos that was enabled by default: Enhanced Visual Search."²⁰

His objection was not to the mathematics, and he said so: "I'm not claiming that Apple's privacy protection technology is flawed."²¹ The argument he made instead is the one worth keeping — "Technology is never a substitute for consent," and "There's more to privacy than just secrecy; privacy also means ownership."²¹

Thomas Claburn, reporting for The Register on 3 January 2025, recorded the same fact in the same terms: the feature was enabled "by default, seemingly without explicit consent."²²

Two different properties. One is whether a server can read your data. The other is whether you chose to send it.

The caveats, and what would change them

The honest counter-argument is that these numbers are falling fast, and Jeremy Kun makes it himself. Homomorphic encryption, he writes, "shifts the capability/privacy trade-off to a question of cost. And the cost of homomorphic encryption is rapidly decreasing."²³ He also wrote the 2023 primer quoted above.

That before-and-after belongs to one engineer working the same problem across three years — not to two independent parties.

The field's own measurements support him. In SimplePIR's comparison table an early single-server construction reaches 0.131 MB/s of throughput against SimplePIR's 10,305 MB/s — a gap of roughly 78,000×, derived here from two printed cells rather than stated by the authors.²⁴ No latency figure is quoted in this post; Google's post notes that its "latency numbers are presented for a single-threaded CPU."²⁵

Two more limits deserve naming. Sublinear schemes do exist, at a price: the SimplePIR authors note that recent schemes preprocess the database so the server can answer in sublinear time, "but all known approaches require either client-specific preprocessing ... or impractically large server storage."⁷ Beimel, Ishai and Malkin proposed exactly that model — PIR with preprocessing — in the same paper as the way around their own lower bound.¹

Splitting the work across two non-colluding servers is faster, and weaker in kind: "their security is brittle, as it stems from a non-collusion assumption rather than from cryptographic hardness."²⁶

What none of this moves is the shape. Falling costs make more circuits affordable. They do not make a circuit out of an open-ended conversation.

What this means for a folder of notes

For a folder of prose, the answer that holds today is to keep the computation local and send on purpose. The shipped constructions fit queries with a known shape and a fixed size. A vault of thousands of files, searched by a question you have not written yet, is the opposite shape.

Two adjacent facts complete the picture. Whether your data left the device at all is usually decided by the embedding step rather than the chat step, which is the subject of The Chat Runs on Your Machine — the Embedding Step May Have Uploaded Every Note.²⁷

And an embedding sent in the clear is not an anonymous artifact, as The Embedding of Your Note Is Not Anonymous sets out.²⁸ The construction described here is the one case where that same outbound vector is a ciphertext the server cannot decrypt.

So the practical reading is short:

1. Treat "encrypted" as a claim about one path, not about a product.
2. Ask which leg of a pipeline leaves your device, and in what form.
3. Expect encrypted computation where the query is a lookup, not where it is a conversation.
4. Read a default-on setting as a consent question, separate from the cryptography.
5. Keep the folder local when the work can be done locally.

Craig Gentry's 2009 construction promised "a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt."²⁹ Seventeen years on, that promise is intact and exact. It was always a promise about circuits.

Frequently Asked Questions

The questions below are the ones people actually ask about this, several of them in public developer forums over the past decade. Each answer is scoped to what the cited sources support, and none of them generalizes into a claim that any particular product keeps your data private.

Could a server search my notes without being able to read them?

For a lookup, yes, and this ships today in at least one consumer product.¹² For open-ended search over a large folder of prose, no. The computation must be expressed with statically known bounds and fixed-size data, and every branch of every conditional is evaluated.⁹ A question you have not written yet has no fixed shape.

Does my AI chat use homomorphic encryption so the provider cannot read it?

No general chat assistant is documented as working this way. Google's engineering post describes encrypted inference as a stated goal — "Our vision is to make HEIR a one-click solution to enable non-experts to incorporate encrypted inference into production applications" — rather than a shipped capability.¹⁶ The deployed examples are lookups.¹²

What is the limiting factor of homomorphic encryption?

Server work, and specifically the read. Because a private query requires touching the whole database,² the ceiling is memory bandwidth: the SimplePIR authors measured roughly 12.4 GB/s/core on their machine and named it a hard limit on throughput.⁷ Their scheme reaches 10 GB/s/core, close to that wall.⁶

Isn't this just end-to-end encryption until you decrypt the query for the model?

That is the distinction worth learning. In the deployed path, no decryption happens at the server. Apple states that "the server does not learn the client's private embedding or the retrieved results," and that the decryption keys stay on the device.¹³¹⁴ The scope is one protocol on one path, and it says nothing about metadata or request timing.

How would you search a database full of encrypted data?

Two options exist. Download all of it, which was the 1995 baseline for perfect single-server privacy.⁵ Or have the server scan all of it blind, which is what private information retrieval does.² The work does not disappear in either case; it moves between the two parties.

Multi-server schemes are faster, so why not just use two servers?

Because the security changes in kind, not degree. The SimplePIR authors write that "their security is brittle, as it stems from a non-collusion assumption rather than from cryptographic hardness."²⁶ You trade a mathematical guarantee for a promise that two operators will not compare notes.

Is the 20,000× figure a measure of how much slower this is?

No. It is a storage ratio for one bit-level scheme. Encrypting a 100×100 greyscale image "will cost you 218 MiB to store all the pixels in memory. It's roughly a 20,000x overhead," because each encrypted bit becomes "a list of roughly 700 32-bit integers."¹¹ Repeating it as a speed figure changes the claim.

The server reads every byte and understands none of it, and that is not a flaw in the design. The exhaustive read is the guarantee, performed in full, on every single query.

Notes stay on your own device with mnmnote.com — plain Markdown, offline, open in any editor.