Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem

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;Combinatorics and Optimization

Yoshida, Kayo

University of Waterloo

关键词: 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;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4219/1/thesis_electronic.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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