You are looking at a specific version 20140902:073559 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
CDHDiffie-Hellman problem$d$-th CDH problemfinite fieldshard-core bitslist decodingmultiplication codePartial-CDH problem.
Contact author(s)
hbzhang @ ucdavis edu
History
2015-05-25: last of 2 revisions
2014-09-02: received
See all versions
Short URL
https://ia.cr/2014/685
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.