|
Friday, May 29, 2009 |
|
|
|
|
Boneh-Boyen signatures and the Strong Diffie-Hellman problem |
|
|
The Boneh-Boyen digital 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 work we show that,
with very few exceptions, the private key in the scheme can be recovered
in $O(p^{\frac{2}{5}+\varepsilon})$ time instead of the usual
$O(\sqrt{p})$ time required for a discrete log, given access to a
signature oracle. This improvement is achieved by proving that the
security of the Boneh-Boyen scheme is equivalent to the intractability
of the $q$-Strong Diffie-Hellman problem. We present implementation
results comparing the performance of our recovery algorithm to generic
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. |