Comment on page

Boomerang Encryption

A core challenge in a mix-net is ensuring that all envelopes get to the appropriate server on the path. A user complaining of protocol deviation (e.g., dropped messages) runs the risk of deanonymization. Boomerang encryption—a simple extension of onion encryption solves this problem by providing “receipts” that can be used by servers to anonymously blame on a user’s behalf. Boomerang encryption is designed to (1) ensure that all servers on a path receive messages addressed to them and (2) allow honest servers to trace the source of active attacks and assign blame accordingly.

Boomerang encryption and routing

Onion routing works in one “direction:” routing envelopes forward through the chain of servers such that only the destination server learns the plaintext message. In contrast, boomerang routing is bidirectional: it applies onion encryption twice, once in the forward direction and once in reverse (hence the name, boomerang). If we define reverse-onion encryption as:
 onion (sk,m):=Encsk(Encsk1(Encsk1(m)))\overleftarrow{\text { onion }}(\mathbf{s k}, m):=\operatorname{Enc}_{\mathbf{s k}_{\ell}}\left(\operatorname{Enc}_{\mathbf{s k}_{\ell-1}}\left(\ldots \operatorname{Enc}_{\mathbf{s k}_{1}}(m) \ldots\right)\right)
then boomerang encryption is defined as:
 boomerang (sk,m,m):= onion (sk,m onion ( sk ,m))\overleftrightarrow{\text { boomerang }}(\mathbf { sk }, \overrightarrow{m}, \overleftarrow{m}):=\overrightarrow{\text { onion }}(\mathbf{s k}, \overrightarrow{m} \| \overleftarrow{\text { onion }(\text { sk }}, \overleftarrow{m}))
is the forward message and
is the returned message. We note that the
cannot be returned without first decrypting all envelopes in the forward onion chain.
Boomerang decryption as an anonymous proof-of-delivery. We make the following somewhat surprising observation: a successful boomerang decryption can be turned into a proof of message delivery when applied to onion routing. Specifically, letting
(the returned message) be a random nonce acts as a message delivery receipt: it guarantees that every server along the path decrypted the correct onion layer and forwarded it to the next server. To see why this holds, observe that in order to successfully recover
, all envelopes in the forward onion must be decrypted to recover
m onion ( sk ,m)\overrightarrow{m} \| \overleftarrow{\text { onion }}(\text { sk }, \overleftarrow{m})
. Therefore, message
must have been delivered to the server at the end of the path (i.e., the last envelope in the forward onion chain must have been decrypted).