The monodromy pairing and discrete logarithm on the Jacobian of finite graphs

Journal of mathematical cryptology

article

Farbod Shokrieh¹ 

[1] Georgia Institute of Technology

关键词: Discrete logarithm;    graphs;    Jacobian;    monodromy pairing;    generalized inverses;    critical group;    sandpiles;   

DOI  :  10.1515/jmc.2010.002

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

Every graph has a canonical finite abelian group attached to it. This group has appeared in the literature under a variety of names including the sandpile group, critical group, Jacobian group, and Picard group. The construction of this group closely mirrors the construction of the Jacobian variety of an algebraic curve. Motivated by this analogy, it was recently suggested by Norman Biggs that the critical group of a finite graph is a good candidate for doing discrete logarithm based cryptography. In this paper, we study a bilinear pairing on this group and show how to compute it. Then we use this pairing to find the discrete logarithm efficiently, thus showing that the associated cryptographic schemes are not secure. Our approach resembles the MOV attack on elliptic curves.

【 授权许可】

CC BY|CC BY-NC-ND