Access Provider Privacy
Whenever you connect to the web, you're connecting via some kind of access provider. Most people will think of their ISP (internet service provider) aka your home broadband provider, but these days we're constantly connecting our phones to wifi at work, in cafes, shops and airports. Many phone network providers are teaming up with wifi networks so your phone will automatically connect to wifi spots around your city, and the latest phones support making calls and texts over the wifi connection.
My privacy requirement is that when I connect to an access point, my web traffic is protected from the access provider, and that they can't see what I'm browsing or read the emails or messages that I download over their wifi. You might feel that this is unnecessary; can't we just trust the access providers? I'm not going to get into that here, other than to point out that you're also trusting every individual tech geek that works at those companies, and a lot of small technology outsourcing companies that they will use for IT installation and support. You're also hoping that they haven't been hacked by malicious individuals, and that they never will be hacked (probability:zero). And regarding your need for privacy, even if you are entirely blameless, consider the possibility that one day a friend or relative sends you a "private" message in which they joke about something that looks illegal or sinister when taken out of context. Their privacy is dependent on your privacy.
VPNs
OK, let's start simple here. Say your company has a bunch of computers in two offices in different cities. Each office has its own private network, connecting just the computers in that office to each other. Naturally, you'll want to be able to connect the two networks together (an 'inter-office-network'!). That's the "N" in VPN. So you connect the two with a cable from one office to another. These days, unlike when the telegraph first arrived, you don't lay the cable yourself, you lease one from the phone company. Everything works great, the connection is Private (that's the P), but, leasing a line is really expensive. And since the internet is already available for free, why not use that instead? So you want a private network that goes out over the public internet, so you need some fancy software that creates a Virtual reality (that's the "V") style simulation of a Private Network on top of the public internet.
That's where VPNs come from. These days, you can download a VPN client to your phone or laptop, and connect to a cloud-based VPN server. Now, it's as if you have a cable connecting your device to that server directly, throught the magic of encryption and internet routing. Any traffic that goes over that tunnel can't be accessed by the real devices in between, such as the wifi router in the cafe, because it's encrypted and only the VPN server knows how to decrypt it.
So, VPN clients are a great solution for maintaining privacy from your access provider, right? It's true they provide a potential solution, but there are pitfalls. The VPN client on your phone can stop running, or need to reconnect to the server, while this is happening all your web traffic is susceptible. Even if the VPN stays up and running all the time, you can't always be sure what traffic is routed over it. Remember our two offices VPN example? Well in that situation, IT guys would still route the web traffic from PCs in the office directly to the internet - only traffic destined for the other office's machines would be routed over the VPN.
Most VPN client apps for phones do try to route everything over the VPN, since that's the real reason people use them. But they can still leak information. When you connect to a wifi access point, your device has to talk to it directly in order to get configuration information so that it can actually work (this is called DHCP). If the VPN client refused to let any traffic go to any destination other than over the VPN, you wouldn't be able to connect to the access point in the first place.
Even if you get your VPN configured as tight as possible, it's quite likely that you still leak DNS lookups (remember those from part 2?). So the access provider can't see exactly what data you're transferring, but they can see all the website addresses that you look up in order to connect to them, which is quite a lot of meta data and certainly doesn't constitute privacy.
The larger access providers, such as the big home broadband companies, are aware of the use of VPNs and of course they can detect when your VPN client attempts to connect to a VPN server (since they know the DNS names and IP addresses of the popular VPN services). If they wanted to, it's pretty easy for them to cause these connections to fail by blocking the initial connection, so your client can't reach the VPN server to start the whole encryption process.
It's also possible for the access provider to take the traffic from your VPN client and send it to one of their own servers. This requires some sophisticated NSA level techniques, but it's entirely feasible. A less sophisticated approach requires the attacker to first hack into the VPN servers and get some decryption keys, but that's not at all infeasible - most OSs have security vulnerabilities and it only takes one server to be unpatched for the attacker to succeed.
Proxies
Now that you understand VPNs, proxies are a sinch, and we already discussed them in a previous post. Essentially a proxy is a server in the cloud that your browser connects to and sends all its web requests to. It's arguably a little simpler than a VPN, and they are just focused on keeping your browser traffic private, unlike the more general purpose VPN.
Unfortunately, many of the popular browsers and proxies still leak DNS requests. So your web traffic is encrypted, but a snooper can easily tell which sites you're accessing.
Dissatisfaction
I'm sure when technically minded people read this, they'll suggest many possible ways of securing your web traffic from the access provider, but I've yet to find anything that a person of basic technical ability can be confident they've configured correctly and be sure they won't leak information or leave themselves open to various vulnerabilities.
