Hacker News Reader

Comment by steelframe | Hacker News Reader

Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure. One reason why this is significant is because existing post-quantum public key algorithms such as SPHINCS+ use much larger keys than classic public key algorithms such as RSA or ECDH.

*Edit: As other have pointed out, for SPHINCS+ it's the signature size and not the key size that's significantly larger.

View on HN

Only PQ hash functions are PQ FWIU. Other cryptographic hash functions are not NIST PQ standardization finalists; I don't think any were even submitted with "just double the key/hash size for the foreseeable future" as a parameter as is suggested here. https://news.ycombinator.com/item?id=25009925

NIST Post-Quantum Cryptography Standardization > Round 3 > Selected Algorithms 2022 > Hash based > SPHINCS+: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...

SPHINCS+ is a hash based PQ Post Quantum (quantum resistant) cryptographic signature algorithm.

SPHINCS+: https://github.com/sphincs/sphincsplus

For those here who don’t know

SPHINCS is essentially Lamport Signatures and SPHINCS+ is essentially removing the need to store “state” by using chains of hashes and a random oracle

https://crypto.stackexchange.com/questions/54304/difference-...

I prefer tham to lattice-based methods because it seems to me that cryptographic hashes (and other trapdoor functions) are more likely to be quantum-resistant than lattices (for which an algorithm like Shor’s algorithm merely hasn’t been found yet).

In case you haven't seen, there was actually a quantum algorithm on preprint recently for solving some class of learning with errors problems in polynomial time. https://eprint.iacr.org/2024/555

And since you apparently haven't seen, the abstract now includes the following note.

> Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.

Oops, I did not, thank you!

Minor note, I'm not an expert in this field but I believe SPHINCS+ uses smaller key sizes than RSA, but is notable for producing much larger signatures than RSA or ECDSA.

> Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure

Can you elaborate on this?

Inverting a general-purpose cryptographic hash function in the quantum setting is (roughly) as hard as it is in the classical setting.

(Roughly because of Grover’s algorithm, but there are algorithms that perform similarly or better on classical machines. Which is why modern hash functions have relatively large margins anyways.)

Reply on news.ycombinator.com