Paper 2013/134
HardCore Predicates for a DiffieHellman Problem over Finite Fields
Nelly Fazio, Rosario Gennaro, Irippuge Milinda Perera, and William E. Skeith III
Abstract
A longstanding open problem in cryptography is proving the existence of (deterministic) hardcore predicates for the DiffieHellman problem defined over finite fields. In this paper, we make progress on this problem by defining a very natural variation of the DiffieHellman 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 DiffieHellman 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 DiffieHellman problem is hardcore;  We define the notion of \emph{partial oneway 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 hardcore.
Note: Added forgotten acknowledgments
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2013
 DOI
 10.1007/9783642400841_9
 Keywords
 HardCore BitsDiffieHellman ProblemFinite FieldsElliptic Curves
 Contact author(s)
 iperera @ gc cuny edu
 History
 20130824: last of 11 revisions
 20130307: 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 = {HardCore Predicates for a DiffieHellman Problem over Finite Fields}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/134}, year = {2013}, doi = {10.1007/9783642400841_9}, url = {https://eprint.iacr.org/2013/134} }