# Post Quantum
## Introduct
- Post Quantum cryptography: là lĩnh vực mật mã nơi các thuật toán mã hóa được phát triển an toàn khỏi kẻ thù với máy tính lượng tử.
- Tất cả các thuật toán bất đối xứng ngày nay (RSA, ECC, DH, DSA) có thể bẻ khóa bằng máy tính lượng tử. Chúng dựa trên bài toán Prime Factoring hoặc Bài toán Logarit rời rạc dễ giải quyết trên các máy tính lượng tử sử dụng Thuật toán Shor. Các nhà toán học và mật mã học đã sử dụng các vấn đề lý thuyết số này để làm cơ sở cho tính bảo mật của các thuật toán bất đối xứng. Bây giờ họ phải tìm kiếm các vấn đề toán học mới mà máy tính lượng tử không thể giải quyết dễ dàng.
- Các thuật toán đối xứng và hàm băm tương đối an toàn khi máy tính lượng tử trở nên phổ biến. [Grover’s Algorithm](https://www.geeksforgeeks.org/introduction-to-grovers-algorithm/) có thể tăng tốc độ tấn công bằng độ phức tạp căn bậc hai. Tuy nhiên, hầu hết các thuật toán có thể được bảo mật trở lại bằng cách tăng gấp đôi kích thước khóa.

## Một vài Định nghĩa
- **Định nghĩa 1:** Khối lập phương $n$ chiều có chiều dài cạnh $p_n$ được xác định bởi:

$$B_n= {x_n \in \mathbb{R^n} | \forall i \in {1,..,n}: - \frac{p_n}{2} \leq x_i \leq \frac{p_n}{2}}.$$

- **Định nghĩa 2:** Khồi cầu $n$ chiều bán kính $n^{-c}$ được xác định bởi:
$$S_n= {x \in \mathbb{R^n} |\ \ \ ||x|| \leq n^{-c}}.\ \text{Với}\ \forall c \in \mathbb{Z^+}.$$

- **Định nghĩa 3:** Cho n là số nguyên dương bất kỳ và s là số thực dương được mặc định bằng 1 khi không được đề cập, hàm Gaussian $p_s: \mathbb{R^n} -> \mathbb{R^+}$ với độ rộng $s$ được định nghĩa là:
$$ p_s(x) = \exp(- \pi ||x||^2 / s^2) = p(x/s).$$
- **Định nghĩa 4:** Phân phối Gauss $D_s$ với tham số $s$ trên $\mathbb{R}^n$ được định nghĩa là:
$$f(x) = \rho_s(x) / \int_{\mathbb{R}^n} \rho_s(z) dz = \rho_s(x) / s^n.$$
- **Định nghĩa 5:** Cho $A$ là tập đếm được bất kỳ và tham số dương $s$, phân phối xác suất Gauss rời rạc $D_{A,s}$ được định nghĩa là:
$$D_{A,s}(x) = \frac{\rho_s(x)}{\rho_s(A)}, \forall x \in A.$$
- **Định nghĩa 6:** Cho một coset mạng $c+L⊂ \mathbb{R}^n$ và tham số dương $s$, phân phối xác suất Gauss rời rạc $D_{c+L,s}$ được định nghĩa là phân phối Gauss được giới hạn trong coset:
$$D_{c+\mathcal{L},s}(x) \propto \begin{cases}
\rho_s(x) & \text{nếu} & x \in c + \mathcal{L} \\
0 & \text{còn lại}
\end{cases}.$$
- **Định nghĩa 7:** Cho $\alpha \in \mathbb{R}^+$, phân phối $Ψ_\alpha$ là phân phối trên $\mathbb{T}$ được lấy bằng cách lấy mẫu từ biến bình thường với giá trị trung bình 0 và độ lệch chuẩn $\frac{\alpha}{\sqrt{2 \pi}}$ và giảm kết quả modulo 1, $$ \forall r \in [0,1], Ψ_\alpha (r)= \sum_{k= - \infty}^{\infty} \frac{1}{\alpha}.\exp(-\pi(\frac{r- k}{\alpha})^2).$$
- **Lưu ý:**
- Phân phối Gauss rời rạc là một cách để biểu diễn xác suất của các sự kiện xảy ra trong một tập đếm được. Nó được sử dụng trong nhiều lĩnh vực khác nhau, bao gồm học máy, xử lý tín hiệu và thống kê.
- Các định nghĩa trên cung cấp các công thức toán học để tính toán xác suất của các sự kiện xảy ra trong một phân phối Gauss rời rạc.

- >Các ký hiệu được sử dụng trong các định nghĩa này có ý nghĩa sau:
>- $\mathbb{R}^n$ là không gian Euclid n chiều.
>- $||x||$ là chuẩn Euclidean của vector x.
>- $p_s(x)$ là hàm Gaussian với độ rộng s.
>- $D_s$ là phân phối Gauss với tham số s.
>- $D_{A,s}$ là phân phối Gauss rời rạc trên tập A với tham số s.
>- $D_{c+ L,s}$ là phân phối Gauss rời rạc được giới hạn trong coset $c+ L$ với tham số $s$.
>- $Ψ_\alpha$ là phân phối trên T được lấy bằng cách lấy mẫu từ biến bình thường với trung bình 0 và độ lệch chuẩn $\frac{\alpha}{\sqrt{2 \pi}}$ và giảm kết quả modulo 1.
>- coset là một tập con đặc biệt của một nhóm được tạo ra từ một phần tử của nhóm và một nhóm con của nhóm đó.

## Lattice
[Ở đây nha mng:)))](https://hackmd.io/Wcgm_jrlREWwNxSPdgUpRg)

## Learning with Errors Problem:
- LWE đề cập đến vấn đề tính toán của việc học một hàm tuyến tính $f(A)$ mà nhận giá trị trên một vòng, dựa trên nhiều mẫu nhiễu của hàm đó. Những mẫu này có dạng cặp $(A, <A, S> + e)$, trong đó $S$ là phần tử bí mật xác định hàm tuyến tính, $e$ là một thuật ngữ lỗi nhỏ từ một phân phối đã biết và $A$ là một phần tử đã biết của vòng.

- Các hệ mật mã dựa trên LWE khá đa dạng, nhưng thường có một số đặc điểm chung:

- Họ sử dụng phép tính modular dưới hai modulo khác nhau: modulo văn bản thô và modulo văn bản mật.
- Khóa bí mật là một phần tử của một không gian vector modulo n.
- Tin nhắn được mã hóa bằng cách thêm một thông điệp nhiễu đã mã hóa vào một tích vô hướng lớn.
- Thông điệp nhiễu là một tổng đã mã hóa đúng của thông điệp và một thuật ngữ lỗi hoặc nhiễu nhỏ.

- Tích vô hướng là giữa khóa bí mật và một phần tử ngẫu nhiên của không gian vector, nơi mà phần tử ngẫu nhiên này được cung cấp như một phần của văn bản mật.

- Điều này trông giống như $(A, <A, S>$ + đã mã hóa$(m, e))$, trong đó $A$ là một phần tử của không gian vector.

- Nếu khóa bí mật đã biết, thì tích vô hướng có thể được trừ ra, chỉ còn lại thông điệp đã mã hóa và nhiễu. Nhờ cách đặc biệt mà thông điệp và nhiễu được mã hóa, nhiễu có thể được loại bỏ khỏi mã hóa, chỉ còn lại thông điệp.

- Có hai phương pháp thông thường để lưu trữ thông điệp và nhiễu trong các hệ thống $LWE$: bạn có thể lưu trữ thông điệp trong các bit cao của mẫu $LWE$ và nhiễu trong các bit thấp, hoặc ngược lại.

- Một số ví dụ về các lược đồ $LWE$ nơi mà thông điệp được lưu trữ trong các bit cao là $Regev09$ và $BFV$.
- Một ví dụ về một lược đồ $LWE$ nơi mà thông điệp được lưu trữ trong các bit thấp là $BGV$.
- **Thuật toán loại trừ Gauss (Gauss elimination algorithm)** có hiệu quả trong việc giải một hệ phương trình $m$, tìm $s = (s_1,s_2, . . . ,s_n)$ ở dạng sau:
$$a_{11}s_1 + a_{12}s_2 + ... + a_{1n}s_n = b_1$$ $$a_{21}s_1 + a_{22}s_2 + ... + a_{2n}s_n = b_2$$ $$.$$ $$.$$ $$a_{m1}s_1 + a_{m2}s_2 + ... + a_{mn}s_n = b_m$$

- Một ví dụ về hệ phương trình trên ở dạng ma trận, cho ma trận $A$ $m×n$, ma trận $s$ $n×1$ và ma trận $b$ $n×1$, sẽ giống như $A·s= b$, trong đó
$$A= \begin{bmatrix}
11 \ 2 \ \ldots \ 3 \\
1 \ 4 \ \ldots \ 1 \\
\vdots \ \vdots \ \ddots \ \vdots \\
5 \ 3 \ \ldots \ 9
\end{bmatrix},
s = \begin{bmatrix}
s_1 \\
s_2 \\
\vdots \\
s_n
\end{bmatrix},
b = \begin{bmatrix}
8 \\
13 \\
\vdots \\
2
\end{bmatrix}$$
- Rõ ràng là bằng cách thêm ma trận $n×1$, ma trận $e$ vào tích $A · s$, ngay cả với các giá trị nhỏ, hệ phương trình trở thành: $$A · s + e = b$$
- LWEP phát biểu rằng, với một vectơ bí mật $s = (s_1,s_2, ...,s_n) ∈ \mathbb{Z}^n$ với các số nguyên hệ số và m phương trình tuyến tính, sao cho:
$$a_{11}s_1 + a_{12}s_2 + ... + a_{1n}s_n \approx b_1$$ $$a_{21}s_1 + a_{22}s_2 + ... + a_{2n}s_n \approx b_2$$ $$.$$ $$.$$ $$a_{m1}s_1 + a_{m2}s_2 + ... + a_{mn}s_n \approx b_m$$
- Thêm một lỗi nhỏ vào mỗi phương trình sẽ phục hồi s. Biểu tượng "≈" được sử dụng trong một lỗi nhất định giá trị tiếp cận phản hồi thực tế.
- Bài toán nghiệm số nguyên ngắn: cho m vectơ ngẫu nhiên đồng đều $a_i \in \mathbb{Z}^n_q$ tạo thành các cột của ma trận $A \in \mathbb{Z}^{n×m}_q$ , tìm một vectơ số nguyên khác không $z \in \mathbb{Z}^m$ của chuẩn $∥z∥ ≤ β$, sao cho:
$$f_A(Z)= Az= \sum_{i}{a_iz_i}= 0 \in \mathbb{Z}^n_q.$$

- Cho $ε = ε(n)$ là một hàm không đáng kể của $n$, và cho $p = p(n)$ là một số nguyên cùng với $a = a(n) ∈ (0, 1)$ sao cho $ap > 2 \sqrt{n}$. Giả sử rằng có thể truy cập một oracle $W$ giải $LWE_{p,Ψ_a}$ cho một số lượng mẫu đa thức. Khi đó, tồn tại một thuật toán lượng tử hiệu quả cho $DGS_{\sqrt{2n}·ηε(L)/a}$. Định lý này kết nối bài toán lattice trong trường hợp xấu nhất với bài toán LWE, cung cấp một dấu hiệu mạnh mẽ về khó khăn của bài toán LWE. Đối với $a$ dương, $\bar{Ψ}_a$ biểu thị phân bố trên $\mathbb{Z}_q$ bằng cách lấy mẫu một biến ngẫu nhiên có giá trị trung bình là 0 và độ lệch chuẩn là $aq/ \sqrt{2π}$, với kết quả được làm tròn đến số nguyên gần nhất và modulo $q$ giảm.
- Tương tự: giả sử có quyền truy cập vào một oracle giải bài toán LWE với các tham số $n$, $m$, $q$, $\bar{Ψ}a$, trong đó $ap > 2 \sqrt{n}$, $q ≤ \text{poly}(n)$ là số nguyên tố và $m ≤ \text{poly}(n)$. Khi đó, tồn tại một thuật toán lượng tử chạy trong thời gian $\text{poly}(n)$ để giải quyết các vấn đề lattice (trường hợp xấu nhất) $SIVP{\tilde{Ω}(n/a)}$ và biến thể quyết định của $SVPO_{\tilde{Ω}(n/a)}$ trong bất kỳ lattice nào có chiều $n$.

## Một số chall liên quan
### LWE High Bits Message
**Chall:**
- [lwe-high-bits.sage](https://cryptohack.org/static/challenges/lwe-high-bits_a83f7bfc0f6e3bfd1b962842feb5d91d.sage)
- [output.txt](https://cryptohack.org/static/challenges/output_575f13474e5a8cc76e938508bce813c2.txt)
**Solve:**
- Từ chall ta biết được cách encypt:
- Chọn ngẫu nhiên $A$, một phần tử ngẫu nhiên của không gian vector $\mathbb{Z}_q^n$.
- Lấy error-term $e$ là một số nguyên trong khoảng $[\frac{-\Delta}{2}; \frac{\Delta}{2}]$.
- Tính $b= <A, S>+ \Delta*m+e$.
- Ta sẽ decrypt dựa vào $(A, b)$ như sau:
- Tính $x= b- <A, S> mod\ q$ và sau đó hiểu $x$ như một số nguyên.
- Tính $m= round(\frac{x}{\Delta})$.

from sage.all import *
n = 64
p = 257
q = 0x10001
delta = round(q / p)
S = [55542, 19411, 34770, 6739, 63198, 63821, 5900, 32164, 51223, 38979, 24459, 10936, 17256, 20215, 35814, 42905, 53656, 17000, 1834, 51682, 43780, 22391, 33012, 61667, 37447, 16404, 58991, 61772, 44888, 43199, 32039, 26885, 17206, 62186, 58387, 57048, 38393, 29306, 58001, 57199, 33472, 56572, 53429, 62593, 14134, 40522, 25106, 34325, 37646, 43688, 14259, 24197, 33427, 43977, 18322, 38877, 55093, 12466, 16869, 25413, 54773, 59532, 62694, 13948]
A = [13759, 12750, 38163, 63722, 39130, 22935, 58866, 48803, 15933, 64995, 60517, 64302, 42432, 32000, 22058, 58123, 53993, 33790, 35783, 61333, 53431, 43016, 60795, 25781, 28091, 11212, 64592, 11385, 24690, 40658, 35307, 63583, 60365, 60359, 32568, 35417, 22078, 38207, 16331, 53636, 28734, 30436, 18170, 15939, 966, 48519, 41621, 36371, 41836, 4026, 33536, 57062, 52428, 59850, 476, 43354, 61614, 32243, 42518, 19733, 63464, 29357, 56039, 15013]
b = 44007
S_vector = vector(GF(q), S)
A_vector = vector(GF(q), A)
x = b - (A_vector.dot_product(S_vector)) % q
m = int(round(int(x) / delta))
print(m)

- Run code ta thu được giá trị của m là 201. Cũng chính là giá trị flag ta cần tìm.
> Flag: 201
### LWE Low Bits Message
**Chall:**

- [lwe-low-bits.sage](https://cryptohack.org/static/challenges/lwe-low-bits_a2c45284086e181a601486fe22f873ff.sage)
- [output.txt](https://cryptohack.org/static/challenges/output_9eb8e78124c8c48ec9eb687bf1d10a4e.txt)
**Solve:**
- Dựa theo chall ta biết được cách encrypt như sau:
- Lấy $A$ ngẫu nhiên, $A \in \mathbb{Z}_p^n$
- Lấy error-term $e$ là một số nguyên trong khoảng $[\frac{-q/p}{2}; \frac{q/p}{2}]$.
- Tính $b = <A,S> + m + p * e$.
- Ta sẽ decrypt như sau:
- Tính $x = b - <A,S> centered\ mod\ q$, $centered\ mod\ q$ là mod q nhưng giá trị sẽ thuộc $[(-q/2, q/2)]$ thay vì $[0, q- 1]$ như thông thường.
- Tính $m= x mod p$.

import numpy as np

def decrypt(S, A, b, p, q):
    inner_product = np.dot(A, S)
    x = (b - inner_product) % q
    if x > q / 2:
        x -= q
    m = x % p
    return m
S = (10082, 48747, 17960, 55638, 37012, 51876, 10128, 37750, 7608, 58952, 33296, 25463, 38900, 85, 65248, 42153, 44966, 31594, 40676, 56828, 30325, 38502, 65083, 7497, 2667, 54022, 24029, 32162, 57267, 12253, 6668, 5181, 14906, 51655, 61347, 4722, 22227, 23606, 63183, 52860, 1670, 31085, 42633, 47197, 7255, 16150, 9574, 62956, 26742, 57998, 49467, 31224, 60073, 12730, 41419, 41042, 53032, 16339, 32913, 16351, 34283, 47845, 3617, 35718)
A = (53751, 21252, 55954, 16345, 60990, 2822, 56279, 37048, 36153, 52141, 2121, 56565, 48112, 43755, 12951, 22539, 29478, 28421, 62175, 10265, 36378, 21305, 42402, 26359, 939, 60690, 1161, 65097, 34505, 19777, 29652, 42868, 49148, 38296, 31916, 25606, 18700, 12655, 35631, 64674, 29018, 21021, 14865, 40196, 14036, 40278, 37209, 35585, 34344, 33030, 285, 58536, 56121, 40899, 24262, 62326, 57433, 5765, 24456, 28859, 45170, 14799, 21567, 55484)
b = 11507
p = 257
q = 65537
n = 64
m = decrypt(S, A, b, p, q)
print(m)

> Flag: 147