Re: Um, guys, get your story straight
One relevant question is whether 4096/8192/more bit RSA will still be safe
Depends entirely on your threat model. As phrased, it's a meaningless question.
Today, monoalphabetic substitution is "safe" when it's used for data that no one wants to put any effort into decrypting.1 A Post-It on the monitor is "safe" if no attacker ever looks at it.
The vast majority of asymmetric encryption today is HTTPS. The vast majority of HTTPS is uninteresting to everyone but the systems legitimately using the connection. We employ it widely because that's easier than trying to ensure it's used on the rare occasions where it might be required.
But then, as far as I understand, much of the strength of the quantum-resilient algorithms lies in the size of their keys
Nope. At any rate, that's not what makes PQC "post-quantum". Obviously key length has to be sufficient to make classical attacks infeasible.
PQC algorithms are quantum-resistant because they employ problems for which there are no known algorithms in complexity class BQP (which aren't also in P, since BQP is a superset of P, obviously). All of this is somewhat speculative; we have some proofs about what isn't in BQP under common assumptions,2 and there are all sorts of intermediate results and strong reasons to believe this and that and so forth. So problems like finding the shortest vector in a lattice that satisfies some requirement, or learning a ring using a set of inputs into which errors have been injected, and so on are used, because there are good reasons to believe these are not tractable even for general quantum computers.
1Yes, comparing symmetric to asymmetric encryption. The larger point stands.
2For example, assuming P≠NP, then there's nothing faster (by complexity) than Grover's algorithm in BQP for doing what Grover's algorithm does.
Biting the hand that feeds IT
