## IACR paper details

Title | On Basing Search SIVP on NP-Hardness |
---|

Booktitle | Theory of Cryptography |
---|

Award | **Best Student Paper** |
---|

Volume | 11239 |
---|

Pages | 98-119 |
---|

Year | 2018 |
---|

URL | Search for the paper |
---|

DOI | 10.1007/978-3-030-03807-6_4 (link) |
---|

Author | Tianren Liu |
---|

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. |
---|

@article{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
}

Download a complete BibTeX file.