math/lattices.tex
lattices.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4% \usepackage{yfonts} % WIP
5\usepackage{amsthm}
6\usepackage{amsmath}
7\usepackage{enumerate}
8\usepackage{hyperref}
9\usepackage{amssymb}
10\usepackage{tikz} % diagram
11\usepackage{changepage} % for adjustwidth
12
13\begin{filecontents}[overwrite]{lattices.bib}
14@misc{chris-peikert,
15 author = {Chris Peikert},
16 title = {{A decade of lattice cryptography}},
17 year = {2016}
18}
19@misc{slides-micciano,
20 author = {Daniele Micciancio},
21 title = {{Introduction to Lattices}},
22 year = {2024}
23}
24@misc{micciano-regev,
25 author = {Daniele Micciancio and Oded Regev},
26 title = {{Lattice-based Cryptography}},
27 year = {2008}
28}
29@misc{matan,
30 author = {Matan Prasma},
31 title = {{Lattices, an elementary and rigurous account}},
32 year = {2024}
33}
34@misc{menezes,
35 author = {Alfred Menezes},
36 title = {{A Gentle Introduction to Lattice-Based Cryptography}},
37 year = {2026}
38}
39@misc{cynthia-dwork,
40 author = {Cynthia Dwork},
41 title = {{Lattices and Their Application to Cryptography}},
42 year = {1998}
43}
44\end{filecontents}
45\nocite{*}
46
47
48\theoremstyle{definition}
49
50\newtheorem{thm}{Theorem}[section]
51\newtheorem{lemma}[thm]{Lemma}
52\newtheorem{prop}[thm]{Proposition}
53\newtheorem{cor}[thm]{Corollary}
54\newtheorem{defn}[thm]{Definition}
55\newtheorem{remark}[thm]{Remark}
56\newtheorem{ex}[thm]{Example}
57
58\newcommand{\Rr}{\mathbb{R}}
59\newcommand{\Zz}{\mathbb{Z}}
60\newcommand{\Ll}{\mathcal{L}}
61
62\title{Notes on Lattices}
63\author{arnaucube}
64\date{2026}
65
66\begin{document}
67
68\maketitle
69
70\begin{abstract}
71 Notes taken while studying lattice-based cryptography.
72
73 Usually while reading books and papers I take handwritten notes in paper notebooks, this document contains some of them re-written to $LaTeX$.
74\end{abstract}
75
76\tableofcontents
77
78\section{Lattices}
79\subsection{Hard problems}
80
81\begin{defn}[SVP (Shortest Vector Problem)]
82find a shortest non-zero vector $x \in \Ll$, ie. that minimizes the Euclidean norm $||x||$, that is $\lambda_1(\Ll)=||x||$.
83\end{defn}
84
85\begin{defn}[CVP (Closest Vector Problem)]
86given 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||$.
87\end{defn}
88
89\begin{defn}[NTRU key recovery problem]
90Given $h(x)$, find ternary polynomials $f, g \in \mathcal{T}$ satisfying
91$$f(x) \cdot h(x) = g(x) \pmod q \in R_q$$
92Where $R_q = \Zz_q[X]/(X^n-1)$.
93\end{defn}
94
95\begin{defn}[SIS (Short Integer Solution)]
96Given $q \in \Zz$ and matrix $A \in \Zz_q^{m \times n}$, find a non-zero short $z \in \Zz^n$ s.th.
97$$A \cdot z = 0 \pmod q$$
98
99\small{"short": $z \in \{B, B\}^n$ for some bound $B$, often $z \in \{-1, 0, 1 \}^n$.}
100\end{defn}
101
102The set of all solutions to the SIS problem forms the (q-ary) lattice
103$$\Lambda^{\perp}_q(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
104where the SIS problem becomes the SVP for $\Lambda_q^{\perp}(A)$
105
106\begin{itemize}
107\item LLL algorithm is used to solve SVP and CVP.
108
109 \item Both SVP and CVP become computationally difficult (NP hard*) as the lattice dimension $n$ grows.
110\end{itemize}
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
128\subsection{Dual lattices}
129
130\begin{defn}[Dual of a lattice] \label{dual}
131 For a lattice $\Ll$, its dual is
132 $$\Ll^* = \{ y \in \Rr^m ~|~ \langle y, x \rangle \in \Zz ~\forall~ x \in \Ll \}$$
133\end{defn}
134
135\begin{lemma}
136 $$\Ll = q \Ll^{\perp *} ~\text{ie.}~ \frac{1}{q} \Ll = \Ll^{\perp *}$$
137\end{lemma}
138\begin{proof}
139 \begin{enumerate}[i.]
140 \item
141 Take $y \in \frac{1}{q} \Ll$, then $\exists s \in \Zz^n, z \in \Zz^m$ such that
142 $$y = \frac{1}{q} (A^Ts + qz) = \frac{1}{q} A^T s +z$$
143
144 Let $x \in \Ll^\perp$. By definition $Ax=0 \pmod q$, therefore $\exists~ k \in \Zz^n$ such that $Ax = qk$.
145
146 Compute
147 \begin{align*}
148 \langle y, x \rangle &= \langle \frac{1}{q} A^T s + z, x \rangle\\
149 &= \frac{1}{q} \langle A^T s, x \rangle + \langle z, x \rangle\\
150 &= \frac{1}{q} \langle s, Ax \rangle + \langle z, x \rangle\\
151 &= \frac{1}{q} \langle s, qk \rangle + \langle z, x \rangle\\
152 &= \langle s, k \rangle + \langle z, x \rangle
153 \end{align*}
154 and $\langle s, k \rangle + \langle z, x \rangle \in \Zz$, since each of $s, k, z, x \in \Zz$.
155
156 Thus $\langle y, x \rangle \in \Zz$, hence by \ref{dual}, $y \in \Ll^{\perp *}$.
157
158 We started from $y \in \frac{1}{q}\Ll$, so, now we have
159 $$y \in \Ll^{\perp *} ~\forall~ y \in \frac{1}{q} \Ll$$
160 therefore
161 $$\Ll^{\perp *} \supseteq \frac{1}{q} \Ll$$
162
163 \item
164 Now we prove the reverse inclusion. Take $y \in \Ll^{\perp *}$.
165
166 Observe that $q \Zz \subseteq \Ll^\perp$, because
167 $$\forall z \in \Zz^m,~ A(qz) = qAz = q 0 = 0 \pmod q$$
168
169 Since $y \in \Ll^{\perp *}$, we must have $\langle y, qz \rangle \in \Zz ~\forall~ z \in \Zz^m$.
170
171 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).
172
173 We know that $\langle y, qz \rangle \in \Zz ~\forall z \in \Zz^m$ (including $z=e_i$), thus\\
174 $q e_i = (0, \ldots, 0, q, 0, \ldots, 0)$. Therefore,
175 $$\langle y, q e_i \rangle = q \langle y, e_i \rangle = q \cdot y_i$$
176 since $\langle y, e_i \rangle = y_i$ (extracts the i-th position from $y$).
177
178 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$
179
180 This argument works $\forall i \in [m]$, that is, $q y_1, \ldots, q y_m \in \Zz$. Therefore
181 $$qy \in \Zz^m ~\forall~ y \in \Ll^{\perp *}$$
182
183 $qy \pmod q$ is orthogonal to $ker(A)$. %TODO
184
185 Let $\hat{x} \in ker(A) \subseteq \Zz_q^m$.
186 Since $A \hat{x}=0$, then $Ax =0 \pmod q$, thus $x \in \Ll^\perp$.
187
188 Since $y \in \Ll^{\perp *}$, $\langle y, x \rangle \in \Zz$. Multiply it by $q$,
189 $$\langle qy, x \rangle = q \langle y, x \rangle \in q \Zz$$
190 hence $\langle qy, x \rangle = 0 \pmod q$, thus $qy \pmod q \in ker(A)^\perp$.
191
192 \begin{adjustwidth}{2em}{0pt}
193 Observe: $ker(A)^\perp = im(A^T)$, proof:
194 let $A: \Zz_q^m \longrightarrow \Zz_q^n$, define
195 $$ker(A) = \{ x \in \Zz_q^m ~|~ Ax=0 \} = \Ll^\perp(A)$$
196
197 Define the orthogonal complement
198 $$(ker(A))^\perp = \{ y \in \Zz_q^m ~|~ \langle y, x \rangle =0 \pmod q ~\forall~ x \in ker(A) \}$$
199 $$im(A^T) = \{ A^T s ~|~ s \in \Zz_q^n \}$$
200
201 Then, $(ker(A))^\perp = im(A^T)$.
202 \end{adjustwidth}
203
204 Continuing from $qy \pmod q \in (ker(A))^\perp$, we've just seen that $(ker(A))^\perp = im(A^T)$, thus
205 $$\exists s \in \Zz^n ~\text{s.th.}~ qy=A^Ts \pmod q$$
206
207 Therefore, for some
208 $$z \in \Zz^m, ~ qy=A^Ts +qz$$
209 which means that $qy \in \Ll$ (by definition of $\Ll$). Divide that by $q$, obtaining
210 $$y \in \frac{1}{q} \Ll$$
211
212 Thus, $\forall y \in \Ll^{\perp *}$, we have $y \in \frac{1}{q} \Ll$.
213
214 Hence $\Ll^{\perp *} \subseteq \frac{1}{q} \Ll$.
215 \end{enumerate}
216
217 \vspace{0.6cm}
218 Putting together $(i).~ \Ll^{\perp *} \supseteq \frac{1}{q} \Ll$, and $(ii).~ \Ll^{\perp *} \subseteq \frac{1}{q} \Ll$, we have
219 $$\Ll^{\perp *} = \frac{1}{q} \Ll$$
220\end{proof}
221
222
223\bibliographystyle{unsrt}
224\bibliography{lattices.bib}
225
226\end{document}