Paper 2014/685
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 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 the long-standing open problem over finite fields $\mathbb{F}_{p^t}$ for any constant $t>1$. In particular, we show that all the individual bits of the CDH problem over $\mathbb{F}_{p^2}$ and almost all the individual bits of the CDH problem over $\mathbb{F}_{p^t}$ for $t>2$ are hard-core.
Note: Theorem 1 and Theorem 9 are revised to work for a more general, probabilistic adversary. Previously they only work for an adversary that always returns correct answers.
Metadata
- Available format(s)
- 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)
- haibin @ cs unc edu
- History
- 2015-05-25: last of 2 revisions
- 2014-09-02: received
- See all versions
- Short URL
- https://ia.cr/2014/685
- License
-
CC BY