Tại sao các tham số (chẳng hạn như mô-đun và kích thước) của mã hóa đồng cấu lại quá lớn?

So với các sơ đồ PQC dựa trên mạng phổ biến, mô đun $q$ và kích thước $n$ của mã hóa đồng hình là rất lớn. Ví dụ, ở Kyber, $n=256, n \times k = \{512,768,1024\}$, $q = 12289$ hoặc $3329$, khi ở FV hoặc các chương trình HE khác, $n$ có thể là $2^{14}$, và $q$ có thể đạt $2^{744}$. Cả hai đều dựa trên vấn đề mạng tinh thể. Tại sao các thông số rất khác nhau?

Tất cả các lược đồ dựa trên (R)LWE đều có các bản mã nhiễu. Nói chung, nếu tiếng ồn nhỏ hơn một phần của q (giả sử, nhỏ hơn q/2), thì quá trình giải mã sẽ hoạt động.

Nếu bạn chỉ muốn mã hóa một tin nhắn và giải mã nó trong tương lai, thì bạn có thể mã hóa bằng tiếng ồn rất lớn, gần bằng q rồi. Nhưng khi nhiễu lớn thì vấn đề LWE khó hơn, vì vậy, với cùng mức độ bảo mật, bạn có thể chọn các thông số nhỏ hơn.

Nhưng đối với các sơ đồ đồng hình, bạn cũng muốn thao tác với các bản mã và các thao tác này làm tăng nhiễu, vì vậy bạn phải bắt đầu với nhiễu nhỏ (ví dụ: nếu các bản mã mới có nhiễu gần bằng q/4, thì một lần bổ sung duy nhất sẽ gây ra nhiễu đến q/2 và không thể thực hiện phép toán đồng cấu nào nữa). Thông thường, các sơ đồ chọn nhiễu ban đầu được giới hạn bởi một số hằng số nhỏ và tăng q để có thêm chỗ cho sự tăng trưởng nhiễu do các hoạt động đồng hình tạo ra. Nhưng sau đó, bài toán LWE trở nên dễ dàng hơn, vì vậy, để đạt được mức độ bảo mật mong muốn, họ phải tăng kích thước, $n$.

Bạn sẽ nhận thấy rằng các sơ đồ có mức tăng nhiễu nhỏ hơn có thể chọn tham số nhỏ hơn nhiều (ví dụ: TFHE sử dụng $n = 2^{10}$ và $q = 2^{32}$).