RLWE giải thích

Trong RLWE, ta thường chọn vành đa thức sau, trong đó q là số nguyên tố, và n là lũy thừa của 2, vd $2^k$ $$\mathbb Z_q[X]/(X^n + 1)$$

Chúng ta biết rằng ${X^{2^k}} + 1$ là một đa thức bất khả quy dưới $Z$, bởi vì Đa thức Cyclotomic, nhưng trong cái này câu hỏi, xem xét $$\mathbb Z_{17}[X]/(X^4 + 1)$$ $(X^4 + 1)$ có thể được nhân tố thành $$\mathbb (X^2 + 4)(X^2 - 4) = X^4 - 16 = X^4 + 1$$ bởi vì $Z_{17}$, hơn nữa nó thậm chí có thể được nhân tố thành $(x + 15)(x + 9)(x + 8)(x + 2)$ Dưới $Z_{17}$

Vậy thì tại sao chúng ta cần phải chọn một đa thức bất khả quy như ${X^{2^k}} + 1$ ở vị trí đầu tiên khi nó có thể giảm theo $Z_q$, hơn nữa những lợi thế của việc lựa chọn là gì ${X^{2^k}} + 1$ như là của chúng ta lý tưởngvà việc chọn một số nguyên tố đủ lớn q(lớn hơn nhiều so với 17) có ngăn kịch bản trên xảy ra không?

Cảm ơn!

Các đa thức cyclotomic được sử dụng trong các bằng chứng rằng các vấn đề về mạng trong trường hợp xấu nhất giảm xuống RLWE. Nếu bạn cố gắng khởi tạo RLWE bằng các đa thức khác, thì bạn không có những đảm bảo chính thức như vậy về độ khó của bài toán. Bạn có thể kiểm tra bộ slide này của Peikert để giới thiệu, sau đó đọc tài liệu tham khảo nếu bạn muốn biết thêm chi tiết.

Và lựa chọn $q$ sao cho đa thức cyclotomic không tách hoàn toàn là vô ích, vì độ khó của bài toán RLWE chỉ phụ thuộc vào độ dài bit của $q$, không phải trên định dạng của nó.

Nhân tiện, khi triển khai BGV, FV, CKKS hoặc các kế hoạch khác dựa trên RLWE, chúng tôi thường hạn chế các lựa chọn của mình về $q$ ép buộc $X^n + 1$ để tách hoàn toàn, để chúng ta có thể sử dụng Biểu diễn RNS (còn gọi là double-CRT).