6

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $NP$-hard problem. The story is rather simple, but also technical. Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case ...


4

They don't need to be: isogeny-based cryptography has no connection to any NP-complete problems, as far as I am aware. Generally you want the underlying mathematical problem to be hard, and you can't get "harder" than NP, since (to be very imprecise) the secret key of a public-key cryptosystem acts like a "witness" for any hard problem ...


Only top voted, non community-wiki answers of a minimum length are eligible