Quantum computers will break the encryption that protects the internet

Re:Quantum computers will break the encryption that protects... by elbybasolis on Saturday October 20, 2018 @05:40AM (#18262522)

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?

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by thornjm on Saturday October 20, 2018 @05:45AM (#18262541)

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

You can see round one submissions on the left.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by elbybasolis on Saturday October 20, 2018 @06:04AM (#18262594)

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.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by daveFNbuck on Saturday October 20, 2018 @11:37AM (#18263732)

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.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by daodedickinson on Saturday October 20, 2018 @07:33AM (#18262783)

Only after the real powers are done using the exploit.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by keeperofdakeys on Saturday October 20, 2018 @05:51AM (#18262560)

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.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by xucheng on Saturday October 20, 2018 @06:36AM (#18262659)

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

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by keeperofdakeys on Saturday October 20, 2018 @06:54AM (#18262695)

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

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by bsaul on Saturday October 20, 2018 @05:43AM (#18262530)

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

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by throwaway2048 on Saturday October 20, 2018 @05:58AM (#18262580)

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.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by elbybasolis on Saturday October 20, 2018 @05:49AM (#18262552)

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.

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by rollcat on Saturday October 20, 2018 @06:50AM (#18262685)

> 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).

[ Parent | on HN ]

Re:Quantum computers will break the encryption that protects... by imranq on Saturday October 20, 2018 @11:40AM (#18263747)

It would still take linear time to determine the prime factors

[ Parent | on HN ]