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