International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Basing Search SIVP on NP-Hardness

Tianren Liu
DOI: 10.1007/978-3-030-03807-6_4
Search ePrint
Search Google
Conference: TCC 2018
Award: Best Student Paper
Abstract: The possibility of basing cryptography on the minimal assumption $$\mathbf{NP }\nsubseteq \mathbf{BPP }$$ NP⊈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)$$ O~(n)-approximate shortest independent vector problem $${\textsf {SIVP}}_{\tilde{O}(n)}$$ SIVPO~(n).Although $${\textsf {SIVP}}$$ SIVP is NP-hard in its exact version, Guruswami et al. (CCC 2004) showed that $${\textsf {gapSIVP}}_{\sqrt{n/\log n}}$$ gapSIVPn/logn is in $$\mathbf{NP } \cap \mathbf{coAM }$$ NP∩coAM and thus unlikely to be $$\mathbf{NP }$$ NP-hard. Indeed, any language that can be reduced to $${\textsf {gapSIVP}}_{\tilde{O}(\sqrt{n})}$$ gapSIVPO~(n) (under general probabilistic polynomial-time adaptive reductions) is in $$\mathbf{AM } \cap \mathbf{coAM }$$ AM∩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 $$\mathbf{NP }$$ NPbe reduced to solving search SIVP with approximation factor $$\tilde{O}(n)$$ O~(n)?We eliminate such possibility, by showing that any language that can be reduced to solving search $${\textsf {SIVP}}$$ SIVP with any approximation factor $$\lambda (n) = \omega (n\log n)$$ λ(n)=ω(nlogn) lies in AM intersect coAM.
  title={On Basing Search SIVP on NP-Hardness},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  author={Tianren Liu},