In our blockchain we use post-quantum cryptography to reach maximum protection level.
The point of a post-quantum cryptographic algorithm is to keep on ensuring its security characteristics even faced with quantum computers. Quantum computers are deemed feasible, according to our current understanding of the laws of physics, but some significant technological issues remain to be solved in order to build a fully operational unit. Such a quantum computer would very efficiently break the usual asymmetric encryption and digital signature algorithms based on number theory (RSA, DSA, Diffie-Hellman, ElGamal, and their elliptic curve variants).
In 2022, the U.S. National Institute of Standards and Technology (NIST) concluded the third round of its post-quantum cryptography standardization process, which began in 2016.
In the first round, 69 algorithms were submitted. Only 3 digital signature schemes made it to the final round: two of them, CRYSTALS-Dilithium and Falcon, are based on lattice problems, while the third, SPHINCS+, is based on hash functions. Kyber 512 has also reached the final round of examination, but in 2023.
Let’s describe all these algorithms:
Kyber 512
Kyber is a post-quantum key encapsulation mechanism (KEM), designed to protect sensitive information in the face of future quantum computers. It’s like a highly secure lock that requires a special key to open. This key is generated using complex mathematical problems that are extremely difficult for even powerful computers to solve, even quantum ones.
Kyber is considered one of the most promising post-quantum cryptography algorithms and has been selected as a finalist in the NIST post-quantum cryptography standardization project. This means it’s being evaluated for potential inclusion in future cryptographic standards.
Technical information
Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. The submission lists three different parameter sets aiming at different security levels. Specifically, Kyber-512 aims at security roughly equivalent to AES-128, Kyber-768 aims at security roughly equivalent to AES-192, and Kyber-1024 aims at security roughly equivalent to AES-256.
Crystals-Dilithium
Dilithium is a digital signature scheme that is strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices. The security notion means that an adversary having access to a signing oracle cannot produce a signature of a message whose signature he hasn’t yet seen, nor produce a different signature of a message that he already saw signed. Dilithium is one of the candidate algorithms submitted to the NIST post-quantum cryptography project.
CRYSTALS-Dilithium is a lattice-based digital signature scheme whose security is based on the hardness of finding short vectors in lattices. The CRYSTALS-Dilithium Digital Signature Algorithm is a member of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite of algorithms.
Technical information
The strength of a CRYSTALS-Dilithium key is represented by the size of its matrix of polynomials. For example, CRYSTALS-Dilithium (6,5) has a matrix size of 6x5. The larger the matrix size, the stronger the key. CRYSTALS-Dilithium keys can only be used for Digital Signature Generation and Verification.
Dilithium is also can be used in a so-called hybrid mode in combination with an established “pre-quantum” signature scheme.
Falcon
Falcon is a post-quantum signature scheme selected by the NIST at the fourth round of the post-quantum standardisation process.
The design rationale of Falcon takes advantage of multiple tools to ensure compactness and efficiency with provable security. To achieve this goal, the use of a NTRU lattice allows the size of the signatures and public-key to be relatively small, while fast Fourier sampling permits efficient signature computations.
Technical information
- Falcon is the most compact of all post-quantum signature schemes
- a true Gaussian sampler is used internally, which guarantees negligible leakage of information on the secret key up to a practically infinite number of signatures (more than 2^64)
- thanks to the use of NTRU lattices, signatures are substantially shorter than in any lattice-based signature scheme with the same security guarantees, while the public keys are around the same size.
- use of fast Fourier sampling allows for very fast implementations, in the thousands of signatures per second on a common computer; verification is five to ten times faster.
The authors of Falcon provide a reference implementation in C as required by the NIST and one in Python for simplicity
Sphincs+
Sphincs+ is a lighter version of SPHINCS, which principle is like previously described protocols.
Algorithm developers made some efforts to make SPHINCS faster, more efficient and protective.
Technical information
These changes have resulted in parameter sets with signature sizes as small as 8kb. While this is at the lowest NIST security level and requires a few seconds for signing, it’s still a significant improvement. For many applications like certificate or code signing, a signing time of around one second is acceptable. Even at the highest NIST security level (5), our signature size is only 30kb, compared to SPHINCS’s 41kb.
They also have improved multi-target attack protection by using different hash functions for each call, keyed with unique keys and bitmasks. These are pseudorandomly generated based on context and a public seed. Also the tweakable hash functions were introduced for more flexibility.
Finally, developers present three different incarnations of SPHINCS+:
- SPHINCS+-SHA3 (using SHAKE256)
- SPHINCS+-SHA2 (using SHA2)
- SPHINCS+-Haraka (using the Haraka short-input hash function)
Shipovnik
”Shipovnik” is a digital signature scheme constructed using the Fiat-Shamir transformation applied to the Stern identification scheme (with zero-knowledge proofs), developed by the company Kryptonit.
The security of this digital signature scheme is based on the computational hardness of the random linear code decoding problem. Elwyn Berlekamp proved in 1978 that this problem is NP-complete. To date, no efficient algorithms for solving problems of this class are known, neither for classical nor for quantum computers.
Technical information
According to “Kryptonit”, as of November 2023, the best known classical computer attack against the “Shipovnik” scheme requires 2^256 bit operations. This means it is infeasible to execute within a reasonable timeframe even on the fastest supercomputers. The theoretical quantum resistance is estimated at 2^170 operations, which also makes it impractical to break, even with future quantum computers with billions of qubits.
The “Shipovnik” scheme possesses several significant advantages that distinguish it from others. Among them is a small public key size, which accelerates key exchange and reduces traffic. In this parameter, “Shipovnik” outperforms all lattice-based signatures. Most importantly, the scheme’s security has been fully substantiated, with the proof relying solely on mathematical problems that have already been proven to be difficult.
The same cannot be said for the digital signatures that reached the NIST competition finals. For example, strict security proofs are only provided for CRYSTALS-Dilithium and SPHINCS+. However, even they are based on the assumption of the hardness of certain problems whose complexity has not been proven. Of all the finalists, the SPHINCS+ algorithm is the most difficult to implement and is also slower. However, this algorithm was left as a backup option, as it is the only one based on a different mathematical basis - on hash functions rather than lattices.