Topic: Quantum Computing and Bitcoin - page 2. (Read 1122 times)

it is not about SHA256, it is not an encryption mechanism and QC has nothing to do with it and there will be no technology ever capable to do anything about it!
QC is good at solving a row of mathematical problems much faster than conventional computers and it includes ECDSA which is Elliptic Curve Digital Signature Algorithm used by bitcoin and many other institutions and people as well as banks and anybody who is involved in e-commerce and needs signing transactions or documents digitally.

That said, you are right, QC is not just about bitcoin and is a more general threat to financial and legal systems and security of digital sphere. Interestingly, bitcoin would be among the least vulnerable technologies because most systems are open to QC attack in large widows of time while bitcoin public keys are not disclosed (being hashed) and any hypothetical QC attack has to be carried out in like few hours in the worst case! It is the window in which bitcoin keys are disclosed and open to attack but not confirmed yet to become useless.

If now all of the sudden the SHA256 encryption could be decoded that bitcoin being useless would be our least concern as the banks and web pages also use this technology right?

Although that is true. The difficulty would also increase to prevent any issues with quantum computing. The real issue with quantum computers is breaking the current algorithm and not the mining aspect.

A problem with the mining aspect is that quantum computers could push up the difficulty and render the network difficult for those who can't afford quantum computers.

Quantum computing will not destroy Bitcoin. I believe that given enough time and the right amount of preparation we can implement ways of protecting against quantum computers. The biggest concern is QC attacks which later quantum computers should be capable of doing. But by the time that this happens we should of been able to look at the situation and guard against it by changing algorithms and everything. I assure you that there's enough people working on the protection of Bitcoin that a quantum computer will not destroy it. Its true that quantum computers will put much of the security of users at risk and not just in Bitcoin. But technology seems to adapt and balance itself out. Currently we have algorithms which traditional computers cannot break. I expect this to be the same when quantum computers are released.

This is a quote form the Bitcoin wiki: "As of 2016, the largest general-purpose quantum computers have fewer than 10 qubits. Attacking Bitcoin keys would require around 1500 qubits. Humanity currently does not have the technology necessary to create a quantum computer large enough to attack Bitcoin keys. It is not known how quickly this technology will advance; however, cryptography standards such as ECRYPT II tend to say that Bitcoin's 256-bit ECDSA keys are secure until at least 2030-2040."

As you can see from that quote the current quantum computers are no where near being sufficent enough to be a threat to Bitcoin. In fact we are far off it. As you can see they put a deadline on it and say that the ECDSA keys are secure until at least 2030. Which gives us more than enough time to prepare for the development of better quantum computers.

In fact users can guard against quantum computers themselves. By regularly moving their coins around and only using one address. This would prevent any brute force attempts by a quantum computer.

Take a look at Von-Neumann extractor.

The most important point of failure that I see in asymmetric encryption is running a Random Function in key generation stage. providing real randomness is one of the hardest problems that I ever seen - because what you think is random at first sight, in fact carries a hidden pattern inside. so most of the time random number generation is where Cryptanalysis begin their job from.

We should migrate all the sha256 functions to sha-3, that would be the measures to take, but remember, is aquantum computer can break bitcoin, then that's the smaller issue because in that point all the security agencies would be vuln, sha256 is protecting the military  secrets and all the gov important stuf, so, with that power who will fuck bitcoin while he can fuck the world.

face recog., voice recog, any other biometric solutions, especially OTPs - these all - need a centralized system to handle their procedures (to compare users given credentials and broadcast related granted or denied access message to the system) and can not fit in a decentralized project. you can use them in a private blockchain, not those with public access.

NIST is working on a timeline of around 5 to 10 years before publishing recommendations of the best quantum resistant algorithms to apply.
There's a lot of great work already going on and already a range of algorithms to choose from, the question which are the most efficient and reliable and ultimately which get NIST backing and make it into standards.

With regards to timelines, I often hear two opinions, neither of which I have any reason to accept over the other.

The first is that practical quantum computing is still a decade away and so there's time to get this right through NIST. That could very well be true.
The second is that quantum computing is more advanced that is publicly understood and is in part why a certain agency is accelerating the replacement of their Suite B cryptography suite with a new quantum resistant suite.

Whatever the truth, we need to follow standards bodies like NIST and work methodically to get things right.

This is interesting and seems logical solution to me. However, just to point out that sms authentication is not secure and people are working on identity based authentication as an additional security layer. One day instead of using login via facebook or twitter, you might just use login via bitcoin and use your bio metric or identity to autheticate.

It is a new proposal: Attacking RNG by machine learning boosted by QC. Your previous suggestion was taking advantage of a vulnerable RNG to narrowing down the search space and using QC for boosting the process. I am afraid the new attack is unlikely to work, as well.

We have Cryptographically Secure Pseudo Random Number Generators (CSPRNG), that are provably safe against AI techniques including neural networks and machine learning. For instance suppose we are getting closer to machine learning being disruptively boosted by a hypothetical QC machine reasonably cheap and powerful. Wallets would be able to apply a Von Neumann extractor to their systems in case they have not already considered it.

Bottom line: QC is just another technology and technology can't fight mathematics. It is always possible to force cryptographers to use more sophisticated techniques because of significant technological achievements that provide more processing powers, but it is not possible to beat cryptography in the race.

thanks for the paper, my friend.
these sort of encryption algorithms belong to a major family of algorithms that we call them One-Time-Pad:

https://en.wikipedia.org/wiki/One-time_pad

the operator XOR (or MOD when you try to work with ASCII values of characters) is necessary -  not a simple ADD operation. including fibo sequence here doesn't provide a better level of security..

Great question. Made me to think a bit on a possible solution. Below is just my high-level thought without getting into too much of feasibility check.

Quantum computer possesses two major threats to bitcoin Network.

Challenge 1. Quantum computer can rig up blockchain by centralizing its hashing power and

Challenge 2. It can crack to cryptography key and the encryption.

Both are valid security concerns. Something to worry about for sure. But let's understand this basic that it is not just a security threat to bitcoin, but also a security threat to all software's that use encryption see for example it is the threat to all the WhatsApp messages that you send to your friends, it is a threat for you to secure your login credentials for bitcointalk, it is a thread for you as a customer of a bank to prevent your money in the bank account and so on and so forth.

Having established that it is not just a Bitcoin Network security concerned also a security concern for every software that uses encryption technique, let's evaluate two possible solutions to the problem. Once again let me clarify that double two solutions are just my high-level thoughts.

Solution 1.  DAG based blockchain network will grow in future and Proof of Work based blockchain network systems will possibly be eliminated. This might take care of challenge number 1 above

Solution 2. One time password (OTP) or additional security layer to get access to the account will rise and might take care of challenge number 2 above. Two-factor Authentication may become more advanced by the time. Face recognition or voice recognition maybe used along with biometrics in order to get an access to an account in next few years maybe. But this challenge is not hard to overcome. In this manner The Challenge number can be solved.

what about QC on Fibonacci Sequence? (http://www.ijesi.org/papers/Vol(6)9/Version-3/B0609030714.pdf) Scroll down to encryption / decryption?

please keep us posted about any improvement by QC in RNG attacks, Ali. I just googled and found nothing worthy. but found something amazing in these old stuffs:

https://en.wikipedia.org/wiki/Random_number_generator_attack#cite_note-20
https://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/
https://bitcoin.org/en/alert/2013-08-11-android

------------------

now, there is a question. while machine learning could be used in attack to RNG and macine learning could also improve by QC, there should be a chance in doing something real with QC on RNG - just a gesture..

update:
https://en.wikipedia.org/wiki/Quantum_machine_learning

You are taking my post out of context... the word "if" should clue you in. I know that this is nowhere close to feasible now. Perhaps I should have replaced it with the word when to make it more clear?

Now it makes a bit more sense but not enough. Again, it has nothing to do with QC:

If hypothetically, one could find such a vulnerability in the RNG used in a wallet, to be able to "narrow" the search space in brute forcing RIPEMD-160 hash he needs to:
1- 'Guessing' a 'more likely' private key (using the vulnerability in the Random Number Generator),
2- Performing one simple multiplication to compute a public key for it,
3- Generating  ripemd-160 hash of the public key,
4- Praying for a match.

None of the above is QC related.

If a government takes the control of 51%, the rest of miners/users can discuss and, through a consensus, left from that blockchain (or ignore the government manipulation). So this bad guy will have a worthless private bitcoin. Simple like that.

misunderstood. the SHA256 is not broken in output. what I wrote above is about the weakness in providing input for the SHA256 - because of weakness in random number generation. this is much more about vulnerabilities that exist in implementation stages of a secure platform - not the Math behind it. so we need to know how QC could influences in the structure of providing (and predict) input for SHA256 (or any other hash algorithm).

UPDATE:
we all know several online/offline bitcoin address generators that only run random function in javascript / server-side script. better solutions make the user to move her mouse to reach better amount of randomness. as I know we have no control over quality of randomness in bitcoin protocol. hope the paper bellow help:

http://www.mixoftix.net/knowledge_base/security/Key_Generation_with_Verifiable_Randomness.pdf

Wrong. There is no shortcut for sha2 and if it would be ever possible to find such a shortcut the whole bitcoin blockchain security will become void and you don't need to wait for QC to bring it down.