Score:0

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

ธง ph

ตาม FiatâShamir ฮิวริสติก มีสองพารามิเตอร์ของอัลกอริทึม: จำนวนเฉพาะมาก $p$ และรากดั้งเดิม $g$. จึงเกิดคำถามตามมามากมายว่า

  1. จำนวนเฉพาะควรใหญ่แค่ไหน $p$ เป็น? วิธีการเลือก $p$ ตัวอย่างเช่น อัลกอริทึม PohligâHellman หรืออัลกอริทึมอื่น ๆ ที่รู้จักไม่สามารถทำลายมันได้?
  2. วิธีเลือกรากดั้งเดิม $g$? เท่าที่ฉันรู้มันเป็นปัญหาของ NP
  3. ปลอดภัยไหมที่จะใช้ค่าเดียวกันของ $p$ และ $g$ สำหรับสองความท้าทาย?
Кирилл Волков avatar
ph flag
@fgrieu เหตุใดการใช้ Schnor group แทน safe prime จึงดีกว่า
Score:2
ธง cn

ดูเหมือนจะมีความสับสนที่นี่ตามที่ fgrieu ระบุไว้อย่างถูกต้อง Fiat-Shamir เป็นวิธีการสร้างเหรียญสาธารณะ คุณไม่จำเป็นต้องเลือกพารามิเตอร์ใดๆ สำหรับ Fiat-Shamir นอกเหนือจากฟังก์ชันแฮช: พารามิเตอร์อื่นๆ ทั้งหมดเป็นพารามิเตอร์ของโปรโตคอลแบบโต้ตอบซึ่งคุณกำลังสร้างแบบไม่โต้ตอบ หรือของคำสั่งที่คุณกำลังพยายามพิสูจน์ โดยปกติแล้ว สำหรับการพิสูจน์ความรู้ของลอการิทึมแบบไม่ต่อเนื่อง กลุ่ม ตัวกำเนิด $g$และโมดูลัส $p$เป็นส่วนหนึ่งของคำอธิบายของคำสั่ง การพิสูจน์ Schnorr เป็นหลักฐานเชิงโต้ตอบสำหรับการจัดการข้อความดังกล่าว และ Fiat-Shamir สามารถใช้เพื่อทำให้เป็นแบบโต้ตอบไม่ได้

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

Score:1
ธง ng

ฮิวริสติกของ Fiat-Shamir เป็นวิธีการทั่วไปในการสร้างแบบแผนการพิสูจน์ (หรือลายเซ็น) แบบไม่โต้ตอบจากแบบแผนการพิสูจน์ความรู้แบบโต้ตอบ หนึ่ง ตัวอย่าง ของรูปแบบการโต้ตอบที่คล้อยตาม Fiat-Shamir ฮิวริสติกคือ โปรโตคอลในกลุ่ม 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$ ที่มีขนาดใกล้เคียงกัน

โพสต์คำตอบ

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