[tsimionescu]

By this standard, there is no current encryption method (except for pre-shared one time pads when used correctly) that is known to be unbreakable. For example, it is not proven that prime factoring can't be done much more efficiently on a classical computer - for all we know, it's possible that tomorrow someone will come up with a novel algorithm that can break RSA in just a small number of operations. Same is true for elyptic curves - we don't have any mathematical proof that it's impossible for a much better algorithm than the currently known ones is possible.

However, just like for RSA we know that the problem of efficient integer factoring has been worked on for a long time with no progress, the same is true for quantum computing. We have been trying to figure out quantum algorithms for a great number of problems that are hard for classical computers for a long time now, and we haven't been able to, except for the ones that we have. Mathematicians have also developed certain intuitions for which problems have characteristics that make them potentially easier to solve on a QC and which don't.

In general, just like with P=NP?, we haven't proven yet if BQP, roughly the class of problems which have efficient QC versions, is equal or not to P, the class of problems that can be efficiently solved on a classical computer; and we also don't know if BQP=NP.

So yes, there is at least a theoretical possibility that the problems used for creating post-quantum encryption will turn out to be in BQP, will turn out to have an efficient quantum algorithm that solves them. But that would come from mathematical research, it is entirely unrelated to creating and tinkering with actual quantum computers. The math of quantum algorithms is currently far ahead of the engineering and physics on building the actual computers.

[connorboyle]

Has there been "no progress" on classical prime factorization? What about the AKS primality test, a polynomial-time algorithm to test the primality of a number, published in 2002? (This is not my field of expertise; I'm genuinely curious if there's a good reason to discount this as progress towards efficient prime factorization)

[mswphd]

Primality testing was essentially solved in the 70s with Miller-Rabin. AKS made that (randomized) algorithm deterministic, albeit at much higher (polynomial) running-time.

For your overall question, the current record-holders for integer factorization wrote a paper on this a few years ago that is probably a good reference

https://hal.science/hal-03691141/file/cryptography.pdf

The (rough) outline of the paper is that

1. theoretically there's been no progress on factoring in ~30 years

2. practically, there have been both improved hardware + efficient implementations driving the progress. They estimate that current nation-states can (classically) break RSA-1024. The cost would be approximately 500,000 core-years of computation. At current cloud prices this is doable on aws for < $1B.

3. attacks against factoring use a technique ("index calculus") that can also be used to attack finite-field discrete logarithm. There were significant advances on that problem in the 2010s (at least for certain parameters, namely the "small characteristic" setting). An easy way to communicate this is that the RSA factoring record is ~830 bits, while the binary-field discrete logarithm record is > 30,000 bits. These significant advances have not been able to be ported over to factoring, nor have they been ported over to medium/large-characteristic discrete logarithm. It is a (very upsettingly) large open question of whether similar-magnitude improvements are possible more generally for index calculus algorithms.

[cyberax]

> Has there been "no progress" on classical prime factorization?

Not recently. The primality tests don't really help all that much. We already had polynomial tests that are really fast since the 70-s.

Think about this idea: the output of the counting function for the number of primes ("Euler's totient function") lies almost on the logarithmic curve, and we can compute logarithms quickly to any precision. So we can easily find the general area of the curve that should contain the current prime. And then we can quickly test if the given number is in fact the prime number within it.

This is probabilistic because the prime distribution is not _strictly_ logarithmic. We can imagine that by computing a logarithm we might end up in the next "bucket" and check for the wrong prime.

The fascinating part is that zeroes of the Riemann zeta function encode these corrections on top of the logarithmic curve. If the Riemann hypothesis is correct, then these corrections are _bounded_ and we simply can not end up in a different "bucket" by accident.

[Cider9986]

Would post-quantum encryption also be harder for regular computers to crack?

[mswphd]

It's not particularly related. We have efficient quantum algorithms for RSA and discrete logarithms. Both are solved by viewing them as instances of the "hidden subgroup problem" over an abelian group.

Some well-known other problems are also HSP instances over non-abelian groups, for example

1. the learning with errors assumption (the main PQ thing people like) is a HSP instance over the dihedral group, and

2. graph-isomorphism is a HSP instance over the symmetric group.

LWE appears to be quite hard classically (SOTA attacks are 2^{~0.3n} time and exponential memory). Graph isomorphism is a famously easy problem outside of P, namely it is in quasi-polynomial time. So the fact that both are not in BQP doesn't say much about their relative classical difficulty.

[some_furry]

The international standardization effort that led to ML-KEM and ML-DSA focused both on classical attacks (regular computers) and quantum attacks.

There were 5 levels being considered for each submission.

Level 1 - at least as difficult to attack as AES-128 (block cipher)

Level 2 - at least as difficult to attack as SHA-256 (hash function)

Level 3 - at least as difficult to attack as AES-192 (block cipher)

Level 4 - at least as difficult to attack as SHA-384 (hash function)

Level 5 - at least as difficult to attack as AES-256 (block cipher)

The security of attacking an N-bit block cipher is morally congruent to a birthday collision against a {2N}-bit hash function. With some caveats: https://soatok.blog/2024/07/01/blowing-out-the-candles-on-th...

ML-DSA-44 (smallest parameter set) targets Level 2 for signatures.

ML-KEM-768 targets Level 3 for KEMs.

[kibwen]

This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.

[tptacek]

There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.

[mswphd]

With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme.

In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorithm for a particular one (SIVP_\gamma), if he could only obtain an efficient quantum algorithm for a certain novel/simple problem (the learning with errors problem). He was unable to do this, so instead framed his result as a reduction from SIVP_\gamma to LWE, and additionally showed how one can build cryptography from LWE. This is essentially the contents of his 2005 LWE paper, for which he later got the Godel prize.

So in a quite literal sense, LWE is the byproduct of a failed search for a quantum algorithm for SIVP_\gamma, and was therefore "post-quantum from the start". Regev mentions this as his initial motivation for looking into LWE on page 4 of his LWE survey

https://cims.nyu.edu/~regev/papers/lwesurvey.pdf

[tptacek]

I didn't say Kyber/MLKEM or even LWE was a contender vs. curves in the 1990s; that wouldn't have made sense. I said lattice cryptography. As I understand it, our formal understanding of LWE is actually better than that of the original NTRU problem.

I liken this to the original Certicom proposals from the 1990s versus Curve25519. There's a diversity of curve approaches (binary field Koblitz vs prime-field curves, etc; things were wackier in the early aughts too) just as there is a diversity of implementation strategies for lattice KEMs.

The notion I'm hostile to is the one that poses lattices as moon math.

[mswphd]

Yes I know. That was what my initial paragraph was about.

And yes, our formal understanding of LWE is much better than the original NTRU problem. NTRU itself

1. admits non-trivial attacks if the ciphertext modulus is too large, as well as

2. had a signature algorithm (NTRU-sign) that was completely broken.

Lattice-based signatures were actually a relatively thorny thing to develop. The first non-broken lattice-based signature was proposed in 2009 iirc. I think this was after Gentry developed fully homomorphic encryption (though his initial scheme is now broken as well). Even in modern treatments, it's a fair statement to say that constructing a secure lattice-based signature is of similar complexity to constructing a secure fully homomorphic encryption scheme (although there are some relatively-simple ones these days).

You can make stronger statements about our understanding of LWE though. I would say that it is relatively uncontentious to state that LWE and elliptic-curve DLOG are the two problems we understand the best theoretically in public-key cryptography, and it is not particularly close. The only remote contenders would be

1. finite-field DH, though arguably our understanding of this is still not great (are CDH and DDH equivalent? well sort of, but the details become quite messy).

2. RSA. There are still many basic questions about it that are wide-open, namely is it equivalent to factoring? There are other questions that are unknown as well, for example how hard it is to attack. "Everyone knows" that you just use GNFS, with L[1/3, c] complexity. But other index calculus attacks were improved to L[1/4, c] complexity in the 2010s. Can those attacks extend to factoring? Things get even worse when you consider the veritable zoo of attacks on RSA when you get a small detail wrong (Coppersmith-style attacks in the presence of some leaked key bits, improved attacks depending on what particular RSA exponents you've chosen, etc).

I think you could even go farther and say that we understand LWE better than elliptic curve DLOG. This would of course be contentious, but is meant to communicate just how good of a (theoretical) understanding we have of the LWE problem.

Of course, the main point in EC DLOG's favor is that, when correctly parameterized (which is a thorny point itself, but mostly fine these days), there are the generic group lower bounds (2^n time, poly space), and attacks have never beaten them. While for LWE attacks have always been of the form (exp time, exp space) (or 2^{n\log n} time, poly space), but the exponent in the "exp"'s doesn't have as clean of a conjectured lower bound, and has been reduced some over time.

[zeroonetwothree]

I would find BQP = NP ≠ P more surprising than P = NP. But maybe it’s just me :)

[kibwen]

> except for pre-shared one time pads when used correctly

The relevant property here is known as "information-theoretic security", and I'm not sure if one-time pads are the only way to achieve it, e.g. Shamir's secret sharing also has this property (although the use case is slightly different): https://en.wikipedia.org/wiki/Information-theoretic_security

[zeroonetwothree]

Isn’t one time pad just a simple version of secret sharing?

[kibwen]

I would say that SSS is a generalization of OTP, but OTP in practice is so dramatically and unbelievably simpler than SSS that it's not practically useful to consider it as "just" a special-case of SSS. Which is to say, if you were implementing OTP, you would not just implement SSS and then set the right parameters; you would use an entirely distinct implementation.

[mswphd]

you can sort-of view it that way, but it's not particularly useful. There are settings where you can view (steps of) a cryptographic algorithm as applying a one-time pad with a pseudorandom pad (say counter-mode encryption for the most obvious example, though it appears elsewhere as well).

Alternatively, shamir's secret sharing can be extended to threshold settings pretty easily. So you can write a generalized scheme where you only recover things when "enough people" (but perhaps not everyone) tries to reconstruct. This generalized scheme doesn't look particularly like the one-time pad.

So they end up coinciding in the 2-party case over F2 but it seems to be mostly a coincidence.

[chadgpt3]

Those are the only two known algorithms that have this property.