PQ anonymity for Stealth Address Protocol

Privacy
1

PQ SAP - PQ Anonymity

Thanks Hy, @mmjahanara, @Pierre, @winderica, and kassandra for useful discussion and feedback.

TLDR;

This post is the 2nd post of a series of posts on Stealth Address Protocol and its Post-quantum upgrade. See Post Quantum Stealth Address Protocol for the 1st post.

Later post:

Scheme 6 PQ SAP - PQ Spending

A Stealth Address Protocol allows:

  • a receiver to register a public Stealth Meta Address
  • a sender to derive a one-time Stealth Address for the receiver using the Stealth Meta Address and an ephemeral secret (also a nonce)
  • payments from a sender to a receiver, under different one time Stealth Addresses (meaning different nonces) of the same Stealth Meta Address, are unlinkable
  • sender anonymity is not-guaranteed (as a current property)

The (current) components often coupled with the Stealth Address Protocol are:

  • Stealth Meta Address registry where receivers can register their public keys and Annoucement registry where senders can announce their stealth payments to receivers
  • nonce manager on sender’s side to prevent re-using the same one-time Stealth Address twice or more
  • stealth payment discovery or scanning service for stealth payments, for this purpose, we usually rely on Dual Key Stealth Address Protocol, which separates the spending key from the viewing key
 RECEIVER (Bob)                          SENDER (Alice)
 k_view, k_spend                         nonce mgr: fresh r, never reuse
 M = (P_view, P_spend)                        |
      |                                       |
      | register M                            | lookup M
      v                                       v
 [META ADDRESS REGISTRY] ---------------------+
                                              |  s    = KA(r, P_view)
                                              |  P_st = P_spend + H(s)G
                                              |  R    = pub(r), vtag
                                              |
 [LEDGER]              value -> P_st  <-------+
 [ANNOUNCEMENT REGISTRY]  (R, P_st, vtag) <---+
      |
      | Bob (or view-delegate) scan: s' = KA(k_view, R); vtag? P_spend+H(s')G == P_st?
      v
 Bob spends with k_spend + H(s')

 unlinkable : P_st from same M, different r        [ HOLDS ]
 sender     : Alice's account funds + announces    [ EXPOSED ]
 keys       : k_view = detect (delegatable), k_spend = spend

A quantum attacker, observing the permanently-on-chain ERC6538Registry and ERC5564Announcer, will capture R and (K,V), and all the stealth payments to a stealth address P, and can recover r from R, k from K, and v from V, and be effectively the scanner with v and the receiver with k and have full viewing and spending access to the stealth payments.

We focus on upgrading the two core components of an SAP, namely the (1/2)-ECDH and the ECDSA, resulting in a schemeId = 3, 5, and 6 SAP, and interpret the implications to existing components.

Replacing ECDH with ML-KEM aims to protect payment discovery and recipient unlinkability against quantum attackers. Replacing ECDSA aims to protect spending authorization. Schemes 2-5 retain ECDSA and therefore do not provide both properties.

In this first extension of ERC-5564, we attempt to replace the ECDH with a PQ ML-KEM, resulting in SAPs schemeId = 2-5.

We have an accompanied repo for scheme 3 which is the best first step to PQ SAP upgrade

Recalling ML-KEM

We adopt FIPS 203 for ML-KEM Module-Lattice-Based Key-Encapsulation Mechanism Standard, published 13 August 2024.

A KEM (Key-Encapsulation Mechanism) consists of three algorithms and a collection of parameter sets. The three algorithms are:

  • A probabilistic key generation algorithm denoted by KeyGen
  • A probabilistic “encapsulation” algorithm denoted by Encaps
  • A deterministic “decapsulation” algorithm denoted by Decaps
Alice                          :                   Bob
                               :
+------------------+           :
|      KeyGen      |           :
+------------------+           :
     |       |                 :
     |       +-----------------:--------------------+
     v                         :                    v
+------------------+           :           +------------------+
| decapsulation key|           :           | encapsulation key|
+------------------+           :           +------------------+
     |                         :                    |
     v                         :                    v
+------------------+    +------:-----+     +------------------+
|      Decaps      |<---| ciphertext |<----|      Encaps      |
+------------------+    +------:-----+     +------------------+
     |                         :                    |
     v                         :                    v
+------------------+           :           +------------------+
| Alice's copy of  |           :           |  Bob's copy of   |
| the shared secret|           :           | the shared secret|
+------------------+           :           +------------------+
                               :
         r'                    :                    r

A KEM is used to establish a shared secret between two parties Alice and Bob as described above.

  • Alice first runs KeyGen to generate a public encapsulation key and a private decapsulation key
  • The other party, Bob, given Alice’s encapsulation key, runs the Encaps algorithm, can produce the shared secret key r along with its associated ciphertext, and then send the ciphertext to Alice
  • Alice can then run the Decaps algorithm with her decapsulation key and the ciphertext, to obtain r' = r of the shared secret key.

ML-KEM is with three parameter sets: ML-KEM-512, ML-KEM-768, and ML-KEM-1024, with different parameter sizes as shown below (bytes):

encapsulation key decapsulation key ciphertext shared secret key
ML-KEM-512 800 1632 768 32
ML-KEM-768 1184 2400 1088 32
ML-KEM-1024 1568 3168 1568 32

Let us first fix the syntax of ML-KEM (with \lambda being security parameter):

  • (dk,ek) \leftarrow KeyGen(\lambda)
  • (r,c) \leftarrow Encaps(ek)
  • r' \leftarrow Decaps(dk,c)

A successful ML-KEM yields r' = r. A small note is that, given c, the attacker cannot tell whether it is encapsulated with a public ek or a public ek'. This is what we call indistinguishability of keys (IK-CCA, a.k.a ANO-CCA), which turns out to be important for SAP.

Does ML-KEM offer ANO-CCA?

Intuitively and fortunately, yes. There is a dedicated analysis of Post-Quantum Anonymity of Kyber in the quantum random oracle model (QROM). However, it analyzes round-3 Kyber, so applying its results to standardized ML-KEM requires accounting for the changes in FIPS 203. As specified, the FIPS 203 transform matches the intermediate transform in Figure 6 of the analysis: it returns the first half of G on valid encapsulations and uses a separate ciphertext-dependent rejection key on invalid ciphertexts. See our attempt to a high level explanation in ML-KEM and its ANO-CCA.

Direct ML-KEM: SAP schemeId = 2

We directly replace ECDH with ML-KEM.

The Math

Let G be the generator of the Elliptic Curve group, and H(\cdot) a shared-secret-key-to-scalar cryptographic hash function:

  • the receiver randomly samples k the spending key and runs (dk,ek) \leftarrow KeyGen(\lambda) and register (K, ek), where K = kG, to the public registry as the Stealth Meta Address
  • for a one time payment, the sender (in some way) obtains (K, ek), runs (r,c) \leftarrow Encaps(ek), and compute h = H(r), set P = K + hG, sends the fund to P, and then publish c
  • the receiver, or a scanning service that the receiver entrust with the decapsulation key dk, can match the stealth payment by first decapsulating r' = Decaps(dk,c), and recompute h' = H(r'), and the receiving address P' = K + h'G, and test whether P =? P'
  • however, only the receiver, who has k (not even the scanning service who only has dk), can access the fund, with the one-time spending key now being k + h for the public key P = kG + hG

As c is secure against a quantum attacker (attacker cannot learn r or linking c to ek due to ANO-CCA), a linkage back to the Stealth Meta Address (K = kG, ek) is prevented against the said attacker.

The extended ERC-5564

We can extend ERC-5564 as follows:

  • replacing viewing key pair (v,V) with ML-KEM key pair (ek,dk), and modify the algorithms per the above math, now st:eth:0x<spendingPubKey><ek>
  • we can CHOOSE to keep the NAIVE view-tag h^* which is of size 1 byte extracted as the most significant byte from h, this allows checking h^* =? H(r')[0] after recovering r' (instead of another EC scalar multiplication, and EC addition and a hash, albeit this is of a different proportion w.r.t schemeId-1), WITH SOME ANONYMITY RISK (see below).

ERC5564Announcer does not need to be modified except for perhaps a naming change, to emit respective events to announce when something is sent to a stealth address (Announcement(uint256 indexed schemeId, address indexed stealthAddress, address indexed caller, bytes mlKEMciphertext, bytes metadata)). However, with ML-KEM-768, the mlKEMciphertext is 1088 bytes.

ERC6538Registry which centralizes the registration and retrieval of public stealth meta addresses can keep current form (mapping(address registrant => mapping(uint256 schemeId => bytes))). However, with ML-KEM-768, the encapsulation key size is 1184 bytes, the bytes part will be increased by 1151 bytes.

The naive ViewTag vs CRQC

Recalling that

  • P = K + hG = (k+h)G
  • h^* = h[0]

a CRQC that knows the derived public key P can:

  • recover p=\log_G(P);
  • recover k_i=\log_G(K_i) for each candidate public spending key K_i in the registry;
  • compute h_i=(p-k_i)\bmod n and test whether h_i[0]=h^*.

The correct recipient passes while an independently generated wrong candidate passes with probability approximately 1/256. This gives a recipient-linkage filter without breaking ML-KEM. The attack requires P, which becomes recoverable from an ordinary ECDSA spend. We can prevent this direct test by deriving the tweak and view tag independently from the shared secret:

  • h=H(DS1 \parallel r)
  • h^*=H(DS2 \parallel r)[0]

The sender knows r from encapsulation, and the receiver or scanner obtains it through decapsulation. Recovering h through quantum discrete logarithms does not directly reveal the independently derived tag. Thus, the tag’s privacy depends on the protected shared secret r, without requiring the sender to know dk.

This attack is applicable to all ECDSA-based SAPs attempting to upgrade to PQ anonymity via ML-KEM (2-5 in this post).

Retrospective to schemeId = 1

  • The spend cost (gas cost) is the same
  • The forward secrecy issue remains, whoever holds dk can link the stealth payment back to the Stealth Meta Address
  • We need a full decapsulation even if we keep the view-tag.
  • the Announcement of ERC5564Announcer increase roughly by 33x, but on the other hand, this should deter DDoS attack
  • the Stealth Meta Address in ERC6538Registry increase roughly by 18x
  • ML-KEM size makes PIR and OMR worse

Hybrid-Combiner: SAP schemeId = 3

While it is theoretically ideal that scheme 2 where we replace (1/2)-ECDH with ML-KEM is sufficient for post-quantum anonymity, in practice, we usually rely on a hybrid combiner of both ECDH and ML-KEM to hedge ML-KEM security during transitional period (i.e. during migration and BEFORE CRQC arrives), hence we propose schemeId 3 for practical usage. Scheme 3 is the combination of scheme 1 and scheme 2, concretely:

  • Stealth Meta Address is (K,V,ek)
  • Sender shares two secrets with the receiver: r_{ec} using V (as in scheme 1), and r_{pq} using ek (as in scheme 2)
  • We adopt a domain-separated hybrid combiner to combine r_{ec} and r_{pq}
r = SHA3-256(DS || r_ec || r_pq || epk || ct || viewing_pk_ec || ek)

Security Considerations

As the post-quantum anonymity relies entirely on ML-KEM ciphertext, AT LEAST ONE decapsulation is necessary for security, hence, “optimization” such as “let’s make viewtag the 1st byte of hash of r_{ec} to have the same filter cost of scheme 1” is yet another catastrophic optimization.

One may also consider “reusing the scheme 1 meta address as it now seems scheme 3 will work as we append an ek to the end of the scheme 1 address”. Doing this will essentially drags along the history of scheme 1, which is considered to be broken when CRQC arrives.

Pair-wise-KEM-SAP schemeId 4,5

We can extend schemeId-2 to schemeId = 4 with pair-wise hybrid encryption (and similarly schemeId-3 to schemeId = 5), by leveraging the shared secret r to derive a new nonce for subsequent transactions of the same sender-receiver pair. This will remove the mlKEMciphertext (of scheme 2 and 3) and replace the original ephemeralPubKey with a new ephemeralPubKey that is even smaller than that of schemeId-1.

For the sake of readability, we only describe scheme 4 (the only-ML-KEM version).

The Math

Let G be the generator of the Elliptic Curve group, and H(\cdot) a bytes-to-scalar cryptographic hash function:

  • the receiver randomly samples k the spending key and runs (dk,ek) \leftarrow KeyGen(\lambda) and register (K, ek), where K = kG, to the public registry as the Stealth Meta Address
  • for a stealth pairwise-key-exchange the sender (in some way) obtains (K, ek), runs (r,c) \leftarrow Encaps(ek), and compute h = H(r), set P = K + hG, sends 0 to P, and then publish c
  • the receiver, or a scanning service that the receiver entrust with the decapsulation key dk, can match the stealth pairwise-key-exchange by first decapsulating r' = Decaps(dk,c), and recompute h' = H(r'), and the receiving address P' = K + h'G, and test whether P =? P'
  • for a one time payment, the sender who has already shared a pairwise-key r with the receiver, randomly samples \tilde{r}, and compute \tilde{h} = H(r||\tilde{r}), set \tilde{P} = K + \tilde{h}G, sends some fund to \tilde{P}, and then publish \tilde{r}
  • the receiver, or a scanning service that the receiver entrust with the already exchanged pairwise-key r, can match the stealth payment by recomputing h'' = H(r||\tilde{r}), and the receiving address P'' = K + h''G, and test whether P'' =? \tilde{P}
  • however, only the receiver, who has k (not even the scanning service who only has both dk and r), can access the fund, with the one-time spending key now being k + \tilde{h} for the public key \tilde{P} = kG + \tilde{h}G

The Standards

We can extend ERC-5564 as follows:

  • replacing viewing key pair (v,V) with ML-KEM key pair (ek,dk), and modify the algorithms per the above math, now st:eth:0x<spendingPubKey><ek>
  • we can keep view-tag h^* and give the same treatment to \tilde{h}^* of size 1 byte extracted as the most significant byte from h and \tilde{h}, this allows checking h^* =? H(r')[0] and \tilde{h}^* =? H(r||\tilde{r})[0] after recovering r' and \tilde{r} (instead of another EC scalar multiplication, and EC addition and a hash, albeit this is of a different proportion w.r.t schemeId-1).

Notice that naive viewtag derivation should not be used and the same treatment for viewtag above should be applied here to REMOVE ANONYMITY RISK, for both first contact and actual payment messages.

ERC5564Announcer can be used for schemeId-2 (or 3) for stealth key-exchange and schemeId-4 (resp. 5) for stealth payment.

ERC6538Registry which centralizes the registration and retrieval of public stealth meta addresses can keep current form (mapping(address registrant => mapping(uint256 schemeId => bytes))). However, with ML-KEM-768, the encapsulation key size is 1184 bytes, the bytes part will be increased by 1151 bytes.

Retrospective to previous schemes

  • the first contact between the sender and the receiver has additional overhead of the stealth key exchange but then the actual stealth payment costs less than even scheme 1
  • r as a new key to manage and scan per sender-receiver pair (subject to short-circuit on first match), however this means that now receiver can delegate r instead of ek (and/or V), and at the same time, now forward secrecy is more fine-grained with the pairwise r
  • additionally, IF the sender makes \tilde{r} a COUNTER (per r) WITHOUT PUBLISING IT, while we still preserve randomness of \tilde{h} = H(r||\tilde{r}), receiver doesn’t need to store \tilde{r}, but only keep track of the counter, or simply scan from 0, to match its stealth payments, indeed, management of r is easier than management of all shared secrets of previous schemes

Worthy Lightweight Deviations

A stealthier SAP

Notice that the key pair of all previous schemes maintain a key K, mathematically speaking, K has the same property of V, which means, an additional secret can be shared between the sender and the receiver with the cost of ONE additional ephemeralPubKey, this opens a potential upgrade to SAP, which we call “a-stealthier-SAP”. All we need to do, applicable to all previous schemes, are the following additional steps (and some trivial modifications to the ERC-5564 which make it a new scheme that is still compatible with the existing infrastructure ERC5564Announcer and ERC6538Registry):

  • sender samples r_K
  • computes R_K = r_KG and S_K = r_KK,
  • publishes R_K in the announcement,
  • and sends fund from an address B to P_K = K + H(S_K)G
  • P = K + H(S)G is kept for matching purpose, and this goes into the stealth address field of the announcement
  • sender uses another address A to send the announcement
  • announcement and actual payment can be in different block

Concretely it gives the following:

Party Recognizes the notification Derives the actual payment address Can spend
Sender Yes Yes No
Scanner holding v Yes No, from the cryptographic inputs alone No
Receiver holding k,v Yes Yes Yes
Outside classical observer Not directly Not directly No

This effectively disconnects the stealth payment (from B to P_K) and the announcement (caller A with stealth address P for matching) and make a stealth payment not being obviously classified as a stealth payment anymore. Yet another great effect that this can give, is now Ethereum can be used to facilitate stealth payments on another blockchain, i.e. Ethereum for announcement while actual (no-one-can-tell-it-is-a-stealth) payment can happen on another chain (assuming there is always a way to modify the algorithm to accomodate the foreign chain’s addressing scheme).

IMPORTANT: the PQ version should combine S_K with r_{pq} as in schemeId 3, and we have

Observer Knows S_K? Knows r_{pq}? Can reconstruct the payment address?
Classical scanner holding dk No Yes No
Quantum outsider without dk Yes No No
Quantum scanner holding dk Yes Yes Yes

While this may have already been considered before, making this happened in the classical settings essentially double the announcement cost (2 ephemeralPubKeys to announce) compared to scheme 1, however in the post quantum settings with the addition of ML-KEM it makes this cost has become almost free which makes it even more appealing now.

Post-quantum Recoverability

This is a upgrade that any SAP (even scheme 1) can consider, if we make the key k a hash of a seed s, which is never used in any SAP operation (except during key management), combining this with the onchain announcement (which has the secret r protected by ML-KEM), we have PQ recoverability, i.e. if a quantum incident happens, the legitimate owner of the SAP meta address can prove in zk k = H(s) and use the observation of p = k + r to beat quantum adversary in the address recovery (assuming we have an enforceable, precommitted recovery policy, or an explicit assumption about future consensus intervention). Expanding this to a complete scheme is an interesting and important future work that we will consider.

PQ spending for Stealth Address Protocol