Bitcoin Forum

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

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

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

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

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 (http://arxiv.org/pdf/quant-ph/0301141v2.pdf) That's a terrifying thought.

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.

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

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.   

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

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?

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

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

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.

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

:) 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.

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

http://www.iqt.org/

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

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.

Search on this forum sux. That why u see so many duplicate topics.

Sticky this one

This thread (https://bitcointalk.org/index.php?topic=3008.80) has some very detailed discussion that would be a bit more useful as a sticky, imo.

looks fine but needs a bundle of links at the top

Don't forget this thread - Why is Bitcoin safe against a quantum computer? (https://bitcointalk.org/index.php?topic=153302.0)

PS: Btw, seems Bitcoin is NOT safe.

For a moment I thought this was going to be another speculative pre-order thread  ;D

haha.

quantumfly labs...first qubit comupter......pay now 1024 qbit device by November....

pay 100 BTC to sig address pm me

This thread is borderline off-topic for this sub-forum. Or rather, I think it's off-topic but there isn't a subforum that it would be more on-topic in.

It also begins with a misrepresentation of the expected performance of quantum computers: They are not even theorized to provide an exponential speedup in the general case. (If it did lamport wouldn't be strong against QC either)

There is no way in hell that I'm going to sticky it.

He's not talking about a 51% attack. He is talking about 51% of all miners (well actually, 51% of all hashing power, not necessarily proportional to the individual "miner") switching to a new client with different rules in place. If that happens then the main branch (i.e. longest) of the blockchain will be the one following the new rules. This is essentially what is happening with the block size change on 15th May where most miners will switch to a new set of "rules" (in this case not an explicit rule, but an implementation specific implied rule). The rules of bitcoin are decided by whatever the majority (51%) of the miners agree on.

Adding qubits is not as trivial as adding bits. It can be 2^N problem (i think), so we may never have enough qubits. There was a lot of experimental breakthroughs lately, but still we are very, very far from the goal of creating scalable quantum computer.
Roughly, but for n qubits we need another k times n (k may be quite large) for error correction.
Some Swiss banks have already established quantum key distribution as 2 years test by SwissQuantum ended in 2011 was a success: http://en.wikipedia.org/wiki/Quantum_key_distribution#Quantum_Key_Distribution_Networks (http://en.wikipedia.org/wiki/Quantum_key_distribution#Quantum_Key_Distribution_Networks), so maybe it's not that stupid to think about quantum computers that early. But I think that right now there are many much more important things to do.

Public-key schemes based on Multivariate Quadratic polynomials where claimed to resist quantum computer attacks: http://eprint.iacr.org/2008/349.pdf (http://eprint.iacr.org/2008/349.pdf)

Your call it will just go on anyway!!!!

However, the first youtube link by the Australian Usyd research team (and they have actually made a working 1qbit device) gives a fairly solid view,  as to the expected performance which appears to be a doubleing for every qubit added. So there's that...not sure your claim "its not even thoerized" holds water as clearly that Prof Usyd team are theorizing and a whole lot and more by actually making a qbit chip

In this thread alone there appears to be at least 2 Physics PHD's who are in the filed who give similar views.

But hey its cutting edge tech and will be open to a lot of different views, but it needs to be addressed.





your kinda right on this point in both counts, and this was my initial view as well when I posted, I wrote i wasn't sure this belongs in this sub forum....but it is an issue, and it keeps raising its head....some one else suggested newbs.....I think that this is probably as close as it gets...

well I will cross that out!

Meh.  The world record for quantum computing is 21.  Not 21 qubits, but 21=3*7 at least a few percent of the time.  This was after roughly a decade of work since the previous record of 15=3*5.  But, to be fair, a good chunk of that decade was in making the initial 15=3*5 result actually be a quantum effect.

Then there is the tricky part about building quantum circuits.  Turns out that those get harder the bigger you make them, while classical circuits only get harder at changes of scale.  As in, when we shrink a transistor, we can suddenly put billions of them on a die, instead of millions.  But adding qubits isn't simply a matter of finding physical room for them, they interact, so the difficulty multiplies for each one added.

I suspect that we have at least a couple of decades, minimum, before quantum attacks on ECDSA become a serious threat.  And even if they do, good key hygiene (for example, what the stock client has been doing since day 1) will make the attacks pointless.

**facepalm**

Lamport is fine.

Quantum computation does not give an exponential speedup in the general case. It can not solve arbitrary  problems that take 2^N time on a classical computer.  For general non-linear search (which is _most things_) quantum computation is theorized to give at least and at most a sqrt() speedup,  in other words something that takes 2^N operations on a classical computer takes 2^(N/2) operations on a sufficiently large quantum computer.   This means that e.g. for a hash or block cipher you can double the number of bits and get back to where you started in terms of operation count.

There are some problems like factoring and the related discrete-log problem which can be expressed in a way which has a special periodic structure which has much greater speedup, but this is not usual.  It's why it's believed that RSA and ECDSA will not be strong against large QC's.

All this is predicated on "sufficiently large" QC's which may actually turn out to be physically impossible to construct, e.g. the noise level or coherence time my degraded exponentially in the number of qbits based on some yet undiscovered issues... so who knows.

Fortunately the way Bitcoin is constructed we are already somewhat hardened against quantum computers: When you use Bitcoin correctly and only use each address once the public key is only known for the brief window between announcement and mining, limiting the time under which a ECDSA attack could happen. The script system is flexible and we could introduce quantum-computer secure signatures at any point in time in a backwards compatible way, and start running them in-parallel with ECDSA signatures.

Unfortunately, while I'm a great fan of lamport the signatures are between 16KiB and 65KiB (for 128 and 256 bits of QC security, respectively).  Basically a 150 fold increase in transaction size and bandwidth.  Imagine a blockchain of 1TB instead of 7GB now. While we'd introduce them if QCs started to look like they might become an actual threat in the next decade, they just aren't viable absent that kind of threat.

um ok so your arguing against.... yourself here...or I am misreading you....

you said (If it did lamport wouldn't be strong against QC either) then Lamport is fine?

subtle.

good point about the size issue!!!!

Lamport signatures are known for being QC-resistant, but they are also one-time use. There is a way to combine them with a merkle tree to get more uses out of them, but it increases both the public key size and the signature size, I believe--but perhaps just one or the other, I don't remember. NTRUsign is a QC-resistant DSA that is far more data friendly than any other, but it also has a very limited lifespan in the number of times a public key can be used to sign something before the private key can be discovered. Not as big of an issue for bitcoin, but keys and signatures are still quite a bit larger than ECDSA.

Agreed. I think an article on the Wiki would be more appropriate than a sticky. It's not like quantum computers are an urgent must-read topic for the development forum.

On the other hand as (some form of) QCs are more realistic than the average sci-fi threat, we do get a lot of questions about them, some writing from an expert that'd reassure people that they're 1) not really an issue or 2) we can adopt when they come, would be nice to refer them to.

Hehe, exactly. November, 20000 AD.

There are some other hash-based signature schemes with much lower key sizes. For example, Qubic uses 64 bytes only for 2-step signing. There is a gap in time between each step though.

FWIW the experience of people working in the lab building QC prototypes has been that the engineering effort required to get them to actually work increases exponentially as the number of qbits goes up. Of course the most qbits used in a calculation is currently just six IIRC, so that trend doesn't have very much data backing it.

A bit out there suggestion....but I wonder if in someway, QC can be leveraged in a way to reveal new ways to build QC, I.E some sort of algorithm that reveals or solves a problem to build on the next Qbit....again I know this is quite an out there suggestion, given its largely a material/science nano tech exercise with FM' and STM domain...

Another interesting to note that biological systems have no trouble making complex 3D nano pick and place systems....I intuitively feel the solution to this problem will be in understanding how biological systems pick and place atoms at 36C!

then of course cool to run.....

If quantum computers was capable of breaking ECC but not breaking RIPEMD-160, then people would still not be able to spend old coins that they don't own using the standard address system.

However, to spend the coin, the owner inherently has to publish their public key in the spend transaction.  This gives a window where someone else can break the ECC and send the coin to themselves.

Maybe it would be worth having some system where you publish a hash of the signature first and then once that is incorporated into the chain, then you publish the public key.  This would require an opcode that you can ask to find a previous transaction and extract data from it.