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