1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{enumerate}
  7\usepackage{hyperref}
  8\usepackage{amssymb}
  9\usepackage{tikz} % diagram
 10\usepackage{changepage} % for adjustwidth
 11
 12\begin{filecontents}[overwrite]{lattices.bib}
 13@misc{chris-peikert,
 14  author = {Chris Peikert},
 15  title = {{A decade of lattice cryptography}},
 16  year = {2016}
 17}
 18@misc{matan,
 19  author = {Matan Prasma},
 20  title = {{Lattices, an elementary and rigorous account}},
 21  year = {2024}
 22}
 23@misc{slides-micciano,
 24  author = {Daniele Micciancio},
 25  title = {{Introduction to Lattices}},
 26  year = {2024}
 27}
 28@misc{micciano-regev,
 29  author = {Daniele Micciancio and Oded Regev},
 30  title = {{Lattice-based Cryptography}},
 31  year = {2008}
 32}
 33@misc{menezes,
 34  author = {Alfred Menezes},
 35  title = {{A Gentle Introduction to Lattice-Based Cryptography}},
 36  year = {2026}
 37}
 38@misc{cynthia-dwork,
 39  author = {Cynthia Dwork},
 40  title = {{Lattices and Their Application to Cryptography}},
 41  year = {1998}
 42}
 43\end{filecontents}
 44\nocite{*}
 45
 46
 47\theoremstyle{definition}
 48
 49\newtheorem{thm}{Theorem}[section]
 50\newtheorem{lemma}[thm]{Lemma}
 51\newtheorem{prop}[thm]{Proposition}
 52\newtheorem{cor}[thm]{Corollary}
 53\newtheorem{defn}[thm]{Definition}
 54\newtheorem{remark}[thm]{Remark}
 55\newtheorem{ex}[thm]{Example}
 56
 57\newcommand{\Rr}{\mathbb{R}}
 58\newcommand{\Zz}{\mathbb{Z}}
 59\newcommand{\Ll}{\mathcal{L}}
 60
 61\title{Notes on Lattices}
 62\author{arnaucube}
 63\date{2026}
 64
 65\begin{document}
 66
 67\maketitle
 68
 69\begin{abstract}
 70    Notes taken while studying lattice-based cryptography.
 71
 72    Usually while reading books and papers I take handwritten notes in paper notebooks, this document contains some of them re-written to $LaTeX$.
 73\end{abstract}
 74
 75\tableofcontents
 76
 77\section{Lattices}
 78\subsection{Hard problems}
 79
 80\begin{defn}[SVP (Shortest Vector Problem)]
 81find a shortest non-zero vector $x \in \Ll$, ie. that minimizes the Euclidean norm $||x||$, that is $\lambda_1(\Ll)=||x||$.
 82\end{defn}
 83
 84\begin{defn}[CVP (Closest Vector Problem)]
 85given a vector $y \in \Rr^n$ with $y \not\in \Ll$, find a nonzero vector $x \in \Ll$ that is closest to $y$, ie. that minimizes the Euclidean norm $||y-x||$.
 86\end{defn}
 87
 88\begin{defn}[NTRU key recovery problem]
 89Given $h(x)$, find ternary polynomials $f, g \in \mathcal{T}$ satisfying
 90$$f(x) \cdot h(x) = g(x) \pmod q \in R_q$$
 91Where $R_q = \Zz_q[X]/(X^n-1)$.
 92\end{defn}
 93
 94\begin{defn}[SIS (Short Integer Solution)]
 95Given $q \in \Zz$ and matrix $A \in \Zz_q^{m \times n}$, find a non-zero short $z \in \Zz^n$ s.th.
 96$$A \cdot z = 0 \pmod q$$
 97
 98\small{"short": $z \in \{B, B\}^n$ for some bound $B$, often $z \in \{-1, 0, 1 \}^n$.}
 99\end{defn}
100
101The set of all solutions to the SIS problem forms the (q-ary) lattice
102$$\Lambda^{\perp}_q(A) = \{ z \in \Zz^n ~|~ A z = 0 \in \Zz_q^m \} \supseteq \Zz_q^n$$
103where the SIS problem becomes the SVP for $\Lambda_q^{\perp}(A)$
104
105\begin{itemize}
106\item LLL algorithm is used to solve SVP and CVP.
107
108  \item Both SVP and CVP become computationally difficult (NP hard) as the lattice dimension $n$ grows.
109\end{itemize}
110
111
112
113\begin{defn}[Ring SIS (Ring Short Integer Solution)]
114given a uniformly random matrix $A \in^R R_q^n$, with elements $a_i \in R_q$, find a non-zero integer vector $z \in R^n$ of norm $||z|| \leq \beta$ such that
115
116$$A z = \sum_i a_i \cdot z_i = 0 \in R_q$$
117\end{defn}
118
119\begin{defn}[MSIS (Module Short Integer Solution)]
120given a uniformly random matrix $A \in^R R_q^{m \times n}$, with columns $a_i \in R_q^m$, find a non-zero integer vector $z \in R^n$ of norm $||z|| \leq \beta$ such that
121
122$$A z = 0 \in R_q^m$$
123$$ie.~ \sum_i a_{ij} \cdot z_j = 0 \in R_q, ~~for~ i=1, \ldots, m$$
124\end{defn}
125
126Notice that Module-SIS is a Ring-SIS with $rank=1$ ($m=1$).
127
128The next form is useful to compress the size of a SIS matrix by $n$ columns: 
129\begin{defn}[Hermite Normal Form (HNF)]
130  Assume the leftmost $n$ columns $A_1 \in \Zz_q^{n \times n}$ of $A=[A_1|A_2] \in \Zz_q^{n \times m}$ form an invertible matrix.
131
132  Then replace $A$ by
133  $$A_1^{-1} \cdot A = [ I_n ~|~ \overline{A} = A_1^{-1} \cdot A_2]$$
134  and threat the $I_n$ submatrix as implicit.
135
136  Then, $A$ and $[I_n ~|~ \overline{A}]$ have exactly the same set of short SIS solutions.
137\end{defn}
138
139\begin{defn}[LWE distribution]
140  $s \in \Zz_q^n$ (secret), $a \in \Zz_q^n$, $e \in \Xi$, output
141  $$(a, b= \langle s, a \rangle + e \pmod q) \in (\Zz_q^n \times \Zz_q)$$
142\end{defn}
143
144\begin{defn}[Search-LWE]
145  given $m$ independent samples $(a_i, b_i) \in \Zz_q^n \times \Zz_q$, for a uniform $s \in \Zz_q^n$ (fixed for all samples), find $s$.
146\end{defn}
147\begin{defn}[Decision-LWE]
148  given $m$ independent samples $(a_i, b_i) \in \Zz_q^n \times \Zz_q$, distinguish which one is not random and it is an actual instance.
149\end{defn}
150
151
152
153\subsection{Dual lattices}
154
155From previous section, we have LWE-Lattice and SIS-Lattice:
156
157
158Search-LWE can be seen as a Bounded-Distance Decoding (BDD) problem on q-ary m-dimensional integer lattices:\\
159for LWE samples, vector $b$ is relatively close to exactly one vector in the LWE lattice:
160\begin{defn}[LWE Lattice] \label{lwe-lattice}
161  A LWE-Lattice $\Ll$ is defined
162  \begin{align*}
163    \Ll &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
164	&= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
165  \end{align*}
166\end{defn}
167
168SIS can be seen as a SVP on q-ary m-dimensional lattices:
169\begin{defn}[SIS-Lattice] \label{sis-lattice}
170  A SIS-Lattice $\Ll$ is defined
171$$\Ll^\perp = \{ z \in \Zz^m ~|~ Az=0 \in \Zz_q^n \} \supseteq q \Zz^m$$
172\end{defn}
173
174
175\begin{defn}[Dual of a lattice] \label{dual-lattice}
176    For a lattice $\Ll$, its dual is
177    $$\Ll^* = \{ y \in \Rr^m ~|~ \langle y, x \rangle \in \Zz ~\forall~ x \in \Ll \}$$
178\end{defn}
179The dual lattice consists of all vectors that measure lattice points with integer-valued linear measurements.
180
181\begin{remark}
182  For a lattice basis $B=(b_1, \ldots, b_n)$, the dual basis $B^*=(b_1^*, \ldots, b_n^*)$ is the unique basis satisfying
183  $$
184    \langle b_i^*, b_j \rangle
185    = \delta_{ij} =
186      \begin{cases}
187	1, & \text{if } i = j, \\
188	0, & \text{if } i \neq j
189      \end{cases}
190  $$
191  where $\delta_{ij}$ is the Kronecker delta.
192\end{remark}
193
194\begin{lemma}
195    $$\Ll = q \Ll^{\perp *} ~\text{ie.}~ \frac{1}{q} \Ll = \Ll^{\perp *}$$
196\end{lemma}
197\begin{proof}
198    \begin{enumerate}[i.]
199    \item
200      Take $y \in \frac{1}{q} \Ll$, then by \ref{lwe-lattice}, $\exists~ s \in \Zz^n, z \in \Zz^m$ such that
201    $$y = \frac{1}{q} (A^Ts + qz) = \frac{1}{q} A^T s +z$$
202
203    Let $x \in \Ll^\perp$. By definition (\ref{sis-lattice}) $Ax=0 \pmod q$, therefore $\exists~ k \in \Zz^n$ such that $Ax = qk$.
204
205    Compute
206    \begin{align*}
207	\langle y, x \rangle &= \langle \frac{1}{q} A^T s + z, x \rangle\\
208			     &= \frac{1}{q} \langle A^T s, x \rangle + \langle z, x \rangle\\
209			     &= \frac{1}{q} \langle s, Ax \rangle + \langle z, x \rangle\\
210			     &= \frac{1}{q} \langle s, qk \rangle + \langle z, x \rangle\\
211			     &= \langle s, k \rangle + \langle z, x \rangle
212    \end{align*}
213    and $\langle s, k \rangle + \langle z, x \rangle \in \Zz$, since each of $s, k, z, x \in \Zz$ separately.
214
215    Thus $\langle y, x \rangle \in \Zz$, hence by \ref{dual-lattice}, $y \in \Ll^{\perp *}$.
216
217    We started from $y \in \frac{1}{q}\Ll$, so, now we have
218    $$y \in \Ll^{\perp *} ~\forall~ y \in \frac{1}{q} \Ll$$
219    therefore
220    $$\Ll^{\perp *} \supseteq \frac{1}{q} \Ll$$
221    
222    \item
223    Now we prove the reverse inclusion. Take $y \in \Ll^{\perp *}$.
224
225    Observe that $q \Zz^m \subseteq \Ll^\perp$, because
226    $$\forall z \in \Zz^m,~ A(qz) = qAz = q 0 = 0 \pmod q$$
227
228    Since $y \in \Ll^{\perp *}$, we must have $\langle y, qz \rangle \in \Zz ~\forall~ z \in \Zz^m$.
229
230    Let $e_i \in \Zz^m$ be the $i-th$ standard basis vector, ie. $e_i=(0, \ldots, 0, 1, 0, \ldots, 0)$ (where one is at the i-th position).
231
232    We know that $\langle y, qz \rangle \in \Zz ~\forall z \in \Zz^m$ (including $z=e_i$), thus, for
233    $q e_i = (0, \ldots, 0, q, 0, \ldots, 0)$,
234    $$\langle y, q e_i \rangle = q \langle y, e_i \rangle = q \cdot y_i$$
235    since $\langle y, e_i \rangle = y_i$ (extracts the i-th position from $y$).
236
237    So, since $\langle y, qz \rangle \in \Zz ~\forall z \in \Zz^m$, and $\langle y, q e_i \rangle = q y_i$, then $q y_i \in \Zz$
238
239    This argument works $\forall i \in [m]$, that is, $q y_1, \ldots, q y_m \in \Zz$. Therefore
240    $$qy \in \Zz^m ~\forall~ y \in \Ll^{\perp *}$$
241
242    For $\overline{x} \in ker(A) \subseteq \Zz_q^m$, since $A \overline{x}=0$, then $Ax =0 \pmod q$, thus $x \in \Ll^\perp$ (by its definition \ref{sis-lattice}).
243
244    Since $y \in \Ll^{\perp *}$, by the definition of $\Ll^{\perp *}$ (\ref{dual-lattice}), $\langle y, x \rangle \in \Zz$. Multiply it by $q$,
245    $$ q \langle y, x \rangle = \langle qy, x \rangle \in q \Zz$$
246    hence $\langle qy, x \rangle = 0 \pmod q$, thus $qy \pmod q \in ker(A)^\perp$.
247
248    \begin{adjustwidth}{4em}{0pt}
249      We'll now prove the following identity, valid for every integer $q\geq 2$, which we will use later:
250      $$(\ker A)^\perp=im(A^T)$$
251      where $A:\Zz_q^m \to \Zz_q^n$.
252
253      Let $y \in im(A^T)$. Then $\exists~ s \in \Zz_q^n$ such that $y=A^Ts$.
254
255      Then, $\forall~ x \in \ker(A)$, by definition of the kernel, $Ax=0$. Want to prove that $y$ is orthogonal to every $x \in \ker(A)$:
256      $$\langle y,x\rangle = \langle A^Ts,x\rangle = \langle s,Ax\rangle = 0$$
257
258      thus, $\langle y,x\rangle =0 ~\forall~ x \in \ker(A)$, hence $y$ is orthogonal to every $x$, that is, $y \in (\ker(A))^\perp$.
259
260      Therefore,
261      $$im(A^T) \subseteq (\ker(A))^\perp$$
262
263      For the reverse inclusion, it suffices to show that both sets have the same number of elements:
264
265      By the First Isomorphism Theorem,
266      $$|im(A)| = \frac{ |\Zz_q^m|}{|\ker(A)|} = \frac{q^m}{|\ker(A)|}$$
267
268      Notice that for every subgroup $K \subseteq \Zz_q^m$, the dot product on $\Zz_q^m$ is nondegenerate, therefore
269      $$|K^\perp| = \frac{q^m}{|K|}$$
270
271      so, applied to $\ker(A)$,
272      $$|\ker(A)^\perp| = \frac{q^m}{|\ker(A)|}= |im(A)|$$
273
274      which, by transposition properties, $|im(A)|=|im(A^T)|$, thus
275      $$|\ker(A)^\perp| = |im(A^T)|$$
276
277      hence,
278      $$(\ker(A)^\perp) = im(A^T)$$
279    \end{adjustwidth}
280
281    Continuing from $qy \pmod q \in (ker(A))^\perp$, we've just seen that $(ker(A))^\perp = im(A^T)$, thus
282    $$\exists s \in \Zz^n ~\text{s.th.}~ qy=A^Ts \pmod q$$
283
284    Therefore, for some
285    $$z \in \Zz^m, ~ qy=A^Ts +qz$$
286    which means that $qy \in \Ll$, by definition of $\Ll$ (\ref{lwe-lattice}). Divide that by $q$, obtaining
287    $$y \in \frac{1}{q} \Ll$$
288
289    Thus, $\forall y \in \Ll^{\perp *}$, we have $y \in \frac{1}{q} \Ll$.
290
291    Hence $\Ll^{\perp *} \subseteq \frac{1}{q} \Ll$.
292    \end{enumerate}
293
294    \vspace{0.6cm}
295    Putting together $(i).~ \Ll^{\perp *} \supseteq \frac{1}{q} \Ll$, and $(ii).~ \Ll^{\perp *} \subseteq \frac{1}{q} \Ll$, we have
296    $$\Ll^{\perp *} = \frac{1}{q} \Ll$$
297\end{proof}
298
299
300\bibliographystyle{unsrt}
301\bibliography{lattices.bib}
302
303\end{document}