PQ anonymity for Stealth Address Protocol

What it is

Second post in an ethresear.ch series upgrading Ethereum's Stealth Address Protocol (ERC-5564/ERC-6538) to post-quantum anonymity by swapping the (1/2)-ECDH key agreement for ML-KEM (FIPS 203). It defines schemeIds 2–5 (scheme 6, PQ spending, is a later post). Schemes 2–5 keep ECDSA for spending, so they buy PQ anonymity (payment discovery + recipient unlinkability), not PQ spending authorization.

The view-tag attack and its precondition

The naive optimization keeps the 1-byte view tag as h* = h[0] where P = K + hG = (k+h)G. A cryptographically-relevant quantum computer (CRQC) that knows the derived address P can recover p = log_G(P), recover k_i = log_G(K_i) for every candidate spending key in the registry, compute h_i = (p - k_i) mod n, and test h_i[0] == h*. The true recipient always passes; a wrong candidate passes with ≈1/256. This is a recipient-linkage filter that works without breaking ML-KEM.

The precondition the summary omits: the attack requires P, which only becomes recoverable from an ordinary ECDSA spend. An unspent stealth address is not exposed by this filter. Because it hinges on ECDSA discrete-log recovery, it applies to all ECDSA-based schemes (2–5).

Fix — derive tweak and tag independently from the shared secret with domain separation:

• h = H(DS1 || r)
• h* = H(DS2 || r)[0]

Recovering h via quantum discrete log no longer reveals the independently-derived tag; tag privacy now rests on the ML-KEM-protected secret r.

Hard invariant for implementers

PQ anonymity rests entirely on the ML-KEM ciphertext, so at least one full decapsulation is mandatory before matching. Any "optimization" that makes the view tag the first byte of H(r_ec) (the classical secret) to match scheme-1 filter cost is called a "catastrophic optimization." Also: do not reuse a scheme-1 meta address by appending an ek — it drags along scheme-1 history, which is considered broken once a CRQC arrives.

Size/gas overheads (ML-KEM-768)

• Encapsulation key: 1184 bytes → ERC6538Registry entry grows by 1151 bytes (~18×).
• Ciphertext: 1088 bytes → ERC5564Announcer payload grows ~33× (noted as an incidental DDoS deterrent).
• Larger sizes make PIR and OMR scanning worse. Spend gas cost is unchanged from scheme 1; forward-secrecy issue (dk-holder can link back to the meta address) remains.

Variants worth noting

• schemeId 3 — hybrid combiner running ECDH and ML-KEM in parallel, mixing both secrets: r = SHA3-256(DS || r_ec || r_pq || epk || ct || viewing_pk_ec || ek). Recommended as the practical migration step (hedges ML-KEM during transition).
• schemeId 4/5 — pairwise-KEM: one KEM exchange establishes r per sender-receiver pair, then subsequent payments use h̃ = H(r || r̃) with r̃ optionally an unpublished counter (receiver scans from 0). This drops the per-payment ciphertext, making later payments cheaper than scheme 1.
• "stealthier SAP" — publishes R_K = r_K·G, funds P_K = K + H(S_K)G from a separate address, and announces a different matching address P via yet another address, decoupling payment from announcement so it isn't identifiable as a stealth payment (and enabling cross-chain payment). Nearly free once ML-KEM overhead is already paid.

Caveats

ANO-CCA for ML-KEM is argued from an analysis of round-3 Kyber in the QROM; the authors note applying it to standardized FIPS 203 requires accounting for the transform changes and offer only a "high-level" justification. PQ spending (scheme 6) and the recoverability scheme are left as future work.