Score:3

เครื่องจำลองสร้างการถอดเสียงที่ถูกต้องภายใต้ HVZK ด้วยฮิวริสติก Fiat-Shamir ได้อย่างไร

ธง ru

พื้นหลัง

ฉันเข้าใจโปรโตคอลของ Schnorr เวอร์ชันอินเทอร์แอกทีฟ และฉันเข้าใจว่าโปรแกรมจำลองสามารถสร้างเอาต์พุตที่ i.i.d ให้กับเอาต์พุตของผู้พิสูจน์ยืนยันได้อย่างไร:

โปรโตคอลของ Schnorr เวอร์ชันโต้ตอบ วิธีที่ตัวจำลองสร้างเอาต์พุตย้อนกลับ

คำถาม

สิ่งที่ฉันไม่เข้าใจคือตัวจำลองสร้างการถอดเสียงที่ถูกต้องได้อย่างไรเมื่อเราย้ายไปยังโปรโตคอลระบุตัวตนของ Schnorr เวอร์ชันที่ไม่โต้ตอบ หน้า 4 ของเอกสารประกอบการบรรยาย CS355 ประจำปี 2562 แสดงให้เห็นว่าเครื่องจำลองสามารถ "Program $H(g,h,u)$ เป็น $ค$".

โปรแกรมฟังก์ชันแฮช

และหน้าที่ 23 ของ ติดตามเอกสารประกอบการบรรยาย แสดงว่าเครื่องจำลองสามารถตั้งค่าได้ $H$ ไปยังฟังก์ชันแฮชใดๆ โดยพลการ

เหตุใด S จึงมีความสามารถนี้ในการเปลี่ยนฟังก์ชันแฮช

มันดูแปลกสำหรับฉันและฉันไม่เข้าใจ เหตุใดเราจึงถือว่า S มีความสามารถในการเลือกฟังก์ชันแฮชใดๆ ในความเป็นจริงจะมีฟังก์ชันแฮชคงที่ที่เราใช้เพื่อสร้างความท้าทายแบบสุ่ม $ค$, ขวา?

ความเข้าใจของฉันคือการพิสูจน์ HVZK ไม่ทำงานหากเราไม่อนุญาตให้ตัวจำลองสร้างฟังก์ชันแฮชใดๆ สมมติว่าเรามีฟังก์ชันแฮชที่ป้องกัน preimage คงที่ เครื่องจำลองไม่สามารถสร้างข้อความของผู้พิสูจน์ได้ $u$, $z$ ในลักษณะที่สอดคล้องกับความท้าทายนั้น ในกรณีโต้ตอบ ตัวจำลองสามารถเลือกได้ $z$ และ $ค$ สุ่มและทำงานย้อนหลังเพื่อรับ $u$ กำหนดได้ที่ไหน $u = \frac{g^z}{h^c}$. แต่ในกรณีที่ไม่โต้ตอบคุณต้องค้นหา $u$ และ $ค$ ดังนั้น $u = \frac{g^z}{h^c}$ และ $H(g,h,u) = c$และนี่คือ NP-ฮาร์ด ดังนั้นคุณจึงสูญเสียคุณสมบัติที่ไม่มีความรู้ เนื่องจากโปรแกรมจำลองไม่สามารถสร้างการถอดเสียงที่ถูกต้องได้

ดังนั้นการพิสูจน์ความรู้ที่ไม่มีความรู้เป็นศูนย์แบบไม่โต้ตอบจะถูกนำไปใช้ในทางปฏิบัติอย่างไร

บรรณานุกรม

cn flag
ยินดีต้อนรับสู่การตระหนักว่าแบบจำลอง oracle แบบสุ่มนั้นค่อนข้างแปลก
Vadym Fedyukovych avatar
in flag
ดูเหมือนว่าคำถามนี้จะสงสัยว่าใครจะได้รับเอาต์พุตแฮชที่คาดหวังโดยการเลือกอินพุตบางส่วนโดยการสุ่ม โดยมีโอกาสสำเร็จและจำนวนครั้งในการพยายามที่สมเหตุสมผล และยังคงสอดคล้องกับคำจำกัดความแฮชที่ปลอดภัย บางทีฉันเองก็สงสัยเหมือนกัน แต่ขอแนะนำให้คุณคุยกับอาจารย์ก่อน
Score:1
ธง es

ประเด็นสำคัญที่นี่คือการเปลี่ยนแปลงของ Fiat-Shamir คุณต้องแยกให้ออกระหว่างความหมายของความปลอดภัยในการใช้งานจริง และความหมายในทฤษฎีการออกแบบของคุณ เป็นความจริงที่ในทางปฏิบัติเราใช้ฟังก์ชันแฮชเพื่อใช้การแปลง Fiat-Shamir แต่อย่างที่คุณกล่าวถึง ดูเหมือนจะไม่ง่ายเลยที่จะจำลองการพิสูจน์ในกรณีนี้ อย่างไรก็ตาม ในทางทฤษฎี เราใช้วัตถุในอุดมคติที่เรียกว่า "สุ่มออราเคิล" และขึ้นอยู่กับคุณสมบัติที่เราถือว่าสำหรับออราเคิลแบบสุ่มนี้ เราสามารถทำการจำลองได้ แม่นยำกว่านั้น oracle แบบสุ่มสามารถตั้งโปรแกรมได้หรือตั้งโปรแกรมไม่ได้ ด้วยความสามารถในการตั้งโปรแกรมได้ หมายความว่าโปรแกรมจำลองได้รับอนุญาตให้เลือกคำตอบสำหรับแบบสอบถามของออราเคิล ตัวอย่างเช่น ในบริบทของการพิสูจน์ที่ไม่มีความรู้เป็นศูนย์ (NIZK) แบบไม่โต้ตอบ สิ่งนี้ทำให้เครื่องจำลองสามารถสร้างหลักฐานที่น่าเชื่อถือแต่ปลอมได้ในทางกลับกัน โมเดล Oracle แบบสุ่มที่ไม่สามารถตั้งโปรแกรมได้ (NPRO) จะจำกัดตัวจำลองไม่ให้สามารถเลือกคำตอบสำหรับคำถามได้อีกต่อไป แต่เครื่องจำลองจะทำงานได้ก็ต่อเมื่อเห็นคู่คำถาม/คำตอบทั้งหมดที่สร้างขึ้นโดยฝ่ายต่างๆ ในระหว่างโปรโตคอล ข้อจำกัดเกี่ยวกับเครื่องจำลองนี้ (หรือมากกว่านั้นโดยทั่วไปคือการลดความปลอดภัย) ทำให้การพิสูจน์พื้นฐานเป็นที่ต้องการมากกว่า เนื่องจากใช้คุณสมบัติที่น้อยลงของ oracle แบบสุ่ม ดังนั้นจึงถือได้ว่าเป็นขั้นตอนหนึ่งในการกำจัดมันออกไป แต่ในการพิสูจน์บางอย่างของ NIZK เช่น การแปลง Fiat-Shamir ของโปรโตคอลของ Schnorr การเขียนโปรแกรม Oracle แบบสุ่มดูเหมือนจะมีความสำคัญต่อการจัดหาคุณสมบัติ ZK

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา