Xây dựng thuật toán bộ giải CDH

Giả sử $C_k: (g, g^a, g^b) \mapsto g^{ab}$ là trình giải quyết CDH của bạn, giải quyết nó với xác suất $1 - \frac{1}{2^k}$ và biểu tượng đặc biệt khác. Hãy xây dựng chúng từ $C_1$ đệ quy.

Xây dựng $C_{k+1}$:

1. Tính toán $C_k(g, g^a, g^b)$. Nếu nó trở lại $g^{ab}$, xuất nó (xác suất của điều này là $1 - \frac{1}{2^k}$). Nếu không, hãy chuyển sang bước thứ hai.
2. Tạo hai số ngẫu nhiên độc lập $x$ và $y$ phân bố đều từ 1 đến $p-1$.
3. Tính toán $g^{ax}$ và $g^{bởi}$. Lưu ý rằng chúng độc lập với $g^a$ và $g^b$.
4. Tính toán $C_1(g, g^{ax}, g^{by})$. Nếu nó trả về ký hiệu đặc biệt, hãy xuất nó ra (xác suất của nó là $\frac{1}{2^{k+1}}$). Nếu không nó đã tính toán $g^{abxy}$. Đi đến bước thứ năm.
5. Sử dụng thuật toán Euclide mở rộng để tìm $z$, như vậy mà $xyz \equiv 1 (\mod p-1)$.
6. Tính toán $g^{abxyz} = g^{ab}$ và xuất nó (xác suất của nó là $\frac{1}{2^{k+1}}$).

Không khó để thấy rằng tổng xác suất xuất ra $g^{ab}$ Là $1 - \frac{1}{2^k}$ hiện nay.