# Achieving Sender Anonymity in Tor against the Global Passive Adversary
## 4 The Proposed Protocol
### Set-Up Phase
#### 4.2.3 Sender and Proxy Key Generation  
First, \(F\) is set to 1. Then, \(r_{i}\) selects a random public key \(PK_{r_{j}}\) from \(Q\setminus\{PK_{r_{i}}\}\). \(r_{i}\) selects its public DH parameter \(y_{ij}\) and encrypts it with \(PK_{r_{j}}\), thus obtaining \(C_{ij}=E_{PK_{r_{j}}}(y_{ij})\). Then, \(PDH\) is set to \(C_{ij}\). \(R\) is set to a random value used by \(r_{j}\) to reply with its public DH parameter, which is needed by \(r_{i}\). This DH parameter is used in the construction of the key that \(r_{i}\) will use to send a message by using \(r_{j}\) as a proxy. This key \(k_{ij}\) is called the _sender key_ for \(r_{i}\) (with respect to \(r_{j}\)), and the _proxy key_ for \(r_{j}\) (with respect to \(r_{i}\)). Finally, \(H\) is filled with random bits.  
The token \(T\) is encrypted by \(r_{i}\) with \(k_{i}\), by obtaining \(C_{T}=E_{k_{i}}(T)\). Then, \(C_{T}\) is sent to \(next(r_{i})\).  
When \(C_{T}\) reaches \(next(r_{i})\), it decrypts \(C_{T}\), by obtaining \(T\), and since \(F=1\), it tries to read the field \(PDH=C_{ij}\) of \(T\). If \(next(r_{i})\
eq r_{j}\), \(next(r_{i})\) is not able to decrypt such a field, and then it re-encrypts the token with the forward key \(k_{next(r_{i})}\) shared with \(next(next(r_{i}))\) and forwards the token. The token moves through the ring until it reaches \(r_{j}\). At this point, \(r_{j}\) decrypts \(C_{ij}\) and obtains \(y_{ij}\), with which it generates the key \(k_{ij}\) which is shared with \(r_{i}\). The token is filled as follows. \(F\) remains set to 1. \(PDH\) is set to \(\tilde{y}_{ij}\). \(\tilde{y}_{ij}\) represents the public DH parameter of \(r_{j}\) that will be used by \(r_{i}\) to generates the key \(k_{ij}\). \(R\) remains unaltered, and finally, \(H\) is set to the hashed value \(H(k_{ij})\). This new token moves through the ring until \(r_{i}\). Observe that all the nodes between \(r_{j}\) and \(r_{i}\), after decrypting the token with their forward keys, understand that the token is used to reply to a node, but are unaware of the sender and the recipient of this token.  
When \(r_{i}\) receives the token, it identifies the token as a reply of \(r_{j}\) thanks to the random \(R\). Then, \(r_{i}\) can generate the key \(k_{ij}\) as \(r_{j}\). This token is then disposed by \(r_{i}\). Finally, \(r_{i}\) drops from the set \(Q\) the node \(r_{j}\). Note that any external observer only knows that a key was exchanged by a given node \(r_{i}\), but does not know with which node.  
The entire process (which started at time \(t_{1}\)) is repeated \(k-2\) times, until all \(k_{ij}\) are exchanged.  
When all the \(k(k-1)\) tokens are disposed of, each node \(r_{i}\) owns (in addition to the forward key) two symmetric keys \(k_{ij}\) and \(k_{ji}\) shared with each other node \(r_{j}\) of the ring. The key \(k_{ij}\) represents a sender key for \(r_{i}\), since it used by \(r_{i}\) when has to send a message by selecting \(r_{j}\) as a proxy node (see next section). On the other hand, \(k_{ij}\) represents a proxy key for \(r_{j}\), since it is used by \(r_{j}\) when plays the role of proxy node.  
In Figure 1, the sequence diagram of the set-up phase is depicted.