Hardness of Computing
Individual Bits for One-way Functions on Elliptic Curves
Alexandre Duc (EPFL,
Dimitar Jetchev (EPFL,
Abstract:
We prove that if one can predict any of the bits of the input to an elliptic
curve based one-way function over a finite field, then we can invert the
function. In particular, our result implies that if one can predict any of
the bits of the input to a classical pairing-based one-way function with
non-negligible advantage over a random guess then one can efficiently invert
this function and thus, solve the Fixed Argument Pairing Inversion problem
(FAPI-1/FAPI-2). The latter sheds some light on the security of various
pairing-based schemes such as the identity-based encryption scheme of Boneh--Franklin, Hess' identity based signature scheme,
as well as Joux's three-party one-round key
agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in
polynomial time then one can solve the Computational Diffie--Hellman
problem (CDH) in polynomial time.
Our result implies that all the bits of the one-way functions defined above
are hard-to-compute. The argument is based on a list-decoding technique via
discrete Fourier transforms due to Akavia--Goldwasser--Safra as well as an
idea due to Boneh--Shparlinski.