IACR News item: 07 March 2013
Nelly Fazio, Rosario Gennaro, Irippuge Milinda Perera, William E. Wkeith III
ePrint ReportTo 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 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 $\\mathbb{F}{p^2}$ and prove that every bit (and every segment predicate) of one of the input coordinate for these functions is hard-core.
Additional news items may be found on the IACR news page.