Survey of existing attempts at privacy-preserving messaging protocols

[Mikerah]

In order to have a good view of the current landscape of privacy-preserving communication protocols, I think it would be a good idea to write a survey paper on current protocols. It'll enable us to determine what we want appropriate from other protocols and not duplicate the same types of design mistakes. It would also serve as a very useful resource for other researchers in the field that may want to work on other types of protocols, as well.

I am interested in helping this get started, if others think this is important.

[Mikerah]

I started researching other messaging protocols and found this resource co-authored by Harry Halpin. It is effectively what I was proposing to do and it dates back to 2016.

[burdges]

Almost everyone involved who hails from academia has informally done this themselves. At a high level, we often address the technical concerns in our talks, but mostly they boil down to scalability, unclear anonymity advantages, and not providing uniform protections.

PIR has scales poorly but some mitigations exist. PIR only protects recipients, making it only a one component. It's also hard to make PIR decentralized. In fact, PIR helps with some blockchain and dapp problems, so we must develop decentralized variants, but likely for more narrow use cases. We cannot way for that research in this project anyways.

DC-nets have no hope for scaling up. As they scale poorly, DC-nets provide only a small anonymity set, but small anonymity sets benefit only the rich and powerful who can exploit weak plausible deniability better by influencing the courts and media. All so called scalable DC-net designs use DC-nets as a local transport in what amounts of a mixnet of local DC-nets. DC-nets claimed "information theoretic security" advantage is actually a weakness in that they lack route unpredictability and thus make compromise attacks easier. DC-nets claimed low-latency advantage sounds like a footgun for applications. Afaik forward secrecy, and flexibility in PQ KEXs, is the only place where DC-nets have a clear advantages over mixnets. DC-net come with harder development challenges like synchronization and traitor tracing.

We may experiment with efficient verifiable shuffles just for fun, but initially we'll adopt Loopix's cover traffic model to address active attacks. Afaik there are no really scalable Academic designs employing verifiable shuffles, see the Vuvuzela, Alpenhorn, etc. papers from MIT's CSAIL group.

We cannot protect users from one another in mixnets without SURBs, including Loopix's provider model and afaik Katzenpost. We consider this critical for both financial applications, like defenses against front running, as well as wider social good, well provider designs throw journalist's sources under the bus.

There are numerous similar engineering decisions evaluated here: https://github.com/burdges/lake/tree/master/Xolotl/papers

[gpestana]

We're trying to put together a list of research and projects of privacy preserving primitives and protocols (https://github.com/hashmatter/privacy-preserving-primitives) so that it's easier to system designers and developers to understand what protocols and mechanisms are out there for building privacy preserving networks. It's quite a large scope but hopefully will help to answer this question over time.

Feel free to contribute. W3F messaging protocol js a must-have there

[robertkiel]

Solved during Pre-FOSDEM workshop

[oskarth]

Discussed briefly during workshop. Worth revisiting. Duplicate https://github.com/w3f/messaging/issues/5

[gnarea]

Relaynet is something you may want to add to your survey. Privacy-preserving was a critical requirement, but the primary goal of Relaynet is to maintain connectivity when repressive regimes shut down the Internet (by using meshnets and/or sneakernets as backup). Which in turn leads to stringent privacy requirements, since the adversaries (or their allies) will have deep pockets and users will be risking their lives in some cases.

Here's a succinct, technical description: Relaynet will be a delay-tolerant, overlay network that runs on top of the Internet, sneakernets and meshnets. It supports unicast routing but in the future it'll also support multicast and broadcast. Apps on the network use asynchronous messaging. Communication is end-to-end encrypted (with perfect forward secrecy and future secrecy). The network is defined by an open protocol suite.

I built a proof of concept to make Twitter work on a sneakernet and I've addressed the issues uncovered in a security audit commissioned by the Open Technology Fund.

I think the main difference between Relaynet and the approach(es) you're considering is that, because Relaynet uses asynchronous messaging to achieve delay-tolerance, I'm using a federated style whereas yours is more decentralised. By "federated" I mean that end user devices have to be paired to brokers (called "gateways"), which are Internet hosts operated by a company, a charity or yourself (in a way, they're analogous to VPN servers).

Why didn't I use a truly decentralised/P2P architecture? Because of my target audience: People who have smartphones/laptops but are permanently or temporarily disconnected from the Internet.

• Peers will not be online in the traditional sense -- Alice may be connected to the Internet, but if Bob isn't, they couldn't establish a TCP connection. Although you could theoretically use stuff like IPoAC or the Bundle Protocol, the potentially large latency will make it unusable for 99% of the peers who have a normal connection to the Internet (and it'd get much worse if you tried to do a TLS handshake).
• Even if you solved the problem above, people disconnected from the Internet thanks to repressive regimes won't typically have the means to incentivise people in "normal" countries. They can only pay local prices (and they do pay for sneakernets today).

But despite the differences, I think we're very much aligned when it comes to privacy on the Internet, so maybe there's some opportunity to collaborate? I hope to start building the network soon.

[burdges]

How does Relaynet differ from Briar?

I think offline messaging sounds interesting, but tricky to bring into scope. I suppose one can look to briar for inspiration, meaning always use the mixnet over the internet, like briar always uses Tor, but provide some mesh transport for reaching the internet or sending messages directly via mesh. I think mixnet messages prepared by offline nodes could use SURBs so the online node's internet connection remains hidden, but this still requires the offline node know about the mixnets nodes. I think sending directly via mesh cannot provide full privacy, but maybe users only upgrade specific contacts to that mode or something.

[gnarea]

Hey @burdges! Sorry for the delay, your message got lost in my inbox. To answer your question:

The main difference is that Briar is an app, whereas Relaynet is a network on which you can build apps. And that has a number of implications -- For example, say you want to build a Twitter or Mastodon client: With Relaynet, you'd build a standalone app or integrate a pre-existing one; with Briar, you'd have to change Briar's source code.

Briar ships with useful functionality like blogging, instant messaging and fora, whilst Relaynet itself is just an overlay network and therefore not useful on its own. In my vision of an ideal world, apps like Briar will run on Relaynet, and their developers wouldn't have to write any code to support the underlying network (Internet, sneakernets, meshnets).

I totally see why sneakernet or offline messaging support can be tricky to bring into the scope of the work you're doing at W3F. I think that alone would be a project in its own right.

Also agreed re: meshnets and privacy. I think the risks can be mitigate (not eliminated) with some flooded routing algorithm as opposed to trying to use the shortest route to the destination, but then that'd lead to scalability concerns.