Cryptology ePrint Archive: Report 2008/170

Cryptanalysing the Critical Group: Efficiently Solving Biggs's Discrete Logarithm Problem

Simon R. Blackburn

Abstract: Biggs has recently proposed the critical group of a certain class of finite graphs as a platform group for cryptosystems relying on the difficulty of the discrete log problem. The paper uses techniques from the theory of Picard groups on finite graphs to show that the discrete log problem can be efficiently solved in Biggs's groups. Thus this class of groups is not suitable as a platform for discrete log based cryptography.

Category / Keywords: public-key cryptography /

Date: received 15 Apr 2008, last revised 7 Nov 2008

Contact author: s blackburn at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20081107:113055 (All versions of this report)

Short URL: ia.cr/2008/170

Discussion forum: Show discussion | Start new discussion