81–90 of 127 posts
Earlier quoted context omitted.
We are within 20 years of scalable quantum computers already.
The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?
Earlier quoted context omitted.
If scalable quantum computers do not exist, we do not need PQC.
Hemomorphic encryption is not the same thing as post quantum crypto?
Post quantum crypto is cryptography that cannot be broken by a quantum computer. This is rather nebulous, since we haven't yet discovered all possible algorithms that can run on quantum computers. Before you know it, someone comes along and finds a new efficient algorithm for quantum computers that breaks something thought to be post-quantum. Which is what is happening here - if the results stand up under scrutiny.
Sidenote: it may turn out that any crypto scheme which supports some operation on ciphertexts that translates into an operation on the plaintexts is quantum-resilient (or, vice versa, quantum-vulnerable). But tgat would require a fornal proof.
Earlier quoted context omitted.
We are within 20 years of scalable quantum computers already.
The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?
Earlier quoted context omitted.
The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?
The last time I checked they even cheated to factor fifteen
Earlier quoted context omitted.
I didn’t say the runtime did I? The approximation ratio went from exponential to polynomial noise ratio. This just went from 2^n to n^4.5 and everyone seems to say “oh this is fine”.
The attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.
Earlier quoted context omitted.
The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?
Significantly larger numbers than 15 have been factored [1] but not using Shor's algorithm. Shor's algorithm is particularly sensitive to noise/errors in your quantum computer and isn't going to be useful unless we get a properly error corrected machine working. The algorithms used in [1] are considerably less fancy (with worse asymptomatic performance) but are more resilient to noise. [1] https://arxiv.org/abs/2012.…
Earlier quoted context omitted.
The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?
Significantly larger numbers than 15 have been factored [1] but not using Shor's algorithm. Shor's algorithm is particularly sensitive to noise/errors in your quantum computer and isn't going to be useful unless we get a properly error corrected machine working. The algorithms used in [1] are considerably less fancy (with worse asymptomatic performance) but are more resilient to noise. [1] https://arxiv.org/abs/2012.…
Earlier quoted context omitted.
The last time I checked they even cheated to factor fifteen
You should check again. Numbers like 1099551473989 have been factored successfully by now. The arxiv link in the sibling post is a good start.
Earlier quoted context omitted.
Major systems and big companies like Google are already mid-transition to PQC. So it is alarming.
Their deployment is additive. You would need to break both the PCQ and classical schemes, so they’d be unaffected here.
The NIST process has been running for 7 years, though they do have a few "non-lattice" schemes waiting for a 4th round of standardization: the code-based schemes Classic McEliece, BIKE and HQC. We could switch over to those, and the work to add crypto-agility to protocols would not be wasted, but the work on lattice software and hardware would be largely wasted.
Also, error-correcting codes are also solving short-vector problems in a lattice! But since the lattice has a different shape maybe it would be fine? After codes the list gets pretty thin... like there's CSIDH, but it's very slow, has partial quantum attacks, and it isn't very trusted after SIKE got broken in half.