Để cho $\mathbb G$ với máy phát điện $g$, đó là thứ tự nguyên tố 256-bit $q$và số nguyên tố 128 bit $p$ được biết và cố định.
Giả sử chúng ta có một thuật toán $\mathcal A$ mà trên đầu vào $(h_1,h_2)\in\mathbb G^2$, với $h_1=g^{a_1}$, $h_2=g^{a_2}$ cho ngẫu nhiên $a_1,a_2\in\mathbb Z_q$, đầu ra $h_3=g^{a_1+a_2\bmod p}$ với xác suất không biến mất, như trong câu hỏi.
Xác định thuật toán $\mathcal A'$ đó trên đầu vào $h\in\mathbb G$ nỗ lực để xuất $y$ với $g^y=h$, và hướng tới điều này:
- vẽ $u$ ngẫu nhiên trong $\mathbb Z_q$, tính toán $h_1=g^u\;h$, mà bây giờ là ngẫu nhiên trong $\mathbb G$; do đó có một duy nhất (như chưa biết, ngẫu nhiên) $a_1\in\mathbb Z_q$ với $g^{a_1}=h_1$
- vẽ $a_2$ ngẫu nhiên trong $\mathbb Z_q$, tính toán $h_2=g^{a_2}$
- chạy $\mathcal A$ với đầu vào $(h_1,h_2)$, được $h_3$ giả định là (với xác suất không biến mất) $g^{a_1+a_2\bmod p}$
- tìm thấy $x\in\mathbb Z_q$ với $0\le x<p<2^{128}$ như vậy mà $g^x=h_3$, yêu cầu theo thứ tự $2^{66}$ hoạt động nhóm bằng cách sử dụng Polard's rho với các điểm phân biệt, bộ nhớ ít khả thi và dễ dàng phân phối
- tính toán $r=x-a_2\bmod p$; nó giữ $a_1\equiv r\bmod p$, và $0\le a_1<q$; để cái (sd chưa biết) $s\in\left[0,\left\lfloor q/p\right\rfloor\right]$ được như vậy mà $a_1=r+s\,p$, do đó $g^{r+s\,p}=h_1$, do đó $g^{s\,p}=h_1\,g^{q-r}$, do đó $g^s=(h_1\,g^{q-r})^{p^{-1}\bmod q}$
- tính toán $h_4=(h_1\,g^{q-r})^{p^{-1}\bmod q}$; nó giữ $g^s=h_4$ và $s<2^{129}$
- tìm thấy $s$ bằng phương pháp cơ bản giống như $x$
- tính toán $a_1=r+s\,p$, do đó sao cho $g^{a_1}=h_1$
- tính toán và đầu ra $y=a_1-u\bmod q$, đó là như vậy mà $g^y=h$.
thuật toán của chúng tôi $\mathcal A'$ do đó có thể tính logarit rời rạc $y$ để căn cứ $g$ của bất kỳ yếu tố nhất định $h$ Trong $\mathbb G$ với xác suất không biến mất, và khả thi ít hoạt động. Điều này được cho là không thể. Do đó giả định của chúng tôi rằng $\mathcal A$ tồn tại là sai.
Do đó, chúng tôi trả lời câu hỏi trong tiêu cực.
