Hacker News Reader

Comment by krior | Hacker News Reader

But their post-quantum-algorithm also uses sha256. Afaik only asymetric crypto is in danger from quantum computers.

Ah it's interesting, AIUI cryptographic hashes are safe from quantum attacks (for there's an infinity of secrets that, once hashed, give a specific hash and hence somehow it's not possible to use a quantum computer to forge what you'd want).

And from the other comment, symmetric cryptography is safe too from QC attacks.

So it's apparently as you wrote: it's really only asymmetric crypto that is at risk.

> AIUI cryptographic hashes are safe from quantum attacks (for there's an infinity of secrets that, once hashed, give a specific hash and hence somehow it's not possible to use a quantum computer to forge what you'd want).

Quantum algorithms require some sort of quantum 'trick' to actually have any speedup over classical computers. The most general quantum trick is Grover's algorithm, which lets you find f⁻¹(x) (given f and x) in sqrt(N) queries rather than N queries, where N is the size of the set from which x is drawn. This cuts the bit security of every algorithm in half, although for things like cryptographic hashes, it really means that a second preimage is now only as 'easy' as finding a collision (due to the birthday attack).

The other really well-known quantum trick is QFT, which allows you to find the period of an unknown periodic function really quickly. This is what allows quantum computers to break asymmetric algorithms based on integer factoring or elliptic curves, since they can both be expressed in terms of the QFT.

Reply on news.ycombinator.com