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 an hour ago | parent | next [-]

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)

▲

Cider9986 2 hours ago | parent | prev | next [-]

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

	▲	kibwen 37 minutes ago \| parent \| next [-]
		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.
	▲	some_furry an hour ago \| parent \| prev [-]
		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.

▲

zeroonetwothree an hour ago | parent | prev | next [-]

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

▲

kibwen an hour ago | parent | prev [-]

> 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 an hour ago \| parent \| next [-]
		Isn’t one time pad just a simple version of secret sharing?
	▲	chadgpt3 an hour ago \| parent \| prev [-]
		Those are the only two known algorithms that have this property.