7 ms·
A quick post on Chen's algorithm
- glitchc 3y agoLet'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 3y agoExtra-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 3y ago> (my favorite maxim from 2012 era atheism debates on youtube) It's a bit older than that: https://en.wikipedia.org/wiki/Extraordinary_claims_require_extraordinary_evidence https://en.wikipedia.org/wiki/Extraordinary_claims_require_e...
- ecosystem 3y ago"Bananas: atheists worst nightmare"?
- vitus 3y agoI 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 3y agoSVP 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 https://cims.nyu.edu/~regev/papers/cvpconp.pdf
- archgoon 3y agoChen has not claimed to have broken SVP; only in certain situations. This is a better LLL; not a polynomial hierarchy overturning.
- gradschoolfail 3y agoAs 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 3y agoI appreciate short, accessible writeups on subjects like these.
- faitswulff 3y agoIt 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/ https://signal.org/blog/pqxdh/ [1]: https://pq-crystals.org/kyber/ https://pq-crystals.org/kyber/
- contact9879 3y agoGreen 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/ https://security.apple.com/blog/imessage-pq3/
- glitchc 3y agodeleted
- jameswryan 3y agoRainbow is not a KEM, but a signature scheme.
- deleted 3y ago[deleted]
- tptacek 3y agoMore or less all of the "serious", actually deployed PQC schemes involve lattices, going back before the competition.
- contact9879 3y ago
- dang 3y agoRecent and related: Quantum Algorithms for Lattice Problems - https://news.ycombinator.com/item?id=39998396 https://news.ycombinator.com/item?id=39998396 - April 2024 (118 comments)
- enthdegree 3y agoThe 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 3y agofix it! (please)
- matthewdgreen 3y agoThanks, it's fixed. That's what I get for quickly adding links.
- Samuel_w 3y ago[dead]
- givemeethekeys 3y agoIf the research is true, will it make it possible for someone to easily steal my bitcoin?
- peddling-brink 3y agoOnly if you give them the keys.
- harryp_peng 3y agodude are you nuts the whole point of all that was to steal you without the key
- tptacek 3y agoYes, if they have a sufficiently powerful quantum computer.
- fsmv 3y agoThis 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 3y agoSim swaps are easier
- Linda231 3y ago[dead]
- keepamovin 3y agoThere'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
- YoumuChan 3y agoWe don't even know the complexity class of factorization or discrete log, yet we still use those problems in DH, RSA, ECDSA, ...
- eru 3y agoAll 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 3y agoWe 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 3y agoI 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.
- anonymous-panda 3y agoI 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 3y agoI 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-landscape-of-climate-finance-2023/ https://www.climatepolicyinitiative.org/publication/global-l... ) and maybe a couple billion bucks a year on quantum computers.
- eru 3y agoMeasures 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 3y agoThese technologies are manufactured with stricter environmental controls when done in the US versus China. The picture isn't as simple as it may seem.
- eru 3y agoHow does this complicate the picture? The environmental controls you are talking about mostly protect the local environment. Protecting the local environment is great, but crudely speaking, the global climate doesn't much care about whether you dump some toxic waste in some part of China. What I hear in complaints about the exports from the Americans is that they are worried about good old jobs for good old American boys and girls (preferably in a union that is a strong voting block one way or another). So I would take the Americans at their word here. Yet again, if the local environment in China was a priority of the administration that outweighed concern about climate change, you would see a very different policy. Instead of just putting tariffs and other restrictions on imports of some Chinese goods. You can probably come up with your own examples.
- mvkel 3y agoQuantum 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 3y agoQuantum 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.