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

DOI10.1515/JMC.2010.002zbMATH Open1231.05173arXiv0907.4764OpenAlexW3099502112MaRDI QIDQ3580731FDOQ3580731

Authors: Farbod Shokrieh 

Publication date: 13 August 2010

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0907.4764

Recommendations

• A combinatorial description of the monodromy of log curves
• Monodromy of a class of logarithmic connections on an elliptic curve
• A graph-theoretic approach to Jacobsthal polynomials
• Exponents of Jacobians of graphs and regular matroids
• Monodromy conjecture for log generic polynomials
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• The monodromy pairing for logarithmic 1-motifs
• Graphs and the Jacobian conjecture
• A Jacobian module for disentanglements and applications to Mond's conjecture
• scientific article; zbMATH DE number 1064800

zbMATH Keywords

graphsdiscrete logarithmJacobiancritical groupgeneralized inversessandpilesmonodromy pairing

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Jacobians, Prym varieties (14H40) Computational number theory (11Y99)

Cites Work

• Self-organized criticality
• Self-organized critical state of sandpile automaton models
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Critical groups for homeomorphism classes of graphs

Cited In (19)

• Divisors on graphs, binomial and monomial ideals, and cellular resolutions
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• A monodromy graph approach to the piecewise polynomiality of simple, monotone and Grothendieck dessins d'enfants double Hurwitz numbers
• On a Cohen-Lenstra heuristic for Jacobians of random graphs
• The distribution of sandpile groups of random graphs
• A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• The critical groups of Adinkras up to 2-rank of Cayley graphs
• The distribution of sandpile groups of random graphs with their pairings
• A note on Brill-Noether existence for graphs of low genus
• Critical groups of simplicial complexes
• Realization of groups with pairing as Jacobians of finite graphs
• The critical group from a cryptographic perspective
• The monodromy pairing for logarithmic 1-motifs
• Cryptanalysing the critical group: efficiently solving Biggs's discrete logarithm problem
• The sandpile group of a thick cycle graph
• Two-vertex generators of Jacobians of graphs
• Chip-firing games and critical groups
• Canonical measures on metric graphs and a Kazhdan's theorem

This page was built for publication: The monodromy pairing and discrete logarithm on the Jacobian of finite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580731)