การสร้างอัลกอริทึมตัวแก้ CDH

สมมติ $C_k: (g, g^a, g^b) \mapsto g^{ab}$ เป็นตัวแก้ CDH ของคุณ ที่แก้ด้วยความน่าจะเป็น $1 - \frac{1}{2^k}$ และสัญลักษณ์พิเศษอื่นๆ มาสร้างมันจาก $C_1$ เรียกซ้ำ

โครงสร้างของ $C_{k+1}$:

1. คำนวณ $C_k(g, g^a, g^b)$. ถ้ามันกลับมา $ก^{ab}$, ส่งออก (ความน่าจะเป็นของสิ่งนี้คือ $1 - \frac{1}{2^k}$). มิฉะนั้น ให้ไปที่ขั้นตอนที่สอง
2. สร้างตัวเลขสุ่มอิสระสองตัว $x$ และ $y$ กระจายอย่างสม่ำเสมอตั้งแต่ 1 ถึง $p-1$.
3. คำนวณ $g^{ax}$ และ $g^{โดย}$. โปรดทราบว่าพวกเขาเป็นอิสระจาก $g^a$ และ $g^b$.
4. คำนวณ $C_1(g, g^{ax}, g^{by})$. หากส่งคืนสัญลักษณ์พิเศษ ให้ส่งออก (น่าจะเป็น $\frac{1}{2^{k+1}}$). มิฉะนั้นจะมีการคำนวณ $g^{abxy}$. ไปที่ขั้นตอนที่ห้า
5. ใช้อัลกอริทึมแบบยุคลิดแบบขยายเพื่อค้นหา $z$, ดังนั้น $xyz \equiv 1 (\mod p-1)$.
6. คำนวณ $g^{abxyz} = g^{ab}$ และส่งออก (ความน่าจะเป็นของมันคือ $\frac{1}{2^{k+1}}$).

ไม่ยากที่จะดูว่าความน่าจะเป็นโดยรวมของการส่งออก $ก^{ab}$ เป็น $1 - \frac{1}{2^k}$ ตอนนี้.