Post-quantum encryption

[tevador]

The purpose of this issue is to discuss the post-quantum (PQ) encryption algorithm selection for Jamtis - the next addressing scheme for Monero.

Motivation

FCMP++ will be shipping with Carrot [1], which is a CryptoNote-compatible addressing scheme. Carrot already brings several forward-secrecy improvements, notably:

1. A quantum enabled adversary (QEA) is not able to construct a transaction graph just by observing the blockchain.
2. Several parts of the transaction protocol use symmetric-key derivations that are PQ secure. This includes address generation and internal enotes.

However, if a QEA learns just one wallet address, they can deanonymize a large portion of the wallet's transaction history, including:

1. All incoming external enotes with their amounts.
2. In some cases, the spends of such enotes (this requires at least 2 enotes received to the same wallet address to be spent).

The purpose of Jamtis is to provide forward secrecy against a QEA even if a wallet address is publicly known or under a stronger assumption that the address-generator wallet tier is leaked.

Achieving the above goal boils down to selecting a suitable PQ public key encryption scheme.

Post-quantum encryption

Key exchange types

When talking about PQ encryption algorithms in a blockchain setting, it is important to distinguish between non-interactive key exchange (NIKE) and a more general key encapsulation mechanism (KEM).

Non-interactive key exchange (NIKE)

With a non-interactive key exchange, Alice and Bob can establish a shared secret just by knowing each other's public keys. If Alice's public key is A = a * G and Bob's public key is B = b * G, then their shared secret is a * B = b * A. Here the symbol * refers to the application of some secret action on a public key and G is a common base key.

Notice that the action * must be commutative: (ab) * G = (ba) * G. The most common example is scalar multiplication in an elliptic curve group or in the multiplicative group of integers modulo a prime, which was the first public key algorithm published by Diffie and Hellman in 1976 [2].

The advantages of NIKE for Monero are two-fold:

1. NIKE allows multiple recipients to use the same public key to calculate a shared secret with the sender of the transaction. It means that a 16-output transaction still only needs one public key.
2. The fact that NIKE applies a secret action directly to a public key allows for rerandomizations of a public key. This means that the address-generator wallet tier can generate unlinkable addresses without the knowledge of the resulting decryption key.

Key encapsulation mechanism (KEM)

KEM is a generalized key exchange for algorithms that don't have the symmetry needed for NIKE. Most PQ key exchange algorithms belong to this category.

With a KEM, Alice takes Bob's public key B and mixes it with some randomness a, which produces a shared key and a ciphertext. Bob can then decrypt the ciphertext with his private key b to get the shared key. Notice that Alice has no defined public key in this process.

If Alice wants to communicate with Bob and Charlie, she needs to produce two different ciphertexts, one using Bob's public key B and one using Charlie's public key C.

This has two implications for Monero:

1. A multi-output transaction needs to contain one ciphertext per recipient.
2. There is no way to rerandomize a public key, which means the address-generator tier can always decrypt transactions.

Hardness assumptions and protocols

The discrete logarithm problem (DLP) is not considered to be hard to solve for a QEA.

The following 3 problems are assumed to be hard and have been used to construct PQ key exchange protocols:

Error correcting codes

Decoding a randomly chosen linear error correcting code is assumed to be computationally hard. One of the first public key cryptosystems, published in 1978 by R.J. McEliece [3], is based on this assumption. This cryptosystem has withstood almost 50 years of cryptanalysis and is considered to be one of the most secure choices for PQ encryption.

A modern version of the McEliece cryptosystem was submitted to the NIST Post-Quantum Cryptography Standardization (PQCS) [4], where it advanced to the 4th round, but was not selected for ratification.

Besides high security, classic McEliece also has a very small ciphertext size, which is convenient for blockchain transaction sizes. Unfortunately, its usability is limited by the large public key size.

Lattices

Finding a short vector in a multidimensional lattice is assumed to be computationally hard. A large number of PQ cryptosystems are based on this assumption. This includes CRYSTALS-Kyber [5], which was standardized by NIST in 2022. Other notable cryptosystems are NTRU [6] and NTRU Prime [7], which also participated in the NIST PQCS and both advanced to the 3rd round.

Lattice-based cryptosystems have public keys and ciphertext sizes of around 1 KB and offer high security and high speed. However, some of the proposed cryptosystems might be covered by patents (for example US9094189B2 and US9246675B2).

Isogenies

Finding an isogeny between two elliptic curves is assumed to be hard. A prominent cryptosystem based on this assumption was SIKE [8], which advanced to the 4th round of the NIST PQCS, but was completely broken by a classical attack in 2022 [9]. The attack on SIKE doesn't imply that the isogeny hardness assumption is wrong becaue SIKE implicitly used a much stronger assumption.

CSIDH (pronounced "sea-side") is another cryptosystem based on isogenies. It was published in 2018 [10], so it didn't participate in the NIST PQCS. CSIDH uses a commutative action, so it's a rare example of a PQ NIKE. All known classical attacks on CSIDH have exponential complexity, but a subexponential quantum attack is known [11], which somewhat reduces the security of CSIDH compared to the previously mentioned cryptosystems.

Comparison of algorithms

Table 1 lists a selection of PQ key exchange algorithms, resulting Jamtis address sizes and approximate pruned transaction sizes.

I selected the smallest proposed parameter sizes for classic McEliece [4] and NTRU [6] and the two smallest parameter sizes for CSIDH [10]. Curve25519 is listed for comparison.

Algorithm	Type	Address size	2/2 tx size	2/16 tx size
Curve25519	NIKE	244	278	2021
McEliece-3488	KEM	418000	374	3557
NTRU-509	KEM	1363	977	13205
CSIDH-512	NIKE	346	342	2085
CSIDH-1024	NIKE	449	406	2149

Table 1: Address sizes and pruned transaction sizes of various PQ key exchange algorithms in comparison with Curve25519.

Pruned transaction sizes include a 32-byte key image per input and a 32-byte output key, 32-byte commitment, 32-byte ephemeral key, a 3-byte view tag, a 8-byte encrypted amount, a 16-byte encrypted Janus anchor and the required PQ key material for each recipient.

Classic McEliece has acceptable blockchain cost, but results in unusably large addresses. It's therefore disqualified.

NTRU (and other lattice-based cryptosystems) would require addresses longer than 1300 characters and would significantly increase the pruned sizes of all transactions (up to 6x for 16 outputs). If there were no alternatives, I think these costs might be acceptable, but it would have a negative impact on the uptake of Jamtis and willingness of users to run Monero nodes.

However, CSIDH offers significiantly better results than lattice based cryptosystems, so it's the clear winner here.

CSIDH

This section examines CSIDH in more details and focuses on its security and performance.

Brief description

In CSIDH, Alice's private key is a secret isogeny a and Bob's private key is another secret isogeny b. The base curve is E0: y2 = x3 + x. Elliptic curves are defined over the prime field Fp. The size of p determines the security level.

Alice's public key is a curve EA: y2 = x3 + Ax2 + x such that EA = a * E0, where * is the application of the secret isogeny. Similarly for Bob, EB = b * E0. Public keys are uniquely encoded with the coefficient of the x² term of the curve equation.

Alice's and Bob's shared secret is simply EAB = a * EB = b * EA thanks to the commutativity of the isogeny action. CSIDH is nearly a drop-in replacement for the classical Diffie-Hellman key exchange.

Classical security and performance

The best classical attack on CSIDH-p has a complexity of O(p1/4). The smallest instance that reaches 128 bits of classical security is CSIDH-512.

Table 2 also lists the performance of CSIDH compared to Curve25519 in Intel Skylake cycles. The CSIDH-512 isogeny action takes approximately 1000 times longer than a Curve25519 scalar multiplication. The slowness of CSIDH is not a big problem for Jamtis. The PQ shared secret will be calculated only for enotes with a matching 24-bit view tag. However, it might have an impact on users who receive lots of payments to Jamtis addresses.

CSIDH public keys need to be validated to avoid attacks. Table 1 lists the validation time in Skylake cycles. The key validation could be a consensus rule, in which case it would add roughly 1.3 ms (13 ms) to transaction verification times for CSIDH-512 (CSIDH-1024), assuming a 3 GHz CPU.

Cryptosystem	Algorithm	Attack complexity	Compute action [cy]	Validate pub. key [cy]	Impl. ref.
Curve25519	Pollard's rho	2126	100 000	0	[12]
CSIDH-512	Meet-in-the-middle	2128	125 000 000	4 000 000	[13]
CSIDH-1024	Meet-in-the-middle	2256	470 000 000	41 000 000	[13]

Table 2: Classical security and performance of CSIDH in comparison with Curve25519.

Post-quantum security

The post-quantum security of CSIDH is more complicated. The attack with the lowest asymptotic complexity is based on Kuperberg's collimation sieve and has a time complexity of 2O(√log(N)), where N is the size of the CSIDH group. In comparison, Shor's algorithm has an asymptotic complexity of log(N)3.

Table 3 lists the quantum computer resources needed to break a key.

Cryptosystem	Algorithm	Logical qubits	QROM bits	T-gates	Attack time	Ref.
Curve25519	Shor's	3000	226	227	8.3 seconds	[14]
CSIDH-512	Kuperberg's	1000000	240	261	4500 years	[11, 15]
CSIDH-1024	Kuperberg's	>1000000	244	273	2×107 years	[11, 15]

Table 3: Post-quantum security of CSIDH in comparison with Curve25519.

Logical qubits

This is the number of logical qubits needed to run the algorithm. Note that the quantum oracle proposed in ref. [15] requires 2⁴⁰ qubits, but there is an optimization that can reduce the number of qubits to 2²⁰ at the cost of of increasing the number of gates by a factor of 4. I'm assuming the optimization is used.

QROM

QROM (sometimes called QRAM or QRACM) is a special type of memory that stores read-only classical data ("ones and zeroes") that can be accessed by a quantum computer.

The exact technology how to make QROM is unclear (it can't use transistors like classical RAM), but it is assumed that QROM will be cheaper than quantum memory. Note that this is not a generally accepted assumption. For example, ref. [16] argues that highly scalable QROM is unlikely to ever exist.

Kuperbergs'a algorithm requires a high amount of QROM, so it would become impractical if QROM can't be made to scale. Shor's algorithm can work without QROM (it's only used to store a precomputed table of points to speed up the algorithm).

Attack time

The number of T-gates measures the running time of the algorithm. For Shor's algorithm, ref. [14] assumes a highly scalable quantum computer using superconducting qubits with a cycle time of 1 μs. When parallelized, these devices can break one Curve25519 key per 8.3 seconds. A quantum computer based on trapped ions would be about 1000 times slower.

I've extrapolated the attack times from ref. [14] to the number of T-gates for CSIDH. Note that this ignores the much higher memory requirements of the the CSIDH algorithm. Even under these optimistic asumptions, the time to break CSIDH-512 is in thousands of years and the time to break CSIDH-1024 is in millions of years.

CSURF

There is a variant of CSIDH called CSURF, which was published in 2019 [17]. CSURF requires p = 7 mod 8 (CSIDH has p = 3 mod 8) and uses elliptic curves in the form of y2 = x3 + Ax2 - x. It can use 2-isogenies to slightly speed up the calculation of the group action (the claimed speed-up is around 5%). Otherwise it's very similar to CSIDH.

A 2023 paper analyzed the recovery of CSIDH/CSURF private keys if some bits are known [18]. Their main result is that a CSIDH private key can be quickly recovered if ~54% of the high bits are known. For CSURF, this raises to ~76% (improved to 74% in a later paper [19]). This means that CSURF has better resistance to side channel attacks (which might leak some private key bits) but also to quantum attacks. For example, the Kuperberg's sieve calculations from ref. [11] assume that all but the lowest 56 bits of the secret key need to be recovered by the quantum computer. Ref. [18] shows that only 139 bits of the 256-bit CSIDH-512 private key need to be recovered quantumly (the rest can be recovered classically in polynomial time).

Further research shows that CSURF is not actually faster than CSIDH, despite the claims from ref. [17]. The problem is that elliptic curves y2 = x3 + Ax2 - x have slower projective formulas than standard Montgomery curves. Specifically, the cost per ladder step is 11M + 5S vs 8M + 4S [20]. This makes CSURF practically slower than CSIDH because high performance implementations use projective formulas.

However, primes p = 7 mod 8 can still be used with standard Montgomery curves. This is briefly mentioned in ref. [17, Remark 3] and further researched in ref. [21]. This approach requires selecting one of the two orbits and validating that public keys are in the correct orbit. While this adds some small overhead (2 Legendre symbol calculations), it mitigates a general key control vulnerability in CSIDH [22].

PEGASIS

A new method of calculating the group action called PEGASIS was published in 2025 [23]. PEGASIS calculates the whole group action using one 2^e-isogeny so it can be considered as an extension of CSURF. A major advantage of PEGASIS is that it can use special-form primes such as p = 15 * 21004 - 1, which have a much faster field arithmetic than the general-form primes used by CSIDH and CSURF. A later published variant qt-Pegasis [24] brought some incremental efficiency improvements. No optimized imlpementation currently exists (the papers only give python/sage implementations), so real-world performance is uncertain, but it's probably faster than both CSIDH and CSURF. Note that the last PEGASIS paper is less than 1 month old, so this is cutting-edge research.

Summary

I'm proposing to use CSIDH/CSURF for PQ encryption with Jamtis addresses. I think the best choice is CSIDH-1024 for a more conservative security margin.

Algorithm	Address	2/2 tx	2/16 tx	Decrypt enote	Validate pubkey	log(T)	Years to break
CSIDH-512	346	342	2085	~83 ms	~1.3 ms	61	4500
CSIDH-768	397	374	2117	~180 ms	~5 ms	67	300 000
CSIDH-896	422	390	2133	~240 ms	~8 ms	70	2 000 000
CSIDH-1024	448	406	2149	~310 ms	~13 ms	73	18 000 000

Table 4: Summary of CSIDH parameters. Performance of CSIDH-512 and CSIDH-1024 is from ref. [13], the numbers for CSIDH-768 and CSIDH-896 are extrapolated.

References

[1] "Carrot" https://github.com/jeffro256/carrot/blob/master/carrot.md

[2] "New directions in cryptography", W. Diffie; M. Hellman (1976) https://ieeexplore.ieee.org/document/1055638

[3] "A public-key cryptosystem based on algebraic coding theory.", R.J. McEliece (1978) https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF

[4] "Classic McEliece:
conservative code-based cryptography", Albrecht et al. (2022), https://classic.mceliece.org/nist/mceliece-submission-20221023.pdf

[5] "CRYSTALS-Kyber", Avanzi et al. (2021), https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

[6] "NTRU", Chen et al. (2020), https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/NTRU-Round3.zip

[7] "NTRU Prime", Bernstein et al. (2020) https://ntruprime.cr.yp.to/nist/ntruprime-20201007.

[8] "Supersingular Isogeny Key Encapsulation", Jao et al. (2022), https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/submissions/SIKE-spec.pdf

[9] "An efficient key recovery attack on SIDH", W. Castryck, T. Decru (2022) , https://eprint.iacr.org/2022/975

[10] "CSIDH: An Efficient Post-Quantum Commutative Group Action", Castryck et al. (2018), https://eprint.iacr.org/2018/383

[11] "He Gives C-Sieves on the CSIDH", C. Peikert (2019), https://eprint.iacr.org/2019/725

[12] "Security and Efficiency Trade-offs for Elliptic Curve Diffie-Hellman at the 128-bit and 224-bit Security Levels", K. Nath, P. Sarkar (2019), https://eprint.iacr.org/2019/1259

[13] "CTIDH: faster constant-time CSIDH", Banegas et al. (2021), https://eprint.iacr.org/2021/633

[14] "How to compute a 256-bit elliptic curve private key
with only 50 million Toffoli gates", D. Litinski (2023), https://arxiv.org/abs/2306.08585

[15] "Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies", Bernstein et al. (2018), https://eprint.iacr.org/2018/1059

[16] "QRAM: A Survey and Critique", S. Jaques, A. G. Rattew (2023), https://arxiv.org/abs/2305.10310

[17] "CSIDH on the surface", W. Castryck and T. Decru (2019), https://eprint.iacr.org/2019/1404

[18] "Solving the Hidden Number Problem for CSIDH and CSURF via Automated Coppersmith", J. Meers, J. Nowakowski (2023), https://eprint.iacr.org/2023/1409

[19] "Computing Asymptotic Bounds for Small Roots in Coppersmith's Method via Sumset Theory", Feng et al. (2024), https://eprint.iacr.org/2024/1330

[20] "On the Performance Analysis for CSIDH-Based Cryptosystems", Heo et al. (2020), https://www.mdpi.com/2076-3417/10/19/6927

[21] "Optimized CSIDH Implementation Using a 2-torsion Point", Heo et al. (2020), https://eprint.iacr.org/2020/391

[22] "A note on key control in CSIDH", A. Sanso (2022), https://eprint.iacr.org/2022/847

[23] "PEGASIS: Practical Effective Class Group Action using 4-Dimensional Isogenies", Dartois et al. (2025), https://eprint.iacr.org/2025/401

[24] "qt-Pegasis: Simpler and Faster Effective Class Group Actions", Dartois et al. (2025), https://eprint.iacr.org/2025/1859

[kayabaNerve]

Clarifying, do you plan to propose CSIDH alone or a hybrid?

Personally, I don't believe parameters smaller than 768 are reasonable due to the evolution of attacks seen overtime.

The bandwidth looks great though!

[tevador]

Yes, Jamtis uses hybrid encryption. It has 3 shared secrets with Curve25519 and 1 shared secret with CSIDH. Full specs will follow once the PQ algorithm is selected. I'm also tentatively in favor of CSIDH-1024 for conservative security, but we need to make sure that the address size and performance is acceptable.

[tevador]

Also note that while CSIDH-768 is possible, no such implementation exists. We have constant-time implementations for CSIDH-512 and CSIDH-1024 only.

[tevador]

I added CSIDH-768 and CSIDH-896 as options to Table 4. The performance numbers are extrapolated from the asymptotic complexities of the respective operations.

[tevador]

Futher CSIDH-related research:

CSURF

There is a variant of CSIDH called CSURF, which was published in 2019 [17]. CSURF requires p = 7 mod 8 (CSIDH has p = 3 mod 8) and uses elliptic curves in the form of y2 = x3 + Ax2 - x. It can use 2-isogenies to slightly speed up the calculation of the group action (the speed-up is around 5%). Otherwise it's very similar to CSIDH.

A 2023 paper analyzed the recovery of CSIDH/CSURF private keys if some bits are known [18]. Their main result is that a CSIDH private key can be quickly recovered if ~54% of the high bits are known. For CSURF, this raises to ~76% (improved to 74% in a later paper [19]). This means that CSURF has better resistance to side channel attacks (which might leak some private key bits) but also to quantum attacks. For example, the Kuperberg's sieve calculations from ref. [11] assume that all but the lowest 56 bits of the secret key need to be recovered by the quantum computer. Ref. 18 shows that only 139 bits of the 256-bit CSIDH-512 private key need to be recovered quantumly (the rest can be recovered classically in polynomial time).

The conclusion is that CSURF might be not only a faster but also a more secure variant of CSIDH.

PEGASIS

A new method of calculating the group action called PEGASIS was published in 2025 [20]. PEGASIS calculates the whole group action using one 2^e-isogeny so it can be considered as an extension of CSURF. A major advantage of PEGASIS is that it can use special-form primes such as p = 15 * 21004 - 1, which have a much faster field arithmetic than the general-form primes used by CSIDH and CSURF. A later published variant qt-Pegasis [21] brought some incremental efficiency improvements. No optimized imlpementation currently exists (the papers only give python/sage implementations), so real-world performance is uncertain, but it's probably faster than both CSIDH and CSURF. Note that the last PEGASIS paper is less than 1 month old, so this is cutting-edge research.

---

Apart from the size of the prime p, we have 3 options for Jamtis:

CSIDH

Pros:

• a high-performance constant-time implementation exists (for 512 and 1024)
• detailed post-quantum security estimates have been done

Cons:

• slower than CSURF
• probably less secure than CSURF

CSURF

Pros:

• slightly faster than CSIDH
• probably more secure than CSIDH

Cons:

• there is no high-performance constant-time implementation
• quantum oracle analysis has not been done (but is likely very similar to CSIDH)

PEGASIS

Pros:

• probably the fastest variant

Cons:

• there is no high-performance constant-time implementation
• quantum oracle analysis has not been done
• uncertain security