Nói chung, nếu bạn đang hỏi về một định nghĩa cụ thể, bạn nên bao gồm một liên kết đến định nghĩa đang được đề cập.
Tuy nhiên, nói chung, người ta biết rằng PKE đòi hỏi mã hóa ngẫu nhiên (hoặc nonce không lặp lại, tôi sẽ bỏ qua điều này).
Điều này có nghĩa là (ngoại trừ trong cài đặt đặc biệt) chức năng:
$$\mathsf{Enc} : \mathcal{PK}\times\mathcal{M}\to\mathcal{C}$$
là một ngẫu nhiên thuật toán (trong đó $\mathcal{PK}$ là không gian của tất cả các khóa công khai).
Bạn luôn có thể [1] viết một thuật toán ngẫu nhiên dưới dạng xác định thuật toán lấy đầu vào là một số chuỗi ngẫu nhiên, tức là viết:
$$\mathsf{Enc}^{det} : \mathcal{PK}\times\mathcal{M}\times\mathcal{R}\to\mathcal{C}$$
ở đâu $\mathsf{Enc}^{det}(pk, m;r)$ mô phỏng thuật toán $\mathsf{Enc}(pk,m)$và khi thuật toán yêu cầu các bit ngẫu nhiên, nó sẽ sử dụng chuỗi (cố định) $r$ như một nguồn của các bit "ngẫu nhiên".
Điều này phù hợp với phép biến đổi FO, vì nó có thể được "phân tích" thành hai bước (các bước $T$-biến đổi và $U$- biến đổi, xem tờ giấy này).
Các $T$-biến đổi sửa đổi $\mathsf{Enc}$ trong hai cách:
phi ngẫu nhiên hóa: Thay vì sử dụng tính ngẫu nhiên $r$, một người sử dụng một lời tiên tri ngẫu nhiên $G$ để thiết lập $r := G(m)$, tức là chọn $\mathsf{Enc}^{det}(pk,m) := \mathsf{Enc}(pk,m; G(m))$
mã hóa lại: Giải mã cũng được sửa đổi, cụ thể là kiểm tra xem $m'\gets\mathsf{Dec}(sk, c)$ mối quan hệ $c = \mathsf{Enc}^{det}(pk, m')$ nắm giữ. Để kiểm tra này có ý nghĩa, mã hóa (tất nhiên) phải mang tính xác định.
Dù sao, để có thể thực hiện bước đầu tiên của $T$-biến đổi, người ta cần biết $\mathcal{R}$, vì bạn cần có thể chọn một nhà tiên tri ngẫu nhiên $G : \mathcal{M}\to\mathcal{R}$. Tiêu biểu $\mathcal{R}$ có thể được viết dưới dạng $\{0,1\}^k$ cho một số $k$ [2].
[1] Có thể có một số bệnh lý ở đây nếu thuật toán ngẫu nhiên có thời gian chạy "đa thức dự kiến", thay vì kết thúc trong một số thời gian chạy đa thức.Tôi sẽ bỏ qua điều này, nó không liên quan đến mã hóa.
[2] Lưu ý rằng có những kế hoạch mà bạn có thể lo lắng rằng $\mathcal{R} \neq \{0,1\}^k$, hoặc thậm chí $\mathcal{R} = \{0,1\}^k$ nhưng sự phân bố của tiếng ồn mà $\mathsf{Enc}$ nhu cầu không thống nhất $\{0,1\}^k$. Tôi đặc biệt nghĩ đến các lược đồ dựa trên mạng tinh thể, trong đó tính ngẫu nhiên thường là "giống như Gaussian" (hoặc nói là nhị thức trung tâm), mặc dù điều này cũng xảy ra đối với các lược đồ dựa trên mã, trong đó tính ngẫu nhiên thường có trọng số cản cố định iirc. Một lời tiên tri ngẫu nhiên thường sẽ có đầu ra $G(m)$ đó là ngẫu nhiên thống nhất trên $\{0,1\}$. Đây không phải là vấn đề thực sự --- người ta có thể sử dụng thuật toán lấy mẫu $\mathsf{Samp} : \{0,1\}^k \to \mathcal{R}$ để chuyển đổi đầu ra của tiên tri ngẫu nhiên sang phân phối mong muốn. Điều này xảy ra ngay cả đối với mã hóa ngẫu nhiên, trong đó thay vì sử dụng RO cho tính ngẫu nhiên, thuật toán sử dụng một số dạng ngẫu nhiên của hệ thống (được giả định là không thể phân biệt bằng tính toán với các bit ngẫu nhiên thống nhất).
