By Dr. Leemon Baird, Ty "Patches" Smith & Rohit Sinha

Quantum Computers
Ordinary computers today are known as “classical” or “non-quantum” computers. There is a new kind of computer that is being researched, known as a “quantum computer”. These will only be useful for a small number of problems, but for those problems, they can be exponentially more powerful than classical computers. At the moment, no quantum computers have been built that are big enough and reliable enough to be used to break cryptography, but it is possible that such computers could exist in the future. So it is worth considering whether we will be secure, if they are ever built.

Understanding Ed25519
Ed25519 is a version of the Edwards-curve Digital Signature Algorithm or EdDSA. It uses the Curve25519 elliptic curve to create secure digital signatures. Known for its efficiency and compact design, Ed25519 meets the high standards of security for classical computing. It offers 128-bit security, which means breaking it through a classical, non-quantum computer using the best attacks that are currently known would require an astronomical number of operations — 2^128. Breaking a key means that an attacker can find the private key associated with a public key. This would allow an attacker to steal all tokens and crypto in an account, or impersonate someone in a smart contract call, or do anything else that the legitimate owner can do. Therefore it is extremely important to ensure that the keys cannot be broken.

Quantum Resistance: The Reality for Ed25519 and ECDSA
Elliptic curve cryptography (ECC) is not quantum-resistant. This includes Ed25519 and other ECC-based schemes like ECDSA. Both rely on the security of ECC, which quantum algorithms — especially Shor’s Algorithm — can break with ease, if run on a large quantum computer. Shor’s Algorithm can solve the discrete logarithm problem, which forms the backbone of ECC security, in a very short time on a powerful quantum computer. This means that when quantum computing reaches sufficient strength, it could potentially break Ed25519 and ECDSA.

Ed25519 and ECDSA are well-regarded and mature technologies in the context of classical security. They remain secure in today’s world but are vulnerable in the face of future quantum advances. This vulnerability places them on equal footing against the quantum threat.

The Future of Cryptography: Post-Quantum Solutions
To guard against quantum attacks, cryptographers have started developing algorithms specifically designed to withstand quantum computing. The National Institute of Standards and Technology (NIST) recently said they will standardize at least three post-quantum signature algorithms. These include algorithms called Falcon, CRYSTALS-Dilithium, and SPHINCS+. All are strong candidates for quantum-resistant cryptography. However, adopting these algorithms comes with challenges.

1. Larger Signature and Key Sizes
   Post-quantum algorithms often require much larger signatures than Ed25519, which uses a compact 64-byte signature. For example: signatures in Falcon, CRYSTALS-Dilithium, and SPHINCS+ can range from several kilobytes to even tens of kilobytes. These larger sizes create challenges for storage and bandwidth, especially in systems with high transaction volumes.

2. Verification Time
   Quantum-resistant algorithms generally require longer verification times compared to Ed25519, which can perform over 70,000 verifications per second. In contrast, Falcon, CRYSTALS-Dilithium and SPHINCS+ operate at much slower speeds, performing approximately 14,000, or 10,000, or 1,000 verifications per second, respectively. This slower speed can be an issue for applications that need to verify high volumes of signatures rapidly.

These factors mean that moving to post-quantum cryptography will involve redesigning systems to handle the increased storage needs and computational demands. They will also increase the price of transactions, because of the extra bytes needed for the signature on each transaction. When NIST finishes standardizing those three signature algorithms, plus perhaps the additional algorithms being considered, then they can be integrated into Hedera. We are watching progress in this area carefully, to ensure that good solutions will be implemented before they are needed.

Hashes

Quantum computers can also be used to attack hash functions. Cryptographers believe that 256-bit hashes are secure against attacks from classical computers, and 384-bit hashes are needed to be secure against quantum computers. Most blockchains use 256 bits, but Hedera uses 384 bits. This ensures that Hedera is already post-quantum for its hashes, which ensures that the entire history of the hashgraph and the history of the consensus events are all tied together with secure, post-quantum hashes. So even if powerful quantum computers are developed, they will be unable to create a false history or false “blockchain”.

Looking Ahead: Preparing for a Quantum-Safe World

While Ed25519 and ECDSA offer excellent protection against classical attacks, they both lack defenses against the threat of quantum computing. The current push to develop post-quantum algorithms aims to keep cryptography secure as quantum technology advances. As research progresses, new standards are emerging to address this challenge and ensure a quantum-safe future for cryptography.