Homomorphic Routing

We propose a new private routing and packet forwarding scheme for the Internet---Homomorphic Routing (HR)---that enables endpoints to communicate with one another without divulging source or destination addresses to the routers or service providers along the path. This is achieved via homomorphic encryption, whereby domains can match encrypted address ranges with encrypted destinations of packets without the need of decryption. Compared to approaches such as source or onion routing, HR is a hop-by-hop solution that allows current BGP-like decisions and traffic engineering techniques to remain largely unchanged, while per-flow state need not be maintained by routers. Preliminary performance evaluation shows that HR implies a tolerable computational overhead compared to plain text operations. Through aggregation we can compress inter-domain routing rules to around 5% of those required for current IPv6 and we can organize encrypted forwarding rules so that matching can be achieved in logarithmic time.