[HN Gopher] Quantum Algorithms for Lattice Problems
___________________________________________________________________
Quantum Algorithms for Lattice Problems
Author : trotro
Score : 180 points
Date : 2024-04-11 04:32 UTC (1 days 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. 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.
| Ar-Curunir wrote:
| The algorithm is only quantum-polynomial time for a parameter
| regime not applicable to the PQC candidates.
| pclmulqdq wrote:
| 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 and quantum cracking attempts for a very long
| time - cracking these codes is equivalent to creating a very
| valuable algorithm in error correcting codes.
|
| The NIST also is dead set on people using only PQC or classical
| crypto, not a wrapper with both. That is stupid IMO.
| pseudo0 wrote:
| > The NIST also is dead set on people using only PQC or
| classical crypto, not a wrapper with both. That is stupid
| IMO.
|
| Yeah, this is rather baffling. After SIKE got broken, you'd
| think they would have realized the importance of combining
| these new cutting-edge candidates with something reliable.
| cryptonik wrote:
| 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 ?
| pclmulqdq wrote:
| The charitable interpretation I would give the NIST - and a
| very real concern - is that they are not sure that one form
| of cryptography doesn't weaken the other, without proofs.
| Since these cryptosystems also tend to work in different
| number fields, it's very hard to prove anything about their
| interactions at all.
|
| We all know the uncharitable interpretation, that the PQC
| algorithms may be backdoored.
| kamilner wrote:
| 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.
| Ar-Curunir wrote:
| The remark clearly states that CRYSTALs is not affected by
| this attack.
| less_less wrote:
| 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.
| 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.
| pvg wrote:
| _breakable with a Python script_
|
| The traditional, elegant method of a more civilized age:
|
| _Last on the program were Len Adleman and his computer,
| which had accepted a challenge on the first night of the
| conference. The hour passed; various techniques for
| attacking knapsack systems with different characteristics
| were heard; and the Apple II sat on the table waiting to
| reveal the results of its labors. At last Adleman rose to
| speak mumbling something self-deprecatingly about "the
| theory first, the public humiliation later" and beginning
| to explain his work. All the while the figure of Carl
| Nicolai moved silently in the background setting up the
| computer and copying a sequence of numbers from its
| screen onto a transparency. At last another transparency
| was drawn from a sealed envelope and the results placed
| side by side on the projector. They were identical. The
| public humiliation was not Adleman's, it was knapsack's._
|
| W. Diffie, The first ten years of public-key
| cryptography, _Proceedings of the IEEE_ , vol. 76, no. 5,
| pp. 560-577, May 1988
| maple3142 wrote:
| AFAIK, only SIDH-like schemes that exposes auxiliary
| points are broken, so others schemes like CSIDH may have
| some chances? https://issikebrokenyet.github.io/
| 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 :)
| rgmerk wrote:
| So a thing which is currently useless because it runs at a
| speed that makes the Harvard Mark I look fast, might be
| rendered useless if a thing that doesn't physically exist
| despite decades of effort is constructed? :P)
| 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.
| troq13 wrote:
| Google has dozens of chrome extensions in their app store
| that anyone can check in 2 mins are plain malware, and they
| do nothing about it. If they cared about security that's what
| they would be working on, these guys just want to publish
| papers.
| j2kun wrote:
| I'm sure they have thought more about how to prioritize
| security threats than an anonymous internet commenter.
| troq13 wrote:
| The fact that you work at Google and did not care to ask
| what are the extensions just confirms to me nobody there
| cares.
| basementcat wrote:
| I'll bite; what are some of these extensions?
| troq13 wrote:
| 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 about security
| say that's the state of things with these extension and
| app store apps, and nobody at google seems to think
| fixing it is their job.
|
| Funny thing is, they were asking this google friend for
| advice about getting rid of the malicious chat before
| they realized it was this chrome extension. The advice
| the google employee gave was to format the computer (it
| wouldn't have fixed it because once they logged into
| chrome again all the extensions would come back).
|
| Hard sell that people running this clown show could be
| doing PQC in any meaningful sense (other than publishing
| papers. The papers are fine).
| j2kun wrote:
| 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.
| troq13 wrote:
| Yes I am checking the link my friend sent me now it it
| was that one, it is down. Thank you for your interest.
| j2kun wrote:
| "One person doesn't care, therefore nobody cares"
| hackerlight wrote:
| Arrogance.
| Attrecomet wrote:
| 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.
| troq13 wrote:
| 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.
| adastra22 wrote:
| Their deployment is additive. You would need to break both
| the PCQ and classical schemes, so they'd be unaffected here.
| 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).
| ilya_m wrote:
| ... only if scalable quantum computers exist.
| warkdarrior wrote:
| If scalable quantum computers do not exist, we do not need
| PQC.
| foota wrote:
| Hemomorphic encryption is not the same thing as post
| quantum crypto?
| deknos wrote:
| Homomorphic Encryption does often use lattice mathematics
| Ar-Curunir wrote:
| But classically secure FHE is still a useful thing (even
| if it is broken by hypothetical quantum computers).
| sgt101 wrote:
| 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 irrelevant to life now so I feel 20 years of warning is
| quite sufficient.
| adastra22 wrote:
| We are within 20 years of scalable quantum computers
| already.
| Ar-Curunir wrote:
| FHE is still only known from lattices, and has nothing to
| do with post-quantum computers.
| deknos wrote:
| Are the OpenSSH lattice instances or the ones of DJB affected by
| this problem?
| tschumacher wrote:
| Some post-quantum signatures like CRYSTALS-Dilithium are based on
| lattices. Makes me think that quantum key distribution (what I've
| been working on for the past 6 months) has a chance to actually
| become useful instead of being only of interest to academics and
| to a few companies that sell overpriced solutions to paranoids.
| Vecr wrote:
| Code based systems are still in, and classic McEliece could be
| extended to ~50 MiB for a keypair and still be way more
| practical than QKD. Just run the max current classic McEliece
| spec hybrid post quantum with X448.
| sgt101 wrote:
| NSA is that you?
| hannob wrote:
| 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 important, makes the whole
| thing mostly useless, and is often omitted by QKD advocates.
| HappyPanacea wrote:
| 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?
| ilya_m wrote:
| 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.
| less_less wrote:
| 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.
| hellobye wrote:
| Hello everyone. I am a college student and currently new to this
| field. If possible can somone explain in simple terms that what
| real future impacts would this paper can create?
| swells34 wrote:
| It would be silly not to first ask your interpretation, given
| that you are a college student.
|
| Since this is about quantum computing, real world effects are
| very likely to be none except an exorbitant amount of grant
| money.
| da-bacon wrote:
| 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 exponential just changed to a
| polynomial?
|
| An analogy would be something like this. Factoring is hard. We
| base RSA on the hardness of this problem and there we use numbers
| that are the product of two primes. Someone just found an
| algorithm that doesn't work to find the product of two primes,
| but can take a product of four primes and return two products of
| two primes. Do you feel safe with RSA?
|
| Anyway the paper could be wrong or it could be right, it will
| take a while for those in the field to dig through this. As a
| cautionary tale, there have been a few extra good quantum people
| who have proposed quantum attacks on lattice problems that have
| later been shown to have bugs.
| Ar-Curunir wrote:
| 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.
| da-bacon wrote:
| 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".
___________________________________________________________________
(page generated 2024-04-12 23:01 UTC)