This report presents an overview of post-quantum digital signatures (PQDS) for blockchain technology. The advent of quantum computing poses a significant threat to the cryptographic algorithms currently used in blockchain systems, necessitating the development and adoption of quantum-resistant algorithms. This report covers the basics of digital signatures, the current standardized algorithms, various types of post-quantum cryptographic approaches, community discussions, and other related projects. We discuss how these algorithms can be used in the blockchain ecosystem and list all the pros and cons. This report is intended to serve as a starter guide for a detailed post-quantum road-map for the blockchain community.
Digital Signatures
Digital signatures are essential for verifying the authenticity and integrity of messages, transactions, and documents. A valid digital signature guarantees the receiver that the message is from the sender and has not been tampered during transit. These signatures use a pair of keys: a private key for signing and a public key for verification. When a sender initiates a transaction, they sign it with their private key, generating a unique signature. Anyone with access to the sender's public key can verify this signature, ensuring that the transaction is authentic and has not been altered.
In blockchain systems, each transaction is authorized by a digital signature. This signature is a cryptographic proof that verifies the sender's identity and ensures that the transaction has not been tampered with. Miners and validators use these signatures to confirm the validity of each transaction on a block, before adding that block to the blockchain.
Most blockchains currently use the Elliptic Curve Digital Signature Algorithm (ECDSA) or its variants such as BLS and Schnorr. These signature schemes are efficient and provide strong security guarantees under classical computing assumptions. Since the hardness assumption for ECDSA is the discrete logarithm problem, and quantum computers can solve this using Shor's algorithm in polynomial time, these signature schemes need to be replaced with quantum-safe signatures for the survival of blockchain systems.
NIST Standardization
The National Institute of Standards and Technology (NIST) has been actively involved in standardizing post-quantum cryptographic (PQC) algorithms. Their standardization process involves multiple rounds of open-source evaluation, focusing on security, efficiency, and overall performance of various PQC algorithms. In July 2022, NIST announced three digital signature algorithms for post-quantum standardization
- CRYSTALS-DILITHIUM
- FALCON
- SPHINCS+
NIST continues to seek additional digital signature schemes, including code-based and isogeny-based signatures, to diversify and strengthen the cryptographic toolbox against quantum threats.
Table 1 presents all the digital signature candidates for NIST PQC standardisation, their type and latest status. The round numbers in the status indicate the NIST round after which the scheme was not considered for standardization.
Table 2 presents the signature schemes that NIST is considering for standardization in an additional round. Since these schemes are still under consideration, we have included all the published attacks for these schemes.
Post-Quantum Digital Signature Schemes
Lattice-Based Cryptography
Lattice-based cryptography is founded on the complexity of lattice problems, notably the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem. These problems are computationally hard, making lattice-based schemes resistant to both classical and quantum attacks. The primary strength of lattice-based cryptography is its robustness and scalability. These schemes are efficient and can handle large-scale data and transactions, making them suitable for applications such as secure communication protocols and blockchain technology. CRYSTALS-Dilithium and Falcon are prominent examples of lattice-based digital signature algorithms selected by NIST for post-quantum cryptographic standardization.
- CRYSTALS-Dilithium: Dilithium is based on the hardness of lattice problems, specifically using the Module Learning with Errors (MLWE) problem. It is designed to be secure against both classical and quantum attacks, providing strong security under chosen message attacks. It has been selected by NIST for post-quantum cryptographic standardization due to its efficiency and robust security guarantees, making it suitable for a wide range of applications including secure communications and blockchain technology.
- Falcon: Falcon (Fast-Fourier Lattice-based Compact Signatures over NTRU) is another lattice-based scheme. It relies on the NTRU lattice and the Fast Fourier Transform to achieve both security and efficiency. Falcon is known for its small key sizes and fast signature generation and verification, making it an attractive option for applications requiring high-performance operations while maintaining strong security against quantum attacks.
Altough lattice-based cryptography provides a good balance of small key sizes and efficiency, a recent publication, Quantum Algorithms for Lattice Problems by Yilei Chen, has questioned the structured approach to these algorithms. This paper explores a polynomial-time quantum algorithm for the LWE problem with certain polynomial modulus-noise ratios. Due to the reductions of different types of SVP to LWE shown by Oded Regev, this proves fatal for lattice-based cryptography. Despite innovative ideas using Gaussian functions with complex variances and windowed QFTs, an unresolved bug prevents the algorithm from fully achieving its goal. While lattice-based schemes Dilithium and Falcon remain secure for now, this research raises concerns about future vulnerabilities.
Hash-Based Cryptography
Hash-based cryptography relies on the security properties of cryptographic hash functions to create quantum-resistant digital signatures. Schemes such as SPHINCS+ and XMSS utilize the difficulty of inverting hash functions to provide strong security guarantees.
One of the key advantages of hash-based cryptography is its simplicity and well-understood security properties. Unlike more complex mathematical problems, the security of hash-based schemes is straightforward to analyze and implement. However, these schemes often result in larger signature sizes and require more computational resources, which can be a challenge in resource-constrained environments.
- SPHINCS+: SPHINCS+ is a stateless hash-based digital signature scheme. It is designed to be secure against quantum attacks by relying solely on the security properties of cryptographic hash functions. SPHINCS+ offers flexibility in terms of signature size and security levels, and it is particularly well-suited for environments where long-term data integrity and security are critical.
- Picnic: Picnic is a post-quantum digital signature scheme that combines symmetric key primitives with zero-knowledge proofs to provide security against quantum attacks. Unlike lattice-based schemes, Picnic does not rely on any specific hard mathematical problems but instead uses cryptographic hash functions and block ciphers.
Multivariate Polynomial Cryptography
Multivariate polynomial cryptography is based on the difficulty of solving systems of multivariate quadratic equations. Schemes like Rainbow and GeMSS use the complexity of these equations to offer robust security against quantum attacks, making them suitable for applications where both speed and security are essential.
The primary advantage of multivariate polynomial cryptography is its efficiency in generating and verifying signatures. However, the complexity of these schemes can pose implementation challenges, requiring careful optimization to ensure security and performance.
-
Rainbow: Rainbow is a multivariate polynomial-based digital signature scheme based on the Oil-Vinegar signature scheme and relies on the hardness of solving systems of multivariate quadratic equations, which is an NP-hard problem. This scheme offers very small signature sizes and efficient verification, making it suitable for applications requiring high-performance and secure digital signatures.
The paper Breaking Rainbow Takes a Weekend on a Laptop by Ward Beullens introduces a new key recovery attacks against the Rainbow signature scheme. This attack significantly outperforms previous ones, making it feasible to recover the secret key for Rainbow's SL 1 parameters within an average of 53 hours using a standard laptop. In lieu of this attack, Rainbow was not selected for standardization.
-
GeMSS: GeMSS (Great Multivariate Short Signature) is another multivariate signature scheme built from the Hidden Field Equations cryptosystem (HFE) by using the so-called minus and vinegar modifiers (HFEv-). It offers short signatures and high performance. GeMSS has been selected as one of the alternative candidates in the third round of the NIST Post-Quantum Cryptography Standardization Project.
Isogeny-Based Cryptography
Isogeny-based cryptography leverages the difficulty of computing isogenies between elliptic curves, a problem that is considered resistant to quantum attacks due to its mathematical complexity. Isogeny-based schemes are particularly suitable for constrained environments like IoT devices and mobile platforms, where both security and efficiency are crucial.
The strength of isogeny-based cryptography lies in its small key sizes and efficient computations, making it ideal for applications where resources are limited. Despite its promising security features, isogeny-based cryptography is still an emerging field, with ongoing research needed to fully understand its potential and limitations.
- SQIsignHD: SQIsignHD is a post-quantum digital signature scheme inspired by SQIsign, leveraging recent algorithmic advancements in the representation of isogenies of arbitrary degrees. With signatures as small as
bytes for NIST-1 security levels, SQIsignHD combines compactness with strong security, though the verification process, which involves computing a higher-dimensional isogeny, remains computationally intensive.
Comparison and Analysis
In this section, we provide a comparative analysis of various post-quantum cryptographic (PQC) digital signature schemes, focusing on their key sizes and performance metrics. Performance data has been aggregated from different sources, i.e. PQC Digital Signature Speed Tests, GeMSS, SQIsign and is provided here for reference. For more details about how PQC bench-marking is performed, refer to GeMSS, pqm4 and SQIsign.
Table 3 presents a comparison of the schemes based on their public key size (pK), secret key size (sK), and signature size (sig) in bytes. It highlights the sizes of public keys, secret keys, and signatures for each scheme across NIST security levels 1 (128 bit AES), 3 (192 bit AES), and 5 (256 bit AES). For example, the Dilithium schemes exhibit moderate key sizes with relatively large signatures, while Falcon schemes are characterized by smaller key sizes and signatures. SPHINCS+ and Picnic have very compact key sizes but significantly larger signatures. Rainbow and GeMSS schemes, although offering very small signature sizes, have extremely large public and secret key sizes. The emerging SQIsignHD and SQIsign2D-West schemes demonstrate compact signature sizes, emphasizing its potential efficiency.
Table 4 evaluates the performance of these schemes in terms of key generation, signing, and verification times. The provided values are in millions of CPU cycles (MC - Mcycles). Dilithium and Falcon schemes show balanced performance, with Falcon being notably efficient in signing and verification. SPHINCS+ and Picnic, despite their larger signature sizes, exhibit slower signing and verification times. Rainbow and GeMSS schemes, while having large key sizes, also have substantial signing and verification times, making them less practical for performance-critical applications. The performance data for SQIsignHD is not available due to it's recent publication.
Community Discussions about PQC
The blockchain community has been exploring quantum-resistant solutions
since the early
BitcoinPQ
Bitcoin Post-Quantum (BPQ) was an experimental branch of Bitcoin designed to address the vulnerabilities posed by quantum computing. BPQ aims to mitigate this risk by incorporating quantum-safe digital signatures, specifically the extended Merkle signature scheme (XMSS), which is resistant to both classical and quantum attacks.
BPQ intended to serve as a contingency blockchain to safeguard against sudden advancements in quantum computing that could jeopardize current cryptographic methods. The project proposed a hard fork of Bitcoin, introducing new rules at a specific block height to support quantum-safe signatures, increase block size, and alter the mining algorithm. Users were encouraged to transfer their assets to new XMSS-based addresses to protect their funds. This initiative also includes the development of quantum-safe non-interactive zero-knowledge proofs to maintain privacy. This project seems to be abandoned with no updates since
QRL: The Quantum Resistant Ledger
The Quantum Resistant Ledger (QRL) is a blockchain platform designed to be secure against both current and future quantum computing threats. QRL offers a post-quantum secure digital signature scheme through the use of hash-based eXtended Merkle Signature Scheme (XMSS) signatures to secure transactions. This framework protects digital assets and communications, ensuring long-term security and resilience. QRL also supports a range of features including reusable addresses, quantum-resistant tokens, and secure messaging, making it a comprehensive solution for quantum-safe blockchain technology.
According to the QRL road-map, the platform has several advanced features in development and planned for future releases. These include a quantum-secure Proof-of-Stake system currently in development, aimed at enhancing the network's scalability and security. The road-map also outlines plans to introduce smart contracts, leveraging quantum-resistant cryptographic techniques to maintain the integrity and functionality of decentralized applications within the QRL ecosystem. The platform supports multi-platform wallets, quantum-resistant tokens, and secure messaging systems using advanced cryptographic algorithms like Dilithium and Kyber. Additionally, QRL has implemented an extensible address format, allowing for future upgrades to cryptographic hash functions and signature schemes.
Despite initial enthusiasm, the project faced controversies and diminished community engagement, though it continues to update its platform. QRL's website remains active, but community discussions have significantly decreased since 2019.
Ethereum Quantum Resistance Roadmap
Ethereum's community has been proactive in discussing quantum resistance. The Ethereum road-map includes a comprehensive plan to future-proof the blockchain against emerging threats, such as quantum computing. One critical aspect of this road-map is enhancing Ethereum's cryptographic resilience by incorporating quantum-resistant technologies. Although quantum computers are still some years away from being a significant threat, Ethereum developers are already working on integrating cryptographic solutions like STARK-based and lattice-based signatures.
In his article on STARK signature aggregation, Vitalik Buterin outlines a method to aggregate a large number of digital signatures using STARKs. The current BLS signature aggregation method is not quantum-proof and requires significant computational resources. Buterin proposes using hash-based signatures and a multi-layered recursive approach for STARK proofs to handle aggregation efficiently. This approach allows the network to manage a large number of signatures securely and efficiently, potentially within a few seconds, even in an unstructured network.
Both the cryptographic solutions are still in the research phase and are considered several years away from implementation, but these efforts ensure that Ethereum remains secure and reliable well into the future.
PQC-related Projects & Proposals
Quantum Canary
The Quantum Canary project is designed as an early warning system to detect if quantum computational capabilities that could threaten blockchain security have been developed. This innovative approach involves implementing smart contracts that issue bounties for breaking specific cryptographic signatures. The idea is to incentivize individuals to attempt breaking these signatures; successful attempts would indicate that the encryption algorithm is no longer secure. This proactive measure allows the blockchain community to stay ahead of potential threats and update security protocols before any large-scale quantum attack can occur. For more details about how this could be implemented, visit 'A cryptographic canary against quantum computers'
Emergency Hard-Fork
Proposed by Ethereum co-founder Vitalik Buterin as a response to a quantum emergency, this measure involves a hard fork that would revert all blocks created after the detection of large-scale quantum-based theft. The primary goal is to safeguard user funds by disabling traditional Externally Owned Account (EOA)-based transactions and introducing new transaction types that support quantum-resistant STARK proofs. This proposal is designed to quickly switch to quantum-resistant signatures in case of a quantum attack. By switching to quantum-resistant cryptographic methods, the blockchain can maintain its integrity and continue to protect user assets effectively.
Expiring Unsafe Addresses
To mitigate risks, there is a proposal to gradually phase out old and vulnerable blockchain addresses that expose public keys, which are susceptible to quantum attacks. This involves notifying users to transfer their funds to quantum-safe addresses, ensuring that their assets remain secure. We would also require consensus among the blockchain community to ignore transactions from unsafe addresses after a specified period, rendering them unusable. By encouraging users to adopt quantum-safe addresses, the community can ensure a smoother transition to more secure cryptographic practices, ultimately protecting the network from future vulnerabilities and maintaining the trust and reliability of blockchain technology.
Implementations and Source Code
Here, we provide links to the implementations and source code for various post-quantum digital signature schemes. Detailed repositories and resources are available for each scheme, allowing researchers and developers to explore, test, and integrate these quantum-resistant algorithms into their applications.