## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

# Tutte seminar - David Jao

Friday, May 29, 2009 — 3:30 PM to 4:30 PM EDT

## Boneh-Boyen signatures and the Strong Diffie-Hellman problem

Speaker: Dan McQuillan Norwich University Mathematics & Computer Building (MC) 5158

### 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.

Location
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1

### September 2020

S M T W T F S
30
31
1
2
3
5
6
8
9
10
12
13
15
16
19
20
22
23
26
27
29
30
1
2
3
1. 2020 (92)
1. November (1)
2. October (1)
3. September (12)
4. August (11)
5. July (17)
6. June (11)
7. May (6)
8. March (11)
9. February (11)
10. January (11)
2. 2019 (167)
1. December (5)
2. November (15)
3. October (18)
4. September (15)
5. August (9)
6. July (17)
7. June (18)
8. May (16)
9. April (9)
10. March (24)
11. February (13)
12. January (8)
3. 2018 (138)
4. 2017 (103)
5. 2016 (137)
6. 2015 (136)
7. 2014 (88)
8. 2013 (48)
9. 2012 (39)
10. 2011 (36)
11. 2010 (40)
12. 2009 (40)
13. 2008 (39)
14. 2007 (15)