Abstract
dc:description.abstractThe Boneh-Boyen signature scheme is a short signature scheme which is provably secure in the standard model under the q-Strong Diffie-Hellman (SDH) assumption. The primary objective of this thesis is to examine the relationship between the Boneh-Boyen signature scheme and SDH. The secondary objective is to survey surrounding topics such as the generic group model, related signature schemes, intractability assumptions, and the relationship to identity-based encryption (IBE) schemes. Along these lines, we analyze the plausibility of the SDH assumption using the generic bilinear group model. We present the security proofs for the Boneh-Boyen signature scheme, with the addition of a small improvement in one of the probability bounds. Our main contribution is to give the reduction in the reverse direction; that is, to show that if the SDH problem can be solved then the Boneh-Boyen signature scheme can be forged. This contribution represents the first known proof of equivalence between the SDH problem and Boneh-Boyen signatures. We also discuss the algorithm of Cheon for solving the SDH problem. We analyze the implications of Cheon's algorithm for the security of the Boneh-Boyen signature scheme, accompanied by a brief discussion on how to counter the attack.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Yoshida, Kayo
Subjects
dc:subject × 23- cryptography
- digital signatures
- signature scheme
- Diffie-Hellman
- Strong Diffie-Hellman
- SDH
- Boneh-Boyen signatures
- Pollard rho
- Pollard lambda
- baby-step giant-step
- assumptions
- short signatures
- random oracle
- generic group
- BLS
- Waters
- Okamoto
- identity-based encryption
- IBE
- Cheon's algorithm
- partial fraction
- security
- existential forgery
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/4219