Tham gia Đăng nhập
Điểm:2
Sheldon avatar Crypto

Ý nghĩa của trình xác minh là "ppt" là gì? và tại sao chúng ta cần trình xác minh là ppt trong Bằng chứng tương tác?

lá cờ nl
Sheldon

Tôi đã nghiên cứu về Zero Knowledge Proof. Tôi tìm thấy Định nghĩa về bằng chứng tương tác nói rằng Trình xác minh là ppt. Và tôi chỉ tìm thấy trong PP (Độ phức tạp) Wikipedia nói rằng ppt:

Máy Turing liên kết đa thức và xác suất là đặc trưng như PPT, viết tắt của thời gian đa thức xác suất máy móc.[2] Đặc tính này của máy Turing không yêu cầu một xác suất lỗi giới hạn. Do đó, PP là lớp phức tạp chứa tất cả các vấn đề có thể giải quyết bằng một PPT máy bị lỗi xác suất nhỏ hơn 1/2.

Vẫn còn rất khó hiểu về PPT, tên đầy đủ của PPT là gì? chúng tôi có cần trình xác minh là PPT cho Bằng chứng tương tác không?

Nguồn từ: Zero Knowledge Proofs CS276: Mật mã học, UC Berkeley

54
0 + 0
Điểm:2
avatar Crypto
lá cờ et
user93353

PPT là thuật toán thời gian đa thức xác suất.

Trình xác minh xác định sẽ luôn tạo ra cùng một đầu ra/trả lời cho bất kỳ đầu vào nào.

Hãy lấy một chuỗi tương tác.

Prover gửi $p_1$.

Người xác minh trả lời bằng $f(p_1) = v_1$

Prover trả lời lại với $g(v_1) = p_2$

Chức năng $f$ mà người xác minh sử dụng là xác định. tức là đối với một đầu vào cụ thể, nó luôn trả lời với cùng một câu trả lời.

Trong một xác minh xác suất, $f$ cũng có ngẫu nhiên hóa làm đầu vào. I E. $g$ mất 2 đầu vào $f(v_i, r)$ ở đâu $r$ là một giá trị ngẫu nhiên. Vì thế $f$ là không xác định và người xác minh là người xác minh xác suất. Và nếu $f$ chạy trong thời gian đa thức, trình xác minh là trình xác minh Thời gian đa thức xác suất (PPT).

0 + 0
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

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