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

DOI10.1515/JMC.2010.002MaRDI QIDQ3580731zbMATH OpenOpenAlexFDO

Authors Farbod Shokrieh

Publication date 13 August 2010

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

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

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)

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.

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

Cites work

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

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
• A note on Brill-Noether existence for graphs of low genus
• The critical groups of Adinkras up to 2-rank of Cayley graphs
• The distribution of sandpile groups of random graphs with their pairings
• 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)