Điểm:4

Mối quan hệ giữa Trình trích xuất kiến ​​thức và tính hợp lý trong ZKPoK

lá cờ gd

Đọc Tại sao Zk-SNARK là Đối số của Kiến thức nếu Trình trích xuất Kiến thức tồn tại? Tôi cảm thấy bối rối trước tuyên bố đầu tiên của OP:

Theo những gì tôi biết, việc chứng minh sự tồn tại của Người trích xuất tri thức có nghĩa là hoàn toàn hợp lý.

Câu trả lời tập trung vào tính hợp lý không nhất thiết phải hoàn hảo, nhưng có vẻ như nó ngầm xác nhận hàm ý về tính hợp lý của trình trích xuất.

Trước hết, hãy để tôi nói rằng khi tôi đọc "soundness", tôi nghĩ đến thuộc tính của các IP nói rằng không có chiến lược Người chứng minh nào có thể thuyết phục Người xác minh về một biểu tượng không thuộc Ngôn ngữ với xác suất cao hơn mức không đáng kể... điều này có vẻ khá khác biệt "đối tượng" hơn là một trình trích xuất "tràn ra" nhân chứng, vì vậy thật khó để tôi có được một ý tưởng ít nhất là ngây thơ về hàm ý được cho là đó.

Tuy nhiên, tôi đã bắt đầu tin vào điều đó, vì những nguồn tôi tìm thấy, ví dụ:

[...] thuộc tính lành mạnh được thay thế bằng thuộc tính khai thác kiến ​​thức [...]

Khi nói đến việc chứng minh tính đúng đắn của bằng chứng tri thức, chúng ta có một cách tiếp cận hình thức rất hay. Giống như với Trình mô phỏng mà chúng ta đã thảo luận ở trên, chúng ta cần chứng minh sự tồn tại của một thuật toán đặc biệt. Thuật toán này được gọi là trình trích xuất kiến ​​thức và nó thực hiện chính xác những gì nó tuyên bố. Trình trích xuất kiến ​​thức (hay gọi tắt là âExtractorâ) là một loại Trình xác minh đặc biệt tương tác với một Nhà cung cấp và – nếu Nhà cung cấp thành công trong việc hoàn thành bằng chứng― Trình trích xuất sẽ có thể trích xuất Proverâ bí mật ban đầu. Và điều này trả lời câu hỏi của chúng tôi ở trên. Để chứng minh tính đúng đắn cho bằng chứng tri thức, chúng ta phải chỉ ra rằng Trình trích xuất tồn tại cho mọi Người chứng minh có thể.

TUY NHIÊN trong đoạn 4.5 "What about soundness?" của Về việc xác định bằng chứng về tri thức nơi Bellare và Goldreich xử lý công thức PoK của họ so với những công thức trước đó (https://www.wisdom.weizmann.ac.il/~oded/PS/pok.ps) Tôi đã tìm thấy những từ này:

Chúng tôi lưu ý rằng định nghĩa của chúng tôi không yêu cầu trường hợp $x$ không ở trong $L_R$. Đặc biệt, tính đúng đắn (tức là, một giới hạn về khả năng của người chứng minh để khiến người xác minh chấp nhận $x$ không ở trong $L_R$) không được yêu cầu. Do đó, một người xác minh tri thức cho $R$ không nhất thiết xác định bằng chứng tương tác về tư cách thành viên trong $L_R$. Điều này trái ngược với các định nghĩa trước đó; chúng có điều kiện "tính hợp lệ" ngụ ý điều kiện lành mạnh, do đó điều kiện sau luôn được giữ vững. Chúng tôi cảm thấy rằng việc "tách rời" tính đúng đắn khỏi tính hợp lệ của chúng tôi là hợp lý cả về mặt khái niệm lẫn dưới ánh sáng của một số ứng dụng nhất định.

Nhân tiện, đó là cùng quan điểm với "Nền tảng mật mã" nổi tiếng của Golderich, phần 4.7.

Vì vậy, một lần nữa tôi lại nghi ngờ về: Knowledge Extractor $=>$ âm thanh

Ai đó có thể nêu bằng chứng hàm ý một cách rõ ràng hoặc ít nhất là cho tôi bất kỳ gợi ý nào về nó không?

Hoặc có thể bản thân sự tồn tại của Trình trích xuất tri thức theo một cách nào đó giúp Người xác minh không bị thuyết phục về một "nhân chứng" mà Người cung cấp thực sự không biết, vì vậy nó có thể được coi là một loại "tài sản hợp lý" ngay cả khi có bản chất khác với thông thường cái? (quan điểm này dường như được xác nhận bởi Geoffroy Couteau trong phần trao đổi câu hỏi/câu trả lời được trích dẫn ban đầu khi ông viết:

Vâng, có một số khía cạnh trong hương vị của sự vững chắc: cho dù bạn có "sự vững chắc về tư cách thành viên" hay "sự vững chắc về kiến ​​thức" hay không (tôi thường nói "khả năng trích xuất kiến ​​thức" trong bài viết của mình để phân biệt với sự vững chắc thông thường)

tuy nhiên nếu đó là trường hợp thì tôi đã mong anh ấy sửa lỗi "ngụ ý" đó của OP)

Xin lỗi vì đã dài dòng, tôi hy vọng đã mô tả những nghi ngờ của mình một cách dễ hiểu.

DiamondDuck avatar
lá cờ hu
Tôi không hoàn toàn hiểu câu hỏi của bạn. Đối với IP lành mạnh, nếu bạn lấy DLOG làm ngôn ngữ, thì một chuỗi trống từ câu tục ngữ sẽ thuyết phục được Verifier$(X=g^x)$ rằng $X$ có trong ngôn ngữ đó. Nhưng nó không truyền đạt ý tưởng rằng người tục ngữ biết $x$. Vì vậy, công cụ trích xuất kiến ​​​​thức dành cho tính hợp lý của kiến ​​​​thức (ngụ ý rằng người tục ngữ thực sự biết $x$ để tạo ra bằng chứng hợp lệ).
baro77 avatar
lá cờ gd
IP được xác định rõ ràng bởi Tính đầy đủ và Tính hợp lý, trong khi đối với Tính đầy đủ của PoK và Sự tồn tại của Trình trích xuất tri thức được trích dẫn. Tôi đoán có thể có hai cách giải thích: KE => thuộc tính Soundness thông thường hoặc KE đại diện cho một hương vị âm thanh khá khác biệt nhưng dù sao cũng đầy đủ. Văn học không giúp tôi hiểu đâu là trường hợp đúng và cách chứng minh nó (hoặc ít nhất là cảm thấy nó hợp lý)
Điểm:5
lá cờ cn

Khả năng trích xuất kiến ​​​​thức là một thuộc tính mạnh hơn tính hợp lý. Dưới đây, tôi sẽ phác thảo lý do tại sao khả năng trích xuất kiến ​​​​thức vô điều kiện ngụ ý độ tin cậy thống kê. Theo thuật ngữ không chính thức, trạng thái vững chắc về mặt thống kê:

"Nếu tuyên bố không chính xác, thì bất kỳ người chứng minh ác ý nào cũng sẽ có xác suất không đáng kể để đưa ra bằng chứng chấp nhận"

Mặt khác, KE tuyên bố:

(*) "Lấy bất kỳ thuật toán chứng minh (có thể độc hại) nào, tạo ra một bằng chứng chấp nhận với xác suất không đáng kể. Sau đó, có một trình trích xuất (thời gian đa thức dự kiến) tương tác với chứng minh này và khôi phục một nhân chứng (tức là một bằng chứng) rằng tuyên bố là đúng".

Công thức như trên, tương đối rõ ràng rằng KE ngụ ý tính đúng đắn: nếu KE được đảm bảo tìm ra bằng chứng cho tuyên bố là đúng, thì điều đó đặc biệt ngụ ý rằng tuyên bố thật. Nói cách khác, (*) ngụ ý:

"Nếu có một thuật toán chứng minh (có thể độc hại) tạo ra một bằng chứng chấp nhận với xác suất không đáng kể, thì tuyên bố đó nhất thiết phải đúng"

Lấy mâu thuẫn cho: "Nếu tuyên bố không chính xác, thì không có thuật toán chứng minh nào có thể tạo ra một bằng chứng chấp nhận với xác suất không đáng kể",

đó chính xác là thống kê sự lành mạnh. Lưu ý rằng điều này không cung cấp cho bạn hoàn hảo lành mạnh: đối với điều này, bạn sẽ cần một dạng khả năng trích xuất kiến ​​​​thức "siêu mạnh" để đảm bảo trích xuất một nhân chứng từ bất kỳ người chứng minh (có thể độc hại) nào đưa ra bằng chứng chấp nhận với bất kỳ xác suất $p>0$.

Lưu ý rằng cũng tồn tại những tình huống mà chúng ta chỉ có thể chứng minh một dạng tính toán của KE, chẳng hạn như "hoặc chúng ta có thể trích xuất một nhân chứng từ chứng minh thành công có giới hạn đa thức này, hoặc chúng ta có thể sử dụng chứng minh để giải bài toán khó này". Trong trường hợp này, KE tính toán ngụ ý tính đúng đắn của tính toán.

Điểm:0
lá cờ gd

Cảm ơn bạn! Bây giờ bản phác thảo của bạn đã giúp tôi không còn bị lạc trong các chi tiết chính thức của FoC 4.7 và cũng hiểu Khi tri thức lành mạnh hàm ý lành mạnh , được tìm thấy trong khi đó và đáng được trích dẫn ở đây, tôi đoán vậy (đó là lý do tại sao tôi viết bài này như một câu trả lời)

Tôi nghĩ rằng sự nhầm lẫn của tôi trước hết là do tôi không phải là chuyên gia trong lĩnh vực này ;-) và sau đó là từ sự lựa chọn nhạy bén của Goldreich để không xác định KE Validity cho các tuyên bố sai và suy luận sau đây của anh ấy về việc không thể xử lý các trường hợp tuyên bố sai (thậm chí nếu bản phác thảo của bạn khiến tôi nghĩ rằng, ngay cả khi không được xác định trong trường hợp đó, có vẻ như KE không thể trả lại nhân chứng không tồn tại của một tuyên bố sai, vì vậy KE trả lại một nhân chứng thực sự ngụ ý tuyên bố là đúng, vì vậy chuỗi logic của bạn cũng có vẻ hợp lệ theo Goldreich's giả định)

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