<p>Consider the following question:</p>

<p>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)$.</p>

<p>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.</p>

<p>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)$.</p>

<p>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$.</p>

<p>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?</p>

CC BY-SA 3.0
2016-02-20T04:46:58.333Z
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?
Daniel Apon
CC BY-SA 3.0
2016-02-20T17:26:01.660Z
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.
Lior Eldar
CC BY-SA 3.0
2016-02-21T14:56:52.397Z
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")
Daniel Apon
CC BY-SA 3.0
2016-02-21T15:03:32.853Z
(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.)
Daniel Apon
<nt.number-theory><comp-number-theory><lattice><integer-lattice>
Simplified lattices
Lior Eldar
# Simplified lattices

(Asked by: username_0 on 2016-02-19)

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?

**Tags:** nt.number-theory, comp-number-theory, lattice, integer-lattice
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_1**: 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")  
> **username_1**: (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.)  

---

## 0 answers

