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