On the Limits of Non-Approximability of Lattice Problems

Webpage for a paper by Goldreich and Goldwasser


Abstract

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of sqrt(n), of optimization problems in integer lattices; specifically, the closest vector problem (CVP), and the shortest vector problem (SVP). These interactive proofs are for the ``coNP direction''; that is, we give an interactive protocol showing that a vector is ``far'' from the lattice (for CVP), and an interactive protocol showing that the shortest-lattice-vector is ``long'' (for SVP). Furthermore, these interactive proof systems are Honest-Verifier Perfect Zero-Knowledge.

We conclude that approximating CVP (resp., SVP) within a factor of sqrt(n) is in the intersection of NP and coAM. Thus, it seems unlikely that approximating these problems to within a sqrt(n) factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al showed that the gap problem corresponding to approximating CVP within n cdot sqrt(n) (resp., approximating SVP within n) is in the intersection of NP and coNP. On the other hand, Arora et al showed that the gap problem corresponding to approximating CVP within exp(sqrt(log n)) is quasi-NP-hard.


Comment

In our paper, we only showed that these gap problems are unlikely to be NP-hard under smart Cook-reductions, where the latter are Cook-reductions that make no query the violates the promise (of the target promise problem).

Following the publication of our work, Jin-yi Cai and Ajay Nerurkar (see ``A note on the non-NP-hardness of approximate lattice problems under general Cook reductions'', IPL, Vol. 76, pages 61-66, 2000) observed that one can remove the restriction to smart reductions. Let us rephrase their result as folllows.

Theorem: Let Pi=(Yes,No) be a promise problem that satisfies the following three conditions: (1) the promise problem Pi is NP-hard under (general) Cook-reductions, (2) the promise problem Pi is in coAM, and (3) the set No is in coAM. Then AM=coAM.

In the paper we consider the promise problems gapCVP and gapSVP. As shown in the paper, the promise problem gapCVP (resp., gapSVP) is in coAM. Obviously, the set of no-instances is in coNP (and thus in coAM). Thus, if the promise problem gapCVP (resp., gapSVP) is NP-hard under (general rather than only smart) Cook-reductions then AM=coAM.

Proof: Let L denote the complement set of No; that is, L contains both the yes-instances and the instances that violate the promise of Pi. Recall that by our hypothesis, Pi is NP-hard (under Cook-reductions), Pi is in coAM, and L is in AM.

Consider the following prover strategy. The prover invokes the reduction machine answering all queries according to L, and sends its computation transcript. In addition, for queries in L, the prover invokes the AM-proof for proving membership in L. For queries out of L (i.e., queries in No), the prover invokes the AM-proof for proving membership in the complement of the promise problem Pi. Recall that the latter proof system is guaranteed to accept each input in No and reject each input in Yes.

Completeness: whenever the query is in Yes we answered yes (because Yes is a subset of L) and successfuly proved the validity of this answer. Furthermore, whenever the query is not in No (but is rather in L), we answered yes and successfuly proved the validity of this answer. (Note that in these cases we invoke the AM-proof for the set L.) On the other hand, whenever the query is in No (i.e., out of L), we answered no and successfuly proved the validity of this answer (via the AM-proof for proving membership in the complement of the promise problem Pi).

Soundness: Suppose a prover tries to cheat. Then it must supply an computation transcript with a "wrong" answer to some query. Intuitively, this query should be one that violates the promise of Pi, because otherwise both proof systems are guaranteed to work. But also in case the query violates the promise we are OK, because the reduction is resilient to any answer we give in this case (and so no answer is "wrong" in this case). Formally, if the query satisfies the Pi-promise, then the prover cannot convince the verifier of a wrong answer (for it). Thus, the prover is unlikely to provide an accepting computation of the reduction that uses wrong answers for these queries, and soundness follows by the validity of the reduction (which holds no matter how queries that violate the promise are answered).

Indeed, the key point is that violating queries, which are handled by the presecribed prover as members of L, do not disrrupt the emulation of the reduction. In the good case (i.e., completeness) violating queries are treated as yes-instances (which is fine), whereas in the bad case (i.e., soundness) we don't care about them. Furthermore, in the good case (i.e., completeness), using an AM-proof for L (rather than for Pi) guarantees that the completeness condition is satisfied. QED


Material available on-line


Back to either Oded Goldreich's homepage. or general list of papers.