Discrete Logarithm on the Jacobian of Finite Graphs Export

@article{citeulike:5298089, abstract = {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.}, archivePrefix = {arXiv}, author = {Shokrieh, Farbod}, citeulike-article-id = {5298089}, citeulike-linkout-0 = {http://arxiv.org/abs/0907.4764}, citeulike-linkout-1 = {http://arxiv.org/pdf/0907.4764}, day = {27}, eprint = {0907.4764}, keywords = {crypto, discrete-laplacian, graph, sandpile}, month = {Jul}, posted-at = {2009-08-04 11:37:48}, priority = {2}, title = {Discrete Logarithm on the Jacobian of Finite Graphs}, url = {http://arxiv.org/abs/0907.4764}, year = {2009} }

TY - JOUR ID - citeulike:5298089 L3 - citeulike-article-id:5298089 N2 - 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. TI - Discrete Logarithm on the Jacobian of Finite Graphs KW - crypto KW - discrete-laplacian KW - graph KW - sandpile AU - Shokrieh, Farbod PY - 2009/Jul/27/ UR - http://arxiv.org/abs/0907.4764 ER -