math/slides/slides_lattices-intro.tex
slides/slides_lattices-intro.texRaw
1\documentclass{beamer}
2\usefonttheme[onlymath]{serif}
3
4\mode<presentation>
5{
6 \usetheme{Frankfurt}
7 \usecolortheme{dove} %% grey scale
8 \useinnertheme{circles}
9 % \setbeamercovered{transparent}
10}
11
12\hypersetup{
13 colorlinks,
14 citecolor=black,
15 filecolor=black,
16 linkcolor=black,
17 urlcolor=blue
18}
19\usepackage{graphicx}
20\usepackage{color}
21\usepackage{changepage} % for adjustwidth
22
23\graphicspath{ {./imgs-lattices} }
24
25\setbeamertemplate{itemize}{$\circ$}
26\setbeamertemplate{itemize items}{$\circ$}
27
28\beamertemplatenavigationsymbolsempty %% no navigation bar
29
30\setbeamertemplate{footline}{\hspace*{.1cm}\scriptsize{
31\hspace*{50pt} \hfill\insertframenumber/\inserttotalframenumber\hspace*{.1cm}\vspace*{.1cm}}}
32
33\setbeamertemplate{caption}[numbered]
34\setbeamerfont{caption}{size=\tiny}
35
36\newtheoremstyle{customstyle}
37 {18pt} % Space above
38 {0pt} % Space below
39 {} % Body font
40 {} % Indent
41 {\bfseries} % Head font
42 {.} % Punctuation after head
43 { } % Space after head
44 {} % Head spec
45
46\theoremstyle{customstyle}
47
48\newtheorem{thm}{Theorem}[section]
49\let\lemma\relax
50\let\endlemma\relax
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
57
58\newcommand{\Rr}{\mathbb{R}}
59\newcommand{\Zz}{\mathbb{Z}}
60\newcommand{\Ll}{\mathcal{L}}
61
62\title{Introduction to lattice based cryptography}
63\author{arnaucube}
64\date{\scriptsize{September 2026, Barcelona}}
65
66\begin{document}
67
68\frame{\titlepage}
69
70
71
72\section[Motivation]{Motivation}
73
74% - Motivation
75% - till now we've been mostly using RSA & E.C. cryptography
76% - they are susceptible to quantum computers based attacks. Shor's algorithm, etc
77% - post-quantum cryptography context: hash-based (starks), lattices, isogenesis
78% - historical timeline of papers (XMMS SPHINCHS (+), Falcon, etc (exclude isogenesis)
79% - hash vs lattices: hash had more engineering effort, it's currently more performant. Lattice have more algebraic structure, interesting properties.
80% - Lattices math
81% - lattice hard problems are based on the hardness of finding short vectors. SVP, CVP, SIS, etc
82
83% TODO: why lattices are post quantum
84% Lattices are already used in browsers: explain how, dual signautres, etc
85
86\begin{frame}{Motivation}
87 \begin{itemize}
88 \item till now most cryptography relied on hardness of finding prime factors or finding the discrete logarithm, ie. RSA, Elliptic Curves, etc
89 \item Shor's algorithm suggests that factorization can be done in polynomial time (on quantum computers).\\
90 \small{
91 $\rightarrow$ given an odd composite $n \in \Zz$, find $d \in \Zz$, such that $1< d <n$ and $d|n$.
92 }
93 \end{itemize}
94\end{frame}
95
96\begin{frame}{Post Quantum Cryptography - Status of the ecosystem}
97 \begin{itemize}
98 \item isogenesis based
99 \item hash based
100 \item codes based
101 \item lattice based
102 \item multivariate based
103 \end{itemize}
104 TODO
105\end{frame}
106
107\begin{frame}{Motivation (in Ethereum's ecosystem)}
108 \begin{itemize}
109 \item Ethereum, is going with hash-based signatures for the validators.
110 \begin{itemize}
111 \item aggregation through SNARK proofs (eg. binius, flock, etc)
112 \item each slot a different XMSS leaf
113 \item the most conservative choice in terms of security
114 \end{itemize}
115 \item hash-based simpler to implement, less potential errors. Whereas lattice-based have more subtelties
116 \item hash-based schemes don't have much algebraic structure
117 \begin{itemize}
118 \item good for less attacks, not so fun to build stuff with
119 \item eg. elliptic curves have algebraic structure, allows for signature aggregation, thresholds, etc
120 \end{itemize}
121 \item lattice-based schemes have smaller proofs, signatures and public keys
122 \end{itemize}
123\end{frame}
124
125\section[Preliminaries]{Preliminaries}
126\begin{frame}{Preliminaries}
127 Recap of concepts:
128 \begin{itemize}
129 \item Rings
130 \begin{itemize}
131 \item ideals
132 \end{itemize}
133 \item Vector Spaces
134 \item Modules
135 \end{itemize}
136\end{frame}
137
138\begin{frame}{Rings}
139 \vspace*{-0.5cm}
140 \small{
141 \begin{defn}[Ring]
142 A set $A$ with operations called \emph{addition} and \emph{multiplication} which satisfy the following axioms:
143 \begin{enumerate}[i.]
144 \item $A$ with addition alone is an abelian group.
145 \item Multiplication is associative.
146 \item Multiplication is distributive over addition. That is, $\forall a,b,c \in A$,
147 $$a(b+c) = ab + ac$$
148 $$(b+c)a = ba + ca$$
149 \end{enumerate}
150 \end{defn}
151
152 \pause
153 Remark: a field is a ring with inverse.
154
155 \pause
156 \begin{defn}[Ideal]
157 $I \subset R$ ($R$ ring) such that $0 \in I$ and $\forall x \in I,~ r \in R,~ xr, rx \in I$.\\
158 \hspace*{2em} ie. $I$ absorbs products in $R$.
159 \end{defn}
160
161 \pause
162 Eg: Ring $\Zz=\{\ldots, -2, -1, 0, 1, 2, 3, \ldots \}$, Ideal $n \Zz= \{n k ~|~ k \in \Zz \}$ for fixed $n \in \Zz$.
163 }
164\end{frame}
165
166
167\begin{frame}{Vector spaces}
168 % vector space
169 % norm of a vector
170 % linear independent
171 % span
172 % basis
173 % rank: number of basis vectors / maximum number of linearly independent columns / maximum number of linearly independent rows
174 % some diagram
175
176
177 \begin{defn}[Vector space]
178 A \emph{vector space} over a field $F$ is a set $V$, with two operations $+, \cdot$, called \emph{vector addition} and \emph{scalar multiplication}, such that
179
180 \begin{itemize}
181 \item $V$ with vector addition is an abelian group
182 \item $\forall k \in F$ and $\overrightarrow{a} \in V$, the scalar product $k \overrightarrow{a}$ is an element of $V$, subject to the following conditions:
183 $\forall k, l \in F,~\overrightarrow{a},\overrightarrow{b} \in V$
184 \begin{enumerate}[i.]
185 \item $k(\overrightarrow{a} + \overrightarrow{b}) = k\overrightarrow{a} + k\overrightarrow{b}$
186 \item $(k + l)\overrightarrow{a} = k\overrightarrow{a} + k\overrightarrow{b}$
187 \item $k(l\overrightarrow{a}) = (kl)\overrightarrow{a}$
188 \item $1 \overrightarrow{a} = \overrightarrow{a}$
189 \end{enumerate}
190 \end{itemize}
191 \end{defn}
192
193 \begin{itemize}
194 \item basis: set of vectors that \emph{span} the vector space
195 % TODO WIP
196 \end{itemize}
197\end{frame}
198
199
200\begin{frame}{Modules}
201 \small{
202
203 \begin{defn}[Module]
204 Let $A$ be a ring. An $A$-module is an Abelian group $M$ with a multiplication
205 map
206 \begin{align*}
207 A \times M &\longrightarrow M\\
208 (f, m) &\longmapsto fm
209 \end{align*}
210 satisfying $\forall~ f,g \in A,~~ m, n \in M$.
211 \begin{enumerate}[i.]
212 \item $f(m \pm n)=fm \pm fn$
213 \item $(f \pm g) m = fm \pm gm$
214 \item $(fg) m = f(gm)$
215 \item $1_A m = m$
216 \end{enumerate}
217 \end{defn}
218
219 \pause
220
221 Remark: Vector spaces are defined over fields, a Module is the generalization of a vector space where the scalars come from a ring instead of a field.
222 }
223\end{frame}
224
225\section[Lattices]{Lattices}
226
227\begin{frame}{Lattices}
228 \begin{defn}[Lattice]
229 A lattice $\Ll$ in $\Rr^n$ is the set of all integer linear combinations of $m$ linearly independent vectors $b_1, \ldots, b_m \in \Rr^n$, with $m \leq n$.
230
231 \pause
232 $B = b_1, \ldots, b_m \in \Rr^n$ is the \emph{basis} of $\Ll$. We denote it $\Ll=\Ll(B)$.
233
234 $$\Ll(B) := B \cdot \Rr^n = \{ \sum_{i=1}^n c_i b_i ~|~ c_i \in \Rr^n \}$$
235 \end{defn}
236
237 \pause
238 Note: basis of a lattice are not unique.
239
240 \pause
241 Dimension of $\Ll$ is $n$, rank of $\Ll$ is $m$. Full-rank lattice: $m=n$.
242
243 \pause
244 In most cryptographic applications, $b_1, \ldots, b_n \in \Zz^n$, ie. $\Ll$ is an integer lattice.
245
246\end{frame}
247
248\begin{frame}{}
249 \includegraphics[width=9.5cm]{./2d-lattice}
250\end{frame}
251
252\begin{frame}{Lattice properties}
253 a $n$-dimensional lattice $\Ll$ is
254 \begin{enumerate}[i.]
255 \item \emph{additive subgroup} of $\Rr^n$: $\Ll$ is the nonempty subset of $\Rr^n$ closed under vector addition (and substraction),\\
256 $$\text{ie.}~ \forall x,y \in \Ll,~ -x, x+y \in \Ll$$
257 \item \emph{discrete}: every $x \in \Ll$ has a neighborhood in $\Rr^n$ in which $x$ is the only lattice point.
258 \end{enumerate}
259
260 \pause
261
262 \small{
263 \begin{defn}[\emph{minimum} of a lattice $\Ll$]
264 $$\lambda_1(\Ll) = min \{ ||x|| ~|~ x\in \Ll, x \neq 0 \}$$
265
266 \pause
267
268 \emph{Successive minima} $\lambda_i(\Ll)$: smallest radius $r$ s. th. $\Ll$ the $n$-dimensional ball of radius $r$ contains $i$ linearly independent lattice points.
269 $$\lambda_1(\Ll) \leq \lambda_2(\Ll) \leq \cdots \leq \lambda_n(\Ll)$$
270 \end{defn}
271 }
272\end{frame}
273
274\begin{frame}{Lattice properties}
275 recall, a lattice:
276 $$\Ll(B) := B \cdot \Zz^n = \{ \sum_{i=1}^n z_i b_i ~|~ z_i \in \Zz^n \}$$
277
278 \pause
279
280 \begin{itemize}
281 \item $B = (b_1, \ldots, b_n) \in \Zz^{n \times n}$: basis matrix, finite description of the lattice (not the lattice itself)
282 \item the matrix-vector product $Bz$ maps an integer coordinate vector $z \in \Zz^n$ into a lattice point in $\Zz^n$.
283
284 \pause
285 \item since columns of $B$ are linearly independent (bcs they are a basis), every point of $\Ll(B)$ has a unique integer coordinate vector relative to the basis
286 \begin{itemize}
287 \item the lattice $\Ll(B)$ is the invariant set of points
288 \item the basis $B$ is not unique
289 \end{itemize}
290
291 \pause
292 \item $B \in \Zz^{n \times n}$, $n$ vectors, each with $n$ coordinates $\Longrightarrow$ requires $\mathcal{O}(n^2)$ integers.
293 \begin{itemize}
294 \item only if we could have some better lattice structure to represent the lattice with fewer entries...
295 \end{itemize}
296 \end{itemize}
297\end{frame}
298
299\begin{frame}{q-ary lattice}
300 a full-rank lattice is q-ary if $q \Zz^d \subseteq \Ll \subseteq \Zz^d$
301
302 $\Longrightarrow$ q-ary lattice is an infinite set of integer points, but membership depends only on the residue class modulo $q$
303 $$\text{ie. if}~ x \in \Ll, ~\text{then}~ x + qz \in \Ll ~\forall z \in \Zz^d$$
304
305 \pause
306
307 Let $A \in \Zz^{n \times m}$ define the homomorphism
308 \begin{align*}
309 \psi_A: \Zz^m &\longrightarrow \Zz_q^n\\
310 z &\longmapsto Az \pmod q
311 \end{align*}
312
313 \pause
314
315 % image q-ary lattice:
316 % $$\Ll_q(A) = \{ y \in \Zz^n ~|~ y=Az \mod q ~\text{for some}~ z \in \Zz_q^m \}$$
317 %
318 % lattice generated by the rows of $A$.
319 % \pause
320
321 q-ary lattice:
322 $$\Ll_q^{\perp}(A) = ker(\psi_A) = \{ z \in \Zz^m ~|~ Az = 0 \mod q \}$$
323 contains all vectors that are orthogonal modulo $q$ to the rows of $A$.
324
325 \scriptsize{
326 The q-ary lattice generated by the rows of $A$:
327 $$\Ll_q(A) = \{ y \in \Zz^m ~|~ y=A^Tz \mod q ~\text{for some}~ z \in \Zz_q^n \}$$
328 }
329
330 % TODO why q-ary is better? prev.slide says O(n^2) without q-ary, how with q-ary?
331\end{frame}
332
333\begin{frame}{Polynomial rings}
334 \small{
335 \begin{itemize}
336 \item The NTRU paper (1996) introduced the usage of polynomial rings, which latter was ported over Ajtai work and other lattices, now is the general approach in Ring-SIS, Ring-LWE, Module-LWE, etc.
337
338 \item Polynomial rings: represent an $n$-dimensional vector
339 $(a_0,\ldots,a_{n-1}) \in \Zz_q^n$ as a single ring element (polynomial)
340 $$a(X) = a_0 + a_1 X + \cdots + a_{n-1} X^{n-1} \in \Zz_q[X]/(X^n+1)$$
341 \end{itemize}
342 }
343
344 \pause
345 \small{
346 \begin{itemize}
347 \item[-] Addition:
348 $a(x) + b(x) = \sum_{i=1}^d (a_i + b_i) X^i$
349 \pause
350 \item[-] Multiplication:
351 $$a(X) \cdot b(X)
352 = \left(
353 \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}
354 a_i b_j X^{i+j}
355 \right)
356 \in \Zz_q[X]/(X^n+1)$$
357
358 \hspace*{4em}Since $X^n=-1$ then $X^{n+k} = -X^k$\\
359 $\Longrightarrow~ \mathcal{O}(n^2)$ naively, $\mathcal{O}(n \log n)$ using NTT.
360 \end{itemize}
361 }
362\end{frame}
363
364
365\section[Hard problems]{Hard problems}
366
367\begin{frame}{Incomplete Timeline}
368 \begin{timeline}
369 1978 \quad Knapsack cryptosystems attacked using lattice methods
370
371 1996 \quad NTRU encryption
372
373 2005 \quad Learning With Errors (LWE)
374
375 2008 \quad Practical secure lattice-signature schemes
376
377 2009 \quad Fully Homomorphic Encryption (FHE)
378
379 2016 \quad NewHope (Ring-LWE KEM)
380
381 2017 \quad Kyber (Module-LWE based) & Dilithium (Module-LWE & Module-SIS based)
382
383 2020s \quad standardiszation: ML-KEM (Kyber) and ML-DSA (Dilithium)
384 \end{timeline}
385\end{frame}
386
387
388\begin{frame}{Hard problems in lattices - SVP and CVP}
389 \begin{itemize}
390 \item In elliptic curve cryptography, we rely on the hardness of the Discrete Logarithm problem:\\
391 \begin{adjustwidth}{2em}{0pt}
392 given publicly known $g, p \in \mathbb{G}$, find privately known $x \in \Zz$ such that $p=g^x$.
393 \end{adjustwidth}
394
395 \item In lattice based cryptography, we rely on problems related to finding short vectors in the lattice.
396 \end{itemize}
397
398 \pause
399 \begin{defn}[SVP (Shortest Vector Problem)]
400 find a shortest non-zero vector $x \in \Ll$, ie. that minimizes the Euclidean norm $||x||$, that is $\lambda_1(\Ll)=||x||$.
401 \end{defn}
402
403 \pause
404 \begin{defn}[CVP (Closest Vector Problem)]
405 given 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||$.
406 \end{defn}
407\end{frame}
408
409\begin{frame}
410 \includegraphics[height=\paperheight]{./cvp_2d}
411\end{frame}
412
413\begin{frame}{Why Lattices?}
414 \begin{itemize}
415 \item LLL algorithm is used to solve SVP and CVP.
416 \begin{itemize}
417 \item LLL (Lenstra–Lenstra–Lovász): polynomial time method used for lattice basis reduction, which transforms a given basis of a lattice into a new basis that is shorter and nearly orthogonal
418 \end{itemize}
419
420 \item Both SVP and CVP become computationally difficult (NP hard*) as the
421 lattice dimension $n$ grows (even on quantum computers)
422 \end{itemize}
423\end{frame}
424
425
426\begin{frame}{NTRU}
427
428 \begin{defn}[NTRU key recovery problem]
429 Given $h(x)$, find ternary polynomials $f, g \in \mathcal{T}$ satisfying
430 $$f(x) \cdot h(x) = g(x) \pmod q \in R_q$$
431 Where $R_q = \Zz_q[X]/(X^n-1)$.
432 \end{defn}
433
434 \pause
435 \begin{itemize}
436 \item 1998, was first scheme using polynomial rings, which latter where approached as agebraically structured lattices
437 \begin{itemize}
438 \item "lattice-based" bcs recovering the small secret polynomials can be formulated and attacked as a lattice problem
439 \item earlier lattice usage: in 1978, Knapsack cryptosystems targeted by lattice attacks
440 \end{itemize}
441 \item following the approach, in 2002, Micciano modified Ajtai's function to work over polynomial rings getting efficiency improvements
442 \end{itemize}
443\end{frame}
444
445% TODO diagrams of SVP, CVP, SIS
446
447\begin{frame}{Hard problems in lattices - SIS}
448 \begin{defn}[SIS (Short Integer Solution)]
449 given $q \in \Zz$ and matrix $A \in \Zz_q^{m \times n}$, find a non-zero short $z \in \Zz^n$ s.th.
450 $$A \cdot z = 0 \pmod q$$
451
452 \small{"short": $z \in \{B, B\}^n$ for some bound $B$, often $z \in \{-1, 0, 1 \}^n$.}
453 \end{defn}
454
455 \pause
456 The set of all solutions to the SIS problem forms the (q-ary) lattice
457 $$\Lambda^{\perp}_q(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
458 where the SIS problem becomes the SVP for $\Lambda_q^{\perp}(A)$
459
460\end{frame}
461
462\begin{frame}{}
463 \begin{defn}[Ring SIS (Ring Short Integer Solution)]
464 given 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
465
466 $$A z = \sum_i a_i \cdot z_i = 0 \in R_q$$
467 \end{defn}
468
469 \pause
470 \begin{defn}[MSIS (Module Short Integer Solution)]
471 given 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
472
473 $$A z = 0 \in R_q^m$$
474 $$ie.~ \sum_i a_{ij} \cdot z_j = 0 \in R_q, ~~for~ i=1, \ldots, m$$
475 \end{defn}
476
477 \pause
478 Notice that Module-SIS is a Ring-SIS with $rank=1$ ($m=1$).
479\end{frame}
480
481\begin{frame}{}
482 % TODO maybe rm these remarks
483 \begin{itemize}
484 \item without $||z|| \leq \beta$, it is easy to find a solution via \emph{Gaussian elimination}.
485 \item $\beta < q$, because otherwise $z=(q, 0, \ldots, 0) \in R^m$ would always be a valid solution.
486 \item $\beta$ and $m$ must be large enough so that a solution is guaranteed to exist, usually $\beta \geq \sqrt{\hat{m}}$ and $m \geq \hat{m}$ where $\hat{m}$ is the smallest integer greater than $n \log q$.
487 \end{itemize}
488
489 Again: overall when doing lattice-based cryptography, we will be interested into keeping the values \emph{short}, aka. of small norm.
490 \pause
491 (example of decomposing values to keep small norms when doing operations in cryptographic protocols)
492\end{frame}
493
494\begin{frame}{Hard problems in lattices}
495 \begin{defn}[LWE (Learning With Errors)]
496 choose a matrix $A \in^R \Zz_q^{m \times n}$, a secret vector $s \in^R \Zz_q^n$, and an error vector $e \in^R [-B, B]^m$. Let $b = As +e \pmod q \in \Zz_q^m$.
497
498 Given the pair $(A, b)$, the goal is to recover $s$.
499 \end{defn}
500 Search-LWE \& Decisional-LWE problems.
501
502 \pause
503 For LWE samples, vector $b$ is relatively close to exactly one vector in the LWE lattice:
504 \begin{align*}
505 \Lambda_q(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
506 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
507 \end{align*}
508
509 \pause
510 Observe: if $e=0$, is a system of linear equations, which can be efficiently determined using Gaussian elimination over $\Zz_q$. Hardness comes from the noise/error term $e \neq 0$ (and the norm bound).
511
512 \pause
513 Similarly as with SIS, we also have Ring-LWE and Module-LWE variants of LWE.
514\end{frame}
515
516\begin{frame}{Plain - Module - Ring}
517 $$R_q = \mathbb{Z}_q[x]/(x^n+1)$$
518
519 \small{
520 $$
521 \begin{array}{c|c|c}
522 \text{Assumption} &
523 \text{Public linear relation} &
524 \text{Underlying algebra}
525 \\ \hline
526 \text{Plain LWE} &
527 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
528 A \in \mathbb{Z}_q^{m \times n}
529 \\[0.5em]
530 \text{Module-LWE} &
531 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
532 A \in R_q^{k \times k},
533 \quad
534 \mathbf{s},\mathbf{e},\mathbf{b} \in R_q^k
535 \\[0.5em]
536 \text{Ring-LWE} &
537 b = as + e \pmod q &
538 a,s,e,b \in R_q
539 \end{array}
540 $$
541 $$
542 \begin{array}{c|c|c}
543 \text{Assumption} &
544 \text{Public linear relation} &
545 \text{Underlying algebra}
546 \\ \hline
547 \text{Plain SIS} &
548 A\mathbf{z} = \mathbf{0} \pmod q,
549 \quad
550 \mathbf{z} \neq \mathbf{0},
551 \quad
552 \|\mathbf{z}\| \text{ small} &
553 A \in \mathbb{Z}_q^{m \times n},
554 \quad
555 \mathbf{z} \in \mathbb{Z}^n
556 \\[0.8em]
557 \text{Module-SIS} &
558 A\mathbf{z} = \mathbf{0} \pmod q,
559 \quad
560 \mathbf{z} \neq \mathbf{0},
561 \quad
562 \|\mathbf{z}\| \text{ small} &
563 A \in R_q^{m \times n},
564 \quad
565 \mathbf{z} \in R^n
566 \\[0.8em]
567 \text{Ring-SIS} &
568 a z = 0 \pmod q,
569 \quad
570 z \neq 0,
571 \quad
572 \|z\| \text{ small} &
573 a \in R_q,
574 \quad
575 z \in R
576 \end{array}
577 $$
578}
579
580
581\end{frame}
582
583\begin{frame}{Dual lattices}
584 SIS lattice:
585 $$\Ll^{\perp}(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
586
587 LWE lattice:
588 \begin{align*}
589 \Ll(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
590 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
591 \end{align*}
592
593
594 \pause
595 Dual of a lattice:
596 $$\Ll^* = \{ y \in \Rr^m ~|~ \langle y, x \rangle \in \Zz ~\forall~ x \in \Ll \}$$
597
598 ie. all vectors that measure lattice points with integers.
599
600 \vspace{0.5cm}
601 \pause
602 SIS lattices and LWE lattices are dual to each other
603 $$\Ll(A) = q \Ll^{\perp *}(A) ~~~\text{ie.}~~~ \frac{1}{q} \Ll(A) = \Ll^{\perp *}(A)$$
604
605\end{frame}
606
607\begin{frame}
608 \hspace*{-0.8cm}
609 \includegraphics[width=\paperwidth]{./lattice_examples}
610\end{frame}
611
612\begin{frame}{Ajtai commitments}
613
614 \begin{defn}[Ajtai commitemnt]
615 For a public random matrix $A \in \Zz_q^{m \times n}$, embedding matrix $G \in \Zz_q^{m \times l}$ and a short random vector $r \in \{-B, B\}^n$ (for bound $B$), an Ajtai commitment to the message $x \in \Zz_q^l$ (bounded to $B$) is
616 $$c = A r + G x \pmod q \in \Zz_q^n$$
617 \end{defn}
618
619 Observe that this is closely related to the SIS problem ($Az=0 \pmod q$), and it relies on its hardness.
620
621
622\end{frame}
623
624\section[Some cryptography]{Some cryptography}
625
626\begin{frame}{ML-KEM (Kyber)}
627 \begin{itemize}
628 \item ML-KEM (Kyber): Key Encapulation Mechanism. ie. Alice encapsulates a (symmetric) key using Bob's public key
629 \item ML-DSA (Dilithium): signature scheme
630 \item Falcon: signature scheme
631 \item LaBRADOR: SNARK scheme
632 \end{itemize}
633\end{frame}
634
635
636\begin{frame}{ML-DSA signatures}
637\end{frame}
638
639\begin{frame}{Falcon signatures}
640\end{frame}
641
642
643\begin{frame}{LaBRADOR SNARK}
644\end{frame}
645
646\section[Conclusions]{Conclusions}
647
648\begin{frame}{Benchmarks}
649 \centering
650 \tiny
651 \setlength{\tabcolsep}{4pt}
652 \renewcommand{\arraystretch}{1.10}
653
654 \textbf{Digital signatures}
655 \vspace{0.05cm}
656
657 \resizebox{0.88\textwidth}{!}{%
658 \begin{tabular}{llll}
659 \toprule
660 \textbf{Scheme} &
661 \textbf{Assumption} &
662 \textbf{Public key size} &
663 \textbf{Signature size} \\
664 \midrule
665
666 Falcon-512
667 & NTRU lattice
668 & $897$ B
669 & $666$ B \\
670
671 ML-DSA-44
672 & Module-LWE / Module-SIS
673 & $1.31$ KB
674 & $2.42$ KB \\
675
676 XMSS-SHA2-10-256
677 & hash based, stateful
678 & $64$ B
679 & $2.50$ KB \\
680
681 SLH-DSA-128s
682 & hash based, stateless
683 & $32$ B
684 & $7.86$ KB \\
685
686 ECDSA-secp256k1
687 & elliptic curves
688 & $33$ B
689 & $64$ B \\
690
691 \bottomrule
692 \end{tabular}%
693 }
694
695 \vspace{0.20cm}
696
697 \textbf{SNARKs / STARKs}
698 \vspace{0.05cm}
699
700 \resizebox{0.87\textwidth}{!}{%
701 \begin{tabular}{lll}
702 \toprule
703 \textbf{Scheme} &
704 \textbf{Assumption / technique} &
705 \textbf{Proof size} \\
706 \midrule
707
708 Groth16
709 & pairings / elliptic curves
710 & $\sim 128$ B \\
711
712 LaBRADOR
713 & Module-SIS
714 & $\sim 50$--$60$ KB \\
715
716 Flock
717 & binary fields + coding theory
718 & $\sim 200$--$400$ KiB \\
719
720 Binius64
721 & binary fields + sumcheck
722 & $\sim 200$--$500$ KiB \\
723
724 Plonky2 & Plonk + FRI
725 & $\sim 40$--$200$ KB \\
726
727 Plonky3 / FRI-STARK
728 & polynomial IOP + FRI
729 & $\sim 1$--$3$ MiB \\
730
731 \bottomrule
732 \end{tabular}
733 }
734\end{frame}
735
736\begin{frame}{Conclusions}
737\end{frame}
738
739
740\end{document}