International Association
for Cryptologic Research

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.