Vâng, nó vẫn còn khó thông qua một đối số lai đơn giản.
Về cơ bản, đối với $i\in[k]$ xác định "phân phối hỗn hợp"
$$H_i = (A, A\vec s_1 + \vec e_1,\dots, A\vec s_i + \vec e_i, \vec u_{i+1},\dots, \vec u_k).$$
Sau đó, vấn đề phân biệt giữa $H_i$ và $H_{i+1}$ có thể được coi là có thể rút gọn thành bài toán LWE.
Khi sử dụng điều này để phân tích cụ thể mọi thứ, điều này cho phép người ta tận dụng lợi thế của việc phân biệt giữa $H_0$ và $H_k$ qua $k$ gấp nhiều lần lợi thế của bộ phân biệt LWE.
Lập luận này (và nói chung là kỹ thuật sử dụng lại $A$) ngày trở lại ít nhất Chức năng Trapdoor tổn hao và ứng dụng của chúng của Peikert và Waters năm 2008.
Nó có một số lợi ích hợp lý nhẹ, cụ thể là:
- về nguyên tắc người ta có thể tiêu chuẩn hóa một ma trận duy nhất $A$ mà tất cả người dùng sử dụng (tương tự như cách các nhóm DDH được chuẩn hóa) hoặc thậm chí
- người ta có thể "tái sử dụng" một $A$ trong một khoảng thời gian tương đối ngắn, nhưng vẫn không tầm thường, chẳng hạn như 1 giờ.
Mặc dù vậy, nó không còn được hấp dẫn nhiều nữa.
Điều này là vì hai lý do chính
- người ta có thể giảm được kích thước của $A$ bằng cách thu hút các phiên bản có cấu trúc của LWE (đồng thời nâng cao hiệu quả của các hoạt động có liên quan) và
- trong thực tế người ta không thường xuyên gửi $A\in\mathbb{Z}_q^{n\times m}$ với chi phí của $nm\log_2q$ bit (lớn, dẫn đến việc tìm kiếm các đối số khấu hao giống như đối số bạn đề xuất). Thay vào đó, bạn chỉ cần gửi một "hạt giống" $\{0,1\}^\lambda$, được mở rộng thành một ma trận ngẫu nhiên $A$ sử dụng chức năng đầu ra có thể mở rộng tại đích. Hầu hết các ứng cử viên NIST PQC sử dụng phương pháp này.
Cũng cần nhắc lại rằng ý tưởng về một "trường hợp LWE được tiêu chuẩn hóa" ở trên có một vài lý do thực tế khiến nó có thể không thông minh trong thời gian dài, cụ thể là
nó mở ra cho bạn các cuộc tấn công tính toán trước (tương tự như các tiêu chuẩn hóa nhóm DDH khác, chẳng hạn như cuộc tấn công LogJam), và quan trọng hơn
người ta có thể xây dựng "các phiên bản LWE có cửa hậu" --- đại khái là phân phối các ma trận ngẫu nhiên $A$ không thể phân biệt về mặt tính toán với ngẫu nhiên, nhưng có một "cửa sập" cho phép một người phá vỡ LWE.
Phiên bản LWE có cửa hậu tương đối đơn giản (không may là tôi không nhớ đã gán nó cho ai).
Nhớ lại rằng giả định NTRU tạo khóa một khóa công khai $h$, và khóa bí mật $f$, như vậy mà $hf = g$ nhỏ".
Bằng cách sử dụng dạng "ma trận" thích hợp của sự vật, chúng ta có được ma trận $H, F$ như vậy mà:
- $HF = G$ là nhỏ, và
- $H$ không thể phân biệt về mặt tính toán với ngẫu nhiên thống nhất.
Sau đó, nếu chúng ta sử dụng $H^t$ dưới dạng ma trận ngẫu nhiên của một cá thể LWE, ví dụ: nhận một mẫu $(H^t, H^t s + E)$, chúng ta có thể dễ dàng phá vỡ giả định LWE bằng cách sử dụng ma trận ngẫu nhiên này, như $F^t H^t s + F^t E = Gs + F^t E$ là "nhỏ" (tôi tin). Đây là tất cả với ma trận $H$ không thể phân biệt về mặt tính toán với ngẫu nhiên theo NTRU, ví dụ: cửa hậu này $H$ rất khó phát hiện.
