Skip to main content

Anonymous Routing Tokens

Anonymous routing tokens (ART)​

Anonymous routing tokens (ARTs) are used to determine and verify routing paths. Construction of ARTs is inspired by anonymous tokens based on blind signatures, but has two key differences: namely, ARTs are signed by a group of signers and are publicly verifiable. Specifically, tokens are signed by an anytrust group. This guarantees that at least one honest signer is present when signing each token and forms the basis for integrity in Trellis. The blind signature serves two purposes: ensuring that (1) the payload encapsulated by the ART comes from an (anonymous) user, and (2) the path through the mix-net, as determined by the ART, is uniformly random (even for malicious users).

How our routing tokens work. Routing tokens are generated by users and signed by an anytrust group. Each token encapsulates the necessary information a server requires to route envelopes on a link in the mix-net. Each signer (a server in an anytrust group) holds a partial signing key � � x i ​

associated with a global public signature verification key t v k ℓ tvk ℓ ​

for the ℓ ℓ th layer. The user has each group member provide a partial signature for the blinded token. The user then unblinds and recovers the multi-signature with respect to t v k ℓ tvk ℓ ​

by combining the partial signatures. If at least one signer is honest, then the signature is unforgeable and cannot be traced to the tokens seen during signing. The randomness of each token signature—which is uniform and independent provided at least one signer is honest—determines how envelopes are routed through the network and guarantees a random path selection.

Routing tokens and path selection​

During the path establishment protocol, each server (anonymously) receives ARTs for the links it is responsible for. Each token determines the next server on a link (and can be checked with ART.NextServer), which allows each server to (1) determine where to send envelopes in the subsequent layer and (2) anonymously verify path adherence (without knowledge of the full path, only the local link).

Boomerang routing on a path​

We use boomerang encryption to route envelopes through the mix-net. We assume that the boomerang encryption scheme is instantiated using IND-CCA secure encryption (where the shared encryption key is derived from the Diffie-Hellman message in the ART payload). Each intermediate layer ciphertext (i.e., envelope) is signed and can be verified by the server using the signature verification key given in the corresponding ART payload. This gives us authenticated boomerang routing which ensures that: (1) each server receives every envelope for each link and (2) all envelopes on a link are valid authenticated encryptions under the associated link public keys. Any failure of these two properties (e.g., failed decryption, bad signatures, or missing envelopes) triggers a blame protocol.