Đầu tiên, đã có công việc tiếp theo đối với BPR, bao gồm cả một nghiên cứu thực tế. PRF và PRG. Ở đây "thực tế" có nghĩa là cực nhanh --- ~5 chu kỳ mỗi byte, (và nhỏ bằng ~3 đối với PRG iirc). Điều này nằm trong hệ số 10 của AES khi sử dụng AES-NI. Có một vài cảnh báo về điều này mặc dù:
- Các phím rất lớn
- Tôi tin rằng hướng dẫn AVX được sử dụng, vì vậy một số tăng tốc phần cứng được sử dụng
- Rất nhỏ thông số được chọn.
Các tham số nhỏ này sao cho tương đương LWR/LWE không còn được biết là giữ [1], và hơn nữa, thực sự không có bất kỳ sự giảm thiểu có ý nghĩa nào đối với một vấn đề mạng cứng. Do đó, các thông số/bảo mật được chọn cụ thể bằng cách phân tích một số cuộc tấn công đã biết. Điều này nghe có vẻ như nó sẽ được bạn quan tâm.
- Mối quan hệ giữa k, n và m là gì? Làm thế nào lớn p và q phải được?
Nó phụ thuộc vào nếu bạn muốn nó được có thể chứng minh là an toàn hoặc an toàn theo kinh nghiệm. Để bảo mật có thể chứng minh được, định lý 5.2 của bài báo mà bạn liên kết dường như cung cấp cho bạn chính xác mối quan hệ mà bạn muốn. Đối với bảo mật heuristic (sử dụng các tham số nhỏ hơn), những điều liên quan cần xem xét là:
- phần 4 của bài báo PRF, và
- phần 3 của bài báo PRG.
nhưng chúng không đưa ra những bất đẳng thức đẹp mà bạn có thể muốn, bởi vì những bất đẳng thức như vậy không được biết đến.
Thay vào đó, họ đánh giá một số cuộc tấn công đã biết để có các lựa chọn tham số cụ thể.
- Làm thế nào thời gian mà thuật toán được biết đến nhiều nhất để phá vỡ tính bảo mật của chức năng này chia tỷ lệ với k, n và m?
Xem phần 4 của bài báo PRF và phần 3 của bài báo PRG, trong đó một số tính toán có liên quan được thực hiện.
3.a Đầu ra của F là một ma trận. Entropy của ma trận nghĩa là gì?
Nghiêm túc mà nói, không có gì. Entropy là một thuộc tính của phân phối xác suất, vì vậy xác nhận quyền sở hữu sẽ chỉ có ý nghĩa nếu một người xem $F$ không phải là một ma trận, mà là một phân phối trên các ma trận. Để có được một số ý tưởng về ý nghĩa của các tác giả, hãy để $q = p_0 p_1$ là một nửa số nguyên tố.
Sau đó nếu $A, S_1,\dots S_k$ được phân phối sao cho (với xác suất 1):
- $A\bmod p_0 \equiv 0$, và
- $S_i\bmod p_1\equiv 0$ cho tất cả $i$,
sau đó $F(A, S_1,\dots, S_k) \equiv 0\bmod q$ liên tục, vì vậy PRF sẽ có thể dự đoán được. Việc hạn chế để $A, S_i$ không thể đảo ngược $\bmod q$ dừng sự cố cụ thể (tiềm năng) này (và có thể hơn thế nữa).
3.b Và, câu lệnh này có chỉ ra rằng F là hàm một đối một không?
Không, nhưng nó không được mong đợi.Chúng tôi muốn $F$ không thể phân biệt được với một chức năng ngẫu nhiên. Lưu ý rằng các hàm ngẫu nhiên không phải là 1-1 (bạn có thể định lượng điều này thông qua một kỹ thuật gọi là "chuyển đổi PRP-PRF", nhưng điều này không đặc biệt phù hợp).
[1] Lưu ý rằng đối với hầu hết các nguyên mẫu dựa trên mạng "thực tế", đây đã là trường hợp --- ví dụ: SABER tự dựa trên tính bảo mật cụ thể của MLWR mô-đun nhỏ, mặc dù mô-đun của nó là $2^{13}\xấp xỉ 8k$ Là nhiều lớn hơn mô đun của $q = 257$ mà các PRF/PRG này sử dụng. Điều này phần nào có liên quan, vì gần đây người ta đã thảo luận rằng LWR mô-đun nhỏ không được phân tích mật mã tốt. Nhìn thấy chủ đề nhóm google NIST PQC này. Kể từ chủ đề này vào khoảng tháng 12, mọi người đã chạy một số thử nghiệm (và không tìm thấy bất kỳ điều gì bất ngờ), nhưng từ chủ đề này, có vẻ như mọi người chưa thử phân tích trực tiếp LWR mô-đun nhỏ cho đến một hoặc hai tháng trước.
Có một số tình huống mà người ta có thể sử dụng các nguyên mẫu dựa trên LWR thực tế và có được sự bảo mật có thể chứng minh được dựa trên các vấn đề về mạng, nhưng "tiêu chuẩn" duy nhất mà tôi biết về điều này là của Sam Kim (Key Homomorphic) PRF dựa trên lưới. Hart Montgomery cũng có một Phiên bản không chuẩn của LWR ông có thể chứng minh an ninh cho.
