Score:4

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

ธง ng

คำถาม

ฉันแสวงหาก ดีขึ้นในเชิงปริมาณ การพิสูจน์ทฤษฎีบท 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} $

พล็อต

ckamath avatar
ag flag
การวิเคราะห์ของคุณดูเหมือนจะมีเหตุผล คุณอาจต้องใช้ *แยกบทแทรก* ของ Pointcheval-Stern (บทแทรก 1 [ที่นี่](https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf)) เพื่อวิเคราะห์การทำงาน เวลาเนื่องจากพื้นที่ความน่าจะเป็นไม่เป็นอิสระโดยสิ้นเชิง: คุณมีช่องว่าง $\mathcal{X}\times\mathcal{Y}$ พร้อมคุณสมบัติบางอย่างและให้ตัวอย่างสุ่ม $(X,Y)$ จากช่องว่างนี้ซึ่ง 'ดี ' เป้าหมายคือการประมาณค่าความน่าจะเป็นของตัวอย่างที่สัมพันธ์กัน $(X,Y')$ โดยที่ $Y'$ แบบสุ่มก็ 'ดี' เช่นกัน ฉันพลาดอะไรไปหรือเปล่า
fgrieu avatar
ng flag
ฉันกำลังพยายามหาทางพิสูจน์ที่ง่ายกว่าบทแทรกแยก และถ้าฉันไม่เข้มงวดนัก ฉันพลาดตรงจุดไหน เหตุผลของฉันคือการรีสตาร์ทมีโอกาสสำเร็จอย่างน้อยเท่ากับการรันจากจุดกำเนิด เพราะเรารีสตาร์ทจากจุดหนึ่งในรันที่สำเร็จ (และทฤษฎีบท/การยืนยันที่เชื่อมโยงกันของฉัน ซึ่งฉันคิดว่าเข้มงวดและมีประโยชน์) ความน่าจะเป็นที่การรีสตาร์ทใช้ $r_2=r_1$ (ซึ่งใช้ไม่ได้) คือ $1/q$ ต่อการรันซ้ำ ดังนั้น $\lfloor3/\epsilon\rfloor/q$ [re-fixed] คือเราทำให้การรันทั้งหมดเพียงพอหรือไม่ สำหรับความน่าจะเป็น $4/5$ ฉันไม่คิดว่าฉันจะประมาณอย่างอื่น
ckamath avatar
ag flag
ดังนั้น ถ้าฉันเข้าใจถูกต้อง คุณสนใจตัวอย่างย้อนแย้งที่การวิเคราะห์แบบไม่เข้มงวดล้มเหลวหรือไม่
fgrieu avatar
ng flag
ฉันกำลังถามว่ามีช่องโหว่ในการพิสูจน์ของฉันหรือไม่ หรือข้อง่ายๆ ที่นำไปสู่ขอบเขตเชิงปริมาณที่ดีเมื่อเปรียบเทียบกัน (เมื่อนำไปใช้ในย่อหน้าก่อน _tentative answer_) วิธีแสดงช่องโหว่ในการพิสูจน์คือตัวอย่าง $\mathcal A$ (ซึ่งสามารถสร้างจาก DLP oracle) ที่มีความน่าจะเป็น $\epsilon$ ของความสำเร็จภายในเวลา $t$ แต่ $\mathcal A_1$ ไม่ใช่ $>4/5-\lfloor3/\epsilon\rfloor/q$ ความน่าจะเป็นของความสำเร็จที่อ้างสิทธิ์หลังจาก $\lfloor3/\epsilon\rfloor$ รัน (เริ่มและรีสตาร์ทรวมกัน) ของ counterexample $\mathcal A$
Score:1
ธง ag

$ \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.

ckamath avatar
ag flag
@fgrieu: [สิ่งนี้](https://eprint.iacr.org/2021/971) ปรากฏใน eprint วันนี้ (จะปรากฏที่ Crypto'21)
Score:0
ธง in

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

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

ยิ่งไปกว่านั้น กระบวนการพิสูจน์ความปลอดภัยควรอิงตามเกม/รูปแบบการโจมตีของฝ่ายตรงข้าม เช่น 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 (อาจไม่เหมาะสม) เราไม่จำเป็นต้องนำมันเข้าสู่การทดลองจริง ก็เพียงพอแล้วที่เราจะลดความปลอดภัยของโครงร่างลงเหลือปัญหาหนักๆ อย่างน้อยหนึ่งปัญหา

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

fgrieu avatar
ng flag
ฉันได้พบกับ EUF-CMA และ EUF-DCMA ในบริบทของลายเซ็นเท่านั้น ในที่นี้ บริบทคือ [รูปแบบ/โปรโตคอลการระบุตัวตน](https://toc.cryptobook.us/book.pdf#page=691) 3 รอบ ดังนั้นจึงเป็นพื้นฐานของรูปแบบลายเซ็นผ่านการแปลง FIat-Shamir , ถ้าเราเพิ่มแฮชและข้อความเพื่อเซ็น; ที่นี่ไม่มีเลยและ EUF-CMA กับ EUF-DCMA เป็นเรื่องเกี่ยวกับตัวเลือกข้อความแบบโต้ตอบและแบบไม่โต้ตอบ ค่าที่ใกล้เคียงที่สุดคือ $I$ แต่ใจของฉันเจ็บปวดว่าทำไมการพิสูจน์ของฉันจึงเลือก $I$ แบบโต้ตอบ โดยที่หลักฐานดั้งเดิมทำให้ไม่โต้ตอบ อัปเดต: หนังสือลายเซ็นของ Katz ดูดีมาก!
ming alex avatar
in flag
@fgrieu โดยทั่วไป รูปแบบการระบุตัวตนส่วนใหญ่ไม่มีการโต้ตอบ ในความประทับใจของฉัน รูปแบบการระบุตัวตนของ Schnorr เรียกอีกอย่างว่าโปรโตคอล Sigma ซึ่งเป็นวิธีการรับรองความถูกต้องที่ตอบสนองต่อความท้าทาย อย่างที่คุณพูด มันสามารถเปลี่ยนจากรูปแบบที่ไม่โต้ตอบได้โดยใช้วิธี FIat-Shamirแต่ฉันไม่เข้าใจว่าอะไรทำให้คุณเจ็บปวด ในขั้นตอนการพิสูจน์ทั้งหมด S มีบทบาทเป็นผู้ลงนามหรือผู้ตรวจสอบเพื่อโต้ตอบกับ A เพื่อตอบสนองสิ่งที่ A ต้องการ ดังนั้นเราจึงไม่จำเป็นต้องสนใจว่า A สร้าง *I* หรือลายเซ็น *s* ใน PPT ได้อย่างไร กล่าวอีกนัยหนึ่ง เราสามารถคิดว่า A เป็นกล่องดำ

โพสต์คำตอบ

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