You are looking at a specific version 20150525:015707 of this paper. See the latest version.

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, when allowing changing field representations, the unpredictability of every single bit of one of the coordinates of the secret Diffie-Hellman value.

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
CDHDiffie-Hellman problem$d$-th CDH problemfinite fieldshard-core bitslist decodingmultiplication codenoisy oraclePartial-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
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.