Score:3

บดขยี้ด้วยฮิวริสติกของ Fiat-Shamir

ธง in

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$? ที่แย่ไปกว่านั้น ถ้าผู้พิสูจน์สามารถแฮชอะไรก็ได้ที่เขาต้องการล่ะ?

Score:9
ธง cn

อะไรจะหลีกเลี่ยงไม่ให้ผู้พิสูจน์บดบังข้อความของเขาเพื่อให้สามารถปลอมแปลงหลักฐานปลอมได้

เราสามารถถามคำถามเดียวกันกับคำพยากรณ์แบบสุ่มได้เช่นกัน! อะไรทำให้ผู้พิสูจน์ไม่บดขยี้ข้อความของเขาจนกว่าเขาจะสร้างหลักฐานปลอมได้ สิ่งที่คุณแนะนำสามารถทำได้ด้วย 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

Vadym Fedyukovych avatar
in flag
"ในโปรโตคอล Σ-ทั่วไป..ไม่ได้อยู่ในภาษา โดยเฉลี่ยจะมี 1 ที่ช่วยให้ผู้พิสูจน์สามารถโกงได้" สิ่งนี้มีไว้สำหรับตรวจสอบคำตอบที่พิสูจน์แล้ว เช่น พีชคณิตซับใน อาจไม่ใช่เรื่องทั่วไป บางคนอาจยืนยันค่าสัมประสิทธิ์ยกกำลังสอง (พิจารณาความท้าทายเป็นตัวแปรอิสระ) รวมสามคำตอบเช่นทฤษฎีบทพีทาโกรัส เพิ่มโอกาสโกงสองเท่าในกรณีนี้
Bean Guy avatar
in flag
อืม นั่นคือสิ่งที่ฉันคิด อย่างไรก็ตาม ความเป็นไปได้ของการโจมตีแบบ "บดขยี้" ควรได้รับการพิจารณาทุกครั้งที่มีความตั้งใจที่จะสร้างโปรโตคอล ใช่ไหม? ฉันคิดว่ายังไม่ได้รับการพิสูจน์ (ในกรณีทั่วไป) ว่าความน่าจะเป็นของการโจมตีแบบบดสำเร็จนั้นน้อยมาก
Geoffroy Couteau avatar
cn flag
@Vadym ถูกต้อง ถูกต้องกว่าหากกล่าวว่าเป็นภาษาเชิงเส้น หรือพูดง่ายๆ ว่าจำนวนเฉลี่ยจะเป็นเศษส่วนเล็กน้อยของพื้นที่ท้าทายโดยทั่วไป
Vadym Fedyukovych avatar
in flag
@Geoffroy อาจเป็นไปได้ว่าแนวคิด "พลังแห่งความท้าทาย" นี้เกินจริงในส่วนของฉันและโปรโตคอลΣส่วนใหญ่ที่เผยแพร่นั้นเป็น "เชิงเส้น" อยู่แล้ว ประเด็นของฉันคือมีความคืบหน้าในการออกแบบโปรโตคอล Σ ประเภทนี้เพื่อพิสูจน์ความสัมพันธ์พหุนามก่อนวัน R1CS/snark

โพสต์คำตอบ

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