Giáo sư của bạn đang nói về tối ưu hóa tương đối phổ biến sau đây
Để cho $\mathcal{K}$ là một tập hợp, và để cho $\mathsf{Sample} : \{0,1\}^r\to\mathcal{K}$ là một thuật toán, trên đầu vào $r$ các bit ngẫu nhiên thống nhất, xuất ra một phần tử $k\in \mathcal{K}$.
Nếu $\mathsf{PRG} : \{0,1\}^s\to\{0,1\}^r$ là một PRG, sau đó cho $s\leftarrow\{0,1\}^s, r\leftarrow\{0,1\}^r$, sự phân phối của
$$\mathsf{Sample}(\mathsf{PRG}(s))\approx_c \mathsf{Sample}(r)$$
không thể phân biệt được về mặt tính toán.
Bằng chứng về điều này là tầm thường. Bằng sự an toàn của PRG, $\mathsf{PRG}(s) \approx_c r$. Áp dụng thuật toán (hiệu quả) $\mathsf{Sample}$ duy trì tính không thể phân biệt tính toán (nếu không thì $\mathsf{Sample}$ sẽ là một đối thủ hiệu quả chống lại PRG).
Về cơ bản, nếu công trình cuối cùng của bạn cần một $s$khóa -bit, thường có thể đủ để khóa là một $r$-bit hạt giống PRG, sau đó kéo dài phần này thành $s$ bit với PRG.
Có một số chi tiết cụ thể để chỉ ra ở trên:
Khóa cuối cùng được tạo từ $\mathsf{Sample}(r)$ bản thân nó không nhất thiết phải là ngẫu nhiên thống nhất (mặc dù đây là trường hợp phổ biến nhất cho đến nay).
Người ta có thể làm suy yếu các giả định về kết quả trên hơn nữa --- bằng cách kêu gọi các bộ trích xuất ngẫu nhiên, đầu vào $r$ bản thân nó không cần phải đồng nhất, mà thay vào đó yêu cầu "đủ entropy tối thiểu" theo cách có thể được thực hiện chính xác.
Bạn vẫn cần trao đổi khóa. Trò chơi bảo mật của PRG yêu cầu hạt giống của PRG phải được giữ bí mật để giữ an ninh, vì vậy bạn vẫn cần đảm bảo rằng Eve không có quyền truy cập vào hạt giống (như bạn đã đề cập).
Tất cả sự tối ưu hóa này nói rằng "tải trọng" của trao đổi khóa có thể được thực hiện nhỏ hơn bằng cách sử dụng PRG (đặc biệt, nó có thể được $r$ bit hơn là $s$ chút ít).
Có một tối ưu hóa liên quan (khác biệt theo một cách tinh tế) mà nó cũng có thể đáng để thảo luận.
Thông thường trong mật mã (đặc biệt, trong mật mã mạng và mật mã dựa trên mã hóa), người ta phải truyền một phần tử ngẫu nhiên lớn, thống nhất.
Cụ thể, giả định Học với Lỗi là về các "mẫu" của LWE:
$$ (A, As+e)$$
Tôi sẽ không bận tâm xác định mọi thứ trong ví dụ này, và thay vào đó hãy nói rằng $A$ thường là một ma trận ngẫu nhiên thống nhất, có kích thước $\khoảng 1-10kb$, tùy thuộc vào sơ đồ cụ thể.
Bạn có thể muốn thay thế đối tượng ngẫu nhiên thống nhất này bằng hạt PRG $s$, cái nào sau đó có thể mở rộng một cách xác định thành giá trị ngẫu nhiên $A$ sau. Vì hạt PRG theo thứ tự $\khoảng 128$ bit, đây là mức tăng (tiềm năng) đáng kể.
Tuy nhiên, đây không phải là một tối ưu hóa hợp lệ vì điểm thứ 3 ở trên --- bạn không thể sử dụng PRG để "nén" một giá trị ngẫu nhiên đồng nhất thành một hạt giống ngắn theo cách này nếu sau đó lược đồ của bạn công khai giá trị ngẫu nhiên đồng nhất này. Hoặc bạn có thể, nhưng đối với các PRG cụ thể, điều này hoàn toàn có thể phá vỡ tính bảo mật.
Vẫn còn những điều tương tự bạn có thể làm với những thứ được gọi là hàm đầu ra có thể mở rộng (vì bất kỳ lý do gì, từ viết tắt là XOF). Đây là các nguyên hàm dựa trên hàm băm (đại khái) được sử dụng khi một người muốn các thuộc tính giống PRG, nhưng với một hạt giống công khai.
Dù sao, việc sử dụng XOF để nén một giá trị ngẫu nhiên lớn đồng đều là một cách tối ưu hóa cực kỳ phổ biến. Tôi khá chắc chắn rằng cả hai công ty lọt vào vòng chung kết NIST PQC dựa trên LPR (Sabre/Kyber) đều sử dụng tối ưu hóa này, mặc dù bất kỳ triển khai cụ thể nào cũng có thể sai lệch một chút so với thông số kỹ thuật và bao gồm/không bao gồm tối ưu hóa.
