Bạn có thể. Có một cảnh báo nhất định cần được đề cập ở đây --- độ cứng của vấn đề LWE được kiểm soát (một phần) bởi kích thước của mô đun $q$.
Hai chế độ tham số quan trọng là $q$ hiện tại đa thức lớn trong tham số bảo mật và siêu đa thức lớn.
Mô-đun nhỏ hơn sẽ tốt hơn cho cả hiệu quả và bảo mật.
Tuy nhiên, tôi nghĩ rằng chỉ gần đây chúng ta mới có các PRF mô đun đa thức từ LWE, xem ví dụ cái này.
Cho đến bài báo đó, điều này đã dẫn đến một tình huống buồn cười là chúng ta có thể xây dựng những thứ như FHE cân bằng từ giả định mạng tinh thể yếu hơn so với những gì chúng ta cần để xây dựng PRF.
Đối với siêu đa $q$ mặc dù, có những công trình đơn giản.
Tờ giấy này là một tài liệu tham khảo tốt.
Ý tưởng chính là một mẫu LWE $(a, \langle a,s\rangle + e)$ là giả ngẫu nhiên, vì vậy đây là cơ sở hợp lý cho PRF.
Nếu một người cố gắng viết ra một số ứng cử viên tự nhiên, chẳng hạn như:
$$F_s(a) = \langle a,s\rangle + e\bmod q$$
có hai vấn đề rõ ràng:
đây chỉ là giả ngẫu nhiên nếu $a$ là ngẫu nhiên (vì vậy đây là "PRF yếu" chứ không phải PRF --- chỉ là một mã hóa nguyên thủy hơi khác một chút)
$F_s(a)$ là một chức năng ngẫu nhiên --- lỗi $e$ phải được chọn ngẫu nhiên.
Bạn có thể khắc phục vấn đề thứ hai này bằng cách làm tròn nó thành bội số gần nhất của $p$, tức là viết $F_s'(a) = \lfloor \langle a,s\rangle + e\rceil_p$.
Với điều kiện là $q/p$ đủ lớn, sự lựa chọn ngẫu nhiên của $e$ thường sẽ chỉ ảnh hưởng không đáng kể đến kết quả cuối cùng, vì vậy chúng ta cũng có thể viết hàm (xác định) $F_s'(a) = \lfloor \langle a,s\rangle\rceil_p$.
Ngoài ra, điều này có thể được coi là một PRF yếu được xây dựng từ Học với Làm tròn giả thiết.
Để "nâng cấp" PRF yếu thành PRF tiêu chuẩn, người ta có thể tạo khóa $(A, S_1, \dots, S_k)$, và xác định
$$F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p.$$
Ở đâu $x_i\in\{0,1\}$, và $A, S_1,\dots, S_k$ là các phần tử vành hoặc ma trận có kích thước phù hợp sao cho biểu thức có nghĩa.
Đây chính xác là cấu trúc được thực hiện trong bài báo thứ hai trong phần 5.
Tóm tắt:
- Đúng chúng ta có thể xây dựng PRF từ các vấn đề LWE/mạng
- Thực hiện nó một cách hiệu quả (từ mô đun nhỏ) khó một cách đáng ngạc nhiên, nhưng giờ đây đã biết cách thực hiện (xem bài báo đầu tiên)
- Thực hiện nó từ bài toán LWR thì đơn giản về mặt khái niệm, nhưng chúng ta chỉ có thể đặt tính an toàn của bài toán LWR dựa trên bài toán LWE đối với mô đun lớn.
