Biến đổi số luận (Number Theoretic Transform - NTT) là một phép biến đổi được áp dụng trên các vành, cho phép chúng ta tính toán phép nhân của các phần tử trong những vành đó một cách hiệu quả hơn.
Vành được sử dụng trong ML-KEM và ML-DSA là $\mathbb{Z}_q[X]/(X^n + 1)$. Điều này có nghĩa là chúng ta đang làm việc với các đa thức, trong đó các hệ số được biểu diễn dưới dạng số nguyên modulo $q$, và được rút gọn bởi đa thức $X^n + 1$.
Việc cộng một phần tử này với một phần tử khác được thực hiện theo từng hệ số. Tức là, nếu bạn có hai đa thức:
\[\begin{aligned} \mathbf{a} &= a_0 + a_1X^1 + a_2X^2 + \cdots \\ \mathbf{b} &= b_0 + b_1X^1 + b_2X^2 + \cdots \end{aligned}\]thì tổng của chúng là:
\[\mathbf{a} + \mathbf{b} = (a_0 + b_0) + (a_1 + b_1)X^1 + (a_2 + b_2)X^2 + \cdots\]Phép nhân hai đa thức thì phức tạp hơn một chút. Tích của hai đa thức được tính theo quy tắc sau:
\[\mathbf{c}_k = (\mathbf{a} \cdot \mathbf{b})_k = \sum_{i + j = k} a_i b_j\]Vì vậy, đối với mỗi hệ số trong tích, chúng ta cần thực hiện $n$ phép nhân hệ số. Do chúng ta cần làm điều này cho $n$ hệ số của tích, độ phức tạp của phép nhân sẽ là $\mathcal{O}(n^2)$. Với các giá trị $n$ lớn hơn, điều này trở nên rất tốn kém về mặt tính toán.
Để làm cho ML-KEM và ML-DSA nhanh hơn, chúng ta cần tối ưu hóa các phép nhân này. Và đó là lúc NTT xuất hiện. Với NTT, chúng ta có thể triển khai phép nhân đa thức theo một cách hiệu quả hơn. Cuối cùng, độ phức tạp của phép nhân đa thức sẽ chỉ còn là $\mathcal{O}(n \log n)$.
Định lý thặng dư Trung Hoa
Để hiểu NTT dễ dàng hơn, chúng ta hãy xem xét sự tương tự về mặt ý tưởng của việc áp dụng định lý thặng dư Trung Hoa trong RSA. Định lý này xem xét một danh sách $k$ số $a_i$ theo modulo của một số $m_i$ khác. Gọi $N$ là tích của tất cả các module này, tức là
\[N = m_1 \cdot \cdots \cdot m_k.\]Định lý này cho biết rằng danh sách các giá trị của $a_i \pmod{m_i}$ này mô tả chính xác một số nguyên duy nhất $x \pmod{N}$.
Ví dụ, hãy xem xét một hệ đơn giản chỉ có hai module $m_1 = 11$, $m_2 = 23$ và $N = 11 \cdot 23 = 253$:
\[\begin{aligned} x &\equiv 3 &\pmod{11} \\ x &\equiv 21 &\pmod{23} \end{aligned}\]Cách giải trực tiếp nhất là lấy phương trình thứ hai và thử các bội số của $23$ xem liệu phương trình thứ nhất có thỏa mãn hay không:
\[i \cdot 23 + 21 \overset{?}{\equiv} 3 \pmod{11}\]Chúng ta kiểm tra lần lượt $i=0,1,2,3,…$ sẽ thấy rằng $i=4$ thoả mãn.
\[4 \cdot 23 + 21 = 113 \equiv 3 \pmod{11}\]Vậy $x = 113 \pmod{253}$.
Hệ thống số phần dư
Một tính năng đẹp của định lý thặng dư Trung Hoa là việc thực hiện các phép toán trên các giá trị “nhỏ” $a_i$ tương ứng chính xác với việc thực hiện phép toán tương tự với giá trị “lớn” $x$.
Ví dụ, nếu chúng ta nhân các giá trị $a_i$ ở trên với $3$, chúng ta sẽ có:
\[\begin{aligned} x &\equiv 3 \cdot 3 \equiv 9 \pmod{11} \\ x &\equiv 3 \cdot 21 \equiv 17 \pmod{23} \end{aligned}\]Khi chúng ta giải hệ mới này, chúng ta nhận được $3 \cdot 113 = 339 \equiv 86 \pmod{253}$.
Quay lại RSA, chúng ta làm việc với module $N$ rất lớn, thường có kích thước khoảng 4096 bit. Giá trị $N$ này là tích của hai số nguyên tố $p$ và $q$, cả hai đều là 2048 bit và được sử dụng trong quá trình giải mã.
Thực hiện phép nhân trên một số $x$ 4096 bit là rất chậm. Nếu thực hiện phép nhân thông thường trên CPU 64-bit, việc này sẽ liên quan đến việc chia các số thành 64 phần (limbs) mỗi số, và nhân từng phần với nhau. Tức là $64^2 = 4096$ thao tác nhân 64-bit cho mỗi phép nhân 4096-bit!
Tuy nhiên, vì $N = p \cdot q$, chúng ta có thể tối ưu bằng việc áp dụng định lý thặng dư Trung Hoa. Cụ thể, nếu chúng ta đặt $a_1 \equiv x \pmod{p}$ và $a_2 \equiv x \pmod{q}$, chúng ta có thể thực hiện mọi phép tính trên các giá trị nhỏ $a_i$ thay vì giá trị $x$ lớn.
Bây giờ, chúng ta chỉ thực hiện số học trên các số 2048-bit thay vì 4096-bit. Đối với một phép nhân lớn, chúng ta chỉ cần 2048 phép nhân nhỏ. Quá trình tính toán của chúng ta vừa nhanh hơn gấp đôi!
Chia tách đa thức
Trong khi RSA sử dụng phép nhân giữa các số nguyên lớn, ML-KEM và ML-DSA sử dụng phép nhân trên cấu trúc vành. Vành được sử dụng trong các lược đồ này hơi cồng kềnh để lấy ví dụ. Vì vậy chúng ta hãy xem xét một vành “nhỏ” để dễ hiểu và dễ viết:
\[R = \mathbb{Z}_q[X]/(X^n + 1) = \mathbb{Z}_{17}[X]/(X^4 + 1).\]Nếu chúng ta nhân hai đa thức trên vành này trực tiếp theo công thức:
\[\mathbf{c}_k = (\mathbf{a} \cdot \mathbf{b})_k = \sum_{i + j = k} a_i b_j\]thì chúng ta sẽ phải thực hiện $4 \cdot 4 = 16$ phép nhân $a_i \cdot b_i$.
Bây giờ, chúng ta sẽ áp dụng định lý thặng dư Trung Hoa trên vành này. Chúng ta biết rằng module $N = X^4 + 1$. Chúng ta phải tìm $m_1$ và $m_2$ sao cho
\[m_1 \cdot m_2 = X^4 + 1\]Một lựa chọn khả dĩ là:
\[\begin{aligned} m_1 &= (X^2 - 4) \\ m_2 &= (X^2 + 4) \end{aligned}\]Ta có thể kiểm tra nhanh tích của chúng đúng là $X^4 + 1$.
Tiếp đến, chúng ta viết lại vành $R$ thành hai vành nhỏ hơn như sau:
\[\begin{aligned} R_1 &= \mathbb{Z}_{17}[X]/(X^2 - 4) \\ R_2 &= \mathbb{Z}_{17}[X]/(X^2 + 4) \end{aligned}\]Nếu chúng ta muốn biểu diễn một đa thức $\mathbf{a}$ modulo theo các vành nhỏ hơn này, chúng ta chỉ cần sử dụng phép toán modulo. Ví dụ với $\mathbf{a} = 2 + 7X^3$:
\[\begin{aligned} \mathbf{a} &\mod (X^2 - 4) \equiv 2 + 11X \\ \mathbf{a} &\mod (X^2 + 4) \equiv 2 + 6X \end{aligned}\]Bây giờ chúng ta có thể sử dụng các đa thức bậc 1 nhỏ hơn này để thực hiện phép nhân. Để nhân hai tập hợp các đa thức nhỏ hơn, chúng ta chỉ cần nhân 4 cặp hệ số với nhau; tức là tổng cộng 8 phép nhân. Cũng giống như với thuật toán RSA, giờ đây chúng ta chỉ cần một nửa số lượng phép toán nhân.
Xa hơn nữa
Chúng ta lại có thể chia tiếp vành $\mathbb{Z}_{17}[X]/(X^2 - 4)$ thành hai vành bậc 0 bằng cách tìm hai nhân tử của $(X^2 - 4)$. Tương tự như bước ở trên, chúng ta tìm hai đa thức có dạng $(X + \zeta)$ và $(X - \zeta)$ trong đó $\zeta^2 = 4$. Dễ thấy $\zeta = \sqrt{4} = 2$.
Bây giờ chúng ta có hai vành mới là:
\[\begin{aligned} R_{1,1} &= \mathbb{Z}_{17}[X]/(X + 2) \\ R_{1,2} &= \mathbb{Z}_{17}[X]/(X - 2) \end{aligned}\]Tương tự như vậy, chúng ta có thể chia vành $\mathbb{Z}_{17}[X]/(X^2 + 4)$ thành
\[\begin{aligned} R_{2,1} &= \mathbb{Z}_{17}[X]/(X + 8) \\ R_{2,2} &= \mathbb{Z}_{17}[X]/(X - 8) \end{aligned}\]Khi chúng ta nhân các đa thức trong các vành này, chúng ta lại chỉ cần một nửa số phép toán nhân so với ban đầu. Sau khi chia đa thức lớn thành 4 đa thức nhỏ, chúng ta đã tiếp tục làm giảm đi số lượng phép nhân
(to be continued)