Per-Recipient Blinded Pseudonyms: How Tessera Achieves Cross-Recipient Unlinkability

A Schnorr zero-knowledge proof authenticates the sender without revealing the secret key x. But the proof is computed against a public key Y, and if Y is sent in the clear with every delivery, a network observer can link every message to the sameY and reconstruct the sender's full communication graph. The ZK proof hides the secret; it does not hide the identity.

Tessera solves this with per-recipient blinded pseudonyms: each delivery uses a fresh public key Y' = Y + t · G, wheret = H(seed ‖ session_id) mod q. The observer sees a uniform random curve point; the recipient, who knows seed, recoversY from Y' and verifies the Schnorr proof against it. Two deliveries to the same recipient use differentsession_id, so the Y' values are unlinkable across deliveries and across recipients.

The linkability problem

Concretely, suppose the sender Alice with public key Y_Asends authenticated messages to recipients Bob and Carol. If every delivery carries Y_A in the clear so the recipient can verify the Schnorr proof, an observer sees:

• Delivery 1: public key Y_A, recipient bucket for Bob
• Delivery 2: public key Y_A, recipient bucket for Carol
• Delivery 3: public key Y_A, recipient bucket for Bob

The observer links all three deliveries to the same sender and reconstructs Alice's social graph: {Alice → Bob, Alice → Carol}. The ZK proof is sound — no one can forge Alice's signature — but the metadata is fully exposed. This is exactly the Signal problem.

The blinding solution: Y' = Y + tG

The fix is to send a blinded public key per delivery instead ofY. Alice and Bob enrol pairwise: over a trusted channel they exchange a shared seed (and confirm each other's base public key Y_A, Y_B). For each delivery, Alice derives:

t = H(seed_AB ‖ session_id) mod q
Y' = Y_A + t · G

and computes the Schnorr proof against Y' (notY_A). She sends Y' and the proof over the bucketed broadcast network. The observer sees a random curve pointY' whose distribution is uniform in the group, becauset · G is uniform when t is uniform inZ_q.

How the recipient authenticates

Bob receives a delivery on his bucket and reads Y' plus the Schnorr proof. He does not know which sender produced it, but he holds a small set of enrolment seed values (one per contact). For each contact, he derives the candidate t for the current session_id and checks:

Y_candidate = Y' − t · G
if Y_candidate == Y_A:  # the contact's base public key
    verify Schnorr proof against Y_A (or equivalently against Y')

When the candidate matches, Bob knows the delivery is from Alice and can verify the proof. Crucially, the verification does not require sendingY_A on the wire — only Y' is published. The recipient recovers Y_A locally using the shared seed.

Cross-recipient unlinkability

The same sender Alice delivers to Bob using Y'_AB = Y_A + t_AB · Gand to Carol using Y'_AC = Y_A + t_AC · G, wheret_AB = H(seed_AB ‖ session_id) andt_AC = H(seed_AC ‖ session_id). The two seedvalues are independent (Alice enrolled separately with Bob and Carol), sot_AB and t_AC are independent uniform values inZ_q. Therefore:

Y'_AB − Y'_AC = (t_AB − t_AC) · G    — a uniform random curve point

An observer who sees both Y'_AB and Y'_AC cannot link them to a common sender without solving a discrete log. This is theblinding lemma: the blinded pseudonyms are computationally indistinguishable from independent uniform curve points, so cross-recipient linking reduces to DLog.

Cross-delivery unlinkability

Two deliveries to the same recipient Bob in different sessions use different session_id values, hence differentt, hence different Y'. The observer sees two independent uniform points and cannot link them. Only Bob, with the sharedseed_AB, can recover Y_A from both and link them to Alice — which is exactly the authentication Bob wants.

Enrolment model

Tessera uses pairwise local enrolment, not a global PKI. Two parties exchange seed and confirm each other's base public key over a trusted channel (in person, via QR code, or another verified channel) once. After enrolment:

• Neither party ever sends Y on the wire again.
• Every delivery uses a fresh Y' derived from the shared seed and a session id.
• No central directory stores the mapping of public keys to identities.
• Compromise of one enrolment (one seed) does not affect other contacts.

This is a deliberate trade-off: Tessera gives up the convenience of a global address book in exchange for not having a central server that stores the social graph.

Code example

from tessera.crypto.blinding import BlindedSender, BlindedVerifier

# enrolment (once, over a trusted channel)
seed_AB = secrets.token_bytes(32)
alice_sender = BlindedSender(secret_key=x_A, base_pubkey=Y_A, seed=seed_AB)
bob_verifier = BlindedVerifier(contacts={Y_A: seed_AB})

# per delivery
session_id = os.urandom(16)
Y_prime, t = alice_sender.derive_blinded_pubkey(session_id)
proof = alice_sender.prove(session_id=session_id, message=m)

# bob's side
sender_pubkey, ok = bob_verifier.try_recover(Y_prime, session_id, m, proof)
assert ok and sender_pubkey == Y_A

What this buys

Blinded pseudonyms are the second of Tessera's three privacy mechanisms. The first, Schnorr ZK proofs, hides the secret key. Blinding hides the sender's public identity on the wire. The third, (ε,δ)-DP cover traffic, hides the per-bucket counts that would otherwise reveal which bucket corresponds to an active delivery. The three compose to give authenticated, metadata-private delivery with no central authority.