# Algorithm: Known-Answer Testing

*Every other article in this series makes a server **prove** something. This one is about what
you do when proving is impossible: when the check you would need requires the very secret the
protocol exists to keep from you. The answer is older than cryptography and slightly delightful:
hide questions you already know the answer to among the real ones.*

Prerequisites: none, really. It helps to have read
[The Verifiable OPRF](03-the-verifiable-oprf.md) for the attack this defends against, and
[Rounding by Oblivious Transfer](08-algorithm-rounding-route-b.md) for the second one.

---

## 1. Two attacks that proofs do not reach

The discovery server holds a secret key *s* and answers `F_s(x)` obliviously: it evaluates its
[keyed pseudorandom function](02-the-lattice-oprf.md), a keyed hash, on your phone number
without ever learning which number it was. That arrangement is called an OPRF, an oblivious
pseudorandom function.

Two ways it can misbehave keep coming up, and they have the same shape.

**The per-victim key.** Nothing forces the server to use the *same* *s* for everybody. If it
answers you under a key s<sub>you</sub> it uses for no one else, every value you derive carries a marker
only you produce.

You cannot see this. An OPRF output looks pseudorandom (indistinguishable from random noise)
whatever key made it, and obliviousness protects your *input*, not the server's honesty.

**The nudged rounding table.** The final step of the OPRF rounds a shared value using a small
lookup table the server builds. You open exactly one entry out of 256, via one
[oblivious transfer](07-algorithm-pq-oblivious-transfer.md), which hands you a single entry
without the server learning which.

A server that builds that table from a slightly different number shifts your output. And if it
can observe whether your subsequent lookup succeeded, it learns one bit about your secret input.

[Rounding by Oblivious Transfer](08-algorithm-rounding-route-b.md) covers how much of this proofs
and commitments close. A sliver survives.

We do prove a great deal about the server. It proves it used the committed key for the linear
part (a commitment being a published fingerprint that pins a value down without revealing it); it
proves the rounding parameters came from the committed mask; and it commits to the tables
before it learns your choices. What is left over in both cases has the same awkward form:

> To check the value in front of you, you would need the secret the protocol is specifically
> designed to withhold from you.

You cannot verify a single table entry without knowing the mask that hides the unrounded product.
That is not an engineering oversight. It is the protocol working correctly.

---

## 2. The trick: ask a question you already know the answer to

Suppose you want to know whether a calculator is lying to you, but you cannot check its
arithmetic: the numbers are too big. You can still slip in `2 + 2` occasionally.

That is the whole idea. A **canary** is an input whose value is *public* and whose correct output
under the honest key is *published in advance*. Feed one through the exact same protocol as a real
query and you get a value you can compare against the published one. A server answering under any
other key produces a mismatch.

> **Figure:** Canary queries are indistinguishable from real queries once encrypted

Three properties make it work, and all three matter:

1. **The canary is indistinguishable from a real query.** This is the load-bearing one. Your
inputs travel as [lattice ciphertexts](01-lattice-foundations.md), so the server sees a
random-looking blob whichever it is. It cannot answer canaries honestly and real queries
dishonestly, because it cannot tell them apart.
2. **Its correct answer is public.** A canary's input is a fixed, published constant, so
`F_s(canary)` reveals nothing about *s* the server has not already committed to. It is just a
PRF output (the keyed hash evaluated at a point everyone knows), and publishing it costs
nothing.
3. **You choose where they go, secretly.** The canaries are shuffled in among the real queries
with a cryptographic random number generator. A predictable position would let the server step
around them, defeating the entire mechanism. In the implementation this is a one-line detail
carrying a comment that shouts about it, because it is exactly the kind of thing a later
refactor quietly "simplifies."

---

## 3. How well does it work? A calculation worth doing yourself

Say you resolve *n* real contacts and hide *c* canaries among them, for *B* = *n* + *c* sessions in
total. A server wants to tamper with one particular contact's session, but it has no idea which
slot that is. So it picks a slot and tampers.

Two things can happen:

- The slot holds a canary. Probability *c*/*B*. **It is caught.**
- The slot holds the contact it actually wanted. Probability 1/*B*. It learns something.

Take the ratio of those two probabilities:

`P(caught) / P(hit target) = (c/B) / (1/B) = c`

**For every successful probe, it expects *c* detections.** With 32 canaries, a server that
eventually lands on the contact it was after has been caught about 32 times getting there.

> **Figure:** Tampering with any slot risks hitting a hidden canary; the expected cost is c detections per successful probe

Two things about this result are worth sitting with.

First, *n* cancelled out of the ratio. The guarantee does *not* weaken as the address book grows,
which is not what most people guess.

Second, the attacker cannot improve its odds by being greedy. Tampering with many slots to raise
the chance of hitting the target raises the chance of hitting a canary in exactly the same
proportion. Tampering with *all* of them would guarantee hitting the target. It would guarantee
hitting every canary too.

The strategy has no good version. That is the nicest thing you can say about a defence.

---

## 4. What it costs, and what it does not buy

A canary is a real query. The server does the same work and the wire carries the same bytes, so
*c* canaries cost *c* extra evaluations. That makes the parameter a straightforward dial: more
canaries, more certainty, more work.

The implementation uses a **rate** rather than a fixed count: roughly one canary per four real
resolutions, with a floor of four and a cap.

The floor matters because someone adding a single contact still deserves protection. Four canaries
among five sessions is an 80% chance of catching any tamper.

The rate matters because a fixed count would dilute: 32 canaries among 32 contacts is strong, 32
among 5,000 is thin.

And the ratio from §3 tells you exactly what you are buying at each setting, which is why it is
worth deriving rather than picking a number that feels safe.

Now the honest part, because this is where known-answer testing differs from everything else in
this series.

**It detects; it does not prevent.** A server that gets lucky (tampers once, misses every canary)
did learn its bit. What it cannot do is *repeat*. Sustained probing is caught with probability
approaching one, so one-shot attacks are the only ones left.

In this system that ceiling is lower than it sounds. A resolved contact is cached forever, so a
phone number is resolved once per install.

A reinstall or [a new device](/articles/groupthink/08-mechanism-absorbing-a-new-device.md) does open
another attempt, and multi-device makes that a real path worth naming. But those are rare,
user-visible events the server cannot provoke.

The pace of attempts is set by how often you add a device, not by the attacker's patience. And
every attempt walks the same minefield.

**A miss is not a bug report.** When a canary comes back wrong, the client does not retry or
degrade: it aborts the whole pass, writes nothing to its cache, and raises an alarm. This is the
correct response to evidence of a *cheating server*, which is a different category from a network
error. Treating it as transient would silently discard exactly the signal the mechanism exists to
produce.

**Everything or nothing.** Because a tampered pass might have hit real slots too, a canary
failure invalidates the entire batch, not just the canary. Results are staged and committed only
when every canary has checked out.

> **Figure:** Staged results commit to the cache only if every canary passes; one failure aborts the whole batch

---

## 5. Where else this shows up

The same mechanism guards the [admission token](/articles/relay/11-algorithm-admission-token.md) mint,
where the worry is a per-user issuer key turning the token's cleartext key identifier into a
tracking tag.

There the canary is one of three layers: the key set is committed to a transparency log (an
append-only public record anyone can audit) so it cannot be equivocated, shown one way to you
and another way to everyone else; it is published in full so a per-user key would visibly bloat
the list; and then a canary checks the server actually *used* the key it named.

That layering is the general lesson. A commitment says *what* the key is. Publication makes it
*the same for everyone*. A known-answer test proves the server actually *used* it. They defend
different things, and the third is the only one that survives when you cannot verify the answer
directly.

---

## 6. Summary

- Some server misbehaviour is out of reach of proofs, because checking the value would require
the secret the protocol is built to withhold.
- A **canary** is a public input with a published answer, run through the identical path and
compared. Indistinguishability from real queries is what makes it work: the server cannot
tell which sessions are safe to cheat on.
- Hiding *c* canaries among *n* real queries yields ***c* expected detections per successful
probe**, independent of *n*, and no tampering strategy improves that ratio.
- The cost is *c* extra evaluations; the implementation uses a rate with a floor rather than a
fixed count.
- It **detects rather than prevents**, which is the right goal once the leak is one-shot: a
failure aborts the pass, commits nothing, and raises an alarm rather than being retried away.

---

## References

- Known-answer tests are standard practice in cryptographic validation (NIST's KAT vectors for
algorithm certification are the familiar example). The twist here is *hiding* the test among
live traffic so the party under test cannot recognise it.
- Cut-and-choose in secure computation: the same "commit to many, open some at random" bargain,
from which the probability accounting in section 3 is borrowed.
- S. Dietz, S. Tessaro, "Fully Malicious Authenticated PIR," CRYPTO 2024: validation queries
indistinguishable from real ones, the closest formal treatment of this shape.
- Wikipedia: [Cut-and-choose](https://en.wikipedia.org/wiki/Cut-and-choose),
[Known-answer test](https://en.wikipedia.org/wiki/Known-answer_test),
[Canary trap](https://en.wikipedia.org/wiki/Canary_trap).

*Back up to [The Verifiable OPRF](03-the-verifiable-oprf.md), where the per-victim-key attack
starts, or to [Contact Discovery](00-contact-discovery.md).*
