Paper 2014/685
Bit Security of the CDH Problems over Finite Field
Mingqiang Wang, 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
-
CC BY
BibTeX
@misc{cryptoeprint:2014/685,
author = {Mingqiang Wang and Tao Zhan and Haibin Zhang},
title = {Bit Security of the {CDH} Problems over Finite Field},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/685},
year = {2014},
url = {https://eprint.iacr.org/2014/685}
}
