NIST announces first PQC algoritms to be standardized
groups.google.com
groups.google.com
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 ;)
A similar situation arises with trains, where it is often better to not hold open the door for someone who is late by a few seconds, as the cumulative delay for everyone else in the train exceeds the waiting period of the single person for the next train.
And “CRYSTALS-DILITHIUM” is, obviously, a Star Trek reference. :)
DJB is an author on the SPHINCS+ team; glad to see that his work will be part of the standard.
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.
Along with also apparently some possible remarks about DJB doing something wrong also (I couldn't tell from this at least what it was. I haven't done any complete readings yet).
It was often a huge problem for the people who he was fighting with, though. Are you one of them?
He was one of the earliest PQC popularizers and probably coined the term. But asserting that he enabled everyone else's work is a little like saying that the person who coined "misuse-resistant authenticated encryption" enabled all the different misuse-resistant schemes; the underlying issue was plainly evident, and people were obviously going to work on it.
Your last sentence falls afoul of the HN guidelines, and your comment would be far stronger without it. Which is unfortunate, since there's an interesting and curious conversation to be had about the significance of Bernstein's role in PQC.
https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein#Bernstei...
"The ruling in the case declared that software was protected speech under the First Amendment, which contributed to regulatory changes reducing controls on encryption."
Should NIST be disregarded?
NTRU-prime is not a finalist, but OpenSSH has decided that the NIST designation is irrelevant.
https://www.openssh.com/releasenotes.html
ssh(1), sshd(8): use the hybrid Streamlined NTRU Prime + x25519 key exchange method by default ("sntrup761x25519-sha512@openssh.com"). The NTRU algorithm is believed to resist attacks enabled by future quantum computers and is paired with the X25519 ECDH key exchange (the previous default) as a backstop against any weaknesses in NTRU Prime that may be discovered in the future. The combination ensures that the hybrid exchange offers at least as good security as the status quo.
We are making this change now (i.e. ahead of cryptographically- relevant quantum computers) to prevent "capture now, decrypt later" attacks where an adversary who can record and store SSH session ciphertext would be able to decrypt it once a sufficiently advanced quantum computer is available.
People with qualms about NIST might also reasonably have qualms about AES. And there is a common cipher that people use outside of AES --- Chapoly. But it would be downright weird to use, like, Serpent or Twofish; it would be the cryptography equivalent of a "code smell". Chapoly and AES are the de facto standards, and OpenSSH supports both.
Again though: my question is just, what does this (frankly weird) Bernstein complaint have to do with any of it? Bernstein himself is a NISTPQC participant; he's on one of the (large) winning signature teams.
(I think all the technical details here are super interesting, but not especially motivating; I'm not a cryptographer and you should disregard me as well, but my basic take on QC crypto attacks is "Rodents of unusual size? I don't think they exist.")
The OpenSSH decision to promote NTRU-prime from an experimental feature to the preferred key exchange was breathtakingly rapid, and final. It is a tacit assertion that NIST is no longer relevant.
DJB was on several teams, and I think that OpenSSH would lend greater credence to him than any other council, deservedly so.
We might end up with SPHINCS+, but I will be surprised if KYBER is adopted.
This moved very fast.
One reason KYBER got standardized quickly is that PQC KEMs are time-sensitive if you believe the quantum attack threat is plausibly material within the next 10-15 years. Your adversary in these attacks will almost certainly be state signals intelligence groups, and the expense involved in building attack hardware dwarfs the expense of collecting traffic today to decrypt in 2034. If you're a PQC believer, you want something out the door soon.
I don't understand the special sway you think Bernstein has, versus all the other cryptographers that participate in NISTPQC, with the OpenSSH team. I worry that people believe stuff like this because they know who Bernstein is and what OpenSSH is, and don't off the top of their head know who Tancrède Lepoint is. Note also that the KYBER team includes Peter Schwabe, whose name you should definitely know if you're a Bernstan.
Aside from adherence to DJB, the question will be what can be trusted?
We have been down this road before.
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).
> 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.
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")
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.
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?
> 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.
"It's slower and uses more memory" goes a long way in encouraging the evaluation of other options.
Press release: https://techxplore.com/news/2022-07-nist-quantum-resistant-c...
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?
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.
https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...
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.
Unfortunately that’s pretty uncommon so everyone has to go by base rates (crypto algorithms seem to last x years historically) and vague guesses (quantum computer capabilities seem to be doubling every x years so I dunno maybe enough qbits by 2050)
Ok, let's get a try from a mildly informed person, that is also probably better than the 90% average...
The number of qbits seems to be growing linearly, at about 7 qbits every 2 years. Extending that trend says that none of us will ever see a quantum computer break 256-bits ECC.
But I really doubt the trend will hold. Quantum computing seems prone to surprise gains, and those are unpredictable by their nature.
About this:
> crypto algorithms seem to last x years historically
I don't think we have enough data to decide on an average, but the distribution does surely look fat-tailed, so any statistic summary you make from it will be useless.
If history tells anything, it is that algorithms that have minor attacks will be broken quickly, and algorithms that don't have minor attacks will survive for very long.
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...
Bitcoin uses ECDSA to validate whether coins were spent by the owner of an address.
https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_...
This tells me that Algorand is one of the more serious blockchain projects out there with top cryptographers as evidenced by Falcon.
Any predictions on these time scales are pretty much pointless.
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.
https://arxiv.org/pdf/2009.05045v1.pdf
See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.
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
> 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?
See also sha-3 vs sha-256
NP is the set of all functions that you can verify a solution to in polyomial time, and the solution of the inverse-hash function is just a plaintext that hashes to the right value, and obviously you can check if a plaintext is right in polynomial time by just hashing it and comparing the hashes. Thus reversing a hash function is in NP, so if P=NP it's in P.
There's some subtlety here in that "reversing" a hash function really just means coming up with a plaintext that generates the right hash, not the original one, but you can put any polynomial-time set of constraints on the plaintext and finding a plaintext that satisfies those constraints (and hashes to the right value) is still in NP, so the subtlety really doesn't save you much.
Edit:
Side point, but since we're talking quantum, we should really be saying BQP=NP not P=NP, BQP being the problems solvable in polynomial time on a quantum computer, it's a superset of P and a subset of NP, but we don't know if it's equal to either or both. I.e. P=NP implies BQP=NP, BQP != NP implies P != NP, BQP != P implies P != NP, but the reverse of all of those statements isn't known to be true.
They didn't feel the need to provide multiple recommendations during the AES, or the SHA-3 process, even though Rijndael and Keccak used different constructions relative to RC6/TwoFish and SHA-2/Blake2. Why now?
SHA-3 was explicitly alternative reccomendation. The entire point was to come up with something that was not based on sha-2, because they were worried that the attacks on md5/sha1 could be extended to sha2 (which didn't really happen the way people were worried about). Even to this day, general advice is not to use sha3.
Less clear cut for aes, but at time of standardization (and even now afaik), triple des was considered secure, so its not like there wasn't a secure alternative.
These standards arent meant as implementation guides. You still need cryptography knowledge to securely use them.
So best practice would seem to be to implement both CRYSTALS-Dilithium and SPHINCS+, set CRYSTALS-Dilithium as the default, and provide a switch (config setting, whatever) to switch to SPHINCS+. If you have long-term keys, you should have both forms set up & ready to use.
Presumably, they'll have a better idea by then.
Cryptography is driven by defense applications. For all us civilian types know, these algorithms have been around for 30 years.
I'm having trouble finding it now but I recall someone complaining about the constants for 512 leaving something to be desired.
But proving that the input state is evenly mixed among the output state is THE hard thing to prove (the hash function equivalent of the difficulty of factoring integers), so for the sake of ecosystem diversity NIST chose a hash function based on different principles for SHA-3. It’s not a criticism of SHA-2 that the difference was called out.
The constants are the fractional bits of of successive cube roots. This is effectively a nothing-up-my-sleeve random number selection. If there are problems with this, that in itself would be a serious cryptographic result.
Perhaps NIST knows something we don't ; ^ )
[1] - https://twitter.com/CJTjhai/status/1544398903591796736
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).
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.
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!)
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.
Good news is that we are likely more than 10 years away from QCs being useful enough to do this.
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.
There's a linked PDF paper with more detail.
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.
Quickly (cause I probably won't for a few days), (q//2)m can be seen as a form of error correction. You can check (either pen+paper or programmatically) that, provided |e| < q/4, if noisy_m = (q//2) m + e, then round(noisy_m / (q/4)) = m. So e vanishes because it is bounded (not uniform), + we encode m as (q//2)*m (i.e. in the "most significant bits" of the number).