fred21
Member
Offline
Activity: 138
Merit: 19


December 20, 2018, 08:24:19 PM 

Hello,
I found out that maybe one day, it will be able to find private key from a public key using quantum computing (around 2030)
1) it is said that using several time the same BTC address is risky. I am using a paper wallet with a unique address. How can I use another address with the BTC arriving on the same paper wallet?
2) I have heard that quantum computing will be able to acted for craking a public address ONLY during the transaction process? is it true or not?
3) except making the public address more heavy, what are the options for BTC to be saved from quantum computing?
Thanks for your help.





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

AdolfinWolf
Legendary
Offline
Activity: 1652
Merit: 1326
people run from rain but sit in bathtubs of water


December 20, 2018, 08:54:09 PM 

Hello,
I found out that maybe one day, it will be able to find private key from a public key using quantum computing (around 2030)
1) it is said that using several time the same BTC address is risky. I am using a paper wallet with a unique address. How can I use another address with the BTC arriving on the same paper wallet?
2) I have heard that quantum computing will be able to acted for craking a public address ONLY during the transaction process? is it true or not?
3) except making the public address more heavy, what are the options for BTC to be saved from quantum computing?
Thanks for your help.
1) You can't? You'll need to use a wallet that'll generate a new adress every time you want to receive coins. I don't think that's possible with any paper wallet as the entire idea of a paper wallet is having 1 adress...? 2) The theory is, (correct me if i'm wrong) that it'll need your public key to do so, (cracking the privkey) which is always made public after you signed/broadcasted a transaction from said adress. Afterall, your adress is simply a oneway hash.. 3) https://en.bitcoin.it/wiki/Quantum_computing_and_BitcoinThere's some other threads about this, too. https://bitcointalk.org/index.php?topic=4266048.0




fred21
Member
Offline
Activity: 138
Merit: 19


December 20, 2018, 10:35:18 PM 

1) So how is it possible for some wallet online or hard wallet to give a new address for every transaction? Does this mean that the BTC sent to those address are separated?
there is something as a general key for a wallet called " ECDSA public key"
2) But if you use even one time your public key, this is as risky as you use it several time. Because you display it. I think that cracking with quantum computing is done during transaction. don't you think?




AdolfinWolf
Legendary
Offline
Activity: 1652
Merit: 1326
people run from rain but sit in bathtubs of water


December 20, 2018, 10:56:12 PM 

1) So how is it possible for some wallet online or hard wallet to give a new address for every transaction? Does this mean that the BTC sent to those address are separated?
there is something as a general key for a wallet called " ECDSA public key"
2) But if you use even one time your public key, this is as risky as you use it several time. Because you display it. I think that cracking with quantum computing is done during transaction. don't you think?
1) Basically the amount of adresses that can be generated are infinite (Well, not exactly infinite, 2^160(i think it was??)). Any wallet such as Bitcoin core/Electrum can simply generate a new private key > public key > adress. https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addressesYes. If you make an output to adress X with 1 BTC and to adress Z with 0.5 BTC, from adress Y holding 1.5 BTC,they will indeed be different UTXO’s. 2) I’m not an expert on this. The only thing i do know is that, once you broadcast a transaction,the public keys of the adresses belonging to the UTXO’s that are being spend become known. How and when in this process quantum computing will make use of this to bruteforce your privatekey, i have no clue.




HeRetiK
Legendary
Offline
Activity: 1834
Merit: 1495
the forkings will continue until morale improves


December 20, 2018, 11:32:30 PM Merited by Macadonian (2) 

2) But if you use even one time your public key, this is as risky as you use it several time. Because you display it. I think that cracking with quantum computing is done during transaction. don't you think?
This will depend on how effective a quantum computer will be at deriving the private key from its respective public key. The first viable quantum attacks on Bitcoin's public / private key cryptography will probably still take days, weeks or even months to derive the private key from a public key. At this point address reusage will become a serious security risk; however one time usage of an address should still be fine for the most part. The attack you describe (ie. inflight, during an outgoing transaction) would become a risk once quantum computing reaches an effectiveness that allows deriving the private key within a block interval (ie. within minutes or even seconds, rather than days). At this point each Bitcoin transaction as we know it would be at risk of being diverted in an unprecedented form of doublespend attack (ie. one that requires no hashing power and allows you to doublespend someone elses coins, rather than only your own). Needless to say this would render Bitcoin useless. However we're still very far from the first scenario, let alone the second. For all we know reaching even the first scenario could still take 10, 20 years, if we even see it come to fruition at all. Either way Bitcoin will likely have sufficient time to switch to a quantum resistant private / public key encryption and / or transaction scheme before any such attacks become close to viable.




MagicByt3
Sr. Member
Offline
Activity: 798
Merit: 418
<Insert No Fucks Given Here>


December 21, 2018, 01:24:08 AM 

Quantum has a long way to go before you need to start to worry about this playing out IRL.
They are still trying to work out the qubit's and the size of the machines fill rooms so no need to panic yet.

"If you don't believe it or don't get it, I don't have the time to try to convince you, sorry". Satoshi Nakamoto



fred21
Member
Offline
Activity: 138
Merit: 19


December 21, 2018, 09:56:29 PM 

@HeRetiK
Once you get private key, You get the BTC on the public address.
If quantum computing takes 6 months to derive my private key from my public key and I leave my BTC on this public key (BTC address) during this time duration of more than 6 months. My BTC get stolen.
So will we need to constantly make transaction in order to move BTC from a public key to another?




Macadonian
Member
Offline
Activity: 115
Merit: 329


December 21, 2018, 10:25:59 PM 

Common misconceptions are that quantum computers will be the end of Bitcoin. That's untrue and the only thing quantum computers break is the ECDSA algorithm that Bitcoin currently uses. Please note that I said "currently" indicating that we could possibly change to a quantum resistant algorithm in the future which already exist and several products are already using such a algorithm. Ok so why haven't we changed yet? There's is no need to as quantum computers are far off from becoming a threat. I think the best quantum computer out there right now is 5 qbits and thousands qbits are needed to pose a threat to the algorthim. I'm planning on writing a thread which will go into a little more depth about this soon. Quantum computers are very effective at certain things such as exploiting rules in quantum mechanics that traditional computers cannot access. They are very good at soling specific mathimatical problems e.g factoring integers. However this doesn't mean that they are efficient in all areas. @HeRetiK
Once you get private key, You get the BTC on the public address.
If quantum computing takes 6 months to derive my private key from my public key and I leave my BTC on this public key (BTC address) during this time duration of more than 6 months. My BTC get stolen.
So will we need to constantly make transaction in order to move BTC from a public key to another?
Yes. It's true that you can deprive a private key from a public address using a quantum computer. But we are very far off achieving this with quantum mechanics. Currently as mentioned before the most powerful quantum computer is around 5 qubits right now. However it would require several thousand for it to become a threat to EDSCA. By then I like to think that we would have either moved to a quantum resistant algorithm by then.




bones261
Legendary
Offline
Activity: 1806
Merit: 1823


December 22, 2018, 02:44:01 AM Last edit: December 22, 2018, 02:55:16 PM by bones261 

Common misconceptions are that quantum computers will be the end of Bitcoin. That's untrue and the only thing quantum computers break is the ECDSA algorithm that Bitcoin currently uses. Please note that I said "currently" indicating that we could possibly change to a quantum resistant algorithm in the future which already exist and several products are already using such a algorithm. Ok so why haven't we changed yet? There's is no need to as quantum computers are far off from becoming a threat. I think the best quantum computer out there right now is 5 qbits and thousands qbits are needed to pose a threat to the algorthim. I'm planning on writing a thread which will go into a little more depth about this soon. Quantum computers are very effective at certain things such as exploiting rules in quantum mechanics that traditional computers cannot access. They are very good at soling specific mathimatical problems e.g factoring integers. However this doesn't mean that they are efficient in all areas.
Actually, a company called dwave is selling 2000 qubit computers. However, the applications that it is good for would not be suitable for cracking algorithms. Also, the majority of the qubits have to be used for error correction due to quantum decoherence. There are other challenges with quantum computing as well. Also, the ECDSA can be changed, however; old coins sitting in "legacy" address may still be redeemable. If Satoshi never moves his coins, the ~ 1 million coins recovered could pose a problem. However, I doubt that quantum computing will become a reasonable threat in the near future. Maybe a few decades from now. This should give the BTC dev team plenty of time to come up with a solution.




HeRetiK
Legendary
Offline
Activity: 1834
Merit: 1495
the forkings will continue until morale improves

@HeRetiK
Once you get private key, You get the BTC on the public address.
If quantum computing takes 6 months to derive my private key from my public key and I leave my BTC on this public key (BTC address) during this time duration of more than 6 months. My BTC get stolen.
So will we need to constantly make transaction in order to move BTC from a public key to another?
The BTC address is not the public key. It's the RIPEMD160 hash of a SHA256 hash of the public key, including some bits of error correction and encoded as Base58 [1]. The public key is not published until the first outgoing transaction is made from a BTC address [2], since only then the public key becomes necessary to validate the transaction. Modern P2SH and Bech32 addresses and transactions work slightly differently, but in either case the public key is not published until an outgoing transaction is made. SHA256 appears to be not especially vulnerable to quantum computing [3] (ie. quantum computing does not offer any advantage over classical computing for the subset of mathematical operations required for SHA256); I think the same holds true for RIPEMD160 but I'm not sure. Accordingly a BTC address only becomes potentially vulnerable to quantum computing once the first outgoing transaction has been made, since in either case the public key is not known prior to that transaction. [1] https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses[2] https://en.bitcoin.it/wiki/Transaction[3] https://crypto.stackexchange.com/questions/59375/arehashfunctionsstrongagainstquantumcryptographyandorindependentenough




buwaytress
Legendary
Offline
Activity: 1708
Merit: 1577
Join the worldleading crypto sportsbook NOW!


December 22, 2018, 09:59:18 AM 

Accordingly a BTC address only becomes potentially vulnerable to quantum computing once the first outgoing transaction has been made, since in either case the public key is not known prior to that transaction.
Very good point and probably one of the first things to remind people who talk about the quantum computing threat. Yes, it's a threat, but not one that is present. By the time there is a such a computer capable of cracking a Bitcoin private key, it's a very solid assumption to say that Bitcoin by then would have adopted superior algorithms. It's the nature of tech and cryptography to stay ahead of the curve, and there's every reason to believe Bitcoin will stay far, far ahead of that. And if that doesn't happen, then the very simple solution of singleuse addresses for spending nullifies that threat.




ETFbitcoin
Legendary
Offline
Activity: 1862
Merit: 2782
NotYourKeys.org  Not Your Keys, Not Your Bitcoin


December 22, 2018, 04:33:35 PM 

By the time there is a such a computer capable of cracking a Bitcoin private key, it's a very solid assumption to say that Bitcoin by then would have adopted superior algorithms. It's the nature of tech and cryptography to stay ahead of the curve, and there's every reason to believe Bitcoin will stay far, far ahead of that.
That's right, in fact there are few alternatives (even though mostly have big tradeoff) such as : 1. Lamport Signature. One of the tradeoff is big signature size 2. Latticebased Cryptography 3. Multivariatebased cryptography 4. Hashbased signatures. AFAIK it's designed for privatekey cryptography and publickey "version" is far from secure. More info : 1. https://en.wikipedia.org/wiki/Lamport_signature2. https://medium.com/cryptoblog/whatislatticebasedcryptographywhyshouldyoucaredbf9957ab7173. https://arxiv.org/pdf/1804.00200.pdfAnd if that doesn't happen, then the very simple solution of singleuse addresses for spending nullifies that threat.
It's last resort and unpractical, unless all wallet never allow send Bitcoin to used address.




fred21
Member
Offline
Activity: 138
Merit: 19


December 23, 2018, 11:12:18 PM 

@HeRetiK
OK I learned that public key is not BTC address.
My BTC are stored on a BTC address which has never spent any BTC so I can sleep good at night even if quantum computing arrives.
However, can you derive public key from BTC address with Quantum Computing? I think the answer is no according to what HeRetiK said.




mikeywith
Legendary
Offline
Activity: 1134
Merit: 3618
be constructive or S.T.F.U


December 24, 2018, 01:45:36 AM 

@HeRetiK
OK I learned that public key is not BTC address.
My BTC are stored on a BTC address which has never spent any BTC so I can sleep good at night even if quantum computing arrives.
However, can you derive public key from BTC address with Quantum Computing? I think the answer is no according to what HeRetiK said.
in theory yes, you have to have the public key in order to brute force that private key from the public key. but with that being said, the current computing power is also capable of doing so. technically you can brute force anything, even with a pen and paper you have a chance above 0% of getting the private key. but it's a merely a question of how hard and how much does it cost. but in general if someone has the power to crack the private key from a public key, they would probably make more profit mining. so honestly i do not see any threat coming from quantum computing . btw here is a nice read on the limits of qc > http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf




HeRetiK
Legendary
Offline
Activity: 1834
Merit: 1495
the forkings will continue until morale improves

@HeRetiK
OK I learned that public key is not BTC address.
My BTC are stored on a BTC address which has never spent any BTC so I can sleep good at night even if quantum computing arrives. Oh quantum computing is already here. Matter of fact, you can have some fun with quantum computing today: https://quantumexperience.ng.bluemix.net/qx/experienceIt's just that it still has a long way to go before any of the currently known algorithms can be applied to cryptography in practice. To give some perspective, breaking ECDSA as used by Bitcoin is expected to require thousands of qubits [1][2]. Currently we're at the tens of qubits [3] (ignoring DWave quantum computers which follow a fairly different approach that isn't applicable to the sort of math problem that ECDSA poses [4]). [1] https://security.stackexchange.com/questions/87345/howmanyqubitsareneededtofactor2048bitrsakeysonaquantumcomputer[2] https://en.wikipedia.org/wiki/Ellipticcurve_cryptography#Quantum_computing_attacks[3] https://www.quora.com/Howmanyqubitsdoesthecurrentstateoftheartquantumcomputerhave[4] https://crypto.stackexchange.com/questions/40893/canorcannotdwavesquantumcomputersuseshorsandgroversalgorithmtof[...]
However, can you derive public key from BTC address with Quantum Computing? I think the answer is no according to what HeRetiK said.
in theory yes, you have to have the public key in order to brute force that private key from the public key. Deriving (a) the private key from a public key is a completely different operation from (b) bruteforcing the public key from its nested cryptographic hashes. While (a) may become feasible with quantum computing eventually, (b) appears to be infeasible even for quantum computers. but with that being said, the current computing power is also capable of doing so. technically you can brute force anything, even with a pen and paper you have a chance above 0% of getting the private key. but it's a merely a question of how hard and how much does it cost. Capable of trying maybe, but not capable of succeeding. If you'd try to brute force the Bitcoin address space  and brute forcing is all you could do, given that there's currently neither a way to derive a private key from a public key nor a way to derive a public key from a BTC address  you'll be engulfed by the sun turning into a red giant before finding even your first active private key (Timeframe for the sun turning into a red giant: 5  6 billion years [5]. Yearly chance of finding an active private key using the large bitcoin collider: approx 0.000000000000000000000000055% [6]). And that's just for finding a random private key, not a specific one. Obviously that's based on the computational power we currently have available. However quantum computing is unlikely to have much of an impact on improving the odds of brute forcing a BTC address in practice, which is why the threat posed by quantum computing is one of mathematical prowess (ie. deriving the private key from a public key using what is essentially a computational shortcut) rather than one of brute force (ie. scanning Bitcoin's key space). [5] https://en.wikipedia.org/wiki/Red_giant#The_Sun_as_a_red_giant[6] https://bitcointalk.org/index.php?topic=5073899.msg48145266#msg48145266




fred21
Member
Offline
Activity: 138
Merit: 19


December 24, 2018, 10:22:51 PM 

@HeRetiK Deriving (a) the private key from a public key is a completely different operation from (b) bruteforcing the public key from its nested cryptographic hashes. While (a) may become feasible with quantum computing eventually, (b) appears to be infeasible even for quantum computers.
So why private keys aren't linked to the public keys the same way public keys are linked to BTC addresses? This will make impossible quantum computer to crack private key with knowing public key.




HeRetiK
Legendary
Offline
Activity: 1834
Merit: 1495
the forkings will continue until morale improves


December 25, 2018, 10:18:29 AM 

@HeRetiK Deriving (a) the private key from a public key is a completely different operation from (b) bruteforcing the public key from its nested cryptographic hashes. While (a) may become feasible with quantum computing eventually, (b) appears to be infeasible even for quantum computers.
So why private keys aren't linked to the public keys the same way public keys are linked to BTC addresses? What do you mean by "why"? Technically because we're talking about two completely different types of cryptography. One is asymetric cryptography: https://en.wikipedia.org/wiki/Publickey_cryptographyThe other are cryptographic hashes: https://en.wikipedia.org/wiki/Cryptographic_hash_functionNote that a weakness to quantum computing is neither inherent to asymetric cryptography nor to cryptographic hashes. Not all private / public key schemes are necessarily at risk and not all cryptographic hash functions are necessarily quantum resistant. There's a lot of cryptographic algorithms for either type of cryptography, based on different kinds of math problems; some for which quantum computing will provide little to no speedup. In terms of what satoshi intended  who knows? The quantum algorithms in question have been developed in the 90s so it might well be that satoshi anticipated a possible quantum threat in the future. This will make impossible quantum computer to crack private key with knowing public key.
*without knowing the public key, yes. At least according to our current understanding of mathematics.




fred21
Member
Offline
Activity: 138
Merit: 19


December 25, 2018, 06:45:17 PM 

(b) bruteforcing the public key from its nested cryptographic hashes
By (b) you meant "finding the public key from BTC address", right? And you said that it was totally impossible to perform even with quantum computer, right?




HeRetiK
Legendary
Offline
Activity: 1834
Merit: 1495
the forkings will continue until morale improves


December 25, 2018, 08:52:18 PM 

(b) bruteforcing the public key from its nested cryptographic hashes
By (b) you meant "finding the public key from BTC address", right? Yes. Bruteforcing being the only known way to find the original input (in this case: the public key). And you said that it was totally impossible to perform even with quantum computer, right?
I wouldn't say "totally impossible", but right now we have absolutely no reason to believe that a quantum computer would be better at this task than a classical computer. Note that the theory of quantum computing far precedes it's practical implementation so it's fairly well understood. Accordingly it's rather unlikely that a surprise solution breaking those specific cryptographic hashes will come out of nowhere.




