The analogous hardness assumption on its search problem, called the computational Diffie-Hellman (CDH) assumption, asserts that...

Transcribed Image Text:

The analogous hardness assumption on its search problem, called the computational Diffie-Hellman (CDH) assumption, asserts that it is hard to find [ab] given [a] and [b]. Formally, the CDH assumption is as follows. Definition (CDHGGen assumption). For any PPT adversary B Adven, B en, B(A) = Pr[c] = [ab] (G, q, [1])← GGen(1) a, b← Za [c] B(G, q, [1], [a], [b])_ negl (X). Give a reduction showing that, if a PPT adversary ACDH can solve the CDH problem, then there exists a PPT ADDH that can solve the DDH problem. Analyse the success probability and running time. [1pt] (b) Give a reduction showing that, if a PPT adversary ADLOG can solve the DLOG problem, then there exists a PPT ACDH that can solve the CDH problem. Analyse the success probability and running time. [1pt] Activate Windows The analogous hardness assumption on its search problem, called the computational Diffie-Hellman (CDH) assumption, asserts that it is hard to find [ab] given [a] and [b]. Formally, the CDH assumption is as follows. Definition (CDHGGen assumption). For any PPT adversary B Adven, B en, B(A) = Pr[c] = [ab] (G, q, [1])← GGen(1) a, b← Za [c] B(G, q, [1], [a], [b])_ negl (X). Give a reduction showing that, if a PPT adversary ACDH can solve the CDH problem, then there exists a PPT ADDH that can solve the DDH problem. Analyse the success probability and running time. [1pt] (b) Give a reduction showing that, if a PPT adversary ADLOG can solve the DLOG problem, then there exists a PPT ACDH that can solve the CDH problem. Analyse the success probability and running time. [1pt] Activate Windows

Answer rating: 100% (QA)

a Reduction from CDH to DDH Let ACDH be a PPT adversary that can solve the CDH problem We can construct a PPT algorithm ADD that solves the DDH proble... View the full answer