[HN Gopher] A quick post on Chen's algorithm
___________________________________________________________________
A quick post on Chen's algorithm
Author : feross
Score : 255 points
Date : 2024-04-16 20:16 UTC (1 days ago)
(HTM) web link (blog.cryptographyengineering.com)
(TXT) w3m dump (blog.cryptographyengineering.com)
| glitchc wrote:
| Let's wait for the dust to settle to see if Chen has indeed
| broken the Shortest Vector Problem for lattices. Bold claims
| require strong evidence.
| stoniejohnson wrote:
| Extra-ordinary claims require extra-ordinary evidence!
|
| (my favorite maxim from 2012 era atheism debates on youtube)
|
| But yeah I totally agree. Putting the cart before the horse
| here with the outlined consequences probably isn't smart, but
| to be fair, I haven't (and probably couldn't) read the paper.
| deathanatos wrote:
| > _(my favorite maxim from 2012 era atheism debates on
| youtube)_
|
| It's a bit older than that: https://en.wikipedia.org/wiki/Ext
| raordinary_claims_require_e...
| ecosystem wrote:
| "Bananas: atheists worst nightmare"?
| vitus wrote:
| I was under the impression that the Shortest Vector Problem was
| NP hard (at least, in some cases). If this works even in those
| scenarios, that's an even bolder claim by far.
| pbsd wrote:
| SVP is NP-hard for approximation factors much smaller than
| this algorithm reaches. This algorithm solves approximation
| factors of at best O(n^4.5), but NP-hardness is only shown
| for approximation factors well below n^(1/2). See Figure 1 in
| page 2 of [1] for a breakdown of the hardness of various
| approximation factors.
|
| [1] https://cims.nyu.edu/~regev/papers/cvpconp.pdf
| archgoon wrote:
| Chen has not claimed to have broken SVP; only in certain
| situations. This is a better LLL; not a polynomial hierarchy
| overturning.
| gradschoolfail wrote:
| As pointed out by archgoon (and also pbsd) only for specific
| parameters is the problem broken, somewhat akin to saying a
| problem is NP-hard doesnt mean all instances of a problem are
| hard. But in this case for those parameters it isnt even NP
| hard.
| jonahx wrote:
| I appreciate short, accessible writeups on subjects like these.
| faitswulff wrote:
| It seems like the post-quantum algorithm that Signal selected [0]
| involves lattices [1] somehow:
|
| > Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM),
| whose security is based on the hardness of solving the learning-
| with-errors (LWE) problem over module lattices.
|
| Curious to see if Chen's work will eventually lead to Signal
| selecting a different algorithm.
|
| [0]: https://signal.org/blog/pqxdh/
|
| [1]: https://pq-crystals.org/kyber/
| contact9879 wrote:
| Green explicitly mentions Kyber in his post.
|
| > NIST-approved schemes based on lattice problems include Kyber
| and Dilithium (which I wrote about recently.)
|
| > Chen's algorithm does not immediately apply to the recently-
| standardized NIST algorithms such as Kyber or Dilithium.
|
| And it's not just Signal. Apple's new iMessage protocol, PQ3,
| uses Kyber, too. [1] Most deployments of PQ-crypto that I know
| of have used Kyber.
|
| [1] https://security.apple.com/blog/imessage-pq3/
| glitchc wrote:
| _deleted_
| jameswryan wrote:
| Rainbow is not a KEM, but a signature scheme.
| tptacek wrote:
| More or less all of the "serious", actually deployed PQC
| schemes involve lattices, going back before the competition.
| contact9879 wrote:
| I've seen some Classic McEliece deployments, too. Well, I
| know of only one: Mullvad.
|
| https://github.com/mullvad/mullvadvpn-
| app/blob/main/talpid-t...
| tptacek wrote:
| Some helpful, perhaps valid context is that lattice-based
| cryptography was a contender even before PQC became a thing
| (NTRU being the obvious example).
|
| Really the only point I'm trying to make here is that
| there's nothing eyebrow-raising about systems using lattice
| crypto; after IFP/FFDLP stuff like RSA and ECDLP, lattices
| are maybe the next most mainstream approach to constructing
| asymmetric systems.
| dang wrote:
| Recent and related:
|
| _Quantum Algorithms for Lattice Problems_ -
| https://news.ycombinator.com/item?id=39998396 - April 2024 (118
| comments)
| enthdegree wrote:
| The Wikipedia link on "lattice" points to the wrong article.
| "Lattice-based cryptography" usually means group-sense lattices,
| not order-sense lattices. Lattice groups are even directly
| involved in the rest of the article.
| Upvoter33 wrote:
| fix it! (please)
| matthewdgreen wrote:
| Thanks, it's fixed. That's what I get for quickly adding links.
| givemeethekeys wrote:
| If the research is true, will it make it possible for someone to
| easily steal my bitcoin?
| peddling-brink wrote:
| Only if you give them the keys.
| harryp_peng wrote:
| dude are you nuts the whole point of all that was to steal
| you without the key
| tptacek wrote:
| Yes, if they have a sufficiently powerful quantum computer.
| fsmv wrote:
| This research has no impact on Bitcoin, it was already broken
| post quantum by Shor's algorithm. They will simply change the
| signature algorithm when quantum computers become available so
| it should be fine.
| mensetmanusman wrote:
| Sim swaps are easier
| keepamovin wrote:
| There'll probably be discovered a class of problems which is hard
| and Q hard, provably and we'll be set. Something basically new to
| cryptography, that was tried once in the past but failed until
| seen through a new light of more recent maths or research
| fashion.
|
| But until then it seems to me like something based on the
| difficulty of attacking hash functions would be a good bet for Q
| resistant. Totally unsure how to make a PK scheme from that, but
| it has a few nice properties:
|
| - hashes are often tuneable, you can add more state and increase
| the keyspace/security
|
| - good hashes don't have any weaknesses that Q can exploit
|
| - hashes are often pretty fast
|
| - hashes are well studied
|
| - hashes seem to be hard in C and hard in Q
| Vecr wrote:
| https://en.wikipedia.org/wiki/McEliece_cryptosystem
|
| Yes, it's reasonably fast even at very long lengths, but the
| main problem is the very long lengths. Code based and not hash
| based though.
|
| Edit: not very fast to generate a key though. It's mostly used
| for non-ephemeral stuff.
| amluto wrote:
| The new algorithm purports to solve LWE with certain choices
| of parameters. LWE is the problem of solving a linear system
| of equations over a finite ring, where each equation has an
| additive error from a certain distribution.
|
| McEliece has a public key that is a general linear code. A
| code is a bunch of linear equations constraining codewords,
| and codewords are vectors over a finite field, and decoding a
| code is solving those equations subject to errors from a
| given distribution. Sounds familiar?
|
| They're not the same problem, and the distributions are
| different in rather fundamental ways (which may or may not
| make a difference), but they are quite related. I would not
| move my eggs to the McEliece basket right now.
|
| Hash-based signatures sound as safe as ever.
| karl_gluck wrote:
| Check out the Winternitz One-Time Signature
|
| Sphere10.com/articles/cryptography/pqc/wots
|
| Signing many things with one identity is possible by
| precomputing a Merkle tree, but this takes time and the
| signatures get big.
| er4hn wrote:
| SPHINCS+ is a complete signature scheme that carries that
| idea to it's completion. Shameless plug for where I explain
| it: https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-
| step...
| YoumuChan wrote:
| We don't even know the complexity class of factorization or
| discrete log, yet we still use those problems in DH, RSA,
| ECDSA, ...
| eru wrote:
| All of those problems are known to be in NP and co-NP. In
| that sense, we know some complexity classes they belong to.
|
| However, we don't know if these bounds are tight, or whether
| they are eg in P, or something in between.
| keepamovin wrote:
| We don't know that factorization is NP-complete> Show me a
| reduction from SAT to factorization.
|
| It's kind of trivial to say it's in NP because we can
| verify in P time, that's not a criticism of you just of the
| definition!!
|
| I think a better definition of NP is "only nonpoly algos
| can exist, no P algos can exist". By that definition of NP,
| we don't even know that it's in NP strictly because there
| could exist P algorithms for solving it. It's more in
| 'unknown-NP' if that were a class! hahaha! :)
| SJC_Hacker wrote:
| I think this what alot of people get wrong. "N' in NP
| does not stand for "not" it stands for "non-
| deterministic". Meaning you can solve in P time with a
| non-deterministic Turing machine, or alternatively, a
| function executing on all inputs in parallel.
|
| So maybe it should really be P and NDP.
| keepamovin wrote:
| That's a good explanation. I didn't know that.
| eru wrote:
| > We don't know that factorization is NP-complete.
|
| Yes? No one ever said it was.
|
| None of the common cryptographic problems are expected to
| be NP-complete, even if they aren't in P. That's because
| they are known to be in both NP and in co-NP, and it's
| expected that NP != co-NP.
|
| > I think a better definition of NP is "only nonpoly
| algos can exist, no P algos can exist".
|
| In what sense is that a 'better' definition than the
| standard definition? It sounds like what you are talking
| about is NP\P (where \ is set subtraction, ie 'NP minus
| P').
| keepamovin wrote:
| I think some people have asked whether it was. I'm not
| saying you did, just thought it was interesting! Haha :)
|
| I don't even know what co-NP is. Could you explain?
|
| I think that's a better definition because I find it more
| predictive and useful to think about: pretty concrete to
| know that you can't have a polytime algo for it.
|
| Yeah, I guess what you're saying about NP\P is right in
| that it's a restatement of the definition of what I said,
| haha! I'm not an expert this is just what I think :)
| openasocket wrote:
| I always found that part odd. I'd assume you would want the
| problem you build your crypto system built around to be NP-
| complete, since that would seem to put you on the firmest
| possible ground. And yet those are most likely not NP-
| complete, and I think the post-quantum systems proposed
| aren't NP complete either.
|
| Maybe being NP-complete isn't as important as I realize? Or
| maybe there's something about NP-complete problems that
| make them less amenable to be a valid crypto system?
| ihm wrote:
| There are a bunch of hash based signature schemes, e.g.,
| SPHINCS https://sphincs.org/
| anonymous-panda wrote:
| I find the panic over potential threat of quantum quite amusing
| when the machine is still extremely theoretical - all existing
| machines are slower than classical and it's not even clear they
| can scale to the required number of qubits.
|
| There's nowhere near the same urgency and significantly more
| denial over global warming. A bit apples and oranges but climate
| models have a better track record, are wildly conservative (ie
| our present is much worse than the past climate models predicted)
| and it's a real problem we know exists and is a bullet train
| headed our way.
| CobrastanJorji wrote:
| I totally agree that climate change is a far more serious
| problem than quantum computing, but we do actually spend quite
| a bit on climate change, if not nearly as much as the problem
| warrants.
|
| Depending on how you measure it, we theoretically spend about a
| trillion bucks a year worldwide on climate change (
| https://www.climatepolicyinitiative.org/publication/global-l...
| ) and maybe a couple billion bucks a year on quantum computers.
| eru wrote:
| Measures to combat climate change are weird, and also
| politicised in weird ways.
|
| Eg the US administration like to pretend that climate change
| is a top priority, but then complains when Chinese tax payers
| generously subsidise solar cells and electric cars for
| American consumers.
| mensetmanusman wrote:
| These technologies are manufactured with stricter
| environmental controls when done in the US versus China.
| The picture isn't as simple as it may seem.
| jon_richards wrote:
| When global warming hits, the people who benefited from
| ignoring it will be best off. When quantum computers hit, the
| people benefiting the most _right now_ will be the worst off as
| all their communications from this era are decrypted.
| ziddoap wrote:
| I think this may be your technology bubble showing.
|
| Global warming is talked about on the radio, TV, movies. It's
| sung about in songs. There's several conferences, widely-
| attended protests, stickers on appliances, tax initiatives,
| etc.
|
| A few comments on obscure sites like HN can hardly be called a
| panic. It is silly to suggest that there is more urgency about
| post-quantum attacks on crypto than global warming.
| SJC_Hacker wrote:
| The slow poison is alot less alarming than the sharp knive.
| mvkel wrote:
| Quantum Luddite here.
|
| So much of quantum computing is theory, and so much of current
| crypto is applied.
|
| Is it realistic to think the first applied quantum computers
| could quickly get us to a P=NP solution, rendering all crypto
| effectively irrelevant?
| foota wrote:
| Quantum computers are only tangentially related to P=NP, in
| that some problems in NP may have solutions that are polynomial
| time on quantum computers, but this says nothing about the rest
| of them. This class of problems is know as BQP. Is is possible,
| but unknown, that all problems in NP may belong to BQP, which
| would imply that a sufficiently large quantum computer could
| solve all problems in NP in polynomial time, but even then it
| would be possible that P does not equal NP, since P and NP are
| about classical computers.
___________________________________________________________________
(page generated 2024-04-17 23:02 UTC)