The possibility of basing cryptography on the minimal assumption NPBPP 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 -approximate shortest independent vector problem .
Although SIVP is NP-hard in its exact version, Guruswami et al (CCC 2004) showed that is in NPcoAM and thus unlikely to be NP-hard. Indeed, any language that can be reduced to (under general probabilistic polynomial-time adaptive reductions) is in AMcoAM 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 ?
We eliminate such possibility, by showing that any language that can be reduced to solving search with any approximation factor lies in AM intersect coAM. As a side product, we show that any language that can be reduced to discrete Gaussian sampling with parameter lies in AM intersect coAM.
PDF
