Hacker News Reader

Comment by kefka | Hacker News Reader

In other words, it gives a newfound impetus to follow through with converting to Curve25519 cryptosystems.

It's what we believe to be quantum computer secure.

ECC (including Curve25519) is not secure in a quantum computing world, Shor's algorithm solves discrete log efficiently.

I am not a deep expert in this field but there is a lot of work in post-quantum crypto that derives security from the hardness of some lattice-based problems instead of discrete log (E.g. New Hope being used in an experiment in Chrome is based on RLWE, I think).

In case people want to know more:

https://pqcrypto.org/

(down right now, so here's the cache: https://webcache.googleusercontent.com/search?q=cache:1JkIi2...

)

can you explain this more? What is the affect on cryptography. Thanks a lot

Lots of encryption is based on the prime factorisation being hard to do. Specifically, that it scales significantly as you slightly increase the key size.

There's a quantum algorithm (Shor's algorithm) that doesn't scale quite so badly as the numbers get bigger. That means that with a fast quantum computer you could solve this specific problem much much more quickly than is possible on a classical computer.

However, other crypto types (elliptical curve cryptography EDIT - ECC is not a type that meets these criteria, see the responses to me below) doesn't depend on prime factorisation, but other things. Those other things have no known nice fast quantum algo. I'm not sure where this sits on "there's provably no fast quantum algorithm" and "we don't currently know of one" however (EDIT - ECC is in the "there is definitely a fast quantum algorithm" category!).

Most generally, quantum computers are not just fast regular computers. For some (not all) problems, they scale better for solving the problem. So for example, finding an item in an unordered list. If you have 100 items, you need to on average check 50 items to find it on a regular computer, and if you have a million items you need to check 500,000 items. A quantum computer can run 10 iterations to solve find something out of 100, but just 1000 to find something in a million. Other differences scale better or worse.

Quick simple overview: Some problems that we thought were intractable turn out to be quite possible on quantum computers. But not every problem.

I tried to keep this simple as my understanding is also quite simple, and I don't want to post things that are wrong.

> However, other crypto types (elliptical curve cryptography) doesn't depend on prime factorisation, but other things. Those other things have no known nice fast quantum algo.

This is wrong. https://en.m.wikipedia.org/wiki/Elliptic_curve_cryptography#...

Thank you, I didn't know this. I've updated my post to point out where I'm wrong, hopefully that covers the important bits.

For your clarification, Shor's algorithm just involves encoding every possible value of a function (say f(x) for all values of x) into a bunch of qubits, taking the fourier transform, and measuring, which will tell you the period of that function (some r such that f(x + r) = f(x) for all x). Thus, you can find the period of any function that you can define a fourier transform for. For breaking RSA, your function is on the domain of integers modulo n, so you use the discrete fourier transform. You can also define a fourier transform for functions on the domain of an elliptic curve as well! In fact, any finite abelian group has a unique definition of fourier transform (see https://en.wikipedia.org/wiki/Pontryagin_duality for some of the math behind it). That means we can't just upgrade our crypto to some more complex curve space, because all of them will be vulnerable to Shor's algorithm.

The mathematics behind Shor's algorithm is actually a really interesting read if you enjoy pure, abstract algebra and topology.

We know how to do a lot of number theory stuff quickly on quantum computers that we don't know how to do quickly on classical computers. Some of those things underpin all asymmetric key algorithms in use today. We have to develop asymmetric key algorithms that don't use things we know how to compute quickly on a quantum computer.

Reply on news.ycombinator.com