Bit security of the CDH problems over finite fields

Mingqiang Wang; Tao Zhan; Haibin Zhang

doi:10.1007/978-3-319-31301-6_25

Bit security of the CDH problems over finite fields

Mingqiang Wang
, Tao Zhan
, Haibin Zhang^*

^*Corresponding author for this work

Shandong University
University of North Carolina at Chapel Hill

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

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) made important progress on this problem by defining a weaker Computational Diffie- Hellman problem over F_p2, 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. In this paper, we show that all the individual bits of the CDH problem over F_p2 and almost all the individual bits of the CDH problem over F_pt for t > 2 are hard-core.

Original language	English
Title of host publication	Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers
Editors	Liam Keliher, Orr Dunkelman
Publisher	Springer Verlag
Pages	441-461
Number of pages	21
ISBN (Print)	9783319313009
DOIs	https://doi.org/10.1007/978-3-319-31301-6_25
Publication status	Published - 2016
Externally published	Yes
Event	22nd International Conference on Selected Areas in Cryptography, SAC 2015 - Sackville, Canada Duration: 12 Aug 2015 → 14 Aug 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9566
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Conference on Selected Areas in Cryptography, SAC 2015
Country/Territory	Canada
City	Sackville
Period	12/08/15 → 14/08/15

Keywords

CDH
D-th CDH problem
Diffie-Hellman problem
Finite fields
Hard-core bits
List decoding
Multiplication code
Noisy oracle
Partial-CDH problem

Access to Document

10.1007/978-3-319-31301-6_25

Cite this

Wang, M., Zhan, T., & Zhang, H. (2016). Bit security of the CDH problems over finite fields. In L. Keliher, & O. Dunkelman (Eds.), Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers (pp. 441-461). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9566). Springer Verlag. https://doi.org/10.1007/978-3-319-31301-6_25

Wang, Mingqiang ; Zhan, Tao ; Zhang, Haibin. / Bit security of the CDH problems over finite fields. Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers. editor / Liam Keliher ; Orr Dunkelman. Springer Verlag, 2016. pp. 441-461 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{97ceb4df91f740ff82837d17eb7bd5a3,

title = "Bit security of the CDH problems over finite fields",

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 {\textquoteright}13) made important progress on this problem by defining a weaker Computational Diffie- Hellman problem over Fp2, 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. In this paper, we show that all the individual bits of the CDH problem over Fp2 and almost all the individual bits of the CDH problem over Fpt for t > 2 are hard-core.",

keywords = "CDH, D-th CDH problem, Diffie-Hellman problem, Finite fields, Hard-core bits, List decoding, Multiplication code, Noisy oracle, Partial-CDH problem",

author = "Mingqiang Wang and Tao Zhan and Haibin Zhang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 22nd International Conference on Selected Areas in Cryptography, SAC 2015 ; Conference date: 12-08-2015 Through 14-08-2015",

year = "2016",

doi = "10.1007/978-3-319-31301-6\_25",

language = "English",

isbn = "9783319313009",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "441--461",

editor = "Liam Keliher and Orr Dunkelman",

booktitle = "Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers",

address = "Germany",

}

Wang, M, Zhan, T & Zhang, H 2016, Bit security of the CDH problems over finite fields. in L Keliher & O Dunkelman (eds), Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9566, Springer Verlag, pp. 441-461, 22nd International Conference on Selected Areas in Cryptography, SAC 2015, Sackville, Canada, 12/08/15. https://doi.org/10.1007/978-3-319-31301-6_25

Bit security of the CDH problems over finite fields. / Wang, Mingqiang; Zhan, Tao; Zhang, Haibin.
Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers. ed. / Liam Keliher; Orr Dunkelman. Springer Verlag, 2016. p. 441-461 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9566).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Bit security of the CDH problems over finite fields

AU - Wang, Mingqiang

AU - Zhan, Tao

AU - Zhang, Haibin

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - 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) made important progress on this problem by defining a weaker Computational Diffie- Hellman problem over Fp2, 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. In this paper, we show that all the individual bits of the CDH problem over Fp2 and almost all the individual bits of the CDH problem over Fpt for t > 2 are hard-core.

AB - 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) made important progress on this problem by defining a weaker Computational Diffie- Hellman problem over Fp2, 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. In this paper, we show that all the individual bits of the CDH problem over Fp2 and almost all the individual bits of the CDH problem over Fpt for t > 2 are hard-core.

KW - CDH

KW - D-th CDH problem

KW - Diffie-Hellman problem

KW - Finite fields

KW - Hard-core bits

KW - List decoding

KW - Multiplication code

KW - Noisy oracle

KW - Partial-CDH problem

UR - https://www.scopus.com/pages/publications/84961680255

U2 - 10.1007/978-3-319-31301-6_25

DO - 10.1007/978-3-319-31301-6_25

M3 - Conference contribution

AN - SCOPUS:84961680255

SN - 9783319313009

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 441

EP - 461

BT - Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers

A2 - Keliher, Liam

A2 - Dunkelman, Orr

PB - Springer Verlag

T2 - 22nd International Conference on Selected Areas in Cryptography, SAC 2015

Y2 - 12 August 2015 through 14 August 2015

ER -

Wang M, Zhan T, Zhang H. Bit security of the CDH problems over finite fields. In Keliher L, Dunkelman O, editors, Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers. Springer Verlag. 2016. p. 441-461. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-31301-6_25

Bit security of the CDH problems over finite fields

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this