Undermining Bitcoin’s ECDSA

In the first installment of this series, we introduced the concept of “quantum computing” and how, while still experimental, its implications for blockchain security include the potential exposure of public keys, the theft of funds—and thus the transformation of cryptocurrencies as we know them.

That article focused on the SHA-256 algorithm’s contribution to Bitcoin security primarily via its consensus mechanism, but SHA-256 is only one side of the coin so to speak. In this second part, we will examine the Elliptic Curve Digital Signature Algorithm (ECDSA).

A signature algorithm deeply embedded within the Bitcoin protocol, ECDSA adds a layer of authentication by linking a public key with its corresponding private key. While it’s been a strong and reliable force in maintaining the integrity of transactions, quantum computing could potentially be kryptonite. ECDSA relies on the complexity of the “elliptic curve discrete logarithm problem,” a problem that becomes child’s play for a sufficiently advanced quantum computer running Shor’s algorithm.

MIT professor of applied mathematics Peter Shor developed the algorithm in 1994 while at Bell Labs in New Jersey, and it showcased the remarkable potential of quantum computers in the realm of cryptography. It is designed find the prime factors of an integer exponentially faster than the best-known algorithms can on classical computers. This capability poses a significant threat to ECDSA because it would allow one to derive private keys from their public counterparts –  thus enabling unauthorized signing of transactions, such as sending bitcoin.

There are several paths researchers are exploring to start preparing for crypto’s quantum challenges.

• Quantum-safe public key infrastructure (PKI): this includes revamping the key infrastructure underpinning our digital transactions; the HAPKIDO project takes a “hybrid approach” (the acronym drawing inspiration from the Korean martial art)
• Quantum-safe wallets: a new wave of wallets may feature quantum-resistant algorithms in parallel with traditional ones, offering a piecemeal transition towards quantum safety
• Algorithmic upgrade: retrofitting the Bitcoin protocol to substitute ECDSA with a quantum-resistant alternative would be a high-stakes game requiring community consensus, which has proven very difficult in the past

The last year has seen the inception of several post-quantum cryptography initiatives. Among them, the company PQShield stands out, offering solutions for quantum-safe cryptography “on chips, in applications, and in the cloud”.

The PQM4 project, a library for post-quantum cryptographic algorithms on ARM Cortex-M4 (a highly-efficient embedded processor) “aims to provide efficient and secure implementations of post-quantum cryptographic algorithms for resource-constrained IoT devices”.

Furthermore, the European Commission’s Quantum Flagship program is supporting the “Quantum Internet Alliance” to foster quantum communication infrastructures, echoing the global momentum towards quantum-resilient cryptographic frameworks.

While it’s tempting to think that a simple algorithmic swap could be the cure-all, the real world is often less forgiving. Protocols need rigorous vetting, and cryptographic standards require global acceptance. Any oversight could introduce fresh vulnerabilities, making this a delicate balancing act between security, efficiency and practicality. Developing and integrating quantum-resistant encryption technologies is more marathon than sprint. With growing interest and investment in quantum computing, the race is clearly on.