รับรู้ว่าค่าสุ่มสองค่าถูกยกกำลังเท่ากันหรือไม่

อลิซเลือกตัวเลขสุ่มสองตัวจากเขตข้อมูลจำกัด $Z_p$ : $a$ และ $ข$.

Bob ทำหนึ่งในสองขั้นตอนต่อไปนี้แบบสุ่ม (บางครั้งเขาทำขั้นตอนที่ 1 บางครั้งทำขั้นตอนที่ 2):

1. เขาเลือกหมายเลขสุ่ม $r$ จาก $Z_p$ และคำนวณ $a^r\;mod\;p$ และ $b^r\;mod\;p$ และมอบคุณค่าทั้งสองนี้ให้กับอลิซ
2. เขาเลือกตัวเลขสุ่มที่แตกต่างกันสองตัว $r$ และ $r'$ จาก $Z_p$ และคำนวณ $a^r\;mod\;p$ และ $b^{r'}\;mod\;p$ และมอบคุณค่าทั้งสองนี้ให้กับอลิซ

มีอัลกอริธึมใดที่มีประสิทธิภาพที่อลิซสามารถใช้เพื่อจดจำขั้นตอนที่บ็อบทำไปแล้วบ้าง

น้อยนี่ $a$ และ $ข$ ควรเลือกจาก $\mathbb{Z}^*_p$ และ $r$ ระหว่าง $1$ และ $p-1$ พิเศษ

ดูเหมือนว่าจะเกี่ยวข้องโดยตรงกับปัญหา DDH อย่างน้อยถ้ามีอยู่บ้าง $w$ เช่นนั้น $a = b^w$ หรือ $b = a^w$. นั่นคือถ้าอย่างน้อยหนึ่งใน $a$ หรือ $ข$ สร้างกลุ่มย่อยที่มีอีกกลุ่มหนึ่งซึ่งจะได้รับหาก $p$ เป็นไพรม์ที่ปลอดภัย [หากทั้งคู่เป็นสารตกค้างกำลังสอง/ไม่มีสารตกค้างอยู่ มิฉะนั้นสิ่งใดก็ตามที่ไม่ใช่สารตกค้างคือเครื่องกำเนิด] ไม่แน่ใจเกี่ยวกับกรณีอื่นๆ ในกรณีนี้ $a, b^{r'}, a^{r}$ ทำให้ DDH triplet สร้างขึ้นจาก $ข$ หรือ $b,a^r,b^{r'}$ ทำ DDH triplet จาก $a$. ในกรณีของคุณปัญหา DDH ยากหรือไม่ขึ้นอยู่กับทางเลือกของ $a$ และ $ข$. ถ้าทั้งสอง $a$ และ $ข$ สร้างกลุ่มย่อยเดียวกันด้วยคำสั่งเฉพาะจำนวนมาก จากนั้นปัญหา DDH นั้นถือว่ายากในคอมพิวเตอร์แบบคลาสสิก ดังนั้นจึงไม่มีอัลกอริธึมแบบคลาสสิกที่มีประสิทธิภาพในกรณีนี้ ปัญหา DDH สามารถแก้ไขได้ด้วยความน่าจะเป็นที่สูงกว่าการคาดเดาแบบสุ่มในหลาย ๆ กรณี เช่น ถ้าทั้งคู่ $a$, $ข$ เป็นโมดูโล่ที่ไม่มีสารตกค้าง $p$ และในหมู่ $a^r, b^{r'}$ อันหนึ่งเป็นเศษซากกำลังสองและอีกอันหนึ่งเป็นเศษที่เหลือซึ่งคุณสามารถบอกได้ว่าอันใดอันหนึ่ง $r,r'$ เป็นคี่และอีกอย่างคือคู่และดังนั้น $r \neq r'$.

ในคำถามของคุณ $a$ และ $ข$ ถูกสร้างขึ้นแบบสุ่ม ดังนั้นฉันจะบอกว่ามันแยกแยะได้ ไม่ใช่ทุกกรณีแต่มีประโยชน์ในกรณีที่กล่าวมาแล้วซึ่งในทางวิทยาการคอมพิวเตอร์ถือว่ามีนัยสำคัญจนแยกไม่ออก

ฉันไม่แน่ใจเกี่ยวกับกรณีที่ทั้งสอง $a$ ก็ไม่เช่นกัน $ข$ สร้างกลุ่มย่อยที่มีอีกกลุ่มหนึ่งเพราะฉันไม่สามารถคิดวิธีเชื่อมโยงกับ DDH ได้ อย่างน้อยที่สุดก็ไม่อยู่ในหัวของฉัน อาจมีกรณีย่อยที่ได้เปรียบในเงื่อนไขนั้นด้วย

การปรับปรุง: คุณได้ระบุว่าคุณกำลังพยายามออกแบบโปรโตคอล ประการแรก ไม่ควรลองทำโดยปราศจากความเข้าใจอย่างลึกซึ้งเกี่ยวกับการเข้ารหัส สมมติว่าความปลอดภัยทั้งหมดของระบบขึ้นอยู่กับสิ่งนี้ คุณควรใช้ $g$ ที่ใช้สร้าง $a$ และ $ข$ เพื่อเป็นตัวกำเนิดของกลุ่มย่อยลำดับความสำคัญขนาดใหญ่ $คิว$ และเลือก $r,r'$ ระหว่าง $1$ และ $คิว$ เพื่อให้แน่ใจว่าปัญหา DDH คาดเดาได้ยากในคอมพิวเตอร์แบบคลาสสิก หรือใช้กลุ่ม EC ที่เป็นมิตรซึ่งไม่มีการจับคู่ที่รู้จักซึ่งปัญหา DDH ถูกคาดเดาว่ายากแบบคลาสสิก แต่ฉันยังไม่รู้รายละเอียดของโปรโตคอล และการนำมันไปใช้ก็ยังมีปัญหา เช่น การโจมตีจากช่องทางด้านข้าง เป็นต้น

หาก Bob เต็มใจช่วย Alice จดจำกรณีที่ 1 เขาสามารถใช้โปรโตคอลที่คล้ายกับ Schnorr เป็นตัวพิสูจน์ได้ เขาจะตอบสนองการรักษา $r$ เป็นคีย์ส่วนตัวตรงตามที่โปรโตคอลกำหนด อลิซจะตรวจสอบว่าคำตอบนี้ตรงกับตัวเลขสุ่มหรือไม่ ซึ่งถือว่าเป็นคีย์สาธารณะสองคีย์