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