Bitcoin Forum
December 13, 2017, 08:55:37 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: In light of the NSA's disclosure about ECC, how is cryptocurrency affected?  (Read 2555 times)
americanpegasus
Hero Member
*****
Offline Offline

Activity: 742



View Profile
November 02, 2015, 07:40:13 PM
 #1

Most of you are already aware of the NSA's recent post (https://www.nsa.gov/ia/programs/suiteb_cryptography/) containing such troubling phrases as-  
Quote
Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be.
 
Quote
 
For those customers who are looking for mitigations to perform while the new algorithm suite is developed and implemented into products, there are several things they can do. First, it is prudent to use larger key sizes in algorithms (see the table below) in many systems (especially, smaller scale systems). Additionally, IAD customers using layered commercial solutions to protect classified national security information with a long intelligence life should begin implementing a layer of quantum resistant protection. Such protection may be implemented today through the use of large symmetric keys and specific secure protocol standards.
 (emphasis mine)  
  
There are many possible interpretations of these statements, but it is clear that the world's leading expert on cryptography just put out a gentle (but very public) warning that ECC may not be as secure as we believe.  This being the case, which cryptocurrencies might be affected by this?  Bitcoin?  Cryptonotes like Monero?  Ethereum?  
  
Will those blockchains eventually have to radically change their encryption algorithms?  Are there any steps that should be taken now to preserve privacy and legitimacy before this happens?  
  

Account is back under control of the real AmericanPegasus.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513198537
Hero Member
*
Offline Offline

Posts: 1513198537

View Profile Personal Message (Offline)

Ignore
1513198537
Reply with quote  #2

1513198537
Report to moderator
1513198537
Hero Member
*
Offline Offline

Posts: 1513198537

View Profile Personal Message (Offline)

Ignore
1513198537
Reply with quote  #2

1513198537
Report to moderator
Carlton Banks
Legendary
*
Offline Offline

Activity: 1848



View Profile
November 02, 2015, 07:52:54 PM
 #2

Old argument I believe. Quantum computers breaking the cryptography of binary computing only leads to the use of quantum cryptography. Cat and mouse.

Vires in numeris
achow101
Moderator
Legendary
*
Offline Offline

Activity: 1246


17kKQppUsngUiByDsce4JXoZEjjpvX9bpR


View Profile WWW
November 02, 2015, 08:06:58 PM
 #3

There are many possible interpretations of these statements, but it is clear that the world's leading expert on cryptography just put out a gentle (but very public) warning that ECC may not be as secure as we believe.  This being the case, which cryptocurrencies might be affected by this?  Bitcoin?  Cryptonotes like Monero?  Ethereum?  
Every single cryptocurrency would be affected. They are all based off of bitcoin which uses ECC. The obvious solution is to switch to a quantum resistant algorithm for generating private and public keys. I do not know if one exists yet.

However, if you use bitcoin as it should be without reusing addresses, then the argument that ECC is broken is not as valid. In order for ECC to be broken by quantum computers, the public key needs to be known. The public key is only known when a transaction sends Bitcoin out of an address. Thus, if each address is only used to send one transaction which spends everything to other newly generated addresses, then everything will be fine since even with the public key known, there is nothing to steal.
  
Will those blockchains eventually have to radically change their encryption algorithms?  Are there any steps that should be taken now to preserve privacy and legitimacy before this happens?  
Just to correct you, cryptocurrences DO NOT USE ENCRYPTION. The only crypto part are for key generation and signing, and the hashing of data for txids and blocks. Hashes are considered quantum secure. The security of hashes can be easily increased by doubling the bit length to have the same security we have now, e.g. SHA512 is as secure as SHA256 when quantum computers come around.

Come-from-Beyond
Legendary
*
Online Online

Activity: 1792

Newbie


View Profile
November 03, 2015, 07:20:35 AM
 #4

Every single cryptocurrency would be affected.

Let's not put all cryptocurrencies into the same basket, at least one is made to be quantum-resistant.


However, if you use bitcoin as it should be without reusing addresses, then the argument that ECC is broken is not as valid. In order for ECC to be broken by quantum computers, the public key needs to be known. The public key is only known when a transaction sends Bitcoin out of an address. Thus, if each address is only used to send one transaction which spends everything to other newly generated addresses, then everything will be fine since even with the public key known, there is nothing to steal.

You forgot to add that depending on characteristics of the quantum computer it can find private key and issue another transaction with higher fee before legit transaction is included into the blockchain.
USB-S
Sr. Member
****
Offline Offline

Activity: 364



View Profile
November 03, 2015, 07:38:34 AM
 #5

If I recall correctly, there are currently no quantum computers available. A lot of research and development is put in it though.

But does this mean that quantum computers can brute force any address? If so, is there any way we can move bitcoin protocol to quantum computing level?

Frist cpu then gpu then asics next quantum computers?
Come-from-Beyond
Legendary
*
Online Online

Activity: 1792

Newbie


View Profile
November 03, 2015, 07:57:39 AM
 #6

Frist cpu then gpu then asics next quantum computers?

A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.
americanpegasus
Hero Member
*****
Offline Offline

Activity: 742



View Profile
November 03, 2015, 08:08:51 AM
 #7

Frist cpu then gpu then asics next quantum computers?

A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.
 
 
If should be noted that if a Quantum Computer exists, it is beyond classified.... I do a *lot* of digging on the internet and the dark web and have never heard of a verified one.  The closest we have is D-Wave system's Quantum Annealing computer which is not the same thing. 
 
I have read research of scientists entangling 3 particles, a precursor to the first 4-qubit true quantum computer, but I've never read anything about 4 particles being successfully entangled.  Anyone can feel free to correct me, but wouldn't we need to be able to entangle 128 or 256 particles in a small area to create a "true" quantum computer capable of doing damage to modern cryptography?

Account is back under control of the real AmericanPegasus.
Come-from-Beyond
Legendary
*
Online Online

Activity: 1792

Newbie


View Profile
November 03, 2015, 08:11:39 AM
 #8

If should be noted that if a Quantum Computer exists, it is beyond classified.... I do a *lot* of digging on the internet and the dark web and have never heard of a verified one.  The closest we have is D-Wave system's Quantum Annealing computer which is not the same thing. 
 
I have read research of scientists entangling 3 particles, a precursor to the first 4-qubit true quantum computer, but I've never read anything about 4 particles being successfully entangled.  Anyone can feel free to correct me, but wouldn't we need to be able to entangle 128 or 256 particles in a small area to create a "true" quantum computer capable of doing damage to modern cryptography?

So these guys are stupid you think - https://www.nsa.gov/ia/programs/suiteb_cryptography/ ?
americanpegasus
Hero Member
*****
Offline Offline

Activity: 742



View Profile
November 03, 2015, 08:30:21 AM
 #9


So these guys are stupid you think - https://www.nsa.gov/ia/programs/suiteb_cryptography/ ?

The fact that I read through most of that link, and double checked it before realizing it was the exact same link I posted initially 6x proves I'm too drunk to be commenting on this thread until at least 24 hours from now.

Account is back under control of the real AmericanPegasus.
Carlton Banks
Legendary
*
Offline Offline

Activity: 1848



View Profile
November 03, 2015, 09:01:59 AM
 #10

Frist cpu then gpu then asics next quantum computers?

A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.

A quantum computer wouldn't be doing that to a chain using a hash function that uses quantum cryptography, or is that actually your assertion? That quantum computing is a magical panacea?

Vires in numeris
Tstar
Hero Member
*****
Offline Offline

Activity: 784



View Profile
November 03, 2015, 09:09:50 AM
 #11

Frist cpu then gpu then asics next quantum computers?

A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.

If such a technology would exist right now I do think that BTC technology would be the least to be exploited: i.e. imagine what such a mess this quantum computers could create to the entire internet/developed world. There would be nothing secure.
Ok, maybe I'm going too sci-fi now but, yes, I think BTC will be the last thing to worry about

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



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
























iQeon
.FACEBOOK  ◆  TWITTER  ◆  VK  ◆  INSTAGRAM  ◆  TELEGRAM.
.
REDDIT   ◆   GOOGLE+   ◆  STEEMIT  ◆   SLACK   ◆   LINKEDIN.












USB-S
Sr. Member
****
Offline Offline

Activity: 364



View Profile
November 03, 2015, 09:19:46 AM
 #12

Frist cpu then gpu then asics next quantum computers?

A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.

If such a technology would exist right now I do think that BTC technology would be the least to be exploited: i.e. imagine what such a mess this quantum computers could create to the entire internet/developed world. There would be nothing secure.
Ok, maybe I'm going too sci-fi now but, yes, I think BTC will be the last thing to worry about
that's an interesting argument, forgot that the bitcoin network is the most secure on the planet at this moment. That means Bye bye every commercial bank on this planet. Bankers should definitely rethink their "secure" systems.
keystroke
Hero Member
*****
Offline Offline

Activity: 842


advocate of a cryptographic attack on the globe


View Profile
November 03, 2015, 09:36:06 AM
 #13

Relevant reading from Koblitz and Menezes: https://eprint.iacr.org/2015/1018.pdf

secp256k1 is a Koblitz curve.

Abstract. In August 2015 the U.S. National Security Agency (NSA)
released a major policy statement on the need for post-quantum cryptography
(PQC). This announcement will be a great stimulus to the
development, standardization, and commercialization of new quantumsafe
algorithms. However, certain peculiarities in the wording and timing
of the statement have puzzled many people and given rise to much
speculation concerning the NSA, elliptic curve cryptography (ECC), and
quantum-safe cryptography. Our purpose is to attempt to evaluate some
of the theories that have been proposed.

One possibility:

5.5. The NSA has a political need to distance itself from ECC.
There were some peculiarities in the release of the August 2015 statement
about preparing for post-quantum crypto. Normally all of the big corporations
that do cryptographic work for the U.S. government would have been
given some advance notice, but this was not done. Even more surprising,
the NIST people were not asked about it, and even researchers in IAD were
caught by surprise. It seems that whoever at the NSA prepared the release
did so with minimal feedback from experts, and that includes their own
internal experts.

This suggests that the main considerations might not have been technical
at all, but rather Agency-specific — that is, related to the difficult situation
the NSA was in following the Snowden leaks. The loss of trust and credibility
from the scandal about Dual EC DRBG was so great that the NSA might
have anticipated that anything further it said about ECC standards would
be mistrusted. The NSA might have felt that the quickest way to recover
from the blow to its reputation would be to get a “clean slate” by abandoning
its former role as promoters of ECC and moving ahead with the transition
to post-quantum cryptography much earlier than it otherwise would have.

"The difference between a castle and a prison is only a question of who holds the keys."
americanpegasus
Hero Member
*****
Offline Offline

Activity: 742



View Profile
November 03, 2015, 09:45:48 AM
 #14

Relevant reading from Koblitz and Menezes: https://eprint.iacr.org/2015/1018.pdf

secp256k1 is a Koblitz curve.

 
 
Oh wow, an actual hardcore mathematician in the wild!  I know I promised not to post anymore until I sobered up, but I would love to hear your opinion on whether moving towards abelian surface cryptography is feasible at all, and whether it would provide any further defense against quantum computers: 
 

My original proposal: https://www.reddit.com/r/math/comments/3451ob/is_it_feasibleworthwhile_to_take_elliptic_curve/ 
 
Shit that's above my head: 
 
http://www.hyperelliptic.org/tanja/conf/ECC08/slides/Peter-Stevenhagen.pdf 
http://research.microsoft.com/pubs/249337/abelian.pdf 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.464.9485

Account is back under control of the real AmericanPegasus.
Come-from-Beyond
Legendary
*
Online Online

Activity: 1792

Newbie


View Profile
November 03, 2015, 09:52:14 AM
 #15

A quantum computer wouldn't be doing that to a chain using a hash function that uses quantum cryptography, or is that actually your assertion? That quantum computing is a magical panacea?

From http://188.138.57.93/tangle.pdf:

Quote
It is known that a (today still hypothetic) sufficiently large quantum computer can
be very efficient for handling problems where only way to solve it is to guess answers
repeatedly and check them. The process of finding a nonce in order to generate a
Bitcoin block is a good example of such a problem. As of today, in average one must
check around 2^68 nonces to find a suitable hash that allows to generate a block. It
is known (see e.g. [7]) that a quantum computer would need Θ(√N) operations to
solve a problem of the above sort that needs Θ(N) operations on a classical computer.
Therefore, a quantum computer would be around √(2^68) = 2^34 ≈ 17 billion times more
efficient
in Bitcoin mining than a classical one. Also, it is worth noting that if
blockchain does not increase its difficulty in response to increased hashing power,
that would lead to increased rate of orphaned blocks.

Obviously, Bitcoin can't migrate to quantum PoW, miners won't get such hardware in time.
Tstar
Hero Member
*****
Offline Offline

Activity: 784



View Profile
November 03, 2015, 10:08:42 AM
 #16

Come-from-Beyond,
so let's assume you have a quantum computer that you can use to mine BTC.
Can you use it to disrupt the mining process or not?

I don't understand because before you said that such a computer could
Quote
A quantum computer would rape Bitcoin blockchain with 1000 blocks generated within a minute.

and then quoting that pdf you said
Quote
Obviously, Bitcoin can't migrate to quantum PoW, miners won't get such hardware in time.

So, going back to what I stated at the beginning of this post, if you have a quantum computer could you do that right now or not?


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



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
























iQeon
.FACEBOOK  ◆  TWITTER  ◆  VK  ◆  INSTAGRAM  ◆  TELEGRAM.
.
REDDIT   ◆   GOOGLE+   ◆  STEEMIT  ◆   SLACK   ◆   LINKEDIN.












USB-S
Sr. Member
****
Offline Offline

Activity: 364



View Profile
November 03, 2015, 10:14:08 AM
 #17

A quantum computer wouldn't be doing that to a chain using a hash function that uses quantum cryptography, or is that actually your assertion? That quantum computing is a magical panacea?

From http://188.138.57.93/tangle.pdf:

Quote
It is known that a (today still hypothetic) sufficiently large quantum computer can
be very efficient for handling problems where only way to solve it is to guess answers
repeatedly and check them. The process of finding a nonce in order to generate a
Bitcoin block is a good example of such a problem. As of today, in average one must
check around 2^68 nonces to find a suitable hash that allows to generate a block. It
is known (see e.g. [7]) that a quantum computer would need Θ(√N) operations to
solve a problem of the above sort that needs Θ(N) operations on a classical computer.
Therefore, a quantum computer would be around √(2^68) = 2^34 ≈ 17 billion times more
efficient
in Bitcoin mining than a classical one. Also, it is worth noting that if
blockchain does not increase its difficulty in response to increased hashing power,
that would lead to increased rate of orphaned blocks.

Obviously, Bitcoin can't migrate to quantum PoW, miners won't get such hardware in time.
That pdf is a good read, I guess we just have to jump boats to PoS or other protocol before quantum computers hit the mining scene.
But then again how would we secure other protocols if quantum computers could just brute force them?
Come-from-Beyond
Legendary
*
Online Online

Activity: 1792

Newbie


View Profile
November 03, 2015, 10:24:33 AM
 #18

Come-from-Beyond,
so let's assume you have a quantum computer that you can use to mine BTC.
Can you use it to disrupt the mining process or not?

Yes, with a QC you can invalidate last 1000 blocks, generate 20000 empty blocks and stop mining leaving the others with 20-year block times.
shorena
Legendary
*
Offline Offline

Activity: 1400


ALL escrow is signed! https://keybase.io/verify


View Profile WWW
November 03, 2015, 10:58:10 AM
 #19

For easy reference, [7] from the above linked paper can be found here -> https://dl.acm.org/citation.cfm?doid=261342.261346

Tstar
Hero Member
*****
Offline Offline

Activity: 784



View Profile
November 03, 2015, 11:41:43 AM
 #20

Come-from-Beyond,
so let's assume you have a quantum computer that you can use to mine BTC.
Can you use it to disrupt the mining process or not?

Yes, with a QC you can invalidate last 1000 blocks, generate 20000 empty blocks and stop mining leaving the others with 20-year block times.

Ok, that is clear.
Coming back to wait I said at the beginning I would be really afraid if such a thing exists now since it could disrupt the functioning of everything we rely on nowadays, and as I said, bitcoin would be our last concern.
crazy

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



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
























iQeon
.FACEBOOK  ◆  TWITTER  ◆  VK  ◆  INSTAGRAM  ◆  TELEGRAM.
.
REDDIT   ◆   GOOGLE+   ◆  STEEMIT  ◆   SLACK   ◆   LINKEDIN.












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