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.
Category / Keywords: foundations / Hard-Core Bits, Diffie-Hellman Problem, Finite Fields, Elliptic Curves Original Publication (with major differences): IACR-CRYPTO-2013