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{ {./} }
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\begin{frame}{Motivation}
84 \begin{itemize}
85 \item till now most cryptography relied on hardness of finding prime factors or finding the discrete logarithm, ie. RSA, Elliptic Curves, etc
86 \item Shor's algorithm suggests that factorization can be done in polynomial time (on quantum computers).\\
87 \small{
88 $\rightarrow$ given an odd composite $n \in \Zz$, find $d \in \Zz$, such that $1< d <n$ and $d|n$.
89 }
90 \end{itemize}
91\end{frame}
92
93\begin{frame}{Status of the ecosystem}
94 \begin{itemize}
95 \item isogenesis based
96 \item hash based
97 \item codes based
98 \item lattice based
99 \item multivariate based
100 \end{itemize}
101 TODO
102\end{frame}
103
104\begin{frame}{Motivation}
105 \begin{itemize}
106 \item Ethereum, is going with hash-based signatures for the validators.
107 \begin{itemize}
108 \item aggregation through SNARK proofs (eg. binius, flock, etc)
109 \item each slot a different XMSS leaf
110 \item the most conservative choice in terms of security
111 \end{itemize}
112 \item hash-based simpler to implement, less potential errors. Whereas lattice-based have more subtelties
113 \item hash-based schemes don't have much algebraic structure
114 \begin{itemize}
115 \item good for less attacks, not so fun to build stuff with
116 \item eg. elliptic curves have algebraic structure, allows for signature aggregation, thresholds, etc
117 \end{itemize}
118 \item lattice-based schemes have smaller proofs, signatures and public keys
119 \end{itemize}
120\end{frame}
121
122\section[Preliminaries]{Preliminaries}
123
124\begin{frame}{Rings}
125 \vspace*{-0.5cm}
126 \small{
127 \begin{defn}[Ring]
128 A set $A$ with operations called \emph{addition} and \emph{multiplication} which satisfy the following axioms:
129 \begin{enumerate}[i.]
130 \item $A$ with addition alone is an abelian group.
131 \item Multiplication is associative.
132 \item Multiplication is distributive over addition. That is, $\forall a,b,c \in A$,
133 $$a(b+c) = ab + ac$$
134 $$(b+c)a = ba + ca$$
135 \end{enumerate}
136 \end{defn}
137
138 \pause
139 Remark: a field is a ring with inverse.
140
141 \pause
142 \begin{defn}[Ideal]
143 $I \subset R$ ($R$ ring) such that $0 \in I$ and $\forall x \in I,~ r \in R,~ xr, rx \in I$.\\
144 \hspace*{2em} ie. $I$ absorbs products in $R$.
145 \end{defn}
146
147 \pause
148 Eg: Ring $\Zz=\{\ldots, -2, -1, 0, 1, 2, 3, \ldots \}$, Ideal $n \Zz= \{n k ~|~ k \in \Zz \}$ for fixed $n \in \Zz$.
149 }
150\end{frame}
151
152
153\begin{frame}{Vector spaces}
154 % vector space
155 % norm of a vector
156 % linear independent
157 % span
158 % basis
159 % rank: number of basis vectors / maximum number of linearly independent columns / maximum number of linearly independent rows
160 % some diagram
161
162
163 \begin{defn}[Vector space]
164 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
165
166 \begin{itemize}
167 \item $V$ with vector addition is an abelian group
168 \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:
169 $\forall k, l \in F,~\overrightarrow{a},\overrightarrow{b} \in V$
170 \begin{enumerate}[i.]
171 \item $k(\overrightarrow{a} + \overrightarrow{b}) = k\overrightarrow{a} + k\overrightarrow{b}$
172 \item $(k + l)\overrightarrow{a} = k\overrightarrow{a} + k\overrightarrow{b}$
173 \item $k(l\overrightarrow{a}) = (kl)\overrightarrow{a}$
174 \item $1 \overrightarrow{a} = \overrightarrow{a}$
175 \end{enumerate}
176 \end{itemize}
177 \end{defn}
178
179 \begin{itemize}
180 \item basis: set of vectors that \emph{span} the vector space
181 % TODO WIP
182 \end{itemize}
183\end{frame}
184
185
186\begin{frame}{Modules}
187 \small{
188
189 \begin{defn}[Module]
190 Let $A$ be a ring. An $A$-module is an Abelian group $M$ with a multiplication
191 map
192 \begin{align*}
193 A \times M &\longrightarrow M\\
194 (f, m) &\longmapsto fm
195 \end{align*}
196 satisfying $\forall~ f,g \in A,~~ m, n \in M$.
197 \begin{enumerate}[i.]
198 \item $f(m \pm n)=fm \pm fn$
199 \item $(f \pm g) m = fm \pm gm$
200 \item $(fg) m = f(gm)$
201 \item $1_A m = m$
202 \end{enumerate}
203 \end{defn}
204
205 \pause
206
207 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.
208 }
209\end{frame}
210
211\section[Lattices]{Lattices}
212
213\begin{frame}{Lattices}
214 \begin{defn}[Lattice]
215 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$.
216
217 \pause
218 $B = b_1, \ldots, b_m \in \Rr^n$ is the \emph{basis} of $\Ll$. We denote it $\Ll=\Ll(B)$.
219
220 $$\Ll(B) := B \cdot \Rr^n = \{ \sum_{i=1}^n c_i b_i ~|~ c_i \in \Rr^n \}$$
221 \end{defn}
222
223 \pause
224 Note: basis of a lattice are not unique.
225
226 \pause
227 Dimension of $\Ll$ is $n$, rank of $\Ll$ is $m$. Full-rank lattice: $m=n$.
228
229 \pause
230 In most cryptographic applications, $b_1, \ldots, b_n \in \Zz^n$, ie. $\Ll$ is an integer lattice.
231
232\end{frame}
233
234\begin{frame}{}
235 \includegraphics[width=9.5cm]{./2d-lattice}
236\end{frame}
237
238\begin{frame}{Lattice properties}
239 a $n$-dimensional lattice $\Ll$ is
240 \begin{enumerate}[i.]
241 \item \emph{additive subgroup} of $\Rr^n$: $\Ll$ is the nonempty subset of $\Rr^n$ closed under vector addition (and substraction),\\
242 $$\text{ie.}~ \forall x,y \in \Ll,~ -x, x+y \in \Ll$$
243 \item \emph{discrete}: every $x \in \Ll$ has a neighborhood in $\Rr^n$ in which $x$ is the only lattice point.
244 \end{enumerate}
245
246 \pause
247
248 \small{
249 \begin{defn}[\emph{minimum} of a lattice $\Ll$]
250 $$\lambda_1(\Ll) = min \{ ||x|| ~|~ x\in \Ll, x \neq 0 \}$$
251
252 \pause
253
254 \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.
255 $$\lambda_1(\Ll) \leq \lambda_2(\Ll) \leq \cdots \leq \lambda_n(\Ll)$$
256 \end{defn}
257 }
258\end{frame}
259
260\begin{frame}{Lattice properties}
261 recall, a lattice:
262 $$\Ll(B) := B \cdot \Zz^n = \{ \sum_{i=1}^n z_i b_i ~|~ z_i \in \Zz^n \}$$
263
264 \pause
265
266 \begin{itemize}
267 \item $B = (b_1, \ldots, b_n) \in \Zz^{n \times n}$: basis matrix, finite description of the lattice (not the lattice itself)
268 \item the matrix-vector product $Bz$ maps an integer coordinate vector $z \in \Zz^n$ into a lattice point in $\Zz^n$.
269
270 \pause
271 \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
272 \begin{itemize}
273 \item the lattice $\Ll(B)$ is the invariant set of points
274 \item the basis $B$ is not unique
275 \end{itemize}
276
277 \pause
278 \item $B \in \Zz^{n \times n}$, $n$ vectors, each with $n$ coordinates $\Longrightarrow$ requires $\mathcal{O}(n^2)$ integers.
279 \begin{itemize}
280 \item only if we could have some better lattice structure to represent the lattice with fewer entries...
281 \end{itemize}
282 \end{itemize}
283\end{frame}
284
285\begin{frame}{q-ary lattice}
286 a full-rank lattice is q-ary if $q \Zz^d \subseteq \Ll \subseteq \Zz^d$
287
288 $\Longrightarrow$ q-ary lattice is an infinite set of integer points, but membership depends only on the residue class modulo $q$
289 $$\text{ie. if}~ x \in \Ll, ~\text{then}~ x + qz \in \Ll ~\forall z \in \Zz^d$$
290
291 \pause
292
293 Let $A \in \Zz^{n \times m}$ define the homomorphism
294 \begin{align*}
295 \psi_A: \Zz^m &\longrightarrow \Zz_q^n\\
296 z &\longmapsto Az \pmod q
297 \end{align*}
298
299 \pause
300
301 % image q-ary lattice:
302 % $$\Ll_q(A) = \{ y \in \Zz^n ~|~ y=Az \mod q ~\text{for some}~ z \in \Zz_q^m \}$$
303 %
304 % lattice generated by the rows of $A$.
305 % \pause
306
307 q-ary lattice:
308 $$\Ll_q^{\perp}(A) = ker(\psi_A) = \{ z \in \Zz^m ~|~ Az = 0 \mod q \}$$
309 contains all vectors that are orthogonal modulo $q$ to the rows of $A$.
310
311 \scriptsize{
312 The q-ary lattice generated by the rows of $A$:
313 $$\Ll_q(A) = \{ y \in \Zz^m ~|~ y=A^Tz \mod q ~\text{for some}~ z \in \Zz_q^n \}$$
314 }
315
316 % TODO why q-ary is better? prev.slide says O(n^2) without q-ary, how with q-ary?
317\end{frame}
318
319\begin{frame}{Polynomial ring}
320 At the NTRU paper, they introduced the usage of polynomial rings, which latter was ported over Ajtai work and other lattices, now is the general approach.
321
322 TODO
323 NTRU lattices:
324 \begin{itemize}
325 \item
326 \end{itemize}
327
328 In $R = \Zz_q[X]/(X^n+1)$,
329 \begin{itemize}
330 \item Addition:
331 $$a(x) + b(x) = \sum_{i=1}^d (a_i + b_i) X^i$$
332 \item Multiplication:
333 $$a(x) \cdot b(x) = $$ TODO
334 \end{itemize}
335\end{frame}
336
337\section[Hard problems]{Hard problems}
338
339\begin{frame}{Timeline}
340 \begin{timeline}
341 1978 \quad Knapsack cryptosystems attacked using lattice methods
342
343 1996 \quad NTRU encryption
344
345 2005 \quad Learning With Errors (LWE)
346
347 2008 \quad Practical secure lattice-signature schemes
348
349 2009 \quad Fully Homomorphic Encryption (FHE)
350
351 2016 \quad NewHope (Ring-LWE KEM)
352
353 2017 \quad Kyber (Module-LWE based) & Dilithium (Module-LWE & Module-SIS based)
354
355 2020s \quad standardiszation: ML-KEM (Kyber) and ML-DSA (Dilithium)
356 \end{timeline}
357\end{frame}
358
359\begin{frame}{Hard problems in lattices}
360 \begin{itemize}
361 \item In elliptic curve cryptography, we rely on the hardness of the Discrete Logarithm problem:\\
362 \begin{adjustwidth}{2em}{0pt}
363 given publicly known $g, p \in \mathbb{G}$, find privately known $x \in \Zz$ such that $p=g^x$.
364 \end{adjustwidth}
365
366 \item In lattice based cryptography, we rely on problems related to finding short vectors in the lattice.
367 \end{itemize}
368
369 \pause
370 \begin{defn}[SVP (Shortest Vector Problem)]
371 find a shortest non-zero vector $x \in \Ll$, ie. that minimizes the Euclidean norm $||x||$, that is $\lambda_1(\Ll)=||x||$.
372 \end{defn}
373
374 \pause
375 \begin{defn}[CVP (Closest Vector Problem)]
376 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||$.
377 \end{defn}
378\end{frame}
379
380\begin{frame}{NTRU}
381
382 \begin{defn}[NTRU key recovery problem]
383 Given $h(x)$, find ternary polynomials $f, g \in \mathcal{T}$ satisfying
384 $$f(x) \cdot h(x) = g(x) \pmod q \in R_q$$
385 Where $R_q = \Zz_q[X]/(X^n-1)$.
386 \end{defn}
387
388 \pause
389 \begin{itemize}
390 \item 1998, was first scheme using polynomial rings, which latter where approached as agebraically structured lattices
391 \begin{itemize}
392 \item "lattice-based" bcs recovering the small secret polynomials can be formulated and attacked as a lattice problem
393 \item earlier lattice usage: in 1978, Knapsack cryptosystems targeted by lattice attacks
394 \end{itemize}
395 \item following the approach, in 2002, Micciano modified Ajtai's function to work over polynomial rings getting efficiency improvements
396 \end{itemize}
397\end{frame}
398
399% TODO diagrams of SVP, CVP, SIS
400
401\begin{frame}{Hard problems in lattices}
402 \begin{defn}[SIS (Short Integer Solution)]
403 given $q \in \Zz$ and matrix $A \in \Zz_q^{m \times n}$, find a non-zero short $z \in \Zz^n$ s.th.
404 $$A \cdot z = 0 \pmod q$$
405
406 \small{"short": $z \in \{B, B\}^n$ for some bound $B$, often $z \in \{-1, 0, 1 \}^n$.}
407 \end{defn}
408
409 \pause
410 The set of all solutions to the SIS problem forms the (q-ary) lattice
411 $$\Lambda^{\perp}_q(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
412 where the SIS problem becomes the SVP for $\Lambda_q^{\perp}(A)$
413
414 \begin{itemize}
415 \item LLL algorithm is used to solve SVP and CVP.
416
417 \item Both SVP and CVP become computationally difficult (NP hard*) as the lattice dimension $n$ grows.
418 \end{itemize}
419\end{frame}
420
421\begin{frame}{}
422 \begin{defn}[Ring SIS (Ring Short Integer Solution)]
423 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
424
425 $$A z = \sum_i a_i \cdot z_i = 0 \in R_q$$
426 \end{defn}
427
428 \pause
429 \begin{defn}[MSIS (Module Short Integer Solution)]
430 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
431
432 $$A z = 0 \in R_q^m$$
433 $$ie.~ \sum_i a_{ij} \cdot z_j = 0 \in R_q, ~~for~ i=1, \ldots, m$$
434 \end{defn}
435
436 \pause
437 Notice that Module-SIS is a Ring-SIS with $rank=1$ ($m=1$).
438\end{frame}
439
440\begin{frame}{}
441 % TODO maybe rm these remarks
442 \begin{itemize}
443 \item without $||z|| \leq \beta$, it is easy to find a solution via \emph{Gaussian elimination}.
444 \item $\beta < q$, because otherwise $z=(q, 0, \ldots, 0) \in R^m$ would always be a valid solution.
445 \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$.
446 \end{itemize}
447
448 Again: overall when doing lattice-based cryptography, we will be interested into keeping the values \emph{short}, aka. of small norm.
449 \pause
450 (example of decomposing values to keep small norms when doing operations in cryptographic protocols)
451\end{frame}
452
453\begin{frame}{Hard problems in lattices}
454 \begin{defn}[LWE (Learning With Errors)]
455 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$.
456
457 Given the pair $(A, b)$, the goal is to recover $s$.
458 \end{defn}
459 Search-LWE \& Decisional-LWE problems.
460
461 \pause
462 For LWE samples, vector $b$ is relatively close to exactly one vector in the LWE lattice:
463 \begin{align*}
464 \Lambda_q(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
465 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
466 \end{align*}
467
468 \pause
469 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).
470
471 \pause
472 Similarly as with SIS, we also have Ring-LWE and Module-LWE variants of LWE.
473\end{frame}
474
475\begin{frame}{Plain - Module - Ring}
476 $$R_q = \mathbb{Z}_q[x]/(x^n+1)$$
477
478 \small{
479 $$
480 \begin{array}{c|c|c}
481 \text{Assumption} &
482 \text{Public linear relation} &
483 \text{Underlying algebra}
484 \\ \hline
485 \text{Plain LWE} &
486 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
487 A \in \mathbb{Z}_q^{m \times n}
488 \\[0.5em]
489 \text{Module-LWE} &
490 \mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q &
491 A \in R_q^{k \times k},
492 \quad
493 \mathbf{s},\mathbf{e},\mathbf{b} \in R_q^k
494 \\[0.5em]
495 \text{Ring-LWE} &
496 b = as + e \pmod q &
497 a,s,e,b \in R_q
498 \end{array}
499 $$
500 $$
501 \begin{array}{c|c|c}
502 \text{Assumption} &
503 \text{Public linear relation} &
504 \text{Underlying algebra}
505 \\ \hline
506 \text{Plain SIS} &
507 A\mathbf{z} = \mathbf{0} \pmod q,
508 \quad
509 \mathbf{z} \neq \mathbf{0},
510 \quad
511 \|\mathbf{z}\| \text{ small} &
512 A \in \mathbb{Z}_q^{m \times n},
513 \quad
514 \mathbf{z} \in \mathbb{Z}^n
515 \\[0.8em]
516 \text{Module-SIS} &
517 A\mathbf{z} = \mathbf{0} \pmod q,
518 \quad
519 \mathbf{z} \neq \mathbf{0},
520 \quad
521 \|\mathbf{z}\| \text{ small} &
522 A \in R_q^{m \times n},
523 \quad
524 \mathbf{z} \in R^n
525 \\[0.8em]
526 \text{Ring-SIS} &
527 a z = 0 \pmod q,
528 \quad
529 z \neq 0,
530 \quad
531 \|z\| \text{ small} &
532 a \in R_q,
533 \quad
534 z \in R
535 \end{array}
536 $$
537}
538
539
540\end{frame}
541
542\begin{frame}{Dual lattices}
543 SIS lattice:
544 $$\Ll^{\perp}(A) = \{ z \in \Zz^n ~|~ A \cdot z = 0 \pmod q \}$$
545
546 LWE lattice:
547 \begin{align*}
548 \Ll(A) &= \{ A^T s ~|~ s \in \Zz_q^n \} + q \Zz^m\\
549 &= \{ A^T s + qz ~|~ s \in \Zz_q^n, z \in \Zz^m \}
550 \end{align*}
551
552
553 \pause
554 Dual of a lattice:
555 $$\Ll^* = \{ y \in \Rr^m ~|~ \langle y, x \rangle \in \Zz ~\forall~ x \in \Ll \}$$
556
557 ie. all vectors that measure lattice points with integers.
558
559 \vspace{0.5cm}
560 \pause
561 SIS lattices and LWE lattices are dual to each other
562 $$\Ll(A) = q \Ll^{\perp *}(A) ~~~\text{ie.}~~~ \frac{1}{q} \Ll(A) = \Ll^{\perp *}(A)$$
563
564\end{frame}
565
566\begin{frame}
567 \hspace*{-0.8cm}
568 \includegraphics[width=\paperwidth]{./lattice_examples}
569\end{frame}
570
571\begin{frame}{Ajtai commitments}
572
573 \begin{defn}[Ajtai commitemnt]
574 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
575 $$c = A r + G x \pmod q \in \Zz_q^n$$
576 \end{defn}
577
578 Observe that this is closely related to the SIS problem ($Az=0 \pmod q$), and it relies on its hardness.
579
580
581\end{frame}
582
583\section[Signatures]{Signatures}
584
585\begin{frame}{ML-DSA signatures}
586\end{frame}
587
588\begin{frame}{Falcon signatures}
589\end{frame}
590
591
592\section[SNARKs]{SNARKs}
593
594\begin{frame}{LaBRADOR SNARK}
595\end{frame}
596
597\section[Conclusions]{Conclusions}
598
599\begin{frame}{Benchmarks}
600 TODO prover and verifier speed, proof/signature size
601 stark, labrador, sphinchs, falcon, ml-dsa, etc
602\end{frame}
603
604\begin{frame}{Conclusions}
605\end{frame}
606
607
608\end{document}