If you don't mind a one terabyte public key. https://eprint.iacr.org/2017/351.pdf
Re:Willow, Our Quantum Chip
by adgjlsfhk1 on Tuesday December 10, 2024 @10:30AM
(#42377748)
also that paper (IMO) is ridiculously conservative. Just using 1GB keys is plenty sufficient since it would require a quantum computer with a billion bits to decrypt.
How long does it take to generate a key that big? What probabilities do you need to put on generating a composite number and not a prime? Does the prime need extra properties?
Re:Willow, Our Quantum Chip
by adgjlsfhk1 on Tuesday December 10, 2024 @08:59PM
(#42383905)
Based on https://eprint.iacr.org/2017/351.pdf it would be about 1900 core hours (but I'm pretty sure optimized implementations could bring it down a bunch). No extra properties needed and moderate probability is sufficient.
Although I know it’s an apocryphal quote, I am reminded of “640K should be enough for anybody.”
The Intel 4004, in 1971, had only 2,250 transistors.
A handful of qubits today might become a billion sooner than you think.
Re:Willow, Our Quantum Chip
by adgjlsfhk1 on Tuesday December 10, 2024 @09:18PM
(#42384012)
it took until 2011 before Sandy bridge cracked 2 billion. If we get 40 years of quantum resistance from 1GB RSA, that would be pretty great.
There are several choices with scaling RSA too, you can push the primes which slows generation time considerably. Or the more reasonable approach is to settle on a prime size but use multiple of them (MP-RSA). The second approach scales indefinitely. Though it would only serve a purpose if you are determined to hedge against the accepted PQC algorithms (Kyber/MLKEM, McEliece) being broken at some point.