Aug 19 – 23
Santa Barbara




Hardness of Computing Individual Bits for One-way Functions on Elliptic Curves


Alexandre Duc (EPFL, Switzerland)

Dimitar Jetchev (EPFL, Switzerland)


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.




Back to Conference Program