You are looking at a specific version 20161001:074240 of this paper. See the latest version.

Paper 2016/906

On Basing Search SIVP on NP-Hardness

Tianren Liu

Abstract

The possibility of basing cryptography on the minimal assumption $\textbf{NP}\nsubseteq \textbf{BPP}$ is at the very heart of textbflexity-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 $\textsf{SIVP}_{\tilde O(n)}$. Although $\textsf{SIVP}$ is \textbf{NP}-hard in its exact version, Guruswami et al (CCC 2004) showed that $\textsf{gapSIVP}_{\sqrt{n/\log n}}$ is in $\textbf{NP} \cap \textbf{coAM}$ and thus unlikely to be $\textbf{NP}$-hard. Indeed, any textsfuage that can be reduced to $\textsf{gapSIVP}_{\tilde O(\sqrt n)}$ (under general probabilistic polynomial-time adaptive reductions) is in $\textbf{AM} \cap \textbf{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 {\em search problems}, still leaving open a ray of hope: {\em can $\textbf{NP}$ be reduced to solving search SIVP with approximation factor $\tilde O(n)$?} We show that any textsfuage that can be reduced to solving search $\textsf{SIVP}$ with approximation factor $\tilde O(n)$ lies in \textbf{AM} intersect \textbf{coAM}, eliminating the possibility of basing current constructions on \textbf{NP}-hardness.

Note: The intro is rewritten for eurocrypt

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
foundationsseparation
Contact author(s)
liutr @ mit edu
History
2018-10-18: last of 3 revisions
2016-09-16: received
See all versions
Short URL
https://ia.cr/2016/906
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.