Live data from Hacker News

NIST announces first PQC algoritms to be standardized

groups.google.com

91–100 of 132 posts

Re: NIST announces first PQC algoritms to be standardized

#91
post #72

Earlier quoted context omitted.

I was thinking, if you could definitively prove these assumptions are hard, that would prove P != NP, because if P=NP that would imply there would be an algorithm to solve these types of problems, since they are the type of thing that can be solved in polynomial time with the key, but cannot without a key. (I'm a bit out of my depth here)

For the stuff underlying asymmetric keys, yes. The hash function stuff doesn’t have backdoors.

Hash functions too. If P=NP then you can reverse a hash in polynomial time.

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.

Re: NIST announces first PQC algoritms to be standardized

#92

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?

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

Re: NIST announces first PQC algoritms to be standardized

#93
post #35

Earlier quoted context omitted.

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.

Bernstein seems to be involved in never ending drama. Maybe the problem is him?

Can you summarize? That’s a PDF I can’t read.

Re: NIST announces first PQC algoritms to be standardized

#94
post #35
post #22

Earlier quoted context omitted.

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

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.

I can't seem to find anything on google, did NISTPQC ever reply?

Re: NIST announces first PQC algoritms to be standardized

#95

Earlier quoted context omitted.

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.

Non-cryptographers should not be implementing NIST standards. You should be using higher level APIs written by cryptographers which do employ NIST standards in the details.

If you're including cryptography in a system design, you are almost certainly relying on NIST standards to select algorithms.

Re: NIST announces first PQC algoritms to be standardized

#96
post #74
post #41

Earlier quoted context omitted.

Life's hard and the world is uncertain. If NIST could make an algorithm that they could prove was 100% safe with no possibility of future cryptoanalytical breakthroughs, i am sure they would, but that is beyond current state of the art.

You mean like a one-time pad? I'm sure the folks at NIST know about it; it is completely unbreakable and had been around for a while. Use is not really practical though, so typically reserved for very specific use cases.

This is a silly nitpick. I think its pretty well understood from context i meant a practical quantum safe key agreement algorithm. One time pad cannot be used for that purpose at all, let alone practically.

Re: NIST announces first PQC algoritms to be standardized

#97

Earlier quoted context omitted.

Bernstein seems to be involved in never ending drama. Maybe the problem is him?

Can you summarize? That’s a PDF I can’t read.

There's some technical details that I'm not good enough to summarize, but a large gist of it seems to be that the NISTPQC seems to have gone back on it's word about being transparent through the standardization process and only ever solicited private input after round 2 and round 3 and used that non-published input to make claims about the strength of at least one contender for the standardization. And the way they've done this appears to reek of Dual EC style manipulation again from what DJB brings up? at least as far as how the process is working. I don't believe he's claiming that there's any NSA back doors but alluding to there being a private party that is steering things in ways that might not be good.

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).

Re: NIST announces first PQC algoritms to be standardized

#100
post #35

Earlier quoted context omitted.

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.

Bernstein seems to be involved in never ending drama. Maybe the problem is him?

Bernstein being "involved in never-ending drama" is the reason it's legal to export strong cryptography from the US today and the reason much of this PQC work got done at all. He's clearly a person who often fights in cases where almost everyone else surrendered instead, which is presumably what you mean by "the problem is him," but I don't see why you describe it as a "problem". His inclination to tell hard truths, even when faced with corruption and intimidation, has frequently served the public interest.

It was often a huge problem for the people who he was fighting with, though. Are you one of them?

Post reply on HN