## Cryptology ePrint Archive: Report 2014/685

Bits Security of the CDH Problems over Finite Fields

Mingqiang Wang and Tao Zhan and Haibin Zhang

Abstract: It is a long-standing open problem to prove the existence of (deterministic) hard-core predicates for the Diffie-Hellman problem over finite fields, without resorting to the generic approaches for any one-way functions (e.g., the Goldreich-Levin hard-core predicates). Fazio et al. (FGPS, Crypto '13) make important progress on this problem by defining a weaker Computational Diffie-Hellman (CDH) problem over $\mathbb{F}_{p^2}$, i.e., Partial-CDH problem, and proving the unpredictability of every single bit of one of the coordinates of the secret Diffie-Hellman value. However, the existence of specific hard-core predicates for the regular CDH problems defined over finite fields remains unproven. This paper closes this gap and resolves all the open problems left in FGPS:

1. We prove that the Partial-CDH problem over finite fields $\mathbb{F}_{p^2}$ is as hard as the regular CDH problem over the same fields. 2. We show a much stronger and more generalized result over finite fields $\mathbb{F}_{p^2}$---not only the regular CDH problem over $\mathbb{F}_{p^2}$ admits hard-core predicates but every individual bit of the CDH value is unpredictable. 3. We extend the Partial-CDH problem to define the $d$-th CDH problem over finite fields $\mathbb{F}_{p^t}$ for any polynomial $t>1$ and for any $0\leq d \leq t-1$. We show that computing any single coordinate of the CDH value over $\mathbb{F}_{p^t}$ is equivalent to computing the entire CDH value. 4. We prove that over finite fields $\mathbb{F}_{p^t}$ for any polynomial~$t>1$, each $d$-th CDH problem except $d \neq 0$ admits a large class of hard-core predicates, including every individual bit of the $d$-th coordinate. Hence almost all individual bits of the CDH value of the regular CDH problem over finite fields $\mathbb{F}_{p^t}$ for $t>1$ are hard-core.

Category / Keywords: foundations / CDH, Diffie-Hellman problem, $d$-th CDH problem, finite fields, hard-core bits, list decoding, multiplication code, Partial-CDH problem.