Citizens' privacy is coming under greater threat as an increasing number of entities can access user data. A powerful adversary, such as a nation-state, can gain access to user data using a broad range of techniques, from privately tapping wires and collecting traffic to serving warrants or subpoenas for user data. Protecting user privacy in the face of these types of activities is challenging. Existing protocol encryption such as TLS is not sufficient, since a wide range of data, from DNS lookups to server access logs, may be visible to eavesdroppers or subject to data requests. In this dissertation, I develop new techniques that demonstrate that three aspects of the existing Internet infrastructure, specifically routing, hosting, and naming, can be used to counter surveillance.

First, I study the current state of routing by measuring which countries are on the paths between users and popular websites. I then evaluate different methods for routing Internet traffic around unfavorable countries, and based on these findings, I design and implement RAN, a lightweight system that routes a client's web traffic around specified countries with no modifications to client software.

Second, I describe modifications to content hosting that prevent a powerful adversary such as a nation-state from gaining access to a user's requests for certain Web content. In today's Internet, Content Distribution Networks (CDNs) have rich information both about the content they are serving and the users who are requesting that content. Access to this type of information makes CDNs a target for requests for data about users' browsing activities. To counter this threat, I developed Oblivious CDN (OCDN), which hides from the CDN both the content it is serving and the users who are requesting that content.

In the last part of this dissertation, I explore how the naming infrastructure currently compromises client privacy by looking at conventional DNS as well as onion services. I highlight fundamental issues with both types of domain lookups, and present Oblivious DNS (ODNS) as a new approach to protecting privacy by decoupling client identities from the domains they are looking up.