CryptoDB
On Basing Search SIVP on NP-Hardness
| Authors: | |
|---|---|
| Download: | |
| 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. |
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
}