Mastodon# Quantum Computing: a threat on the Integrity of public blockchains

#### Table of Contents

### But what is Shor’s algorithm?

### The 0xkishan Newsletter

Quantum computing is a new paradigm of computing that uses quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data.

June 07, 2023

In this article, we’ll tackle some mind-boggling questions that even Marvel can’t wrap their heads around. Seriously, all they do is slap the word ‘quantum’ on everything and call it a day. But hey, let’s dive in and see if we can untangle this entanglement.

- Will advancement in Quantum Computing leave Cryptography in the dust?
- Will it be able to know the private keys?
- How will it affect public blockchains like Bitcoin and Ethereum?
- and, Will our assets be safe?

This article doesn’t require any pre-requisite; I’ll explain everything as we proceed. Let’s address Quantum Computing first.

Quantum computing is a new paradigm of computing that uses quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers can potentially solve some problems much faster than classical computers, such as factoring large numbers or searching large databases.

Now let’s compare our quantum computer with our day-to-day classical computer.

For example, a 2048-bit RSA key, which is commonly used for secure communication, requires factoring a 617-digit number. (100000000000000000000000000000) => This is only 30 digit number, by the way.It is estimated that a classical computer would take billions of years to factor a 2048-bit RSA key using the best-known algorithms.

In contrast, a quantum computer running Shor’s algorithm could factor a 2048-bit RSA key in a matter of hours or days, depending on the number of qubits and the quality of the quantum hardware.

Fascinating, isn’t it? Classical computers take billions of years. By the way, our whole universe is only 13.8 billion years old, and we’ve been walking around the planet for 6 million years. On the other hand, a quantum computer will crack this while we are gone for a long drive, and when we come back, all our assets are gone. Just Joking.

Or was it?

Here’s the twist, though. Building a large-scale quantum computer capable of running Shor’s algorithm is a significant engineering challenge, and no such computer currently exists. Unfortunately, or maybe fortunately, the largest quantum computers today have around 100 qubits, which is not enough to factor a 2048-bit RSA key.

You see, you’ll need at the very least 4,000 damn logical qubits to factor a 2048-bit RSA key in a few days or less.

Phew, that was close. **So, are we safe?** Not really until we develop a way to protect ourselves; the cryptographic community is well aware of these potential threats and is actively working on developing quantum-safe cryptography.

Quantum-safe cryptographic algorithms are designed to be resistant to attacks from both classical and quantum computers. These new algorithms are being developed and standardized to replace vulnerable ones, ensuring the continued security of digital communication and assets.

One example of quantum-safe cryptography is lattice-based cryptography, which relies on the hardness of certain problems in lattice theory that are believed to be resistant to quantum attacks. Other candidates include code-based cryptography, multivariate cryptography, and hash-based signatures.

You might be wondering, but how is factoring a prime number has to do anything with the crypto industry?Batman is not affected by the crypto industry; he is a billionaire god dammit.

Factoring large prime numbers is an essential part of many cryptographic systems, including the widely used RSA encryption and digital signature schemes. These systems rely on the fact that it is computationally infeasible to factor large numbers into their prime factors using classical computers.

In RSA encryption, a public key is generated by multiplying two large prime numbers, and the private key is derived from the factors of this product. The security of RSA encryption relies on the fact that it is difficult to factor the product of two large prime numbers into its factors, making it difficult for an attacker to obtain the private key and decrypt messages.

Similarly, in digital signature schemes like RSA and Elliptic Curve Cryptography (ECC), the private key is used to sign messages, and the public key is used to verify the signature. The security of these schemes also relies on the difficulty of factoring large numbers.

If a quantum computer capable of running Shor’s algorithm becomes available, it could efficiently factor large numbers and break the security of these cryptographic systems. This is why the development of quantum-safe cryptographic algorithms is crucial to ensure the continued security of digital communication and assets in the face of quantum computing advancements.

How the hell am I supposed to know? Wait, I am the author.

Shor’s algorithm is a quantum algorithm for factoring large numbers efficiently. It was developed by Peter Shor in 1994 and is one of the most famous quantum algorithms.

The algorithm works by finding the period of a function, which is a mathematical property that repeats after a certain number of iterations. In the case of factoring large numbers, the function used is the modular exponentiation function, which takes a base number, raises it to a power, and then takes the remainder when divided by a large number.

This is way too complex to explain in this article. I’ll write a dedicated article in future to explain it. Please don’t be disappointed.

Is there any other way apart from factoring the prime number that our quantum computer can do to break blockchain security?Well, it can disrupt the consensus mechanism that is used to generate blocks after coming to an agreement with the majority of the participants in the network.

Quantum computers could use their speed advantage to manipulate the consensus algorithms that blockchain networks use to agree on the state of the ledger. For example, an attacker with a quantum computer could perform a 51% attack on a proof-of-work blockchain, such as Bitcoin, by outpacing the honest nodes in finding new blocks and creating a longer chain. This would allow the attacker to double-spend transactions or rewrite the history of the ledger.

However, quantum computing could also offer some benefits for blockchain technology, such as enhancing its performance, scalability, and efficiency. For example, quantum computers could enable new levels of computational power and data analysis for blockchain applications, such as smart contracts, supply chain management, or healthcare records.

Who knows, maybe we’ll combine them together to form Quantum Blockchain!

It could use quantum encryption and signatures to protect the transactions and quantum consensus algorithms to generate the blocks. Quantum blockchain could also use quantum cloud computing platforms to make blockchain more accessible and affordable.

In summary, quantum computing poses both challenges and opportunities for blockchain technology. It could threaten its security by breaking its cryptography and disrupting its consensus, but it could also enhance its performance, scalability, and efficiency by enabling new forms of computation, encryption, and signatures. Quantum blockchain is a possible solution that integrates both technologies to create a more secure and functional network.

References:

. . .

Subscribe to the newsletter to learn more about the decentralized web, AI and technology.