Nymchat technical whitepaper

Post-Quantum Key Agreement in Nymchat

Distributing ML-KEM-768 public keys over Nostr without a directory or a registry, and seeding them from a secret that no public value exposes.

Adding a post-quantum key exchange to a messenger is mostly not a cryptography problem. The primitives are standardized and the libraries exist. The hard part is that every participant now needs a second public key, and a decentralized network has nowhere obvious to put it. This paper describes how Nymchat answers that — where the second key comes from, how it reaches the people who need it, and what the interface is allowed to claim about the result — and, in the last section, what that result does not protect.

1The problem

Nostr private messages are encrypted with NIP-44, which has two separable halves. The half that scrambles the plaintext — ChaCha20 with an HMAC-SHA256 tag, keyed through HKDF (RFC 5869) — is not meaningfully threatened by a quantum computer; Grover's algorithm costs a square-root speedup against a symmetric key, and 256 bits absorbs that. The half that agrees on the key is elliptic-curve Diffie-Hellman over secp256k1, and Shor's algorithm solves the discrete logarithm outright. Recovering one private key from its public counterpart retroactively exposes every shared secret that key ever produced.

The threat this creates is not deferred until such a machine exists. An adversary with storage can record ciphertext today and decrypt it whenever the capability arrives. Anything sent now that still matters then is already compromised. This is the specific attack a post-quantum key exchange defeats, and it is the reason the work cannot wait for the machine to be built.

1.1 The question this paper answers

The mitigation is well understood: run a post-quantum key encapsulation mechanism alongside the classical exchange, so an attacker has to break both to read anything. Nymchat uses ML-KEM-768 (FIPS 203). That immediately raises a distribution problem:

An npub is self-contained. You can write it on paper, read it aloud, or scan it from a screen, and it is all anyone needs to encrypt to you. An ML-KEM-768 public key is 1,184 bytes. It cannot be read aloud, it will not fit in a username, and it does not belong in a QR code beside an identity that is only 32 bytes.

Size is the easy part. The harder part is that a second key brings three distinct problems, and the rest of this paper is largely an answer to them:

• It can be substituted. A key nobody can read at a glance is exactly the kind of thing an attacker swaps for their own. Section 4 binds it to the identity with a signature, which settles this one outright.
• It has to agree across a user's devices. The same account on a phone and a laptop must present the same key, or messages sealed to one cannot be opened on the other. Section 3.2 gets it there.
• It can be lost. The public key is republished from a secret, so what actually has to survive is that secret — and by construction nothing else reconstructs it. Section 10.1 states plainly what that costs, because this one is not solved so much as paid for.

2Design constraints

Four constraints shaped the answer, and they rule out most of the obvious designs before any code is written.

1. As few secrets as possible. Nostr users already carry exactly one secret, the nsec. Every additional secret is another way to lose your history, and someone who knows to back up an nsec will not know to back up anything else. Section 3.1 shows this one cannot be met outright — a post-quantum key derived from the nsec provides no post-quantum protection at all — so the design spends exactly one secret and no more: a single piece of key material, generated once per identity, presented in the same shape as the nsec and in the same place, so that whoever knows how to keep one knows how to keep the other. Section 10.1 is honest about what that still costs.
2. No authority. There is no server that may be trusted to say which key belongs to whom. Any such server becomes the point at which messages can be redirected.
3. Multiple devices, one identity. A Nostr identity is commonly used from several clients at once. Whatever key material exists must end up identical on all of them, and the paths that carry it there must not themselves be readable by the adversary the feature is defending against.
4. No negotiation. Any in-band exchange of “which ciphers do you support?” is a surface an attacker can strip to force the weaker option. The design must have nothing to downgrade.

3An independent root secret

The load-bearing decision is that the ML-KEM decapsulation key is seeded from key material that no public value exposes. Each identity gets one root secret, generated once:

pqRoot   = 32 bytes from a CSPRNG, generated ONCE per identity

seed     = HKDF-Expand(
               HKDF-Extract(salt = "nym-pq-root-v2", IKM = pqRoot),
               info = "mlkem768/epoch/" || epoch,
               64 bytes)

(ek, dk) = ML-KEM-768.KeyGen(seed)

The root is presented to the user the way an nsec is: bech32 with the human-readable prefix nympq, so it reads as nympq1…, shown beside the nsec in the identity screen behind the same reveal interaction, copied with the same control, never logged and never sent anywhere in the clear. It is not a password and it is not a login. It is key material the user can save, exactly like the nsec.

The salt is domain-separated on purpose, so no other secret can ever derive the same keypair. The epoch counter drives rotation (Section 9).

3.1 Why the key cannot be derived from the identity key

The obvious design is to seed the keypair from the secret the user already has:

seed = HKDF(salt = "…", IKM = nsec)          // do not do this

It is attractive for four reasons, all of them real: nothing new to back up, because the nsec already is the backup; every device agreeing by construction, with no synchronization protocol to go wrong; one replaceable announcement per identity being obviously correct, because devices cannot disagree about the key; and the key existing before it is ever published, so a client can seal something to itself on first run.

All four benefits are worthless, for one reason. Shor's algorithm run against a published npub yields the nsec. The seed derivation is a public algorithm over the nsec. So the adversary who breaks the classical half reconstructs the post-quantum half by running the same HKDF that everyone else runs. Against harvest-now-decrypt-later — the one threat the feature exists to stop — a key derived this way adds nothing whatsoever.

The second clause of that rule does as much work as the first. An independently generated secret that is then synchronized between a user's devices inside an ordinary NIP-44 message is the same failure with extra steps: an adversary records that message today and recovers its classical key later, and the root falls out. That is why the paths in the next section are the paths they are, and why none of them is “send it to your other device.”

3.2 Getting the root to the user's other devices

Constraint 3 of Section 2 — one identity, several devices — cannot be satisfied by arithmetic here, because the whole point is that the key is not a function of anything the devices already share. It has to be satisfied by transport instead, and there is exactly one path: the user moves the nympq1… code themselves.

The root is displayed as nympq1… beside the nsec, and a second device accepts it pasted into the same panel. That is the whole mechanism. A device that has not been given the code cannot participate, which Section 4.2 describes.

Manual transfer is a deliberate floor rather than a first step. The rule in Section 3.1 says the root may never travel under classical-only encryption, and every mechanism that would make this automatic — syncing it through a relay, wrapping it to the identity key — violates exactly that. The step the user performs is the reason the protection is real.

The format leaves room for a wrapped path: a record may carry a list of wraps, each an AEAD blob under a key the user can reproduce on another device — a passkey PRF output, for instance. Nothing ships one today, and until something does, the nympq1… code is the only way across. Section 10.1 states what that costs.

The record itself lives in its own settings category, nymchat-pq-root, and syncs the way the other categories do. Even carrying no wraps it does necessary work: its presence is how a second device learns that this identity already has a root, which is what stops it minting a rival one (Section 3.3).

3.3 Generation and adoption

On boot, holding a durable identity, a client works in this order:

1. Look for an existing nymchat-pq-root record.
2. Record found, and this device can unwrap it — adopt it and announce this identity as post-quantum capable.
3. Record found, and this device cannot unwrap it — do not generate a new root, and do not publish any announcement at all. Prompt the user to link this device by entering the nympq1… code from a device that already has it.
4. No record — generate a root, publish the record, announce, and show the nympq1… code to the user once so they can save it.

Step 3 is the step that is easy to get wrong, and it is the reason the ordering is written down rather than left to each implementation. Two devices that each decide to generate a root produce two independent roots under one identity, and that is the failure this ordering exists to prevent.

4The capability announcement

The public half of the derived keypair is published as an addressable NIP-01 event — kind 30078, tagged nym-pq:

{
  "kind": 30078,
  "tags": [
    ["d", "nym-pq"],
    ["t", "nym-pq"],
    ["expiration", "<unix seconds>"]
  ],
  "content": {
    "v":     2,
    "alg":   "mlkem768",
    "nym":   1,
    "epoch": 0,
    "pk2":   "<base64url ML-KEM-768 encapsulation key>",
    "exp":   <unix seconds>,
    "devices": [ ... ]
  }
}

Addressable means the relay keeps one event per (kind, pubkey, d-tag), so a republish replaces the previous announcement in place. Each identity therefore has exactly one current record, which is what makes “look up Alice's key” a single unambiguous fetch rather than a list to reconcile.

The signature is the binding. The event is signed by the identity key, so the claim “this ML-KEM key belongs to this npub” is exactly as strong as the npub itself. Substituting a different encapsulation key requires forging a secp256k1 signature. An attacker who can do that does not need to bother with the KEM.

Announcements expire. A seven-day NIP-40 expiration, republished every 24 hours, keeps the record a statement about a client that is still running rather than one that used to be. The root itself never expires; only the claim about it does.

A lapsed announcement is read exactly like one that never carried a key: peers send ordinary NIP-44, which every login can read, and the client resumes the post-quantum exchange on its next connection, when it republishes. So going quiet for longer than a week costs protection for the messages sent during the gap — they are classically encrypted rather than quantum-resistant — and costs nothing else. Delivery is unaffected, nothing already received becomes unreadable, and no action is needed on return.

That asymmetry is the reason for the expiry rather than an accident of it. Without one, a record outlives the key it names: a device that is wiped, reset, or has its root replaced leaves a standing instruction to encapsulate to a key nobody holds any more, and messages sent under it are lost with no error on either side. Seven days bounds that window, and lets relays drop the record themselves rather than relying on clients to notice.

The key field names its format. The field is pk2, and the digit is part of the contract rather than decoration: it names the payload format the key may be used with. A reader that does not recognize the field concludes “Nymchat client, no post-quantum key” and sends ordinary NIP-44, which every login can read. That is the correct failure direction, and it is worth stating as a rule the format numbering exists to enforce: an unrecognized capability claim must cost protection, never delivery. A key a peer cannot use is worse than no key at all, because the message it produces is lost with no error on either side.

4.1 Absence is meaningful, and three-valued

A subtle but important detail: the announcement is published by every Nymchat client, not only post-quantum-capable ones, and the key field is optional. That yields three distinguishable states rather than two:

Collapsing the third row into the fourth would be a real loss. A keyless announcement is a signed statement that the sender runs Nymchat, which lets the send path skip a speculative cross-protocol wrap it would otherwise have to include for anyone it cannot identify.

4.2 A device that cannot open the root stays silent

The announcement is replaceable: one event per identity, last write wins. That is what makes the single-record design work, and it is also what makes an unlinked device dangerous if it publishes. A device that announced a key it had minted for itself would clobber the real record and send every peer to encrypting under a key the other devices cannot open.

So a device that knows a root exists but cannot open it publishes no announcement at all. It is not broken and it is not locked out of the application: it still reads every message it has the keys for and still sends classically, while prompting the user to link it. Silence is the correct behavior for a device that cannot speak for the identity.

5Discovery and the send decision

Clients learn peers' keys two ways. A standing subscription covers the people a user actually corresponds with — open conversations and group members — so their announcements arrive as ordinary events. For a peer met for the first time, a one-shot query runs at send time, bounded at 2.5 seconds; if it does not resolve, the message goes classical, which is the behavior that existed before post-quantum was added rather than a new failure mode.

A negative result is cached for ten minutes rather than forever. A user who links a new device, or who moves from a browser-extension login to a local key, becomes post-quantum capable mid-conversation, and a permanently cached “no” would keep them on classical encryption for the life of the announcement.

5.1 Why there is no downgrade attack

The routing decision reduces to a single question:

pq = (we hold a signed, unexpired ML-KEM key for this recipient)

There is no capability negotiation, no supported-algorithms list, and no field an attacker can clear to force a weaker path. Holding the announcement is the negotiation, and it is signed. The failure mode of a stripped or withheld announcement is that the message goes classical — the status quo before this feature — rather than that a hybrid message is downgraded to something forgeable.

The converse also holds and matters more: a client sends hybrid only when it holds a key, and holding the key is proof the recipient can decapsulate. There is no state in which a message is sent post-quantum to someone who cannot read it.

6The hybrid construction

Nymchat does not replace NIP-44. It wraps it. An unmodified NIP-44 ciphertext is the inner layer, and ML-KEM keys an outer AEAD around it:

inner = nip44_encrypt(plaintext, conversation_key(sender, recipient))

info  = "nymchat-pq2" || sender_secp_pk || recip_secp_pk || kem_ct || recip_kem_pk
prk   = HKDF-Extract(salt = "nymchat-pq2-v1", IKM = kem_ss)
key   = HKDF-Expand(prk, info || "key",   32)
nonce = HKDF-Expand(prk, info || "nonce", 12)

outer = ChaCha20-Poly1305(key, nonce, plaintext = inner, aad = info)

payload = "pq2." || base64url(kem_ct) || "." || base64url(outer)

Both secrets must still be recovered to read the message: the outer layer yields only a NIP-44 ciphertext, and opening that needs the classical ECDH. A quantum adversary who breaks secp256k1 gets the inner key and still faces ML-KEM; a break of ML-KEM strips the outer layer and leaves NIP-44 standing. Each input earns its place:

• kem_ss keys the outer layer alone. Nothing in this derivation touches the raw ECDH output, which is what Section 6.1 turns on.
• kem_ct, recip_kem_pk and both identity keys are bound in as associated data, so the outer layer is committed to the exact transcript that produced it. Splicing a ciphertext onto another sender's identity fails authentication rather than decrypting.

Encapsulation is performed fresh on every message. The recipient's ML-KEM key is long-lived, but each message carries an independent ciphertext and therefore an independent kem_ss. That is what makes deriving the nonce rather than randomizing it sound: ChaCha20-Poly1305 is broken by reusing a (key, nonce) pair, and here the key itself is new for every message, so no pair can repeat.

6.1 Why the layers stay separate

The alternative is to mix both secrets into a single conversation key and hand that to NIP-44:

ck = HKDF-Extract(salt = "…",
                  IKM  = ecdh_x || kem_ss || …)          // do not do this

That construction is sound as cryptography. It has one structural problem: it needs ecdh_x, the raw x-coordinate of the ECDH output, as key material — and a browser extension (NIP-07) or a remote signer (NIP-46) never returns that value. It performs NIP-44 on the caller's behalf and hands back a ciphertext, which is the entire point of holding the key somewhere the application cannot reach.

Mixing the secrets therefore excludes every login that keeps the identity key in a signer, which is to say the most careful users, and no amount of work on the key derivation can change it. Layering removes the dependency: NIP-44 stays whole and is produced by whatever holds the identity key, signer included, while the KEM half is computed from the recovery code the client holds directly. Signer logins are ordinary post-quantum participants in both directions.

The cost is bandwidth, and it is not small. The ML-KEM ciphertext is 1,088 bytes and rides on every message, base64url-encoded to 1,451 characters; the outer AEAD adds a 16-byte Poly1305 tag and expands the NIP-44 payload it wraps by a third. A 50-character message grows from 176 bytes to 1,712, and a 2,000-character one from 2,820 to 5,238. The floor is roughly 1.5 KB per message regardless of how short the message is, which is the price of encapsulating afresh every time rather than reusing a shared secret.

6.2 Self-describing payloads

The pq2. prefix makes deployment incremental: it is self-describing, so a client picks the decryption path by inspecting the payload rather than by trusting a tag or remembering what a peer supports. A reader that does not recognize a prefix fails to open that payload rather than mis-reading it, and messages sealed before either side could do post-quantum stay readable as ordinary NIP-44 with no migration.

6.3 Both layers of the gift wrap

A NIP-17 private message is a NIP-59 gift wrap: an unsigned rumor, sealed under the sender's identity key (kind 13), then wrapped under a throwaway key generated per message (kind 1059). On a login that holds the identity key directly, Nymchat hybridizes both layers, each with its own encapsulation.

A signer login gets the outer layer only. The seal is produced by the signer as ordinary NIP-44 — the application never sees the key that makes it — so it cannot be hybridized in place. This costs nothing against the attack in question: the seal is reachable only through the wrap, and the wrap is what a recorder stores. An adversary holding recorded traffic must break ML-KEM before a seal is even visible to attack.

7Group messages and partial coverage

A group message is not one ciphertext. It is the same plaintext fanned out to every member, each copy encapsulated to that member's own ML-KEM key. A member who has published a key gets a hybrid wrap; one who has not gets a classical wrap.

This creates an accounting problem that a naive implementation gets wrong. If eight of ten members receive a hybrid copy, the message is not eight-tenths protected. An adversary needs one classical copy of a plaintext that is identical in all ten, so the message is protected only if every copy is.

Nymchat therefore tracks per-message coverage during the fan-out — the count is only knowable while the wraps are being built — and the badge reports “quantum-resistant to 8 of 10 members” rather than claiming the message is protected. Where no count is available, which is the normal case for a received group message (only the sender counts the fan-out), the interface reports partial rather than full protection. Claiming full protection on the strength of one's own copy alone would be an overstatement about the message as a whole.

7.1 What the shield reports

The shield states the truth about the message, not about the software that sent it:

• Full protection: every copy of this plaintext went out hybrid.
• Partial: some copies of a group message went out classically. Drawn degraded rather than full, because one classical copy of a plaintext identical in all of them is all an adversary needs.
• Classical is stated outright rather than shown as no badge, because an absent indicator is ambiguous between “unprotected”, “broken”, and “this build lacks the feature”.

The verdict is recorded when the message is sealed rather than recomputed from what a peer advertises later. Ciphertext that already exists cannot become better protected than it was, and an interface that redrew old messages on the strength of a new announcement would be asserting something false about bytes on a relay.

The group rules above stack on top of this rather than replacing it: a group message is fully protected only when every member's copy was, and a received group message with no coverage count shows partial.

8Copies addressed to yourself

Several things a client stores are encrypted to the user's own identity: synced settings, the conversation list, group keys, and the message archive. These carry more about a user than most single messages do, so leaving them classical would make them the weakest stored artifact regardless of how carefully the messages themselves were sealed. They use the same hybrid, encapsulated to the user's own root-derived key — with the one exception described in Section 3.2, the nymchat-pq-root category itself, which cannot be sealed under a key that only it can produce.

These artifacts are where the design matters most. A settings blob or an archive row sits in one place for years, which is exactly the shape of thing a harvest-now-decrypt-later adversary collects — far more so than any single message, which is at least ephemeral in the user's own mind.

One constraint governs the format here rather than the key. A self-addressed copy has to be readable by every device on the account, so each device advertises what it can open in the roster its announcement carries, and the account writes only what all of them can read. Writing anything else would lock a device out of its own settings — the same silent failure Section 3.2 avoids by other means, arriving from a different direction.

9Rotation

The epoch counter in the derivation is what makes rotation possible without new key material. Incrementing it yields a fresh keypair from the same root and a republished announcement; peers pick up the new key from the replaceable record. Rotation therefore does not ask the user to write anything down a second time: the root is generated once per identity and the epoch does the turning.

9.1 Old epochs are kept, and nothing is re-encrypted

Nothing is rewritten when a key rotates. A client builds decryption candidates from the current epoch down to epoch − 3, so a message sealed shortly before a rotation still opens against the keypair that was current when it was sent.

That window is what makes rotation safe to do at all: without it, every rotation would strand whatever was in flight. Anything already sealed stays readable for the life of the identity, because a message the user can no longer open is strictly worse for them than one whose protection cannot be improved retroactively (Section 10.5).

10What this does not protect

A paper that only lists what a design achieves is not describing a system, and overstating a security property in an interface is worse than omitting it. The following are outside what this construction defends.

10.1 The root is a second secret, and losing it is unrecoverable

This is the design's real price. The constraint in Section 2 that a user should have exactly one thing to keep cannot be met: the nsec alone does not reconstruct the post-quantum key, because the whole point is that no public value and no other secret exposes it. If no device holds the root and none of Section 3.2's wraps can be opened, material sealed to the root-derived key is not recoverable. There is no escrow and there is deliberately no authority that could hold one.

With manual transfer the only path, this is sharper than it may first read. A user who never copies the nympq1… code anywhere has exactly one copy of it, on one device, and losing that device loses every post-quantum message, settings blob and archive row sealed to it. The nsec does not help; that is the property the whole design rests on.

Any wrapped path added later must clear the same bar the manual one does. An attacker attacks the cheapest path available, so a scheme is worth what its weakest recovery route is worth — a memorable passphrase, for instance, would put the whole thing at whatever the passphrase is worth, and the wrapped row is exactly the artifact a harvest-now-decrypt-later adversary collects and grinds offline at leisure.

10.2 Authentication, as distinct from confidentiality

Every signature in Nostr is Schnorr over secp256k1, and that is unchanged here. An adversary with a quantum computer could forge signatures and impersonate a user in real time. What the hybrid key exchange defeats is harvest-now-decrypt-later: an attacker recording traffic today cannot read it later. It does not make a message unforgeable against an adversary who already has the machine. This distinction is carried into the applications deliberately — the padlock indicator reports authentication, the shield reports confidentiality, and they are separate glyphs because a message can have one without the other.

It also bounds what the announcement in Section 4 can promise. The binding between an npub and an ML-KEM key is a secp256k1 signature, so an adversary who can forge those can substitute a key of their own. Confidentiality against a future adversary is not the same as authenticity against one.

10.3 Metadata

Gift wrapping conceals the sender, the recipient beyond a single p tag, the kind, and the timestamp of the inner message. It does not conceal that an event exists, its size, or when a relay received it. Traffic analysis is not addressed by any part of this design.

10.4 The offline mesh

Nymchat's Bluetooth mesh transport is a separate protocol with its own handshake, and it is not covered by this work. Messages over the mesh are classical.

10.5 Messages already sent

Ciphertext recorded while either side was still classical stays classical permanently. It already exists and cannot be re-sealed. Protection begins at the message where both sides held post-quantum keys, not at the moment the feature was switched on.

11Alternatives considered

12Implementation parity

Nymchat ships two independent implementations of this construction — one in JavaScript for the web application, one in Dart for the mobile applications, including a from-scratch ML-KEM-768 port. Two implementations of the same primitive is ordinarily a liability, so they are pinned against each other rather than trusted to agree.

The Dart ML-KEM implementation is validated against the official NIST ACVP known-answer tests for ML-KEM-768 (ML-KEM-*-FIPS203) — 25 key-generation, 25 encapsulation and 10 decapsulation cases, run as their own suite. Those are the vectors NIST publishes to validate an implementation, so passing them is evidence the port is correct, not merely evidence that the two clients agree with each other. Above that, a shared fixture of test vectors — seed derivation, encapsulation, both payload formats, and complete gift wraps — is generated from the JavaScript reference and checked by both test suites. The root secret extends that fixture rather than replacing it: root to seed, root to keypair, the root's public fingerprint, and the derived key, nonce and associated data of the outer layer are vectors of their own, so the two clients cannot disagree about what a nympq1… code means or about the bytes a message is sealed with. A divergence in either implementation fails the build rather than producing a message the other client cannot open.

The fingerprint is worth naming among these. It is what tells a device “this is the root I hold” from “this is a different one”, and a client that could not reproduce another client's fingerprint would read a perfectly good record as no record at all — and then, following Section 3.3, mint a second root and split the identity. It is a vector for exactly that reason.