Welcome to the resource topic for 2009/221
Title:
Boneh-Boyen signatures and the Strong Diffie-Hellman problem
Authors: David Jao, Kayo Yoshida
Abstract:The Boneh-Boyen signature scheme is a pairing based short signature scheme which is provably secure in the standard model under the q-Strong Diffie-Hellman assumption. In this paper, we prove the converse of this statement, and show that forging Boneh-Boyen signatures is actually equivalent to solving the q-Strong Diffie-Hellman problem. Using this equivalence, we exhibit an algorithm which, on the vast majority of pairing-friendly curves, recovers Boneh-Boyen private keys in O(p^{\frac{2}{5}+\varepsilon}) time, using O(p^{\frac{1}{5}+\varepsilon}) signature queries. We present implementation results comparing the performance of our algorithm and traditional discrete logarithm algorithms such as Pollard’s lambda algorithm and Pollard’s rho algorithm. We also discuss some possible countermeasures and strategies for mitigating the impact of these findings.
ePrint: https://eprint.iacr.org/2009/221
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .