I took image from Simons Institute's presentation. Complexity classes of Approximate SVP problem according to approximation factors are given in the table. My question is, What is the meaning of blue arrow -Crypto- in this picture?


Lattice-based cryptography is based on the hardness of certain lattice problems (almost tautologically). The region marked "crypto" denotes the region of approximation factors $\gamma$ such that:

  1. We know how to construct cryptographic primitives assuming the hardness of $\mathsf{SVP}_\gamma$
  2. It is plausible that $\mathsf{SVP}_\gamma$ is hard (as there are not known poly-time algorithms).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.