University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

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 JaoExport this event to calendar

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

Boneh-Boyen signatures and the Strong Diffie-Hellman problem

Speaker: Dan McQuillan
Affiliation: Norwich University
Room: 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
Canada

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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)