2022/11/15 by Joseph H. Silverman, Silverman, Joseph H. · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #graph theory and CDMA systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2211.08511
Charles, Goren, and Lauter [J. Cryptology 22(1), 2009] explained how one can construct hash functions using expander graphs in which it is hard to find paths between specified vertices. The set of solutions to the classical Markoff equation X2+Y2+Z2=XYZ in a finite field \mathbbFq has a natural structure as a tri-partite graph using three non-commuting polynomial automorphisms to connect the points. These graphs conjecturally form an expander family, and Fuchs, Lauter, Litman, and Tran [Mathematical Cryptology 1(1), 2022] suggest using this family of Markoff graphs in the CGL construction. In this note we show that in both a theoretical and a practical sense, assuming two randomness hypotheses, the path problem in a Markoff graph over \mathbbFq can be solved in subexponential time, and is more-or-less equivalent in difficulty to factoring q-1 and solving three discrete logarithm problem in \mathbbFq^*.