Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum Algorithms for Lattice Problems

eprint.iacr.org

Post reply on HN
Print view View original

61–70 of 127 posts

Re: Quantum Algorithms for Lattice Problems

#61

Post by Ar-Curunir »

da-bacon wrote: post #54

People seemed to be focusing on the fact that this wouldn’t break the NIST leading PQC public key cryptosystem, but I think that misses the point. This takes a problem at the core of this security, which previously only had an exponential approximation, and finds a polynomial approximation. Sure that polynomial is too high O(n^4.5) to break the leading proposed systems, but I mean are you really feeling safe when an…

The running time of attacks hasn't suddenly become O(n^4.5). The latter figure describe the noise ratio for which the LWE assumption becomes broken in quantum polynomial time.

The proposed post-quantum encryption schemes use a much smaller noise ratio which (at the moment) is not affected by these attacks.

Re: Quantum Algorithms for Lattice Problems

#62

Post by Ar-Curunir »

ghostway wrote: post #3
ghostway wrote: post #2

From the paper: > Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. For example, for CRYSTALS-Kyber [BDK+18], the error term is chosen from a small constant range, the modulus is q = 3329, the dimension is n = 256 · k w…

(of course, this doesn't mean we are in the clear -- a polynomial-time algorithm is alarming)

The algorithm is only quantum-polynomial time for a parameter regime not applicable to the PQC candidates.

Re: Quantum Algorithms for Lattice Problems

#63

Post by Ar-Curunir »

pclmulqdq wrote: post #32
ghostway wrote: post #2

From the paper: > Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. For example, for CRYSTALS-Kyber [BDK+18], the error term is chosen from a small constant range, the modulus is q = 3329, the dimension is n = 256 · k w…

Factorization and discrete log are also polynomial on a quantum computer, and we are very good at just increasing bit widths. If CRYSTALS is also polynomial in BQP, there is very little reason to invest so much into it. I am still of the (very controversial) opinion that the only PQC algorithm worth investing in at the expense of classical algorithms is Classic McEliece. This is a code that has stood up to classical…

The remark clearly states that CRYSTALs is not affected by this attack.

Re: Quantum Algorithms for Lattice Problems

#64

Post by kamilner »

cryptonik wrote: post #57
pclmulqdq wrote: post #32

Earlier quoted context omitted.

Factorization and discrete log are also polynomial on a quantum computer, and we are very good at just increasing bit widths. If CRYSTALS is also polynomial in BQP, there is very little reason to invest so much into it. I am still of the (very controversial) opinion that the only PQC algorithm worth investing in at the expense of classical algorithms is Classic McEliece. This is a code that has stood up to classical…

Thanks for your comment, very interesting. About your last paragraph : Do you know why NIST refuses hybridization, when European agencies imposes it ? What is the political behind it ?

NIST does not refuse hybridization, they will be publishing guidance on hybrid schemes in the draft of SP 800-227 at the same time as the final standards. They don't impose it though, because at a large scale it's more efficient to run just (fast) ML-KEM instead of (fast) ML-KEM + (slower) ECDH, which more than doubles your computation time for what they see as no benefit.

Re: Quantum Algorithms for Lattice Problems

#65

Post by ilya_m »

HappyPanacea wrote: post #55
hannob wrote: post #52

Earlier quoted context omitted.

QKD does not solve the problem that quantum computers create, and cannot replace public key cryptography. That's a common misconception that the marketing departments of QKD research tries to keep alive. Even under ideal conditions (whether these can exist is debatable), the best QKD gives you is a securely encrypted channel only when you already have a securely authenticated channel . The latter is extremely importa…

If you don't have an authenticated channel, you are susceptible to a MITM attack which makes any asymmetric crypto useless. Thus I think there is an implicit assumption in any asymmetric crypto that you already have an authenticated channel. Or did I miss something?

Grossly simplifying, Alice and Bob may establish an authenticated channel either by physical means (a wire) or by some combination of certificates/passwords and out-of-band authentication. Most of the time, QKD implicitly assumes the former - a line-of-sight connection or a fiber-optics cable. In these circumstances the parties might as well exchange flash drives with one-time pads, similarly to how the Kremlin-White House hotline was protected.

Re: Quantum Algorithms for Lattice Problems

#66

Post by adastra22 »

sgt101 wrote: post #49
warkdarrior wrote: post #41

Earlier quoted context omitted.

If scalable quantum computers do not exist, we do not need PQC.

We need PQC about 20 years before practical, scalable gate quantum computers appear (if they can do all the right gates). I think that this will be signaled when someone factors a 32 bit integer on one. At that point I guess it'll be about 20 years before someone can factor a 2048 bit integer, and I'll get twitchy about what I am sending over the wire with PKI. My feeling is that all my secrets from 20 years ago are…

We are within 20 years of scalable quantum computers already.

Re: Quantum Algorithms for Lattice Problems

#67

Post by adastra22 »

j2kun wrote: post #17
troq13 wrote: post #9

Just a bit more improvement and they might be able to use a computer that doesn't exist to break an encrypting scheme nobody uses. Alarming.

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.

Re: Quantum Algorithms for Lattice Problems

#68

Post by j2kun »

troq13 wrote: post #43
basementcat wrote: post #42

Earlier quoted context omitted.

I’ll bite; what are some of these extensions?

HBO watch party. If relays a fake costumer support chat if you visit a site like united airlines, that puts you in touch with scammers (probably does other malwary stuff too). A friend almost got scammed by this, they reported it to someone they know who works at Google and a couple months later the extension is still up. Tbh that is the only actual example I know, but after poking around a bit, ppl who actually know…

There was a previous one removed a few months ago for malware called HBO Max Watch Party. Was that it? If you have a specific extension id I can file a bug on your behalf.

And after reading about the situation internally, I can confirm there are dozens of people working on this problem, and that you have no idea what you're talking about. So please try to be a bit more humble.

Re: Quantum Algorithms for Lattice Problems

#69

Post by j2kun »

troq13 wrote: post #37
j2kun wrote: post #36

Earlier quoted context omitted.

I'm sure they have thought more about how to prioritize security threats than an anonymous internet commenter.

The fact that you work at Google and did not care to ask what are the extensions just confirms to me nobody there cares.

"One person doesn't care, therefore nobody cares"

Re: Quantum Algorithms for Lattice Problems

#70

Post by da-bacon »

Ar-Curunir wrote: post #61
da-bacon wrote: post #54

People seemed to be focusing on the fact that this wouldn’t break the NIST leading PQC public key cryptosystem, but I think that misses the point. This takes a problem at the core of this security, which previously only had an exponential approximation, and finds a polynomial approximation. Sure that polynomial is too high O(n^4.5) to break the leading proposed systems, but I mean are you really feeling safe when an…

The running time of attacks hasn't suddenly become O(n^4.5). The latter figure describe the noise ratio for which the LWE assumption becomes broken in quantum polynomial time. The proposed post-quantum encryption schemes use a much smaller noise ratio which (at the moment) is not affected by these attacks.

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”.
Post reply on HN