Topic: Quantum Computers META THREAD Defacto STICKY (Read 4520 times)

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.

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

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.

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.

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.

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.

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!!!!

**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.

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.

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!

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, 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

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.

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.

haha.

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

pay 100 BTC to sig address pm me

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

Don't forget this thread - Why is Bitcoin safe against a quantum computer? (https://bitcointalksearch.org/topic/why-is-bitcoin-safe-against-a-quantum-computer-153302)

PS: Btw, seems Bitcoin is NOT safe.

looks fine but needs a bundle of links at the top

This thread has some very detailed discussion that would be a bit more useful as a sticky, imo.

Sticky this one

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