Chứng minh một biến thể của CDH là khó

để cho $(\mathbb{G},q,p)$ là một nhóm $\mathbb{G}$ với thứ tự chính $q$ và máy phát điện $g$. Giả sử rằng CDH khó so với thiết lập này (Cụ thể là, đã cho $(g,g^a,g^b)$, thật khó để tìm thấy $g^{ab}$).

Bây giờ hãy xem xét những điều sau: đối với một đối thủ theo thời gian đa thức xác suất $\mathcal{A}$, và đưa ra $(\mathbb{G},q,p)$, chọn ngẫu nhiên $a,b,c\in \mathbb{Z}_q$ và chạy $\mathcal{A}(g,g^a,g^b,g^c)$. $\mathcal{A}$ thành công nếu nó xuất ra bất kỳ $g^{ab}, g^{ac}, g^{bc}$.

Tôi để cho thấy điều này cũng là khó khăn. Cách tiếp cận hơi rõ ràng sẽ là giảm ba đầu ra có thể dẫn đến thành công cho CDH, ví dụ: $g^{bc}$ chính xác là CDH nếu đầu vào là $(g,g^b,g^c)$. Tuy nhiên, trong trường hợp này, chúng tôi cũng được cung cấp $g^a$ vì vậy đây không phải là mô phỏng của CDH. Tôi cũng đã thử các cách tiếp cận khác, cố gắng chọn $c$ như vậy mà tôi có thể phục hồi $g^{ab}$ với xác suất cao trong mọi trường hợp. Tôi đã nhìn $g^c=g^{a+b}$ nhưng sau đó tôi không chắc chắn làm thế nào để có được $g^{ab}$ từ $g^{a^2+ab}$.

Mọi trợ giúp đều được đánh giá cao, đây không phải là bài tập về nhà.