On Mon, Jan 31, 2022 at 8:13 AM, Stefan Claas<stefan@ctemplar.com> wrote: --------- Original Message ---------- On Sun, January 30, 2022 at 8:15 PM, grarpamp@gmail.com wrote: On 1/30/22, jim bell wrote:
Quantum Computing Threatens Everything — Could it be Worse Than the Apocalypse?
Jim Bell's comment: Headline sounds overblown, but...
What are peoples current estimated years for when QC will... a) Break some of today's modern yet non-PQC cryptosystems?
I seem to recall that cryptosystems based on multi-dimensional lattices are thought to be quantum-resistant. https://en.wikipedia.org/wiki/Lattice-based_cryptography?wprov=sfla1
From that: "Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems, which could, theoretically, be easily attacked by a quantum computer, some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently."(End of quote) An RSA-type system depends on the difficulty of factoring a huge composite number, but I think that involves only one 'degree of freedom'. That is, as your guess for one factor goes up, the other goes down. However, finding distances in a large-dimensional lattice might involve as many degrees of freedom as dimensions, or maybe (dimensions minus 1). Perhaps this is what would defeat quantum calculations.