NIST announces first PQC algoritms to be standardized

from skimming it, his main argument is that Kyber relies on many constructions (e.g. cyclotomic polynomials) that are actively under attack - researchers have been successfully chipping away at them and show no signs of stopping.

he also alleges that NIST have been moving the goal posts to favor Kyber, and they've been duplicitous in their narrative.

he favors NTRU, which iirc isn't his.

code_biologist• 4 years ago

Here's the warning: Lattice-based cryptography is much more risky than commonly acknowledged. This applies, in particular, to lattice KEMs under consideration within the NIST Post-Quantum Cryptography Standardization Project (NISTPQC) as of October 2021. The above document...

There's a linked PDF paper with more detail.

kzrdude• 4 years ago

Is djb involved in any of the standardized algorithms here by the way?

markschultz5• 4 years ago

Yes, many. I believe he's on the SPHINCS+ team (was standardized), Classic McCliece (round 3, not standardized), and NTRU_PRIME (round 3, passed over for Kyber). Perhaps more, but he has significant skin in the game.

chasil7• 4 years ago

OpenSSH has already chosen NTRU-Prime. Will there be a retrofit of CRYSTALS-KYBER? Or has the market already chosen?

DJB is an author on the SPHINCS+ team; glad to see that his work will be part of the standard.

https://sphincs.org/

layer8• 4 years ago

OpenSSH has merely chosen that as its current default. Surely multiple algorithms will be supported in the future as they have in the past.

chasil7• 4 years ago

There was considerable strife for Daniel J. Bernstein during this competition.

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&c...

It would not surprise me if OpenSSH only chooses to add SPHINCS+ and refuses the others.

CircleSpokes• 4 years ago

I imagine they would add support for the standardized algorithms and still support the ones they are currently using too.

bwesterb3• 4 years ago

NTRU-Prime, NTRU, Kyber and SABER are all great KEMs. NIST could've chosen any one of them. NIST never standardised Ed25519 and OpenSSH still uses it, which is perfectly fine.

Zamicol2• 4 years ago

Ed25519 is in the draft standard, as well as Ed25519ph: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5-draft...

elromulous• 4 years ago

PQC = post quantum cryptography

haggy• 4 years ago

Ah thank you. I figured the 'Q' stood for quantum but you saved me a fair amount of googling :)

capableweb• 4 years ago

"fair amount of googling"?

Not sure what browser you use, but in most you can select what you wanna search for, click "Search on $searchEngine for $term" and there you go! For PQC, I get Wikipedia link with "PQC can refer to: Post-quantum cryptography" in the description as the 3rd result on Google.

Not sure what classifies as "fair amount", but for me it took about 1-2 seconds to find the Wikipedia link ;)

cpeterso• 4 years ago

Looks like the name “CRYSTALS-KYBER” is a Star Wars reference (kyber crystals). At least one of the authors of CRYSTALS-KYBER (Peter Schwabe) published an earlier PQC algorithm called “NewHope”, another Star Wars reference.

And “CRYSTALS-DILITHIUM” is, obviously, a Star Trek reference. :)

ENOTTY• 4 years ago

What's up with this?

In addition, NIST has engaged with third parties that own various patents directed to cryptography, and NIST acknowledges cooperation of ISARA, Philippe Gaborit, Carlos Aguilar Melchor, the laboratory XLIM, the French National Center for Scientific Research (CNRS), the University of Limoges, and Dr. Jintai Ding. NIST and these third parties are finalizing agreements such that the patents owned by the third parties will not be asserted against implementers (or end-users) of a standard for the selected cryptographic algorithm

and

NIST expects to execute the various agreements prior to publishing the standard. If the agreements are not executed by the end of 2022, NIST may consider selecting NTRU instead of KYBER. NTRU was proposed in 1996, and U.S. patents were dedicated to the public in 2007.

hn_throwaway_99• 4 years ago

NIST is going the proper route to ensure that any standards they publish can be freely implemented without implementers having to pay patent royalties. That's the reason for your second quote - if KYBER patent holders don't want to agree, they should know that NIST won't choose them for the standard.

nullc2• 4 years ago

Just to clarify: My understanding is that the authors of Kyber aren't the patent holders in question-- rather a third party has patents which may read on Kyber and several other of the NIST finalists.

It's really unfortunate the the licensing terms weren't announced at the same time: Depending on how they're written the result may still be unattractive to use, and since they've already announced the selection NIST probably just lost some amount of negotiating leverage.

(As the obvious negotiation would be "agree to these terms we find reasonable, or we just select NTRU prime")

rdpintqogeogsaa• 4 years ago

Key part here is "are finalizing". It's still possible for at least some of the deals to fall through. I guess NTRU is the backup plan just in case and/or a method to apply pressure by saying the public is now aware there's a plan B. I exüect this passage to imply at least one negotiation has been going poorly.

It would probably be interesting to look up who of these people also has patents outside of the USA. If there really is someone being particularly stubborn, one might reasonably expect them to enforce the non-US patent variant outside of the USA.

formerly_proven• 4 years ago

Crypto that requires royalties won't be widely implemented, so you basically don't need to bother standardizing it.

madars• 4 years ago

If the agreements are not executed by the end of 2022, NIST may consider selecting NTRU instead of KYBER.

It is especially interesting that NTRU (nor NTRU Prime, a different proposal) is _not_ advancing to the 4th round. Wouldn't you want to encourage more analysis for your (implied) runner-up?

willglynn• 4 years ago

Not only that, NIST says:

Overall assessment. One important feature of NTRU is that because it has been around for longer, its IP situation is more clearly understood. The original designers put their patents into the public domain [113], in addition to most of them having expired.
As noted by the submitters, NTRU may not be the fastest or smallest among the lattice KEM finalists, and for most applications and use cases, the performance would not be a problem. Nonetheless, as NIST has selected KYBER for standardization, NTRU will therefore not be considered for standardization in the fourth round.

https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf

"NTRU is obviously legal and perfectly suitable, but we're not picking it." I find this to be a baffling position given the as-yet-unsolved patent issues with KYBER.

jjice• 4 years ago

Been waiting on this announcement for a while. As someone who took a crypto class in college, but isn't a crypto expert (just knows the basics and basic theory), this is very neat to see. I'm looking forward to never implementing it myself :)

RcouF1uZ4gsC• 4 years ago

HN Crypto and Quantum Experts.

What is your prediction when classical public key encryption using elliptical curve cryptographic becomes practically vulnerable to quantum computers, such that we would need these PQC algorithms.

10 years out? 20 years out? 50 years out? 100 years out?

hannob• 4 years ago

I've been following this space for a while and this is a good question, but I think the answer is really a "ranges from 10 years to never".

There's a lot of investment currently in the quantum computer space (+ a lot of hype and scams). Yet this is still all very early research and far away from any practical use. The challenges to really build a QC that can break cryptography are enormous - and it is absolutely a possibility that they're too big to overcome.

chasil7• 4 years ago

This article asserts that D-Wave and other quantum annealing devices will be able to mount attacks long before a machine exists that can run Shor's algorithm with error-corrected qubits in sufficient quantity.

https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...

Asraelite• 4 years ago

I want to see these actually being implemented in current software ASAP (layered with traditional crypto). As-is it's possible to capture encrypted traffic out of the air, store it for however many decades are needed, and then decrypt it in future.

NavinF2• 4 years ago

"When will 256 bit ECC become insecure?" : https://www.metaculus.com/questions/8169/?invite=GpV2Dc

The community prediction is 22% by 2032 which seems way too high IMO. I predict 5% due to advances in automated algorithm search and 0% due to quantum computers in that time frame.

marcosdumay2• 4 years ago

Why would a croudsoursing site know that? This is the kind of question where 1 expert will fare better than the average of 90% of the people.

IncRnd• 4 years ago

I think what you are asking may better be answered by ignoring PQC and following CNSA recommendations for up to TOP SECRET. The crypto is likely what you already use, but it defines how to get enough bits of security from an algorithm.

There is a table of transition algorithms on the second or third page, depending on your screen size. [1]

[1] https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa...

danuker• 4 years ago

I expect you'd see a large increase in Bitcoin Days Destroyed, perhaps unrelated to market volume, should someone break ECDSA.

Bitcoin uses ECDSA to validate whether coins were spent by the owner of an address.

https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_...

jleahy2• 4 years ago

The modern wallets don’t publish the public key though, so this is not likely to help.

rvz• 4 years ago

Well good thing that some of the cryptographers that created Falcon [0][1] (the ones who developed Algorand) for post-quantum cryptography for digital signatures use cases is considered to be 'standardised' as such.

This tells me that Algorand is one of the more serious blockchain projects out there with top cryptographers as evidenced by Falcon.

[0] https://falcon-sign.info

[1] https://github.com/algorand/falcon

bawolff8• 4 years ago

https://xkcd.com/678/

Any predictions on these time scales are pretty much pointless.

ghaff• 4 years ago

It's worth noting that the relevant timeframe to implement PQC isn't just when quantum computers become sufficiently fast to break current crypto (assuming the answer isn't never). It can take a decade or longer to re-encrypt data and/or to update cryptographic infrastructure.

Given that (varied) expert option on quantum computing being able to break current public key cryptography seems to mostly fall in the 10-20 year range, there is some, at least mild, urgency to start using PQC for the most sensitive data relatively soon.

kvathupo3• 4 years ago

Not an expert, but you should upgrade now to prevent attackers from stealing your encrypted data today, and decrypting it later. That said, you'll have to determine if your data is worth stealing.

bwesterb3• 4 years ago

It's hard to say. Here is a great paper that tries to answer this question.

https://arxiv.org/pdf/2009.05045v1.pdf

See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.

Zamicol2• 4 years ago

The linked study is about RSA, not elliptical curve cryptography

adastra226• 4 years ago

10-20 years. As soon as we have atomically precise manufacturing, there are multiple approaches to making stable, scalable quantum computers that work. I see APM being possible on that time horizon. One company, Zyvex, has already prototyped those capability in the lab.

upofadown3• 4 years ago

We have not been able to implement even a single logical qubit of the sort required to run Shor's algorithm (we would need thousands). It is impossible to extrapolate from zero.

sweis• 4 years ago

The record for factoring using a quantum computer is 21. Don't read that as 21 bits. 3*7. This has been the record for 12 years and that is arguably a result that is "cheating" with a priori knowledge of the factors.

There are some other examples of people factoring special-form composites that are particularly easy to factor on quantum computers, but those are basically stunts with no impact.

To threaten RSA, quantum computers need to increase the number qubits 6 orders of magnitude and improve the error correction at least 2 orders of magnitude. Check out this blog post for an illustration of where we are at: https://sam-jaques.appspot.com/quantum_landscape

baby4• 4 years ago

I'm betting on never

sbf5012• 4 years ago

Waiting for the ELI5 sites to explain Kyber and LWE. :)

markschultz5• 4 years ago

I wrote up an introduction to a (severely unoptimized for pedagogical purposes) version of FrodoKEM

https://mark-schultz.github.io/nist-standard-out/

It's the same base scheme as Saber/Kyber, although as Saber/Kyber are over algebraically structured lattices they are significantly more efficient.

sbf5012• 4 years ago

Thanks for taking the time to write this up. But, woof, it's a bit more than ELI5. :) The python code makes it a little more clear since I'm not familiar with some of the notation. However, it does seem kind of magic that 'e' is derived during the encryption and then sort of vanishes. I also don't quite get the bounded vs uniform vector sampling calls (one for s and the other for chi). But this at least greases the wheels so to speak, so thanks!

baby4• 4 years ago

I wrote a chapter containing explanations on these here: https://livebook.manning.com/book/real-world-cryptography/ch...

forty4• 4 years ago

Coincidentally, we have just published this today, if you want to play with PQ crypto in JavaScript https://github.com/Dashlane/pqc.js

buu700• 4 years ago

Similarly, I just published this a few days ago: https://github.com/cyph/pqcrypto.js

Edit: lol, actually it looks like you guys borrowed some of my code for that. (Which is totally fine and part of the point of open source!)

forty4• 4 years ago

Apparently yes! I'm told we did use your other older project ntru.js as mentioned in the readme :) thanks for sharing your code!

oconnore4• 4 years ago

Additionally, SPHINCS+ will be standardized to avoid only relying on the security of lattices for signatures
Both BIKE and HQC are based on structured codes, and either would be suitable as a general-purpose KEM that is not based on lattices

What's up with this caveat? Why would the standard require algorithms not based on lattices assuming there is confidence in the lattice based approach?

Is this a security concern, or is there some performance (ops/sec or size) related trade-off?

bawolff8• 4 years ago

Presumably to hedge their bets. If suddenly someone finds a major problem with latices, its good to have an alternative waiting in the wings.

See also sha-3 vs sha-256

oconnore4• 4 years ago

If NIST feels the need to hedge their bets, why are they publishing at all? The whole point of these recommendations is so that I, a non-expert, don't have to reason about cryptographic bets.

hinkley2• 4 years ago

Particularly sha-3 vs sha-512, which turned out to have issues.

kvathupo3• 4 years ago

A point rendering the choice even more curious: Germany and the Netherlands have recommended the use of encryption not relying on the shortest vector problem [1]. The two suggestions of FrodoKEM (relying on hardness of the learning with errors problem) and Classic McEliece (relying on hardness of decoding random codes?) aren't lattice-based apparently.

Perhaps NIST knows something we don't ; ^ )

[1] https://twitter.com/CJTjhai/status/1544398903591796736

markschultz5• 4 years ago

LWE's hardness is based on SVP (ignoring issues of tightness, which isn't unique to FrodoKEM). The difference between FrodoKEM + Kyber/Saber isn't relying on SVP/not (they all essentially do), but is on relying on LWE over structured lattices or not.

At a very high level, all of the three rely on an n x n matrix at a certain point. The "structured lattice" schemes (Kyber/Saber) make structural assumptions about this matrix, say that each row is a cyclic shift of the previous row. This turns an O(n^2) object into an O(n) object, giving many performance improvements. The downside is that the additional structure can plausibly be used for attacks (but the best attacks ignore the structure, so this is a "potential issue", not a current issue).

nullc2• 4 years ago

The security story for lattices hasn't been very stable.

Consider the graph in the Classic McEliece marketing materials, showing the exponent in the attack costs for lattice-based crypto:

https://classic.mceliece.org/comparison.html

Because of communication cost considerations the lattice candidates use problems small enough that another substantial improvement in attacks could leave them vulnerable (no shock that they use small problems: if you're really not communication cost constrained use McEliece and don't worry about it).

If you do use lattice key agreement, be sure to use it in a hybrid configuration (combined with ECC like ed25519 or Curve448) to avoid the (small but hard to assess) risk that your security upgrade could actually be a security downgrade.

latenightcoding2• 4 years ago

Some people believe you can generalize Shor's algorithm to attack lattice-based cryptography.

kragen2• 4 years ago

Presumably since Dual_EC_DRBG it is counterproductive to rely on NIST's recommendations for secure cryptography. What should we rely on instead?

tptacek8• 4 years ago

https://news.ycombinator.com/item?id=31994063

oittaa• 4 years ago

DJB

bioemerl• 4 years ago

Something that worries me, if someone cracks our current encryption using quantum computers couldn't they be logging everything we say right now and everything we say right now is actually unsecure to someone 10 years in the future?

tptacek8• 4 years ago

Yes. That's, for instance, why people say the KEM problem has more urgency than the signature problem; a PQC KEM is what you need today if you're worried that someone's archiving your TLS sessions so they can break them with the quantum computer their government promised them for Christmas in 2034. Even if your KEX involves a signature, your adversary can't time-travel back to 2022 to break it with their 2034 scooty-puff quantum edition. But if all you've got is classical ECC and RSA, you're in trouble.

If you assume the PQC KEM doesn't interact with classical ECDH, you might want to get some kind of PQC KEM rolled out as quickly as you can, in a dual construction with ECDH; the worst that happens is, your new KEM isn't quantum-safe (or anything-safe), but your ECDH holds up. But that's (if you believe in quantum attacks on crypto) still better than no PQC KEM at all.

snapetom• 4 years ago

Yes. This is why the work is being done now, and there will be an urgency in moving PQC algorithms from academia to commercial use. Everything that has been stolen in data breaches up until then will be broken once QC are viable.

Good news is that we are likely more than 10 years away from QCs being useful enough to do this.

baby4• 4 years ago

Shameless plug: I wrote about all these schemes in Chapter 14 on post-quantum cryptography of Real-World Cryptography https://www.manning.com/books/real-world-cryptography?a_aid=...

These are meant as a gentle introduction to the ideas and intuitions behind the schemes. The book is recent but some of that stuff (hash-based signatures) I started writing back in 2015 and is available on my blog: https://cryptologie.net/article/306/one-time-signatures/

At the time the schemes had not yet been chosen, fortunately I picked the right ones :) don't have to rewrite that chapter (yet).

carride• 4 years ago

Some news analysis https://news.ycombinator.com/item?id=31997362

NIST announces first PQC algoritms to be standardized

Related Stories