4 ms·

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 a

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?

bsaul 8y ago
I'm not an expert at all, but fwiu quantum computers makes cryptographic encryption a linear problem.
- elbybasolis 8y ago
  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.
  - rollcat 8y ago
    > 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).
  - imranq 8y ago
    It would still take linear time to determine the prime factors
- throwaway2048 8y ago
  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.
thornjm 8y ago
The world is working on it: https://csrc.nist.gov/projects/post-quantum-cryptography https://csrc.nist.gov/projects/post-quantum-cryptography You can see round one submissions on the left.
- elbybasolis 8y ago
  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.
  - daodedickinson 8y ago
    Only after the real powers are done using the exploit.
  - daveFNbuck 8y ago
    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.
keeperofdakeys 8y ago
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 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 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 https://en.wikipedia.org/wiki/Post-quantum_cryptography.
- xucheng 8y ago
  FYI, Elipical Curve Cryptography is also broken with the quantum computer using the same Shor’s algorithm.
  - keeperofdakeys 8y ago
    Thanks, I didn't realise that. I need to do some more reading about the topic.

bsaul 8y ago

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

elbybasolis 8y ago
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.
- rollcat 8y ago
  > 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).
- imranq 8y ago
  It would still take linear time to determine the prime factors
throwaway2048 8y ago
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.

thornjm 8y ago

The world is working on it: https://csrc.nist.gov/projects/post-quantum-cryptography https://csrc.nist.gov/projects/post-quantum-cryptography You can see round one submissions on the left.

elbybasolis 8y ago
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.
- daodedickinson 8y ago
  Only after the real powers are done using the exploit.
- daveFNbuck 8y ago
  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.

keeperofdakeys 8y ago

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 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 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 https://en.wikipedia.org/wiki/Post-quantum_cryptography.

xucheng 8y ago
FYI, Elipical Curve Cryptography is also broken with the quantum computer using the same Shor’s algorithm.
- keeperofdakeys 8y ago
  Thanks, I didn't realise that. I need to do some more reading about the topic.