Hard-Core Predicates for a Diffie-Hellman Problem over Finite Fields

Nelly Fazio; Rosario Gennaro; Irippuge Milinda Perera; William E.  Skeith III

Paper 2013/134

Hard-Core Predicates for a Diffie-Hellman Problem over Finite Fields

Nelly Fazio, Rosario Gennaro, Irippuge Milinda Perera, and William E. Skeith III

Abstract

A long-standing open problem in cryptography is proving the existence of (deterministic) hard-core predicates for the Diffie-Hellman problem defined over finite fields. In this paper, we make progress on this problem by defining a very natural variation of the Diffie-Hellman problem over $\mathbb{F}_{p^2}$ and proving the unpredictability of every single bit of one of the coordinates of the secret DH value. To achieve our result, we modify an idea presented at CRYPTO'01 by Boneh and Shparlinski [4] originally developed to prove that the LSB of the elliptic curve Diffie-Hellman problem is hard. We extend this idea in two novel ways: 1. We generalize it to the case of finite fields $\mathbb{F}_{p^2}$; 2. We prove that any bit, not just the LSB, is hard using the list decoding techniques of Akavia et al. [1] (FOCS'03) as generalized at CRYPTO'12 by Duc and Jetchev [6]. In the process, we prove several other interesting results: - Our result also hold for a larger class of predicates, called \emph{segment predicates} in [1]; - We extend the result of Boneh and Shparlinski to prove that every bit (and every segment predicate) of the elliptic curve Diffie-Hellman problem is hard-core; - We define the notion of \emph{partial one-way function} over finite fields $\mathbb{F}_{p^2}$ and prove that every bit (and every segment predicate) of one of the input coordinates for these functions is hard-core.

Note: Added forgotten acknowledgments

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in CRYPTO 2013
DOI: 10.1007/978-3-642-40084-1_9
Keywords: Hard-Core Bits Diffie-Hellman Problem Finite Fields Elliptic Curves
Contact author(s): iperera @ gc cuny edu
History: 2013-08-24: last of 11 revisions; 2013-03-07: received; See all versions
Short URL: https://ia.cr/2013/134
License: CC BY

BibTeX

@misc{cryptoeprint:2013/134,
      author = {Nelly Fazio and Rosario Gennaro and Irippuge Milinda Perera and William E.  Skeith III},
      title = {Hard-Core Predicates for a Diffie-Hellman Problem over Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2013/134},
      year = {2013},
      doi = {10.1007/978-3-642-40084-1_9},
      note = {\url{https://eprint.iacr.org/2013/134}},
      url = {https://eprint.iacr.org/2013/134}
}