จะเรียกใช้โปรโตคอลคีย์สาธารณะสำหรับการพิสูจน์ตัวตนแบบ Zero-Knowledge ได้อย่างไร

ในเอกสาร Zero-Knowledge Proofs of Identity (โดย Feige, Fiat และ Shamir) มีการอธิบายโปรโตคอล ZK ที่ใช้ประโยชน์จากสารตกค้างกำลังสอง ส่วนที่ 3 อธิบายถึง "แผนการระบุที่มีประสิทธิภาพ" แต่ (ตามความเข้าใจของฉัน) อัลกอริทึม PK ดูเหมือนจะใช้งานไม่ได้ (ในแง่ "ใช้งานไม่ได้" ไม่ใช่ในแง่ของ "ความปลอดภัยต่ำ")

โปรโตคอลการสร้างคีย์คือ (ขั้นตอนที่ 1-3 ถูกยกมาจากกระดาษโดยใช้รูปแบบเดียวกับกระดาษ):

ตั้งค่า: ให้ $n$ เป็นจำนวนเต็ม Blum (ผลคูณของจำนวนเฉพาะสองตัว $p$ และ $คิว$โดยที่ทั้งสอง $p$ และ $คิว$ สอดคล้องกับ 3 mod 4) อนุญาต $Z_n$ ระบุวงแหวนของสิ่งตกค้างภายใต้การทำงานของ mod

1. เลือก $k$ ตัวเลขสุ่ม $S_1, ..., S_k$ ใน $Z_n$.
2. เลือกแต่ละรายการ $I_j$ (สุ่มและอิสระ) เช่น $\pm 1 / S_j^2$ (สมัย น).
3. เผยแพร่ $I = I_1, ..., I_k$ และเก็บไว้ $S = S_1, ..., S_k$ ความลับ.

หากไม่มีสัญกรณ์ ในการรับรหัสสาธารณะ เราจำเป็นต้องคำนวณกำลังสองของแต่ละความลับ $S_j$ แล้วหาผกผันแบบโมดูลาร์ของกำลังสองนี้ หรือ $(n-1)$ คูณอินเวอร์สนี้ (เช่น. $S_j^2 \cdot I_j = 1 (\text{mod}n)$ หรือ $S_j^2 \cdot I_j = -1 (\text{mod}n)$).

ประเด็นคือในขั้นตอนที่ 2 $Z_n$ ไม่ใช่ฟิลด์ซึ่งหมายความว่า $I_j$ ไม่รับประกันว่าจะมีอยู่จริง กล่าวคือใด ๆ $g \ใน Z_n$ จะไม่มีการผกผันหากอย่างใดอย่างหนึ่ง $p | g$ หรือ $q | g$. สำหรับขนาดใหญ่มาก $n$ สิ่งนี้ไม่น่าจะเกิดขึ้น แต่เป็นการง่ายที่จะพิสูจน์ว่ามันเกิดขึ้นเสมอ

หลักฐานการมีอยู่: โดยไม่สูญเสียความหมายทั่วไป $p < q$. แล้ว $p^2 \ใน Z_n$. เพราะ $\text{gcd}(p^2, n) = p > 1$เราเห็นอย่างนั้น $p^2$ ไม่มีผกผัน $Z_n$.

ตัวอย่างเล็กๆ: เมื่อ $n = 21$, ไม่มีสมาชิกของเซตนี้มีการผกผัน $Z_n$ $\{0, 3, 6, 7, 9, 12, 14, 15, 18\}$. บางคนเป็นผู้สมัครที่ถูกต้องเพื่อให้เป็นไปไม่ได้ $I_j$ (ตามข้างบนคือ $S_j = 3$ แล้ว $S^2_j = 9$).

คุณควรทำอย่างไรถ้าคุณได้รับหนึ่งในตัวเลขที่ "เสีย" เหล่านี้ วาดอีกครั้ง? สำหรับขนาดใหญ่ $n$ ความน่าจะเป็นมีน้อย (ง่ายต่อการคำนวณจำนวน "หัก" ใน $Z_n$ เช่น $1 + (p-1) + (q-1) = p+q-1$ซึ่งอันตรธานไป $pq$ สำหรับขนาดใหญ่ $p$ และ $คิว$) แต่อย่างน้อยในการทดสอบการใช้งานที่มีขนาดเล็ก $n$ (ชอบ $n = 21$) มันทำลายรหัสใด ๆ ที่พยายามทำให้ผกผัน