Hacker News Reader

Comment by elbybasolis | Hacker News Reader

I’m concerned with the ability of conventional computers to keep up with cryptography in the quantum age of computation. But can’t we just jack up the current algorithms to have higher order problem sets to solve? In other words can’t we turn something like a SHA-256 into a SHA-2048 and take a hit on the time complexity to generate such cryptographic (in this case a hashing algorithm) products? Can’t we just scale up the problem size and assume that the solution will be exponentially more difficult to solve?

View on HN

The world is working on it: https://csrc.nist.gov/projects/post-quantum-cryptography

You can see round one submissions on the left.

I see this playing out similarly to the Y2K situation. There will be a race to upgrade all cryptographic security measures currently in place to handle the new power in computation. In the beginning however those who would have access to such power would make a mint supplying a service (AWS and the like) to compute these products.

Y2K was a trivial issue that everyone knew how to fix for decades. Computing was important to how the world ran, but not nearly as ubiquitous as it is now. It still took a large effort to upgrade everything for Y2K.

Only after the real powers are done using the exploit.

Cryptography is based on "hard problems", something that is easy to solve one way, but hard the other way. Quantum computers provide algorithms that can severely break some of these (namely RSA with Shor's Algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm), and speed up all the others (namely Grovers Algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm). So it's not possible to simply increase bits to ensure algorithms are still secure, but it will work for most of them.

On the bright side there is also a branch of cryptography called post-quantum cryptography, which is a collection of algorithms designed to be more resistant in the face of quantum computers https://en.wikipedia.org/wiki/Post-quantum_cryptography.

FYI, Elipical Curve Cryptography is also broken with the quantum computer using the same Shor’s algorithm.

Thanks, I didn't realise that. I need to do some more reading about the topic.

I'm not an expert at all, but fwiu quantum computers makes cryptographic encryption a linear problem.

This is not true, symmetric block ciphers (AES) are at worst about halved in strength.

Asymmetric crypto that depends on prime factorization or discreet logarithms (such as RSA and EDSA) are indeed fatally weakened by large enough quantum computer, but it is not a problem for other mathematically one way "hard" crypto constructs like hash trees or the McEliece cryptosystem.

In that case can we start computing cryptographic products with quantum computers such that there is no gap? If we reduce the time complexity of factoring a prime number to linear wouldn’t we be able to produce larger cryptographic products? Effectively going back to where we started but with more computing power? Surely this would require easy access to quantum computation to be practical and thus a gap in power, but necessity would drive the market to make this type of power more mainstream.

> In that case can we start computing cryptographic products with quantum computers such that there is no gap?

QC solves one kind of problems, that are hard for classical computers, but not another (see all the links to post-quantum crypto in the comments). OTOH there will be a very large window during which QC will be cheap enough to rent by the hour on AWS, but equipping every lightbulb with a QC will be prohibitively expensive (think current GPU prices).

It would still take linear time to determine the prime factors

Reply on news.ycombinator.com