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 $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 hold also for a larger class of predicates, called 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 partial one-way function over finite fields $F_{p^2}$ and prove that every bit (and every segment predicate) of one of the input coordinate for these functions is hard-core.
Category / Keywords: foundations / Hardcore Bits, Diffie-Hellman Problem, Finite Fields, Elliptic Curves Date: received 6 Mar 2013, last revised 9 Mar 2013 Contact author: iperera at gc cuny edu Available formats: PDF | BibTeX Citation Note: Added forgotten acknowledgments Version: 20130309:163229 (All versions of this report) Discussion forum: Show discussion | Start new discussion