## CryptoDB

### Paper: On Basing Search SIVP on NP-Hardness

Authors: Tianren Liu DOI: 10.1007/978-3-030-03807-6_4 Search ePrint Search Google TCC 2018 Best Student Paper 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.
##### BibTeX
@inproceedings{tcc-2018-29005,
title={On Basing Search SIVP on NP-Hardness},
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11239},
pages={98-119},
doi={10.1007/978-3-030-03807-6_4},
author={Tianren Liu},
year=2018
}