Bằng chứng bảo mật liên quan đến một phản ví dụ không có kiến ​​thức an toàn trong mô hình độc lập nhưng không an toàn trong mô hình UC

Lý lịch

Phản ví dụ về kiến ​​thức không (ZK) sau đây được mô tả trong tác phẩm của Canetti [Bảo mật và Thành phần của Giao thức Mật mã: Hướng dẫn, trang 26] để chỉ ra rằng tồn tại một số giao thức an toàn trong mô hình độc lập nhưng không an toàn trong mô hình UC:

Giả sử có một "hệ thống câu đố" mà cả người chứng minh và người xác minh có thể tạo ra các câu đố một cách hiệu quả, và

• Người tục ngữ có thể giải một cách hiệu quả bất kỳ câu đố nào, và
• Người xác minh không thể (i) giải các câu đố một cách hiệu quả hoặc (ii) phân biệt giữa một lời giải hợp lệ hay một lời giải ngẫu nhiên không hợp lệ cho một câu đố nhất định, ngay cả khi câu đố đó do chính nó tạo ra.

Bây giờ, được cung cấp một giao thức ZK $\pi$ đối với một số quan hệ NP $R$, chúng ta có thể xây dựng một giao thức khác $\pi'$ ở đâu

1. Người chứng minh và người xác minh chạy $\pi$,
2. Người tục ngữ gửi một câu đố ngẫu nhiên $p$ đến người xác minh,
3. Người xác minh phản hồi bằng một giải pháp "có mục đích" $s$ vì $p$, cộng với một câu đố $p'$,
4. Nếu $s$ là một giải pháp hợp lệ cho $p$, người tục ngữ tiết lộ nhân chứng bí mật của mình $w$ (trong giao thức ZK $\pi$) cho người xác minh. Mặt khác, người tục ngữ gửi một giải pháp $s'$ vì $p'$ đến người xác minh.

Câu hỏi của tôi về bảo mật trong mô hình độc lập

Như đã khẳng định trong tác phẩm của Canetti, nếu $\pi$ là ZK trong độc lập thiết lập, sau đó là như vậy $\pi'$. Để thấy điều này, tôi cho rằng $\pi$ nhận ra một cách an toàn chức năng ZK $\mathcal{F}_{\textsf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$ trong cài đặt độc lập và cố gắng thể hiện điều đó $\pi'$ cũng nhận ra một cách an toàn $\mathcal{F}_{\textsf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$. Đặc biệt, nếu trình xác minh là độc hại trong $\pi'$, tôi có thể xây dựng trình giả lập sau $\mathcal{S}_V$ điều đó nội bộ điều hành kẻ thù trong thế giới thực $\mathcal{A}$:

• $\mathcal{S}_V$ gọi trình mô phỏng cho $\pi$ để tạo ra $\pi$-một phần bảng điểm giữa người xác minh trung thực và người xác minh ác ý (hoặc tương đương, chúng ta có thể diễn đạt lại điều này trong $\mathcal{F}_{\textsf{zk}}^R$-mô hình lai),
• $\mathcal{S}_V$ gửi một câu đố ngẫu nhiên $p$ đến $\mathcal{A}$,
• $\mathcal{S}_V$ nhận được một cặp $(s, p')$ từ $\mathcal{A}$,
• Nếu $s$ là một giải pháp hợp lệ cho $p$, $\mathcal{S}_V$ phá thai. Nếu không thì, $\mathcal{S}_V$ gửi một giải pháp $s'$ vì $p'$ đến $\mathcal{A}$.

Rõ ràng là, trừ khi $\mathcal{S}_V$ hủy bỏ, thực thi lý tưởng với sự có mặt của $\mathcal{S}_V$ không thể phân biệt được với việc thực hiện thực tế với sự có mặt của $\mathcal{A}$. Với giả thiết (i), chúng ta có thể thấy rằng việc hủy bỏ này xảy ra với xác suất không đáng kể. Vì vậy, $\pi'$ được bảo mật trước trình xác minh độc hại và do đó ZK.

Câu hỏi 1:

Điều khiến tôi bối rối là chứng minh trên không yêu cầu giả định (ii). Thật vậy, Canetti lập luận rằng

Hơn nữa, thực tế là $P$ (tức là, tục ngữ) cung cấp $V$ (tức là người xác minh) với một giải pháp $s'$ đến câu đố $p'$ không thực sự là một vấn đề trong một môi trường độc lập, vì $V$ không thể phân biệt $s'$ từ một giá trị ngẫu nhiên (mà $V$ có thể do chính nó tạo ra).

Làm thế nào để giả định này giúp thiết lập tài sản ZK của $\pi'$ trong cài đặt độc lập?

Sự hiểu biết của tôi:

Đối với tôi, việc thực hiện tuần tự của $\pi'$ (ngay cả đối với các đầu vào giống nhau) vẫn là ZK vì người tục ngữ trung thực lấy mẫu một câu đố ngẫu nhiên $p$ mỗi lần.Những câu đố này khác với những câu đố mà người xác minh ác ý đã biết lời giải với xác suất áp đảo (tùy thuộc vào không gian của câu đố). Do đó, người xác minh không thể sử dụng các câu đố đã biết này để buộc người xác minh đưa ra nhân chứng với xác suất không đáng kể trong các lần thực hiện tuần tự của $\pi'$.

Tất nhiên, để kết hợp giả định (ii) vào bằng chứng, có vẻ như chúng ta có thể sửa đổi $\mathcal{S}_V$ để ở bước cuối cùng $\mathcal{S}_V$ gửi một giải pháp ngẫu nhiên $s'$ đến $\mathcal{A}$ (chứ không phải là một giải pháp hợp lệ cho $p'$). Không mất tính tổng quát, ta xét rằng $\mathcal{A}$ đưa ra quan điểm của nó trong trường hợp này. Sau đó, chúng ta có thể thấy rằng giải pháp $s'$ được bao gồm trong $\mathcal{A}$quan điểm của. Để đạt được bảo mật độc hại trong mô hình độc lập, giải pháp ngẫu nhiên $s'$ trong mô phỏng nên không thể phân biệt được với thực thi thực tế. Tuy nhiên, giả định về việc người xác minh không có khả năng phân biệt các giải pháp KHÔNG THỂ được dịch thành giả định rằng người phân biệt (phân biệt giữa thực thi lý tưởng và thực tế) không thể phân biệt giữa giải pháp thực và giải pháp ngẫu nhiên. Do đó, giả định (ii) dường như bất lực vì người phân biệt vẫn có thể phân biệt hai thế giới một cách hiệu quả bằng cách quan sát giải pháp $s'$ Trong $\mathcal{A}$quan điểm của.

Theo tôi, vấn đề này có thể xuất phát từ việc có sự giảm trừ giữa giả định (i) và (ii), là sự giảm trừ giữa giả định CDH và DDH. Việc giảm này làm cho một trong hai giả định trở nên dư thừa. Đây có phải là một sự hiểu biết chính xác?

Câu hỏi của tôi về bảo mật trong mô hình UC

Như đã khẳng định trong tác phẩm của Canetti, $\pi'$ không an toàn trong mô hình UC do hai lần thực thi đồng thời của $\pi'$ với cùng một đầu vào $(x, w)$ có thể rò rỉ nhân chứng $w$ đến trình xác minh độc hại. Cụ thể hơn, cuộc tấn công hoạt động như sau:

$V$ đầu tiên chờ đợi để nhận các câu đố $p_1$ và $p_2$ từ $P$ trong hai buổi. Sau đó nó sẽ gửi $(s, p_2)$ đến $P$ trong phiên đầu tiên, đối với một số tùy ý $s$. Đáp lại, $V$ nhận được từ $P$ một giải pháp $s_2$ đến $p_2$, mà nó trở lại $P$ trong phiên thứ hai. Từ $s_2$ là một giải pháp chính xác, $P$ bây giờ sẽ tiết lộ $w$.

Chúng ta hãy giả sử rằng $\pi$ nhận ra một cách an toàn $\mathcal{F}_{\textsf{zk}}^R$ trong mô hình UC và xem xét lại sự không an toàn này từ góc độ chứng minh an ninh. Bây giờ, chúng ta có thể xem xét một mô phỏng $\mathcal{S}_V'$ trong mô hình UC. Cụ thể hơn, $\mathcal{S}_V'$ giống hệt với $\mathcal{S}_V$ ngoại trừ nó bên ngoài tương tác với máy môi trường $\mathcal{Z}$ đóng vai trò là trình xác minh độc hại (chứ không phải nội bộ tương tác với $\mathcal{A}$). Từ $\pi'$ KHÔNG an toàn với UC, $\mathcal{S}_V'$ nên hủy bỏ ở bước cuối cùng với xác suất không đáng kể. Nói cách khác, $\mathcal{Z}$ sẽ có thể giải câu đố một cách hiệu quả $p$ được lấy mẫu bởi người chứng minh trung thực. $\mathcal{Z}$ được thông báo nhiều hơn $\mathcal{A}$ trong mô hình độc lập vì giải pháp $s$ chọn bởi $\mathcal{Z}$ không chỉ phụ thuộc vào chế độ xem của nó trong phiên hiện tại mà còn phụ thuộc vào các phiên đồng thời khác. Vì vậy, dường như có hai cách có thể cho $\mathcal{Z}$ để giải quyết $p$: (một) $\mathcal{Z}$ giải quyết $p$ bởi chính nó, hoặc (b) $\mathcal{Z}$ không thể giải quyết hiệu quả $p$ nhưng sử dụng các phiên khác để giải quyết nó. Cuộc tấn công thuộc trường hợp (b).

Câu hỏi 2:

Ngay cả khi chúng ta cho rằng $\mathcal{Z}$ không thể khởi động trường hợp (b) tấn công, phải không $\pi'$ vẫn không an toàn trong mô hình UC? Đối với tôi, nếu $\mathcal{Z}$ có thể làm theo mã của người tục ngữ trung thực để giải quyết $p$ và giả định (i) liên quan đến người xác minh không áp dụng cho $\mathcal{Z}$. Trong trường hợp này, $\mathcal{Z}$ có thể sử dụng trường hợp (a) tấn công để phân biệt hai thế giới.

Tổng quát hơn, nếu chúng ta đưa ra một số giả định về các bên bị hỏng trong mô hình UC, liệu những giả định này có áp dụng cho máy môi trường không $\mathcal{Z}$ kiểm soát các bên này? Lưu ý rằng trong mô hình độc lập, phân biệt và đối thủ là những thực thể riêng biệt. Ngược lại, người phân biệt và kẻ thù đều là cỗ máy môi trường $\mathcal{Z}$ trong mô hình UC.

Câu 3:

Để chính thức lập luận rằng một giao thức là an toàn trong mô hình UC, chúng ta có nên liệt kê rõ ràng tất cả các cách có thể cho $\mathcal{Z}$ để xây dựng các thông báo gửi đi của nó dựa trên quan điểm của nó về việc thực thi không đồng bộ tùy ý của (có thể là số lượng không giới hạn) phiên?

Tôi đã đọc một số bằng chứng UC, nhưng hầu hết không đề cập rõ ràng đến việc thực thi các phiên không đồng bộ. Vì các giao thức trong các phiên khác có thể tùy ý, tôi nghĩ rằng không thể liệt kê $\mathcal{Z}$tin nhắn của dựa trên $\mathcal{Z}$lượt xem của tất cả các phiên. Vì vậy, làm thế nào chúng ta có thể chắc chắn rằng $\mathcal{Z}$tin nhắn được chuyển tiếp đến trình mô phỏng sẽ không thất bại trong quá trình mô phỏng khi chúng tôi viết bằng chứng bảo mật trong mô hình UC?