Điểm:4

Groth16 mô phỏng bằng chứng không kiến ​​thức cho câu lệnh không hợp lệ

lá cờ mx

Thuộc tính không kiến ​​thức của Groth16 (https://eprint.iacr.org/2016/260, trang 8) đối số không kiến ​​thức không tương tác dựa trên sự tồn tại của trình mô phỏng $\text{Sim}$ tạo bằng chứng "giả" cho các tuyên bố hợp lệ $(\phi, w) \in R$ mà không biết nhân chứng $w$ cho tuyên bố $\phi$.

Câu hỏi của tôi là liệu Groth16 cũng tồn tại một trình giả lập $\text{Sim}'$ để tạo bằng chứng "giả" cho không hợp lệ các câu lệnh $\phi'$, mà không có nhân chứng $w'$ với $(\phi', w') \in R$ tồn tại. Chính thức, Groth16 có thỏa mãn khái niệm sau không?

Kiến thức không giả mạo: Cho tất cả $\lambda \in \mathbb{N}, (R, z) \gets \mathcal{R}(1^\lambda), (\phi, w) \in R$, tất cả các $\phi'$và tất cả các đối thủ $\mathcal{A}$: $Pr[(\sigma, \tau) \gets \text{Setup}(R); \pi \gets \text{Prove}(R, \sigma, \phi, w): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1] = Pr[(\sigma, \tau) \gets \text{Thiết lập}(R); \pi \gets \text{Sim}'(R, \tau, \phi'): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1]$

Bất kỳ câu trả lời nào cũng sẽ hữu ích, bao gồm bằng chứng cho việc không có kiến ​​​​thức giả về Groth16 hoặc các kế hoạch khác, định nghĩa về các khái niệm tương tự nhưng khác nhau hoặc kết quả không thể thực hiện được.

(Tôi đang cố gắng xây dựng một bằng chứng bảo mật trong đó việc tạo ra các bằng chứng giả mạo như vậy dường như là cần thiết. Tôi chưa bao giờ thấy khái niệm ở trên, nhưng đối với tôi thì có vẻ như vậy $\text{Sim}'$ nên tồn tại cho một số chương trình.)

Điểm:3
lá cờ cn

"Không biết giả tạo" luôn xuất phát từ sự kết hợp của hai thuộc tính:

  • Kiến thức không tiêu chuẩn: tồn tại Sim mô phỏng có thể tạo bằng chứng (không thể phân biệt được với bằng chứng trung thực) cho các tuyên bố hợp lệ và

  • Tư cách thành viên tập hợp con cứng: có một thuật toán lấy mẫu cho ngôn ngữ và các câu sai được lấy mẫu ngẫu nhiên không thể phân biệt được với các câu đúng được lấy mẫu ngẫu nhiên (cũng tồn tại các biến thể của khái niệm này).

Việc kết hợp những điều trên mang lại khái niệm "đúng" cho "kiến thức giả mạo bằng không": lấy mẫu một tuyên bố đúng và xây dựng một NIZK trung thực vì nó không thể phân biệt được với việc lấy mẫu một tuyên bố sai và mô phỏng một NIZK cho nó.

lưu ý 1

Khái niệm kiến ​​​​thức giả mạo trong câu hỏi của bạn là khác nhau (nó không liên quan đến thuật toán lấy mẫu cho ngôn ngữ): bạn đang nói điều đó vì không tí nào tuyên bố đúng $(\phi, w)$không tí nào báo cáo sai $\phi'$, NIZK trung thực với $(\phi,w)$ không thể phân biệt được với NIZK mô phỏng với $\phi'$. Đây là cách quá mạnh mẽ, và nó không bao giờ có thể giữ được. Lý do là thuật toán tấn công $\mathcal{A}$ có thể có $\phi, \phi'$ được mã hóa cứng trong phần mô tả của nó (vì thuộc tính dành cho tất cả $\phi,\phi'$ và tất cả các đối thủ $\mathcal{A}$) và có thể chỉ cần thử thuật toán xác minh trên NIZK. Bây giờ, vì thuật toán xác minh mất $\phi$ (hoặc $\phi'$) làm thông tin đầu vào, đối thủ sẽ luôn phân biệt hai tình huống (nếu quá trình xác minh được thông qua với $\phi'$, đó là bằng chứng giả, nếu không thì đó là bằng chứng thật; lưu ý rằng xét về tính hợp lý, việc xác minh một bằng chứng xác thực do một người chứng minh trung thực tạo ra không thể thành công đối với một tuyên bố không hợp lệ $\phi'$, do đó cuộc tấn công đặc biệt mà tôi vừa mô tả hoạt động với xác suất áp đảo).

Lưu ý 2

Tư cách thành viên tập con cứng là cần thiết cho "không kiến ​​thức giả": nếu không khó để phân biệt các tuyên bố đúng với các tuyên bố sai, chúng ta không thể hình thành bất kỳ khái niệm hữu ích và không tầm thường nào về kiến ​​thức không giả mạo. Nhưng nó phù hợp với hầu hết các ngôn ngữ mật mã được quan tâm - thông thường, chúng tôi quan tâm đến việc tạo NIZK cho các tuyên bố mà người xác minh không thể tự xác minh.

Anakin Charles avatar
lá cờ mx
Cảm ơn, tôi hiểu tại sao khái niệm đề xuất của tôi quá mạnh. Như bạn nói "luôn tuân theo": có tài liệu tham khảo nào cho thấy tư cách thành viên tiêu chuẩn-zk + tập hợp con cứng cho phép bằng chứng mô phỏng về các tuyên bố giả mạo không?
Geoffroy Couteau avatar
lá cờ cn
Tôi không thể nghĩ ra một tài liệu tham khảo tiêu chuẩn nào trong đầu mình, đó giống như một quan sát trực tiếp văn hóa dân gian hơn. Nếu bạn viết định nghĩa về thành viên tập hợp con cứng và kiến ​​thức bằng không, thì "kiến thức giả bằng không" sẽ ngay lập tức theo sau bằng cách áp dụng tuần tự cả hai: bắt đầu bằng một bằng chứng trung thực về một tuyên bố đúng, trước tiên hãy áp dụng kiến ​​thức bằng không để thay thế người chứng minh bằng một trình giả lập, sau đó áp dụng tư cách thành viên tập con cứng để chuyển câu đúng sang câu sai một cách không thể phân biệt (có thể thực hiện ở giai đoạn này vì Sim không yêu cầu nhân chứng).
Anakin Charles avatar
lá cờ mx
Tôi hiểu rồi. Vâng, một bằng chứng trò chơi hop như vậy sẽ dễ dàng xây dựng. Cảm ơn!

Đă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.