[HN Gopher] Quantum Algorithms for Lattice Problems
___________________________________________________________________
Quantum Algorithms for Lattice Problems
Author : trotro
Score : 80 points
Date : 2024-04-11 04:32 UTC (18 hours ago)
(HTM) web link (eprint.iacr.org)
(TXT) w3m dump (eprint.iacr.org)
| ghostway wrote:
| 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 where k [?] {3, 4, 5}, so we
| can think of q as being almost linear in n. For our algorithm, if
| we set aq [?] O(1), then our algorithm applies when q [?]
| ^~(n^2), so we are not able to break CRYSTALS-Kyber yet. We leave
| the task of improving the approximation factor of our quantum
| algorithm to future work.
| ghostway wrote:
| (of course, this doesn't mean we are in the clear -- a
| polynomial-time algorithm is alarming)
| rhaps0dy wrote:
| I don't understand your comment in the context of the
| previous comment you posted. AIUI, the excerpt says "our
| algorithm only applies when the modulus q is larger than n^2"
| where n is 256 _3 or 256_ 6 (I guess?). So the excerpt would
| be saying that the algorithm does not apply in this case,
| because 3000 << (256*3)^2. Right?
| abdullahkhalids wrote:
| If the history of cryptography is any guide, even though
| this result doesn't break LWE crypto-protocols, it's much
| more likely now that someone will come up an improvement
| that will break LWE crypto-protocols in the future. First
| constructions of algorithms are rarely optimal.
|
| Even though the opposite is possible as well, now that a
| concrete algorithm has been made. Someone could very well
| prove that LWE crypto-protocols are secure against some
| class of algorithms this algorithm belongs to.
|
| Of course, right now, we should just wait for the experts
| to read the paper and check if there are any problems.
| deyiao wrote:
| If the findings of this paper hold up, I believe it could pretty
| much undo a decade of NIST's efforts in post-quantum
| cryptography. a seismic shift in the world of cryptography.
| kyoji wrote:
| Not entirely true, there are other PKE and DSA algorithms that
| were/are a part of the competition that used problems not
| related to lattices. However, the lattice-based options were
| often among the fastest and smallest.
| tux3 wrote:
| Isogenies vindicated? :)
| tptacek wrote:
| I know you're kidding but for the benefit of the class
| isogeny schemes were pulled when their best candidate
| design turned out to be breakable with a Python script
| owing to obscure non-cryptographic mathematic research from
| the 1990s.
|
| I'd expect we're not getting isogenies back. :)
| j2kun wrote:
| I was at a conference with some of these folks recently
| and they stated some glimmer of hope remains for
| repairing isogeny-based crypto. I guess we'll see.
| bawolff wrote:
| This is the reason why nist did the decade of work - to focus
| effort on figuring out what options are secure. Finding out an
| option is not secure is a good thing. Its why we are putting
| effort into PQC now before quantum computers are a real threat.
| tptacek wrote:
| No? One of the side effects of running an open competition is
| that it focused attention on a variety of competing options for
| this, all of which were formalized, recorded, and publicly
| evaluated by the world's academic cryptography experts. We're
| strictly better off as a result, and _much_ of NIST 's own work
| would still be valuable even in a hypothetical scenario in
| which none of LWE was quantum-safe.
| anonymousDan wrote:
| Some initial Reddit discussion here:
| https://www.reddit.com/r/cryptography/comments/1c0vlfx/the_f...
| JohnKemeny wrote:
| And a question at crypto.stackexchange:
| https://crypto.stackexchange.com/q/111385
| dogeprotocol wrote:
| Will be interesting to see how this pans out.
| axblount wrote:
| Does this result apply to all LWE problems? Does this approach
| care about LWE vs Ring-LWE at all?
|
| If so, it's a big blow to systems like FrodoKEM that banked on
| unstructured lattices providing higher security.
| tux3 wrote:
| Not a lattice expert, so add salt to taste, but it looks like
| LWE in general (incluring RLWE)
|
| But the current attack essentially wants q > n^2, so even if it
| is confirmed, not all LWE schemes are dead. There will
| certainly be people who tweak the params in response and carry
| on.
|
| However, attacks only get better. And for people in FHE who are
| squeezed between performance problems and dangerously thin
| security parameters, it is a bad day if confirmed. There's no
| credible practical alternative to LWE for FHE...
| j2kun wrote:
| RingLWE security reduces to LWE via a relatively simple
| reduction (see https://www.jeremykun.com/2022/12/28/estimating-
| the-security...).
| tromp wrote:
| 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
| based on a concept called "learning with errors" introduced by
| Oded Regev in 2005.
|
| [1] https://en.wikipedia.org/wiki/Lattice-based_cryptography
|
| [2]
| https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_...
| doomrobo wrote:
| The idea of "appear to be resistant to attack" is an empirical
| one. When someone says that, they are saying that we simply
| have not found a good attack against this problem. That can
| change any day, in principle. Unfortunately, "we don't know of
| an attack" is about as strong a statement you can make in
| cryptography, when talking about a fundamental hardness
| assumption. More verbosely, you'd say "the best known attacks
| take 2^whatever operations on a computer (classical or
| quantum), and that's expensive, so we're probably fine unless
| someone makes a significant leap tomorrow"
| adgjlsfhk1 wrote:
| imo, this isn't quite true. there are a lot of areas where we
| can say "this looks sufficiently secure for now, but given
| the rate of advancement in this area in the last decade, we
| expect it will probably lose a few bits of security in the
| next decade"
| wbl wrote:
| Do you know how little we know? We don't even know P isn't
| PSPACE!
| troq13 wrote:
| 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.
| j2kun wrote:
| Major systems and big companies like Google are already mid-
| transition to PQC. So it is alarming.
| anonymousDan wrote:
| Furthermore this could have implications for fully
| homomorphic encryption schemes based on lattices. But
| nonetheless I laughed :)
| AnthonyMouse wrote:
| More to the point, the purpose of the encrypting system
| nobody uses is to have something to use if anybody ever makes
| the computer that doesn't exist. Now if that happens, what?
| tempaway4785751 wrote:
| We really need to get people to take really complicated
| risks that might never come to pass much more seriously.
| Perhaps someone smart can explain the really complicated
| risks that might never come to pass to the government that
| doesn't really look beyond the three year time horizon and
| get them to allocate some of their money that doesn't
| really exist to help.
| j2kun wrote:
| I work on homomorphic encryption, and there are some rumors
| circulating that, if this checks out, it will break some of the
| leading FHE schemes like BFV, where the moduli used are quite
| large (in the hundreds of bits or even over a thousand bits).
___________________________________________________________________
(page generated 2024-04-11 23:00 UTC)