Thread by @pwuille

1/7 New write-up: github.com/sipa/writeups/…

Imagine you can encrypt all of an application's P2P network connections, but only some are deliberately to specific peers, while others are just made randomly.

How private can you make an authentication protocol for this use case? Very!

2/7 The most surprising part is that if you can make it so that a Man-in-the-Middle cannot tell deliberate connections and random ones apart, the random ones get some protection too: MitMs can't selectively intercept if every connection could be an attempt to authenticate.

3/7 How to achieve that? All you need is to make sure responders don't learn which (unsuccessful) keys the attempt was for, and treat failed authentication attempts equal to random ones. Then run with random keys if you don't desire authentication.

4/7 It seems that it is not that hard to construct protocols which achieve this, as well as more far-reaching privacy properties. But at the same time, it does seem like a problem space that's unstudied for now.

5/7 The write-up is primarily intended as an introduction to the (interesting, IMO!) problem space and an informal description of the desired cryptographic properties it has. It also lists a few example protocols that achieve them, but proofs are a work in progress.

6/7 My interest is specifically in the context of P2P like Bitcoin's, where most connections are random, but sometimes people make deliberate connections (e.g. between their own nodes). We also want to avoid introducing discoverable identities here.

7/7 I do hope this can turn into a more formal publication at some point, but in the interest of having something to point to, this write-up is a start.

Thanks to all that contributed to the write-up and ideas it is based on: Greg Maxwell, @real_or_random, and @murchandamus.