tevador/seraphis-pq.md

## seraphis-pq.md

      
    Raw
  

              seraphis-pq.md
            
          
    [Draft] Zero-cost post-quantum mitigations for Seraphis

This draft presents post-quantum mitigations for Monero's next transaction protocol Seraphis. These mitigations are "zero-cost" in the sense that they only involve changes to the way private keys and blinding factors are calculated, which is transparent to blockchain verifiers. Mitigated keys will be compatible with a future hard-fork that can be put in place to ensure monetary soundness and security of the protocol even against a quantum computer.
While these mitigations do not prevent a quantum adversary from breaking the privacy of past transactions, they protect Monero from a total collapse that would result from an undetectable money supply inflation or  the theft of users' funds.
1. Introduction

In 2020, Monero performed a post-quantum security audit that confirmed severe vulnerabilities of the transaction protocol against quantum algorithms [1]. In descending order of severity, a quantum adversary (QA) would be able to:

undetectably inflate the money supply,
steal users' funds,
deanonymize the transaction graph.

While the audit mostly focused on Monero's current transaction protocol RingCT, the above issues also apply to the next transaction protocol Seraphis [2]. In addition, Seraphis is also vulnerable to a double-spending attack because its key images are not perfectly bound to the output keys. Double-spending would also enable a QA to undetectably inflate the money supply.
The following mitigations are proposed for Seraphis:

Embedding ElGamal commitments into Pedersen commitments. ElGamal commitments are pefectly binding and prevent a QA from opening the commitment to arbitrary values.
Using hash-based commitments to prove the correctness of key images, preventing a QA from double-spending.
Embedding a quantum-resistant public key into the private spend key to prevent a QA from stealing outputs they don't own.

1.1 Preliminaries

We use the additive notation for elliptic curve operations. Lowercase letters usually refer to the elements of Z_q, where q is the prime order of the main subgroup of the ed25519 elliptic curve. Uppercase letters usually refer to group elements (elliptic curve points). G is the generator of the elliptic curve and H, J, X, U are four additional generators with a (presently) unknown discrete logarithm relationship to G.
The function H_q() refers to a hash function {0,1}* -> Z_q. The function H₃₂() refers to a hash function {0,1}* -> {0,1}²⁵⁶. The concatenation operator is denoted by ||.
Domain-separation tags are denoted with a capital letter T.
2. Seraphis basics

2.1 Amount commitments

Similarly to RingCT, transaction amounts in Seraphis are hidden with Pedersen commitments. Pedersen commitment C to a value v using a blinding factor r is derived as:
C = r G + v H (2.1.1)
Rewritten in terms of log_G, the commitment becomes:
c = r + v*h (2.1.2)
where H = h G. This is an equation with 2 variables, so anyone who learns h can open the commitment to an arbitrary value of v by calculating the corresponding blinding factor as r = c - v*h.
2.2 Output keys

In Seraphis, the public spend key has the form of:
K_s = k_vb X + k_s U (2.2.1)
where k_vb is the private view key and k_s is the private spend key.
Public address keys have the form of:
K_addr = K_s + k_{addr_x} X + k_{addr_u} U (2.2.2)
where k_{addr_x} and k_{addr_u} are private key extensions derived from a secret key s_ga and the address index j:
k_{addr_x} = H_q(s_ga || T_{addr_x} || j) (2.2.3)
k_{addr_u} = H_q(s_ga || T_{addr_u} || j) (2.2.4)
One-time output keys have the form of:
K_o = K_addr + k_{sender_x} X + k_{sender_u} U (2.2.5)
where K_addr is the public key of the address the output was sent to and k_{sender_x} and k_{sender_u} are address extensions generated by the sender from the shared secret s_shared and the amount commitment C:
k_{sender_x} = H_q(T_{sender_x} || s_shared || C) (2.2.6)
k_{sender_u} = H_q(T_{sender_u} || s_shared || C) (2.2.7)
2.3 Key images

A Seraphis one-time output key has the form of:
K_o = k_x X + k_u U (2.3.1)
where
k_x = k_vb + k_{addr_x} + k_{sender_x} (2.3.2)
k_u = k_s + k_{addr_u} + k_{sender_u} (2.3.3)
The corresponding key image is:
K_i = (k_u / k_x) U (2.3.4)
We can rewrite Eq. 2.3.1 in terms of log_U as:
k_o = k_x*x + k_u (2.3.5)
where X = x U. An adversary who knows x can produce an arbitrary number of different valid key images for every K_o, allowing unlimited double spending.
3. Proposed constructions

3.1 Amount commitments

While Pedersen commitments do not bind a QA to the original amount, ElGamal commitments are a different form of homomorphic commitments that are pefectly binding.
3.1.1 ElGamal commitments

An ElGamal commitment to a value v with a blinding factor r consists of two group elements C, D calculated as:
C = r G + v H
D = r J
There are three problems with ElGamal commitments:

The range proofs are less efficient than for Pedersen commitments.
They do not hide the value v from a QA, who can learn r by calculating the discrete log of D.
They require twice the blockchain space of Pedersen commitments.

The first problem can be solved by treating an ElGamal commitment as if it was a Pedersen commitment, ignoring the value of D. This is the main idea behind "switch commitments" [3]. Keeping D allows past amounts to be validated in the future if the danger of quantum computers arises.
The second problem can be solved by defining a switch commitment as the pair (C, d), where d = H₃₂(D).
3.1.2 Zero-cost solution

Finally, an even more efficient solution was proposed in the Mimblewimble mailing list [4]. A switch commitment can be constructed by simply tweaking the blinding factor r. It works as follows:

Generate a random blinding factor r'.
Construct an ElGamal commitment with C' = r' G + v H and D' = r' J (3.1.2.1)
Calculate a new blinding factor r = r' + H_q(T_elgamal || C' || D').
Output a Pedersen commitment C = r G + v H.

This construction removes all the disadvantages of ElGamal commitments, while still allowing the post-quantum validation protocol (Ch. 4) to verify that the commitment is being open to the original value.
3.2 Wallet keys

To prevent a QA from directly learning wallet seeds by calculating a discrete logarithm, each wallet must be derived from a secret seed m that is never directly used as an elliptic curve private key.
3.2.1 Private view key

The private view key k_vb must be constructed independently of the spend key as:
k_vb = H_q(m || T_vb) (3.2.1.1)
The associated public view key is defined as:
K_vb = k_vb X (3.2.1.2)
This public key does not need to be published in the Seraphis protocol, but it is needed in the post-quantum protocol.
3.2.2 Auxiliary spend key

Instead of directly deriving the private spend key from m, we derive an auxiliary spend key as:
k_s' = H_q(m || T_{aux_spend}) (3.2.2.1)
The associated public auxiliary spend key is defined as:
K_s' = k_s' U (3.2.2.2)
3.2.3 Quantum-resistant key pair

Before the wallet can construct the Seraphis spend key, a quantum-resistant key pair (z_qr, Z_qr) is generated using the following seed m_qr:
m_qr = H₃₂(T_qr || m) (3.2.3)
Two possible quantum-resistant signature algorithms are listed in Chapter 5.
3.2.4 Auxiliary key image

The wallet can construct an auxiliary key image as:
K_i' = (k_s' / k_vb) U (3.2.4)
This key image has a similar format as the output key image (Eq. 2.3.4).
3.2.5 Key image proofs

To ensure that the auxiliary key image K_i' is correctly constructed according to Eq. (3.2.4), the wallet must construct two proofs:

σ_ki = (e₁, s₁) - a proof of knowledge of the discrete logarithm of K_i' with respect to the generator U.
π_ki = (e₂, s₂) - a discrete logarithm equality proof showing the knowledge of a private key k_vb such that k_vb X = K_vb and k_vb K_i' = K_s' (these relations hold from Eq. 3.2.1.2, 3.2.2.2 and  3.2.4).

The proofs σ_ki and π_ki are standard Fiat-Shamir proofs discribed in the literature [5].
3.2.5 Private spend key

The Seraphis private spend key is finally constructed as:
k_s = k_s' + k_Ω (3.2.5.1)
where k_Ω is defined as:
k_Ω = H_q(T_spend || Ω) (3.2.5.2)
and Ω is the following tuple:
Ω = (K_vb, K_s', Z_qr, K_i', σ_ki, π_ki) (3.2.5.3)
Since the hash function H_q() is irreversible even for a QA, the constuction proves that the tuple Ω had existed before the public spend key K_s was created.
3.3 Output keys

3.3.1 Address key extensions

Rather than using Eq. 2.2.3 and 2.2.4, address key extensions must be constructed as:
k_{addr_x} = H_q(T_{addr_x} || K_s || s_addr) (3.3.1.1)
k_{addr_u} = H_q(T_{addr_u} || K_s || k_{addr_x} || s_addr) (3.3.1.2)
where K_s is the wallet public spend key (Eq. 2.2.1) and
s_addr = H₃₂(s_ga || T_{addr_inner} || j) (3.3.1.3)
The irreversibility of H_q() proves that the spend key K_s had existed before the address extension k_{addr_x} and that k_{addr_x} was created before k_{addr_u}.
3.3.2 One-time address extensions

Rather than using Eq. 2.2.6 and 2.2.7, sender key extensions must be constructed as:
k_{sender_x} = H_q(T_{sender_x} || K_addr || s_sender) (3.3.2.1)
k_{sender_u} = H_q(T_{sender_u} || K_addr || k_{sender_x} || s_sender) (3.3.2.2)
where K_addr is the address public key and
s_sender = H₃₂(T_{sender_inner} || s_shared || C) (3.3.2.3)
The irreversibility of H_q() proves that the address key K_addr had existed before the sender extension k_{sender_x} and that k_{sender_x} was created before k_{sender_u}.
3.4 Key images

The Seraphis key image (Eq. 2.3.4) can be equivalently expressed as:
K_i = K_xs + (k_Ω + k_{addr_u} + k_{sender_u}) K_xu (3.4.1)
where the public keys K_xs and K_xu meet the following three discrete logarithm relationships:
k_x K_xs = K_s' (3.4.2)
k_x K_xu = U (3.4.3)
k_x K_i' = K_si (3.4.4)
The public key K_si is defined as:
K_si = K_s' + k_{addr_x} K_i' + k_{sender_x} K_i' (3.4.5)
Substituting for K_i', K_s' and K_si into Eq. 3.4.4 yields:
(k_x * k_s' / k_vb) U = k_s' U + (k_{addr_x} * k_s' / k_vb) U + (k_{sender_x} * k_s' / k_vb) U
k_x * k_s' / k_vb = k_s' + k_{addr_x} * k_s' / k_vb + k_{sender_x} * k_s' / k_vb
k_x * k_s' = k_vb * k_s' + k_{addr_x} * k_s' + k_{sender_x} * k_s'
k_x = k_vb + k_{addr_x} + k_{sender_x}
which matches the definition of k_x (Eq. 2.3.2).
Rearranging Eq. 3.4.2 and 3.4.3 yields:
K_xs = (k_s' / k_x) U (3.4.6)
K_xu = (1 / k_x) U (3.4.7)
Substituting for K_xs and K_xu into Eq. 3.4.1 shows that it's equivalent to Eq. 2.3.4.
4. Post-quantum validation protocol

This proposal does not modify any Seraphis consensus rules, but offers a secondary quantum-resistant protocol that can be activated by a hard fork.
4.1 Input validation

Spending a Seraphis e-note (K_o, C) in the post-quantum protocol requires the transaction to reveal the following:

The hidden ElGamal commitment (C', D') (Eq. 3.1.2.1)
A range proof for the commitment.
The tuple Ω (Eq. 3.2.5.2)
The secret key s_addr (Eq. 3.3.1.3)
The secret key s_sender (Eq. 3.3.2.3)
The public key K_xs (Eq. 3.4.6)
The public key K_xu (Eq. 3.4.7)
The discrete logarithm equality proof π_x = (e₃, s₃) for the pairs (K_xs, K_s'), (K_xu, U) and (K_i', K_si) (Eq. 3.4.2-3.4.4)
A quantum-resistant signature with the private key z_qr (Ch. 3.2.3). This signature should sign all transaction outputs.

To validate the spend, consensus needs to perform the following steps:

Validate C ?= C' + H_q(T_elgamal || C' || D') G
Validate the range proof
Validate the proofs σ_ki and π_ki from Ω
Calculate k_Ω = H_q(T_spend || Ω)
Calculate K_s = K_vb + K_s' + k_Ω U
Calculate k_{addr_x} = H_q(T_{addr_x} || K_s || s_addr)
Calculate k_{addr_u} = H_q(T_{addr_u} || K_s || k_{addr_x} || s_addr)
Calculate K_addr = K_s + k_{addr_x} X + k_{addr_u} U
Calculate k_{sender_x} = H_q(T_{sender_x} || K_addr || s_sender)
Calculate k_{sender_u} = H_q(T_{sender_u} || K_addr || k_{sender_x} || s_sender)
Validate K_o ?= K_addr + k_sender X + k_{sender_u} U
Validate the proof π_x
Calculate the key image K_i = K_xs + (k_Ω + k_{addr_u} + k_{sender_u}) K_xu
Validate that K_i is not spent.
Validate the quantum-resistant signature with Z_qr.

4.2 Output validation

All transaction outputs must contain ElGamal commitments with valid range proofs. The component-wise sum of the output commitments must be equal to the component-wise sum of the input commitments.
This protocol does not put any other restrictions on the output format, so it can be used to migrate Seraphis outputs to a new quantum-secure privacy protocol.
4.3 Privacy caveats

The quantum-resistant protocol makes the input e-notes provably spent, which may reduce the privacy of past transactions that used the e-notes as decoys.
All migrated outputs that belong to the same wallet share the same tuple Ω, which links them together.
5. Post-quantum signature algorithms

In July 2022, NIST has announced 3 post-quantum digital signature algorithms that have been selected for standardization [6]:

CRYSTALS-Dilithium
Falcon
SPHINCS+

These algorithms have survived at least 6 years of cryptanalysis and offer acceptable size and performance to be practically usable. Falcon is patented [7], so that leaves just two possible candidates to be used by Monero.
5.1 CRYSTALS-Dilithium

CRYSTALS-Dilithium is lattice-based signature scheme. It offers decently sized public keys and signatures and relatively fast key generation (with comparable performance to elliptic curves).


variant
security level
public key size
signature size
keygen (Intel Skylake)


Dilithium2
128-bit
1 312
2 420
~100 μs


Dilithium3
192-bit
1 952
3 293
~200 μs


The major disadvantage of lattice-based systems is that they rely on new hardness assumptions, which may be broken in the future.
5.1.1 Hardware wallets

The generation of a CRYSTALS-Dilithium public key requires approximately 10 KB of RAM and takes around 50 ms on ARM Cortex M4.
5.2 SPHINCS+

SPHINCS+ is hash-based digital signature scheme. It's the most conservative choice because it only relies on the preimage resistance of hash functions.
The disadvantages of SPHINCS+ are relatively large signatures and slow key generation.


variant
security level
public key size
signature size
keygen (Intel Haswell)


SPHINCS+-SHA-256-128s-simple
128-bit
32
7 856
~100 ms


SPHINCS+-SHA-256-128s-robust
128-bit
32
7 856
~200 ms


SPHINCS+-SHA-256-128f-simple
128-bit
32
17 088
~1.5 ms


SPHINCS+-SHA-256-128f-robust
128-bit
32
17 088
~3 ms


SPHINCS+-SHA-256-192s-simple
192-bit
48
16 224
~150 ms


SPHINCS+-SHA-256-192s-robust
192-bit
48
16 224
~300 ms


SPHINCS+-SHA-256-192f-simple
192-bit
48
35 664
~3 ms


SPHINCS+-SHA-256-192f-robust
192-bit
48
35 664
~6 ms


5.2.1 Hardware wallets

The generation of a SPHINCS+ public key requires approximately 2 KB of RAM and takes around 0.5 seconds on ARM Cortex M4 for the "f-simple" variants and around 10-20 seconds for the "s-simple" variants. The "robust" variants are twice slower.
6. Summary

Incorporating this protocol into Seraphis requires the following 4 wallet-side functions:

MakeCommit(r', v), returns (C, r) (Ch. 3.1.2)
MakeWallet(m), returns (k_vb, k_s) (Ch. 3.2)
MakeAddressExt(K_s, s_ga, j), returns (k_{addr_x}, k_{addr_u}) (Ch. 3.3.1)
MakeSenderExt(K_addr, s_shared, C), returns (k_{sender_x}, k_{sender_u}) (Ch. 3.3.2)

These functions enable a backwards-compatible post-quantum protocol to be activated eiher as an emergency hard-fork or as part of a post-quantum migration process.
While it's possible that the post-quantum protocol may not be needed in the foreseeable future, the "zero-cost" nature of this proposal makes it a very cheap mitigation for a possible disaster.
References

[1] https://github.com/insight-decentralized-consensus-lab/post-quantum-monero/blob/master/writeups/technical_note.pdf
[2] https://github.com/UkoeHB/Seraphis/blob/master/Seraphis-0-0-16.pdf
[3] https://eprint.iacr.org/2017/237.pdf
[4] https://lists.launchpad.net/mimblewimble/msg00479.html
[5] https://crypto.ethz.ch/publications/files/CamSta97b.pdf
[6] https://csrc.nist.gov/projects/post-quantum-cryptography/selected-algorithms-2022
[7] https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/selected-algos-2022/final-ip-statements/Falcon-Statements-final.pdf
variant	security level	public key size	signature size	keygen (Intel Skylake)
Dilithium2	128-bit	1 312	2 420	~100 μs
Dilithium3	192-bit	1 952	3 293	~200 μs
variant	security level	public key size	signature size	keygen (Intel Haswell)
SPHINCS+-SHA-256-128s-simple	128-bit	32	7 856	~100 ms
SPHINCS+-SHA-256-128s-robust	128-bit	32	7 856	~200 ms
SPHINCS+-SHA-256-128f-simple	128-bit	32	17 088	~1.5 ms
SPHINCS+-SHA-256-128f-robust	128-bit	32	17 088	~3 ms
SPHINCS+-SHA-256-192s-simple	192-bit	48	16 224	~150 ms
SPHINCS+-SHA-256-192s-robust	192-bit	48	16 224	~300 ms
SPHINCS+-SHA-256-192f-simple	192-bit	48	35 664	~3 ms
SPHINCS+-SHA-256-192f-robust	192-bit	48	35 664	~6 ms