# PQC-Lattice based cryptography筆記

## Lattice

### Lattices defination

- An n-dimensional lattice $\mathcal L$ is an subset of $\mathbb R^n$ that is both
1. additive subgroup: $0\in \mathcal L$, and $\forall x, y\in \mathcal L, -x, x+y\in \mathcal L$
2. discrete: every $x \in \mathcal L$ has a neighbor in $\mathbb R^n$ in which x is the only lattice point.

- minimum distance of a lattice $\mathcal L$
$$\lambda_1(\mathcal L):=\min_{v\in \mathcal L \backslash\{0\}}||v||.$$
$||\cdot||$ denote the minimum euclidean norm, and $\lambda_i(\mathcal L)$ is the norm of $i$-th sortest linearly independent vector.

- quotient qroup $\mathbb R^n/\mathcal L$ of cosets
$$c+\mathcal L = \{c+v:v\in\mathcal L\}, c\in \mathbb R^n$$

- fundamental domain of $\mathcal L$ is a set $\mathcal F\subset \mathbb R^n$ that
contain exactly one representative $\bar c\in (c+\mathcal L)\cap \mathcal F$ in every coset $c+\mathcal L$
(我的理解是找到一個保證任何平移後都會洽有一個晶格點落在其中的空間)

- Bases: every lattice $\mathcal L$ always finitely generated as the integer linear combinations of some linearly independent $basis$ vector $B=\{b_1, b_2, ..., b_k\}:$
$$\mathcal L = \mathcal L(B):=B \cdot \mathbb Z^k=\left\{\sum_{i=1}^kz_ib_i:z_i\in \mathbb Z\right\}$$
A lattice base $B$ is not unique: for any unimodular matrix $U\in \mathbb Z^{n\times n}$(unimodular means having determinant $\pm 1$), $B\cdot U$ is also a basis of $\mathcal L(B)$

- fundamental parallelpipeds:
for a lattice $\mathcal L$ having a basis $B$, a commonly used fundamental domain is the origin-centered fundamental parallelepiped $\mathcal P(B):=B\cdot [-\frac 1 2, \frac 1 2)^n$, where coset $c+\mathcal L$ has representative $c-B\cdot \lfloor B^{-1}\cdot c\rceil$.
proof.
lemma: $\forall x\in \mathbb R^n, x-\lfloor x\rceil\in [-\frac 1 2, \frac 1 2)^n$
$\eqalign{
&c-B\cdot \lfloor B^{-1}\cdot c\rceil \\
=&B\cdot (B^{-1}\cdot c)-B\cdot \lfloor B^{-1}\cdot c\rceil\\
=&B\cdot (B^{-1}\cdot c-\lfloor B^{-1}\cdot c\rceil)\\
\in &B\cdot {[-\frac 1 2, \frac 1 2)}^n
}$

- dual lattice:
the dual (or reciprocal) of a lattice $\mathcal L\in\mathbb R^n$ is defined as
$$\mathcal L^*:=\{w:\langle w, \mathcal L\rangle\subseteq\mathbb Z \},$$
if $B$ is a basis of $\mathcal L$, then $B^{-t}:=(B^t)^{-1}=(B^{-1})^t$ is a basis of $\mathcal L^*$,
and $\forall c\in \mathbb R, (c\mathcal L)^*=c^{-1}\mathcal L^*$

### Computational Problems
All mentioned problems can be defined with respect to any norm, but the Euclidean norm $||x|| = \sqrt{\sum_i x^2}$ is the most common

- Shortest Vector Problem (SVP)
given an arbitrary basis $B$ of some lattice $\mathcal L=\mathcal L(B)$, find $v\in \mathcal L$ for which $||v||=\lambda_1(\mathcal L)$

- Approximate Shortest Vector Problem (SVP$_\gamma$)
$\gamma=\gamma(n)$ is a factor function $\geq 1$ where n is the dimension of the lattice, find a nonzero vector $v\in \mathcal L$ for which $||v||\leq\gamma(n)\cdot\lambda_1(\mathcal L).$

- Decisional Approximate SVP (GapSVP$_\gamma$)
Given a basis $B$ of n-diemnsional lattice $\mathcal L$, determine $\mathcal L$ is either $\lambda_1(\mathcal L)\leq 1$ or $\lambda_1(\mathcal L)> \gamma(n)$

- Closest Vector Problem (CVP)
Givven a lattice basis $\text B$ and a target vector $\text t$ (not necessarily in the lattice), find the lattice point $\text v\in\mathcal L(\text B)$

- Shortest Independent Vectors Problem (SIVP)
Given a basis $B$ of full-rank n-dimensional lattice $\mathcal L$ ouput $S = \{s_i\}\subset \mathcal L$ with n linearly independent lattice vector that $\forall i, ||s_i||\leq\lambda_n(\mathcal L)$

- Approximate Shortest Independent Vectors Problem (SIVP$_\gamma$)
Given a basis $B$ of full-rank n-dimensional lattice $\mathcal L$ ouput $S = \{s_i\}\subset \mathcal L$ with n linearly independent lattice vector that $\forall i, ||s_i||\leq\gamma(n)\cdot\lambda_n(\mathcal L)$

- Bounded Distance Decoding Problem (BDD$_\gamma$)
Given a basis $B$ of an n-dimensional lattice $\mathcal L$ and a target point $t\in\mathbb R^n$ with $dist(t, \mathcal L)<d=\lambda_1(\mathcal L)/(2\gamma(n))$ garanteed, find the unique lattice vector $v\in\mathcal L$ s.t. $||t-v||<d$

### q-ary lattices

lattices $\mathcal L$ satisfying $q\mathbb Z^n\subseteq\mathcal L\subseteq\mathbb Z^n$ for some integer(possibly prime) $q$
- the membership of a vector $\text x$ in $\mathcal L$ is determined by $\text x \mod q$,
- such lattices are in one-to-one correspondence with linear codes in $\mathbb Z_q^n$
- $\forall \mathcal L\subseteq\mathbb Z^n, \mathcal L$ is a q-ary lattice for some $q$, which $q$ is an integer mutiple of $\det(\mathcal L)$
- Given a matrix $\text A\in\mathbb Z^{n\times m}_q$ for some integers q, m, n, we can define two m-dimensional q-ary lattices
$$\eqalign{
\Lambda_q(\text A) &=\{\text y\in\mathbb Z^m:\text y=\text A^T\text s \text { mod } q \text{ for some }s\in\mathbb Z^n\}\\
\Lambda^\bot_q(\text A) &=\{\text y\in\mathbb Z^m:\text{Ay}=0\text{ mod q}\}
}$$

- the first q-ary lattice is generated by the rows of $\text A$, e.g. it corresponds to the code generated by the rows of $\text A$
- the second q-ary lattice contains all vectors that are orthogonal modulo $q$ to the rows of $\text A$, e.g. it corresponds to the code whose parity check matrix is $\text A$
- follows from the defination that first and second lattice are dual two each other, e.g., $\Lambda^\bot_q(\text A)=q\cdot \Lambda_q(\text A)^*$ and $\Lambda_q(\text A)=q\cdot \Lambda^\bot_q(A)^*$

### Finding Short Vectors in Random q-ary Lattices
Given a random matrix $\text A\in\mathbb Z^{n\times m}_q$ for some $q$, $n$, and $m\geq n$ and we are asked to find a short vector in $\Lambda^\bot_q(\text A)$
- it's equivalent to asking for a short solution to a set of $n$ random equations modulo $q$ in $m$ variables
- there will be two algorthim mentioned later

#### estimate the length of the shortest nonzero vector
- assume $q$ is prime
- with high probability (with m is not too close to n), the rows of $\text A$ are linearly independent over $\mathbb Z_q$
- In such case, the number of elements of $\mathbb Z^m_q$ that belong to $\Lambda^\bot_q(\text A)$ is exactly $q^{m-n}$
- It follows that $\det(\Lambda^\bot_q(A))=q^n$
- We heuristically estimate $\lambda_1(\Lambda^\bot_q(A))$ as the smallest radius of a ball whose volume is $q^n$, i.e. $\lambda_1(\Lambda^\bot_q(A))\approx q^{n/m}\cdot ((m/2)!)^{1/m}/\sqrt\pi\approx q^{n/m}\cdot \sqrt{\frac{m}{2\pi e}}$, which we use the formula for the volume of a ball in m dimensions
- for resonable values of m (not too close to n nor too large), some experiments in low dimensions indicated this estimate to be very good.

### Lattice reduction methods
- the length of the vector obtained by running the best known algorithms on a random m-dimensional q-ary lattice $\Lambda^\bot_q(A)$ is close to $$\min\{q, (\det(\Lambda^\bot_q(A)))^{1/m}\cdot \delta^m\}=\min\{q, q^{n/m}\delta^m\}$$, the parameter $\delta$ depends on the algorithm used. Faster algorithms provide $\delta\approx 1.013$ whereas slower and more precise algorithm provide $\delta\approx 1.012$ or even $\delta\approx 1.011$, Gama and Nguyen in fact estimate that a factor of 1.005 is totally out of reach in dimension 500
- m's effect on the hardness of the question , this figure is $q^{n/m}\delta^m$ with $\delta=1.01$, $q=4416857$, and $n=100$. The minimum of the function is $2^{2\sqrt{n\log q\log\delta}}$, it means the sortest vectors are produced when $m=\sqrt{n\log q/\log\delta}$
- So when consider the problem, reducing the dimension to desired m is really helpful on finding the shortest vector.
- Combinatorial methods
given a matrix $A\in \mathbb Z^{n\times m}_q$, we want to find a lattice point in $\Lambda^\bot_q(A)$ with cooridinates all bounded in absolute value by $b$
- Divide the columns of $A$ into $2^k$ groups (for some k to be determined)
- For each group, build a list containing all linear combinations of the columns with coefficients in $\{-b, ..., b\}$
- At this point we have $2^k$ list, each containing $L=(2b+1)^m/2^k$ vectors in $\mathbb Z^n_q$
- Combining all list by pair:
$\text x$ in first list, $\text y$ in second list, take all $\text x+\text y$ that is zero in the first $\log_q L$ coordinates
- Since the coordinate can take $q^{\log_q L}=L$ values, we expect the merged list to $L\cdot L/L=L$
- keep combining for k turn, then we get only one list of size $L$ containing vectors that are 0 in their first $k\cdot \log_qL$ coordinates, so we choose k s.t. $n\approx (k+1)\log_qL$, then we can expect the next turn get all zero vector
- cost:
The all zero vector found in the last list is given by a combination of the columns of A with coefficients bounded by b, so we have found the desired short lattice vector. Differently from lattice reduction, we can always expect this attack to succeed when A is random. The question is: what is the cost of running the attack? It is easy to see that the cost of the attack is dominated by the size of the lists L, which equals (2b + 1)m/2 k.

## (Descrete) Gaussians and Subgaussians

- Gaussians: for any $n\in \mathbb Z$ and real $s>0$, which $s$ is omitted if $s=1$, the Gaussian function $\rho_s(\text x):=e^{-\pi (\frac{||\text x||}{s})^2} = \rho(\text x/s)$

- Continuous Guassian distribution $D_s$ of parameter $s$ over $\mathbb R^n$ is defined to have probability density function proportional to $\rho_s$ i.e.
$$f(\text x):=\frac{\rho_s(\text x)}{\int_{\mathbb R^n}\rho_s(\text z)d\text z}=\rho_s(\text x)/s^n$$

- discrete Gaussian probability distribution $D_{c+\mathcal L, s}(\text x)$:
$$D_{c+\mathcal L, s}(\text x)\propto
\left\{\begin{array}{r}
\begin{align}
&\rho_s(\text x) &{\text{if x}\in c+\mathcal L}\\
&0 &{\text{otherwise.}}
\end{align}
\end{array}\right.$$

- Smoothing parameter:
- define $\rho_s(c+\mathcal L):=\sum_{\text x\in c+\mathcal L}\rho_s(\text x)$
- smoothing parameter $\eta_\varepsilon(c+\mathcal L)$ with tolerance $\varepsilon>0$
$$\eta_\varepsilon(c+\mathcal L):=min(\forall_{s>0}, \rho_{1/s}(\mathcal L^*)\leq1+\varepsilon)$$
- theorem 2.3.1
$\forall \mathcal L\subseteq \mathbb R^n, \eta_{2^{-n}}(\mathcal L)\leq\sqrt n/\lambda_1(\mathcal L^*)$
- theorem 2.3.2
$\forall \mathcal L\subseteq \mathbb R^n$ and $\varepsilon \in (0, 1/2),$
$$\eta_\varepsilon(\mathcal L)\leq \min_{basis \text { B } of \text { }\mathcal L}||\tilde {\text B}||\cdot \sqrt{\log O(n/\varepsilon)}\leq\lambda_n(\mathcal L)\cdot \sqrt{\log O(n/\varepsilon)}$$
where $||\tilde {\text B}||=\max_i||\tilde {\text{b}_i}||$ denotes the maximal length of the Gram-Schmidt orthogonalized vector $\{\tilde{\text b_i}\}$ of the ordered basis $\text B={\text b_i}$

- Several works have shown that when $s\geq\eta(\mathcal L)$, the discrete Guassion distribution $\text D_{c+\mathcal L, s}$, behaves very much like the continuous Gaussian $\text D_s$ in many important respects. For example, their moments and tails are nearly the same, and the sum of independent discrete Gaussians is a discrete Gaussian.

- Subgaussianity
a real random variable $X$ is subgaussian with parameter $s$ if for every $t\geq 0$, $$\Pr[|x|>t]\leq 2e^{-\pi \frac{t^2}{s^2}}$$
more generally, a random vector $\text x$ over $\mathbb R^n$ is subgaussian with parameter $s$ if every marginal $\langle \text x, \text u\rangle$ is, for all unit vectors $\text u\in\mathbb R^n$
- Examples with parameter s:
1. any symmetric random variable having magnitude bounded by $s/\sqrt{2\pi}$
2. the continuous Gaussian $D_s$ and discrete Gaussian $D_{\mathcal L,s}$ over any lattice $\mathcal L$
3. discrete Gaussian $D_{c+\mathcal L,s}$ over any coset when $s\geq \eta(\mathcal L)$ (under a slight relaxation of subgaussianity)

## Cryptographic

- security parameter $\lambda$ relugate the running times of all algorithm. e.g. polynomial $\lambda^{O(1)}$ running time for all algorithms, and that the attacker's advantage is negligible $\lambda^{-\omega(1)}$
- Function Families
A function family is a function $f:K\times X\rightarrow Y$ where space $K$ for keys, $X$ for domain, and $Y$ for range, it is called family since the set of functions $f_k(\cdot)=f(k,\cdot)$ for keys $k\in K$. if $|X|>|Y|$, i.e. the function "compresses" its input by some amount, it is often called hash function.
properties:
- one way family $f$
given $k\in K, y=f_k(x)\in Y$ where $k, x$ are randomly chosen from prescribed distributions, it is infeasible to find any preimage $x'\in f_k^{-1}(y)$.
- collision resistant family f
given a random $k\in K$ (chosen from a prescried distribution), it is infeasible to find distinct $x, x'\in X$ such that $f_k(x)=f_k(x').$

- Public-Key Encryption (Asymmetric encryption scheme)
- An asymmetric encryption scheme consist of three randomized algorithms having following interfaces:
1. key generator
given the security parameter, ouputs a public key and secret key
2. encryption algorithm
takes the public key and a message (from some set of valid messages) and outputs a ciphertext
3. decryption algorithm
takes a secret key and a ciphertext, and outputs either a message or a distinguished "failure" symbol.

- semantic security, or indistingusiability under chosen-plaintext attack (IND-CPA) parameterized by a bit $b\in \{0, 1\}$
1. Generate a public/secret key pair, and give the public key to the attacker, who must reply with two valid message $m_0, m_1$. (If the valid message space is just {0, 1}, then we may assume that $m_b=b$ without loss of generality.)
2. Encrypt $m_b$ using the public key and give the resulting "challenge ciphertext" to the attacker.
3. Finally, the attacker either accepts or rejects.

An encryption scheme is said to be semantically (or IND-CPA) secure if it is infeasible for an attacker to distinguish between two cases $b=0$ and $b=1$. That is, its probabilities of accepting in the two cases should differ by only a negligible amount.
- active security, or indistinguishability under chosen-ciphertest attack (IND-CCA)
give the attacker access to a decryption oracle, i.e., one that runs the decryption algorithm (with the secret key) with any ciphertext the attacker may query, except for the challenge ciphertext. The scheme is said to be actively (or IND-CCA) secure if it is infeasible for an attacker to distinguish between the two cases $b=0$ and $b=1$

## LWE(Learning With Error)-based cryptosystem
- introduction
LWE-based system is perhaps the most efficient lattice-based cryptosystem to date supported by a theoretical proof of security.
- naive construct complexity
When based on the hardness of lattice problems in dimension n, the cryptosystem has a public key of size $\tilde{O}(n^2)$, requires $\tilde O(n)$ bit operations per encrypted bit, and expands each encrypted bit to $O(1)$ bits.
- parameter
This problem is parametrized by integers $n, m, q$ and a probility distribution $\chi$ on $\mathbb Z_q$, typically taken to be "rounded" normal distribution.
- input
The input is a pair $(\text A, \text v)$ where $\text A\in \mathbb Z^{m\times n}_q$ is choosen uniformly, and $\text v$ is either chosen uniformly from $\mathbb Z^m_q$ or chosen to be $\text{As}+\text e$ for a uniformly chosen $\text s\in \mathbb Z^n_q$ and a vector $\text e\in \mathbb Z^m_q$ chosen according to $\chi^m$
- cryptosystem
It is parameterized by integers $n, m, \ell, t, r, q$, and a real $\alpha > 0$. n is in some sense the main security parameter.
- The message space is $\mathbb Z^\ell_t$.
- $f$ is the functions that maps the message space $\mathbb Z^\ell_t$ to $\mathbb Z^\ell_q$ by multiplying each coordinate by $q/t$ and rounded to nearest integer. $f^{-1}$ dividing each coordinate by $q/t$ and rounding to the nearest integer.
- scheme
- Decryption description
$$\begin{split}
f^{-1}(\text c-\text S^T)&=f^{-1}(\text P^T\text a+f(\text v)-\text S^T\text A^T\text a)\\
&=f^{-1}((\text A\text S+\text E)^T\text a+f(\text v)-\text S^T\text A^T\text a)\\
&=f^{-1}(\text E^T\text a+f(\text v))
\end{split}$$
- Decrypyion error
- in order for a letter decryption error to occur, say in the first letter, the first coordinate of $\text E^T\text a$ must be greater than $q/(2t)$ in absolute value.
- since the sum of independent normal variables is still a normal variable with the variance begin the sum of variances, Fixing the vector $\text a$ and ignoring the rounding, the distribution of the first coordinate of $\text E^T\text a$ is a normal distribution with mean 0 and standard deviation $\alpha q||a||/\sqrt{2\pi}$
- Now the norm of $\text a$ can be seen to be with very high probability close to $$||a||\approx\sqrt{r(r+1)m/3}$$ by estimate the square expectation value $$\frac 1{2r+1}\sum^r_{k=-r}k^2=\frac {r(r+1)}{3}$$
- $\Phi$ is the cumulative distribution function of the standard normal distribution, then $$\text{error probability per letter}\approx 2\Bigg(1-\Phi\Bigg(\frac 1{2t\alpha}\cdot\sqrt{\frac{6\pi}{r(r+1)m}}\Bigg)\Bigg)$$
- final conclusion