Điểm:2

Hiểu "đối số tua lại"

lá cờ cm
AXX

Tôi đã đọc qua các câu hỏi liên quan trên SE này, nhưng tôi vẫn không hiểu tại sao chúng ta có thể sử dụng đối số tua lại.Cụ thể, tua lại có vẻ như là một siêu năng lực thực sự mạnh mẽ đối với tôi và tôi không hiểu tại sao giả định mạnh mẽ như vậy không làm suy yếu sức mạnh của kết luận. Chắc chắn, trình xác minh đối thủ không học được gì từ trình giả lập có thể thao túng thời gian, nhưng nếu một thực thể nào đó mạnh đến mức có thể thao túng thời gian, tôi không ngạc nhiên khi nó an toàn trước bất kỳ đối thủ nào, tôi cũng không tin rằng các thực thể khác không có sức mạnh này vẫn an toàn.

Tôi nghĩ rằng có thể khả năng tua lại này có liên quan đến quyền truy cập tiên tri của trình giả lập vào trình xác minh, để trình giả lập thực sự có thể thực hiện "nhìn trước" để tìm hiểu câu hỏi mà trình xác minh sẽ hỏi và sau đó chuẩn bị câu trả lời cho phù hợp. Nếu đây là trường hợp, thì tôi tin chắc rằng thực sự không có siêu năng lực nào, vì đó là điều mà chính người xác minh có thể làm được, và do đó, thuộc tính không kiến ​​thức sẽ xuất hiện.

Điểm:4
lá cờ gd

Theo như tôi biết, bạn đã có điểm. "Tua lại" chỉ là chiến lược "nhìn về phía trước" có thể thực hiện được bằng quyền truy cập tiên tri của trình giả lập vào trình xác minh

Nó thường được gọi là "siêu năng lực" bởi vì đó là khả năng mà Prover không có trong quá trình thực thi giao thức thông thường, nếu không, tính hợp lý có thể bị tổn hại (vì trình mô phỏng có thể tạo ra bản ghi tương tác thuyết phục mà không cần biết bất cứ điều gì, nên nó có thể mạo danh một hành vi gian lận chứng minh giả vờ chứng minh một tuyên bố sai)

Về thực tế là mô phỏng chính xác là thứ mà người xác minh có thể làm một mình, điều đó đúng: người giả lập không biết gì để chứng minh ZKness, và ai là ứng cử viên sáng giá hơn Người xác minh cho vai trò của một người không biết?!


CHỈNH SỬA ĐỂ TRẢ LỜI NHẬN XÉT SAU:

Trong chương 6 của Hướng dẫn về nền tảng của mật mã học (Springer) Yehuda Lindell viết:

Đầu tiên, người ta có thể thắc mắc làm thế nào có thể tua lại trình xác minh “về mặt kỹ thuật” Trên thực tế, khi xem xét kiến ​​thức về hộp đen bằng 0, điều này là không đáng kể. Cụ thể, trình mô phỏng được cấp quyền truy cập tiên tri vào chức năng thông báo tiếp theo V*(x, z, r, ·) của trình xác minh. Điều này có nghĩa là nó cung cấp bản ghi m' = (m1, m2, . . . . . ) của tin nhắn đến và nhận lại tin nhắn tiếp theo được gửi khi V* có đầu vào x, đầu vào phụ z, băng ngẫu nhiên r và tin nhắn đến m'

vì vậy, đây chỉ là tin nhắn tiếp theo, không phải toàn bộ bản ghi kết quả khi kết thúc tương tác (nếu đây là nghi ngờ của bạn).

Với định nghĩa đã nói ở trên về chức năng tin nhắn tiếp theo (trong đó thử thách của người chứng minh thuộc về các tin nhắn mà người xác minh đã nhận trước đó), "cách hiển nhiên" của bạn đối với tôi có vẻ sai đối với người xác minh chung chung (còn gọi là có khả năng gian lận) V*.

Nếu trình xác minh là trung thực (do đó, thử thách là "ngẫu nhiên" một cách trung thực - ngay cả khi không nhất thiết phải được phân phối đồng đều), bạn có thể chỉ cần hoàn nguyên thứ tự mà trình giả lập nhận được thông báo (vì vậy đầu tiên là kết quả, sau đó thử thách, sau đó là cam kết): BTW, đó là chiến lược để chứng minh rằng giao thức nhận dạng Schnorr là HVZKP (bỏ qua - vì mục đích đơn giản - rằng chúng ta đang xử lý các bản phân phối chứ không chỉ các giá trị thực tế).

Nhưng nếu chúng ta phải đối phó với một người xác minh có khả năng gian lận V* (và đó là trường hợp giả định trong phần 8.7 của bài giảng của bạn), có thể các thử thách là chức năng của các cam kết, vì vậy chúng không độc lập lẫn nhau, vì vậy chiến lược tốt nhất của bạn là thử tất cả các kết quả cho đến khi bạn tìm thấy cái hợp lệ (hoặc, theo quan điểm bài giảng của bạn, đưa ra kết quả, bạn bắt đầu thử tất cả các cam kết cho đến khi hàm tạo ra thử thách "đúng")... dù sao thì bạn cũng phải kiểm tra một số trường hợp tăng theo cấp số nhân nếu bạn chỉ có một bậc tự do, vì vậy Trình mô phỏng PPT không thể xử lý nó, hay còn gọi là ZK không được chứng minh:

Điều này có nghĩa là sau khi trình mô phỏng tua lại, toàn bộ giao thức sẽ bắt đầu lại từ đầu. Điều này ngụ ý rằng số lần tua lại dự kiến ​​là theo cấp số nhân và chúng tôi không thể xây dựng trình mô phỏng PPT, ngụ ý rằng chúng tôi không thể chứng minh thuộc tính không kiến ​​thức.

Vì vậy, không có gì mâu thuẫn giữa định nghĩa tua lại ở trên và kết luận của đoạn đầu tiên trong phần 8.7 của bài giảng của bạn.

Tôi thừa nhận rằng tôi chưa nghĩ nhiều về lý do tại sao một trình giả lập phải là PPT và không thể - giả sử - không bị giới hạn về mặt tính toán, ít nhất là về nguyên tắc: Tôi muốn nghe ý kiến ​​​​của những người khác về điều đó. Trong khi đó, những phỏng đoán được giáo dục của tôi là:

  • "chúng tôi coi những nhiệm vụ khó thực hiện mà máy PPT không thể thực hiện được" (Goldreich, Foundation of Cryptography Tập I trang 19)
  • đối với bất kỳ mục đích sử dụng thực tế nào, chúng tôi luôn bị hạn chế sử dụng các thực thể hiệu quả (bao gồm cả các bộ chứng minh, ngay cả khi về mặt lý thuyết không có vấn đề gì khi coi chúng là không giới hạn)
  • sự tồn tại của một trình mô phỏng là điều kiện đủ nhưng không cần thiết đối với ZK, do đó, việc sử dụng mô hình này đồng nghĩa với việc thiếu bất kỳ giả định toàn diện nhất nào: trong trường hợp này, có vẻ như có thể chấp nhận được việc sử dụng một định nghĩa quá thận trọng
AXX avatar
lá cờ cm
AXX
Bây giờ tôi có một câu hỏi tiếp theo khác... Nếu chúng ta thực sự hiểu việc tua lại là xem trước, thì chúng ta có thể chứng minh thuộc tính không kiến ​​thức của giao thức 3 vòng (được đề cập trong [ghi chú này](https://courses.grainger.illinois .edu/cs598dk/fa2019/Files/lecture08.pdf) trong 8.7) theo cách rõ ràng: chúng tôi xem trước để tìm tất cả $n$ thông báo mà người xác minh sẽ hỏi, sau đó chúng tôi chuẩn bị các cam kết của mình trong giai đoạn đầu cho phù hợp.Vì vậy, là sự hiểu biết của tôi về oracle sai? Nó thực sự truy xuất tin nhắn tiếp theo hay chỉ là kết quả cuối cùng khi tương tác với trình xác minh?
baro77 avatar
lá cờ gd
câu trả lời trong câu trả lời đã chỉnh sửa :)
AXX avatar
lá cờ cm
AXX
Cảm ơn vì đã chỉnh sửa, tôi nghĩ bây giờ cuối cùng tôi cũng đã nắm vững những điểm tinh tế trong các lập luận tua lại. Thật vậy, tôi chưa bao giờ nhận ra rằng những thách thức mà người xác minh gửi có thể "thích ứng" với các cam kết trong giai đoạn đầu tiên.
Điểm:2
lá cờ ng

tua lại một chương trình phổ biến trong máy tính. Một cách để gọi nó là lấy một ảnh chụp nhanh, sau đó chạy lại nó khi môi trường thực thi ảo cho phép. Một ứng dụng đang hoàn thành trò chơi arcade cổ điển mà không khởi động lại từ đầu sau một lỗi. Tất cả những gì cần làm là quyết định thời điểm chúng ta muốn tua lại; tạo một bản sao của tất cả trạng thái của máy (RAM và các thanh ghi) tại thời điểm đó; sau đó đặt mọi thứ trở lại vị trí.

Ít nhất một số bằng chứng sử dụng tua lại hoạt động theo cách này: chúng tôi trả lại chương trình kẻ tấn công giả định và lời tiên tri về trạng thái đã lưu, sau đó khởi động lại bằng một băng ngẫu nhiên khác/câu trả lời tiên tri khác từ thời điểm đó. Chúng tôi kiểm soát băng ngẫu nhiên (do đó, các giá trị mới của oracle), giống như máy chủ VM có thể kiểm soát RNG của máy ảo khách. Khả năng đó cho phép chúng tôi biến chương trình tấn công giả định đó thành thứ tấn công một giao thức khác, do đó chứng minh tính bảo mật của giao thức sau này ngụ ý rằng không thể có chương trình tấn công giả định như vậy.

Thay vì là một "siêu năng lực", tôi thấy đây là một công trình sử dụng môi trường điện toán mạnh hơn một chút, giống như một máy tính chủ cho một máy ảo.

Lưu ý: Tôi không chắc liệu sự tương tự này có hoạt động để tua lại như trong trình giả lập ZK hay không.

baro77 avatar
lá cờ gd
imho, cơ sở hạ tầng VM chỉ là một ví dụ THỰC TẾ về cách truy cập tiên tri hộp đen vào chương trình con _next_message_ của trình xác minh có thể đạt được trong kịch bản "thế giới thực" ngày nay. Tuy nhiên, khi chúng tôi xử lý ZK Simulator, chúng tôi quan tâm đến điều kiện tồn tại của nó, chứ không phải cách triển khai nó.. vì vậy, "siêu năng lực" ở đây không đề cập đến một môi trường máy tính cụ thể, mà là các khả năng được phép bên ngoài các ràng buộc bằng chứng tương tác (hay còn gọi là các quy tắc giao thức, một cách thô thiển nói)
AXX avatar
lá cờ cm
AXX
Cảm ơn bạn đã trả lời! Nó cho tôi cảm giác về cách người ta có thể tua lại một chương trình trong thế giới vật chất. Có vẻ như điều này yêu cầu kẻ tấn công chạy trên một môi trường ảo do người bảo vệ kiểm soát, điều mà tôi cho rằng đó là điều mà kịch bản ZK không cho phép (hoặc nếu không thì một kẻ phá hoại độc hại có thể dễ dàng giành chiến thắng như @ baro77 đã lưu ý).

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