## Intro to Lattice-based Cryptography ### By Daniel Benarroch, July 2020 **Most pictures taken from [Daniele Micciancio's](https://simons.berkeley.edu/talks/basic-mathematics-lattices) & [Chris Peikert's](https://simons.berkeley.edu/talks/lwe-worst-case-average-case-reductions-and-cryptomania) presentations** --- ## Content Lattices - Motivation - What is a Lattice? - Important properties - Computational problems - Hard Problems from Lattices - Regev Encryption --- ## Motivation - **Mathematics:** used to bridge two fields - **Cryptanalysis:** many problems can be represented with lattices - **Post-quantum cryptography:** hard problems against QC ---- ### Applications - Symmetric crypto: PRF / Hashes - PKC: encryption and signatures (NIST competition) - Identity/Attribute-based encryption - **Homomorphic encryption** - Zero knowledge proofs --- ## What is a Lattice? <u>**Definition 1**</u> A lattice $\mathcal{L}$ of $\mathbb{R}^n$ is a discrete subgroup of $\mathbb{R}^n$ 1- *additive subgroup*: $\textbf{0} \in \mathcal{L}$, $-\textbf{x}, \textbf{x}+\textbf{y} \in \Lambda$ for every $\textbf{x}, \textbf{y} \in \mathcal{L}$ 2- *discrete*: every $\textbf{x} \in \mathcal{L}$ has a neighborhood in $\mathbb{R}^n$ in which $\textbf{x}$ is the only lattice point (We will talk about full-rank lattices only; i.e.: they span $\mathbb{R}^n$) ---- #### Example 1 Simplest $n$-dimensional lattice is $\mathcal{L} = \mathbb{Z}^n$ and $c\mathcal{L}$ for any $c \in \mathbb{R}$  ---- <u>**Definition 2**</u> A lattice $\mathcal{L}$ is the set of all *integer* linear combinations of *linearly independent* basis vectors $\textbf{B} = \{\textbf{b}_1, ..., \textbf{b}_n\} \subset \mathbb{R}^{n}$ $\mathcal{L} = \textbf{B}\mathbb{Z}^n$ where $\textbf{B}\in \mathbb{R}^{d \times n}$  ---- #### Two definitions are equivalent $2 \implies 1$ 1. Existance of shortest vector is equivalent to having a discrete space 2. Parallepiped associated to basis is equivalent to coset group $2 \Longleftarrow 1$ 1. Group defines basis by picking linearly indep vectors. If it does not span $\mathcal{L}$, then find contraction about size of parallepiped ---- ### Lattice Basis We say the (integer) lattice is the span of its basis, written as $\begin{equation} \mathcal{L} = \sum^n_{i=1} \textbf{b}_i \cdot \mathbb{Z} = \left\{ \sum^n_{i=1}c_i \textbf{b}_i : c_i \in \mathbb{Z} \right\} \end{equation}$ where the generating basis matrix ---- ### Cosets As an additive subgroup, we can talk of the quotient group $\mathbb{R}^n / \mathcal{L}$ of cosets $\begin{equation} \textbf{c} + \mathcal{L} = \{\textbf{c} + \textbf{v} : \textbf{v} \in \mathcal{L} \}, \textbf{c} \in \mathbb{R}^n \end{equation}$ > Imagine taking the lattice and moving it around all over the underlying real space. Each position is a coset of the lattice > ---- ### Fundamental Region The fundamental region of the lattice is the parallepiped $\begin{equation} \mathcal{P}(\textbf{B}) := \textbf{B}\cdot \left[-\frac{1}{2}, \frac{1}{2} \right)^n \end{equation}$ Where different bases define different fundamental regions, all with the same volume, as $\mathrm{det}(\mathcal{L}) = \mathrm{vol}(\mathcal{P}(\textbf{B})) = |\mathbb{Z}^n / \mathcal{L}|$   ---- > Note that any fundamental region (for different basis and cosets), provides a standard set of representative elements for the coset. --- ## Other important metrics and measurements 1. Minimum distance 2. Successive minima 3. Distance function 4. Covering radius & Smoothing parameter ---- ### Minimum distance $\begin{eqnarray} \lambda_1 = \lambda_1(\mathcal{L}) &= \min_{\textbf{x}, \textbf{y}\in \Lambda; \textbf{x}\neq \textbf{y}} \|\textbf{x} - \textbf{y} \| \\ &= \min_{\textbf{x}\in \Lambda; \textbf{x}\neq \textbf{0}} \|\textbf{x}\| \end{eqnarray}$  ---- where $\|\textbf{x}\| = \sqrt{x_1^2 + ... + x_n^2}$ > Note that $\lambda_1$ is easy to compute in 2D (Lagrange), but hard in $n$D ---- ### Successive minima The $i$-th successive minimum $\lambda_i(\mathcal{L})$ is the smallest $r$ s.t. $\mathcal{L}$ has $i$ linearly independent vectors of norm at most $r$ Trivial example is in $\mathbb{Z}^n$: $\lambda_1 = \lambda_2 = ... = \lambda_n = 1$  ---- ### Bounds on $\lambda_i$ - Minkowski #1 $\rightarrow \lambda_1 \leq \sqrt{n}(\det \mathcal{L})^{\frac{1}{n}}$ - Minkowski #2 $\rightarrow (\prod_{i=1}^n \lambda_i)^{\frac{1}{n}} \leq \sqrt{n}(\det \mathcal{L})^{\frac{1}{n}}$ Very analytical proofs. --- ## Some computational problems From SVP to BDD ---- ### Shortest Vector Problem (SVP) > For an arbitrary basis $\textbf{B}$ of a lattice $\mathcal{L}$, find the shortest non-zero lattice vector: $\textbf{v} \in \mathcal{L}$ s.t. $\|\textbf{v}\| = \lambda_1(\mathcal{L})$. We write $\textbf{v} = \textbf{B}\textbf{x}$ for $\textbf{x} \in \mathbb{Z}^n$  ---- ### Approximate & Decisional - Approximate SVP (SVP$_{\gamma}$) $\rightarrow \|\textbf{v}\| \leq \gamma(n)\cdot \lambda_1(\mathcal{L})$ - Decisional approx SVP (GapSVP$_{\gamma}$) $\rightarrow \text{ determine } \lambda_1 \leq 1 \text{ or } \lambda_1 > \gamma(n)$ ---- ### Approximate SIVP$_{\gamma}$ For an arbitrary basis $\textbf{B}$ of a full-rank, $n$-dimensional lattice, output $\textbf{S} = \{\textbf{s}_i\} \subset\mathcal{L}(\textbf{B})$ of $n$ linearly indep. lattice vectors where $\|\textbf{s}_i\| \leq \gamma(n)\cdot \lambda_n\mathcal{L}$ for all i.  ---- ### State-of-the-art Attacks These are well studied problems: - Lenstra, Lenstra, and Lovasz (LLL) algorithm most well known, **polynomial time for sub-exponential approx factors** - For polynomial approx factors, only **~exponential time and space** IMPORTANT: this is also state for quantum algorithms --- ## One more important problem ---- ### Distance function For any point $\textbf{t} \in \mathbb{R}^n$, define the distance to the lattice $\begin{equation} \mu(\textbf{t}, \mathcal{L}) = \min_{\textbf{x}\in \mathcal{L}} \|\textbf{t} - \textbf{x}\| \end{equation}$ ---- - One can ask the question of how close is any point to the lattice? Closest Vector Problem (not THAT interesting for crypto) - Used in coding theory to study level of noise in communication channel  ---- ### Bounded Distance Decoding (BDD$_{\gamma}$) Problem > Given $(\mathcal{L}, \textbf{t}, d)$ s.t. > $\begin{equation} \mu(\textbf{t}, \mathcal{L}) < d = \lambda_1 / (2\gamma(n)) \end{equation}$ > find **unique** $\textbf{v} \in \mathcal{L}$ where s.t. $\|\textbf{t} - \textbf{v}\| < d$ Vector assured to exist; remove the condition to get CVP. ----  --- ## Using noise in lattices ---- ### Covering radius Is maximum distance between the lattice and any point in the span of the lattice: $\begin{equation} \mu(\mathcal{L}) = \max_{\textbf{t} \in span(\mathcal{L})} \mu(\textbf{t}, \mathcal{L}) \end{equation}$ Spheres of radius $\mu(\mathcal{L})$ cover the whole space  ---- ### Smoothing lattices Now imagine adding more and more noise to make uniform distribution > Radius at most $\|\textbf{r}\| \leq (\log n) \cdot \sqrt{n} \lambda_n$   ---- ### Smoothing parameter *Best done with Gaussian noise of width $|r_i| \approx \eta_{\epsilon} \leq (\log n) \lambda_n$* We call $\eta_{\epsilon}$ the smoothing parameter, with several technical results. > Think about it as the amount of "blur" needed to smooth out the lattice. --- ## Discrete Gaussian Distributions We recall the basic concepts and definitions, which are used in cryptosystems to make problems hard. ---- ### Gaussian function For any integer $n\geq 1$ and real $s>0$, define Gaussian function of width $s$: > $\begin{equation} \rho_s(\textbf{x}) := \exp(-\pi\|\textbf{x}\|^2/s^2)\end{equation}$ Where $\rho_s(\textbf{x}) = \prod_{i=0}^n \rho_s(x_i)$; in the continuous setting, it defines a normal distribution  ---- ### Discrete Gaussian probability > Defined for a coset $\textbf{c}+ \mathcal{L} \subset \mathbb{R}^n$ and parameter $s>0$, discrete Gaussian by restriction $\begin{equation} D_{\textbf{c} + \mathcal{L}, s}(\textbf{x}) \propto \rho_s(\textbf{x}) \text{ if } \textbf{x} \in \textbf{c} + \mathcal{L} \text{; or } 0 \text{ otherwise.} \end{equation}$ ---- ### Sampling > For any basis $\textbf{B}$ of a lattice $\mathcal{L}$, for any coset $\textbf{c}+\mathcal{L}$, and any Gaussian $s \geq K$, there is an randomized, poly-time algorithm that outputs a sample of $\mathcal{L}$ that is within statistical distance $\epsilon$ of $D_{\textbf{c}+\mathcal{L}, s}$ ---- ### Algos - A variation of "nearest plane" algorithm by Babai'85 is first well known sampling algo, but innefficient. - Peikert'10 came up with a novel "perturbation" sampling that is quasi-linear - Brakerski and more... --- ## Cryptographic problems Foundations and the all-encompassing problem, learning with errors ---- ### q-ary Lattices Cryptography likes to work modulo some integer, $q$. In lattices, the reason is in connection to worst-case vs average-case reductions. > $\mathcal{L} \subseteq \mathbb{Z}^n$ is integer lattice > $q\mathbb{Z}^n \subseteq \mathcal{L}$ is periodic modulo small $q$ Functions based on q-are lattices use modulo arithmetic ---- Standard way of building such lattice: Take matrix $\mathcal{L}_q(\textbf{A}) = \{ \textbf{x} | \textbf{x} \mod q = \textbf{A}\textbf{u}\textit{ for } \textbf{u} \in \mathbb{Z}^n_q \} \subseteq \mathbb{Z}^n$ - Consider image of $\textbf{A}$, lattice spanned by it - Can also consider the kernel of this where $\textbf{Au} = 0 \mod q$ and these are reciprocal conditions ---- Confusing note: > in cryptography one does not need to think about lattices. In some sense, lattices are so nice, that they can apply "post-cryptography" and things will work out. ---- ### Short Integer Solution (SIS) This problem has applications in symmetric crypto. Informally: for random uniform elements in a group, find an integer linear combination that sums to zero. ---- **Parameters** - $n$ number of dimensions, main hardness - $q$ defines the group $\mathbb{Z}^n_q$ (think $q \approx n^2)$ - $\beta$ positive real - $m$ number of elements ---- #### SIS$_{n,q,\beta, m}$ For $n$ uniformly random vectors $\textbf{a}_i \in \mathbb{Z}^m_q$, rows of matrix $\textbf{A} \in \mathbb{Z}^{n\times m}_q$, find non-zero integer vector $\textbf{z} \in \mathbb{Z}^m$ of short norm $\|\textbf{z}\| \leq \beta$ s.t. > $\begin{equation} f_{\textbf{A}}(\textbf{z}) := \textbf{Az} = \sum_{i=1}^m \textbf{a}_i \cdot z_i = 0 \in \mathbb{Z}^n_q \end{equation}$ ---- **Intuition** By Gaussian elimition, this would be easy, but large $\textbf{z}$ vector, so require it to be small - must take $\beta < q$ or trivial solution $\textbf{z}=(q,0,...,0)$ would be legit - $\beta$ and $m$ must be large enought to ensure existence ---- **Reductions** - Ajtai'96: SIS reduced GapSVP$_{\gamma}$ and GapSIVP$_{\gamma}$ in the worst-case for $\gamma = \beta\cdot poly(n)$ and $q \geq \beta\cdot poly(n)$ - Best result today by Micciancio and Peikert'13: much lower $q$ and $\gamma$, so smaller keys and stronger guarantees ---- ### Ajtai CRF Think of SIS as a function: $\begin{equation} f_{\textbf{A}}(\textbf{x}) = \textbf{Ax} \mod q \end{equation}$  ---- **Concretely** - Parameters: $m,n,q \in \mathbb{Z}$ - Key: $\textbf{A} \in \mathbb{Z}_q^{n\times m}$ - Input: $\textbf{x} \in \{0,1\}^m$ - Output: $f_{\textbf{A}}(\textbf{x}) = \textbf{Ax} \mod q$ ---- **CR** If collision > $\textbf{Ax} = \textbf{Ax}' \rightarrow \textbf{Az} = \textbf{A}(\textbf{x}-\textbf{x}') = 0$ where $\textbf{z}$ is short, solution to SIS ---- **Also it is a one-way function** > If SIVP is hard, then $f$ is a one-way function for $m> n \log q$ ---- **Remember the confusing note?** Note that the $q$-ary lattice $\mathcal{L}'_q(\textbf{A})$ is the kernel of $f_{\textbf{A}}$ - Finding collisions $f_{\textbf{A}}(\textbf{x}) = f_{\textbf{A}}(\textbf{y})$ is equivalent to finding short vectors (SIVP) - Inverting it is equivalent to CVP under some conditions We applied lattices given matrices and vectors (integers, modulo $q$) ---- ### Regev'05 Learning With Errors Informally search version: given many noisy inner products $<\textbf{s},\textbf{a}_i> + e_i$ find the secret $\textbf{s}$ common to all Note that without the error, easy to solve as set of linear equations by Gaussian elimination. ---- **Parameters:** - dimension $n$ - modulus $q = poly(n)$ - error distribution $\chi$ on $\mathbb{Z}_q$ ---- **Search Problem** Given arbitrary samples below, find $\textbf{s} \in \mathbb{Z}_q^n$  ---- **Other form** $g_{\textbf{A}}(\textbf{s};\textbf{e}) = \textbf{As} + \textbf{e} \mod q$ > Given $\textbf{A}$ and $g_{\textbf{A}}(\textbf{s};\textbf{e})$, recover $\textbf{s}$  ---- **Error Distribution** Think of Gaussian / normal distribution such that stdDev $= \alpha q$  ---- **Decision version** Differentiate between distributions $\begin{equation} (\textbf{A}, \textbf{b}) \approx (\textbf{A}, \textbf{u}) \end{equation}$ where $\textbf{u} \in \mathbb{Z}_q^m$ is uniformly random. ---- **LWE as lattice problem** related to the BDD problem > $\textbf{v} \in \mathcal{L}$ where s.t. $\|\textbf{t} - \textbf{v}\| < d$ > $\textbf{v} \in \mathcal{L}$ where s.t. $\|\textbf{t} - \textbf{v}\|$ is small > $\textbf{x} \in \mathbb{Z}_q^n$ where s.t. $\textbf{Ax}+e - \textbf{Ax} \approx 0$ ---- **Reductions** $g_{\textbf{A}}$ is hard to invert on average. Assuming GapSVP, LWE is hard in the worst-case. GapSVP, SIVP $\leq$ search-LWE $\leq$ decision-LWE $\leq$ Crypto > search-LWE $\equiv$ decision-LWE ---- **Intuition and Quantumness** - Best known algoritms (even in quantumness run in exponential time) - Average-case = worst-case (every problem in the family is hard). - For any classical alg to solve search-LWE it can translate into quantum alg to solve decision-LWE > This and the fact that there is no quantum algorithm to solve SVP makes us think it is post-quantum resistant --- ## Cryptographic applications Regev encryption scheme is used as a basis for many other schemes ---- ### Public-key encryption scheme from LWE [Regev05, GPV08] Say, Alice and Bob want to communicate. Bob will send a message to Alice. #### Public set up: $parameters = \mathrm{Gen}(\lambda)$ - $n, q, m, \chi$ - Sample $\textbf{A} \in \mathbb{Z}^{n\times m}_q$ ---- #### Key generation: $(sk, pk) = \mathrm{Gen}(\textbf{A}, m, n, q)$ - Sample short vector $sk = \textbf{x} \leftarrow \mathbb{Z}^m$ - Compute $pk = \textbf{u} = \textbf{A}\textbf{x}$ > for parameters, if $m > n \log q$ then public key is uniform random vector by LHL ---- #### Encryption: $(\textbf{b}^t, b') = \mathrm{Enc}(bit, \textbf{u})$ - Bob wants to encrypt $bit \in \{0,1\}$ - Sample secret $\textbf{s} \in \mathbb{Z}_q^n$ - Computes "preamble" LWE vector $\begin{equation} \textbf{b}^t = \textbf{s}^t \textbf{A} + \textbf{e}^t \end{equation}$ - Computes payload $\begin{equation} b' = \textbf{s}^t\textbf{u} + e' + bit\cdot \frac{q}{2} \end{equation}$ ---- #### Decryption: $bit = \mathrm{Dec}(\textbf{b}^t, \textbf{b}', \textbf{x})$ Alice computes $\begin{eqnarray} & \textbf{b}' - \textbf{b}^t \cdot \textbf{x} \\ = & \textbf{s}^t\cdot \textbf{u} - \textbf{s}^t\textbf{Ax} - \textbf{e}^t\textbf{x}+ e' + bit\cdot \frac{q}{2} \\ = & smallError + bit\cdot \frac{q}{2} \end{eqnarray}$ If result is small, then $bit=0$, otherwise $bit =1$ ---- **Putting it together**  ---- **Security** - Eve sees $(\textbf{A},\textbf{u}), (\textbf{b}^t, b')$ - This is LWE samples by multiplying by $\textbf{s}$ - If change the latter with truly uniform samples, $bit$ is hidden informational theoretically - So based on decision-LWE ---- # Thank You!  --- ## Bibliography [[MicSim20a]](https://simons.berkeley.edu/talks/basic-mathematics-lattices) Daniele Micciancio, *Mathematics of Lattices*, Lattices Bootcamp at Simons Institute [[MicSim20b]](https://simons.berkeley.edu/talks/sis-worst-case-average-case-reductions-and-minicrypt), Daniele Micciancio, *The Short Integer Solutions Problem and Cryptographic Applications*, Lattices Bootcamp at Simons Institute [[PeiSim20a]](https://simons.berkeley.edu/talks/lwe-worst-case-average-case-reductions-and-cryptomania) Chris Peikert, *The Learning With Errors Problem and Cryptographic Applications*, Lattices Bootcamp at Simons Institute [[RegLWE]](https://cims.nyu.edu/~regev/papers/lwesurvey.pdf) Oded Regev, *The Learning with Errors Problem*, survey published online