Điểm:3

Việc mã hóa cứng một phần tử của ngôn ngữ thành trình mô phỏng có phổ biến/hợp lệ không?

lá cờ us

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$$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ì đó?

Điểm:2
lá cờ us

Trên thực tế, tôi đã nhầm lẫn mà không có lý do (cảm ơn Michael): chúng tôi chỉ có thể xác định hai trò chơi lai (chúng tôi chỉ phác thảo bằng chứng ở đây):

  1. trong trò chơi đầu tiên, chúng tôi thay thế $\textsf{Bằng chứng}(k, (d, r))$ ($r$ là tính ngẫu nhiên được sử dụng trong mã hóa) với $Sim(k)$: vậy tin nhắn được gửi là bây giờ $(k, Sim(k))$. Không thể phân biệt với $(k,\textsf{Bằng chứng}(k,(d,r)))$ do giao thức là ZK, và $k$ bằng ngôn ngữ thích hợp (nghĩa là nó là mã hóa của một $d \in \mathcal{L}$).
  2. Sau đó, trong phép lai thứ hai, chúng tôi thay thế $k$ trong cả tin nhắn và Trình mô phỏng bằng một $k'$ đến từ một mã hóa ngẫu nhiên $d$ (có thể không thuộc $\mathcal{L}$): tin nhắn mới là $(k', Sim(k'))$. Không thể phân biệt nó với $(k, Sim(k))$ hoặc chúng ta có thể sử dụng trình mô phỏng này để phá vỡ IND-CPA: ý tưởng đơn giản là yêu cầu đối thủ chạy $Sim$ về mã hóa đầu vào $e$, sau đó gửi $(e,Sim(e))$ đến người phân biệt. Geoffroy cũng đưa ra nhận xét rằng ở đây chúng ta cần IND-CPA chống lại đối thủ không thống nhất (dù sao đó cũng là định nghĩa tiêu chuẩn). lý do là $\stackrel{comp}{\equiv}$ được xây dựng cho các bộ phân biệt không đồng nhất: do đó, nếu một bộ phân biệt không đồng nhất có thể phá vỡ IND-CPA, thì bước này không hợp lệ đối với các bộ phân biệt không đồng nhất như vậy.

Liên quan đến trình giả lập không đồng nhất (cảm ơn Geoffroy đã làm rõ) định nghĩa tiêu chuẩn yêu cầu trình giả lập thống nhất. Tuy nhiên, việc có một trình giả lập không đồng nhất sẽ mang lại một số đảm bảo và hầu hết thời gian có một trình giả lập không đồng nhất cũng tốt. Lý do là chúng tôi hy vọng tính bảo mật sẽ được duy trì ngay cả đối với các trình xác minh không đồng nhất không trung thực, vì vậy sẽ hợp lý khi cho phép trình giả lập cũng không đồng nhất vì nó chịu trách nhiệm tái tạo đầu ra của trình xác minh.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.