Phiên bản ngắn: Đây có phải là một thông lệ phổ biến (và một thông lệ hợp lệ) để mã hóa cứng một phần tử $d \in \mathcal{L}$ của một ngôn ngữ vào một trình giả lập? (làm cho trình giả lập không đồng nhất và không mang tính xây dựng)
phiên bản dài:
tôi có một câu tục ngữ $P$ thực hiện như sau: phải mất một chuỗi bit $d \in \mathcal{L}$ đối với một số ngôn ngữ trong $\textsf{NP}$, sau đó nó mã hóa $d$ sử dụng mã hóa bảo mật CPA để lấy mã hóa $k$, và nó sẽ gửi bằng chứng Không có kiến thức không tương tác (NIZK) $\pi$ Chứng minh rằng $k$ mã hóa một tin nhắn $d \in \mathcal{L}$. Bây giờ tôi muốn nói rằng chương trình này không rò rỉ nhiều thông tin về $d$, theo nghĩa là tồn tại một trình giả lập $Sim$ sao cho đối với bất kỳ trình xác minh không thống nhất độc hại nào $V^*$:
$$\{Sim(V_\lambda^*)\}_{\lambda,d} \stackrel{comp}{\equiv} \{\textsf{OUT}_{V^*}(P_\lambda(d) \leftrightarrow V^*_\lambda)\}_{\lambda,d}$$
(các $\{X_{\lambda,d}\}_{\lambda,d}\stackrel{comp}{\equiv}\{Y_{\lambda,d}\}_{\lambda,d}$ biểu tượng biểu thị tính không thể phân biệt tính toán: đối với bất kỳ bộ phân biệt không đồng nhất nào $D$, tồn tại không đáng kể $\mu$ như vậy cho tất cả $\lambda \in \mathbb{N},d \in \mathcal{L}$, $|\Pr[D_\lambda(X_d)]-\Pr[D_\lambda(Y_d)]| < \mu(\lambda)$)
Không có phần NIZK, bằng chứng rất đơn giản: trình giả lập của tôi sẽ chọn ngẫu nhiên $d'$ và mã hóa nó thành $k'$: Tôi không phân biệt được $k$ và $k'$ mà không vi phạm bảo mật CPA. Theo trực giác, việc thêm bằng chứng NIZK sẽ không làm rò rỉ thêm thông tin...Tuy nhiên, tôi không chắc chắn cách giải quyết trường hợp đó: Tôi có một ý tưởng, nhưng nó có vẻ khá lạ đối với tôi (tôi chưa bao giờ thấy loại phương pháp đó trước đây) và tôi hơi nghi ngờ về nó.
Vấn đề chính của tôi là nếu tôi nhập ngẫu nhiên $d'$ đến NIZK, sau đó $d'$ có thể không thuộc về $\mathcal{L}$, vì vậy tôi không thể sử dụng trình giả lập NIZK, dự kiến $k$ là một mã hóa của một $d \in \mathcal{L}$. Vì vậy, ý tưởng của tôi là để nói rằng nếu $\mathcal{L}$ không trống, thì tồn tại một chuỗi $d' \in \mathcal{L}$ (có thể bằng hoặc không bằng $d$). Sau đó, nếu tôi mã hóa chuỗi này thành $k'$, $k'$ hiện là một phần tử "hợp lệ" để nhập vào trình mô phỏng NIZK. Vì vậy, bây giờ tôi chỉ có thể chạy trình giả lập NIZK với $k'$ để có được $Sim$ Tôi muốn: bằng chứng cuối cùng về tính không thể phân biệt sẽ thêm một phân phối trung gian, trong đó chúng tôi sử dụng $k$ với trình giả lập NIZK: không thể phân biệt hai trò chơi đầu tiên do thuộc tính NIZK, hai trò chơi thứ hai sẽ không thể phân biệt được do thuộc tính CPA. (Tôi vẫn cần viết bản phác thảo bằng chứng này một cách chính thức để xác minh xem nó có mắc lỗi ngu ngốc hay không).
Tuy nhiên, mã hóa cứng một phần tử của $\mathcal{L}$ vào trong $Sim$ có vẻ hơi kỳ lạ đối với tôi (đáng chú ý là vì trình giả lập không mang tính xây dựng và không đồng nhất vì đối với bất kỳ kích thước nào của $d$ chúng ta cần một sự khác biệt $d'$). Đó có phải là điều gì đó phổ biến/hợp lệ trong bằng chứng Không có Kiến thức hay tôi đang thiếu thứ gì đó?