Điểm:5

"Nhân chứng" và "Bằng chứng" có giống nhau khi nói về Kiến thức Không? Còn "lập luận" thì sao? Và "tuyên bố"?

lá cờ in

Tôi đã thấy mọi người tạo ra nhiều sự khác biệt khi đọc các bài báo về tri thức không.
Tôi đã thấy thuật ngữ "Lập luận về kiến ​​thức" dường như được sử dụng như một "Bằng chứng về kiến ​​thức" yếu hơn: điều tôi hiểu là nếu bạn nói về thuộc tính lành mạnh thông thường, bạn nói về "đối số", trong khi nếu bạn nói về thuộc tính hợp lệ (từ Proofs of Knowledge) thì bạn nói về "bằng chứng". Nó có đúng không?

Nhưng điều khiến tôi bối rối nhất là tôi đã thấy thuật ngữ "nhân chứng" và "bằng chứng" được sử dụng khác nhau và để diễn đạt cùng một khái niệm. Tôi biết nhân chứng là gì (về cơ bản, bí mật của Prover), nhưng tôi cũng đã nghe các cụm từ:
"P không biết một nhân chứng, nhưng anh ta biết một bằng chứng"
"tạo nhân chứng VÀ tạo bằng chứng"
"trong Zk-SNARKS, tính ngắn gọn: kích thước của bằng chứng nhỏ hơn nhiều so với kích thước của nhân chứng".

"Xác minh bằng chứng nhanh hơn nhiều so với trực tiếp kiểm tra tuyên bố, ngay cả khi đưa ra nhân chứng."
Cụm từ cuối cùng này thực sự hỗn loạn đối với tôi.

Vậy chúng có khác nhau không? Nếu vậy, sự khác biệt giữa "bằng chứng" và "tuyên bố" là gì?
Tiếng Anh không phải là ngôn ngữ mẹ đẻ của tôi, đó có thể là vấn đề, nhưng làm ơn bạn có thể làm rõ tất cả các điều khoản này cho tôi được không?

Điểm:2
lá cờ gd

Về một vài chủ đề bên lề

Tôi tin rằng chúng ta nói về "Đối số" khi "Bằng chứng" về tính hợp lý phụ thuộc vào các giả định tính toán: do đó, tính hợp lý của Đối số yếu hơn so với Bằng chứng, nhưng thường đủ mạnh khi xem xét rằng các ứng dụng mã hóa hiện tại luôn dựa vào độ cứng tính toán; và đối tác là, ví dụ, Đối số NP có thể là ZK là một cách mạnh hơn so với Bằng chứng NP (ZK theo thống kê so với ZK tính toán).

Hậu tố "of Knowledge" được sử dụng (cho cả Bằng chứng hoặc Luận điểm) khi người châm ngôn nắm giữ thông tin có thể trích xuất hiệu quả thông qua một "thiết lập đặc biệt" (đặc biệt theo cách tương tự mà Trình mô phỏng là đặc biệt).


Hoặc thử nghĩ theo cách này: "hương vị lành mạnh" và "biết điều gì đó (hoặc không)" là hai thuộc tính trực giao, vì vậy bạn có thể có một "tích Descartes" gồm các kết hợp:

  1. Bằng chứng ZK
  2. Đối số ZK
  3. Bằng chứng về kiến ​​​​thức ZK
  4. ZK Argument of Knowledge ("ARK" trong ZK-SNARK)

1 và 3 có độ chính xác cao hơn (*), 2 và 4 chỉ tính toán; đối với 3 và 4, một Trình trích xuất tồn tại (đó là cách được công nhận để chứng minh Kiến thức) có thể lấy thông tin mà trình tục ngữ nắm giữ một cách hiệu quả (và nó không phá vỡ thuộc tính ZK theo cách tương tự mà Trình mô phỏng không phá vỡ tính hợp lý... tạm dừng/ tua lại và tất cả những thứ đó ..)

vì vậy, một Đối số, yếu hơn bằng chứng từ góc độ lành mạnh, có thể có mức độ bảo mật (thống kê) mạnh hơn so với bằng chứng (tính toán) không? Tôi nghĩ là ổn thôi...nhưng làm thế nào đến? Không thể hiểu tại sao điều đó lại có thể.

Nếu bạn hiểu rằng "sự vững chắc" và "kiến thức" là hai thuộc tính riêng biệt, thì bạn cũng sẽ hiểu rằng thuộc tính riêng biệt thứ ba là "sự hiểu biết bằng không", có thể phụ thuộc vào cái trước theo cách không như bạn mong đợi.

Tôi chỉ là một người đam mê và ham đọc sách, vì vậy tôi đoán bạn có thể dễ dàng nhận được nhiều lời giải thích tốt hơn của tôi, tuy nhiên tôi muốn gợi ý cho bạn chương 4 của cuốn Foundations of Cryptography Vol.1 của Oded Goldreich ...thực sự sâu sắc...

(*) không chỉ ở “mức độ” thống kê, trong Proofs, tính đúng đắn được chứng minh bằng sự suy diễn logic từ ngữ cảnh và tiên đề, do đó, cách chứng minh “cổ điển/tiêu chuẩn” phổ biến

lá cờ in
Được rồi, về cơ bản khi bạn nói về thuộc tính lành mạnh ở cấp độ tính toán, bạn sử dụng thuật ngữ Đối số, trong khi nếu bạn xác định Trình trích xuất tri thức và chứng minh rằng một nhân chứng tồn tại, thì bạn nói về bằng chứng... Hoặc có thể bạn nói về bằng chứng ngay cả khi không có Trình trích xuất kiến ​​thức mà chỉ là thuộc tính lành mạnh ở mức độ bảo mật thống kê? Ngoài ra, do đó, một Đối số, yếu hơn bằng chứng từ góc độ hợp lý, có thể có mức độ bảo mật Zero Knowledge (thống kê) mạnh hơn so với bằng chứng (tính toán)? Ý tôi là, được rồi... nhưng sao lại thế? Không thể hiểu tại sao điều đó lại có thể.
baro77 avatar
lá cờ gd
Tôi đã cố gắng trả lời bằng một bình luận, nhưng tôi cần thêm chỗ trống nên tôi đã chỉnh sửa câu trả lời trước đó của mình
lá cờ in
Cảm ơn bạn rất nhiều, tôi đã đưa ra câu trả lời hay nhất cho Yehuda vì câu trả lời đó là điều chính tôi cần để giải tỏa tâm trí nhưng ngay cả câu trả lời của bạn cũng rất hữu ích. Trước đây tôi không biết rõ sự khác biệt giữa lập luận và bằng chứng nhưng bây giờ tôi đã biết, rất nhiều thuật ngữ khác nhau cần học để thực sự hiểu Zero Knowledge... Tôi đã ủng hộ bạn!
baro77 avatar
lá cờ gd
Anh đã làm điều đúng đắn! :) Yehuda không chỉ nổi bật trong ngành, mà còn thuộc về một nhóm các chuyên gia / Giáo sư quyên góp một phần thời gian của họ ở đây cho cộng đồng: vì vậy, việc cung cấp thuốc cho hoạt động giảng dạy của họ ngoài kênh chính thức của các lớp học đại học: không phổ biến và đáng khen ngợi, giúp truyền bá tri thức có chất lượng. Vì vậy, tôi cảm ơn anh ấy và những người khác (bây giờ tôi nhớ @GeoffroyCouteau, nhưng chắc chắn rằng tôi cũng nhớ nhiều người khác nữa). Về tôi, tôi chỉ học như bạn và cố gắng trả lời giúp tôi củng cố các khái niệm: cảm ơn vì đã ủng hộ!
Điểm:2
lá cờ us

Đầu tiên, điều quan trọng là phải hiểu rằng không phải ai cũng sử dụng thuật ngữ một cách chính xác hoặc theo cùng một cách. Vì vậy, bạn sẽ không tìm thấy sự nhất quán hoàn toàn ở mọi nơi. Phải nói rằng, tôi tin rằng trong trường hợp này nó khá rõ ràng. Một chứng kiến là một loại chứng minh rất cụ thể. Cụ thể, đó là cái mà chúng ta gọi là bằng chứng NP rằng $x\trong L$. ($\mathcal NP$ như một lớp phức tạp có thể được xem xét theo nhiều cách. Theo tôi, cách "tốt nhất" về mặt khái niệm là một loại ngôn ngữ mà các câu lệnh có bằng chứng bằng văn bản hiệu quả. Đó là, tồn tại một máy xác minh thời gian đa thức (tất định) $V$ như vậy mà $x\trong L$ khi và chỉ nếu tồn tại một $w$ như vậy mà $V(x,w)=1$. Tuy nhiên, có nhiều cách khác để chứng minh các tuyên bố. Đầu tiên, có những tuyên bố mà chúng tôi chứng minh rằng không có trong $\mathcal NP$. Thứ hai, chúng tôi có thể đang chứng minh một câu lệnh NP, nhưng chúng tôi muốn các thuộc tính khác - chẳng hạn như kiến ​​​​thức bằng không. Trong trường hợp như vậy, chúng tôi sử dụng một bằng chứng tương tác. Người tục ngữ có thể sử dụng nhân chứng, nhưng không gửi nó đi. Cuối cùng, có thể có các trường hợp (như trong SNARK) trong đó bằng chứng có thể ngắn hơn bằng chứng NP ban đầu và chúng tôi có thể muốn bằng chứng trong đó thời gian xác minh bằng chứng ngắn hơn thời gian chạy $V(x,w)$ và xác minh nó theo cách NP cổ điển, v.v. Tôi hy vọng điều này làm cho nó rõ ràng.

lá cờ in
Cảm ơn bạn rất nhiều Yehuda, vâng, điều này giúp ích rất nhiều.Tôi nghĩ rằng nhân chứng là một bí mật nào đó cho phép Người chứng minh luôn tạo ra bằng chứng một cách hiệu quả, nếu bạn có nó, và tôi nghĩ nó "hơi" đúng (có thể không phải lúc nào cũng hiệu quả) phải không? Nhưng bản thân nhân chứng cũng có thể được coi là bằng chứng, nhưng là bằng chứng NP, phải không? Câu hỏi xuất hiện một cách tự nhiên là: làm thế nào có thể trong các ngữ cảnh như SNARK, một bằng chứng ngắn hơn và nhanh hơn một nhân chứng, nếu nhân chứng là một bằng chứng xác định NP? Điều gì có thể nhanh hơn thế?
lá cờ in
Ý tôi là, tôi đoán để xác minh bằng chứng P, bạn vẫn cần chạy V(x, p) giống như bạn chạy V(x, w), phải không? Và nhân chứng mạnh hơn nhiều so với bằng chứng, vậy làm sao nó có thể nhanh hơn? Đó là nghi ngờ duy nhất của tôi
Yehuda Lindell avatar
lá cờ us
Hãy nghĩ về việc P đang làm việc chăm chỉ hơn để cung cấp thứ gì đó dễ dàng hơn cho V. Ngoài ra, không giống như bằng chứng NP, chúng tôi cho phép người xác minh đôi khi mắc lỗi (với xác suất thấp) và chúng tôi cũng cho phép điều đó mang tính xác suất. Những điều này giúp ích rất nhiều.
lá cờ in
Ok, vì vậy hãy cho tôi biết nếu tôi hiểu rõ vì rất khó để xem hình ảnh đầy đủ: trong một giao thức tương tác, Nhân chứng là bằng chứng sẽ luôn được Người xác minh chấp nhận, vì vậy nếu bạn có Nhân chứng, bạn luôn có thể chứng minh rằng x nằm trong L với xác suất 1, nhưng không thực sự hiệu quả. Thay vào đó, nếu bạn có bằng chứng, bạn có thể chứng minh rằng x thuộc L với xác suất (khá cao) nhất định. Bằng cách này, một bằng chứng có thể nhanh hơn một nhân chứng. Đây có phải là cách chính xác để xem sự khác biệt giữa bằng chứng và nhân chứng?
Yehuda Lindell avatar
lá cờ us
Đúng. Điều duy nhất tôi sẽ nói khác đi là trong nửa sau, tôi sẽ đề cập đến một "hệ thống bằng chứng" liên quan đến người chứng minh và người xác minh. Điều này khác với một nhân chứng cung cấp sự tương tự của một bằng chứng bằng văn bả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.