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\usepackage{xcolor}
23\usepackage[most]{tcolorbox}
24
25\graphicspath{ {./imgs-lattices} }
26
27\setbeamertemplate{itemize}{$\circ$}
28\setbeamertemplate{itemize items}{$\circ$}
29
30\beamertemplatenavigationsymbolsempty %% no navigation bar
31
32\setbeamertemplate{footline}{\hspace*{.1cm}\scriptsize{
33\hspace*{50pt} \hfill\insertframenumber/\inserttotalframenumber\hspace*{.1cm}\vspace*{.1cm}}}
34
35% paint red background to slides that I may end up removing
36\newenvironment{mayberm}[1][red!20]
37 {\setbeamercolor{background canvas}{bg=#1}}
38 {}
39
40
41\setbeamertemplate{caption}[numbered]
42\setbeamerfont{caption}{size=\tiny}
43
44\newtheoremstyle{customstyle}
45 {18pt} % Space above
46 {0pt} % Space below
47 {} % Body font
48 {} % Indent
49 {\bfseries} % Head font
50 {.} % Punctuation after head
51 { } % Space after head
52 {} % Head spec
53
54\theoremstyle{customstyle}
55
56\newtheorem{thm}{Theorem}[section]
57\let\lemma\relax
58\let\endlemma\relax
59\newtheorem{lemma}[thm]{Lemma}
60\newtheorem{prop}[thm]{Proposition}
61\newtheorem{cor}[thm]{Corollary}
62\newtheorem{defn}[thm]{Definition}
63\newtheorem{remark}[thm]{Remark}
64
65
66\newcommand{\Rr}{\mathbb{R}}
67\newcommand{\Zz}{\mathbb{Z}}
68\newcommand{\Ll}{\mathcal{L}}
69
70\title{Introduction to lattice based cryptography}
71\author{arnaucube}
72\date{\scriptsize{September 2026, Barcelona}}
73
74\begin{document}
75
76\frame{\titlepage}
77
78
79
80\section[Motivation]{Motivation}
81
82% - Motivation
83% - till now we've been mostly using RSA & E.C. cryptography
84% - they are susceptible to quantum computers based attacks. Shor's algorithm, etc
85% - post-quantum cryptography context: hash-based (starks), lattices, isogenesis
86% - historical timeline of papers (XMMS SPHINCHS (+), Falcon, etc (exclude isogenesis)
87% - hash vs lattices: hash had more engineering effort, it's currently more performant. Lattice have more algebraic structure, interesting properties.
88% - Lattices math
89% - lattice hard problems are based on the hardness of finding short vectors. SVP, CVP, SIS, etc
90
91% TODO: why lattices are post quantum
92% Lattices are already used in browsers: explain how, dual signautres, etc
93
94\begin{frame}{Motivation}
95 \begin{itemize}
96 \item till now most cryptography relied on hardness of finding prime factors or finding the discrete logarithm, ie. RSA, Elliptic Curves, etc
97 \item Shor's algorithm suggests that factorization can be done in polynomial time (on quantum computers).\\
98 \small{
99 $\rightarrow$ given an odd composite $n \in \Zz$, find $d \in \Zz$, such that $1< d <n$ and $d|n$.
100 }
101 \item even if quantum computers never reach, the threat is there, so we must prepare
102 \item since 2023/2024 Chrome and Firefox have lattice-based cryptography to the browser for TLS
103 \begin{itemize}
104 \item hybrid: X25519 + ML-KEM to stablish a symmetric encryption key
105 \item protect against \emph{harvest now, decrypt later} attacks
106 \end{itemize}
107 \end{itemize}
108\end{frame}
109
110\begin{frame}{Motivation (in Ethereum's ecosystem)}
111 \begin{itemize}
112 \item Ethereum, is going with hash-based signatures for the validators.
113 \begin{itemize}
114 \item aggregation through SNARK proofs (eg. binius, flock, etc)
115 \item each slot a different XMSS leaf
116 \item the most conservative choice in terms of security
117 \end{itemize}
118 \item hash-based simpler to implement, less potential errors. Whereas lattice-based have more subtelties
119 \item hash-based schemes don't have much algebraic structure
120 \begin{itemize}
121 \item good for less attacks, not so fun to build stuff with
122 \item eg. elliptic curves have algebraic structure, allows for signature aggregation, thresholds, etc
123 \end{itemize}
124 \item lattice-based schemes have smaller proofs, signatures and public keys
125 \begin{itemize}
126 \item better suited for end-user wallets
127 \end{itemize}
128 \end{itemize}
129\end{frame}
130
131\begin{frame}{Post Quantum Cryptography - Status of the ecosystem}
132 \begin{itemize}
133 \item isogenesis based
134 \item hash based
135 \item codes based
136 \item lattice based
137 \item multivariate based
138 \end{itemize}
139 TODO
140\end{frame}
141
142\section[Preliminaries]{Preliminaries}
143\begin{frame}{Preliminaries}
144 Recap of concepts:
145 \begin{itemize}
146 \item Rings
147 \begin{itemize}
148 \item ideals
149 \end{itemize}
150 \item Vector Spaces
151 \item Modules
152 \item Kernel
153 \end{itemize}
154\end{frame}
155
156
157\begin{mayberm}
158
159\begin{frame}{Rings}
160 \vspace*{-0.5cm}
161 \small{
162 \begin{defn}[Ring]
163 A set $A$ with operations called \emph{addition} and \emph{multiplication} which satisfy the following axioms:
164 \begin{enumerate}[i.]
165 \item $A$ with addition alone is an abelian group.
166 \item Multiplication is associative.
167 \item Multiplication is distributive over addition. That is, $\forall a,b,c \in A$,
168 $$a(b+c) = ab + ac$$
169 $$(b+c)a = ba + ca$$
170 \end{enumerate}
171 \end{defn}
172
173 \pause
174 Remark: a field is a ring with inverse.
175
176 \pause
177 \begin{defn}[Ideal]
178 $I \subset R$ ($R$ ring) such that $0 \in I$ and $\forall x \in I,~ r \in R,~ xr, rx \in I$.\\
179 \hspace*{2em} ie. $I$ absorbs products in $R$.
180 \end{defn}
181
182 \pause
183 Eg: Ring $\Zz=\{\ldots, -2, -1, 0, 1, 2, 3, \ldots \}$, Ideal $n \Zz= \{n k ~|~ k \in \Zz \}$ for fixed $n \in \Zz$.
184 }
185\end{frame}
186
187
188\begin{frame}{Vector spaces}
189 % vector space
190 % norm of a vector
191 % linear independent
192 % span
193 % basis
194 % rank: number of basis vectors / maximum number of linearly independent columns / maximum number of linearly independent rows
195 % some diagram
196
197
198 \begin{defn}[Vector space]
199 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
200
201 \begin{itemize}
202 \item $V$ with vector addition is an abelian group
203 \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:
204 $\forall k, l \in F,~\overrightarrow{a},\overrightarrow{b} \in V$
205 \begin{enumerate}[i.]
206 \item $k(\overrightarrow{a} + \overrightarrow{b}) = k\overrightarrow{a} + k\overrightarrow{b}$
207 \item $(k + l)\overrightarrow{a} = k\overrightarrow{a} + k\overrightarrow{b}$
208 \item $k(l\overrightarrow{a}) = (kl)\overrightarrow{a}$
209 \item $1 \overrightarrow{a} = \overrightarrow{a}$
210 \end{enumerate}
211 \end{itemize}
212 \end{defn}
213
214 \begin{itemize}
215 \item basis: set of vectors that \emph{span} the vector space
216 % TODO WIP
217 \end{itemize}
218\end{frame}
219
220
221\begin{frame}{Modules}
222 \small{
223
224 \begin{defn}[Module]
225 Let $A$ be a ring. An $A$-module is an Abelian group $M$ with a multiplication
226 map
227 \begin{align*}
228 A \times M &\longrightarrow M\\
229 (f, m) &\longmapsto fm
230 \end{align*}
231 satisfying $\forall~ f,g \in A,~~ m, n \in M$.
232 \begin{enumerate}[i.]
233 \item $f(m \pm n)=fm \pm fn$
234 \item $(f \pm g) m = fm \pm gm$
235 \item $(fg) m = f(gm)$
236 \item $1_A m = m$
237 \end{enumerate}
238 \end{defn}
239
240 \pause
241
242 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.
243 }
244\end{frame}
245
246\begin{frame}{Kernel}
247 TODO
248
249 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]
250 Intuition: set of inputs that a function completely "erases", ie. they all get mapped to zero.
251 \end{tcolorbox}
252\end{frame}
253
254\end{mayberm}
255
256\section[Lattices]{Lattices}
257
258\begin{frame}{Lattices}
259 \begin{defn}[Lattice]
260 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$.
261
262 \pause
263 $B = b_1, \ldots, b_m \in \Rr^n$ is the \emph{basis} of $\Ll$. We denote it $\Ll=\Ll(B)$.
264
265 $$\Ll(B) := B \cdot \Rr^n = \{ \sum_{i=1}^n c_i b_i ~|~ c_i \in \Rr^n \}$$
266 \end{defn}
267
268 \pause
269 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]
270 \emph{Intuition: endless grid of dots where you can only move by taking whole-number
271 steps along a fixed set of directions.}
272 \end{tcolorbox}
273
274 \pause
275 Note: basis of a lattice are not unique.
276
277 \pause
278 Dimension of $\Ll$ is $n$, rank of $\Ll$ is $m$. Full-rank lattice: $m=n$.
279
280 \pause
281 In most cryptographic applications, $b_1, \ldots, b_n \in \Zz^n$, ie. $\Ll$ is an integer lattice.
282
283\end{frame}
284
285\begin{frame}{}
286 \includegraphics[width=9.5cm]{./2d-lattice}
287\end{frame}
288
289\begin{frame}{}
290 \includegraphics[width=9.5cm]{./two_bases_lattice}
291\end{frame}
292
293\begin{frame}{Lattice properties}
294 a $n$-dimensional lattice $\Ll$ is
295 \begin{enumerate}[i.]
296 \item \emph{additive subgroup} of $\Rr^n$: $\Ll$ is the nonempty subset of $\Rr^n$ closed under vector addition (and substraction),\\
297 $$\text{ie.}~ \forall x,y \in \Ll,~ -x, x+y \in \Ll$$
298 \item \emph{discrete}: every $x \in \Ll$ has a neighborhood in $\Rr^n$ in which $x$ is the only lattice point.
299 \end{enumerate}
300
301 \pause
302
303 \small{
304 \begin{defn}[\emph{minimum} of a lattice $\Ll$]
305 $$\lambda_1(\Ll) = min \{ ||x|| ~|~ x\in \Ll, x \neq 0 \}$$
306
307 \pause
308
309 \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.
310 $$\lambda_1(\Ll) \leq \lambda_2(\Ll) \leq \cdots \leq \lambda_n(\Ll)$$
311 \end{defn}
312 }
313\end{frame}
314
315\begin{frame}{}
316 \includegraphics[width=9.5cm]{./cvp_sphere}
317 % \includegraphics[width=9.5cm]{./sphere_packing} % TODO
318\end{frame}
319
320\begin{frame}{Lattice properties}
321 \small{
322 recall, a lattice:
323 \vspace*{-0.7cm}
324 $$\Ll(B) := B \cdot \Zz^n = \{ \sum_{i=1}^n z_i b_i ~|~ z_i \in \Zz^n \}$$
325
326 \pause
327 \vspace*{-0.4cm}
328 \begin{itemize}
329 \item $B = (b_1, \ldots, b_n) \in \Zz^{n \times n}$: basis matrix, finite description of the lattice (not the lattice itself)
330 \item the matrix-vector product $Bz$ maps an integer coordinate vector $z \in \Zz^n$ into a lattice point in $\Zz^n$.
331 \end{itemize}
332 }
333
334 \pause
335
336 \vspace*{-0.4cm}
337\begin{columns}[T]
338 \begin{column}{0.65\textwidth}
339
340 \small{
341 \begin{itemize}
342 \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
343 \begin{itemize}
344 \item the lattice $\Ll(B)$ is the invariant set of points
345 \item the basis $B$ is not unique
346 \end{itemize}
347
348 \vspace*{-0.3cm}
349 \pause
350 \item $B \in \Zz^{n \times n}$, $n$ vectors, each with $n$ coordinates $\Longrightarrow$ requires $\mathcal{O}(n^2)$ integers.
351 \begin{itemize}
352 \item only if we could have some better lattice structure to represent the lattice with fewer entries...
353 \end{itemize}
354 \end{itemize}
355 }
356
357 \end{column}
358
359 \begin{column}{0.40\textwidth}
360 \centering
361 \includegraphics[width=\linewidth]{./two_bases_lattice}
362 \end{column}
363\end{columns}
364\end{frame}
365
366
367\begin{frame}{q-ary lattice}
368 a full-rank lattice is q-ary if $q \Zz^d \subseteq \Ll \subseteq \Zz^d$
369
370 $\Longrightarrow$ q-ary lattice is an infinite set of integer points, but membership depends only on the residue class modulo $q$
371 $$\text{ie. if}~ x \in \Ll, ~\text{then}~ x + qz \in \Ll ~\forall z \in \Zz^d$$
372
373 \pause
374
375 Let $A \in \Zz^{n \times m}$ define the homomorphism
376 \begin{align*}
377 \psi_A: \Zz^m &\longrightarrow \Zz_q^n\\
378 z &\longmapsto Az \pmod q
379 \end{align*}
380
381 \pause
382
383 % image q-ary lattice:
384 % $$\Ll_q(A) = \{ y \in \Zz^n ~|~ y=Az \mod q ~\text{for some}~ z \in \Zz_q^m \}$$
385 %
386 % lattice generated by the rows of $A$.
387 % \pause
388
389 q-ary lattice:
390 $$\Ll_q^{\perp}(A) = ker(\psi_A) = \{ z \in \Zz^m ~|~ Az = 0 \mod q \}$$
391 contains all vectors that are orthogonal modulo $q$ to the rows of $A$.
392
393 \scriptsize{
394 The q-ary lattice generated by the rows of $A$:
395 $$\Ll_q(A) = \{ y \in \Zz^m ~|~ y=A^Tz \mod q ~\text{for some}~ z \in \Zz_q^n \}$$
396 }
397
398 % TODO why q-ary is better? prev.slide says O(n^2) without q-ary, how with q-ary?
399\end{frame}
400
401\begin{frame}{Polynomial rings}
402 \small{
403 \begin{itemize}
404 \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.
405
406 \item Polynomial rings: represent an $n$-dimensional vector
407 $(a_0,\ldots,a_{n-1}) \in \Zz_q^n$ as a single ring element (polynomial)
408 $$a(X) = a_0 + a_1 X + \cdots + a_{n-1} X^{n-1} \in \Zz_q[X]/(X^n+1)$$
409 \end{itemize}
410 }
411
412 \pause
413 \small{
414 \begin{itemize}
415 \item[-] Addition:
416 $a(x) + b(x) = \sum_{i=1}^d (a_i + b_i) X^i$
417 \pause
418 \item[-] Multiplication:
419 $$a(X) \cdot b(X)
420 = \left(
421 \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}
422 a_i b_j X^{i+j}
423 \right)
424 \in \Zz_q[X]/(X^n+1)$$
425
426 \hspace*{4em}Since $X^n=-1$ then $X^{n+k} = -X^k$\\
427 $\Longrightarrow~ \mathcal{O}(n^2)$ naively, $\mathcal{O}(n \log n)$ using NTT.
428 \end{itemize}
429 }
430\end{frame}
431
432
433\section[Hard problems]{Hard problems}
434
435\begin{frame}{Incomplete Timeline}
436 \begin{timeline}
437 1978 \quad Knapsack cryptosystems attacked using lattice methods
438
439 1996 \quad NTRU encryption
440
441 2005 \quad Learning With Errors (LWE)
442
443 2008 \quad Practical secure lattice-signature schemes
444
445 2009 \quad Fully Homomorphic Encryption (FHE)
446
447 2016 \quad NewHope (Ring-LWE KEM)
448
449 2017 \quad Kyber (Module-LWE based) & Dilithium (Module-LWE & Module-SIS based)
450
451 2020s \quad standardiszation: ML-KEM (Kyber) and ML-DSA (Dilithium)
452 \end{timeline}
453\end{frame}
454
455
456\begin{frame}{Hard problems in lattices - SVP and CVP}
457 \small{
458 \begin{itemize}
459 \item In elliptic curve cryptography, we rely on the hardness of the Discrete Logarithm problem:\\
460 \begin{adjustwidth}{2em}{0pt}
461 given publicly known $g, p \in \mathbb{G}$, find privately known $x \in \Zz$ such that $p=g^x$.
462 \end{adjustwidth}
463
464 \item In lattice based cryptography, we rely on problems related to finding short vectors in the lattice.
465 \end{itemize}
466 }
467
468 \pause
469 \begin{defn}[SVP (Shortest Vector Problem)]
470 find a shortest non-zero vector $x \in \Ll$, ie. that minimizes the Euclidean norm $||x||$, that is $\lambda_1(\Ll)=||x||$.
471 \end{defn}
472
473 \colorbox{gray!20}{Intuition:
474 find the shortest possible jump from the origin to another dot
475 }
476
477 \pause
478 \begin{defn}[CVP (Closest Vector Problem)]
479 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||$.
480 \end{defn}
481
482 \colorbox{gray!20}{Intuition:
483 find the grid dot that is closest to a given point (off the grid)
484 }
485
486\end{frame}
487
488\begin{frame}
489 \includegraphics[height=\paperheight]{./cvp_2d}
490\end{frame}
491
492\begin{frame}{Why Lattices?}
493 \begin{itemize}
494 \item LLL algorithm is used to solve SVP and CVP.
495 \begin{itemize}
496 \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, which makes SVP and CVP easier to approximate or solve using subsequent algorithms.
497 % \colorbox{gray!20}{Intuition:
498 \begin{tcolorbox}[colback=gray!15, colframe=gray!15] Intuition:
499 make the lattice basis less skewed. Same grid of points, just a simpler
500 basis. We don't change the lattice, we change the coordinate system used to
501 describe it. $\longrightarrow$ easier to solve SVP and CVP.
502 % }
503 \end{tcolorbox}
504 \item improvement: BKZ reduction algorithm
505 \end{itemize}
506
507 \item Both SVP and CVP become computationally difficult (NP hard) as the
508 lattice dimension $n$ grows (even on quantum computers)
509 \end{itemize}
510\end{frame}
511
512
513\begin{frame}{NTRU}
514
515 \begin{defn}[NTRU key recovery problem]
516 Given $h(x)$, find ternary polynomials $f, g \in \mathcal{T}$ satisfying
517 $$f(x) \cdot h(x) = g(x) \pmod q \in R_q$$
518 Where $R_q = \Zz_q[X]/(X^n-1)$.
519 \end{defn}
520
521 \pause
522 \begin{itemize}
523 \item 1998, was first scheme using polynomial rings, which latter where approached as agebraically structured lattices
524 \begin{itemize}
525 \item "lattice-based" bcs recovering the small secret polynomials can be formulated and attacked as a lattice problem
526 \item earlier lattice usage: in 1978, Knapsack cryptosystems targeted by lattice attacks
527 \end{itemize}
528 \item following the approach, in 2002, Micciano modified Ajtai's function to work over polynomial rings getting efficiency improvements
529 \end{itemize}
530\end{frame}
531
532% TODO diagrams of SVP, CVP, SIS
533
534\begin{frame}{Hard problems in lattices - SIS}
535 \begin{defn}[SIS (Short Integer Solution)]
536 given $q \in \Zz$ and matrix $A \in \Zz_q^{m \times n}$, find a non-zero short $z \in \Zz^n$ s.th.
537 $$A \cdot z = 0 \pmod q$$
538
539 \small{"short": $z \in \{B, B\}^n$ for some bound $B$, often $z \in \{-1, 0, 1 \}^n$.}
540 \end{defn}
541
542 \pause
543 The set of all solutions to the SIS problem forms the (q-ary) lattice
544 $$\Lambda^{\perp}_q(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
545 where the SIS problem becomes the SVP for $\Lambda_q^{\perp}(A)$
546
547 \small{
548 \hspace*{2em}\colorbox{gray!20}{Intuition:
549 find a short nonzero vector in the lattice $\Lambda^{\perp}_q(A)$
550 }
551 }
552
553\end{frame}
554
555\begin{frame}{}
556 \begin{defn}[Ring SIS (Ring Short Integer Solution)]
557 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
558
559 $$A z = \sum_i a_i \cdot z_i = 0 \in R_q$$
560 \end{defn}
561
562 \pause
563 \begin{defn}[MSIS (Module Short Integer Solution)]
564 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
565
566 $$A z = 0 \in R_q^m$$
567 $$ie.~ \sum_i a_{ij} \cdot z_j = 0 \in R_q, ~~for~ i=1, \ldots, m$$
568 \end{defn}
569
570 \pause
571 Notice that Module-SIS is a Ring-SIS with $rank=1$ ($m=1$).
572\end{frame}
573
574\begin{frame}{}
575 % TODO maybe rm these remarks
576 \begin{itemize}
577 \item without $||z|| \leq \beta$, it is easy to find a solution via \emph{Gaussian elimination}.
578 \item $\beta < q$, because otherwise $z=(q, 0, \ldots, 0) \in R^m$ would always be a valid solution.
579 \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$.
580 \end{itemize}
581
582 Again: overall when doing lattice-based cryptography, we will be interested into keeping the values \emph{short}, aka. of small norm.
583 \pause
584 (example of decomposing values to keep small norms when doing operations in
585 cryptographic protocols (eg. in LaBRADOR))
586\end{frame}
587
588\begin{frame}{Hard problems in lattices}
589 \begin{defn}[LWE (Learning With Errors)]
590 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$.
591
592 Given the pair $(A, b)$, the goal is to recover $s$.
593 \end{defn}
594 Search-LWE \& Decisional-LWE problems.
595
596 \pause
597 For LWE samples, vector $b$ is relatively close to exactly one vector in the LWE lattice:
598 \begin{align*}
599 \Lambda_q(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
600 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
601 \end{align*}
602
603 \pause
604 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).
605
606 \pause
607 Similarly as with SIS, we also have Ring-LWE and Module-LWE variants of LWE.
608\end{frame}
609
610\begin{frame}{Plain - Module - Ring}
611 $$R_q = \mathbb{Z}_q[x]/(x^n+1)$$
612
613 \small{
614 $$
615 \begin{array}{c|c|c}
616 \text{Assumption} &
617 \text{Public linear relation} &
618 \text{Underlying algebra}
619 \\ \hline
620 \text{Plain LWE} &
621 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
622 A \in \mathbb{Z}_q^{m \times n}
623 \\[0.5em]
624 \text{Module-LWE} &
625 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
626 A \in R_q^{k \times k},
627 \quad
628 \mathbf{s},\mathbf{e},\mathbf{b} \in R_q^k
629 \\[0.5em]
630 \text{Ring-LWE} &
631 b = as + e \pmod q &
632 a,s,e,b \in R_q
633 \end{array}
634 $$
635 $$
636 \begin{array}{c|c|c}
637 \text{Assumption} &
638 \text{Public linear relation} &
639 \text{Underlying algebra}
640 \\ \hline
641 \text{Plain SIS} &
642 A\mathbf{z} = \mathbf{0} \pmod q,
643 \quad
644 \mathbf{z} \neq \mathbf{0},
645 \quad
646 \|\mathbf{z}\| \text{ small} &
647 A \in \mathbb{Z}_q^{m \times n},
648 \quad
649 \mathbf{z} \in \mathbb{Z}^n
650 \\[0.8em]
651 \text{Module-SIS} &
652 A\mathbf{z} = \mathbf{0} \pmod q,
653 \quad
654 \mathbf{z} \neq \mathbf{0},
655 \quad
656 \|\mathbf{z}\| \text{ small} &
657 A \in R_q^{m \times n},
658 \quad
659 \mathbf{z} \in R^n
660 \\[0.8em]
661 \text{Ring-SIS} &
662 a z = 0 \pmod q,
663 \quad
664 z \neq 0,
665 \quad
666 \|z\| \text{ small} &
667 a \in R_q,
668 \quad
669 z \in R
670 \end{array}
671 $$
672}
673
674
675\end{frame}
676
677\begin{frame}{Dual lattices}
678 SIS lattice:
679 $$\Ll^{\perp}(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
680
681 LWE lattice:
682 \begin{align*}
683 \Ll(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
684 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
685 \end{align*}
686
687
688 \pause
689 Dual of a lattice:
690 $$\Ll^* = \{ y \in \Rr^m ~|~ \langle y, x \rangle \in \Zz ~\forall~ x \in \Ll \}$$
691
692 ie. all vectors that measure lattice points with integers.
693
694 \vspace{0.5cm}
695 \pause
696 SIS lattices and LWE lattices are dual to each other
697 $$\Ll(A) = q \Ll^{\perp *}(A) ~~~\text{ie.}~~~ \frac{1}{q} \Ll(A) = \Ll^{\perp *}(A)$$
698
699\end{frame}
700
701\begin{frame}
702 \hspace*{-0.8cm}
703 \includegraphics[width=\paperwidth]{./lattice_examples}
704\end{frame}
705
706\begin{frame}{Ajtai commitments}
707
708 \begin{defn}[Ajtai commitemnt]
709 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
710 $$c = A r + G x \pmod q \in \Zz_q^n$$
711 \end{defn}
712
713 Observe that this is closely related to the SIS problem ($Az=0 \pmod q$), and it relies on its hardness.
714
715
716\end{frame}
717
718\section[Some cryptography]{Some cryptography}
719
720\begin{frame}{Lattice-based cryptography}
721 \begin{itemize}
722 \item ML-KEM (Kyber): Key Encapulation Mechanism. ie. Alice encapsulates a (symmetric) key using Bob's public key
723 \item ML-DSA (Dilithium): signature scheme
724 \item FN-DSA (Falcon): signature scheme, based on NTRU
725 \item LaBRADOR: SNARK scheme
726 \item FHE (BFV, BGV, CKKS, TFHE)
727 \end{itemize}
728\end{frame}
729
730\begin{mayberm}
731\begin{frame}{ML-KEM (Kyber)}
732 \scriptsize{
733 \begin{itemize}
734 \item KEM = Key Encapsulation Mechanism
735 \begin{itemize}
736 \item Alice encapsulates a (symmetric) key using Bob's public key
737 \end{itemize}
738 \item based on Module-LWE
739 \end{itemize}
740 }
741
742$$R_q=\mathbb{Z}_q[X]/(X^{256}+1), A\in R_q^{k\times k}$$
743
744\textbf{Key generation:}
745$$
746\mathbf{s},\mathbf{e}\leftarrow\chi^k,
747\qquad
748\mathbf{t}=A\mathbf{s}+\mathbf{e}
749$$
750
751$$
752pk=(A,\mathbf{t}),\qquad sk=\mathbf{s}
753$$
754
755\textbf{Encapsulation:}
756$$
757\mathbf{u}=A^T\mathbf{r}+\mathbf{e}_1,
758\qquad
759v=\mathbf{t}^T\mathbf{r}+e_2+\operatorname{Encode}(m)
760$$
761
762$$
763c=(\mathbf{u},v),
764\qquad
765K=\operatorname{KDF}(m,c)
766$$
767
768\textbf{Decapsulation:}
769$$
770m'=\operatorname{Decode}\!\left(v-\mathbf{s}^T\mathbf{u}\right)
771$$
772
773Since
774$$
775v-\mathbf{s}^T\mathbf{u}
776=
777\operatorname{Encode}(m)
778+\mathbf{e}^T\mathbf{r}
779+e_2-\mathbf{s}^T\mathbf{e}_1,
780$$
781the message is recovered up to small noise.
782\end{frame}
783\end{mayberm}
784
785
786\begin{frame}{ML-DSA signatures}
787\end{frame}
788
789\begin{mayberm}
790\begin{frame}{Falcon signatures}
791\end{frame}
792
793
794\begin{frame}{LaBRADOR SNARK}
795\end{frame}
796\end{mayberm}
797
798\section[Conclusions]{Conclusions}
799
800\begin{frame}{Benchmarks}
801 \centering
802 % \small{
803 \setlength{\tabcolsep}{4pt}
804 \renewcommand{\arraystretch}{1.10}
805
806 \textbf{Digital signatures}
807 \vspace{0.05cm}
808
809 \resizebox{0.88\textwidth}{!}{%
810 \begin{tabular}{llll}
811 \toprule
812 \textbf{Scheme} &
813 \textbf{Assumption} &
814 \textbf{Public key size} &
815 \textbf{Signature size} \\
816 \midrule
817
818 Falcon-512
819 & NTRU lattice
820 & $897$ B
821 & $666$ B \\
822
823 ML-DSA-44
824 & Module-LWE / Module-SIS
825 & $1.31$ KB
826 & $2.42$ KB \\
827
828 XMSS-SHA2-10-256
829 & hash based, stateful
830 & $64$ B
831 & $2.50$ KB \\
832
833 SLH-DSA-128s
834 & hash based, stateless
835 & $32$ B
836 & $7.86$ KB \\
837
838 ECDSA-secp256k1
839 & elliptic curves
840 & $33$ B
841 & $64$ B \\
842
843 \bottomrule
844 \end{tabular}%
845 }
846
847 \vspace{0.20cm}
848
849 \textbf{SNARKs / STARKs}
850 \vspace{0.05cm}
851
852 \resizebox{0.87\textwidth}{!}{%
853 \begin{tabular}{lll}
854 \toprule
855 \textbf{Scheme} &
856 \textbf{Assumption / technique} &
857 \textbf{Proof size} \\
858 \midrule
859
860 Groth16
861 & pairings / elliptic curves
862 & $128$ B \\
863
864 LaBRADOR
865 & Module-SIS
866 & $50$--$60$ KB \\
867
868 Flock
869 & binary fields + coding theory
870 & $200$--$400$ KiB \\
871
872 Binius64
873 & binary fields + sumcheck
874 & $200$--$500$ KiB \\
875
876 Plonky2 & Plonk + FRI
877 & $40$--$200$ KB \\
878
879 Plonky3 / FRI-STARK
880 & polynomial IOP + FRI
881 & $1$--$3$ MiB \\
882
883 \bottomrule
884 \end{tabular}
885 }
886\end{frame}
887
888\begin{frame}{Conclusions}
889 \begin{itemize}
890 \item not a single assumption: NTRU, SIS, R-SIS, M-SIS, LWE, R-LWE, M-LWE, $\ldots$
891 \end{itemize}
892\end{frame}
893
894
895\end{document}