Welcome to the resource topic for 2016/906
Title:
On Basing Search SIVP on NP-Hardness
Authors: Tianren Liu
Abstract:The possibility of basing cryptography on the minimal assumption NP$\nsubseteq$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)-approximate shortest independent vector problem \text{SIVP}_{\tilde O(n)}. Although SIVP is NP-hard in its exact version, Guruswami et al (CCC 2004) showed that \text{gapSIVP}_{\sqrt{n/\log n}} is in NP$\cap$coAM and thus unlikely to be NP-hard. Indeed, any language that can be reduced to \text{gapSIVP}_{\tilde O(\sqrt n)} (under general probabilistic polynomial-time adaptive reductions) is in AM$\cap$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 NP be reduced to solving search SIVP with approximation factor \tilde O(n)? We eliminate such possibility, by showing that any language that can be reduced to solving search \text{SIVP}_{\gamma} with any approximation factor \gamma(n) = \omega(n\log n) lies in AM intersect coAM. As a side product, we show that any language that can be reduced to discrete Gaussian sampling with parameter \tilde O(\sqrt n)\cdot\lambda_n lies in AM intersect coAM.
ePrint: https://eprint.iacr.org/2016/906
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .