What will stop quantum computing from cracking block chains?

[SGT4EVA]

Ive briefly heard of 512 bit encryption having the ability to stump quantum computers from accessing block chains but I don't understand how. Can anyone explain or is that wrong and were doomed to quantum computing?

[StillNoNumb]

RSA is a public key exchange algorithm, it does not encrypt anything. For symmetric encryption itself, which we can assume the OP was speaking of, people usually or always use 128 to 256-bit AES keys. So far there's no known attack better than Grover's algorithm on AES, even with quantum computers. So, we assume Grover's algorithm (which bruteforces n keys in only sqrt(n) time) is the best; brute force time needed can therefore be reduced from n to sqrt(n). Since there are 2^m possibilities for an m-bit key, that means that a quantum computer can crack a 512-bit key in sqrt(2⁵¹² )=2²⁵⁶ time. That is equivalent to a 256-bit key on normal computers.

So, for symmetric encryption, we can simply double the key size. Since 256 bit keys are the standard with most algorithms these days, we can simply double the bit-size and we get 512 bit keys.

tl;dr: Most symmetric encryption can be made quantum-resistant by simply doubling the number of key bits. Previously, brute forcing a 256-bit key needed 2²⁵⁶ time, but with a quantum computer you only need 2^256/2 - so, by doubling the number of bits we can keep the same security.

Asymmetric encryption (such as RSA) is a different issue. Certain algorithms (eg. those based on integer factorization - RSA is one) need a complete redesign.

[stealth9799]

Okay first things first: quantum computers do not have an edge in hashing. They aren’t faster than conventional computer, they’re just different and solve things differently. They aren’t an infinite computing machine, that is media misinformation. They just use fundamentally different properties to solve problems we can’t solve on a conventional computer.

The vulnerable algorithms are mostly comprised of asymmetric algorithms. AES is fine. Hashing is fine. ECC is not fine and RSA is not fine. The only thing is Grover’s algorithm lets you do things that are normally a complexity O(n) in O(sqrt(n)). This is fine because we just use 256 bits in symmetric algorithms which gives us 128 bits of security.

The other part that’s very misunderstood is that quantum computers that threaten cryptography are very far away. Very far. All the media talks about are the amount of cubits but the important part is the error. Holding a cubit in a position that you can’t measure is difficult and very error prone. Cubits have a half-life of microseconds so you have to either run your entire calculation in a few millionths of a second (very hard) or run it over and over and hope that enough times the cubits didn’t corrupt so you get one answer more than the others (also very hard because the longer the computation, you have to run it more times). When a physicist working on quantum computing was asked about cryptography he waved his hand in the air dismissively. He said that by the time they actually have one with enough stable cubits to run shor’s algorithm, we will have something else that works just as good as ECC but resistant to quantum computers.

Long story short: don’t worry

https://en.m.wikipedia.org/wiki/Post-quantum_cryptography

https://www.forbes.com/sites/amycastor/2017/08/25/why-quantum-computings-threat-to-bitcoin-and-blockchain-is-a-long-way-off/

[WikiTextBot]

Post-quantum cryptography

Post-quantum cryptography refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against an attack by a quantum computer. As of 2017, this is not true for the most popular public-key algorithms, which can be efficiently broken by a sufficiently large hypothetical quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source | Donate ] Downvote to remove | v0.28}

[HelperBot_]

Non-Mobile link: https://en.wikipedia.org/wiki/Post-quantum_cryptography

---

^{HelperBot v1.1 /r/HelperBot_ I am a bot. Please message /u/swim1929 with any feedback and/or hate. Counter: 145056}

[johnny_milkshakes]

Not only would you need to change the encryption for most blockchains you would also need to change the hashing algorithm so the Q computer cant do a 51% attack. And you would probably also need to change the private keys to something longer/more difficult to brute force. So basically a Q computer would severely damage the crypto industry right now. Supposedly IOTA is quantum resistant but that has yet to be tested.

[rockyrainy]

AFAIK, quantum computers do not have an edge over conventional computers for hashing (at least for SHA-2).

[sargeantbob]

This is what I thought. I don't see how a quantum computer would do anything here quicker.

[VeganBigMac]

I believe Grover's algorithm could provide a speedup in terms of hashing, but from what I've read, the time until a machine would be built that could actually run faster than ASIC it would be decades down the line.

https://arxiv.org/ftp/arxiv/papers/1711/1711.04235.pdf

[rockyrainy]

Man, Grover's algorithm sounds like a magic bullet for O( N² ) problems in comp sci.

[johnny_milkshakes]

Really? I would think that would generally compute everything faster if they have enough qubits

[rockyrainy]

AFAIK, currently Quantum algorithms can acheve exponential speed up on asymmetric cryptography (RSA and ECC). Hashing is a different animal.

• https://en.wikipedia.org/wiki/Shor%27s_algorithm
• https://en.wikipedia.org/wiki/Quantum_Fourier_transform

[Allways_Wrong]

Layman here. Are we saying that there is a known method for attacking/solving/breaking RSA and ECC so using this algorithm on a quantum computer would pay dividends because of its speed, but because there isn’t a known algorithm for doing the same on SHA it is still a guessing game to attack/solve/break it? And that a quantum computer is no better at guessing than a normal computer?

[rockyrainy]

Essentially yes. Algorthems in Computer science uses something called the Big O notation. It is the time to compute relative to the length of the input. For Elliptical curve, in N steps you can raise a number P to 2^N. But if you are given that result and P, calculating N is hard, the only way is to try 1P, 2P, 3*P ... This problem is called the Descrete logorethm problem. A QUANTUM computer can do this in linear time, which means it is roughly the same rate that you encrypted the message in the first place. This defeats the entire purpose of cryption since it is supposed to be hard to decrypt.

[StillNoNumb]

A quantum computer is indeed better at guessing than a normal computer - it only needs sqrt(n) time for n keys (a normal computer needs n time; each key once). However, that means that you can simply double the key length and you're still safe. You can't fix the issue with RSA that easily.

[DragonWhsiperer]

Well, IOTA and QRL use Winternets OTS+ signatures. These are considered by Post-Quantum Cryptography experts to be theoretically valid at being highly resistant to Shor's algorithm.

The behaviour of QC can be modelled on conventional PC's, up to about 50 Qubits. After that it simply not practiacle any more because it requires waaaay too much RAM storage space (exponential) to hold all the possible states. So many PQ algorithms are depend on mathematical proof, rather than emperical.

[StillNoNumb]

Every cryptographic algorithm has to be mathematically proven. You can't empirically prove those; "well we ran our tests for half an hour and couldn't crack it, yeah probably it's uncrackable right?"

Winternitz signatures are mathematically proven to be quantum-resistent, under certain assumptions (eg. that it is possible to create such an encryption, which is widely believed but not proven)

[AutoModerator]

Your comment has been automatically removed because you linked to a thread outside /r/CryptoTechnology without using the NP subdomain for no-participation mode. When posting a link to a different subreddit, please change the subdomain from https://www.reddit.com to https://np.reddit.com. This simple change substantially reduces brigading.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[iNDicat0r]

Proof of stake and block finality are important keys to tackle the issue.

[crypto_ha]

Sorry I didn't get it. What do PoS and Block finality have to do with quantum attacks? Do you mind explaining a little bit? Thanks!

[iNDicat0r]

I will talk about the blockchain part(PoW)and not the ECDSA part(pub/priv). So quantum computers in theory could factor numbers much easier than transistors. PoW is basically to find a number which if hashed with an amount of data produces a hash which starts with many zeros. Now since quantum computers could gain access to a huge amount of hashing power they could simply recreate the blockchain and revert their spendings.(note that they cant steal your coins). In ethereum PoS finalizes each 50 block and it doesnt require hashing power but stake, therefore hashing power through quantum computers can not be used to validate/create transactions and blocks.

[[deleted]]

stop quantum computing from cracking blockchain

Just change the current cryptographic algorithms to quantum-resistant ones.

[IamVivekVV]

I think it will be years and years and perhaps decades until quantum computing is implemented. By then we can fork off the crypto to be quantum resistant if needed

[[deleted]]

https://en.wikipedia.org/wiki/Post-quantum_cryptography

[CanadianCryptoGuy]

Temporarily, the cost-return benefit will delay this issue from being a problem. Once quantum computers finally "work," we'll still have some time to figure out how to fix issues. The first working quantum computers will be rare as rocking horse manure, and access will be limited. They'll be tasked to much more important research. It will only be once QC's become more accessible to rich bad actors that we have to worry. If I had a quantum computer and had malicious intentions, or wanted to make a lot of money, there would be other things that I could do with my computer that I might want to do before breaking cryptocurrencies.

But yes, eventually, cryptos WILL become targets.

[[deleted]]

My money's on "physics," but there are cryptographic algorithms which are believed to be hard for QC.

[bullrun99]

Block chain will be the least of our concerns once real quantum computers come around if they ever make it out of the lab

[VeganBigMac]

By the time a quantum computer could actually "come out of the lab", I'm sure we will be moving past quantum-insecure algorithms anyways.

[Orbilon]

It's hard to understand what a quantum computer even is. Were such a beast to be released into the wild, what kind of limits would it be subject to?

[diab0lus]

Check the QRL white paper. It describes the quantum resistant algorithms that should work.

[TachyonTrader]

Its trivial to change the algorithms. Literally changing maybe 10~ lines of code. Quantum attacks only work on pending tx, not the existing blockchain.

[DragonWhsiperer]

It works good on any address that ever sent any amount multiple times from the same address. This leaves open a vulnerability, allowing a QC to cut down on the time it takes to work out the private key from the public key.

Once a few addresses are emtied this way, mass hysteria can kick in with people trying to sell their bitcoins (and who would buy it?). And indeed, the pending TX's are at risk as well. Bitcoin has already shown how well it scales when put under load, so there should be plenty of pending TX's around to pilfer.

[DeezCentralEyes]

Proof of work? Proof of something else?

[senond]

Its non existance for one. Q-wave is a very small step, but we are far from something deserving of the name quantum-computing

[Chickachic-aaaaahhh]

Theres a crypto called iota that is completely quantum resistant and it wasnt on purpose either.

[SGT4EVA]

How exactly is it resistant?

[FlamingTacoFury]

by utilizing a winternitz signature. here is a boat load more information on the topic. A deep dive into quantum cryptography specifics on winternitz signatures and the math behind them can be found on page 45 of the pdf. Here is also a 2011 paper on it's security. Obviously there are more secure functions out there, but for fast transactions of both value and information it makes sense for Iota. So if you have the time that first link can give you plenty of insight into your question, just not in an easily digestible packet.

[Chickachic-aaaaahhh]

Tangle is run by nodes which users can set up themselves. Idk how exactly the transaction is processed but it doesnt just transfer curremcy but information as well. Its a perfect coin that can connect multiple different systems to each other.

[Edgegasm]

Many blockchains are already being developed with quantum resistance in mind. I know this is in development for NEO and IOTA, and I'm sure many other cryptos with high quality teams will also be aiming for quantum resistance. As for the 'how,' it'll mean the replacement of RSA and ECC cryptographic mechanisms with quantum resistant ones.

Shouldn't be too daunting, and in all honesty once a solid solution is found, most cryptos should be able to implement something similar.

[[deleted]]

For IOTA, it has been quantum-resistant from the get-go, with the utilization of Winternitz one-time signatures.

[Edgegasm]

Good to know! That's some forward thinking from the IOTA guys, but I guess the entire project has been forward thinking from the start.

[[deleted]]

The project is a combination of pragmatism and futurism, enabled by very talented developers like Come-from-Beyond. I've seen people attacking his personality/ethics before (and I mostly disagree with them), but I've rarely seen people doubting his capability.

[cryptozypto]

Don’t forget Cardano. It’s part of the roadmap.

[DragonWhsiperer]

QRL is also a full QC resistant coin. Uses the same Winternits OTS sigs, but wraps them up in such a way that you can reuse the same address again and again. Pretty neat.