Minimal and Fastest Anonymous Communication against Colluding Passive Adversaries

Anonymous communication protocols are crucial in protecting privacy from colluding eavesdroppers on the Internet. Onion Routing protocols provide relationship anonymity-unlinkability of senders and receivers-by decrypting the entire packet at each on-path relay. Although this decryption prevents adversaries from linking inbound and outbound packets at every relay, it bottlenecks forwarding performance. This paper highlights its excessiveness, proposing that packet unlinkability across the end-to-end path suffices, rather than at every individual relay. We introduce Cabbage Routing, where each relay decrypts only a portion of the packet, and consecutive relays collaboratively decrypt the entire packet, defeating passive adversaries. This approach not only improves performance on software platforms but enables operation at Tbps-class speeds on hardware platforms. We present the protocol design, implementation on both software and hardware platforms, formal security validation, and experimental performance analyses. Our evaluations affirm that the Cabbage Routing protocol is secure and provides high forwarding speeds appropriate for wide deployment over the Internet.