4 ms·

> Large-scale quantum computers are capable of breaking all of the common forms of asymmetric cryptography used on the Internet today. Is that actually true?

> Large-scale quantum computers are capable of breaking all of the common forms of asymmetric cryptography used on the Internet today. Is that actually true? I was under the impression that there exists quite a large class of trapdoor functions (functions that are one-to-one maps, cheap to compute but whose reciprocal is crazy expensive to compute without some sort of oracle-like information) that could not be attacked by quantum computers? Are there no asymmetric algorithm that are impervious to QC in use today on the internet? Or are they specifically talking about the fact that RSA-style algos are vulnerable?

uv-depression 3y ago
Symmetric algorithms are largely safe-ish; the best known attack is Grover's algorithm, which reduces the effective bits by half (runs in O(sqrt(N)) evaluations). Shor's algorithm is a polynomial-time solution to the discrete logarithm problem, which has traditionally been the basis for asymmetric cryptography.
- ur-whale 3y ago
  > Shor's algorithm is a polynomial-time solution to the discrete logarithm problem Yes, exactly, and the discrete logarithm problem is but a narrow sliver of a much larger class of trapdoor functions, most of which don't have the equivalent of Shor's algorithm to be attacked with. That's precisely the point I was trying to make.
jlokier 3y ago
A trapdoor function isn't the same as asymmetric cryptography. Trapdoor functions can be used to build asymmetric cryptography, i.e. public-key encryption and signing. In general, hash-based asymmetric cryptography can do it with any hash you consider strong enough, such as SHA-256. Unfortunately the keys and signatures tend to be large, which is the problem the article is talking about. That's why they are not in common use. For example, although SHA-256 is 256 bits, which is considered small, the keys and signatures of asymmetric cryptography built with SHA-256 are very much larger. Making the keys and signatures smaller, yet secure and fast enough, is currently state of the art research.

uv-depression 3y ago

Symmetric algorithms are largely safe-ish; the best known attack is Grover's algorithm, which reduces the effective bits by half (runs in O(sqrt(N)) evaluations). Shor's algorithm is a polynomial-time solution to the discrete logarithm problem, which has traditionally been the basis for asymmetric cryptography.

ur-whale 3y ago
> Shor's algorithm is a polynomial-time solution to the discrete logarithm problem Yes, exactly, and the discrete logarithm problem is but a narrow sliver of a much larger class of trapdoor functions, most of which don't have the equivalent of Shor's algorithm to be attacked with. That's precisely the point I was trying to make.

jlokier 3y ago

A trapdoor function isn't the same as asymmetric cryptography. Trapdoor functions can be used to build asymmetric cryptography, i.e. public-key encryption and signing. In general, hash-based asymmetric cryptography can do it with any hash you consider strong enough, such as SHA-256. Unfortunately the keys and signatures tend to be large, which is the problem the article is talking about. That's why they are not in common use. For example, although SHA-256 is 256 bits, which is considered small, the keys and signatures of asymmetric cryptography built with SHA-256 are very much larger. Making the keys and signatures smaller, yet secure and fast enough, is currently state of the art research.