Bitcoin Forum
September 15, 2019, 05:21:10 PM *
News: If you like a topic and you see an orange "bump" link, click it. More info.
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Bitcoin’s race to outrun the quantum computer  (Read 161 times)
Hydrogen
Hero Member
*****
Offline Offline

Activity: 1190
Merit: 717



View Profile
August 22, 2019, 04:22:20 PM
 #1

Quote
The world’s best cryptographers meet this week to compete in a U.S.-sponsored challenge to create a quantum-resistant standard.

Want to steal some Bitcoin? All you need to do is find your victim’s 16-character public key and calculate their private key by solving something called an “elliptic curve discrete logarithm problem.” No sweat! With a regular computer, that’ll take you around 50 million times the amount of time the universe itself has left—around 0.65 billion billion years.

Ah, but with the right quantum computer, able to process information at speeds exponentially faster than today’s supercomputers? Suddenly, what seems uncrackable becomes child’s play, able to be broken in under 10 minutes.

The quantum-computing problem is nothing new to crypto, and many experts believe we have at least a decade or more to come up with quantum-resistant cryptography. However, some observers say that recent and unexpectedly fast advances are causing the time horizon to dramatically shrink. The most aggressive estimate says that bitcoin will be hackable by 2027, according to Fact Based Insights.

“We moved the state of the art more in the last two years than it has progressed in the last 15 or 20,” says Stewart Allen, Chief Operating Officer at IonQ, a company that claims to make some of the most powerful quantum computers in the world, in an interview with Decrypt.

On Thursday, top cryptographers will meet in Santa Barbara at the University of California for the National Institute of Standards and Technology (NIST) Post Quantum Cryptography semi finals. The finalists of the NIST competition will be announced in the months after the conference, though it might take years before the winner is annointed. Cryptographers say the standards that result represent blockchain’s best hope for resisting the rapidly encroaching power of quantum computers.

”If someone cracked your key, they could do anything they wanted,” Rob Campbell, President at Baltimore,Maryland-based Med Cybersecurity, told Decrypt. Anyone with sensitive information on the blockchain—cash, personal data, medical records—is at risk. With that sort of information, quantum hackers could “forge your name, take your assets,” and, if there’s medical data to be found, maliciously “triple your dose,” said Campbell. “It’s an open door.”

Take the Bitcoin blockchain: an unencrypted public key is sent along with every bitcoin transaction, and left unencrypted during the time it takes for the network to confirm the block, around ten minutes. That’s theoretically more than enough time for a quantum-equipped hacker to calculate a private key from the public key and replace the recipient’s address with his own.

Que Quantum?  

Transistors in conventional computers capture data in terms of 1s and 0s. Is the sky blue today? If it is, 1. If not, 0. Computing is essentially combinations of these calculations: have enough transistors, you can compute almost anything.

With quantum computers, it’s possible for the same input, called a qubit, to represent both 0 and 1 at the same time, a non-binary state known as “quantum superposition”—think Schrödinger's dead-and-alive cat. This makes quantum computers exponentially more powerful; one lone, superpositioned qubit can handle the processing load of at least two full-sized transistors on a regular computer.

Using modified versions of “Shor’s algorithm,” a quantum algorithm that rapidly turns large numbers into prime factors, hackers could reverse the process that makes private keys so difficult to crack.

But at the moment, the best quantum computer is probably Google's Bristlecone quantum computer, which has 72 qubits. Miruna Rosca, a PhD student in post-quantum cryptography, tells Decrypt you’d probably need around 4000 qubits to break current cryptographic algorithms.

So how long do we have?
IonQ’s Allan, who creates quantum computers for a living, speculates it’ll take about a decade for post-quantum cryptography to become an issue. By then, he reckons, someone will probably have developed a quantum-resistant blockchain. Danny Ryan, a core researcher at Ethereum, thinks the same: “This isn't really a meaningful problem in the next 10 years and likely not for 20 to 30. That said, we tend to be bad at estimating things like this so we should be ready to transition sooner rather than later.”

But others say the problem requires immediate attention, and that—beyond the threat to Bitcoin—quantum computing could pose a major cybersecurity threat. Med Cybersecurity’s Rob Campbell says that a government armed with quantum decryption software could read all the world’s secrets.

A U.S. Navy signal officer by training, Campbell’s time in the classified research and development world has taught him that secret government technologies often outpace commercially available technology. “We were decades ahead of the commercial world,” he said. “We didn’t want any potential adversaries to know what our capabilities are.”

Even if Campbell’s claims seem ambitious, he points out that if an enemy security agency scrape all of your encrypted data today—which they certainly could—they’ll be able to decrypt all that data once they’ve built a powerful enough quantum computer. That’s enough to make developing quantum-resistant cryptographic techniques an issue of national security.

In any case, the arms race for quantum supremacy is well underway: China just spent $10 billion on a research center for quantum computers, and the U.S. has pumped hundreds of millions of dollars into the field.

Quantum-resistant techniques
Quantum computing can be just as effective for cryptographers as it is for hackers. Unobserved, superpositioned particles exist in multiple states, but when detected, they “collapse” to one point in space-time. Quantum cryptography has the same properties; because the protons that make up an encoded transaction shift upon observation, a successful attacker would have to break the laws of physics to intercept it.

This makes information encoded at the quantum level resistant to, among other things, so-called “man in the middle attacks,” where attackers intercept the transmission itself without having to decrypt the key.

A few blockchains claim to apply quantum-resistant techniques to ensure signatures and hashes remain encrypted, including QRL, IOTA, HyperCash, and Starkware. But with quantum computing still in its formative years, it’s difficult to determine the strength of these claims.

Until a quantum-resistant algorithm is tested and accepted by the wider academic community, there’s no assurance that any of these blockchains will be resilient enough against quantum computers. Scientists like Campbell are waiting on the results of next week’s NIST competition at UCAL-Santa Barbara; the final winners might not be announced for a few years, however. NIST tentatively expects drafts for standardisation will be completed around 2022.

“These winners are considered to be the best candidates on Earth and will likely go on to be standard cryptography and will be used by most of the planet,” says Campbell.

But developing the algorithm might not be the difficult part for large blockchains like Ethereum or Bitcoin. Whereas owners of centralized protocols can update the system as they please, blockchains, democratic by nature, require broad consensus among many thousands of miners to pass an upgrade.

In the case of an upgrade, all wallets that aren’t quantum-resistant become vulnerable to attack. That includes the 1 million bitcoins mined by Bitcoin’s pseudonymous inventor, Satoshi Nakamoto—if those aren’t migrated to a new, quantum-resistant wallet, they’re treasure for the first person with a powerful enough quantum computer.

“If high powered quantum computers appeared tomorrow,” said Ethereum’s Ryan, “we'd have many more problems than just the security of our blockchains.”

A 2019 National Academy of Sciences report concludes that, even if quantum computing is about a decade off, prioritising research is necessary to minimize “the chance of a potential security and privacy disaster.” Best get cracking, then.

https://decrypt.co/8498/bitcoins-race-to-outrun-the-quantum-computer

....


Many aspects of this initiative would appear to be political and agenda based rather than technologically or scientifically motivated. Like artificial intelligence, recent breakthroughs in brute forcing have come mainly from innovation associated with smaller nanoscale fabrication process of semiconductors.

We've witnessed many calls from political figures for corporations like apple to explicitly build backdoors into encryption standards used by iphones. Governments around the world would appear to unanimously support wholesale decryption defeating backdoors built into products ranging from smart phones to routers to operating systems.

In that the spirit of this competition would appear to run contrary to the status quo.

The excerpt below raises interesting questions.

Quote
Scientists like Campbell are waiting on the results of next week’s NIST competition at UCAL-Santa Barbara; the final winners might not be announced for a few years, however. NIST tentatively expects drafts for standardisation will be completed around 2022.

These winners are considered to be the best candidates on Earth and will likely go on to be standard cryptography and will be used by most of the planet,” says Campbell.

Maybe this competition is intended to create encryption standards utilized by the entire world that have backdoors or vulnerabilities specifically engineered into them?

It could be a decent security practice to avoid whatever encryption standards are produced as a result of this?

1568568070
Hero Member
*
Offline Offline

Posts: 1568568070

View Profile Personal Message (Offline)

Ignore
1568568070
Reply with quote  #2

1568568070
Report to moderator
1568568070
Hero Member
*
Offline Offline

Posts: 1568568070

View Profile Personal Message (Offline)

Ignore
1568568070
Reply with quote  #2

1568568070
Report to moderator
1568568070
Hero Member
*
Offline Offline

Posts: 1568568070

View Profile Personal Message (Offline)

Ignore
1568568070
Reply with quote  #2

1568568070
Report to moderator
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1568568070
Hero Member
*
Offline Offline

Posts: 1568568070

View Profile Personal Message (Offline)

Ignore
1568568070
Reply with quote  #2

1568568070
Report to moderator
1568568070
Hero Member
*
Offline Offline

Posts: 1568568070

View Profile Personal Message (Offline)

Ignore
1568568070
Reply with quote  #2

1568568070
Report to moderator
1568568070
Hero Member
*
Offline Offline

Posts: 1568568070

View Profile Personal Message (Offline)

Ignore
1568568070
Reply with quote  #2

1568568070
Report to moderator
pereira4
Legendary
*
Offline Offline

Activity: 1526
Merit: 1129



View Profile
August 22, 2019, 06:58:04 PM
Merited by Welsh (5), LoyceV (2), ETFbitcoin (1), LeGaulois (1), hugeblack (1)
 #2



Maybe this competition is intended to create encryption standards utilized by the entire world that have backdoors or vulnerabilities specifically engineered into them?

It could be a decent security practice to avoid whatever encryption standards are produced as a result of this?

If you are paranoid about the outcome of this US sponsored competition to come up with encryption standards, then you should be paranoid about Bitcoin's SHA256, Tor or anything else that came out of US related activity.

In any case there's no real reason to worry about any of this, quantum computing as it is today it's just a meme. I would stick to SHA256 and plan for a NIST alternative in the future if necessary.. and non-US stuff doesn't necessarily mean safer anyway. It just has to be peer reviewed by as many independent and widespread people as possible.

Satoshi most likely did the right thing at not using something more exotic, it could have backfired, SHA256 was the most widespread with hardware support and timetested, peer-reviewed by cryptographers.




.




  ▄▄▄▄▄▄▄▄▄▄▄▄▄
▄████████▀▀▀▀███▄
███████▀     ████
███████   ███████
█████        ████
███████   ███████
▀██████   ██████▀
  ▀▀▀▀▀   ▀▀▀▀▀

  ▄▄▄▄▄▄▄▄▄▄▄▄▄
▄██▀▀▀▀▀▀▀▀▀▀▀██▄
██    ▄▄▄▄▄ ▀  ██
██   █▀   ▀█   ██
██   █▄   ▄█   ██
██    ▀▀▀▀▀    ██
▀██▄▄▄▄▄▄▄▄▄▄▄██▀
  ▀▀▀▀▀▀▀▀▀▀▀▀▀

            ▄▄▄
█▄▄      ████████▄
 █████▄▄████████▌
▀██████████████▌
  █████████████
  ▀██████████▀
   ▄▄██████▀
    ▀▀▀▀▀

    ██  ██
  ███████████▄
    ██      ▀█
    ██▄▄▄▄▄▄█▀
    ██▀▀▀▀▀▀█▄
    ██      ▄█
  ███████████▀
    ██  ██




               ▄
       ▄  ▄█▄ ▀█▀      ▄
      ▀█▀  ▀   ▄  ▄█▄ ▀█▀
███▄▄▄        ▀█▀  ▀     ▄▄▄███       ▐█▄    ▄█▌   ▐█▌   █▄    ▐█▌   ████████   █████▄     ██    ▄█████▄▄   ▐█████▌
████████▄▄           ▄▄████████       ▐███▄▄███▌   ▐█▌   ███▄  ▐█▌      ██      █▌  ▀██    ██   ▄██▀   ▀▀   ▐█
███████████▄       ▄███████████       ▐█▌▀██▀▐█▌   ▐█▌   ██▀██▄▐█▌      ██      █▌   ▐█▌   ██   ██          ▐█████▌
 ████████████     ████████████        ▐█▌    ▐█▌   ▐█▌   ██  ▀███▌      ██      █▌  ▄██    ██   ▀██▄   ▄▄   ▐█
  ████████████   ████████████         ▐█▌    ▐█▌   ▐█▌   ██    ▀█▌      ██      █████▀     ██    ▀█████▀▀   ▐█████▌
   ▀███████████ ███████████▀
     ▀███████████████████▀
        ▀▀▀█████████▀▀▀
FIND OUT MORE AT MINTDICE.COM
figmentofmyass
Hero Member
*****
Offline Offline

Activity: 1204
Merit: 877



View Profile
August 22, 2019, 09:42:16 PM
 #3

okay, so we're maybe 8-30 years out from quantum computers breaking ECDSA. what's the plan? how far ahead should we integrate a quantum resistant signature scheme?

In any case there's no real reason to worry about any of this, quantum computing as it is today it's just a meme. I would stick to SHA256 and plan for a NIST alternative in the future if necessary.. and non-US stuff doesn't necessarily mean safer anyway. It just has to be peer reviewed by as many independent and widespread people as possible.

my understanding is that ECDSA will eventually be vulnerable to quantum computers. SHA-256 not so much.

pooya87
Legendary
*
Offline Offline

Activity: 1764
Merit: 1869


Remember tonight for it's the beginning of forever


View Profile
August 23, 2019, 03:38:19 AM
 #4

Quote
victim’s 16-character public key

in what world is a bitcoin public key a 16-character string? even if you encode it with smallest encodings used in bitcoin you wouldn't make it to 16 characters. even encoding the RIPEMD160 hash of the SHA256 hash of the public key is going to give you 20 bytes that would encode to 26 characters minimum Cheesy

Quote
Maybe this competition is intended to create encryption standards utilized by the entire world that have backdoors or vulnerabilities specifically engineered into them?
NIST standards are not for the "entire" world and the entire world has never been using their standards anyways. for example SHA256 is theirs, other countries sometimes have their own standards which they use. SM3 is the Chinese equivalent of SHA256. Streebog is the Russian equivalent.

Hydrogen
Hero Member
*****
Offline Offline

Activity: 1190
Merit: 717



View Profile
September 11, 2019, 08:39:53 PM
 #5

If you are paranoid about the outcome of this US sponsored competition to come up with encryption standards, then you should be paranoid about Bitcoin's SHA256, Tor or anything else that came out of US related activity.

In any case there's no real reason to worry about any of this, quantum computing as it is today it's just a meme. I would stick to SHA256 and plan for a NIST alternative in the future if necessary.. and non-US stuff doesn't necessarily mean safer anyway. It just has to be peer reviewed by as many independent and widespread people as possible.

Satoshi most likely did the right thing at not using something more exotic, it could have backfired, SHA256 was the most widespread with hardware support and timetested, peer-reviewed by cryptographers.


This being the anniversary of the september 11th World Trade Center attacks. It should be remembered that the official report attributing the destruction of buildings to office fires was drawn up by NIST (National Institute of Science and Technology). The 9/11 report NIST released was NOT open to peer review by architects, structural engineers or anyone with the academic or professional credentials who might normally peer review that type of report.

Not only does NIST have a history of publishing controversial findings as their initial 9/11 publishing containing "pancake theory" was wholly debunked by engineers across the globe. They also have a history of producing work that is completely closed to peer review or any form of accountability process.

Quantum computing is pseudoscience imo. There is no real quantum computing threat or crisis aside from media gaslighting and sensationalism. What we're witnessing is the typical process by which crisis is artificially manufactured to push agendas.

Kakmakr
Legendary
*
Offline Offline

Activity: 1778
Merit: 1354

★ ChipMixer | Bitcoin mixing service ★


View Profile
September 14, 2019, 09:05:58 AM
 #6

Well, I think the solution is already out there in the form of SHA512.  Roll Eyes  Most processors today can handle SHA512 much easier today, so it is not unlikely that they would switch to SHA512 in the future.  Huh  They are obviously not just doing this to protect Crypto currencies, because most secure sites and even some Banking services use SHA256 today.  Cheesy

Will the change from SHA256 to SHA512 necessitate a whole Bitcoin fork or can this just be done with a normal node update? I am not a developer, so I might be asking a stupid question... sorry.  Roll Eyes

buwaytress
Hero Member
*****
Offline Offline

Activity: 1106
Merit: 956


I bit, therefore I am


View Profile
September 14, 2019, 01:15:24 PM
 #7

Will the change from SHA256 to SHA512 necessitate a whole Bitcoin fork or can this just be done with a normal node update? I am not a developer, so I might be asking a stupid question... sorry.  Roll Eyes

Was a separate discussion I saw just days ago about SHA512 and it would seem to be that changing the hash function isn't as drastic as changing the algorithm itself (which I'm certain needs the hard fork). It seems to me it's still consensus that's required though, so if there were resistance...

On the other hand, if I understood that discussion well enough, there's simply not enough justification for sha512, not enough benefit.

Neither am I (a developer!) so I don't know the right answer to this, but now you ask, I wonder if I should look up how and when forks are needed...

pooya87
Legendary
*
Offline Offline

Activity: 1764
Merit: 1869


Remember tonight for it's the beginning of forever


View Profile
Today at 03:41:44 AM
Merited by HeRetiK (1)
 #8

Well, I think the solution is already out there in the form of SHA512.  Roll Eyes  Most processors today can handle SHA512 much easier today, so it is not unlikely that they would switch to SHA512 in the future.  Huh  They are obviously not just doing this to protect Crypto currencies, because most secure sites and even some Banking services use SHA256 today.  Cheesy

Will the change from SHA256 to SHA512 necessitate a whole Bitcoin fork or can this just be done with a normal node update? I am not a developer, so I might be asking a stupid question... sorry.  Roll Eyes

not only switching to SHA512 is unlikely, i would say it is stupid.
for starters it would make everything twice as big and that is while we are trying so hard to compress everything and make them smaller to keep it manageable (for storage and scaling).
on top of that you can't just stop there, you have to change the curve too. with a 256 bit curve it is not useful to use a 512 bit hash function. you have to also switch to a 512+ bit curve like secp521r1. i am also sure that switch to SHA512 would break 90% of bitcoin implementations because they either don't have the functionality to calculate "e" during ECDSA since they never needed it or they have a false one in place.

and finally as i have said before, unlike SHA1 versus SHA256 where the algorithms are different, in SHA512 versus SHA256 the algorithm is exactly the same (hence the switch being stupid). when a hash function becomes obsolete/weak like SHA1 it is not because of the size of it (160 bit) it is because a vulnerability in the algorithm was found, again like SHA1 which leads to attacks becoming easier (decreasing complexity from from 280 down to 263.1).
if such switch some day happens it will be to a different 256-bit algorithm such as Keccak-256, Blak2b-256,...

Pages: [1]
  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!