Boneh-Boyen signatures and the Strong Diffie-Hellman problem

David Jao and 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.

Note: Added corrections and acknowledgments.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of Pairing 2009 paper. Contains detailed tables and graphs of experimental results.
Contact author(s)
djao @ math uwaterloo ca
History
2009-05-31: last of 2 revisions
See all versions
Short URL
https://ia.cr/2009/221

CC BY

BibTeX

@misc{cryptoeprint:2009/221,
author = {David Jao and Kayo Yoshida},
title = {Boneh-Boyen signatures and the Strong Diffie-Hellman problem},
howpublished = {Cryptology ePrint Archive, Paper 2009/221},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/221}},
url = {https://eprint.iacr.org/2009/221}
}

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