Discussion Post on PQC - Quantum Vulnerabilities of Blockchains

Cryptography
, ,
21

Apologies for that, it must have been the framing.

Should have added more context.

I was referencing the link on this sentence.

The section “Consensus in the decentralised realm of Bitcoin is hard” talks about how challenging it will be to implement quantum-safe cryptography on legacy blockchains. In its third paragraph, the author(s) infer that governance and consensus would be difficult after migration because the process would take more time than before.

My questions are:

  • Is this true?
  • If true, why and how does quantum proof cryptography affect blockchain consensus?

I would also appreciate any resources you can share on the subject matter

2 Likes
22

I think you are misunderstanding the paper and conflating the decision-making that takes place within a community and on-chain consensus. They are not the same thing.

“Achieving this consensus is extremely difficult, so the governance issues are possibly equal to the complexities of the technical problems – agreement takes much more time than people think,” says Barmes. While not enough is being done on technical solutions, too little attention is also given to governance issues, he adds.

6 Likes
23

much gratitude to you @Harvesto for your work in this investigation paper. this exploration paper required some investment to comprehend. i.e it took my time. my opinion in this research paper is that With both the specialized and administration issues, I think plainly a significant measure of time is expected to make digital currencies impervious to quantum assaults. At present, not very many digital forms of money have made the most vital moves towards becoming quantum-secure, and most digital forms of money don’t for even a moment recognize this issue in their guides. To appropriately get the fate of cryptographic forms of money I accept that center improvement groups ought to become educated about the dangers, devise a movement plan, and consolidate it in their guide. Acting presently will take into consideration sufficient readiness and at last a smooth progress. I think if we fail to act on time, rushing into solutions when the threat becomes more imminent, the chance of implementation errors increases which can have an undesired result.

4 Likes
24

Great observation Henry, devising a plan that makes digital currencies impenetrable to quantum attacks will take time but I will like to mention some theoretical methods to combat potential quantum attacks (read about this from a website but can’t recall the exact source)

  • Dynamic AI models can compute the fraud risk of pending transactions at every moment until validation. These models can deduce the potential profits of adversaries for every threat vector, thus arriving at the possibility of any transaction being fraudulent. Insurance products can be designed to cover the fraud risk of pending transactions.
  • Consensus rule: Principles of effective incentive design can be used to formulate changes in consensus rules, such as applying a markup on transaction fees for p2pk and reusing p2pkh wallets. This would prompt users to switch to safer behaviour.

@Larry_Bates @Ulysses do you know if any of these methods have been implemented and has any of the methods made any difference?

5 Likes
25

Thanks @GloriaOkoba for your quick response. Your comment is helpful to me. Though looking forward to hearing from @Larry_Bates and @Ulysses .

2 Likes
26

glad to know i could be of help @Henry, hopefully we get to hear from @Ulysses and @Larry_Bates soon

2 Likes
27

Digital Ledger Technologies (DLT) such as blockchain are being deployed as part of diverse applications that span multiple market segments. Application developers have successfully leveraged the blockchain characteristics of decentralization, immutability, cryptographic security and transparency to create the solution benefits of redundancy, non-repudiation and enhanced auditing/compliance. Blockchain infrastructures make very extensive use of digital signature algorithms, hashing algorithms and public-key cryptography. The rapid pace of progress that is being experienced with quantum computing technology has made the prospect of quantum computer cyber-attacks a very real possibility.

Initiatives are therefore underway to augment today’s blockchain infrastructures with cryptographic algorithms that are highly resistant to quantum computer attack. These post-quantum algorithms are based on computational problems that are known to be very difficult for quantum computers to solve by using either Shor’s algorithm or Grover’s algorithm.

5 Likes
28

thanks for the enlightenment @WaterLily ,found this very helpful

2 Likes
30

Very interesting topic @Harvesto … from what I have read about this topic
QC mostly poses a threat to discrete log or integer factorization-based public key signature techniques. Currently, the discrete log issue in an elliptic curve group is what makes bitcoin work. The ECDSA signature algorithm includes this. If quantum computing becomes a reality, it would be foolish to keep this module in place.

To be more realistic, this should be amended in a few years with a soft fork, which is likely to pass with little opposition. (Assuming no one has discovered a means to cash in on the vulnerability and also controls a significant mining cartel.)

According to Wikipedia, there are plans to switch from an ECDSA signature to a Schnorr signature soon. Although it uses less space, this technique is still based on the discrete log problem. People are eager to lower the storage cost because, as things stand, storing the signature data is the most expensive part of a transaction. According to some responses, QC will completely ruin cryptography. That is untrue. We already have public key cryptography that is QC resistant, such as NTRU Quantum-Resistant High Performance Cryptography. Since this system is built on integer lattices rather than discrete logs or factorization, nobody currently appears to be aware of how to apply QC to solve this issue. As a result of this competition, many more such algorithms will be developed (Computer Security Resource Center). According to some responses, QC can be used to extract a private key from a bitcoin address. For the most typical type of address, namely pay to public key hash, this is categorically false. The public key is hashed as shown in this diagram (File:PubKeyToAddr.png - Bitcoin Wiki), which shows how it becomes an address. Addresses aren’t just public keys in a hat (anymore).

5 Likes
31

Hi Gift

Glad to see you’re well-grounded in QC and cryptographic signature knowledge.

I especially agree with your remark here. The notion that quantum computers/hackers will eventually break Bitcoin and other blockchains is just typical FUD being spread by ignorance of how these systems work.

True, the QC threat to existing blockchains is real, but not on the scale most people think.

Also, I like to take another thinking approach; quantum computing can be used to strengthen and secure the blockchain against the various threats it faces daily.

Just thinking about it lights me up, because it’s not all doom and gloom as articles out there will have you believe.

Thanks for stopping by and sharing your thoughts!

1 Like
32

Hi Henry

Thanks for sharing your thoughts on the post.

Well, the threat is imminent, but still far away.

Kind of like a paradox.

But then, you’re right when you say center improvement groups (or Devs) should do something about it.

Already, they have started doing some groundwork and research, with the evidence in [NIST’s Quantum] proof signatures. (NIST Reveals 26 Algorithms Advancing to the Post-Quantum Crypto ‘Semifinals’)

I think what’s left is the successful migration of these blockchains to these signature schemes and some more security checks.

Well, let’s see how it goes.

2 Likes
33

Quantum advantages

Though I think Shor’s Algorithm is a cracking saver and makes the work easier when in combo with quantum computers. Shor’s Algorithm reduces the amount of time complexity to solve for a private key from it’s public key from O (2^n) to O(n⁴)

Grovers Algorithm reduces the time complexity to solve proof of work for a block from O(N) to O(√N).

Where N is d*2^32

where d is the difficulty of mining the block

Screenshot_20221007-061906
Screenshot_20221007-061906712×391 66.9 KB

Ethereum’s Vulnerability

Now let’s talk about Ethereum, because Ethereum incorporates an account based system rather than the UTXO based system. This is a critical protocol that make a massive difference to it’s quantum vulnerability. Instead of being able to hijack a single transaction while they are in the transaction pool against the time constraints, once an Ethereum account has sent a transaction, it must be stated, meaning the public key is publicly available. If there’s any currency remaining in the Ethereum account that sent the transaction, then this account will be vulnerable until the key us recycled and a new key is created. This is compounded by the fact that in Ethereum there’s a user using block explorers. You can see how much cryptocurrency is held in all the public private key pairs. One example is the ether scan.

Since it’s near impossible to know and attack is happening, what should be done to keep the Blockchain network safe

Well I’ve got some questions if anyone can explain further to me. @Harvesto @zube.paul @Larry_Bates

If encryption is based on the factor of large numbers, then it’s assumed that a hack is possible, cause the process will break with ease (given a hack-to-make quantum computer) . But, are there any other kinds of encryption? I noticed that the private keys for private cryptocurrencies have both numbers and letters. Has encryption advanced to tackle this ever since.

4 Likes
34

Steganography and other types of encryption certainly exist and have existed. The issue becomes when encryption is necessary and why. If someone is using steganography, it’s because they are attempting to hide information even further than when using a simple encryption algorithm. Applied in real life, it would be borderline absurd to start implementing extreme encryption types for simple messaging or simple communications. Further, the encryption types that are utilized currently are implemented for both the ease of application and the ease of decryption for the end user.

This also starts to get to the notion of “encryption indicates information of value” thus creating a target by proxy of indicating there is something valuable. The less an attacker “knows” that something is encrypted, the less likely that attacker is to choose that as a target. In this case, the different types of encryption would be useful to hide information from attackers or observers that would not be the intended audiences. This type of encryption would need to be “non-standardized” as to not immediately flag a potential observer that something of importance was in transit. In this case, a lower frequency type of encryption such as steganography would be much more useful; but would be less accessible.

Ultimately, I think you are alluding to the “unicode” that is the underlying symbolic framework that enables coders to create functions. Unicode is what is going to be the major limiting factor in “coding” encryption; and in that case it is largely why encryption takes the form of numbers and letters instead of using hieroglyphs or other non-alphabetic symbols. Using wingdings as an example for encryption would be useful to confuse a human, but a computer would not see it as any different than letters or numbers.

One of the more novel proposals for encryption is the use of a physical “rock of randomness” that is a 3D printed rock with the encryption embedded in the surface shape of the rock. While the more extreme examples of encryption like the “Rock of Randomness” exist, such types of encryption would be inaccessible to the average user and effectively would be too much encryption for most information exchanges. Rock of Randomness

4 Likes
35

Discussion Summary.

Tags
Security, Network, and Game theory.

About Summary

  • The researchers explore flash loans, how they work, which platforms provide this service and their overall impact on the defi ecosystem.

  • They identify four significant applications (arbitrage, wash trading, flash liquidation, and collateral swap) by studying over 76,000 transactions.

  • Flash loans open up opportunities for financial activities that were previously unavailable without access to large amounts of capital. They are growing in popularity.

Unresolved questions.

The question asked was about the implementation of the proposed solution to the quantum attack, what are your thoughts about the mentioned solution?

Points of disagreement.

  • Discrepancies between two papers - After highlighting the disparity in the number of queries that can lead to a quantum attack.
  • @zubepaul also asked, “Are these potential discrepancies due to developments that have occurred in the last year, or are these analyses simply looking at different types of attacks; some that Bitcoin might be resistant to and others that it might be vulnerable to”?
    To view disagreements and engage with the post, click the link: Discussion Post on PQC - Quantum Vulnerabilities of Blockchains.

Offered solutions.

  • Solutions to Quantum vulnerability gap
  1. This gap between search time and settlement time” is the gap the attacker would have to close to have their chain have the proper hashed sequence to overtake the “honest” chain. That would take roughly three search rounds, or currently 30ish minutes. This assumes the attacker can sustain the attack for that long, which is the limitation on the attacker; their capacity to have enough energy to sustain the attack over time.
  2. One of the most viable proposed solutions to this existential threat is to create a “leaderless” system in which the round is never initiated by the same validator or set of nodes: Scalable and Probabilistic Leaderless BFT Consensus through Metastability. View the full discussion via this link:Discussion Post on PQC - Quantum Vulnerabilities of Blockchains - #12 by Larry_Bates
  • Practiced solutions
  1. Dynamic AI models can calculate the fraud risk of pending transactions at any time before they are validated. These models can calculate adversaries’ potential profits for each threat vector, resulting in the possibility of any transaction being fraudulent. Insurance products can be designed to protect against the risk of fraud in pending transactions.
  2. Consensus rule: Effective incentive design principles can be used to formulate changes in consensus rules, such as applying a markup on p2pk transaction fees and reusing p2pkh wallets. This would encourage users to adopt safer behavior.
  3. Efforts are being made to add cryptographic algorithms that are very resistant to quantum computer attacks to the blockchain infrastructures that exist today. Based on computational problems that are known to be extremely challenging for quantum computers to solve using either Shor’s algorithm or Grover’s method, these post-quantum algorithms were developed. To view the full post use this link: Discussion Post on PQC - Quantum Vulnerabilities of Blockchains - #27 by WaterLily

Points of consensus.

Identification of consequences.

  • At present, not very many digital forms of money have made the most vital moves toward becoming quantum-secure. Most digital forms of money don’t for even a moment recognize this issue in their guides. To appropriately get the fate of cryptographic forms of money I accept that center improvement groups ought to become educated about the dangers, devise a movement plan, and consolidate it in their guide. Acting presently will take into consideration sufficient readiness and smooth progress. I think we fail to act on time, rushing into solutions when the threat becomes more imminent, and the chance of implementation errors increases which can have an undesired result.
  • The identified consequence was addressed by @harvesto and @gloriokoba. To view and share your thoughts, click the link: Discussion Post on PQC - Quantum Vulnerabilities of Blockchains - #23 by Henry

Unexplored territory in the discussion.

  • It also analyses Ethereum’s vulnerability. View the full post by clicking on the link: Discussion Post on PQC - Quantum Vulnerabilities of Blockchains - #33 by Never_in_trenches
  • @larrybates brings a strong argument about encryption and its necessity.
  • He states “This also starts to get to the notion of “encryption indicates information of value” thus creating a target by proxy of indicating there is something valuable. The less an attacker “knows” that something is encrypted, the less likely that attacker is to choose that as a target”.
  1. What are your thoughts on this?
  2. Do you agree with the notion?
  3. What do you think about the encryption types being implemented?

Key resources.

For more insight into the discussion refer to any of these websites .

7 Likes
36

Thanks @Harvesto this is an amazing work…
A little contribution, Many current encryption protocols are at risk from quantum computation. A quantum computer that can defeat the crucial cryptography system is predicted to exist very soon, estimatedly by the year (2035). Many of the crucial sub-routines used by blockchain systems are dependent on cryptographic protocols. Quantum attacks can be used against some of these protocols, but not all of them. . .

Independent nodes that oversee the blockchain must come to an agreement before adding newly verified transactions to the ledger. A network can reach agreement through a variety of ways, with Proof-of-Work being the most common (PoW)… I think this is consensus mechanism.

Here’s a question: Many challenges still lie ahead for postquantum cryptography.
@Harvesto. @zube.paul… Future quantum computers might easily defeat current encryption. Researchers have discovered that a promising algorithm created to defend computers from these sophisticated attacks could be compromised in as little as 4 minutes
what’s your take on this?

3 Likes
37

@Harvesto You’ve done a great job in putting up this summary.

In an attempt to answer the research question, I want to add that Bitcoin relies heavily on ECDSA, which exploits the fact that modulo prime multiplication takes linear time, but modulo prime factorization takes exponential time. Or in simpler terms, it’s possible to encrypt but astronomically difficult to decrypt without the key.

Quantum computers, however, can run Shor’s algorithm. This algorithm solves modulo prime factorization in logarithmic time, which is pretty quick in comparison. This enables quantum computers to decrypt ECDSA (and RSA) without the key.
However, at this point, the largest quantum computer is around 49 qubits, and because the qubits aren’t just storage, but the preservation of complex quantum states between all of them, it becomes exponentially difficult to get those qubits to preserve their states long enough. To break a Bitcoin key, a quantum computer would need to have at least 2330 qubits.

That’s going to take time. But what takes less time is to update the Bitcoin codebase to use more bits for encryption, or to use an asymmetrical algorithm that doesn’t give quantum computers any advantage.

1 Like
39

@Harvesto nice summary you got there ………

Asymmetric encryption can be broken by a sufficiently powerful quantum computer if the public key is known. Overall, symmetric encryption and hashing are secure against intrusion.

So let’s examine that in more detail.

Many cryptocurrencies employ asymmetric encryption; one good example is bitcoin, which makes use of the elliptic curve.
Really, blockchain itself doesn’t. To chain blocks together, it commonly employs hashes, but that’s about it.

therefore, yes. But what about the risk if you actually meant Bitcoin?

The wallet address is the hash of the public key when it comes to BTC, and as was already mentioned, hashes are not subject to QC attack. However, you must upload the entire public key when SPENDING from a wallet address. At that moment, a hacker might decrypt the key and acquire the address’s private key. Although it won’t be quick, they can still complete the task; let’s use six hours as an example.
Therefore, if you withdraw money from a wallet, you must spend it all within six hours. It is actually simpler to withdraw the entire amount in a single transaction and transfer the remaining funds to a NEW wallet that has not yet been compromised.

Therefore, until public keys are included, QCs pose little to no threat to cryptocurrencies and pose none at all to blockchains.
However, hash chaining is not used in every blockchain. It is entirely feasible to chain blocks in a different way, and that method might even employ digital signatures similar to those used in bitcoin transactions. Such chains will have to switch to post-quantum asymmetric techniques (some of which are now undergoing standardization) and probably re-sign all those historical blocks in order to circumvent this (which sounds like a lot of work, but honestly, it would take about a minute per year of block data to be re-signed)

2 Likes
40

You’re welcome @Amazingdez

And thanks for your contribution.

My take on your question can be seen in the earlier threads but let me reiterate.

Yes, there is a looming threat of quantum computers that can break cryptographic signatures and find hashes in minutes… But that reality is theoretical and still in the future.

Quantum computing is developing quickly, and the threats are real, but the resources required to break encryptions - the blockchain in this context - will be considerable. I also believe that while a single encryption standard can be broken with near-future quantum computing, it would be impractical to break (or try to compromise) a whole network

2 Likes
41

@Amazingdez It is true that many current encryption protocols are at risk from quantum computation, and it is possible that a quantum computer capable of defeating these protocols may be developed in the future. However, it is important to note that the development of practical quantum computers is still in the early stages, and it is not clear when they will become widely available or how they will be used. As a result, it is not necessarily a pressing concern at this time.

In the meantime, it is important to continue researching and developing post-quantum cryptographic algorithms as a precautionary measure. It is also important to consider the use of alternative consensus mechanisms in blockchain systems that may be more resistant to quantum attacks.

Proof-of-Work (PoW) is a commonly used consensus mechanism in blockchain systems, but it is not the only one. There are other consensus mechanisms, such as Proof-of-Stake (PoS) and Delegated Proof-of-Stake (DPoS), that do not rely on cryptographic protocols and may be more resistant to quantum attacks. It is important for blockchain developers to carefully consider the security and resilience of the consensus mechanism they choose for their systems.

As I mentioned earlier, many current encryption protocols are at risk from quantum computation, and it is possible that a quantum computer capable of defeating these protocols may be developed in the future. However, the development of practical quantum computers is still in the early stages, and it is not clear when they will become widely available or how they will be used. As a result, it is not necessarily a pressing concern at this time.

In the meantime, it is important for researchers and developers to continue working on post-quantum cryptographic algorithms as a precautionary measure. It is also important for blockchain developers to consider the use of alternative consensus mechanisms that may be more resistant to quantum attacks.

However, It is important to note that the security and resilience of any cryptographic or consensus mechanism will depend on a variety of factors, including the specific algorithms and protocols used, the implementation of those algorithms and protocols, and the overall security of the system in which they are used. Ensuring the security of a system requires a combination of strong cryptographic protocols, effective implementation, and ongoing monitoring and maintenance.

1 Like
42

@zube.paul It is possible that the discrepancies in the analysis of quantum vulnerabilities in Bitcoin could be due to different assumptions or approaches used in the different studies. For example, the study you referenced focused on the resistance of the blockchain backbone protocol to a quantum attacker, while the previous discussion focused on the potential for a quantum computer to execute Shor’s algorithm and break the encryption used by Bitcoin within a certain timeframe.

It is important to note that the security of any cryptographic or consensus mechanism will depend on a variety of factors, including the specific algorithms and protocols used, the implementation of those algorithms and protocols, and the overall security of the system in which they are used. It is also possible that the security of a system may vary depending on the type of attack being considered and the assumptions made about the capabilities and resources of the attacker.

As a result, it is important to consider the security of a system from multiple angles and to continually assess and monitor the security of cryptographic and consensus mechanisms as technology and threats evolve.

Furthermore, Quantum computers have the potential to significantly increase the speed and power of certain computing tasks, including breaking some of the encryption algorithms that are currently used to secure data. This has led to a lot of research into post-quantum cryptography, which refers to cryptographic methods that are resistant to attacks by quantum computers.

One of the challenges in developing post-quantum cryptography is that it is difficult to predict exactly how powerful future quantum computers will be and what kinds of attacks they will be capable of. As a result, it is difficult to design cryptographic algorithms that are completely resistant to all possible attacks by future quantum computers.

In addition, it is important to note that the development of practical quantum computers is still in the early stages, and it is not clear when they will become widely available or how they will be used. As a result, it is important to continue researching and developing post-quantum cryptographic algorithms as a precautionary measure, but it is not necessarily a pressing concern at this time.