3 ms·

It was never mentioned in the article so I just looked it up on Wikipedia, but Elliptic curve cryptography is not secure against future quantum computers.

er4hn 6y ago
Neither is RSA. Most present day asymmetric crypto has its strength (amount of computing required to break it) significantly reduced by quantum computers. The solution is quantum safe algorithms which are a developing field. Symmetric algorithms such as AES can have their strength reduced as well, but (I have no sources to cite) I believe this reduces it from 256-bit to 128-bit. At 128 bits of security it is still widely considered safe to use.
- jesboat 6y ago
  The prototypical quantum attack for symmetric crypto is Grover's algorithm [https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm] which finds "the unique input to a black box function that produces a particular output value". Whereas a classical computer would need to check an average of N/2 values (where N is the size of the domain), Grover's takes O(sqrt(N)). When you're measuring "bits of security", you say N=2^k, so a classical computer would take O(2^k) and Grover's would take O(sqrt(2^k)) = O(2^(k/2)), or a reduction from k bits of security from a classical adversary to k/2 bits of security from a quantum adversary. Hence the wisdom that AES-256 is approximately as secure post-quantum as AES-128 is to classical methods.
  - er4hn 6y ago
    fantastic explanation! Thanks so much for taking the time to write this up.
upofadown 6y ago
Yeah and the currently known quantum resistant algorithms have huge keys. Much larger than RSA. So we shouldn't get too dependent on short keys when designing protocols...
bannerts 6y ago
So with bitcoin and some other uses the actual public ecdsa key is hidden behind some hashing such that you gotta invert the hash function to get to the ecdsa public key before cracking. Also that's not a one to one but... Can you crack sha256 with quantum computing too?
- tylersmith 6y ago
  Not as far as we know. This is nice but not perfect. Eventually a QC will be able to reverse a public key fast enough to double spend in-flight transactions before they're finalized.

er4hn 6y ago

Neither is RSA. Most present day asymmetric crypto has its strength (amount of computing required to break it) significantly reduced by quantum computers. The solution is quantum safe algorithms which are a developing field. Symmetric algorithms such as AES can have their strength reduced as well, but (I have no sources to cite) I believe this reduces it from 256-bit to 128-bit. At 128 bits of security it is still widely considered safe to use.

jesboat 6y ago
The prototypical quantum attack for symmetric crypto is Grover's algorithm [https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm] which finds "the unique input to a black box function that produces a particular output value". Whereas a classical computer would need to check an average of N/2 values (where N is the size of the domain), Grover's takes O(sqrt(N)). When you're measuring "bits of security", you say N=2^k, so a classical computer would take O(2^k) and Grover's would take O(sqrt(2^k)) = O(2^(k/2)), or a reduction from k bits of security from a classical adversary to k/2 bits of security from a quantum adversary. Hence the wisdom that AES-256 is approximately as secure post-quantum as AES-128 is to classical methods.
- er4hn 6y ago
  fantastic explanation! Thanks so much for taking the time to write this up.

upofadown 6y ago

Yeah and the currently known quantum resistant algorithms have huge keys. Much larger than RSA. So we shouldn't get too dependent on short keys when designing protocols...

bannerts 6y ago

So with bitcoin and some other uses the actual public ecdsa key is hidden behind some hashing such that you gotta invert the hash function to get to the ecdsa public key before cracking. Also that's not a one to one but... Can you crack sha256 with quantum computing too?

tylersmith 6y ago
Not as far as we know. This is nice but not perfect. Eventually a QC will be able to reverse a public key fast enough to double spend in-flight transactions before they're finalized.