Bitcoin Forum
April 24, 2014, 10:16:51 AM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: 1 2 [3] 4 5 6  All
  Print  
Author Topic: What does Quantum Computing mean for Bitcoin?  (Read 13335 times)
sgravina
Sr. Member
****
Offline Offline

Activity: 379



View Profile

Ignore
August 22, 2011, 06:11:14 PM
 #41

The best quantum computation ever was the successful factoring of the number 15 into it's prime constituents, 3 and 5.  It did this really slowly.

Quantum computing is interesting and worth pursuing for many reasons, but it will never be a useful computational device.

I don't really know the future, I'm just guessing based on the unsolved problem of reading more than a few qubits of information before it is lost to the environment.  Or the unsolved problem of storing more than a few qubits of information in a device without losing it.

Beyond a few qubits, at least 2 but less than 8, you can't program a problem for a quantum computer and you can't read the result.

Sam
1398334611
Hero Member
*
Offline Offline

Posts: 1398334611

View Profile Personal Message (Offline)

Ignore
1398334611
Reply with quote  #2

1398334611
Report to moderator
Unbeatable Service & Product Support
Grab Your Miners at GAWMiners.com
Order Before April 25th to receive
Double your Hashing Power for 1 week!

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1398334611
Hero Member
*
Offline Offline

Posts: 1398334611

View Profile Personal Message (Offline)

Ignore
1398334611
Reply with quote  #2

1398334611
Report to moderator
1398334611
Hero Member
*
Offline Offline

Posts: 1398334611

View Profile Personal Message (Offline)

Ignore
1398334611
Reply with quote  #2

1398334611
Report to moderator
1398334611
Hero Member
*
Offline Offline

Posts: 1398334611

View Profile Personal Message (Offline)

Ignore
1398334611
Reply with quote  #2

1398334611
Report to moderator
1398334611
Hero Member
*
Offline Offline

Posts: 1398334611

View Profile Personal Message (Offline)

Ignore
1398334611
Reply with quote  #2

1398334611
Report to moderator
kjj
Hero Member
*****
Offline Offline

Activity: 1036


Bitcoin Foundation - Lifetime Member


View Profile

Ignore
August 25, 2011, 03:07:38 PM
 #42

The best quantum computation ever was the successful factoring of the number 15 into it's prime constituents, 3 and 5.  It did this really slowly.

Quantum computing is interesting and worth pursuing for many reasons, but it will never be a useful computational device.

I don't really know the future, I'm just guessing based on the unsolved problem of reading more than a few qubits of information before it is lost to the environment.  Or the unsolved problem of storing more than a few qubits of information in a device without losing it.

Beyond a few qubits, at least 2 but less than 8, you can't program a problem for a quantum computer and you can't read the result.

I'm going to disagree.  The difficulties are, I think, just a matter of engineering.  Extremely difficult engineering, to be sure, but with a huge payoff.

Quantum information theory is too important to be left unused.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
ctoon6
Sr. Member
****
Offline Offline

Activity: 350



View Profile

Ignore
August 27, 2011, 11:41:13 PM
 #43

AFAIK cryptography is never "safe" it has many weaknesses.

1. the vault is only as secure as the key

in theory you never need to encrypt you private keys, just keep them in a place where others can not see it or access it.

2. all encryption can be broken with enough time AFAIK

3. to combat QC now, simply increase the encryption now to unrealistic heights. then you have time to reimplement the needed security once you understand the problem.

to find a private key from a public key would still probably take a while, my guess would be at best, a few days.

4. alternate chains will emerge and probably try to address these problems

and lets not forget the most important thing.

i have yet to see any real benchmark of QC doing real work, and i don't see that happening in the next 5 years.

qbg
Member
**
Offline Offline

Activity: 75


View Profile

Ignore
August 28, 2011, 12:07:25 AM
 #44

2. all encryption can be broken with enough time AFAIK
Except the one time pad.
ctoon6
Sr. Member
****
Offline Offline

Activity: 350



View Profile

Ignore
August 28, 2011, 01:14:05 AM
 #45

2. all encryption can be broken with enough time AFAIK
Except the one time pad.

thats not encryption, thats 2 factor verification, and it too is easily defeated

man in the middle attack
how do you handle it when you "lose" your security token?
phishing

Quantus
Full Member
***
Offline Offline

Activity: 220



View Profile

Ignore
August 28, 2011, 01:27:25 AM
 #46

Simple question, and I am by no means well-rounded in my knowledge of quantum computing. But what I have read indicates that it is a massive hammer to all crypto algos currently in existence. Could the sudden existence of quantum computing mean the sudden uselessness of Bitcoin as a currency?
simply yes. "not if but when they come out with powerful Quantum computers it will simply Crush any and all encryption commonly used today"
hashcoin
Full Member
***
Offline Offline

Activity: 122


View Profile

Ignore
August 28, 2011, 01:41:00 AM
 #47

With QC, far better things can be done than bitcoin.  In particular, it is possible to design quantum e-cash where transactions occur entirely offline and yet doublespending is prevented (i.e., no global blockchain that must be aware of all transactions).

http://dspace.mit.edu/handle/1721.1/52007
ctoon6
Sr. Member
****
Offline Offline

Activity: 350



View Profile

Ignore
August 28, 2011, 02:47:28 AM
 #48

With QC, far better things can be done than bitcoin.  In particular, it is possible to design quantum e-cash where transactions occur entirely offline and yet doublespending is prevented (i.e., no global blockchain that must be aware of all transactions).

http://dspace.mit.edu/handle/1721.1/52007


wanna sum it all up so i don't have to read 15 pages of high level math and complicated quantum theories?

RodeoX
Hero Member
*****
Offline Offline

Activity: 1148


The revolution will be monetized!


View Profile

Ignore
September 01, 2011, 04:55:10 PM
 #49

The spookiest thing about quantum (Einstien called it spooky) is that we do not know how it works. For all we know research may discover ways of accessing secure data via multidimensional exploits. It's no longer even out of the question to think that cause and effect is just a phenomena created by our feeble ability to perceive what's really going on.

I teach biology, and I often wonder if there is a quantum connection between wave colapse and the state we call "living". Right now I can't explain to my students the difference between a dead bird and a live bird.
You are going to hear a lot more about this in the future.

The gospel according to Satoshi - https://bitcoin.org/bitcoin.pdf
neptop
Sr. Member
****
Offline Offline

Activity: 313


View Profile

Ignore
September 01, 2011, 05:16:52 PM
 #50

Time for some conspiracy!


I guess there are a lot of rich people and institution with serious interests in quantum computing because of what it means to security. DARPA always had some secret research in various fields for example. They have virtually unlimited funds. However with the ability to really break (as opposed to just break it by the means of finding something better than brute force) cryptography you are powerful enough to care about Bitcoins or financial institutions anymore.

BitCoin address: 1E25UJEbifEejpYh117APmjYSXdLiJUCAZ
Piper67
Hero Member
*****
Offline Offline

Activity: 868


View Profile

Ignore
September 01, 2011, 05:19:42 PM
 #51

Heh... Richard Feynman, who was instrumental in developing quantum electrodynamics, once famously said that "if you think you understand quantum theory, you don't understand quantum theory".

I hope the same thing applies to quantum computing.  Cheesy
ctoon6
Sr. Member
****
Offline Offline

Activity: 350



View Profile

Ignore
September 01, 2011, 06:37:30 PM
 #52

The spookiest thing about quantum (Einstien called it spooky) is that we do not know how it works. For all we know research may discover ways of accessing secure data via multidimensional exploits. It's no longer even out of the question to think that cause and effect is just a phenomena created by our feeble ability to perceive what's really going on.

I teach biology, and I often wonder if there is a quantum connection between wave colapse and the state we call "living". Right now I can't explain to my students the difference between a dead bird and a live bird.
You are going to hear a lot more about this in the future.

a "real" answer
living is nothing more than chemical reactions and electrical impulses, all working together to create an illusion of live and death.



heres a little something to think about
for all we know or i know, you or i could be "god" and only imagining this thing we call life on earth. we could be like in the matrix for all we know. or you might not exist at all, in theory everything could be everything, and you perception of reality could just be a "wave"

RodeoX
Hero Member
*****
Offline Offline

Activity: 1148


The revolution will be monetized!


View Profile

Ignore
September 01, 2011, 07:04:52 PM
 #53

a "real" answer
living is nothing more than chemical reactions and electrical impulses, all working together to create an illusion of live and death.

You may be right. But even with our substantial knowledge of chemicals and electromagnetism we simply don't know how to get the "living state" going, or how it keeps going.
In physics a lot of discussion about unifying large and small scale theory is underway. But what about life? It seems to me that no theory of physics is complete without an explanation of the weirdest phenomena of all.

The gospel according to Satoshi - https://bitcoin.org/bitcoin.pdf
ctoon6
Sr. Member
****
Offline Offline

Activity: 350



View Profile

Ignore
September 01, 2011, 07:18:35 PM
 #54

a "real" answer
living is nothing more than chemical reactions and electrical impulses, all working together to create an illusion of live and death.

You may be right. But even with our substantial knowledge of chemicals and electromagnetism we simply don't know how to get the "living state" going, or how it keeps going.
In physics a lot of discussion about unifying large and small scale theory is underway. But what about life? It seems to me that no theory of physics is complete without an explanation of the weirdest phenomena of all.

imagine the entire world as a perfect sphere, now take a nail and scratch it, thats how much we know about organic and biological chemistry. the possibilities are endless as carbon is one of the trickiest elements we know of today.

life as we know it may have been created or seeded by extraterrestrials. so the question is probably best answered by them. at least thats my theory, how they were made up to the "god" to answer.
but we can never be sure until we know of a way to make life, depending on how complex it is, life may be made every day, and just dies off due to bad conditions or it could be so complex it only happens once every billion years or so by small chance.

according to Wikipedia
Life is a characteristic that distinguishes objects that have signaling and self-sustaining processes.
Death is the termination of the biological functions that sustain a living organism.

caston
Hero Member
*****
Offline Offline

Activity: 504



View Profile WWW

Ignore
September 02, 2011, 04:14:49 AM
 #55

This was posted to slashdot about a von Neumann quantum computer:

http://www.technologyreview.com/computing/38495/?p1=A1

18jL18iH96BBhwUCQn27FQp7ocodSxvJAB
neptop
Sr. Member
****
Offline Offline

Activity: 313


View Profile

Ignore
September 05, 2011, 02:54:51 PM
 #56

according to Wikipedia
Life is a characteristic that distinguishes objects that have [...] self-sustaining processes.
I see dead people!

BitCoin address: 1E25UJEbifEejpYh117APmjYSXdLiJUCAZ
caston
Hero Member
*****
Offline Offline

Activity: 504



View Profile WWW

Ignore
September 15, 2011, 02:42:47 AM
 #57

I would be more interested in what reversible computing may do for bitcoin.

18jL18iH96BBhwUCQn27FQp7ocodSxvJAB
cbeast
Donator
Hero Member
*
Offline Offline

Activity: 1064

Bitcoin, Decorporated stockholder since 2011.


View Profile

Ignore
September 15, 2011, 03:45:05 AM
 #58

Perhaps Mentats will one day be bred to combine Hawala with Bitcoin.

Any significantly advanced cryptocurrency is indistinguishable from Ponzi Tulips.
etotheipi
Hero Member
*****
Offline Offline

Activity: 1036


Core Armory Developer


View Profile WWW

Ignore
October 10, 2011, 04:20:45 AM
 #59

Sorry to revive an old thread, but I feel I have to contribute, as I have studied Quantum computing, cryptography and Bitcoin all extensively.  I've been considering writing a series on the topic, but I never quite found time to do it.  The least I can do is respond to this thread.

First and foremost, QCs are useless for breaking a public-private keypair if they don't have the public key, and Bitcoin addresses are actually hashes of the public key. The attacker only sees the public key the first time the owner spends coins.  Therefore, if you use each address exactly once, by the time the attacker with the QC sees your public key, the coins have already been sent to another address with an unknown public key.   I don't know if this was an intentional security mechanism, but it adds a high degree of quantum resistance that may actually save the network.  (NOTE:  actually this isn't true for coinbase transactions which usually include the person's full public key, but there's no reason the miners can't switch to regular BTC addresses)

The QC would have to have a faster connection to your computer than your computer has with the rest of the network, then when you broadcast a tx, they have to crack your public key instantaneously and broadcast a replacement transaction to a significant number of nodes before the original transaction propagates.  This would be have to be a highly targeted attack -- still a stretch even if the person with the QC controls a significant number of your peer connections -- and still requires the QC to be fast enough to compute your private key nearly instantaneously.   This would only feasibly succeed if they control all your peer connections.  However, there's a variety of other attacks the person can execute if they control all of your peers...

The other angle is if the person with the QC also controls a significant portion of the global hashrate.  With a classical computer, they can only double spend against you (sometimes), but with a QC they can now also spend your coins.  If they can solve for your private key quickly after you broadcast a tx, there's a chance they can build a new branch of the chain fast enough that discards your transaction and includes one of their own.  However, if someone has enough computing power to do this, the network/community is going to have serious problems regardless of whether QCs are involved.

Secondly, hashing is effectively secure against QCs.  QCs wouldn't break the algorithm itself, but Grover's algorithm can be used on any pure-guessing problem to cut it's compute time down to sqrt of the original problem.  If you are trying to find someone's public key based on their bitcoin address (the hash of it), it will take a classical computer 2^256 guesses, but it will take the QC 2^128 guesses.  This is still wildly infeasible (for reference, the entire bitcoin network has produced about about 2^70 hashes total over the course of 2 years --- approximately 1 quadrillionth of the number of computations required to reverse your public key from your BTC address).

This would be most relevant for mining, but probably still safe for a while.  It takes your classical computer approximately 1^15 hashes on average to compute a new block (at current difficulty), so it would take about 100 million operations on a quantum computer -- but QCs are going to be dirt slow for a long time - it's possible that 100 million ops could take days or months on a QC.  My guess is, miners will have nothing to fear from QCs for a long time.

Thirdly The QCs can only break a public-private keypair if they have enough qubits.  However, number of qubits is going to be one of the bottlenecks of QC, the same way classical computers at one point maxed out at 4kB of RAM.  The QC needs more qubits if the encryption/signing key is longer.  This is likely to be a short term solution for internet cryptography -- use much longer keys.  For instance, switching from 256-bit ECDSA (like bitcoin uses) to 4096-bit ECDSA could add an extra decade to the security of the system (which would be more than enough time to work out alternatives).  Sure, it will take 1 minute to sign a message, but there's plenty of infrastructure that will continue to exist (both Bitcoin and otherwise). 

Fourthly there are asymmetric encryption algorithms that will continue to be secure even in the presence of QCs.  Granted, most asymmetric schemes are based on exactly the kinds of problems that QCs are good at solving (integer factorization, discrete-log), but not all of them.   There's a dozens of unused op-codes, which could be leveraged to switch the network to a quantum-resistant signature algorithm other than ECDSA.  Even the hashing algorithm can be switched.   Satoshi explicitly wanted this in the design, since there's no guarantee that today's encryption algorithms will be secure tomorrow.  He probably didn't have QCs in mind, specifically, but any algorithm could be broken by mathematicians any day.

In summary: The biggest saving grace for BTC is that it uses hashes of public keys instead of the keys themselves.  This, by itself, adds an extremely high degree of quantum-resistance to the BTC network.  Other places where QCs might cause disruption are only purely theoretical, and could take decades for the technology to develop to the level needed to actually execute the attacks.  So, if any of this is ever going to happen, we will see it coming, potentially decades in advance and can prepare accordingly. 


Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
ctoon6
Sr. Member
****
Offline Offline

Activity: 350



View Profile

Ignore
October 10, 2011, 08:16:22 PM
 #60

Sorry to revive an old thread, but I feel I have to contribute, as I have studied Quantum computing, cryptography and Bitcoin all extensively.  I've been considering writing a series on the topic, but I never quite found time to do it.  The least I can do is respond to this thread.

First and foremost, QCs are useless for breaking a public-private keypair if they don't have the public key, and Bitcoin addresses are actually hashes of the public key. The attacker only sees the public key the first time the owner spends coins.  Therefore, if you use each address exactly once, by the time the attacker with the QC sees your public key, the coins have already been sent to another address with an unknown public key.   I don't know if this was an intentional security mechanism, but it adds a high degree of quantum resistance that may actually save the network.  (NOTE:  actually this isn't true for coinbase transactions which usually include the person's full public key, but there's no reason the miners can't switch to regular BTC addresses)

The QC would have to have a faster connection to your computer than your computer has with the rest of the network, then when you broadcast a tx, they have to crack your public key instantaneously and broadcast a replacement transaction to a significant number of nodes before the original transaction propagates.  This would be have to be a highly targeted attack -- still a stretch even if the person with the QC controls a significant number of your peer connections -- and still requires the QC to be fast enough to compute your private key nearly instantaneously.   This would only feasibly succeed if they control all your peer connections.  However, there's a variety of other attacks the person can execute if they control all of your peers...

The other angle is if the person with the QC also controls a significant portion of the global hashrate.  With a classical computer, they can only double spend against you (sometimes), but with a QC they can now also spend your coins.  If they can solve for your private key quickly after you broadcast a tx, there's a chance they can build a new branch of the chain fast enough that discards your transaction and includes one of their own.  However, if someone has enough computing power to do this, the network/community is going to have serious problems regardless of whether QCs are involved.

sorry but this makes no sense to me, either because i dont understand bitcoin correctly, or you dont.

what i know says that the block chain, which EVERYBODY HAS, contains a "list" of every public key and the amount of coins associated with it. the private key of the public key allows you to sign transactions, and you can verify that because the public key will allow you to do so, because that is what makes transactions valid, because you are able to verify it because you do have the public key.

and what do peers really have to do with all of this? they at no point offer any security to the network other than hashing and ensuring your transactions get broadcast.

i do agree with you that QCing may not break bitcoin or any other cryptographic scheme, but the future is very unpredictable so for all we know, cheese could be 600% faster than the current gen cpu's.

Pages: 1 2 [3] 4 5 6  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!