The microblog: 2022.02.18 22:28:22

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:; 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)