10
$\begingroup$

A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications to solving $\mathsf{SIS}_{n,m,q,4}$ in $\mathsf{P}$.

I'm no expert in this area, but it seems to me this contradicts the common thought that $\lambda_1(\Lambda^\perp(\mathbf{A})) = \Omega(\sqrt{n\log q})$ (see, for example, section 2.4.2 of this paper).

As getting into the details of the recent paper is likely off topic for this forum, I'm interested instead in another question --- what concrete/experimental evidence has been collected for the asymptotics of $\lambda_1(\Lambda^\perp(\mathbf{A}))$? Looking into data such as this would be an easy way to gain intuition for whether we're in an $O(1)$ regime or $\Omega(\sqrt{n\log q})$ one, and I had assumed that someone had papers along these lines, but don't actually recall seeing any of it myself.

$\endgroup$
  • 2
    $\begingroup$ I contacted the authors, one of whom (Jia Huiwen in particular) replied: (after translation) Currently there isn't a specific algorithm, it's only deduction on theoretical level, also there's a problem with the proof in the article which we're fixing. $\endgroup$ – DannyNiu Jan 17 '19 at 5:51
  • 2
    $\begingroup$ @DannyNiu Their claim that $\lambda_1(\Lambda^\perp(A)) = O(1)$ shouldn't be dependent on any particular algorithm though. For a particular distribution over $A$ (with fixed $m,n,q$), we have that $\lambda_1(\Lambda^\perp(A))$ is simply a statistic, and should be able to be estimated computationally. Then, by repeating this for various $m,n,q$, you should be able to gain some intuition for the asymptotic properties of $\lambda_1(\Lambda^\perp(A))$. I'm curious if anyone has done this computational exercise, and made some paper out of it (for example), as this seems plausible. $\endgroup$ – Mark Jan 17 '19 at 6:18
  • $\begingroup$ @DannyNiu That being said, I appreciate your update with regards to that paper! $\endgroup$ – Mark Jan 17 '19 at 6:19
  • 3
    $\begingroup$ It looks like the bug is in the proof of the (false) inequality labeled "on the other hand" on page 7. E.g., a random lattice has $bl \approx \sqrt{n}$ but $\rho_1(L^*) \approx 2$. So, they're inequality says $2 \gtrsim \sqrt{n}$. Their proof of this inequality seems to boil down to an argument that the dual lattice $L^*$ always has a vector of length $1/bl$, which is false in general. It has a vector of length $1/\|\tilde{b}_n\|$, but typically not a vector of length, e.g., $1/\|\tilde{b}_1\|$. $\endgroup$ – Noah Stephens-Davidowitz Jan 17 '19 at 16:32
14
$\begingroup$

The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $n$-dimensional lattices $L$ (i.e., $L^* = L$) where $\lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$, hence $\eta_{2^{-n}}(L) = O(1)$ but $\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$.

The statement and proof of Conway and Thompson's result can be found as Theorem 9.5 in https://www.springer.com/us/book/9783642883323 .

$\endgroup$
13
$\begingroup$

Independently of the algorithmic claim, I indeed have serious doubts about Theorem 2. Here is a counterargument (using standard techniques) cooked up with Yang Yu and Wessel van Woerden:

Suppose that $q$ is prime, and suppose that the minimum distance in the 2-norm is indeed bounded by $b=O(1)$. There are at most $Binom[m,b] \cdot (2b+1)^b = poly(m)$ elements x in $\mathbb Z^m \setminus \{0\}$ with $||x||^2_2 \leq b$. But every such vector has only probability $q^{-n}$ to be part of the lattice over the randomness of $A$. By a union bound this means that the probability that any such vector is part of the lattice over the randomness of $A$ is at most $poly(m) \cdot q^{-n}$ which is negligible unless m itself is exponential in $n$.

$\endgroup$
  • 2
    $\begingroup$ You are right and this can be turned into a simple proof (see Micciancio's lecture notes, Exercise 4). So without looking at the paper in detail, it seems there must be something wrong with the proof. $\endgroup$ – blowfish Jan 17 '19 at 9:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.