HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Algorithm: The Admission Token (Lattice OPRF)

10 min read

A deep dive into the token itself: how it is minted so the issuer cannot recognize it later, how it is checked at the turnstile, and why the whole thing rests on the same lattice oblivious PRF the discovery path is built on.

This is the machinery behind Anonymous Admission. It reuses a primitive developed from scratch elsewhere in the sibling series, so this article's job is to show the token lifecycle, not to re-derive the cryptography.

1. The primitive we're standing on

An Oblivious Pseudorandom Function (OPRF) is a two-party protocol where a client learns F_s(x) — a keyed pseudorandom function of its input x — while the server that holds the key s learns nothing about x, and the client learns nothing about s. A Verifiable OPRF (VOPRF) adds a proof that the server used the one committed key and didn't cheat.

The token path uses the OPRF, but not the zero-knowledge proof: the discovery key is fixed forever, so a client can carry its commitment in the app binary, while token keys rotate every 24 hours, leaving nothing stable to bake in. Section 5 covers what the token path does instead — a transparency-log commitment plus a hidden known-answer check, which turns out to be a nice mechanism in its own right.

The discovery series builds the post-quantum, lattice-based OPRF completely from the ground up — the oblivious evaluation, the rounding, the zero-knowledge proof — across several articles. Rather than repeat any of it, this one points there:

  • The Lattice OPRF — how F_s(x) is evaluated obliviously with lattice encryption instead of an elliptic curve.
  • The Verifiable OPRF — how the client forces the server to prove it used the committed key.

If those two are the engine, this article is the vehicle it drives: an anonymous, single-use admission token.

2. Minting a token, blindly

A token is just a value token = F_s(nonce) for a random nonce the client picks — but the way it is computed is the whole point.

  1. Pick a secret. The client generates a fresh random nonce (think: a serial number no one has seen). This nonce, plus the token value, will be the token.
  2. Hide it. The client encrypts the nonce under a lattice scheme, so what leaves the device reveals nothing about the original to anyone who cannot solve Ring-LWE.
  3. Evaluate. credential-svc, over an authenticated session and only if the user is within their per-class hourly budget, applies the secret key s to the blinded value and returns the blinded result — without ever seeing the real nonce. This is done in a two-round exchange and batched, so a client mints a whole roll of tokens (dozens per round) in one trip.
  4. Check the key, then unwrap. Before trusting anything, the client checks it was served the right key — the mechanism in section 5 — and then unwraps the reply to recover the true token = F_s(nonce).

The client now holds (nonce, token) pairs. credential-svc saw only ciphertexts, so it cannot match a minted token to the one the relay later redeems — not because the link was destroyed, but because recovering it means breaking the lattice encryption. That is a computational guarantee, and a post-quantum one; Anonymous Admission works through why it is weaker than the one-time-pad blinding of a classical anonymous token, and why the project took that trade.

3. Spending a token at the turnstile

When Alice sends an envelope, she attaches one unused (nonce, token) pair. The relay, which holds the checking key s, verifies it in the most direct way possible:

  1. Recompute. The relay computes F_s(nonce) itself from the revealed nonce.
  2. Compare, in constant time. It checks the recomputed value equals the presented token, using a constant-time comparison so the timing of the check leaks nothing.
  3. Check the class. It confirms the token's class (send vs ack) matches the envelope (§4), before spending it.
  4. Spend once. It marks the nonce as spent in the double-spend ledger; a second appearance is rejected.

Because the relay holds s, it can recompute F_s(nonce) — that is exactly how it checks the token — but a client cannot, because a client never holds s. So a valid (nonce, token) pair is unforgeable proof that the client obtained it from the authorized, budgeted mint. The relay learns the nonce only now, at spend time — and since that nonce is fresh, random, and blinded from the issuer, revealing it at the turnstile links to nothing at the booth.

That is the anonymity boundary in one sentence: the issuer sees who mints but not what; the relay sees what is spent but not who; and the blind severs the two so completely that even the two of them together cannot rejoin them.

4. Binding the class into the token

Recall the two token classes from article 08: a tight send token and a cheap ack token restricted to small, non-waking receipts. That restriction is not a policy flag the relay checks and could forget — it is bound into the token's cryptography. The two classes are derived under domain separation (the mint mixes a class label into the evaluation), so a send token and an ack token are mathematically distinct objects, and an ack token simply does not verify against a message-class envelope. You cannot upgrade a cheap token to an expensive one because the class is part of what F_s was evaluated over, not a mutable field riding alongside it.

5. Making sure it is the right key

Section 2 step 4 said the client checks the key before trusting the reply. Here is what that means, and it is three separate checks because each one leaves a hole the next closes.

The attack. key_id rides in cleartext inside every token, and the relay reads it on every message to pick the verifying key. Under honest operation there are only a couple of live keys — a send key, an ack key, plus a rotation overlap — so key_id carries about two bits and says nothing about who sent anything. But credential-svc chooses both the key and its id, and the relay accepts whatever is in the key table. A server that mints a distinct key per user turns key_id into a per-user tag the relay can bucket on. It is entirely classical, needs only one party, and — this is the sting — it survives cert rotation, so it stitches a user's deliberately short-lived sender-cert pseudonyms back into one long-lived identity.

Check 1 — consistency: is this the key you say it is? The client folds a public canary into its mint batch: an input whose value is public and whose correct output under each key is published in advance. Its slot is hidden like every other, so the server cannot tell the canary from a real token request, and therefore cannot answer that one honestly while deviating on the rest. If the canary comes back matching the advertised commitment for the key_id we were handed, our tokens were minted under the key the server named.

Check 2 — non-tagging: is that key everyone's key? Consistency alone does not stop the attack, and it is worth seeing why: a server can honestly use a per-user key and honestly commit to it, passing check 1 every time. What stops it is publication. credential-svc publishes the full list of live keys, the client refuses a key_id that is not on it, and it refuses a list that has grown implausibly long. Per-user keys would have to appear in a list every client can see, so the list would swell toward the size of the user base — impossible to hide.

Check 3 — non-equivocation: is that the list everyone else got? Checks 1 and 2 still leave a server free to hand a different short list to each client, which caps the tagging channel without closing it. So the whole key set is committed to the transparency log: one value per version, the same for everybody, and the client will not mint unless the list it was served hashes to the digest committed there.

That sentence is the right idea and, on its own, not enough — which is worth dwelling on, because the gap is the kind that looks closed. Committing the set at a version proves the list was published at some point. It does not prove it is the list in force now, and it does not even prove the server answered the question you asked. Three things have to hold:

  • Bind the version you asked about. Every generation of the key set lives at the same address in the log — only the version number separates them. So the proof you get back has to be for the version you requested, not merely for some version. Without that check the server answers "show me generation 7" with a perfectly valid proof for generation 3, and nothing looks wrong.
  • Prove the next one is absent. Inclusion says a generation exists; it never says it is the latest. An operator can publish several entirely honest generations and hand a different one to each cohort — every client verifies, no root ever forks, and the gossip below sees nothing. The client therefore also demands a proof that version v+1 does not exist, under the same signed root. Under one root the next version either exists or it does not, so everyone who checks agrees on which generation is current, and splitting the userbase now requires showing people different roots — which is a fork.
  • Remember what you have seen. A client that has verified generation 9 must never accept 8 afterwards. Without a local high-water mark, "roll this one device back to a superseded key set" is available to the server for free, and the rolled-back generation is genuinely signed.

With all three, equivocating on the key set means equivocating on the entire log — and a forked log is detected by the cross-user gossip that rides sealed messages.

One more property, easy to miss: the root has to be fresh. A signed root proves authenticity, not currency. A validly-signed root from last month is still validly signed, and the never-go-backwards rule only catches an epoch that moves backwards — not one that stops moving. A server that simply freezes one client's view holds it at an epoch where an obsolete key set honestly was the latest, and every check above passes. Two things close that: the log emits a heartbeat epoch even when idle, so silence itself becomes a signal, and a peer's gossip about a newer epoch is fetched, verified against the pinned root, and adopted — after which the frozen server is serving something older than what you now trust, which is the rollback you already refuse. Staleness is treated as unavailable, never as evidence: an honest log that is simply down looks identical from here, and refusing on it would take the network down with it.

Notice the shape: a commitment says what the key set is, publication makes it the same for everyone, and the hidden known-answer test proves the server actually used what it committed to. None of the three is sufficient alone. The known-answer trick in check 1 recurs elsewhere in the system and gets its own treatment in Known-Answer Testing.

6. Why lattice, and what it costs

Two design commitments distinguish this from the classic anonymous-token systems (Privacy Pass and friends):

  • Post-quantum unforgeability. Classic tokens use an elliptic-curve OPRF, whose unforgeability a quantum computer breaks — and a forged issuer key would let an attacker mint unlimited tokens. That is a forward-looking risk rather than a harvest-now one (a break in 2035 forges 2035 admissions; it does not retroactively deanonymize anyone), but the whole system's rule is "no discrete logs anywhere," so the token uses the lattice OPRF and there is no curve to break.
  • Computational, post-quantum unlinkability. The anonymity between mint and spend rests on the lattice assumption too: what credential-svc saw is a lattice encryption of the client's nonce, and linking it to a redeemed token means breaking Ring-LWE. A quantum computer cannot do that. An adversary with unbounded computation could.

That second bullet is a real trade, not a footnote, and Anonymous Admission §"How strong is that hiding?" works through it: a classical blinded token has unconditional unlinkability and quantum-breakable unforgeability; this one reverses both. Which you prefer depends on whether you fear a future adversary forging tokens or a future adversary de-anonymizing a transcript it recorded today.

References & further reading