10
$\begingroup$

Why q-ary lattices are used to most cryptosystems rather than lattices. In most of the papers q-ary lattices are used. Is there any advantage? and

Given $$B=(v_1,v_2,v_3,.....v_n)$$ is the basis, lattice generated by B $$ L(B)=\{a_1v_1 + ........ + a_nv_n\ |\ a_1........,a_n ∈ Z\}$$ Fix q and given a matrix $$A ∈ Z_{q}^{n×m}$$ m-dimensional lattice $Λ(A^T)$ is defined as $$Λ(A^T)=\{y ∈ Z^m | y ≡ A^Ts\ (\text{mod } q) \text{ for some } s ∈ Z^n_q\}$$ How can we say that the above set of points forms the lattice and does it contains exactly $q^n$ points?

$\endgroup$

1 Answer 1

12
$\begingroup$

The main advantage of using $q$-ary lattices is that it allows a cryptosystem designer to rely on the standard Short Integer Solution (SIS) and Learning With Errors (LWE) problems, which are known to be at least as hard as worst-case lattice problems. So the SIS/LWE problems abstract away the connection to lattices, and give the designer a strong hardness guarantee "for free." By contrast, if one were to work "directly" with lattices, one would have to explicitly describe a distribution over lattices and their secret "trapdoors," show (or assume) that lattices generated in this way are hard, etc. etc.

Another reason is that the SIS/LWE problems are very easy to work with, and admit a lot of versatility; it's less obvious how to obtain comparable properties when working with general lattices. For example, one can perform arithmetic on parity-check/generator matrices $\mathbf{A}$, which can yield many interesting properties and applications (e.g., trapdoor manipulations, homomorphisms, etc.). Most of these arithmetic operations do have interpretations in terms of general lattices, but they've been much easier to discover and exploit when working with $q$-ary lattices and their parity-check/generator matrices.

Regarding your question about $\Lambda(\mathbf{A}^t)$, this is a lattice and hence it has an infinite number of points. However, modulo $q$, it has at most $q^n$ distinct points, at most one per value of $\mathbf{s}$. It has exactly $q^n$ points if and only if no two distinct values of $\mathbf{s}$ yield the same value of $\mathbf{A}^t \mathbf{s} \pmod{q}$, which holds if and only if the right-nullspace (mod $q$) of $\mathbf{A}^t$ is simply $\{ \mathbf{0} \}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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