Date Added: Dec 2009
This paper presents compact message formats for onion routing circuit construction using the Sphinx methodology developed for mixes. The authors significantly compress the circuit construction messages for three onion routing protocols that have emerged as enhancements to the Tor anonymizing network; namely, Tor with predistributed Diffie-Hellman values, pairing-based onion routing, and certificateless onion routing. The new circuit constructions are also secure in the universal composability framework, a property that was missing from the original constructions. Further, the authors compare the performance of the schemes with their older counterparts as well as with each other.