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

71–80 of 127 posts

Re: Quantum Algorithms for Lattice Problems

#71

Post by troq13 »

Attrecomet wrote: post #51
hackerlight wrote: post #40

Earlier quoted context omitted.

Arrogance.

A fitting reply to a total non-sequitur, more like. A huge corps handling of browser extensions has absolutely zero to do with encryption algorithms, and security is such a big field that "care about security" means nothing at all. The comment was just a chance to vent anger at Google in an unproductive way.

It is a pretty random example, but it is meant to say that the math is rarely the limiting factor for security. People spend time thinking about this type of stuff because they like it, not because it is actually important for security.

In my mind RSA is the last instance of a mathematical development changing the game of security. After that it is twists of the same idea on more obscure mathematical objects, and pyrotechnic protocols that only the truly unhinged (ethereum people) are willing to try out in practice.

Re: Quantum Algorithms for Lattice Problems

#72

Post by less_less »

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…

It's NSA who wants only PQC and not hybrid. NIST is fine with hybrid. They don't plan to standardize hybrids as entire units, but they said they plan to standardize the KDF modes you'd need to build them.

Re: Quantum Algorithms for Lattice Problems

#73

Post by troq13 »

j2kun wrote: post #68
troq13 wrote: post #43

Earlier quoted context omitted.

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.

Yes I am checking the link my friend sent me now it it was that one, it is down. Thank you for your interest.

Re: Quantum Algorithms for Lattice Problems

#74

Post by less_less »

ilya_m wrote: post #65
HappyPanacea wrote: post #55

Earlier quoted context omitted.

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…

I'm not a huge fan of QKD, but there is a potential use case for it. Basically, for digital signatures we have schemes like SPHINCS+, and perhaps also PICNIC and FAEST, which don't require "mathematically structured" assumptions like other public-key crypto, but instead are secure based on not much more than one-way functions. If (and it's a big if) quantum computers can break all those structured assumptions but not AES/SHA, then we would still have secure public-key signatures, certificates etc but not KEMs.

But QKD can, in principle, securely distribute keys if you have a way to exchange quantum state (e.g. line-of-sight or some sort of currently-nonexistent quantum router) and a classical authenticated channel. SPHINCS+ could provide that authenticated channel. In that case QKD would enable secure key exchange even between parties who don't have a pre-shared secret.

Of course right now, all of that is science fiction.

Re: Quantum Algorithms for Lattice Problems

#75

Post by troq13 »

j2kun wrote: post #68
troq13 wrote: post #43

Earlier quoted context omitted.

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.

Actually never mind, I double checked and it was just HBO watch party (it is still up and has the malware). I appreciate if you can take a look at this.

Re: Quantum Algorithms for Lattice Problems

#76

Post by Ar-Curunir »

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

Earlier quoted context omitted.

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”.

The attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.

Re: Quantum Algorithms for Lattice Problems

#77

Post by troq13 »

j2kun wrote: post #68
troq13 wrote: post #43

Earlier quoted context omitted.

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.

https://chrome.google.com/webstore/detail/hbo-watch-party/dn...

This is the link to the malicious extension.

Re: Quantum Algorithms for Lattice Problems

#78

Post by troq13 »

j2kun wrote: post #69
troq13 wrote: post #37

Earlier quoted context omitted.

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"

Sadly you are like the 6th google employee I personally told about this (and it is still up).

Re: Quantum Algorithms for Lattice Problems

#79

Post by westurner »

tromp wrote: post #8

How does this affect these statements on Wikipedia [1] > 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. and [2] ? > One class of quantum resistant cryptographic algorithms is bas…

CRYSTALS-Kyber, NTRU, SABER, CRYSTALS-Dilithium, and FALCON are lattice-based method finalists in NIST PQC Round 3.

[1] NIST Post-Quantum Cryptography Standardization: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...

The NTRU article mentions PQ resistance to Shor's only, other evaluations, and that IEEE Std 1363.1 (2008) and the X9 financial industry spec already specify NTRU, which is a Round 3 Finalist lattice-based method.

In [1] Under "Selected Algorithms 2022", the article lists "Lattice: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON; Hash-based: SPHINCS+".

Round 4 includes Code-based and Supersingular elliptic curve isogeny algos.

FWIU There's not yet a TLS 1.4/2.0 that specifies which [lattice-based] PQ algos webservers would need to implement to support a new PQ TLS spec.

Re: Quantum Algorithms for Lattice Problems

#80

Post by adrianN »

adastra22 wrote: post #66
sgt101 wrote: post #49

Earlier quoted context omitted.

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.

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