Mike Dilger ☑️ on Nostr: on Future-proofed Cryptographic Identity: The Koblitz curve selected for bitcoin and ...

on Future-proofed Cryptographic Identity:


The Koblitz curve selected for bitcoin and also used by nostr is OK. If coded properly to avoid timing attacks (using constant-time algorithms) and if people don't make incorrect assumptions like "every random set of bits is a valid private key". Nonetheless, it provides 128-bits of security (even as the keys are 256-bits long, the security level is half of that).

The popular and "safe" ed25519 curve also provides 128-bits of security.

But quantum computing is rapidly progressing, and in about 10 years I find it likely that the ECDLP (elliptic curve discrete log problem) will be broken on one of these new quantum computers using Shor's algorithm.

I shudder to think what would happen to Bitcoin. I hope those core devs are thinking about how to 'upgrade'.

I'm thinking about how to design a long-term sovereign distributed bootstrappable identity that doesn't rely on DNS. In terms of cryptography, the most promising algorithm IMHO is SPHINCS+. NIST chose CRYSTALS-dilithium based on lattice cryptography. But lattice cryptography is rather new and hard to reason about, and paper after paper has slightly weakened various lattice-based cryptographic algorithsm. OTOH SPHINCS+ is based on hashes. Hash-based cryptography is easy to reason about, it has been around longer, and it is much less likely to offer up suprises. [There is a perhaps even more secure algorithm called McEliece designed in the 1970s which is post-quantum safe, but unfortunately the key sizes are about 512 kb!].

So to preserve the same 128-bit security in the post-quantum world, SPHINCS+-128s is IMHO the best bet. The 's' means 'size', in that it tries to use less memory (the alternative being 'f' which means 'fast'). This offers actually 133-bit security, has 32-byte public keys (same as what we are used to), but the private keys are twice that size (64 bytes) and the signatures are a whopping 7,856 bytes long. That's not really whopping when you compare to the 256-bit security variant with 29,792 byte signatures.

In any case, I imagine using such a keypair as a "master" keypair to sign your "bootstrap" record stored in a DHT. Not to sign every event with.

But that brings up a problem. Mainline DHT only works with ed25519. A new DHT would need to be stood up that handles (let's say) 16kb bootstrap records digitally signed by SPHINCS+-128s. Let's say we started out with 8 nodes, each holding 4 GB of data. 8 notes is not very distributed but you have to start somewhere. 4 GB (which is rather small) would hold a whopping 268,435,456 bootstrap records. And all 8 notes could have all records, no real DHT sharding needed yet. My point here being that storage space for all these records would not be a problem... the problems would be attacks on the DHT, of which I am less familiar so I won't talk about it here.

What are bootstrap records? This is where you declare what services you use, at which endpoints, and with what keypairs -- e.g. [nostr, npub, relays] or [mastodon, @user@host] or [x, @username]. These kind of tie together multiple identities similar to keybase... if you want them tied... of course you can (and probably should) run multiple SPHINCS+-128s identities. Software that understands these bootstraps can follow you as you move to different platforms, roll over nostr keypairs, or even (ideally) change what servers you use (if nostr didn't have it's own way of doing that).

So anyhow... these are my thoughts. Just thoughts, not plans.