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