ความเป็นเอกลักษณ์และลายเซ็นของ Schnorr

ฉันกำลังพยายามวิเคราะห์เกม "เอกลักษณ์" เกี่ยวกับลายเซ็นของ Schnorr เกมดังกล่าวอธิบายไว้ใน $\textbf{B.}$ และฉันพยายามที่จะให้ใน $\textbf{1.}$ และ $\textbf{2.}$ คำตอบที่ไม่สมบูรณ์บางส่วนเพื่อแก้ไข สามารถแก้ไขได้อย่างเต็มที่หรือไม่? ฉันไม่ได้ใช้ในการวิเคราะห์การลดปัญหา DL; อาจมีวิธีลดเกมลงหรือไม่? ขออภัยสำหรับการขาดความเข้มงวดในการเข้ารหัสและขอบคุณมากสำหรับการอ่าน

$ \textbf{ก. สมมติฐานการเข้ารหัส:}$

เราจะใช้ฟังก์ชันแฮชการเข้ารหัสที่ปลอดภัย $H$ เอาท์พุทใน $\mathbb Z_n$, ที่ไหน $n$ คือลำดับของเส้นโค้ง สมมติเป็นจำนวนเฉพาะ เราถือว่าลำดับเฉพาะเป็นจำนวนเฉพาะของ $256$ ตัวเลขเมื่อเขียนเป็นฐาน $2$.

$\textbf{บี เกมเข้ารหัส:}$

สมมติว่าเป็นจุดโค้งวงรี $S$ ได้รับการคำนวณหลังจากเลือกทูเพิลแล้ว $\{R,X,m\}$, ที่ไหน $S := R + H(X,R,m).X$ เช่นเดียวกับลายเซ็น Schnorr เราสามารถหาทูเพิลได้จริงหรือไม่ $\{R',X',m'\}$ เช่น $\{R',X',m'\} \neq \{R,X,m\}$ (อย่างน้อยหนึ่งในองค์ประกอบที่แตกต่างกันในสองชุด) การตรวจสอบ $R' + H(X',R',m').X' = S = R + H(X,R,m).X$ ?

เราตั้งสมมติฐานเพิ่มเติมว่าทูเพิล $\{X,R,m\}$ ฝ่ายตรงข้ามสามารถเลือกได้ก่อนเกม เช่น ทูเพิล $\{X,R,m\}$ ผู้ตรวจสอบไม่ได้จัดเตรียมไว้ให้เขา

$\textbf{1. สมมติว่าความรู้ของลอการิทึมแยกเป็น $S$:} $

หากเกมข้างต้นกำหนดให้ต้องแสดงหลักฐานความรู้เรื่องลอการิทึมแบบไม่ต่อเนื่องแก่ S ต่อผู้ตรวจสอบ (เช่น ความรู้เกี่ยวกับ $s$ ดังนั้น $s.G = S$หรืออีกนัยหนึ่งคือเริ่มต้นด้วยลายเซ็น Schnorr ที่ถูกต้อง) ดูเหมือนว่าคำตอบจะเป็นลบ

สมมติขึ้นชั่วคราวว่า $\{X,R, m\}$ และถูกต้อง $s$ โดยตรงโดยผู้ตรวจสอบกับฝ่ายตรงข้าม โดยใช้สัญลักษณ์ธรรมชาติ ฝ่ายตรงข้ามจำเป็นต้องค้นหา $r', x'$ และ $m'$ ดังนั้น $r' + H(X',R',m').x' = s$. ดูเหมือนจะเป็นวิธีเดียวที่จะทำเช่นนี้ได้ เนื่องจากต้องเพิ่มโมดูโลจำนวนเต็มแบบสุ่มสองตัว $n$ กัน (ที่นี่ $r'$, เลือกแบบสุ่ม และ $H(X',R',m').x'$, โมดูโลจำนวนเต็มแบบสุ่ม $n$ เนื่องจากฟังก์ชันแฮชมีความปลอดภัยในการเข้ารหัสโดยการสันนิษฐาน) ส่งผลให้เกิดโมดูโลจำนวนเต็มแบบสุ่ม $n$ซึ่งเป็นผลมาจากผลรวมของโมดูโลจำนวนเต็มสุ่มที่กระจายอย่างสม่ำเสมอ 2 ตัว $n$ เป็นโมดูโลจำนวนเต็มแบบสุ่มที่กระจายอย่างสม่ำเสมอ $n$. เราสามารถละเว้นข้อความ $m$ สำหรับเกมนี้และบังคับให้ป้อนข้อมูลอย่างดุร้าย $r'$, $x'$ (หรือเทียบเท่าเพียงเดรัจฉานบังคับให้เปิด $r'$) ดูเหมือนจะเป็นทางออกเดียวในการชนะเกม ซึ่งทำให้เพลิดเพลิน $256$บิตความปลอดภัยและด้วยเหตุนี้จึงไม่สามารถรักษาได้ ฉันสงสัยว่าการให้เหตุผลนั้นถูกต้องหรือไม่ถูกต้อง?

กลับไปสู่สมมุติฐานเดิมของ $\textbf{B.}$ดูเหมือนว่านี่เป็นไปได้จริงที่ขอบเขตบนของเกมจะ $128$-bit security (ยังเป็นความยากที่ไม่สามารถแก้ไขได้ แต่เป็นเพียงขอบเขตบนเท่านั้น) แทน $256$ เมื่อไร $\{X, R, m\}$ สามารถเลือกได้โดยฝ่ายตรงข้าม (และไม่ได้มอบให้เขา) แก้ไข $x'=x$ และ $r$ และ $r'$ฝ่ายตรงข้ามสามารถแก้ปัญหาวันเกิดและค้นหาบางอย่างได้ $m$ และ $m'$ (โดยใช้อัลกอริทึมวันเกิด) ตรวจสอบความสัมพันธ์ด้านล่างซึ่งเป็นวิธีแก้ปัญหาของเกม: $H(X,R,m) - H(X,R',m') = (r' - r).x^{-1}$.

$\textbf{2. ไม่ถือว่าความรู้เรื่องลอการิทึมแยกเป็น $S$:} $

ฉันไม่แน่ใจว่าข้อโต้แย้งข้างต้นใน $\textbf{1.}$ ถูกต้องโดยประมาณ แต่สถานการณ์นี้ดูยากขึ้นเล็กน้อยที่จะศึกษา

$\textit{2. a) สมมติความรู้ของลอการิทึมแบบไม่ต่อเนื่องให้กับ nonces:}$

ในการชนะเกมนี้ เราจะต้องแสดงหลักฐานความรู้เรื่องลอการิทึมที่ไม่ต่อเนื่องให้กับทั้งสองฝ่ายด้วย $R$ และ $R'$ (หลักฐานความรู้อย่างหนึ่งก็เพียงพอแล้วหาก $R' = R$). เพื่อพยายามแก้ปัญหาที่เราคิดว่ามีคนชนะเกม ซึ่งหมายความว่าโดยการลบสองความสัมพันธ์ที่ผู้ชนะเกมต้องรู้ $u$ ดังนั้น: $$u.G = H(X, R, m).X - H(X',R', m').X'.$$

สมมติว่าเกมนี้ชนะด้วย $X = X'$หมายความว่าลอแกร์ทม์แยกของ $X$ ต้องรู้เพราะต้องรู้จริงว่า $u.G = (H(X, R, m) - H(X,R', m')).X$, และเราด้วยเหตุนี้ในกรณีของ $\textbf{1.}$.

ถ้า $R = R'$ ($X'$ จะเท่ากันหรือไม่ก็ได้ $X$) จากนั้นเราจะถอยกลับในกรณีเฉพาะที่ $u=0$และเรามีสิ่งนั้น $X' = H(X, R, m).H(X',R, m')^{-1}.X$เช่น ลอการิทึมแยก $a$ ของ $X'$ ด้วยความเคารพ $X$ ต้องตรวจสอบ $a = H(X, R, m).H(X',R, m')^{-1}$. แก้ไข $X$ และ $X'$ ดังนั้น $X' = a.X$ สำหรับบางคน $a$อัลกอริทึมที่ดีที่สุดในการแก้ปัญหานี้ดูเหมือนจะเป็นอัลกอริทึมวันเกิดที่มีการป้อนข้อมูลรอบ ๆ $2^{128}$ ข้อความที่แตกต่างกันในการท้าทายเพื่อค้นหาบางอย่างในที่สุด $m$ และ $m'$ ที่ตรวจสอบ $a.H(X',R, m') - H(X, R, m) = 0$.

ถ้าทั้งสอง $X \neq X'$, และ $R \neq R'$ฉันไม่สามารถจัดการเพื่อหาข้อสรุปที่เป็นไปได้ มีใครพอจะทราบคำตอบหรือข้อมูลอ้างอิงสำหรับกรณีนี้หรือไม่?

$\textit{2. b) สมมติความรู้ของลอการิทึมแยกไปยังคีย์สาธารณะ:}$

ดูเหมือนเราจะถอยกลับไปสู่คดี $R = R'$ ของ $\textit{2. ก)}$ ถ้า $R = R'$แต่ฉันไม่จัดการที่จะสรุปว่า $R \neq R'$.

$\textit{2. c) สันนิษฐานว่าไม่มีทั้งลอการิทึมที่ไม่ต่อเนื่องกับ nonces และคีย์:}$

เราสามารถสรุปได้อีกครั้งว่า $R = R'$ โดยใช้อาร์กิวเมนต์เดียวกันกับกรณีใน $\textit{2. ก)}$ สำหรับกรณี $R = R'$แต่ดูเหมือนว่าจะสรุปเป็นอย่างอื่นได้ยากกว่า (เช่น ถ้า $R \neq R'$).