Comment by nefitty | Hacker News Reader

Comment by nefitty | Hacker News Reader

Thanks to the informative resources linked to by jack4818 and ototot I was able to slightly wrap my head around this. I'll share my barely informed, naive understanding in the hopes that it'll help others in a similar position build on it. Please correct me if any of what I share is mistaken!

Quantum computers have special properties that make them capable of breaking commonly used encryption schemes. We're dependent on those schemes for secure communication, like logging into a bank website. Due to this, the organization NIST has been working on finding encryption schemes that would be diffcult to break with a quantum computer.

NIST was at the stage of this project where they felt reasonably confident that three specific encryption schemes met the requirements. This is after review of many candidates. Rainbow made it to the top three. Ward Buellens essentially managed to break Rainbow, thereby making it ineligible for use in a quantum computer-powered future.

I assume this puts the two remaining candidates' eligibility into question. Were the requirements lacking, or is the project inherently at risk of failure due to the nature of quantum computing?

Rainbow is a signature scheme.

Generally it seems the encryption side of post quantum is a bit easier than the signature side. All signature schemes proposed have significant downsides.

(though this result raises very serious questions about the whole process - if it's possible that a promising candidate which probably would've been standardized very soon can be broken so severely it questions whether we know enough about these technologies to standardize them yet)

Ah gotcha. Thank you for taking the time to clarify!

Quantum computers are good at solving the hidden subgroup problem, which generalizes RSA and Diffie Hellman.

The reason they do well in this area is that you can implement a Fourier transform with exponentially fewer quantum logic gates than classical logic gates.

Post quantum involves implementing a cryptosystem which can not be reduced to a hidden subgroup problem, but I’m still not sure if this is sufficient (QIP might solve other classes of problems easily)

Do you have a good reference on the relationship between quantum computers and Fourier transforms? I’m a DSP researcher by day and this is the first time I’ve heard about this, so my interest is piqued.

There is an excruciating amount of papers, but at least it has a sensible name: you can google “quantum Fourier transform” and go down the rabbit hole of suffering from there :D

"... or is the project inherently at risk of failure due to the nature of quantum computing?"

You already and automatically know it's not that, because the article was not about breaking the encryption with a quantum computer.

It was broken with trivial hardware and in trivial time.

Good point. My mistake.

Reply on news.ycombinator.com