2022.02.18 22:28:22 (1494785887552499713) from Daniel J. Bernstein, replying to "Lukas Prokop (@meisterluk)" (1494671385502924800):
Useful reading on some of the basic obstacles: https://www.iacr.org/archive/crypto2006/41170129/41170129.pdf; https://lucatrevisan.github.io/pubs/redux-sicomp.pdf. Increasing approx factors moves from NP-hard to no real hope of proving NP-hard, then to problems that break KEMs (also no hope of converse!), then to problems that have been broken.
2022.02.18 08:14:45 (1494571069839065088) from Daniel J. Bernstein:
No. Lattice KEMs under consideration for deployment (NTRU, Kyber, Frodo, etc.) do _not_ have NP-hardness proofs. (There's also no serious hope of crossing the dividing lines.) Questions to ask: Where did the pervasive misinformation on this topic originate? Who benefits from it?
2022.02.18 14:53:22 (1494671385502924800) from "Lukas Prokop (@meisterluk)":
Where can one expect difficulties bridging the dividing lines between SVP NP-hardness and NTRU/Saber/Kyber? (Serious question out of curiosity)