Finding Short Vectors in Random Lattices (the SIS Problem)

A fundamental computational question one can ask about a lattice is to find a “short” (nonzero) vector in it.

When specifically tailored to the lattices we’ve been dealing with above, the question simply becomes to

Lemma 4 states that when $\beta=q^{n /(n+m)}$ , such a vector surely exists, but the proof does not give us any way of finding it. As of today, all known (quantum) algorithms for finding such vectors (for uniformly random $\mathbf{A}$ ) take $2^{\Omega(m+n)}$ time (c.f. Ajtai et al., 2001 [, ADRS15, AS18]).

The next Lemma is a converse of the one above; it gives a lower bound on the length of an existing non-zero vector.

Proof. The proof is by the pigeonhole principle. There are more than $\left(q^{n /(n+m)}\right)^{n+m}=q^n$ vectors in $\mathbb{Z}^{n+m}$ whose coefficients are between 0 and $q^{n /(n+m)}$ . Since there are only $q^n$ possibilities for the value of $\mathbf{A z}$ mod $q$ , there must exist two distinct $\mathbf{z}_1, \mathbf{z}_2$ with coefficients in the aforementioned range such that $\mathbf{A} \mathbf{z}_1 \equiv \mathbf{A} \mathbf{z}_2(\bmod q)$ . Thus $\mathbf{z}_1-\mathbf{z}_2 \in\left[q^{n /(n+m)}\right]^{n+m}$ and $\mathbf{A}\left(\mathbf{z}_1-\mathbf{z}_2\right) \equiv \mathbf{0}(\bmod q)$ .

The problem does get easier as $\beta$ increases. Clearly if $\beta=q / 2$ , then the problem is trivially solved by just setting the coefficients of $\mathbf{z}$ that are being multiplied by $\mathbf{I}_n$ to the target coefficients. For smaller value of $\beta$ , one would run an algorithm that finds a vector in the lattice that is some factor larger than the smallest vector. All modern efficient (i.e. polynomial-time) algorithms for finding such short vectors are descendants of the famous LLL algorithm Lenstra et al., 1982 which guarantees to find a vector of length at most $2^{O(n+m)}$ times larger than that of the shortest vector in the lattice. Lemma 4 then implies that for a random $\mathbf{A}$ , the LLL algorithm will find a vector $\mathbf{z} \in\left[2^{\Omega(n+m)} \cdot q^{n /(n+m)}\right]^{n+m}$ in $\mathcal{L}_q^{\perp}\left(\left[\mathbf{A} \mid \mathbf{I}_n\right]\right)$ .

While the length of the vector the LLL algorithm is guaranteed to find is exponentially larger (in the dimension of the lattice) than the length of the shortest vector, in practice,

# Generate SIS problem instance
def generate_sis_instance(n, m, q, beta):
    """
    Generate a SIS (Short Integer Solution) problem instance
    
    Parameters:
    n: dimension parameter
    m: number of columns in matrix A
    q: modulus (should be prime)
    beta: bound on solution vector coefficients
    
    Returns:
    A: random matrix A of size n x m over Z_q
    target: target vector (usually zero vector)
    """
    
    # Generate random matrix A over Z_q
    A = random_matrix(Zmod(q), n, m)
    
    # For SIS problem, target is usually zero vector
    target = vector(Zmod(q), [0] * n)
    
    print(f"SIS Problem Instance:")
    print(f"n = {n}, m = {m}, q = {q}, beta = {beta}")
    print(f"Matrix A ({n} x {m}):")
    print(A)
    print(f"Target vector: {target}")
    print(f"Goal: Find z ∈ [-{beta}, {beta}]^{m} such that A*z ≡ {target} (mod {q})")
    
    return A, target

# Example parameters
n = 4
m = 6
q = 101  # small prime
beta = 5

# Generate instance
A, target = generate_sis_instance(n, m, q, beta)

SIS Problem Instance:
n = 4, m = 6, q = 101, beta = 5
Matrix A (4 x 6):
[78  2  9 45 82 84]
[16  2 85  9 85 85]
[57 66 19 70 96 31]
[81 51  5 43 55 98]
Target vector: (0, 0, 0, 0)
Goal: Find z ∈ [-5, 5]^6 such that A*z ≡ (0, 0, 0, 0) (mod 101)

References¶

Ajtai, M., Kumar, R., & Sivakumar, D. (2001). A sieve algorithm for the shortest lattice vector problem. Symposium on the Theory of Computing. https://api.semanticscholar.org/CorpusID:14982298
Lenstra, A. K., Lenstra, H. W., & Lovász, L. M. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261, 515–534. https://api.semanticscholar.org/CorpusID:5701340

Math & Assumptions

LLL Algorithm

Cryptography

Ajtai’s Hash Functions and Commitment Schemes