Main Page

From Q-Day
Jump to navigation Jump to search
Quantum Computer (December 2023)
Google’s 72 qubit sycamore chip
Status (2023) Active
Qubit Types Superconducting, Photonic, Silicon, Neutral Atoms, Trapped Ions, Quantum Dots, Electrons on Helium, NV diamond and The Topological Approach.
Required Qubits to Break RSA 18,434 logical qubits or roughly 18 million physical qubits
Total members from consortia 185 European QuIC members + 147 QED-C members gives 332 members in total
Expected year to break cryptography 2030-2040
Vulnerable algorithms quantum-unsafe algorithms (RSA, DHKE, ECC, ECDSA and ECDH)


Q-Day Quick Start Guide

On Q-Day, we will cover the basics of quantum computing, followed by the quantum threat and its implications on cybersecurity.

Introduction

Q-Day presents the quantum threat in chunks, making it absorbable for the public. Our target audiences are mainly (IT) organisations and individuals that need to migrate to post-quantum secure systems.

To learn more about migration for centralised entities, see Organisations.

Classical Computers and Quantum Computers

Classical computers use bits. They process information in a binary form, which means that they either can be a 1 or a 0.. which essentially indicates the state is either “on” or “off”. They can also indicate true or false, or yes or no, for example. Quantum computers on the other hand, use qubits, which process information differently.

Qubits and Bits

A qubit (short for quantum bit) is the basic unit of information in quantum computing and counterpart to the bit (binary digit) in classical computing. A qubit plays a similar role as a bit, in terms of storing information, but it behaves much differently because of the quantum properties on which it's based[1]

Four Layers Of A Quantum Algorithm

Improvements in these 4 layers, means that the probability of breaking quantum-unsafe cryptography significantly increases.

Layer 1: Algorithm Layer

Shor's Algorithm does not directly solve the factoring problem, but first reduces it to a seemingly different problem. If another (better) algorithm than Shor's Algorithm were to appear, which is very unlikely, then that is a signficant improvement.

Layer 2: Logical layer

The goal of this layer is to write an algorithm in a language that a quantum computer understands. We want to build a circuit we can run. The logical layer is still something as a theory - not in the real-world.

The Question is: What is the best circuit?

There are different parameters.

- Minimal number of qubits - Low circuit depth (number of sequential operations) - Minimal number of specific gates?

It is a challenge by itself to optimise this logical, mathemetical layer because of the many parameters.

Layer 3: Error correction layer

Layer 4: Physical qubit layer

Practical use cases Quantum Computers

2021 Report from Mckinsey shows that China and the EU are leading in government funding.

A usable QC is expected around the year 2030.

Public QC Funding of Countries

Cloud-based services

Cloud-based quantum-computing services, giving the public access to QC. Personal and mobile QC systems are unlikely this decade.

Industry use cases

Pharmaceuticals, Chemicals, Automotive, are fields where QC can play a role in improving R&D and supply-chain optimisation. In Finance, QC may be used for portfolio and risk management.

Blockchain and Q-Day

Introduction

Given there are still over 4 million BTC (about 25% of all Bitcoins) which are potentially vulnerable to a quantum attack[2]. This is tens of billions of dollars at risk for Bitcoin alone!

An attack by a quantum computer that has the capability to break ECC would be disastrous for the cryptocurrency industry. Some call this day "Q-Day" or "Y2Q" or even a "Black swan event[3]".

To understand why Bitcoin is at risk today and truly understand the urgency - take a look at these parameters from the Global Risk Institute[^3]:

- the shelf-life time: the number of years the data should be protected for; - the migration time: the number of years needed to safely migrate the systems protecting that information; - the threat timeline: the number of years before relevant threat actors can potentially access cryptographically-relevant quantum computers.

Organizations will not be able to protect their assets from quantum attacks in time if the quantum threat timeline is shorter than the sum of the shelf-life and migration times.

Or simply put in a formula:

SHELF-LIFE + MIGRATION > THREAT.


The shelf-life is currently unknown. Shelf-life is until Q-Day, OR when the Bitcoin community chooses to implement quantum-resistant algorithms.
The migration time would be the time for cryptocurrency wallet owners to move from old vulnerable addresses to quantum-resistant addresses. Bitcoin is already at a disadvantage here as we assume it is not possible to reach 100% adoption rate (e.g. lost addresses, inactivity..)
The threat timeline - an estimation or prediction for when a quantum computer is feasible enough to break Bitcoin. Currently there are predictions that aim at around 2035.

Definition of Blockchain

A blockchain is “a distributed database that maintains a continuously growing list of ordered records, called blocks.” These blocks “are linked using cryptography. Each block contains a cryptographic hash of the previous block, a timestamp, and transaction data. A blockchain is a decentralized, distributed and public digital ledger that is used to record transactions across many computers so that the record cannot be altered retroactively without the alteration of all subsequent blocks and the consensus of the network[4].

Blockchain checklist

A blockchain by definition should have the following essential properties:

- Decentralisation - ensures that the blockchain is not governed by an individual, group, or even the government
- Immutability - ensures that no one can tamper with the system or change the data that has already been saved into the block
- Consensus mechanism - maintains the security of the blockchain by keeping a record of all legitimate transactions
- Transparent ledger - for providing a high level of trust and integrity
- Cryptography - primary for ensuring the security of participants, transactions, and safeguards against double-spending

In the next section, we will dive into where cryptography is being used within the blockchain.

Decentralisation in Blockchain

First, In centralised systems, the developers have the control and authority to decide what to do with the system - for example, banks and websites. These can be upgraded to post-quantum secure applications if necessary, in a much faster way than decentralised systems like blockchain. This is because in every upgrade a decentralised system like blockchain, there has to be an agreed consensus so all nodes execute the same upgrade.

Second, speaking of blockchain - all users have to manually move their funds from old addresses to new post-quantum secure addresses. Bank users do not have to do this.

Third, lost addresses (addresses where the user forgot or lost the private key) will never be able to move their funds in case of blockchain. These will always stay vulnerable to quantum attacks. Banks do not have this problem.

These are 3 major downsides of blockchain in the context of upgrading to post-quantum security and have to do with the nature of blockchain itself - decentralisation.

Cryptography in the Blockchain

Cryptography is being used in various places in the blockchain technology. First and foremost, it is being used in cryptocurrency addresses. Cryptocurrency addresses, where the user can share their hashed public key in an encoded form to the cryptocurrency's own wallet format and keep the private key to themselves - where the private key can be used to sign transactions to prove ownership of the public key. This ensures the security of all participants - protected funds and where transactions can take place without any centralised governance together with the above properties.

QC Vulnerabilities in Bitcoin

The implications for bitcoin are the following[5]:

Reusing addresses

To spend bitcoin from an address the public key associated with that address must be revealed. Once the public key is revealed in the presence of a quantum computer the address is no longer safe and thus should never be used again. While always using fresh addresses is already the suggested practice in Bitcoin, in practice this is not always followed. Any address that has bitcoin and for which the public key has been revealed is completely insecure.

Processed transactions

If a transaction is made from an address which has not been spent from before, and this transaction is placed on the blockchain with several blocks following it, then this transaction is reasonably secure against quantum attacks. The private key could be derived from the published public key, but as the address has already been spent this would have to be combined with out-hashing the network to perform a double spending attack. Even with a quantum computer a double spending attack is unlikely once the transaction has many blocks following it.

Unprocessed transactions

After a transaction has been broadcast to the network, but before it is placed on the blockchain it is at risk from a quantum attack. If the secret key can be derived from the broadcast public key before the transaction is placed on the blockchain, then an attacker could use this secret key to broadcast a new transaction from the same address to his own address. If the attacker then ensures that this new transaction is placed on the blockchain first, then he can effectively steal all the bitcoin behind the original address.

Quantum computer mining (unlikely to pose as a threat)

We can almost certainly say that quantum computers wont pose a risk to the Bitcoin's Proof-Of-Work system, even with optimistic estimates. Even if it did (for e.g. economical reasons), it would mean that quantum computers would be likely competing with each other.

Mitigating risks in Bitcoin

Bitcoin allows different types of transactions such as escrow and shared ownership. For the purpose of this section, we're limiting it to simple person-to-person transactions only.

Problem: Exposed public key

You still could protect your public key. There are two type of addresses - 'pay to public key’ (p2pk) and the hashed public key. The hashed public key is a one-way cryptographic function, the public key is not directly revealed by the address. However, the public key does get revealed once a transaction is sent from that address. This is why you should avoid address reuse as best you can.

Solution - Avoid address reuse

Avoid address reuse as best you can[^1]. If you would like to stay at the Bitcoin network, move your funds to a new address that hasn't their public keys exposed. Keep in mind though - if Q-Day were to happen, the market is expected to crash and the confidence in Bitcoin and its technology would be lost too.


Solution 2 - Migrating to a post-quantum secure blockchain

Migrating to a post-quantum secure blockchain, the blockchain would be inherently resistant to quantum attacks. If Q-Day were to happen, this would drive the price up and give confidence to its technology.

The price increase would occur because of the masses losing confidence in quantum unsafe blockchain technology and increased confidence in post-quantum secure blockchains. Post-quantum secure blockchains would serve a real use case, which is protecting the assets from quantum attacks, driving up its value.

Conclusion

As in the above, we're assuming that there is no quantum computer that will take advantage of the "window opportunity". As soon as you make a transaction, your public key will be revealed. So, until your transaction isn't mined - you are at risk for an attack. The adversary will first derive your private key from the public key and then initiate a competing transaction to their own address. They will try to get priority over the original transaction by offering a higher mining fee - stealing your coins.

It takes 10 minutes for a Bitcoin transaction to be mined, unless there is a network congestion, which has happened frequently in the past.. It could take much longer. So the rule is - as long as there isn't a quantum computer that is faster than the network - your funds are safe.

Currently it is unclear how fast a quantum computer will be in the future. If a quantum computer will be close to the 10 minutes mark (making it faster than the network), Bitcoin would be inherently broken.

Source: https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html

Miscellaneous

Common Misconceptions

All encryption is at risk from quantum computers.

Statement: False

Not all encryption is at risk from quantum computers. Only quantum-unsafe algorithms are at risk. For example, RSA, ECDSA, etc.

We can just switch to post-quantum algorithms when quantum computers arrive

Statement: False

We can’t do that because of the shelf-life time + the migration time. If those are greater than the threat timeline, then it is at risk.

Source: 2022 Quantum Threat Timeline Report

Quantum computers will be used to protect crypto

Statement: False

Quantum computers will be used to attack cryptography, not protect it. Post-quantum secure cryptography will be used to protect cryptography and keep it secure.

If quantum computing will ever be able to crack encryption the world will have bigger issues to worry about than blockchain. Quantum computing would in theory be able to set off nuclear weapons so I'd say crypto will be just fine.

… Because if quantum computing is being used to crack crypto... it has already cracked every other assets on the planet, every corporation and the Pentagon. Crypto wouldn't even be the most profitable or easiest route to go in this scenario.

Statement: False

We don’t know what state adversary will get its hands first on quantum computers. The consequences for centralised entities is far less than decentralised ones. Centralised entities have it easier to migrate to post-quantum secure systems.

Quantum computers are still decades away.

Organisations are making preparations today for the quantum threat. Intelligence agencies and experts are predicting the year 2030-2040.

Quantum-safe algorithms are just around the corner.

Statement: True

Post-quantum secure algorithms are still in the process of being standardised. However, this doesn’t mean that we can neglect the fact that migration will be easy, once we have those algorithms standardised.

Frequently Asked Questions (FAQ)

Additional Insights

1. Table ECDSA Cryptocurrencies 2. PQC Cryptocurrencies Comparison

PQC Services & Products

Product Name PQC Algorithm PQC Implementation Since Open Source Type of Service/Product
Signal XEdDSA and VXEdDSA, X3DH, PQXDH, Double Ratchet, Sesame 19 September, 2023 Yes Messenger
OpenSSH https://github.com/open-quantum-safe/openssh 11 April, 2023 Yes Protocol
Quantum Resistant Ledger (QRL) XMSS 2017 Yes Cryptocurrency
Mullvad VPN https://mullvad.net/en/blog/stable-quantum-resistant-tunnels-in-the-app April 6, 2023 Yes VPN