Securing Sui in the Quantum Computing Era

The advent of quantum computing creates a critical risk to cryptographically-secured systems. Blockchains, which rely on cryptography for identity management, transaction security, and data integrity, face a particular risk from quantum computing's ability to break traditional encryption models. 

Sui, however, was built to ensure cryptographic agility, making it adaptable to quantum-resistant cryptography. In addition, developers can implement practical transition strategies today ensuring that Sui remains secure, trustworthy, and resilient in the quantum era.

Quantum computing risks

Quantum computing poses a profound threat to traditional cryptographic methods—such as RSA encryption and elliptic curve cryptography (ECC)—by leveraging powerful quantum algorithms like Shor's algorithm, which can break these systems efficiently.  For blockchain ecosystems like Sui, addressing this threat is an important and carefully orchestrated multi-year journey.

Recent breakthroughs, notably Google's Willow quantum computer operating on 105 qubits, signal accelerated progress towards quantum machines powerful enough to compromise classical cryptography. The U.S. National Institute of Standards and Technology (NIST) has mandated the transition to quantum-resistant cryptographic standards by 2035, deprecating classical algorithms by 2030. Blockchain platforms, including Sui, must proactively prepare to adopt quantum-resistant technologies.

This transition is especially urgent for encryption due to "store now, decrypt later" attacks, wherein adversaries collect encrypted data today to decrypt later once quantum computers mature. Immediate action is needed to ensure sensitive blockchain data remains secure over the long term.

Background on post-quantum cryptography

Quantum computing

Classical computers operate on bits using boolean gates. Quantum computers operate on quantum bits (qubits) using a combination of special quantum gates and boolean equivalent gates. Quantum gates give a way to create a superposition of an exponential number of states, which can be operated on parallelly. However, to convert the computation to classical results, we have to perform a “measurement” which can only sample quantum states. Quantum computing is a clever way to exploit these processes to compute non-trivial problems.

State of classical cryptography

There are two dominant patterns of quantum algorithms pioneered by Simon’s/Shor’s algorithms and Grover’s algorithm:

• Period finding: Finding the periodicity of a function. This is especially useful in computing the discrete log of a group-based function. This is because the exponentiation of a group is a periodic function. Cryptographically relevant forms of this functionality can break RSA and elliptic curve-based cryptography.
• Search: Finding the preimage of a function at a particular point. Cryptographically relevant form of this algorithm is inverting hash functions, and breaking symmetric encryptions.

However, while the period finding algorithm provides an exponential speedup, the search algorithm just provides a quadratic speedup. While we have to completely abandon RSA and elliptic curve cryptography, it is thought to be sufficient to just double the security parameter for hash functions and symmetric key encryptions, going from 128 bit security to 256 bit security, for example.

In general, public key encryption and signatures have to transition to completely different algorithms, in comparison to existing ones like RSA and ECDSA. NIST has recommended the following two algorithms based on lattices, among a few more:

• ML-DSA, or Crystals Dilithium for signatures
• ML-KEM, or Crystals Kyber for public-key encryption

Recent developments, like Google Willow, have caused consternation on the impact of immediate quantum improvements on breaking cryptography. However, while Willow operates on 105 qubits, breaking cryptography requires millions of qubits.

The concrete timeline to follow is the NIST post-quantum timeline, which deprecates many of the classical algorithms by 2030 and completely phases them out in 2035.

Cryptography in Sui

The main classical cryptographic primitives used today in Sui and many other chains are:

• ECDSA, EdDSA for signatures
• Hashes for object IDs, accounts, transaction digests, etc
• RSA signatures by zkLogin (as most OpenID providers use that for signing JSON web tokens)
• BLS12-381 curves for the the randomness beacon and signatures
• Public key encryption or key exchange as part of TLS

Signatures

The transition to post-quantum cryptography for Sui requires a careful balance between security, efficiency, and practical deployment considerations. NIST recommends several signature schemes as part of its post-quantum standardization process, including CRYSTALS-Dilithium, FALCON, and SPHINCS+. These schemes are designed to withstand attacks from quantum computers, which threaten the security of existing ECC-based schemes like Ed25519, currently used in Sui.

NIST Recommendations and Security Assumptions: NIST selected three primary signature schemes with different trade-offs:

• CRYSTALS-Dilithium: Based on the hardness of the Module-LWE lattice problems, offering strong security and efficient verification but with relatively large signature sizes.
• FALCON: Also lattice-based, using NTRU assumptions, providing compact signatures and faster verification but also requiring significant floating-point arithmetic for fast Fourier Gaussian sampling.
• SPHINCS+: A stateless hash-based scheme relying only on the security of cryptographic hash functions, but with significantly larger signature sizes and slower signing/verification times.

Parameters for these schemes at different security levels:

For blockchains like Sui, which prioritize high throughput and low-latency signature verification, lattice-based schemes like Dilithium or FALCON are more practical than SPHINCS+.

Batch Verification of Signatures: A crucial optimization in Sui is where multiple signatures from different keys are verified together to improve efficiency. While ECC-based signatures support efficient batch verifications, currently we have a lack of batching optimizations to the same extent for the PQ signatures under consideration:

• Dilithium supports a superficial form of batch verification speedup for single key multiple messages, which leverages optimizations going from matrix-vector multiplications to matrix-matrix multiplications. Speedups are typically 20 to 50 percent over independent verifications.
• FALCON has challenges with batch verification due its structured form of randomness.
• SPHINCS+ does not readily support batch verification due its lack of algebraic structure.

Transition Strategies: There are a few strategies to smoothly transition from a pre-quantum (PreQ) signature scheme to a post-quantum (PQ) signature scheme, including:

Proactive strategies at the time of account creation:

1. At the time of generating an address, PQ signs a PreQ public key. Transition from using the PreQ key to the PQ key
2. Use a PreQ-PQ 1-out-of-2 multisig with an expiration time on the PreQ public key. The multisig address must be a PQ-hash of the 2 public keys.

Adaptive strategies for already existing addresses:

1. Standard ownership transition from a PreQ address to a PQ address.
2. At transition, construct a PQ key pair from the same seed randomness used for a PreQ signature. Post a PQ ZK proof that the underlying seed randomness is the same.

Hash functions

NIST’s PQ standardization process focuses primarily on public-key cryptography, but hash functions also need consideration due to Grover’s algorithm, which reduces their effective security level by roughly half for preimage resistance and roughly one-third for collision resistance (by the related BHT algorithm). The recommended approach for PQ security is to use hash functions with at least 256-bit output to ensure an effective 128-bit preimage resistance against quantum adversaries, and 384-bit output to ensure a 128-bit collision resistance against quantum adversaries.

Properties of a hash function: We are interested in two standard security properties of a hash function:

Second Preimage Resistance: Given an input x and hash output y=H(x), it should be infeasible to find any x' (\neq x), such that y =H(x’) . Same as in preimage resistance, it takes 2^{n-1} hash function queries on the average to break second preimage resistance. With a quantum computer, Grover’s algorithm takes O(2^n/2) queries to find a collision. Thus an output of 256 bits is required for 128-bit security. Security of authenticating addresses needs second preimage resistance, so that an adversary cannot come up with a different verification key for authentication.

Collision Resistance: It should be infeasible to find two inputs x \neq x', such that H(x) = H(x’). Generic birthday attacks take O(2^{n/2}) hash function queries to find a collision, thus effectively halving the security level, compared to preimage and second preimage resistance. The BHT algorithm, which builds on Grover’s algorithm takes O(2^{n/3}) time. Collision resistance is required to prevent forks. Sui digests are 256 bits, so need to be 384 bits to provide 128-bit security.

The theoretical security levels are however upper bounds that can be lowered in actuality by exploiting the specific structure of the hash functions.

Transition Strategies: In Sui, hash functions are only used as compression mechanisms to commit to public data, where storage optimization is a goal rather than privacy. Examples include transaction digests and checkpoint digests. Even address generation involves compressing public keys and other inputs into a fixed length string. In these instances the transition can be pretty straightforward, as it can be checked that the public preimages of the PreQ hash and the PQ hash are the same.

Public key encryption and key exchange

There are several important use cases of encryption in a modern blockchain, although not as centrally important as signature schemes. These include keeping transaction amounts and addresses private, and preventing MEV attacks by encrypting transactions.

Symmetric Key Encryption: As standard encryption algorithms, like AES, are based on non-algebraic structures, they are likely only subject to less devastating quantum attacks, such as the use of Grover’s algorithm. The standard mitigation is to double the key length for a target security level.

Public Key Encryption: Public key encryption schemes, like ElGamal and RSA, depend on group algebra, and as such are broken in quantum polynomial time by Shor’s algorithm. Lattice-based schemes, which depend on noisy algebraic operations, have been proposed to address quantum attack. The security of these schemes depend on the conjectured quantum-hardness of finding short vectors or close vectors in high-dimensional lattices.

NIST has standardized the CRYSTALS DILITHIUM construction for usage as a public key encapsulation mechanism. Also known as ML-KEM, Dilithium uses module lattices in its operations. The underlying hardness assumption is Module-LWE, whose hardness is intermediate between plain LWE (which uses unstructured lattices) and Ring-LWE (which uses lattices induced by polynomial rings). While Ring-LWE offers the best public key and ciphertext sizes, it is also subject to attacks that exploit the ring structure, such as subspace attacks. Module-LWE instead uses modules over ring elements so has less structure than pure ring elements. The parameters of ML-KEM for various security levels are given below:

Farming attacks: Even while quantum computers are not practical today, an attacker may just store PreQ ciphertexts today in anticipation of having access to powerful quantum computers in the future and thereby decrypt the ciphertext. This may be an unacceptable scenario for highly confidential data, meant to be kept secret for decades. It is not enough to just re-encrypt publicly stored PreQ ciphertexts with a PQ encryption key, as an adversary can already have copied the ciphertext. This is in contrast to signature schemes, where layering signatures can fortify against quantum forgeability in the future.

Transition strategies:

1. Ciphertexts requiring transitory privacy can continue for some time with PreQ encryption. Examples include encrypted transactions for MEV mitigation and encrypted NFTs which are planned to be opened after a short timeline.
2. Ciphertexts with low-value data or data whose value would become negligible after a short time period can also continue longer with PreQ encryption. Examples include encrypted news content and entertainment media.
3. Ciphertexts with high-value highly confidential data, especially those requiring privacy beyond 2030, should be PQ encrypted as soon as possible. It is not a secure strategy to post PreQ ciphertexts and switch them to PQ ciphertexts in the future due to farming attacks.

PQ-TLS: The TLS protocol, the ubiquitous protocol underlying establishment of secure channels between web endpoints today, uses both signature and encryption schemes. As such, it is also subject to quantum attacks as described above. OpenSSL 3 has a flexible architecture that allows for the integration of post-quantum algorithms, as developed by Open Quantum Safe provider. The oqs-provider library implements many PQ algorithms, including ML-DSA, ML-KEM, Falcon, and SPHINCS. Amazon has a custom implementation of PQ-TLS for its KMS – while it awaits standardization, this supports endpoints that both run the same software.

ZK proof systems

Modern ZK systems can be broadly divided into two categories:

Linear PCPs: Proof systems such as Pinocchio and Groth16 can be conceptually decomposed into a linear interactive proof (LIP) and a cryptographic linear only encryption. While the LIP part is information theoretic, and thus immune to quantum attacks, the linear only encryption is realized by cryptographic bilinear maps based on pairing-friendly elliptic curves, making the system subject to quantum discrete log attacks.

1. Advantages: short proofs, fast verification time
2. Disadvantages: circuit-specific CRS that scales superlinearly with the circuit size, need for circuit-specific ceremony to avoid trusting a single CRS generator
3. Quantum transition: Constructions such as ACL+22 and JPR23 instantiate the linear-only encryption using lattice-based primitives, thus addressing quantum attacks. However, the state of research is nascent in this area.

IOPs: Proof systems such as PLONK and STARK can be conceptually decomposed into an interactive protocol which exchanges polynomials, a cryptographic polynomial commitment scheme to compress the polynomials, and a cryptographic hash function which folds the interaction by the application of Fiat-Shamir heuristic. While the hash function can be made quantum-resistant by doubling key length, the polynomial commitments need more care.

1. Advantages: transparent or circuit-independent CRS, depending on the polynomial commitment scheme.
2. Disadvantages: longer proof size, slower verification time
3. Quantum transition: group-based polynomial commitment schemes, such as [KZG10] are subject to quantum discrete-log attacks. Hash-function based polynomial commitment schemes, such as FRI and its variants, are plausibly post-quantum.

The holy grail for (zk)SNARKs is:

1. Circuit-independent setup to avoid expensive ceremonies
2. Fast O(\lambda) verification, O(|C|\ log (|C|)\ poly(\lambda)) proving, O(\lambda) proof size
3. Quantum-attack resistant

We do not currently have any construction that achieves all three of the above.

Production systems: Modern production ZK systems, such as Polygon’s Plonky3, StarkWare’s STARKs (and related Winterfell co-developed by Mysten Labs cryptographers), Succinct SP1, and Nexus zkVM, offer different trade-offs in efficiency, scalability, and security.

From a security standpoint, StarkWare and Plonky3 solely rely on hash functions, making them smoothly adaptable to PQ security. SP1 also uses PQ-safe primitives, except for an optional final recursion into compact Groth16 proofs, which remains PQ insecure. Nexus zkVM had legacy reliance on elliptic curve cryptography, due to usage of accumulation-based schemes like Nova/Hypernova, but has recently switched to Circle STARKs.

zkLogin: Sui’s zkLogin uses Groth16 proofs over OIDC JSON web tokens (JWT), which are in turn secured by RSA signatures. Both Groth16 proofs and RSA signatures are subject to quantum attacks. The security properties of zkLogin break when either of them is compromised.

• For the ZK proof, we have to switch to a PQ system, some of which are discussed above. The most important criteria, in addition to PQ security, is driven by user experience: fast low-memory prover, and fast verification on the validator side.
• For JWT signatures, it will be determined by the OIDC standardization process.

Transition strategy for zkLogin: zkLogin addresses are hashes of many fields, including a user’s Web2 ID and a confidentially kept salt. These hashes, being 256 bits, will continue to be plausibly post-quantum for some time as only second preimage resistance is needed.

1. We need to adapt to PQ-JWT and PQ-zkSNARK, while retaining the same address.
2. Some hashes which are internal to the zkLogin circuit, need collision resistance. These need to be expanded to 384 bits for quantum resistance.

Protocols like DKG

Current popular random beacons are threshold BLS signature-based, which uses elliptic curves, and are subject to quantum discrete log attacks. The associated DKG protocols also heavily employ elliptic curve operations. In order to mitigate quantum attacks, researchers have designed random beacons based on symmetric and lattice primitives, such as HashRand, Lattice-based PVSS, and HERB. To transition from PreQ to PQ would require a change of the DKG protocol, but since it’s internal, it can be done anytime without changing the onchain APIs.

Application level use cases

Many smart contracts built on Sui use the cryptography primitives mentioned above on the application layer. Examples include oracles like the native bridge and time-locked encryption. Those applications would need to migrate to PQ alternatives similar to the ones discussed above.

Other Web3 efforts

Other Web3 foundations or companies also have post-quantum offerings or plans to build soon:

• Ethereum, Algorand, and Cardano are actively planning upgrades for quantum resistance.
• Solana recently introduced a quantum-safe feature, the Winternitz Vault, employing hash-based one-time signatures to protect funds from future quantum threats. Similar features can be implemented in Move.