\input zb-basic
\input zb-ioport
\iteman{io-port 06086111}
\itemau{Duc, Alexandre; Jetchev, Dimitar}
\itemti{Hardness of computing individual bits for one-way functions on elliptic curves.}
\itemso{Safavi-Naini, Reihaneh (ed.) et al., Advances in cryptology -- CRYPTO 2012. 32nd annual cryptology conference, Santa Barbara, CA, USA, August 19--23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32008-8/pbk). Lecture Notes in Computer Science 7417, 832-849 (2012).}
\itemab
Summary: 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 has implications 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 functions defined above are hard-to-compute assuming these functions are one-way. 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.
\itemrv{~}
\itemcc{}
\itemut{one-way function; hard-to-compute bits; bilinear pairings; elliptic curves; fixed argument pairing inversion problem; Fourier transform; list decoding}
\itemli{doi:10.1007/978-3-642-32009-5\_48}
\end