**Bit Security of the CDH Problems over Finite Field**

*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 Computational Diffie-Hellman (CDH) 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 problem over $\mathbb{F}_{p^2}$, i.e., Partial-CDH problem, and proving, when allowing changing field representations, the unpredictability of every single bit of one of the coordinates of the secret Diffie-Hellman value.

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

**Date: **received 1 Sep 2014, last revised 24 May 2015

**Contact author: **haibin at cs unc edu

**Available format(s): **PDF | BibTeX Citation

**Note: **We thank EUROCRYPT PCs for pointing us the prior work on the hardness of $d$-th CDH problem by Verheul and by Shparlinski. We proved an essentially stronger result in the case of noisy oracles. In this version, we compare them in detail.

**Version: **20150525:015707 (All versions of this report)

**Short URL: **ia.cr/2014/685

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]