Quantum Computers META THREAD Defacto STICKY

[jubalix]

STICKY

This is a meta thread to collapse all quantum threads into one access point
If you have resources, post or pm with a link

Intro
I have been reading up a bit on Quantum Computers....It seems at least plausible that a QC with enough Qbits will just be fed a representation of a public key and settle out into the lowest state which will be the private key....

Sooner than later we need quantum proof tech....lamport sigs anyone? (apparently no good according to Mod, but Mod now says good..see thread...indeterminate mod?)

EDIT 1:  So a n qubit QC can solve roughly a 2^N problem..........is kinda mind blowing......if it works....
EDIT 2: If BTC does this sooner, it will be a massive pro of BTC uptake, as we would be one the first and currently only banking system that is QC ready. (apparently some Swiss banks are already doing this)

LINKS
Overview (1 qbit computer appears to have been verifiable made)
http://www.youtube.com/watch?v=cugu4iW4W54


Other Threads
Topic: Why is Bitcoin safe against a quantum computer?
https://bitcointalk.org/index.php?topic=153302.0

Topic: What does Quantum Computing mean for Bitcoin?
https://bitcointalk.org/index.php?topic=3008.80

Topic: 512-qubit Quantum Computer acquired, is bitcoin doomed?
https://bitcointalk.org/index.php?topic=240410.0


Papers/Resources
http://arxiv.org/pdf/quant-ph/0407095
http://arxiv.org/pdf/quant-ph/0301141v2.pdf
http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Quantum_computing_attacks
http://en.wikipedia.org/wiki/Post-quantum_cryptography



Organisations funding/building QC's
http://www.dwavesys.com/en/pressreleases.html

http://www.iqt.org/

http://en.wikipedia.org/wiki/In-Q-Tel

Possible Solutions
http://en.wikipedia.org/wiki/Symmetric_cipher
http://en.wikipedia.org/wiki/Quantum_key_distribution#Quantum_Key_Distribution_Networks
http://eprint.iacr.org/2008/349.pdf

[Come-from-Beyond]

I think sooner than later we need quantum proof tech....lamport sigs anyone???

Follow the link in my signature and u'll get to a QC-resistant cryptocurrency.

[jubalix]

I think sooner than later we need quantum proof tech....lamport sigs anyone???

Follow the link in my signature and u'll get to a QC-resistant cryptocurrency.

im not sure about this

"Anyone who is familiar with Bitcoin technical details knows that most of its settings are carved in stone. A block solution takes 10 minutes in average to find, a block reward is 50 BTC (25 BTC in the future), the difficulty is changed every 2016th block in 1/4x-4x range. All these rules won't be, likely, changed, because it's necessary to make the majority of bitcoiners to accept changes which seems to be impossible. If Satoshi made mistakes in Bitcoin parameters noone will correct them.

Unlike Bitcoin, Qubic is designed a way that allows any qubicker to change any settings of their own providers. Reward for new transactions, qubic transformation delay, quorum percentage - all these parameters are easily changable. Noone needs to ask the others to set a particular parameter. Of course, changes made by a few qubickers won't affect functionality of the Qubic network much, but if a rhetorically talented person manages to convince a considerable part of provider owners to use particular values of the parameters, (s)he can change behavior of the whole network. This phenomenon brings back ancient traditions when orators were more powerful than generals or businessmen. It's not necessary to be a tech savvy person to be an influential one in the Qubic world.

Read more: http://qubic.boards.net/index.cgi?board=theconcept&action=display&thread=5#ixzz2R7BHTjv2"

I thought that if 51%  of miner adopted a client change eg 50 millcoins that would then happen

[Come-from-Beyond]

I thought that if 51%  of miner adopted a client change eg 50 millcoins that would then happen

U should count non-mining bitcoiners as well. This seems to be very hard.

[charleshoskinson]

Shor's algorithm applies to RSA and DLP. I'm not currently aware of an attack using a quantum computer for ECDSA. I'll email peter and post his response here.

[Come-from-Beyond]

Shor's algorithm applies to RSA and DLP. I'm not currently aware of an attack using a quantum computer for ECDSA. I'll email peter and post his response here.

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Quantum_computing_attacks

[charleshoskinson]

The citation is wrong on wikipedia, but yes you are apparently correct. A 1000 Qbit computer would be sufficient to break a 160 bit EC key. http://arxiv.org/pdf/quant-ph/0301141v2.pdf That's a terrifying thought.

[TierNolan]

I thought that if 51%  of miner adopted a client change eg 50 millcoins that would then happen

No, the 51% attack is to reverse transactions.

If I send a coin to you and then later send it to someone else.  Who owns the coin?  Encryption can't tell you, you need to know which transaction happened first.

That is what the hashing is for, it locks in transaction ordering.

Nobody can spend your coins but you, unless they break the encryption.  It doesn't matter how much hashing power someone has.

However, with 51% of the hashing power, they can "rewind" the clock so the coin never belonged to you in the first place.

[gglon]

http://arxiv.org/pdf/quant-ph/0301141v2.pdf

This is for prime fields
And this is for curves over binary fields in ECC:  http://arxiv.org/pdf/quant-ph/0407095

[charleshoskinson]

Considering this is a thread about quantum computers and apparently they can break the encryption of the Bitcoin. Coin theft is now a legitimate topic. You guys hear about D-Wave?

[gglon]

Considering this is a thread about quantum computers and apparently they can break the encryption of the Bitcoin. Coin theft is now a legitimate topic. You guys hear about D-Wave?

D-wave runs only one specialized quantum optimization algorithm. So it is not universal quantum computer. It can't run Grover's algorithm which potentially may make hashing easier, but probably not much, as Grover's is not big speedup. And it definitely will never run Shor's that with enough qubits can break RSA and ECC with proper modifications.   

[charleshoskinson]

This is for prime fields
And this is for curves over binary fields in ECC:  http://arxiv.org/pdf/quant-ph/0407095

A prime field implementation is enough to convince me that it is possible in binary fields

But this is awesome:

2m = +7[logm] + 7 + H Qbits

[charleshoskinson]

D-Wave is being funded by the CIA. I really doubt they would have made an investment if there wasn't something in the product pipeline that could run Shor's Algorithm

You seem to have a great deal of experiment with Quantum computers. Are you a physicist?

[gglon]

Last year post-graduate physics student, thesis is in the field of quantum information. So i'm not an expert 

[charleshoskinson]

I'm an additive and analytic number theorist who moved into fully homomorphic encryption. Funny how the Bitcoin community attracts us weirdos   

[madmadmax]

Wouldn't the evolution of bitcoin take it to use different algorithms such as bcrypt by then? I name bcrypt specifically because it can be adjusted as faster computers are available down the road.

[charleshoskinson]

That goes on the hardfork wishlist. They should also change the proof of work to make it immune to ASICs.

[behindtext]

I'm an additive and analytic number theorist who moved into fully homomorphic encryption. Funny how the Bitcoin community attracts us weirdos   

ex-theoretical physics guy here

on the topic of vulnerability of ecdsa keypairs - i think it's absolutely a real threat. gglon does make the fair point that d-wave technology is not a proper universal quantum computer and can only be applied to a subset of quantum computing problems due to the way they keep the quantum systems isolated. back in 2001 there were ppl talking about certain condensed matter systems acting as universal quantum computers, who knows how far that got.

the best you can do with ecdsa is to keep the amount of btc at a given address low, which depends on the BTC/USD rate. if you make a particular address worthwhile to attack, it could very well be brute forced by a few thousand qubit QC. PQ crypto for the PKI would obviously help this.

[charleshoskinson]

http://www.dwavesys.com/en/pressreleases.html

http://www.iqt.org/

http://en.wikipedia.org/wiki/In-Q-Tel

[John (John K.)]

No, not yet another topic on quantum computers and bitcoin... A sticky should be placed at the newbie section covering this topic with its popularity.