Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

NIST selects HQC as fifth algorithm for post-quantum encryption

nist.gov

Post reply on HN
Print view View original

81–90 of 126 posts

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#81

Post by tptacek »

immibis wrote: post #80
tptacek wrote: post #64

Earlier quoted context omitted.

Explain what the compromised selection process does here. NIST doesn't control the submissions.

Seems pretty obvious no? 1. Pretend to be someone else and enter a backdoored algorithm. Or pressure someone to enter a backdoored algorithm for you. Or just give them the algorithm for the reward of being the winner. 2. Be NIST, and choose that algorithm.

You think someone is going to pretend to be Chris Peikert and submit a backdoored construction as him, and that's going to work?

This is the problem with all these modern NIST contest theories. They're not even movie plots. Your last bit, about them paying someone like Peikert off, isn't even coherent; they could do that with or without the contest.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#82

Post by dist-epoch »

FateOfNations wrote: post #74
throw_pm23 wrote: post #68

Earlier quoted context omitted.

Sorry if my question appears ignorant, but how quickly is quantum really coming? If your prior belief is "nothing practical is ever likely to come out of quantum computing", then so far there is nothing that would seriously suggest you to reconsider it. I do not say this lightly, having followed the academic side of QC for more than a decade.

Given how seriously the spookie parts of the US government are taking it, I would treat it with a similar level of urgency. While we obviously aren't privy to everything they know, their public actions indicate that they don't think it's a hypothetical risk, and is something that we will need to be ready for within the next decade or so, given technology refresh cycles: they need to get these crypto algorithms in pla…

> Given how seriously the spookie parts of the US government are taking it, I would treat it with a similar level of urgency

Various US standards require encryption algorithms to be considered safe for the next 30 years.

Sufficiently big quantum computers are likely in the next 30 years, but it's not urgent in any other meaning of the word.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#83

Post by bryan0 »

WaitWaitWha wrote: post #57
throw0101c wrote: post #19

Meta: I can understand the math problems behind RSA and DH, and the general concepts of EC, but all stuff for post-quantum algorithms I have yet to have a intuitive understanding even after reading / watching a bunch of videos trying to explain things.

I was in the same exact boat. I just could not digest it. I found AI (combo Grok & ChatPPT 4o) to be the best resource for this. It was able to break it down to digestible chunks, then pull it together that made sense. It even made suggestions what math areas I need to brush up on.

I just did the same thing. Claude (sonnet 3.7) walked me through a toy implementation of the algorithm.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#84

Post by tptacek »

throw0101c wrote: post #19

Meta: I can understand the math problems behind RSA and DH, and the general concepts of EC, but all stuff for post-quantum algorithms I have yet to have a intuitive understanding even after reading / watching a bunch of videos trying to explain things.

The intuition for ML-KEM-style lattice cryptography is actually kind of straightforward. Generate a secret vector x and a random matrix A; multiply Ax, then corrupt it with a random vector of errors e, so instead of Ax=b you have Ax+e=b.

Solving Ax=b is like week 2 of undergraduate linear algebra. Solving Ax+e=b, in a lattice setting, is Hard in the same sense factoring is: as you run the steps of elimination to attempt to solve it, the errors compound catastrophically.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#85

Post by iovoid »

throw0101c wrote: post #19

Meta: I can understand the math problems behind RSA and DH, and the general concepts of EC, but all stuff for post-quantum algorithms I have yet to have a intuitive understanding even after reading / watching a bunch of videos trying to explain things.

The hash-based one (SPHINCS+) is probably the easiest to understand as its security hinges on hashes being secure, and some statistics.

I found https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step... to be a nice introduction.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#86

Post by j_chance »

tptacek wrote: post #84
throw0101c wrote: post #19

Meta: I can understand the math problems behind RSA and DH, and the general concepts of EC, but all stuff for post-quantum algorithms I have yet to have a intuitive understanding even after reading / watching a bunch of videos trying to explain things.

The intuition for ML-KEM-style lattice cryptography is actually kind of straightforward. Generate a secret vector x and a random matrix A; multiply Ax, then corrupt it with a random vector of errors e, so instead of Ax=b you have Ax+e=b. Solving Ax=b is like week 2 of undergraduate linear algebra. Solving Ax+e=b, in a lattice setting, is Hard in the same sense factoring is: as you run the steps of elimination to atte…

Solving `Ax=b` is easy if `x` can be any value. But if you bound `x` such that all entries must be small (e.g. only zeroes and ones) then the problem is hard: https://en.wikipedia.org/wiki/Short_integer_solution_problem

What you described would be closer to learning with errors (https://en.m.wikipedia.org/wiki/Learning_with_errors) combined with SIS/SVP. Learning with errors is based on the parity learning problem (https://en.m.wikipedia.org/wiki/Parity_learning) in machine learning, which I take as a positive sign of security.

Interestingly you can get information theoretically secure constructions using lattices by tuning the parameters. For example, if you make the `A` matrix large enough it becomes statistically unlikely that more than 1 solution exists (e.g. generate a random binary vector `x` and it's unlikely that an `x'` exists that solves for `b`).

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#87

Post by mort96 »

dist-epoch wrote: post #82
FateOfNations wrote: post #74

Earlier quoted context omitted.

Given how seriously the spookie parts of the US government are taking it, I would treat it with a similar level of urgency. While we obviously aren't privy to everything they know, their public actions indicate that they don't think it's a hypothetical risk, and is something that we will need to be ready for within the next decade or so, given technology refresh cycles: they need to get these crypto algorithms in pla…

> Given how seriously the spookie parts of the US government are taking it, I would treat it with a similar level of urgency Various US standards require encryption algorithms to be considered safe for the next 30 years. Sufficiently big quantum computers are likely in the next 30 years, but it's not urgent in any other meaning of the word.

Well, that depends on whether or not you care about "store now, decrypt later". Will the info you're sending now be totally uninteresting in 5 years? Great, you're probably good. Do you still want it to be secret in 20 years? Implementing post-quantum cryptography might be urgent.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#89

Post by rdtsc »

Y_Y wrote: post #37
rdtsc wrote: post #34

Earlier quoted context omitted.

Heh. That's fair. I wonder what other countries do? Do their agencies trust NIST or they recommend their own and run their programs for algorithms. I am thinking of say Germany, France, Britain etc.

They have their own agencies responsible, but take note of what NIST says (especially the UK). https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisati... https://cyber.gouv.fr/sites/default/files/document/pqc-trans... https://www.ncsc.gov.uk/whitepaper/next-steps-preparing-for-...

Thank you. It seems they sort of follow NIST's guidelines mostly:

> The NCSC recommends ML-KEM-768 and ML-DSA-65 as providing appropriate levels of security and efficiency for most use cases.

Re: NIST selects HQC as fifth algorithm for post-quantum encryption

#90

Post by 0xDEAFBEAD »

formerly_proven wrote: post #65
chowells wrote: post #63

Earlier quoted context omitted.

You generally don't want to layer encryption like that. It apparently really does introduce new kinds of attacks, which has been observed in the real world. The pattern typically used for this is that the key for the high-speed symmetric encryption is split into multiple parts, each of which is encrypted with a separate public key system. One classical, one (or two, now?) with a post-quantum algorithm. As long as eac…

Do not! Use a combiner / KDF.

Curious why this is being downvoted.
Post reply on HN