We’re primarily discussing metadata privacy while the SoK paper by Nik Unger, et al. deals more with authentication, an entirely separate question. We should avoid that derail here, but I’d caution against focusing on deniability between users, like Nik’s PhD work does, although deniability arises naturally below that.
Anyways…
There are numerous academic proposals for messaging that provide metadata privacy in one respect or another, but many lack real scalability. Source-routed mixnet salability is limited by the PKI for nodes. True DC-nets cannot scale. At best DC-nets are only a transport for a mixnet, but an extremely complex one. You obviously cannot scale up broadcast schemes like Whipser or Secure Scuttlebutt, but worse they do not protect senders. PIR has cool blockchain applications, but actually doing decentralize PIR requires a massive research effort, and they serve only highly specialized use cases. Almost all these PIR issues apply to the hybrid mixnet-to-PIR schemes from the MIT CSAIL group, so if you manage then you have a system with like twice the complexity of a mixnet and fewer applications. In short, mixnets are the only scalable option for metadata privacy.
We want a source-routed mixnet work with a sphinx-like packet format and loopix-like mixing and cover traffic. If however you literally follow the loopix paper then their “providers” scheme break receiver anonymity, which creates ethical problems and breaks many financial applications, and cannot be considered decentralized.
Instead, we need a sphinx-like packet format that supports chaining single-use reply blocks (SURBs), which requires adding a “SURB log” field to the packet header. I’ve some notes on the engineering decisions around this in
At the theory level, we should update the security proofs for sphinx to formalize how you use this SURB log field for more complex or group protocols of the sort Status IM does.
I believe the hardest open question is improving the scalability of the mixnet PKI, primarily by understanding the sampling better, but one might explore radical ideas like MPC and pairing-based tricks, like punctured encryption, what I call index-based encryption, or maybe even non-source-routed schemes. At present, almost all non-source-routed schemes only work for highly specilized cases, like voting.
At W3F, we also now have sensible crypto-economic designs for measuring/rewarding relays that avoid per hop payments. Any per hop payment design sounds much too slow and worse creates a crypto-economic scenario that quickly breaks cover traffic. I’ll do a write up in the near future, but I spent the last couple months side tracked by nit-picky signature scheme concerns for polkadot.
the post to signal your interest.