การลดลงเชิงปริมาณของแผนการระบุตัวตนของ Schnorr เป็น DLP

คำถาม

ฉันแสวงหาก ดีขึ้นในเชิงปริมาณ การพิสูจน์ทฤษฎีบท 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$โดยถือว่ามีความซื่อสัตย์
• ในการระบุแต่ละครั้ง:
  1. Prover (P) จับฉลาก $k\gets\mathbb Z_q$คำนวณและส่ง $I:=g^k$
  2. Verifier (V) วาดและส่ง $r\gets\mathbb Z_q$
  3. Prover (P) คำนวณและส่ง $s:=r\,x+k\bmod q$
  4. Verifier (V) ตรวจสอบว่า $g^s\;y^{-r}\;\overset?=\;I$

หลักฐานที่ได้รับคือความขัดแย้ง เราถือว่าอัลกอริทึม PPT $\คณิตศาสตร์ A$ ที่กำหนดให้ $y$ แต่ไม่ $x$ระบุได้สำเร็จด้วยความน่าจะเป็นที่ไม่หายไป เราสร้างอัลกอริทึม PPT ต่อไปนี้ $\คณิตศาสตร์แคล A'$:

1. วิ่ง $\คณิตศาสตร์แคล A(y)$ซึ่งได้รับอนุญาตให้สอบถามและสังเกตการถอดเสียงที่ซื่อสัตย์ $(ฉัน,r,s)$ก่อนถึงขั้นตอนต่อไป
2. เมื่อไร $\คณิตศาสตร์ A$ เอาต์พุต $I$, เลือก $r_1\gets\mathbb Z_q$ และมอบให้ $\คณิตศาสตร์ A$ซึ่งตอบสนองด้วย $s_1$.
3. วิ่ง $\คณิตศาสตร์แคล A(y)$ ครั้งที่สองด้วยเทปสุ่มแบบเดียวกันและการถอดเสียงที่ตรงไปตรงมา และเมื่อผลลัพธ์ออกมา (เหมือนเดิม) $I$, เลือก $r_2\gets\mathbb Z_q$ กับ $r_2\ne r_1$ และให้ $r_2$ ถึง $\คณิตศาสตร์ A$.

   ในท้ายที่สุด, $\คณิตศาสตร์ A$, ตอบกลับด้วย $s_2$.

4. คำนวณ $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} $

$ \newcommand{\sR}{\mathcal{R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $

นี่เป็นการวิเคราะห์ที่เข้มงวดที่สุดที่ฉันคิดได้ -- มันใช้ Splitting Lemma แต่ตัดสินใจพิมพ์ลงไปโดยหวังว่าจะมีคนเห็นว่ามันมีประโยชน์ (โปรดอย่าลังเลที่จะชี้ให้เห็นข้อผิดพลาดใดๆ)

(การวิเคราะห์ด้านล่างมีไว้สำหรับอินสแตนซ์ DLP คงที่ แต่สามารถขยายแนวคิดได้อย่างง่ายดาย)

บทแยก [บทที่ 1, PS]: อนุญาต $\sG\subseteq\sR_-\times\sR_+$ เป็นอย่างนั้น $$\Pr_{(\rho_-,\rho_+)\in\sR_-\times\sR_+}[(\rho_-,\rho_+)\in\sG]\geq\epsilon.$$ สำหรับใดๆ $\beta<\epsilon$, กำหนด $$\sB:=\left\{(\rho_-,\rho_+)\in\sR_-\times\sR_+:\Pr_{\rho_+'\in\sR_+}[(\rho_-,\ rho_+')\in\sG\right\}.$$ การระงับต่อไปนี้:

1. $\Pr[\sB|\sG]\geq\beta/\epsilon$ และ
2. $\Pr_{\rho_+'\in\sR_+}[(\rho_-,\rho_+')\in\sG|(\rho_-,\rho_+)\in\sB]\geq \epsilon-\ เบต้า $

ที่นี่, $\sG$ เป็นชุดของเหรียญสุ่มที่ 'ดี' ในแง่ที่ว่าสิ่งเหล่านี้ทำให้ฝ่ายตรงข้ามประสบความสำเร็จและ $\sB\subseteq\sG$ เป็นส่วนย่อยของเหรียญสุ่มที่ 'ดีกว่า' ในแง่ที่การย้อนกลับและเล่นซ้ำโดยใช้เหรียญเหล่านี้น่าจะประสบความสำเร็จ บทสรุปแรกของบทแทรกคือเหรียญที่ดีย่อมดีกว่าด้วยความน่าจะเป็นเป็นอย่างน้อย $\beta/\epsilon$ และข้อสรุปที่สองคือการสุ่มตัวอย่างเหรียญที่ดีกว่าใหม่จะนำไปสู่เหรียญที่ดีโดยมีความเป็นไปได้เป็นอย่างน้อย $\epsilon-\beta$.

การวิเคราะห์ส่วนแรกของการลดลงนั้นตรงไปตรงมา: ความน่าจะเป็นที่ทั้งหมด $1/\epsilon$ การดำเนินการล้มเหลวคือ $1-(1-\epsilon)^{1/\epsilon}$. สมมติว่าการดำเนินการครั้งล่าสุดสำเร็จ เรามาระบุเหรียญที่ฝ่ายตรงข้ามใช้ในการดำเนินการนี้ก่อนและหลังจุดย้อนกลับโดย $\rho_-$ และ $\rho_+$ตามลำดับ จาก Splitting Lemma ความน่าจะเป็นที่การเล่นซ้ำอย่างน้อยหนึ่งรายการจะสำเร็จคือ $$\frac{\beta}{\epsilon}\left((1-(1-(\epsilon-\beta))^{1/\epsilon}\right).$$ ที่นี่, $\beta/\epsilon$ คือความน่าจะเป็นที่การดำเนินการครั้งสุดท้าย (ซึ่งเรารู้ว่าดี) จะดีกว่า (โดยสรุป $1$) และ $(\epsilon-\beta)$ ภายในวงเล็บคือความน่าจะเป็นที่การสุ่มตัวอย่างเหรียญที่ดีกว่าใหม่จะนำไปสู่เหรียญที่ดี (โดยสรุป $2$).

หากต้องการปรับสมการด้านบนให้เหมาะสม ให้ตั้งค่า $\beta=\epsilon(1-\epsilon)$ (ซึ่งใกล้เคียงกับ $\epsilon$). สิ่งนี้ทำให้มีโอกาสสำเร็จ $(1-\epsilon)(1-(1-\epsilon^2)^{1/\epsilon})$.

[PS]: พอยต์เชวาลและสเติร์น ข้อโต้แย้งด้านความปลอดภัยสำหรับลายเซ็นดิจิทัลและลายเซ็นตาบอด,จค.2543.

ให้ฉันลองตอบคำถามของคุณ :)

ก่อนอื่น ตามคำอธิบายของคุณ (ฉันไม่มีหนังสือที่คุณกล่าวถึง) คำถามนี้เป็นของทฤษฎีความปลอดภัยที่พิสูจน์ได้ แนวคิดทั่วไปของการรักษาความปลอดภัยที่พิสูจน์ได้คือ: สมมติว่ามีอัลกอริทึม/ฝ่ายตรงข้าม ก สามารถทำลายโครงร่างที่ใช้การเข้ารหัสลับด้วยความน่าจะเป็นที่ไม่สำคัญ อีแล้วจำลอง/ผู้ท้าชิง ส สามารถแก้ปัญหาทางคณิตศาสตร์ได้ โครงร่างจะขึ้นอยู่กับการโต้ตอบกับ ก ด้วยความน่าจะเป็นที่ไม่มีนัยสำคัญ **อี' <= อี** กำหนดโดยความน่าจะเป็นของความล้มเหลว

ยิ่งไปกว่านั้น กระบวนการพิสูจน์ความปลอดภัยควรอิงตามเกม/รูปแบบการโจมตีของฝ่ายตรงข้าม เช่น IND-CPA, EUF-CMA เป็นต้น ซึ่งกำหนดความสามารถของฝ่ายตรงข้ามในรูปแบบนั้นๆ ดังนั้น ฉันคิดว่าหลักฐานที่ให้ในส่วนคำถามของคุณอิงตาม EUF-DCMA และหลักฐานในส่วนคำตอบของคุณอิงตาม EUF-CMA

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

ทีนี้มาดูหลักฐานต้นฉบับกัน หากต้องการแก้ปัญหา DLP เครื่องจำลองจะย้อนกลับ ก ที่ ขั้นตอนที่ 3. นั่นคือ ก ถูกรันสองครั้ง ดังนั้น ความน่าจะเป็นที่จะสกัดได้สำเร็จ x เป็น $e'=e*e=e^2$เนื่องจากเป็นเหตุการณ์ต่อเนื่อง นอกจากนี้ในขั้นตอนที่ 3 ความน่าจะเป็นของ $r_1=r_2$ เป็น $1/คิว$. ดังนั้น เราต้องลบด้วย $1/คิว$ เพื่อแก้ไขความน่าจะเป็นที่สำเร็จขั้นสุดท้าย $e'=e^2-1/q$.

กระบวนการพิสูจน์ความปลอดภัยเป็นการทดลองทางความคิดแบบหนึ่ง เช่นเดียวกับ Schroedinger's Cat (อาจไม่เหมาะสม) เราไม่จำเป็นต้องนำมันเข้าสู่การทดลองจริง ก็เพียงพอแล้วที่เราจะลดความปลอดภัยของโครงร่างลงเหลือปัญหาหนักๆ อย่างน้อยหนึ่งปัญหา

กระบวนการพิสูจน์ที่คุณอ้างนั้นน่าสนใจมากและเป็นความรู้ของฉัน มีที่ยอดเยี่ยม หนังสือ เพื่อทำความเข้าใจเพิ่มเติมเกี่ยวกับความปลอดภัยที่พิสูจน์ได้