7
$\begingroup$

Consider the following question:

Let $N$ be some large prime number, and suppose we are given $n$ uniformly independent samples $g_i$ from $0...,N-1$. Think of $N$ as being exponentially large in $n$. Denote the sampled vector by $g = (g_1,...,g_n)$.

The question is: find a vector $h = (h_1,...,h_n)$ with $h \cdot g = 0 \mathrm{\ mod\ } N$, such that $max_{i\in [n]}(|h_i|)$ is of minimal size.

On one hand, ergodic theory tells us that with high probability, for such uniform $g$, the "average" magnitude of a perpendicular $h$ as defined here is $\Omega(N)$, up to possible logarithmic factors. Concretely: Let $r(h) = \prod_{i=1}^n max(1,|h_i|)$ and define $$ R(g,N) = \sum_{h\in [N]^n, h \cdot g = 0} r(h)^{-1}. $$ Then a theorem by Niederreiter shows that $$ \mathbf{E}_g [R(g,N)] = \Theta(\log^n(N)/N). $$ Since there are $N^{n-1}$ vectors perpendicular to $g$ modulo $N$, it implies that the "typical" value of $r(h)$ is $N^{n}$, so the typical coordinate is $\Omega(N)$.

On the other hand, algorithmically the situation seems a bit different: for uniformly random vector $g$, it is very likely that at least two coordinates, say $g_1,g_2$ share a large greatest-common-divisor of magnitude, say $\sqrt{N}$. This implies that one can find a vector $h = (h_1,..., h_n)$, with $h_3 = h_4 = ... = h_n = 0$ perpendicular to $g$ with $max_i |h_i| = O(\sqrt{N})$. Thus a little computation (e.g. computing the GCD) goes a long way in reducing the magnitude of the solution from the "average" magnitude of $N$.

So while this problem is probably NP-hard, I am interested in how hard is it to approximate ? Does it capture the hardness of all lattice problems, or is it somewhat easier?

$\endgroup$
  • $\begingroup$ This looks quite a lot like the Short Integer Solution problem, except that you're considering an inner product instead of a matrix-vector multiplication. (There's a great deal of cryptography based on the average-case hardness of approximating SIS to small polynomial ratios.) If you haven't seen SIS, take a look; if you have seen SIS, what's the relation? Have you thought about it? $\endgroup$ – Daniel Apon Feb 20 '16 at 4:46
  • $\begingroup$ Thanks. Indeed SIS is very related, and is one of the motivations for this question. But note two critical differences: first, as you point out, as an SIS this is a rank-1 matrix A. The worst-to-average case reductions of Ajtai talk about a random integer lattice $A \in Z^{n\times m}$, which has generically rank $n$ I presume. Hence the lattice that arises from the problem above is not a "typical" lattice, that presumably is "equivalent" to the worst-case. On the other hand in SIS, for the field of interest ($GF(N)$) - we take $N = poly(n)$, whereas here it is exponential. $\endgroup$ – Lior Eldar Feb 20 '16 at 17:26
  • $\begingroup$ SIS is still well-defined for any approximation ratio / modulus, and there are many (unbroken/plausible) cryptosystems that assume the hardness of approximating LWE/SIS to superpolynomial or subexponential factors (in the dimension $n$). Basically: LLL and its variants give you an $\exp(n)$ approximation, but that's all. ... Anyway, I don't immediately see a reduction from any common flavor of hard lattice problem, but I can't rule it out either.. (In short: "Hard to say, for me") $\endgroup$ – Daniel Apon Feb 21 '16 at 14:56
  • $\begingroup$ (A "stupid" idea is to try to partition the vector $g$ into $\sqrt{n}$ vectors of $\sqrt{n}$ length, and see if you can reduce from $\sqrt{n}$-dimensional SIS.) $\endgroup$ – Daniel Apon Feb 21 '16 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.