Bitcoin Forum

Most of you are already aware of the NSA's recent post (https://www.nsa.gov/ia/programs/suiteb_cryptography/) containing such troubling phrases as-  
 
 (emphasis mine)  
  
There are many possible interpretations of these statements, but it is clear that the world's leading expert on cryptography just put out a gentle (but very public) warning that ECC may not be as secure as we believe.  This being the case, which cryptocurrencies might be affected by this?  Bitcoin?  Cryptonotes like Monero?  Ethereum?  
  
Will those blockchains eventually have to radically change their encryption algorithms?  Are there any steps that should be taken now to preserve privacy and legitimacy before this happens?  
  

Old argument I believe. Quantum computers breaking the cryptography of binary computing only leads to the use of quantum cryptography. Cat and mouse.

Every single cryptocurrency would be affected. They are all based off of bitcoin which uses ECC. The obvious solution is to switch to a quantum resistant algorithm for generating private and public keys. I do not know if one exists yet.

However, if you use bitcoin as it should be without reusing addresses, then the argument that ECC is broken is not as valid. In order for ECC to be broken by quantum computers, the public key needs to be known. The public key is only known when a transaction sends Bitcoin out of an address. Thus, if each address is only used to send one transaction which spends everything to other newly generated addresses, then everything will be fine since even with the public key known, there is nothing to steal.
  
Just to correct you, cryptocurrences DO NOT USE ENCRYPTION. The only crypto part are for key generation and signing, and the hashing of data for txids and blocks. Hashes are considered quantum secure. The security of hashes can be easily increased by doubling the bit length to have the same security we have now, e.g. SHA512 is as secure as SHA256 when quantum computers come around.

Let's not put all cryptocurrencies into the same basket, at least one is made to be quantum-resistant.



You forgot to add that depending on characteristics of the quantum computer it can find private key and issue another transaction with higher fee before legit transaction is included into the blockchain.

If I recall correctly, there are currently no quantum computers available. A lot of research and development is put in it though.

But does this mean that quantum computers can brute force any address? If so, is there any way we can move bitcoin protocol to quantum computing level?

Frist cpu then gpu then asics next quantum computers?

A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.

 
 
If should be noted that if a Quantum Computer exists, it is beyond classified.... I do a *lot* of digging on the internet and the dark web and have never heard of a verified one.  The closest we have is D-Wave system's Quantum Annealing computer which is not the same thing. 
 
I have read research of scientists entangling 3 particles, a precursor to the first 4-qubit true quantum computer, but I've never read anything about 4 particles being successfully entangled.  Anyone can feel free to correct me, but wouldn't we need to be able to entangle 128 or 256 particles in a small area to create a "true" quantum computer capable of doing damage to modern cryptography?

So these guys are stupid you think - https://www.nsa.gov/ia/programs/suiteb_cryptography/ ?

The fact that I read through most of that link, and double checked it before realizing it was the exact same link I posted initially 6x proves I'm too drunk to be commenting on this thread until at least 24 hours from now.

A quantum computer wouldn't be doing that to a chain using a hash function that uses quantum cryptography, or is that actually your assertion? That quantum computing is a magical panacea?

If such a technology would exist right now I do think that BTC technology would be the least to be exploited: i.e. imagine what such a mess this quantum computers could create to the entire internet/developed world. There would be nothing secure.
Ok, maybe I'm going too sci-fi now but, yes, I think BTC will be the last thing to worry about

that's an interesting argument, forgot that the bitcoin network is the most secure on the planet at this moment. That means Bye bye every commercial bank on this planet. Bankers should definitely rethink their "secure" systems.

Relevant reading from Koblitz and Menezes: https://eprint.iacr.org/2015/1018.pdf

secp256k1 is a Koblitz curve.

Abstract. In August 2015 the U.S. National Security Agency (NSA)
released a major policy statement on the need for post-quantum cryptography
(PQC). This announcement will be a great stimulus to the
development, standardization, and commercialization of new quantumsafe
algorithms. However, certain peculiarities in the wording and timing
of the statement have puzzled many people and given rise to much
speculation concerning the NSA, elliptic curve cryptography (ECC), and
quantum-safe cryptography. Our purpose is to attempt to evaluate some
of the theories that have been proposed.

One possibility:

5.5. The NSA has a political need to distance itself from ECC.
There were some peculiarities in the release of the August 2015 statement
about preparing for post-quantum crypto. Normally all of the big corporations
that do cryptographic work for the U.S. government would have been
given some advance notice, but this was not done. Even more surprising,
the NIST people were not asked about it, and even researchers in IAD were
caught by surprise. It seems that whoever at the NSA prepared the release
did so with minimal feedback from experts, and that includes their own
internal experts.

This suggests that the main considerations might not have been technical
at all, but rather Agency-specific — that is, related to the difficult situation
the NSA was in following the Snowden leaks. The loss of trust and credibility
from the scandal about Dual EC DRBG was so great that the NSA might
have anticipated that anything further it said about ECC standards would
be mistrusted. The NSA might have felt that the quickest way to recover
from the blow to its reputation would be to get a “clean slate” by abandoning
its former role as promoters of ECC and moving ahead with the transition
to post-quantum cryptography much earlier than it otherwise would have.

 
 
Oh wow, an actual hardcore mathematician in the wild!  I know I promised not to post anymore until I sobered up, but I would love to hear your opinion on whether moving towards abelian surface cryptography is feasible at all, and whether it would provide any further defense against quantum computers: 
 

My original proposal: https://www.reddit.com/r/math/comments/3451ob/is_it_feasibleworthwhile_to_take_elliptic_curve/ 
 
Shit that's above my head: 
 
http://www.hyperelliptic.org/tanja/conf/ECC08/slides/Peter-Stevenhagen.pdf 
http://research.microsoft.com/pubs/249337/abelian.pdf 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.464.9485

From http://188.138.57.93/tangle.pdf:


Obviously, Bitcoin can't migrate to quantum PoW, miners won't get such hardware in time.

Come-from-Beyond,
so let's assume you have a quantum computer that you can use to mine BTC.
Can you use it to disrupt the mining process or not?

I don't understand because before you said that such a computer could

and then quoting that pdf you said

So, going back to what I stated at the beginning of this post, if you have a quantum computer could you do that right now or not?

That pdf is a good read, I guess we just have to jump boats to PoS or other protocol before quantum computers hit the mining scene.
But then again how would we secure other protocols if quantum computers could just brute force them?

Yes, with a QC you can invalidate last 1000 blocks, generate 20000 empty blocks and stop mining leaving the others with 20-year block times.

For easy reference, [7] from the above linked paper can be found here -> https://dl.acm.org/citation.cfm?doid=261342.261346

Ok, that is clear.
Coming back to wait I said at the beginning I would be really afraid if such a thing exists now since it could disrupt the functioning of everything we rely on nowadays, and as I said, bitcoin would be our last concern.
crazy

This is ostrich policy. Banks won't be attacked by agencies that will get QCs.

I'm not talking about banks man. I'm worried about public transportations, people's sensitive data and so forth.
You could say I'm being paranoid a bit. But, again, if such a thing would be used for the bad you would not care about your BTC wallet.

Really? Can you back that up with maybe some research?

Last I checked, the only thing that makes quantum computers more efffective at hashing is grover's algorithm, which practically reduces the bit length by half. For the same security, the bit length can just be doubled, so using SHA512 instead of SHA256 on a quantum computer is the same as SHA256 on a classical computer.

Check the quote from the whitepaper upthread. In layman terms, SHA512 won't help, because at current difficulty Bitcoin operates only on 68 bits, the other zillion bits are completely irrelevant.

I don't see where it says where it uses 68 bits. It says that it must search through on average 2^68 nonces. From what I understand, this does not mean that it is only 68 bits and that the number of nonces to search through will increase with a higher difficulty.

It means exactly this - effective hash width is 68 bits. Sorry, can't provide formal proof, just google around.

The effective bit length is actually 136 bits since good algorithms like SHA 256 will require 2^(bit length/2) computations to brute force a single hash. This effective bit length will also change as the difficulty increases because miners will need to search through more nonces when there is a higher difficulty, so the bitcoin network would adjust to a quantum miner so blocks would still come out at around 10 minutes per block. So if we double the bit length by switching to SHA512, the effective bit length will also double so this will essentially make the quantum miners not anymore powerful than classical miners.

One Time Pad without re-use.

Frankly saying, it looks like you randomly put N, N/2 and 2N into different places trying to guess the correct formula. Maybe read the quoted whitepaper first? When the difficulty goes up quantum computers will get even a bigger advantage because of increased leverage (from 17 billion to trillions).