London Algebra Colloquium abstract

Cryptanalysing the critical group

Simon Blackburn (Royal Holloway, University of London), 26th February 2009

Abstract

The critical group of a graph is defined in terms of a certain chip-firing game played on the vertices of the graph. Norman Biggs recently proposed the critical group of a class of graphs as a candidate for a class of groups whose discrete logarithm problem is hard. Such classes are interesting to cryptographers, as public key cryptosystems may be built from them. This talk will define the class that Biggs is interested in, and will show that the discrete log problem is in fact easy to solve.