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{xcolor}
22\usepackage{changepage} % for adjustwidth
23\usepackage{xcolor}
24\usepackage[most]{tcolorbox}
25
26\usepackage{pgf-umlsd} % diagrams
27\usepackage{tikz}
28\usetikzlibrary{positioning,arrows.meta}
29
30\usepackage{comment}
31
32\graphicspath{ {./imgs-lattices} }
33
34\setbeamertemplate{itemize}{$\circ$}
35\setbeamertemplate{itemize items}{$\circ$}
36
37\beamertemplatenavigationsymbolsempty %% no navigation bar
38
39\setbeamertemplate{footline}{\hspace*{.1cm}\scriptsize{
40\hspace*{50pt} \hfill\insertframenumber/\inserttotalframenumber\hspace*{.1cm}\vspace*{.1cm}}}
41
42% paint red background to slides that I may end up removing
43\newenvironment{mayberm}[1][red!20]
44 {\setbeamercolor{background canvas}{bg=#1}}
45 {}
46
47
48\setbeamertemplate{caption}[numbered]
49\setbeamerfont{caption}{size=\tiny}
50
51\newtheoremstyle{customstyle}
52 {18pt} % Space above
53 {0pt} % Space below
54 {} % Body font
55 {} % Indent
56 {\bfseries} % Head font
57 {.} % Punctuation after head
58 { } % Space after head
59 {} % Head spec
60
61\theoremstyle{customstyle}
62
63\newtheorem{thm}{Theorem}[section]
64\let\lemma\relax
65\let\endlemma\relax
66\newtheorem{lemma}[thm]{Lemma}
67\newtheorem{prop}[thm]{Proposition}
68\newtheorem{cor}[thm]{Corollary}
69\newtheorem{defn}[thm]{Definition}
70\newtheorem{remark}[thm]{Remark}
71
72
73\newcommand{\Rr}{\mathbb{R}}
74\newcommand{\Zz}{\mathbb{Z}}
75\newcommand{\Ll}{\mathcal{L}}
76
77\title{Introduction to lattice based cryptography}
78\author{
79\scriptsize{September 2026, Barcelona}
80}
81\date{
82 \scriptsize{
83 \href{https://arnaucube.com}{arnaucube.com}\\
84 \href{https://x.com/arnaucube}{$@$arnaucube}
85}
86}
87
88\begin{document}
89
90\frame{\titlepage}
91
92
93
94\section[Motivation]{Motivation}
95
96% - Motivation
97% - till now we've been mostly using RSA & E.C. cryptography
98% - they are susceptible to quantum computers based attacks. Shor's algorithm, etc
99% - post-quantum cryptography context: hash-based (starks), lattices, isogenesis
100% - historical timeline of papers (XMMS SPHINCHS (+), Falcon, etc (exclude isogenesis)
101% - hash vs lattices: hash had more engineering effort, it's currently more performant. Lattice have more algebraic structure, interesting properties.
102% - Lattices math
103% - lattice hard problems are based on the hardness of finding short vectors. SVP, CVP, SIS, etc
104
105% TODO: why lattices are post quantum
106% [done] Lattices are already used in browsers: explain how, hybrid signatures, etc
107% clarify L^\perp notation, is it q-ary?
108
109\begin{frame}{Motivation}
110 \begin{itemize}
111 \item till now most cryptography relied on hardness of finding prime factors or finding the discrete logarithm, ie. RSA, Elliptic Curves, etc
112 \item Shor's algorithm suggests that factorization can be done in polynomial time (on quantum computers).\\
113 \small{
114 $\rightarrow$ given an odd composite $n \in \Zz$, find $d \in \Zz$, such that $1< d <n$ and $d|n$.
115 }
116 \item even if quantum computers never reach, the fact that there is a threat, forces us to prepare for it
117 \item real-world example: since 2023/2024 Chrome and Firefox have lattice-based cryptography to the browser for TLS
118 \begin{itemize}
119 \item hybrid: X25519 + ML-KEM to stablish a symmetric encryption key
120 \item protect against \emph{harvest now, decrypt later} attacks
121 \end{itemize}
122 \end{itemize}
123\end{frame}
124
125\begin{frame}{Post Quantum Cryptography - Status of the ecosystem}
126 \begin{itemize}
127 \item isogenesis based
128 \item hash based
129 \item codes based
130 \item lattice based
131 \item multivariate based
132 \end{itemize}
133 % TODO
134\end{frame}
135
136
137\begin{frame}{Motivation (in Ethereum's ecosystem)}
138 \begin{itemize}
139 \item Ethereum, is going with hash-based signatures for the validators.
140 \begin{itemize}
141 \item aggregation through SNARK proofs (eg. binius, flock, etc)
142 \item each slot a different XMSS leaf
143 \item the most conservative choice in terms of security
144 \end{itemize}
145 \item hash-based simpler to implement, less potential errors. Whereas lattice-based have more subtelties
146
147 \pause
148
149 \item hash-based schemes don't have much algebraic structure
150 \begin{itemize}
151 \item good for less attacks, not so fun to build stuff with (less room to compose)
152 \item eg. elliptic curves have algebraic structure, allows for signature aggregation, thresholds, etc
153 \end{itemize}
154
155 \pause
156 \item lattice-based schemes have smaller proofs, signatures and public keys
157 \begin{itemize}
158 \item better suited for end-user wallets
159 \end{itemize}
160 \end{itemize}
161\end{frame}
162
163\begin{frame}{First, some tools}
164 \centering
165 \includegraphics[width=8.0cm]{./zelda-dangerous-out-there}
166\end{frame}
167
168\begin{frame}{Recap of concepts}
169 \begin{itemize}
170 \item \textbf{Ring:} a set with addition and multiplication, where addition forms an abelian group and multiplication is associative and distributive over addition.
171 \begin{itemize}
172 \item \textbf{Ideal:} a subset $I \subseteq R$ closed under addition and under multiplication by arbitrary elements of $R$.
173 \scriptsize{
174 \colorbox{gray!20}{Intuition:
175 $I$ absorbs products in $R$.
176 }}
177 \end{itemize}
178
179 \item \textbf{Vector space:} an abelian group of vectors equipped with scalar multiplication by elements of a field.
180 \scriptsize{
181 \begin{itemize}
182 \item \textbf{basis}: linearly independent vectors that span the vector space\\
183 ie. for $b_1, \ldots, b_n$ a basis of $V$, then $\forall v \in V$,
184 $$v=v_1 b_1 + \ldots + v_n b_n \in V$$
185 \end{itemize}
186 }
187
188 \normalsize
189 \item \textbf{Module:} a generalization of a vector space where the scalars come from a ring instead of necessarily a field.
190 % \scriptsize{
191 % \begin{tcolorbox}[colback=gray!15, colframe=gray!15]Intuition:
192 % 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.
193 % \end{tcolorbox}}
194
195 \normalsize
196 \item \textbf{Kernel:} for a homomorphism $f:A\to B$, the subset
197 $\ker(f)=\{x\in A:f(x)=0\}$ of elements mapped to zero.
198 \scriptsize{
199 \colorbox{gray!20}{Intuition:
200 inputs that a function completely "erases", ie. turns into zero.
201 }}
202
203 \end{itemize}
204\end{frame}
205
206
207
208\begin{comment}
209\begin{mayberm}
210
211\section[Preliminaries]{Preliminaries}
212\begin{frame}{Preliminaries}
213 Recap of concepts:
214 \begin{itemize}
215 \item Rings
216 \begin{itemize}
217 \item ideals
218 \end{itemize}
219 \item Vector Spaces
220 \item Modules
221 \item Kernel
222 \end{itemize}
223\end{frame}
224
225\begin{frame}{Rings}
226 \vspace*{-0.5cm}
227 \small{
228 \begin{defn}[Ring]
229 A set $A$ with operations called \emph{addition} and \emph{multiplication} which satisfy the following axioms:
230 \begin{enumerate}[i.]
231 \item $A$ with addition alone is an abelian group.
232 \item Multiplication is associative.
233 \item Multiplication is distributive over addition. That is, $\forall a,b,c \in A$,
234 $$a(b+c) = ab + ac$$
235 $$(b+c)a = ba + ca$$
236 \end{enumerate}
237 \end{defn}
238
239 \pause
240 Remark: a field is a ring with inverse.
241
242 \pause
243 \begin{defn}[Ideal]
244 $I \subset R$ ($R$ ring) such that $0 \in I$ and $\forall x \in I,~ r \in R,~ xr, rx \in I$.\\
245 \hspace*{2em} ie. $I$ absorbs products in $R$.
246 \end{defn}
247
248 \pause
249 Eg: Ring $\Zz=\{\ldots, -2, -1, 0, 1, 2, 3, \ldots \}$, Ideal $n \Zz= \{n k ~|~ k \in \Zz \}$ for fixed $n \in \Zz$.
250 }
251\end{frame}
252
253
254\begin{frame}{Vector spaces}
255 % vector space
256 % norm of a vector
257 % linear independent
258 % span
259 % basis
260 % rank: number of basis vectors / maximum number of linearly independent columns / maximum number of linearly independent rows
261 % some diagram
262
263
264 \begin{defn}[Vector space]
265 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
266
267 \begin{itemize}
268 \item $V$ with vector addition is an abelian group
269 \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:
270 $\forall k, l \in F,~\overrightarrow{a},\overrightarrow{b} \in V$
271 \begin{enumerate}[i.]
272 \item $k(\overrightarrow{a} + \overrightarrow{b}) = k\overrightarrow{a} + k\overrightarrow{b}$
273 \item $(k + l)\overrightarrow{a} = k\overrightarrow{a} + k\overrightarrow{b}$
274 \item $k(l\overrightarrow{a}) = (kl)\overrightarrow{a}$
275 \item $1 \overrightarrow{a} = \overrightarrow{a}$
276 \end{enumerate}
277 \end{itemize}
278 \end{defn}
279
280 \begin{itemize}
281 \item basis: set of vectors that \emph{span} the vector space
282 % TODO WIP
283 \end{itemize}
284\end{frame}
285
286
287\begin{frame}{Modules}
288 \small{
289
290 \begin{defn}[Module]
291 Let $A$ be a ring. An $A$-module is an Abelian group $M$ with a multiplication
292 map
293 \begin{align*}
294 A \times M &\longrightarrow M\\
295 (f, m) &\longmapsto fm
296 \end{align*}
297 satisfying $\forall~ f,g \in A,~~ m, n \in M$.
298 \begin{enumerate}[i.]
299 \item $f(m \pm n)=fm \pm fn$
300 \item $(f \pm g) m = fm \pm gm$
301 \item $(fg) m = f(gm)$
302 \item $1_A m = m$
303 \end{enumerate}
304 \end{defn}
305
306 \pause
307
308 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.
309 }
310\end{frame}
311
312\begin{frame}{Kernel}
313 TODO
314
315 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]
316 Intuition: set of inputs that a function completely "erases", ie. they all get mapped to zero.
317 \end{tcolorbox}
318\end{frame}
319
320\end{mayberm}
321\end{comment}
322
323\section[Lattices]{Lattices}
324
325\begin{frame}{Lattices}
326 \begin{defn}[Lattice]
327 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$.
328
329 \pause
330 $B = \{b_1, \ldots, b_m\} \in \Rr^{n \times m}$ is the \emph{basis} of $\Ll$. We denote it $\Ll=\Ll(B)$.
331 \vspace*{-0.3cm}
332 $$\Ll(B) := B \cdot \Zz^n = \{ \sum_{i=1}^n c_i b_i ~|~ c_i \in \Zz^n \}$$
333 \end{defn}
334
335 \small
336 \pause
337 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]
338 \emph{Intuition: endless grid of dots where you can only move by taking whole-number
339 steps along a fixed set of directions.}
340 \end{tcolorbox}
341
342 \pause
343 Note: basis of a lattice are not unique.
344
345 \pause
346 Dimension of $\Ll$ is $n$, rank of $\Ll$ is $m$. Full-rank lattice: $m=n$.
347
348 \pause
349 In most cryptographic applications, $b_1, \ldots, b_n \in \Zz^n$, ie. $\Ll$ is an integer lattice.
350
351\end{frame}
352
353\begin{frame}{}
354 \includegraphics[width=9.5cm]{./2d-lattice}
355\end{frame}
356
357\begin{frame}{}
358 \includegraphics[width=9.5cm]{./two_bases_lattice}
359\end{frame}
360
361\begin{frame}{Lattice properties}
362 a $n$-dimensional lattice $\Ll$ is
363 \begin{enumerate}[i.]
364 \item \emph{additive subgroup} of $\Rr^n$: $\Ll$ is the nonempty subset of $\Rr^n$ closed under vector addition (and subtraction),\\
365 $$\text{ie.}~ \forall x,y \in \Ll,~ -x, x+y \in \Ll$$
366 \item \emph{discrete}: every $x \in \Ll$ has a neighborhood in $\Rr^n$ in which $x$ is the only lattice point.
367 \end{enumerate}
368
369 \pause
370
371 \small{
372 \begin{defn}[\emph{minimum} of a lattice $\Ll$]
373 $$\lambda_1(\Ll) = min \{ ||x|| ~|~ x\in \Ll, x \neq 0 \}$$
374
375 \pause
376
377 \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.
378 $$\lambda_1(\Ll) \leq \lambda_2(\Ll) \leq \cdots \leq \lambda_n(\Ll)$$
379 \end{defn}
380 }
381\end{frame}
382
383\begin{frame}{}
384 % \includegraphics[width=9.5cm]{./cvp_sphere}
385 \includegraphics[width=9.5cm]{./sphere_packing} % TODO
386\end{frame}
387
388\begin{frame}{Lattice properties}
389 \vspace*{-0.2cm}
390 \small{
391 recall, a lattice:
392 \vspace*{-0.7cm}
393 $$\Ll(B) := B \cdot \Zz^n = \{ \sum_{i=1}^n z_i b_i ~|~ z_i \in \Zz^n \}$$
394
395 \pause
396 \vspace*{-0.4cm}
397 \begin{itemize}
398 \item $B = (b_1, \ldots, b_n) \in \Zz^{n \times n}$: basis matrix, finite description of the lattice (not the lattice itself)
399 \item the matrix-vector product $Bz$ maps an integer coordinate vector $z \in \Zz^n$ into a lattice point in $\Zz^n$.
400 \end{itemize}
401 }
402
403 \pause
404
405 \vspace*{-0.4cm}
406\begin{columns}[T]
407 \begin{column}{0.60\textwidth}
408
409 \small{
410 \begin{itemize}
411 \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
412 \begin{itemize}
413 \item the lattice $\Ll(B)$ is the invariant set of points
414 \item the basis $B$ is not unique
415 \end{itemize}
416
417 \vspace*{-0.3cm}
418 \pause
419 \end{itemize}
420 }
421
422 \end{column}
423
424 \begin{column}{0.40\textwidth}
425 \centering
426 \includegraphics[width=\linewidth]{./two_bases_lattice}
427 \end{column}
428\end{columns}
429
430 \pause
431 \begin{itemize}
432 \item $B \in \Zz^{n \times n}$, $n$ vectors, each with $n$ coordinates $\Longrightarrow$ requires $\mathcal{O}(n^2)$ integers.
433 \begin{itemize}
434 \item only if we could have some better lattice structure to represent the lattice with fewer entries...
435 \end{itemize}
436 \end{itemize}
437\end{frame}
438
439
440\begin{comment}
441\begin{frame}{q-ary lattice}
442 \vspace{-0.4cm}
443 a full-rank lattice is q-ary if $q \Zz^d \subseteq \Ll \subseteq \Zz^d$
444
445 $\Longrightarrow$ q-ary lattice is an infinite set of integer points, but membership depends only on the residue class modulo $q$
446 $$\text{ie. if}~ x \in \Ll, ~\text{then}~ x + qz \in \Ll ~\forall z \in \Zz^d$$
447
448 \pause
449
450 Let $A \in \Zz^{n \times m}$ define the homomorphism
451 \begin{align*}
452 \psi_A: \Zz^m &\longrightarrow \Zz_q^n\\
453 z &\longmapsto Az \pmod q
454 \end{align*}
455
456 \pause
457
458 % image q-ary lattice:
459 % $$\Ll_q(A) = \{ y \in \Zz^n ~|~ y=Az \mod q ~\text{for some}~ z \in \Zz_q^m \}$$
460 %
461 % lattice generated by the rows of $A$.
462 % \pause
463
464 \vspace*{-0.5cm}
465 q-ary lattice:
466 $$\Ll_q^{\perp}(A) = ker(\psi_A) = \{ z \in \Zz^m ~|~ Az = 0 \mod q \}$$
467 contains all vectors that are orthogonal modulo $q$ to the rows of $A$.
468
469 % \scriptsize{
470 % The q-ary lattice generated by the rows of $A$:
471 % $$\Ll_q(A) = \{ y \in \Zz^m ~|~ y=A^Tz \mod q ~\text{for some}~ z \in \Zz_q^n \}$$
472 % }
473
474
475 \small{
476 \begin{tcolorbox}[colback=gray!15, colframe=gray!15] Intuition:
477 keep only the points that satisfy some modular rules. Since everything repeats every $q$ steps, the lattice has a structured and periodic shape, convenient in cryptography.
478 \\Linear algebra modulo $q$, but breaking it requires solving a hard lattice problem.
479 \end{tcolorbox}
480 }
481 % TODO why q-ary is better? prev.slide says O(n^2) without q-ary, how with q-ary?
482 % - modular takes less bits than full integer
483 % - usually A \in \Zz_1^{n \times m} with n<m
484 % - membership is extremely simple (Ax (mod q))
485 %
486 % Notation: \perp ddenotes that the vectors are orthogonal to the rows of \(A\) modulo \(q\), i.e. they lie in the modular kernel.
487\end{frame}
488\end{comment}
489
490\begin{frame}{Polynomial rings}
491 \small{
492 % \begin{itemize}
493 % \item the NTRU paper (1996) was one of the first lattice-based cryptography using polynomial quotient rings, which later same general idea was ported over Ajtai/SIS-style and LWE, leading to Ring-SIS, Ring-LWE, and later on Module-LWE, etc.
494 %
495 % \item Polynomial rings: represent an $n$-dimensional vector
496 % $(a_0,\ldots,a_{n-1}) \in \Zz_q^n$ as a single ring element (polynomial)
497 % $$a(X) = a_0 + a_1 X + \cdots + a_{n-1} X^{n-1} \in \Zz_q[X]/(X^n+1)$$
498 % \end{itemize}
499 NTRU paper (1996), first usage of polynomial quotient rings for lattice-based cryptography. Later ported over Ajtai/SIS-style and LWE, leading to Ring-SIS, Ring-LWE, and later on Module-LWE, etc.
500
501 $$
502 (a_0,\ldots,a_{n-1}) \in \Zz_q^n ~~\Longleftrightarrow~~
503 a(X) = a_0 + \cdots + a_{n-1} X^{n-1} \in \Zz_q[X]/(X^n+1)
504 $$
505 }
506
507 \pause
508 \small{
509 \begin{itemize}
510 \item[-] Addition:
511 $a(x) + b(x) = \sum_{i=1}^d (a_i + b_i) X^i$
512 \pause
513 \item[-] Multiplication:
514 $$a(X) \cdot b(X)
515 = \left(
516 \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}
517 a_i b_j X^{i+j}
518 \right)
519 \in \Zz_q[X]/(X^n+1)$$
520
521 \hspace*{4em}Since $X^n=-1$ then $X^{n+k} = X^n \cdot X^k= -1 \cdot X^k = -X^k$\\
522 $\Longrightarrow~ \mathcal{O}(n^2)$ naively, $\mathcal{O}(n \log n)$ using NTT.
523 \end{itemize}
524 }
525\end{frame}
526
527
528\section[Hard problems]{Hard problems}
529
530\begin{frame}{Incomplete Timeline}
531 \begin{timeline}
532 1978 \quad Knapsack cryptosystems attacked using lattice methods
533
534 1996 \quad NTRU encryption, & Ajtai
535
536 2005 \quad Learning With Errors (LWE)
537
538 2008 \quad Practical secure lattice-signature schemes
539
540 2009 \quad Fully Homomorphic Encryption (FHE)
541
542 2016 \quad NewHope (Ring-LWE KEM)
543
544 2017 \quad Kyber (Module-LWE based), & Dilithium (Module-LWE & Module-SIS based), & Falcon (NTRU based)
545
546 2020s \quad standardiszation: ML-KEM (Kyber) and ML-DSA (Dilithium)
547 \end{timeline}
548\end{frame}
549
550
551\begin{frame}{Hard problems in lattices - SVP and CVP}
552 \small{
553 \begin{itemize}
554 \item In elliptic curve cryptography, we rely on the hardness of the Discrete Logarithm problem:\\
555 \begin{adjustwidth}{2em}{0pt}
556 given publicly known $g, p \in \mathbb{G}$, find privately known $x \in \Zz$ such that $p=g^x$.
557 \end{adjustwidth}
558
559 \item In lattice based cryptography, we rely on problems related to finding short vectors in the lattice.
560 \end{itemize}
561 }
562
563 \pause
564 \begin{defn}[SVP (Shortest Vector Problem)]
565 find a shortest non-zero vector $x \in \Ll$, ie. that minimizes the Euclidean norm $||x||$, that is $\lambda_1(\Ll)=||x||$.
566 \end{defn}
567
568 \colorbox{gray!20}{Intuition:
569 find the shortest possible jump from the origin to another dot
570 }
571
572 \pause
573 \begin{defn}[CVP (Closest Vector Problem)]
574 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||$.
575 \end{defn}
576
577 \colorbox{gray!20}{Intuition:
578 find the grid dot that is closest to a given point (off the grid)
579 }
580
581\end{frame}
582
583\begin{frame}
584 \includegraphics[height=\paperheight]{./cvp_2d}
585\end{frame}
586\begin{frame}
587 \includegraphics[width=9.5cm]{./cvp_sphere}
588\end{frame}
589
590\begin{frame}{Why Lattices?}
591 \begin{itemize}
592 \item LLL algorithm is used to solve SVP and CVP.
593 \begin{itemize}
594 \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.
595 % \colorbox{gray!20}{Intuition:
596 \begin{tcolorbox}[colback=gray!15, colframe=gray!15] Intuition:
597 make the lattice basis less skewed. Same grid of points, just a simpler
598 basis. We don't change the lattice, we change the coordinate system used to
599 describe it. $\longrightarrow$ easier to solve SVP and CVP.
600 % }
601 \end{tcolorbox}
602 \item improvement: BKZ reduction algorithm
603 \end{itemize}
604
605 \item Both SVP and CVP become computationally difficult (NP hard) as the
606 lattice dimension $n$ grows (even on quantum computers)
607 \end{itemize}
608\end{frame}
609
610
611\begin{comment}
612\begin{frame}{NTRU}
613
614 \begin{defn}[NTRU key recovery problem]
615 Given $h(x)$, find ternary polynomials $f, g \in \mathcal{T}$ satisfying
616 $$f(x) \cdot h(x) = g(x) \pmod q \in R_q$$
617 Where $R_q = \Zz_q[X]/(X^n-1)$.
618 \end{defn}
619
620 \pause
621 \begin{itemize}
622 \item 1998, was first scheme using polynomial rings, which latter where approached as agebraically structured lattices
623 \begin{itemize}
624 \item "lattice-based" bcs recovering the small secret polynomials can be formulated and attacked as a lattice problem
625 \item earlier lattice usage: in 1978, Knapsack cryptosystems targeted by lattice attacks
626 \end{itemize}
627 \item following the approach, in 2002, Micciano modified Ajtai's function to work over polynomial rings getting efficiency improvements
628 \end{itemize}
629\end{frame}
630\end{comment}
631
632% TODO diagrams of SVP, CVP, SIS
633
634\begin{frame}{Hard problems in lattices - SIS}
635\begin{columns}[c,onlytextwidth]
636\begin{column}{0.76\textwidth}
637 \begin{defn}[SIS (Short Integer Solution)]
638 given $q \in \Zz$ and matrix $A \in \Zz_q^{m \times n}$, find a non-zero short $z \in \Zz^n$ s.th.
639 $$A \cdot z = 0 \pmod q$$
640
641 \small{"short": $z \in \{\beta, \beta\}^n$ for some bound $\beta$, often $z \in \{-1, 0, 1 \}^n$.}
642 \end{defn}
643\end{column}
644\begin{column}{0.34\textwidth}
645 \pause
646 \includegraphics[width=\linewidth]{./sis-equation}
647\end{column}
648\end{columns}
649\vspace{0.2cm}
650
651 \pause
652 The set of all solutions to the SIS problem forms the (q-ary) lattice
653 $$\Lambda^{\perp}_q(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
654 where the SIS problem becomes almost the SVP for $\Lambda_q^{\perp}(A)$
655
656 \small{
657 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]Intuition:
658 find a short nonzero vector (not the shortest as in SVP) in the lattice $\Lambda^{\perp}_q(A)$
659 \end{tcolorbox}
660 }
661
662\end{frame}
663
664\begin{comment}
665\begin{frame}{}
666 \begin{defn}[Ring SIS (Ring Short Integer Solution)]
667 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
668
669 $$A z = \sum_i a_i \cdot z_i = 0 \in R_q$$
670 \end{defn}
671
672 \pause
673 \begin{defn}[MSIS (Module Short Integer Solution)]
674 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
675
676 $$A z = 0 \in R_q^m$$
677 $$ie.~ \sum_i a_{ij} \cdot z_j = 0 \in R_q, ~~for~ i=1, \ldots, m$$
678 \end{defn}
679
680 \pause
681 Notice that Module-SIS is a Ring-SIS with $rank=1$ ($m=1$).
682\end{frame}
683\end{comment}
684
685\begin{frame}{On the shortness of $z$}
686 % TODO maybe rm these remarks
687 \begin{itemize}
688 \item without $||z|| \leq \beta$, it is easy to find a solution via \emph{Gaussian elimination}.
689 \item $\beta < q$, because otherwise $z=(q, 0, \ldots, 0) \in R^m$ would always be a valid solution.
690 \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$.
691 \end{itemize}
692
693 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]
694 TL;DR: $z$ must be small enough for security reasons.
695 \end{tcolorbox}
696
697 Again: overall when doing lattice-based cryptography, we will be interested into keeping the values \emph{short}, aka. of small norm.
698 \pause
699 (example of decomposing values to keep small norms when doing operations in
700 cryptographic protocols (eg. in LaBRADOR))
701\end{frame}
702
703\begin{frame}{Hard problems - LWE}
704\begin{columns}[c,onlytextwidth]
705\begin{column}{0.76\textwidth}
706 \begin{defn}[LWE (Learning With Errors)]
707 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
708 $$b = As +e \pmod q \in \Zz_q^m$$
709
710 Given the pair $(A, b)$, the goal is to recover $s$.
711 \end{defn}
712\end{column}
713\begin{column}{0.34\textwidth}
714 \pause
715 \includegraphics[width=\linewidth]{./lwe-equation}
716\end{column}
717\end{columns}
718
719 \vspace{0.2cm}
720
721 \pause
722 \small
723 Search-LWE \& Decisional-LWE problems.
724
725 \pause
726 For LWE samples, vector $b$ is relatively close to exactly one vector in the LWE lattice:
727 \begin{align*}
728 \Lambda_q(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
729 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
730 \end{align*}
731
732 \pause
733
734 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).
735
736\end{frame}
737
738\begin{frame}
739 \centering
740 \includegraphics[width=8.5cm]{./lwe-sphere-error}
741\end{frame}
742
743\begin{frame}{Plain - Module - Ring}
744 $$R_q = \mathbb{Z}_q[x]/(x^n+1)$$
745
746 \small{
747 $$
748 \begin{array}{c|c|c}
749 \text{Assumption} &
750 \text{Public linear relation} &
751 \text{Underlying algebra}
752 \\ \hline
753 \text{Plain LWE} &
754 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
755 A \in \mathbb{Z}_q^{m \times n}
756 \\[0.5em]
757 \text{Module-LWE} &
758 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
759 A \in R_q^{k \times k},
760 \quad
761 \mathbf{s},\mathbf{e},\mathbf{b} \in R_q^k
762 \\[0.5em]
763 \text{Ring-LWE} &
764 b = as + e \pmod q &
765 a,s,e,b \in R_q
766 \end{array}
767 $$
768 $$
769 \begin{array}{c|c|c}
770 \text{Assumption} &
771 \text{Public linear relation} &
772 \text{Underlying algebra}
773 \\ \hline
774 \text{Plain SIS} &
775 A\mathbf{z} = \mathbf{0} \pmod q,
776 \quad
777 \mathbf{z} \neq \mathbf{0},
778 \quad
779 \|\mathbf{z}\| \text{ small} &
780 A \in \mathbb{Z}_q^{m \times n},
781 \quad
782 \mathbf{z} \in \mathbb{Z}^n
783 \\[0.8em]
784 \text{Module-SIS} &
785 A\mathbf{z} = \mathbf{0} \pmod q,
786 \quad
787 \mathbf{z} \neq \mathbf{0},
788 \quad
789 \|\mathbf{z}\| \text{ small} &
790 A \in R_q^{m \times n},
791 \quad
792 \mathbf{z} \in R^n
793 \\[0.8em]
794 \text{Ring-SIS} &
795 a z = 0 \pmod q,
796 \quad
797 z \neq 0,
798 \quad
799 \|z\| \text{ small} &
800 a \in R_q,
801 \quad
802 z \in R
803 \end{array}
804 $$
805}
806
807\end{frame}
808
809% TODO maybe remove dual lattices slide
810\begin{comment}
811\begin{mayberm}
812\begin{frame}{Dual lattices}
813 \small
814 SIS lattice:
815 $$\Ll^{\perp}(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
816
817 LWE lattice:
818 \begin{align*}
819 \Ll(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
820 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
821 \end{align*}
822
823
824 \pause
825 Dual of a lattice:
826 $$\Ll^* = \{ y \in \Rr^m ~|~ \langle y, x \rangle \in \Zz ~\forall~ x \in \Ll \}$$
827
828 ie. all vectors that measure lattice points with integers.
829
830 \vspace{0.5cm}
831 \pause
832 SIS lattices and LWE lattices are dual to each other
833 $$\Ll(A) = q \Ll^{\perp *}(A) ~~~\text{ie.}~~~ \frac{1}{q} \Ll(A) = \Ll^{\perp *}(A)$$
834
835 \small{(duality is interesting, because it lets security proofs transfer geometric properties)}
836
837 % TODO add intuition explainer on dual lattices
838 % TODO fix fitting everything
839 \scriptsize{
840 \begin{tcolorbox}[colback=gray!15, colframe=gray!15]Intuition:
841 A lattice tells you where points are allowed to sit; the dual lattice tells you which periodic directions “fit perfectly” with that grid.
842 Original lattice describes the spacing of points, while the dual lattice describes the spacing of compatible frequencies. Wide spacing in the original means tighter spacing in the dual, and vice versa.
843 \end{tcolorbox}}
844\end{frame}
845\end{mayberm}
846\end{comment}
847
848\begin{comment}
849\begin{mayberm}
850\begin{frame}
851 \hspace*{-0.8cm}
852 \includegraphics[width=\paperwidth]{./lattice_examples}
853\end{frame}
854\end{mayberm}
855\end{comment}
856
857
858\section[Some cryptography]{Some cryptography}
859
860% \begin{frame}{Ajtai commitments}
861%
862% \begin{defn}[Ajtai commitemnt]
863% 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
864% $$c = A r + G x \pmod q \in \Zz_q^n$$
865% \end{defn}
866%
867% Observe that this is closely related to the SIS problem ($Az=0 \pmod q$), and it relies on its hardness.
868%
869%
870% \end{frame}
871
872\begin{frame}{Lattice-based cryptography}
873 Some examples
874 \begin{itemize}
875 \item ML-KEM (Kyber): Key Encapulation Mechanism. ie. Alice encapsulates a (symmetric) key using Bob's public key
876 \item ML-DSA (Dilithium): signature scheme
877 \item FN-DSA (Falcon): signature scheme, based on NTRU
878 \item LaBRADOR: SNARK scheme
879 \item FHE (BFV, BGV, CKKS, TFHE)
880 \end{itemize}
881
882 \vspace{1.0cm}
883 \pause
884 Let's do a quick overview of ML-DSA (Dilithium)...
885\end{frame}
886
887% \begin{mayberm}
888% \begin{frame}{ML-KEM (Kyber)}
889% \scriptsize{
890% \begin{itemize}
891% \item KEM = Key Encapsulation Mechanism
892% \begin{itemize}
893% \item Alice encapsulates a (symmetric) key using Bob's public key
894% \end{itemize}
895% \item based on Module-LWE
896% \end{itemize}
897% }
898%
899% $$R_q=\mathbb{Z}_q[X]/(X^{256}+1), A\in R_q^{k\times k}$$
900%
901% \textbf{Key generation:}
902% $$
903% \mathbf{s},\mathbf{e}\leftarrow\chi^k,
904% \qquad
905% \mathbf{t}=A\mathbf{s}+\mathbf{e}
906% $$
907%
908% $$
909% pk=(A,\mathbf{t}),\qquad sk=\mathbf{s}
910% $$
911%
912% \textbf{Encapsulation:}
913% $$
914% \mathbf{u}=A^T\mathbf{r}+\mathbf{e}_1,
915% \qquad
916% v=\mathbf{t}^T\mathbf{r}+e_2+\operatorname{Encode}(m)
917% $$
918%
919% $$
920% c=(\mathbf{u},v),
921% \qquad
922% K=\operatorname{KDF}(m,c)
923% $$
924%
925% \textbf{Decapsulation:}
926% $$
927% m'=\operatorname{Decode}\!\left(v-\mathbf{s}^T\mathbf{u}\right)
928% $$
929%
930% Since
931% $$
932% v-\mathbf{s}^T\mathbf{u}
933% =
934% \operatorname{Encode}(m)
935% +\mathbf{e}^T\mathbf{r}
936% +e_2-\mathbf{s}^T\mathbf{e}_1,
937% $$
938% the message is recovered up to small noise.
939% \end{frame}
940% \end{mayberm}
941
942
943% \begin{frame}{Recall: Sigma protocol over elliptic curve}
944% \begin{center}
945% \begin{sequencediagram}
946% \newinst[1]{a}{Alice}
947% \newinst[3]{b}{Bob}
948% \mess[0]{a}{$R$}{b}
949% \mess[2]{b}{$c$}{a}
950% \mess[2]{a}{$z$}{b}
951% \mess[0]{b}{$ok$}{a}
952% \end{sequencediagram}
953% \end{center}
954% \end{frame}
955
956
957\begin{frame}{Recall: Sigma protocol over elliptic curve}
958
959\scriptsize
960
961\vspace*{-1.0cm}
962$$
963G \in E(\mathbb{F}_p),
964~~
965\operatorname{ord}(G)=q,
966~~
967\text{pub key}~ Y=xG
968$$
969
970\begin{columns}[c,onlytextwidth]
971
972\begin{column}{0.27\textwidth}
973
974\vspace*{-1.8cm}
975$$\textcolor{red}{x} \in \mathbb{Z}_q, ~ \textcolor{blue}{Y}=\textcolor{red}{x}G$$
976$$\textcolor{red}{r} \leftarrow \mathbb{Z}_q, ~~ \textcolor{blue}{R}=\textcolor{red}{r}G$$
977
978$$\textcolor{blue}{z} =\textcolor{red}{r}+c\textcolor{red}{x} \pmod q$$
979
980\end{column}
981
982
983\begin{column}{0.35\textwidth}
984
985\hspace*{-1.0cm}
986\scalebox{0.80}{
987\begin{sequencediagram}
988 \newinst[1]{a}{Prover}
989 \newinst[2]{b}{Verifier}
990
991 % \mess[0]{a}{$\textcolor{blue}{R}$}{b}
992 \mess[0]{a}{$R$}{b}
993 \mess[2]{b}{$c$}{a}
994 % \mess[2]{a}{$\textcolor{blue}{z}$}{b}
995 \mess[2]{a}{$z$}{b}
996 \mess[0]{b}{$ok$}{a}
997\end{sequencediagram}
998}
999
1000\end{column}
1001
1002\begin{column}{0.33\textwidth}
1003
1004
1005
1006% Move only this equation down, without affecting the frame layout
1007\raisebox{-1.4cm}[0pt][0pt]{%
1008 \makebox[\linewidth][c]{$c \leftarrow \mathbb{Z}_q$}%
1009}
1010
1011
1012\vspace*{2.5cm}
1013$$\textcolor{blue}{z}G \stackrel{?}{=} \textcolor{blue}{R}+c\textcolor{blue}{Y}$$
1014
1015indeed,
1016\begin{align*}
1017 \textcolor{blue}{z}G &= (\textcolor{red}{r}+c\textcolor{red}{x})G \\
1018 &= \textcolor{red}{r}G+c(\textcolor{red}{x}G) \\
1019 &= \textcolor{blue}{R}+c\textcolor{blue}{Y}
1020\end{align*}
1021
1022\end{column}
1023\end{columns}
1024\end{frame}
1025
1026\begin{frame}{ML-DSA signatures}
1027\scriptsize
1028
1029$$R_q = \mathbb{Z}_q[X]/(X^n+1)$$
1030
1031\begin{columns}[c,onlytextwidth]
1032
1033\begin{column}{0.27\textwidth}
1034\vspace*{-1.8cm}
1035$$\textcolor{red}{s_1} \leftarrow S^\ell,~ \textcolor{red}{s_2} \leftarrow S^k$$
1036 $$\textcolor{blue}{A} \leftarrow R_q^{k\times\ell},~ \textcolor{blue}{t} = \textcolor{blue}{A}s_1+s_2$$
1037 $$\textcolor{red}{y_1}\leftarrow Y^\ell,~ \textcolor{red}{y_2}\leftarrow Y^k$$
1038 $$\textcolor{blue}{w} = \textcolor{blue}{A}\textcolor{red}{y_1}+\textcolor{red}{y_2}$$
1039
1040 $$\textcolor{blue}{z_1}=\textcolor{red}{y_1}+c\textcolor{red}{s_1},~ \textcolor{blue}{z_2}=\textcolor{red}{y_2}+c\textcolor{red}{s_2}$$
1041 Reject if $z_1,z_2$ are not short.
1042\end{column}
1043
1044
1045\begin{column}{0.35\textwidth}
1046
1047\hspace*{-1.0cm}
1048\scalebox{0.80}{
1049\begin{sequencediagram}
1050 \newinst[1]{a}{Prover}
1051 \newinst[2]{b}{Verifier}
1052
1053 \mess[0]{a}{$w$}{b}
1054 \node[anchor=west] at (6.0,-1.5) {
1055 $c\leftarrow C$
1056 (in practice, $c = H(M ||w)$)
1057 };
1058 \mess[2]{b}{$c$}{a}
1059 \mess[2]{a}{$z_1,z_2$}{b}
1060 % \node[anchor=west] at (7.0,-5.0) {
1061 % $w' = Az_1 + z_2 - ct$
1062 % };
1063 \mess[0]{b}{$ok$}{a}
1064\end{sequencediagram}
1065}
1066
1067\end{column}
1068
1069\begin{column}{0.33\textwidth}
1070
1071% Move only this equation down, without affecting the frame layout
1072% \raisebox{-1.4cm}[0pt][0pt]{%
1073% \makebox[\linewidth][c]{
1074% \vspace*{2.5cm}
1075 % $c\leftarrow C$\\
1076 % \scriptsize{
1077 % (in practice, $c = H(M ||w)$)
1078 % }
1079% }%
1080% }
1081
1082
1083\vspace*{2.5cm}
1084 \begin{align*}
1085 \textcolor{blue}{w} &\stackrel{?}{=} \textcolor{blue}{Az_1}+\textcolor{blue}{z_2}-c \textcolor{blue}{t} \\
1086 &\text{indeed,}\\
1087 &= \textcolor{blue}{A}(\textcolor{red}{y_1}+c\textcolor{red}{s_1})+(\textcolor{red}{y_2}+c\textcolor{red}{s_2}) \\
1088 &~-c(\textcolor{blue}{A} \textcolor{red}{s_1}+\textcolor{red}{s_2}) \\
1089 =\textcolor{blue}{A} &\textcolor{red}{y_1} +c \textcolor{blue}{A} \textcolor{red}{s_1} +\textcolor{red}{y_2} +c \textcolor{red}{s_2}-c\textcolor{blue}{A} \textcolor{red}{s_1}-c\textcolor{red}{s_2}\\
1090 &= \textcolor{blue}{A} \textcolor{red}{y_1}+\textcolor{red}{y_2} = \textcolor{blue}{w}
1091 \end{align*}
1092 Accept if $z_1,z_2$ are short.
1093
1094\end{column}
1095\end{columns}
1096\end{frame}
1097
1098
1099
1100% \begin{frame}{ML-DSA signatures}
1101% %%%
1102% \vspace{-0.5cm}
1103%
1104%
1105% \scriptsize
1106%
1107% $$
1108% R_q = \mathbb{Z}_q[X]/(X^n+1)
1109% $$
1110%
1111% \vspace{-0.4cm}
1112%
1113% \hspace*{-0.7cm}
1114% \begin{tikzpicture}[
1115% >=Latex,
1116% every node/.style={font=\scriptsize},
1117% ]
1118%
1119% % =========================================================
1120% % Headers
1121%
1122% \node[anchor=west] at (0,0)
1123% {\textbf{Signer / Prover}};
1124%
1125% \node[anchor=west] at (8.3,0)
1126% {\textbf{Verifier}};
1127%
1128% % =========================================================
1129% % Keys
1130%
1131% \node[anchor=west, align=left] at (0,-0.8) {
1132% $s_1 \leftarrow S^\ell,~ s_2 \leftarrow S^k$
1133% \\[1mm]
1134% Public:\\
1135% $A \leftarrow R_q^{k\times\ell},~ t = As_1+s_2$
1136% };
1137%
1138% \node[anchor=west, align=left] at (8.3,-1.4) {
1139% Public key:\\
1140% $(A,t)$
1141% };
1142%
1143% \draw[->]
1144% (4.9,-1.5)
1145% --
1146% node[above] {$pk=(A,t)$}
1147% (8.0,-1.5);
1148%
1149% % =========================================================
1150% % Commitment
1151%
1152% \node[anchor=west, align=left] at (0,-2.35) {
1153% Sample short vectors:\\
1154% $y_1\leftarrow Y^\ell,~
1155% y_2\leftarrow Y^k$
1156% \\[1mm]
1157% Compute:\\
1158% $w = Ay_1+y_2$
1159% };
1160%
1161% \draw[->]
1162% (4.9,-3.05)
1163% --
1164% node[above] {$w$}
1165% (8.0,-3.05);
1166%
1167% % =========================================================
1168% % Challenge
1169%
1170% \node[anchor=west, align=left] at (8.3,-3.25) {
1171% $c\leftarrow C$\\
1172% \scriptsize{
1173% (in practice, $c = H(M ||w)$)
1174% }
1175% };
1176%
1177% \draw[<-]
1178% (4.9,-3.9)
1179% --
1180% node[above] {$c$}
1181% (8.0,-3.9);
1182%
1183% % =========================================================
1184% % Response
1185%
1186% \node[anchor=west, align=left] at (0,-4.45) {
1187% Compute:\\
1188% $z_1=y_1+cs_1,~
1189% z_2=y_2+cs_2$
1190% \\[1mm]
1191% Reject if $z_1,z_2$ are not short.
1192% };
1193%
1194% \draw[->]
1195% (4.9,-5.55)
1196% --
1197% node[above] {$z_1,z_2$}
1198% (8.0,-5.55);
1199%
1200% % =========================================================
1201% % Verification
1202%
1203% \node[anchor=west, align=left] at (8.3,-6.0) {
1204% Reconstruct:\\[1mm]
1205% $\begin{aligned}
1206% w'
1207% &= Az_1+z_2-ct \\
1208% &= A(y_1+cs_1)+(y_2+cs_2) \\
1209% &\qquad-c(As_1+s_2) \\
1210% &= Ay_1+y_2 \stackrel{?}{=} w
1211% \end{aligned}$
1212% \\[1mm]
1213% Accept if $z_1,z_2$ are short.
1214% };
1215%
1216% \end{tikzpicture}
1217%
1218%
1219% %%%
1220%
1221% \end{frame}
1222
1223\begin{comment}
1224\begin{mayberm}
1225\begin{frame}{Falcon signatures}
1226\end{frame}
1227
1228
1229\begin{frame}{LaBRADOR SNARK}
1230\end{frame}
1231\end{mayberm}
1232\end{comment}
1233
1234\begin{frame}{Benchmarks}
1235 % TODO review benchmarks
1236
1237 \centering
1238 % \small{
1239 \setlength{\tabcolsep}{4pt}
1240 \renewcommand{\arraystretch}{1.10}
1241
1242 \textbf{Digital signatures}
1243 \vspace{0.05cm}
1244
1245 \resizebox{0.88\textwidth}{!}{%
1246 \begin{tabular}{llll}
1247 \toprule
1248 \textbf{Scheme} &
1249 \textbf{Assumption} &
1250 \textbf{Public key size} &
1251 \textbf{Signature size} \\
1252 \midrule
1253
1254 ECDSA-secp256k1
1255 & elliptic curves
1256 & $33$ B
1257 & $64$ B \\
1258
1259 Falcon-512
1260 & NTRU lattice
1261 & $897$ B
1262 & $666$ B \\
1263
1264 ML-DSA-44
1265 & Module-LWE / Module-SIS
1266 & $1.31$ KB
1267 & $2.42$ KB \\
1268
1269 XMSS-SHA2-10-256
1270 & hash based, stateful*
1271 & $64$ B
1272 & $2.50$ KB \\
1273
1274 SLH-DSA-128s (SPHINCS+)
1275 & hash based, stateless
1276 & $32$ B
1277 & $7.86$ KB \\
1278
1279 \bottomrule
1280 \end{tabular}%
1281 }
1282
1283 \vspace{0.20cm}
1284
1285 \textbf{SNARKs / STARKs}
1286 \vspace{0.05cm}
1287
1288 \resizebox{0.87\textwidth}{!}{%
1289 \begin{tabular}{lll}
1290 \toprule
1291 \textbf{Scheme} &
1292 \textbf{Assumption / technique} &
1293 \textbf{Proof size} \\
1294 \midrule
1295
1296 Groth16
1297 & pairings / elliptic curves
1298 & $128$ B \\
1299
1300 LaBRADOR
1301 & Module-SIS
1302 & $50$--$60$ KB \\
1303
1304 Flock
1305 & binary fields + coding theory
1306 & $200$--$400$ KiB \\
1307
1308 Binius64
1309 & binary fields + sumcheck
1310 & $200$--$500$ KiB \\
1311
1312 Plonky2 & Plonk + FRI
1313 & $40$--$200$ KB \\
1314
1315 Plonky3 / FRI-STARK
1316 & polynomial IOP + FRI
1317 & $1$--$3$ MiB \\
1318
1319 \bottomrule
1320 \end{tabular}
1321 }
1322
1323 \vspace*{0.5cm}
1324 \tiny{\emph{*stateful: signer needs to keep a state, keeping track of the leaves already used. Fine for validator nodes, potential trouble for wallets.}}
1325\end{frame}
1326
1327
1328\section[Takeaways]{Takeaways}
1329
1330{
1331% \setbeamersize{text margin left=0.1cm,text margin right=0.1cm}
1332\setlength{\leftmargini}{0.2em}
1333\setlength{\leftmarginii}{1.2em}
1334
1335\begin{frame}{}
1336 \small
1337 \textbf{Takeaways}
1338 % \vspace*{-0.2cm}
1339
1340 \begin{itemize}
1341 \item quantum thread forces us to prepare for it. Most companies are already preparing for migration to post-quantum
1342 \pause
1343 \item no tool (scheme) for all use cases (eg. Ethereum validators vs wallets)
1344 \pause
1345 \item lattice-based cryptography:
1346
1347 \scriptsize{
1348 \begin{itemize}
1349 \item not a single assumption on all schemes: NTRU, R-SIS, M-SIS, R-LWE
1350 \item actual operations (implementation) are over polynomial rings
1351 % \item smaller proofs and keys than hash-based
1352 \item often significantly smaller signatures/proofs than hash-based alternatives, at the cost of more algebraic complexity
1353 \item often we're interested in 'short' values $\longrightarrow$ typical trick: decompose bigger values before operate on them
1354 \end{itemize}
1355 }
1356 \small
1357
1358 \pause
1359 \item what to read from here
1360 \begin{itemize}
1361 \item \emph{A Decade of Lattice Cryptography}, Chris Peikert \href{https://eprint.iacr.org/2015/939}{https://eprint.iacr.org/2015/939}
1362 \item \emph{A gentle introduction to lattice-based cryptography}, Alfred Menezes \href{https://eprint.iacr.org/2026/1098}{https://eprint.iacr.org/2026/1098}
1363 \end{itemize}
1364 \end{itemize}
1365
1366 \vspace{0.4cm}
1367 \centering
1368 % -\\
1369 \href{https://arnaucube.com}{arnaucube.com}\\
1370 \href{https://x.com/arnaucube}{$@$arnaucube}
1371\end{frame}
1372}
1373
1374
1375\end{document}