SoylentNews is people
SoylentNews
from the for-sufficiently-large-polynomials dept.
From Quantamagazine
Digital security depends on the difficulty of factoring large numbers. A new proof shows why one method for breaking digital encryption won't work.
Virtually all polynomials of a certain type are "prime," meaning they can't be factored.
The proof has implications for many areas of pure mathematics. It's also great news for a pillar of modern life: digital encryption.
The main technique we use to keep digital information secure is RSA encryption. It's a souped-up version of the encryption scheme a seventh grader might devise to pass messages to a friend: Assign a number to every letter and multiply by some secretly agreed-upon key. To decode a message, just divide by the secret key.
Quite a statement by the researchers. This allegedly makes RSA encryption "quantum proof", and if so means that classical encryption may still be with us long after quantum computing arrives. Given that quantum systems require expensive entanglement setups, it may also mean that a cheap encryption method may stay viable.
Paper: Irreducibility of random polynomials of large degree
(Score: 1, Interesting) by Anonymous Coward on Thursday December 20 2018, @06:20PM
A maybe not-so-well-known fact about RSA is that its security does not depend directly on the difficulty of integer factorization at all, but rather a different problem (called the "RSA problem").
Given M, e, and C, where
- M is the product of two (unknown) primes,
- gcd(e, φ(M)) = 1, and
- C ≡ P^e (mod M);
Find P.
(i.e., the RSA problem is finding e'th roots of C, mod M).
We know that, if the factors of M are known, then the RSA problem can be solved efficiently. That implies that factoring M is "at least as hard as" solving the RSA problem.
However the reverse remains an open problem: is the RSA problem "at least as hard as" factoring M? To prove that one must demonstrate that an efficient solution for the RSA problem implies an efficient solution to find M's factors. So in the absense of such a proof, it may be the case that someone finds a way to break RSA that doesn't involve factoring at all!