### Hardness of Computing Individual Bits for One-way 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 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 BonehFranklin, 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.

Available format(s)
Publication info
Published elsewhere. CRYPTO 2012 paper full version
Keywords
One-way functionhard-to-compute bitsbilinear pairingselliptic curvesfixed argument pairing inversion problemFourier transformlist decoding.
Contact author(s)
dimitar jetchev @ epfl ch
History
2012-05-21: revised
See all versions
Short URL
https://ia.cr/2011/329

CC BY

BibTeX

@misc{cryptoeprint:2011/329,
author = {Alexandre Duc and Dimitar Jetchev},
title = {Hardness of Computing Individual Bits for One-way 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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.