Tutte seminar - David Jao

Boneh-Boyen signatures and the Strong Diffie-Hellman problem

Abstract:

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. 

Joint work with Kayo Yoshida.