Paper 2011/329
Hardness of Computing Individual Bits for Oneway Functions on Elliptic Curves
Alexandre Duc and Dimitar Jetchev
Abstract
We prove that if one can predict any of the bits of the input to an elliptic curve based oneway 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 pairingbased oneway function with nonnegligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI1/FAPI2). The latter has implications on the security of various pairingbased schemes such as the identitybased encryption scheme of BonehFranklin, Hess’ identitybased signature scheme, as well as Joux’s threeparty oneround key agreement protocol. Moreover, if one can solve FAPI1 and FAPI2 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 hardtocompute assuming these functions are oneway. The argument is based on a listdecoding technique via discrete Fourier transforms due to Akavia–Goldwasser–Safra as well as an idea due to Boneh–Shparlinski.
Metadata
 Available format(s)
 PDF PS
 Publication info
 Published elsewhere. CRYPTO 2012 paper full version
 Keywords
 Oneway functionhardtocompute bitsbilinear pairingselliptic curvesfixed argument pairing inversion problemFourier transformlist decoding.
 Contact author(s)
 dimitar jetchev @ epfl ch
 History
 20120521: revised
 20110622: received
 See all versions
 Short URL
 https://ia.cr/2011/329
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/329, author = {Alexandre Duc and Dimitar Jetchev}, title = {Hardness of Computing Individual Bits for Oneway Functions on Elliptic Curves}, howpublished = {Cryptology ePrint Archive, Paper 2011/329}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/329}}, url = {https://eprint.iacr.org/2011/329} }