Paper 2016/906

On Basing Search SIVP on NP-Hardness

Tianren Liu


The possibility of basing cryptography on the minimal assumption NP$\nsubseteq$BPP is at the very heart of complexity-theoretic cryptography. The closest we have gotten so far is lattice-based cryptography whose average-case security is based on the worst-case hardness of approximate shortest vector problems on integer lattices. The state-of-the-art is the construction of a one-way function (and collision-resistant hash function) based on the hardness of the $\tilde{O}(n)$-approximate shortest independent vector problem $\text{SIVP}_{\tilde O(n)}$. Although SIVP is NP-hard in its exact version, Guruswami et al (CCC 2004) showed that $\text{gapSIVP}_{\sqrt{n/\log n}}$ is in NP$\cap$coAM and thus unlikely to be NP-hard. Indeed, any language that can be reduced to $\text{gapSIVP}_{\tilde O(\sqrt n)}$ (under general probabilistic polynomial-time adaptive reductions) is in AM$\cap$coAM by the results of Peikert and Vaikuntanathan (CRYPTO 2008) and Mahmoody and Xiao (CCC 2010). However, none of these results apply to reductions to search problems, still leaving open a ray of hope: can NP be reduced to solving search SIVP with approximation factor $\tilde O(n)$? We eliminate such possibility, by showing that any language that can be reduced to solving search $\text{SIVP}_{\gamma}$ with any approximation factor $\gamma(n) = \omega(n\log n)$ lies in AM intersect coAM. As a side product, we show that any language that can be reduced to discrete Gaussian sampling with parameter $\tilde O(\sqrt n)\cdot\lambda_n$ lies in AM intersect coAM.

Note: The intro is rewritten for eurocrypt

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2018
separationlattice-based cryptography
Contact author(s)
liutr @ mit edu
2018-10-18: last of 3 revisions
2016-09-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianren Liu},
      title = {On Basing Search {SIVP} on {NP}-Hardness},
      howpublished = {Cryptology ePrint Archive, Paper 2016/906},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.