คำถาม
ฉันแสวงหาก ดีขึ้นในเชิงปริมาณ การพิสูจน์ทฤษฎีบท 13.11 ใน Katz และ Lindell's รู้เบื้องต้นเกี่ยวกับการเข้ารหัสสมัยใหม่ (3ถ ฉบับ) (หรือเกือบเท่ากัน ทฤษฎีบท 19.1 ใน Dan Boneh และ Victor Shoup ให้ใช้ได้ฟรี หลักสูตรบัณฑิตศึกษาในการเข้ารหัสประยุกต์). หลักฐานเกี่ยวกับแผนการระบุ Schnorr สำหรับกลุ่มทั่วไป $\คณิตศาสตร์แคล G$ ลำดับนายก $q=\lvert\mathcal G\rvert$ และเครื่องกำเนิดไฟฟ้า $g\in\คณิตศาสตร์แคล G$สำหรับการเรียกร้อง:
หากปัญหาลอการิทึมไม่ต่อเนื่องเป็นเรื่องยากเมื่อเทียบกับ $\คณิตศาสตร์แคล G$โครงร่างการระบุตัวตนของ Schnorr จะปลอดภัย
โครงการไป:
- Prover (P) ดึงคีย์ส่วนตัว $x\gets\mathbb Z_q$คำนวณและเผยแพร่รหัสสาธารณะ $y:=g^x$โดยถือว่ามีความซื่อสัตย์
- ในการระบุแต่ละครั้ง:
- Prover (P) จับฉลาก $k\gets\mathbb Z_q$คำนวณและส่ง $I:=g^k$
- Verifier (V) วาดและส่ง $r\gets\mathbb Z_q$
- Prover (P) คำนวณและส่ง $s:=r\,x+k\bmod q$
- Verifier (V) ตรวจสอบว่า $g^s\;y^{-r}\;\overset?=\;I$
หลักฐานที่ได้รับคือความขัดแย้ง เราถือว่าอัลกอริทึม PPT $\คณิตศาสตร์ A$ ที่กำหนดให้ $y$ แต่ไม่ $x$ระบุได้สำเร็จด้วยความน่าจะเป็นที่ไม่หายไป เราสร้างอัลกอริทึม PPT ต่อไปนี้ $\คณิตศาสตร์แคล A'$:
- วิ่ง $\คณิตศาสตร์แคล A(y)$ซึ่งได้รับอนุญาตให้สอบถามและสังเกตการถอดเสียงที่ซื่อสัตย์ $(ฉัน,r,s)$ก่อนถึงขั้นตอนต่อไป
- เมื่อไร $\คณิตศาสตร์ A$ เอาต์พุต $I$, เลือก $r_1\gets\mathbb Z_q$ และมอบให้ $\คณิตศาสตร์ A$ซึ่งตอบสนองด้วย $s_1$.
- วิ่ง $\คณิตศาสตร์แคล A(y)$ ครั้งที่สองด้วยเทปสุ่มแบบเดียวกันและการถอดเสียงที่ตรงไปตรงมา และเมื่อผลลัพธ์ออกมา (เหมือนเดิม) $I$, เลือก $r_2\gets\mathbb Z_q$ กับ $r_2\ne r_1$ และให้ $r_2$ ถึง $\คณิตศาสตร์ A$.
ในท้ายที่สุด, $\คณิตศาสตร์ A$, ตอบกลับด้วย $s_2$.
- คำนวณ $x:=(r_1-r_2)^{-1}(s_1-s_2)\bmod q$, การแก้ปัญหา DLP
พูดขั้นตอนที่ 2 เสร็จสมบูรณ์ด้วยความน่าจะเป็น $\epsilon$. ฉันได้รับหลักฐานของหนังสือกำหนดขั้นตอนที่ 3 เสร็จสมบูรณ์ด้วยความน่าจะเป็นเป็นอย่างน้อย $\epsilon^2-1/q$เหตุใดขั้นตอนที่ 4 จึงแก้ไข DLP เหตุใดจึง $\epsilon^2$ ปรากฏขึ้นและทำไมเราต้องมีขนาดใหญ่ $คิว$ เพื่อเข้าใกล้สิ่งนั้น
เราสามารถลด DLP ในเชิงปริมาณที่น่าเชื่อถือได้หรือไม่
สิ่งที่ไม่น่าพอใจคือ: $\epsilon^2$ซึ่งสามารถแปลได้ว่ามีโอกาสประสบความสำเร็จต่ำ เราต้องการลดลงเมื่อความน่าจะเป็นของความสำเร็จเพิ่มขึ้นเป็นเส้นตรงตามเวลาที่ใช้ ซึ่งมีความน่าจะเป็นต่ำ นอกจากนี้ ความน่าจะเป็นของความสำเร็จจะได้รับโดยเฉลี่ยทั้งหมด $y\in\คณิตศาสตร์แคล G$ไม่ใช่สำหรับปัญหา DLP เฉพาะ
เพื่อให้ประเด็นแรกเป็นรูปธรรม: ถ้า $\คณิตศาสตร์ A$ สำเร็จด้วยความน่าจะเป็น $\epsilon=2^{-20}$ ใน $1$ ประการที่สอง การพิสูจน์บอกว่าเราสามารถแก้ DLP เฉลี่ยด้วยความน่าจะเป็นได้ $2^{-40}$ ใน $2$ วินาที นั่นไม่มีประโยชน์โดยตรง แม้ว่าเราจะทำให้มันกลายเป็นความน่าจะเป็นได้ก็ตาม $1/2$ ใน $2^{40}$ วินาที (11 ศตวรรษ) เราต้องการความน่าจะเป็น $1/2$ ใน $2^{21}$ วินาที (25 วัน)
คำตอบเบื้องต้น
นี่คือความพยายามของฉันสำหรับการวิจารณ์ ฉันอ้างว่าเราสามารถแก้ไข DLP เฉพาะใน $G$ ด้วยเวลาที่คาดไว้ $2t/\epsilon$ (และด้วยความน่าจะเป็น $>4/5$ ภายในเวลา $3t/\epsilon$) บวกกับเวลาสำหรับงานที่ระบุ โดยสมมติเป็นอัลกอริทึม $\คณิตศาสตร์ A$ ที่ระบุรหัสสาธารณะแบบสุ่มในเวลา $t$ ด้วยความน่าจะเป็นที่ไม่หายไป $\epsilon$, และ $คิว$ ใหญ่พอที่เราสามารถลดราคาค่าใดค่าหนึ่งในการสุ่มเลือกได้ $\mathbb Z_q$.
หลักฐานที่อ้างสิทธิ์:
ก่อนอื่น เราสร้างอัลกอริทึมใหม่ $\คณิตศาสตร์แคล A_0$ ที่ป้อนคำอธิบายของการตั้งค่า $(\คณิตศาสตร์แคล G,g,q)$ และ $h\in\คณิตศาสตร์แคล G$
- สุ่มเลือกอย่างสม่ำเสมอ $u\gets\mathbb Z_q$
- คำนวณ $y:=h\;g^u$
- เรียกใช้อัลกอริทึม $\คณิตศาสตร์ A$ ด้วยการป้อนข้อมูล $y$ ทำหน้าที่เป็นรหัสสาธารณะแบบสุ่ม
- เมื่อไหร่ก็ตาม $\คณิตศาสตร์ A$ ขอใบรับรองผลการเรียนที่ซื่อสัตย์ $(ฉัน,r,s)$
- สุ่มเลือกอย่างสม่ำเสมอ $r\gets\mathbb Z_q$ และ $s\gets\mathbb Z_q$
- คำนวณ $I:=g^s\;y^{-r}$
- จัดหา $(ฉัน,r,s)$ ถึง $\คณิตศาสตร์ A$ซึ่งแตกต่างจากการถอดเสียงที่ซื่อสัตย์สำหรับรหัสสาธารณะ $y$
- ถ้า $\คณิตศาสตร์ A$ เอาต์พุต $I$ ภายในเวลารันที่จัดสรรไว้ $t$กำลังพยายามตรวจสอบสิทธิ์
- (หมายเหตุ: เราจะเริ่มต้นใหม่จากที่นี่)
- สุ่มเลือกอย่างเท่าเทียมกัน $r\gets\mathbb Z_q$ และส่งต่อไปยัง $\คณิตศาสตร์ A$
- ถ้า $\คณิตศาสตร์ A$ เอาต์พุต $s$ ภายในเวลารันที่จัดสรรไว้ $t$
- ตรวจสอบ $g^s\;y^{-r}\;\overset?=\;I$ และถ้าเป็นเช่นนั้น ผลลัพธ์ $(u,r,s)$
- มิฉะนั้นให้ยกเลิกโดยไม่มีผลลัพธ์
อัลกอริทึม $\คณิตศาสตร์แคล A_0$ เป็นอัลกอริทึม PPT สำหรับอินพุตคงที่ใดๆ $h\in\คณิตศาสตร์แคล G$ มีความน่าจะเป็นในการวิ่งแต่ละครั้ง $\epsilon$ ไปยังเอาต์พุต $(u,r,s)$, เพราะ $\คณิตศาสตร์ A$ ดำเนินการภายใต้เงื่อนไขที่กำหนด $\epsilon$.
เราสร้างอัลกอริทึมใหม่ $\คณิตศาสตร์แคล A_1$ ที่ป้อนการตั้งค่า $(\คณิตศาสตร์แคล G,g,q)$ และ $h\in\คณิตศาสตร์แคล G$
- วิ่งซ้ำๆ $\คณิตศาสตร์แคล A_0$ กับอินพุตนั้นจนถึงเอาต์พุต $(คุณ,r_1,s_1)$. การวิ่งแต่ละครั้งมีความน่าจะเป็น $\epsilon$ เพื่อให้สำเร็จ ดังนั้น ขั้นตอนนี้คาดว่าจะต้องใช้ $t/\epsilon$ เวลาวิ่ง $\คณิตศาสตร์ A$.
- เริ่มต้นใหม่ $\คณิตศาสตร์แคล A_0$ จากจุดรีสตาร์ทที่บันทึกไว้ (เทียบเท่า: รันใหม่ตั้งแต่เริ่มต้นด้วยอินพุตเดียวกันและเทปสุ่มจนถึงจุดรีสตาร์ทด้วยการสุ่มใหม่หลังจากจุดรีสตาร์ท) จนกว่าจะส่งออก $(u,r_2,s_2)$. การวิ่งแต่ละครั้งมีความน่าจะเป็นเป็นอย่างน้อย $\epsilon$ ให้สำเร็จ (หลักฐานติดตามได้จาก ทฤษฎีบทนั้นเกี่ยวกับความน่าจะเป็นที่ไม่ลดลงของความสำเร็จของอัลกอริทึม ฉันพยายามขอข้อมูลอ้างอิง) ดังนั้นขั้นตอนนี้คาดว่าจะไม่เกิน $t/\epsilon$ เวลาวิ่ง $\คณิตศาสตร์ A$.
- ในกรณี (สันนิษฐานว่าเป็นไปได้อย่างท่วมท้น) $r_1\ne r_2$คำนวณและส่งออก $z:=s_1-s_2-u\bmod q$.
ในผลลัพธ์นั้น ทั้งสองรันของ $\คณิตศาสตร์แคล A_0$ ที่ผลิต $(คุณ,r_1,s_1)$ และ $(u,r_2,s_2)$ ได้ตรวจสอบ $g^{s_i}\;y^{-{r_i}}=I$ กับ $y=h^u$ สำหรับสิ่งเดียวกัน $u$ และ $I$ นั่น $\คณิตศาสตร์แคล A_0$ กำหนดและ $h$ ให้ที่การป้อนของ $\คณิตศาสตร์แคล A_1$. ดังนั้น $\คณิตศาสตร์แคล A_1$ พบ $z$ กับ $h=g^z$จึงแก้ปัญหา DLP ตามอำเภอใจ $h$. คาดว่าจะใช้เวลาดำเนินการใน $\คณิตศาสตร์ A$ มากที่สุด $2t/\epsilon$, และที่เหลือทำให้ $\mathcal O(\log(q))$ การดำเนินการกลุ่มสำหรับการเรียกใช้แต่ละครั้ง $\คณิตศาสตร์ A$ และใบรับรองผลการเรียนที่ซื่อสัตย์แต่ละรายการนั้นต้องการ
$\lfloor3/\epsilon\rfloor$ วิ่งของ $\คณิตศาสตร์ A$ ก็เพียงพอสำหรับอย่างน้อยสองคนที่จะประสบความสำเร็จด้วยความน่าจะเป็นที่ดีกว่า $1-4\,e^{-3}>4/5$: ดูพล็อตนี้ของ $1-(1-\epsilon)^{\lfloor3/\epsilon\rfloor}-\lfloor3/\epsilon\rfloor\,\epsilon\,(1-\epsilon)^{\lfloor3/\epsilon\rfloor-1} $