การเลือกพารามิเตอร์ลอการิทึม Fiat-Shamir แบบไม่ต่อเนื่อง

ฮิวริสติกของ Fiat-Shamir เป็นวิธีการทั่วไปในการสร้างแบบแผนการพิสูจน์ (หรือลายเซ็น) แบบไม่โต้ตอบจากแบบแผนการพิสูจน์ความรู้แบบโต้ตอบ หนึ่ง ตัวอย่าง ของรูปแบบการโต้ตอบที่คล้อยตาม Fiat-Shamir ฮิวริสติกคือ schnorr-ระบุ โปรโตคอลในกลุ่ม Schnorr นั่นคือวิธีที่ฉันจะตีความคำถาม (คำตอบอื่น ๆ หารือเกี่ยวกับมุมมองทั่วไปของฮิวริสติก Fiat-Shamir)

กลุ่ม Schnorr เป็นกลุ่มย่อยของคำสั่งเฉพาะ $คิว$และเครื่องกำเนิดไฟฟ้า $g$, ของ โมดูโลกลุ่มคูณ นายกรัฐมนตรีบางคน $p$. กลุ่มหลักนั่นเอง $\mathbb Z_p^*$ มีคำสั่ง $\varphi(p)=p-1$. เนื่องจากลำดับของกลุ่มย่อยจะแบ่งลำดับกลุ่ม $คิว$ ต้องเป็นการแบ่งเฉพาะ $p-1$. เนื่องจาก $g$ เป็นเครื่องกำเนิดก็ต้องเป็นเช่นนั้น $g^q\equiv1\pmod p$ และ $g\not\equiv1\pmod p$. โดยทั่วไปแล้วกลุ่ม Schnorr จะระบุเป็นจำนวนเต็มสามจำนวน $(p,q,g)$.

จำนวนเฉพาะควรใหญ่แค่ไหน $p$ เป็น? วิธีการเลือก $p$ ตัวอย่างเช่น อัลกอริทึม PohligâHellman หรืออัลกอริทึมอื่น ๆ ที่รู้จักไม่สามารถทำลายมันได้?

เพื่อให้กลุ่ม Schnorr มีความสนใจในการเข้ารหัส ปัญหาลอการิทึมแบบไม่ต่อเนื่องจะต้องเป็นเรื่องยากในกลุ่ม Schnorr นี่แสดงถึงการต่อต้านอัลกอริทึม DLP ที่รู้จัก อัลกอริทึมที่กำหนดขนาดที่ต้องการได้จริง $p$ ในกลุ่ม Schnorr เป็นตัวแปร DLP ของ จีเอ็นเอฟเอส, ซึ่งเป็น แคลคูลัสดัชนี เฉพาะทาง $\mathbb Z_p^*$. เดอะ บันทึกปัจจุบัน เป็นบิต 795 บิต $p$และขนาดขั้นต่ำที่แนะนำสำหรับแอปพลิเคชันปัจจุบันคือ 2048 บิต หรือ 3072 บิตสำหรับ "2030 และหลังจากนั้น"

นอกจากนี้ยังจำเป็นที่ $คิว$ มีขนาดใหญ่พอที่ โรโฮของ Pollard สำหรับ DLP เป็นไปไม่ได้ ค่าใช้จ่ายประมาณ $\Theta(\sqrt q)$ การคูณแบบกลุ่ม ดังนั้น ขอแนะนำอย่างน้อย 224 บิตหรือ 256 บิต $คิว$.

ข้อกำหนดเหล่านี้เพียงพอที่จะประกันการ โพลิก-เฮลล์แมน อัลกอริทึมไม่ต้องกลัว นั่นเป็นเพราะ Pohlig-Hellman ต้องการการแก้ไข DLP ในแต่ละกลุ่มย่อยของคำสั่ง $q^k$ กับ $k\ge 1$, $คิว$ นายกและ $q^k$ การแบ่งลำดับของกลุ่มฐาน และ $k=1$ เป็นกรณีที่ง่ายที่สุด

วิธีเลือกรากดั้งเดิม $g$?

อัลกอริทึมเวลาพหุนามที่น่าจะเป็นนี้จะทำ:

• เลือกไพรม์สุ่ม $คิว$ ตามขนาดที่ต้องการ
• เลือกสุ่มได้ $r$ สำหรับนายกรัฐมนตรี $p=qr+1$ ตามขนาดที่ต้องการ
• เลือกแบบสุ่ม $s$ ใน $[2,p-2]$และคำนวณ $g=s^{(p-1)/q}\bmod p$, จนกระทั่ง $g\ne1$ (ซึ่งเกือบจะแน่นอนอยู่แล้ว)
• เป็นการตรวจสอบความสอดคล้องตรวจสอบ $g^q\bmod พี=1$ (ที่เก็บไว้เว้นแต่จะมีข้อผิดพลาด).

ปลอดภัยไหมที่จะใช้ค่าเดียวกันของ $p$ และ $g$ สำหรับสองความท้าทาย?

ใช่. การรู้วิธีแก้ปัญหาสำหรับ DLP เฉพาะในกลุ่ม Schnorr นั้นไม่ได้ช่วยแก้ปัญหา DLP แบบสุ่มอื่น ๆ ที่ไม่เกี่ยวข้องในกลุ่ม Schnorr เดียวกัน (ยังคงมีความเป็นไปได้ที่การคำนวณล่วงหน้าบางอย่างจะถูกตัดจำหน่ายระหว่าง DLP หลาย ๆ ตัว แต่นั่นก็เล็กน้อย)

เหตุใดการใช้กลุ่ม Schnorr แทนการใช้ไพรม์ที่ปลอดภัยจึงดีกว่า $p$?

นายกรัฐมนตรีที่ปลอดภัย $p$ สอดคล้องกับ $p-1=2q$, หรือ $r=2$ ในข้างต้น แม้ว่าในทางเทคนิคแล้วยังคงตรงกับคำจำกัดความของกลุ่ม Schnorr แต่ก็ไม่ได้ตอบสนองแรงจูงใจที่สำคัญของกลุ่ม Schnorr นั่นคือการมีคำสั่งซื้อ $คิว$ มีขนาดเล็กกว่ามาก $p$. สิ่งนี้น่าสนใจเพราะมีเลขชี้กำลังอยู่ใน $\mathbb Z_q$จึงสั้นลง $คิว$ นำไปสู่การยกกำลังที่เร็วขึ้น ความลับที่สั้นลง และลายเซ็นที่สั้นลง (ในรูปแบบทั่วไปของ Fiat-Shamir heuristic) นอกจากนี้การค้นหาของ $p$ มีส่วนร่วมมากขึ้นเล็กน้อย เท่าที่เราทราบใช้กลุ่ม Schnorr ที่มีขนาดใหญ่พอ $คิว$ และ $p$ มีความปลอดภัยเทียบเท่ากับการใช้ไพรม์ที่ปลอดภัย $p$ ที่มีขนาดใกล้เคียงกัน