1.4. FALCON

[TODO] Viết lại.

Falcon làm việc với các phần tử thuộc vành \(\dfrac{\mathbb{Q}[x]}{\phi(x)}\), ở đây \(\phi(x) = x^n + 1\) và \(n = 2^k\).

Ở đây \(\phi(x)\) là đa thức cyclotomic nên ta có

\[\phi(x) = \prod_{k \in \mathbb{Z}_m^{\times}} (x - \xi^k)\]

với \(m = 2n\) và \(\xi\) là nghiệm bậc \(m\) của đơn vị.

\(\mathbb{Z}_m^{\times}\) là nhóm các phần tử khả nghịch của \(\mathbb{Z}_m\) đối với phép nhân.

Ta có quan hệ

\[\mathbb{Q} \subseteq \mathbb{Q}[x] / (x^2 + 1) \subseteq \cdots \subseteq \mathbb{Q}[x] / (x^{n/2} + 1) \subseteq \mathbb{Q}[x] / (x^n + 1)\]

và chuỗi đẳng cấu

\[\mathbb{Q}^n \cong (\mathbb{Q}[x] / (x^2 + 1))^{n / 2} \cong \cdots \cong (\mathbb{Q}[x] / (x^{n/2} + 1))^2 \cong \mathbb{Q}[x] / (x^n + 1).\]

Đặt

\[a(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1} \in \mathcal{Q}, b(x) = b_0 + b_1 x + \cdots + b_{n-1} x^{n-1} \in \mathcal{Q}\]

với \(\mathcal{Q}\) là vành \(\mathbb{Q}[x] / (x^n + 1)\).

Kí hiệu \(a^*(\xi)\) và gọi là Hermitian adjoint của \(a\), là phần tử duy nhất của \(\mathcal{Q}\) sao cho mọi nghiệm \(\xi\) của \(\phi(x)\) ta đều có \(a^*(\xi) = \overline{a(\xi)}\), trong đó \(\overline{\cdot}\) là liên hợp (conjunction) trên \(\mathbb{C}\).

Với \(\phi(x) = x^n + 1\) thì Hermitant adjoint là \(a^* = a_0 - (a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1})\).

Ta mở rộng định nghĩa (Hermitian) adjoint lên vector và ma trận.

Adjoin \(B^*\) của ma trận \(B \in \mathcal{Q}^{n \times m}\) (tương tự với vector) là adjoint của từng phần tử (component-wise):

\[\begin{split}B = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \Rightarrow B^* = \begin{pmatrix} a^* & b^* \\ c^* & d^* \end{pmatrix}.\end{split}\]

Tích vô hướng (inner product) của hai đa thức \(a(x)\) và \(b(x)\) là

\[\langle a, b \rangle = \dfrac{1}{\deg f(x)} \cdot \sum_{\phi(\xi) = 0} a(\xi) \cdot \overline{b(\xi)}\]

đây gọi là cách biểu diễn bằng fast fourier transform.

Ta mở rộng lên vector, với \(\overline{u} = (u_i)_i\) và \(\overline{v} = (v_i)_i\) thuộc \(\mathcal{Q}^m\) thì

\[\langle \overline{u}, \overline{v} \rangle = \sum_{i} \langle u_i, v_i \rangle.\]

Cách chọn \(\phi(x)\) ở trên cho chúng ta tích vô hướng giống thông thường

\[\langle a, b \rangle = \sum_{i=0}^{n-1} a_i b_i\]

đây là cách biểu diễn bằng hệ số.

Ring lattice: với vành \(\mathcal{Q} = \mathbb{Q}[x] / \phi(x)\) và \(\mathcal{Z} = \mathbb{Z}[x] / \phi(x)\), số nguyên dương \(m \geqslant n\) và ma trận full-rank \(B \in \mathcal{Q}^{n \times m}\), ta kí hiệu \(\Lambda(B)\) và gọi lattice sinh bởi \(B\) là tập \(\mathcal{Z}^n\). Khi đó

\[B = \{ \overline{z} \cdot B : z \in \mathcal{Z}^n \}\]

Mở rộng ra, tập \(\Lambda\) là lattice nếu tồn tại ma trận \(B\) sao cho \(\Lambda = \Lambda(B)\).

Ta có thể nói \(\Lambda \subseteq \mathcal{Z}^m\) là lattice \(q\)-phân nếu \(q \mathcal{Z}^m \subseteq \Lambda\).

Discrete Gaussian:

Với \(\sigma, mu \in \mathbb{R}\) mà \(\sigma > 0\), ta định nghĩa hàm Gauss \(\rho_{\sigma, \mu}\) là

\[\rho_{\sigma, \mu} = \exp(-(x - \mu)^2 / (2 \sigma^2)),\]

và phân phối Gauss rời rạc \(D_{\mathbb{Z}, \sigma, \mu}\) trên vành số nguyên là

\[D_{\mathbb{Z}, \sigma, \mu}(x) = \frac{\rho_{\sigma, \mu}(x)}{\sum_{z \in \mathbb{Z}} \rho_{\sigma, \mu}(z)}.\]

Trực giao hóa Gram-Schmidt.

Mỗi ma trận \(B \in \mathcal{Q}^{n \times m}\) có thể phân tích thành \(B = L \times \tilde{B}\) với \(L\) là ma trận tam giác dưới (lower triangle) với các phần tử trên đường ché chính bằng \(1\).

Các hàng \(\tilde{b}_i\) của \(\tilde{B}\) kiểm tra \(\langle b_i, b_j \rangle = 0\) với \(i \neq j\). Khi \(B\) full-rank thì phân tích này là duy nhất và được gọi là trực giao hóa Gram-Schmidt (Gram-Schmidt orthogonalization GSO).

Ta gọi chuẩn Gram-Schmidt (norm) của \(B\) là giá trị

\[\lVert B \rVert_{GS} = \max_{\tilde{b}_i \in \tilde{B}} \lVert \tilde{b}_i \rVert\]

LDL:math:^* decomposition: LDL:math:^* decomposition viết mỗi ma trận Gram full-rank thành tích LDL:math:^* với:

  1. \(L \in \mathcal{Q}^{n \times n}\) là ma trận tam giác dưới với các phần tử \(1\) trên đường chéo chính.

  2. \(D \in \mathcal{Q}^{n \times n}\) là ma trận chéo.

Nếu tồn tại GSO duy nhất \(B = L \cdot \tilde{B}\) và với ma trận Gram \(G\) full-rank thì tồn tại LDL:math:^* decomp duy nhất \(G = LDL^*\).

Nếu \(G = B \cdot B^*\) thì \(G = L \cdot (\tilde{B} \tilde{B}^*) \cdot L^*\) là LDL:math:^* decomp hợp lệ.

Khi đó, \(L \cdot \tilde{B}\) là GSO của \(B\) khi và chỉ khi \(L \cdot (\tilde{B} \cdot \tilde{B}^*) \cdot L^*\) là LDL:math:^* decomp. của \(B \cdot B^*\).

Keys.

Public params.

  1. Đa thức cyclotomic \(\phi(x) = x^n + 1\) với \(n = 2^k\).

  2. Modulus là \(q \in \mathbb{N}^*\) là số nguyên tố, \(\phi(x) \bmod q\) sẽ split (phân rã) trên \(\mathbb{Z}_q[x]\).

  3. Bound (chặn) \(\lfloor \beta^2 \rfloor > 0\).

  4. Độ lệch chuẩn \(\sigma\) và \(\sigma_{\text{min}} < \sigma_{\text{max}}\).

  5. Chữ ký với độ dài (theo byte) là \(\mathtt{sbytelen}\).

Private key

Private key gồm \(4\) đa thức \(f\), \(g\), \(F\), \(G\) thuộc \(\mathbb{Z}[x] / \phi(x)\) với hệ số ngắn, thỏa phương trình

\[f \cdot G - g \cdot F = q \bmod{\phi(x)}.\]

Đa thức \(f\) cũng phải khả nghịch trong \(\mathbb{Z}_q[x] / \phi(x)\).

Cho trước \(f\) và \(g\), ta có thể tính được \(F\) và \(G\) nhưng sẽ rất tốn sức. Do đó ta cần lưu thêm \(F\) và từ \(f\), \(g\) và \(F\) ta sẽ tính lại \(G\).

FFT representation (biểu diễn FFT) của \(f\), \(g\), \(F\) và \(G\) là dạng ma trận

\[\begin{split}\hat{B} = \begin{pmatrix} FFT(g) & -FFT(f) \\ FFT(G) & -FFT(F) \end{pmatrix}.\end{split}\]

Falcon trees. Falcon trees là cây nhị phân được định nghĩa đệ quy như sau:

  1. Falcon tree với độ cao \(0\) gồm một nút đơn với giá trị là \(\sigma > 0\).

  2. Falcon tree với độ cao \(k\) có tính chất:

  • giá trị tại gốc, \(\mathtt{T}.\mathtt{value}\), là đa thức \(l \in \mathbb{Q}[x] / (x^n + 1)\) với \(n = 2^k\);

  • nút là trái và phải, \(\mathtt{T}.\mathtt{leftChild}\) và \(\mathtt{T}.\mathtt{rightChild}\), là Falcon tree với độ cao \(k - 1\).

Nội dung của Falcon tree \(\mathtt{T}\) được tính từ các thành phần \(f\), \(g\), \(F\), \(G\) của private key và được mô tả bởi thuật toán ở sau.

Public key.

Falcon public key \(pk\) tương ứng với private key \(sk = (f, g, F, G)\) là đa thức \(h \in \mathbb{Z}_q[x] / \phi(x)\) thỏa

\[h = g f^{-1} \pmod{\phi(x), q}.\]