Fiat-Shamir heuristic จะแทนที่ข้อความเหรียญสาธารณะจากเครื่องยืนยันด้วยแฮชของข้อความของผู้พิสูจน์จนถึงจุดนี้ เช่น: $$H(\alpha_1) = \beta_1, \ H(\alpha_1, \alpha_2) = \beta_2,\H(\alpha_1, \alpha_2, \alpha_3) = \beta_3,\vdots$$ ที่ไหน $\alpha_i$เป็นข้อความของผู้พิสูจน์
ฉันเข้าใจว่าเหตุใด Fiat-Shamir heuristic จึงได้รับการพิสูจน์แล้วว่าปลอดภัยใน ROM อย่างไรก็ตาม ในทางปฏิบัติ ฟังก์ชันแฮช $H$ ไม่ใช่นักพยากรณ์ แล้วอะไรล่ะที่หลีกเลี่ยงไม่ให้ผู้พิสูจน์บดบังข้อความของเขาเพื่อให้สามารถปลอมแปลงหลักฐานปลอมได้
ตัวอย่างเช่น ใน ก $\ซิกม่า$-protocol มีเพียงข้อความเดียวจากผู้ตรวจสอบ $\beta_1 = H(\alpha_1)$. จะเกิดอะไรขึ้นถ้าผู้พิสูจน์บดขยี้บางคน $\alpha_1'$ จนกว่าเขาจะพบอินพุตบางอย่างของฟังก์ชันแฮช $\beta_1$ ให้เขาได้รับประโยชน์บางอย่าง?
เหตุใดเราจึงแฮชข้อความของผู้พิสูจน์ก่อนหน้าทั้งหมดเพื่อรับข้อความยืนยันที่ไม่ใช่แบบโต้ตอบถัดไป ซึ่งเป็นปัญหาในการปฏิบัติเช่น $H(\alpha_i) = \beta_i$? ที่แย่ไปกว่านั้น ถ้าผู้พิสูจน์สามารถแฮชอะไรก็ได้ที่เขาต้องการล่ะ?
อะไรจะหลีกเลี่ยงไม่ให้ผู้พิสูจน์บดบังข้อความของเขาเพื่อให้สามารถปลอมแปลงหลักฐานปลอมได้
เราสามารถถามคำถามเดียวกันกับคำพยากรณ์แบบสุ่มได้เช่นกัน! อะไรทำให้ผู้พิสูจน์ไม่บดขยี้ข้อความของเขาจนกว่าเขาจะสร้างหลักฐานปลอมได้ สิ่งที่คุณแนะนำสามารถทำได้ด้วย RO
และคำตอบคือ: ควรมีจำนวนข้อความน้อยมาก $\alpha_1$ ดังนั้น $\beta_1 = H(\alpha_1)$ ให้ผู้พิสูจน์ได้เปรียบ ในแบบฉบับ $\ซิกม่า$-protocol ตัวอย่างเช่นเมื่อข้อความไม่ได้อยู่ในภาษา (ดังนั้นผู้พิสูจน์จึงโกง) มีค่าเฉลี่ย หนึ่ง $\alpha_1$ ที่ทำให้ผู้พิสูจน์สามารถโกงได้ (แบบฝึกหัด: แสดงว่าเป็นกรณีของ $\ซิกม่า$-โปรโตคอลสำหรับสิ่งอันดับ DDH โดยที่คำนั้นอยู่ $(X,Y)$ และพยานคือ $x\in\mathbb{Z}_p$ ดังนั้น $X = ก^x$ และ $Y = h^x$). ดังนั้นหากมี $2^ค$ ค่าที่เป็นไปได้ $\beta_1$ (นั่นคือพื้นที่ท้าทาย) ผู้พิสูจน์ที่เป็นอันตรายจะต้องคำนวณ $O(2^c)$ แฮชเพื่อสร้างหลักฐานปลอม ตอนนี้ทำให้ $ค$ ใหญ่พอ และคุณจะได้รับความปลอดภัยในการคำนวณ
โปรดทราบว่าการโจมตีแบบบดยังคงเป็นข้อพิจารณาที่สำคัญ: $\ซิกม่า$-โปรโตคอลมีการรักษาความปลอดภัยแบบไม่มีเงื่อนไข แต่ทันทีที่คุณคอมไพล์ใน ROM ด้วย Fiat-Shamir ก็จะมีเพียงแค่ การคำนวณ ความสมบูรณ์ ซึ่งหมายความว่าต้องปรับพารามิเตอร์ความปลอดภัยสำหรับความสมบูรณ์ (พื้นที่ท้าทาย) ตามนั้น: พื้นที่ท้าทาย 40 บิตนั้นใช้ได้สำหรับ $\ซิกม่า$-protocol (เนื่องจากมันให้ตัวพิสูจน์ที่เป็นอันตราย a $2^{-40}$ ความน่าจะเป็นทางสถิติที่จะทำลายความสมบูรณ์ได้สำเร็จ ซึ่งเป็นที่ยอมรับได้ในทางปฏิบัติ) แต่พังสำหรับ Fiat-Shamir (เนื่องจากต้องทำลายโปรโตคอลที่คอมไพล์ไว้ $2^{40}$ การดำเนินการซึ่งเป็นเรื่องเล็กน้อยในการดำเนินการ) โดยปกติเราจะใช้พื้นที่ท้าทายเกี่ยวกับ $2^{128}$ เมื่อใช้ Fiat-Shamir
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
