论文标题
一种启发式次指数算法，可在有限字段上找到Markoff图中的路径
A Heuristic Subexponential Algorithm to Find Paths in Markoff Graphs Over Finite Fields
论文作者
论文摘要
查尔斯，戈伦和劳特[J. Cryptology 22（1），2009年]解释了如何使用扩展器图构建哈希函数，在这些图形中很难在指定的顶点之间找到路径。经典Markoff方程的一组解决方案$ x^2+y^2+z^2 = xyz $在有限字段$ \ mathbb {f} _q $具有自然结构作为三方图的天然结构，该结构使用三个非强制性的多项式自动形态来连接点。这些图形猜想形成了一个扩展器家族，而Fuchs，Lauter，Litman和Tran [数学加密1（1），2022]建议在CGL构造中使用此Markoff图系列。在本说明中，我们表明，从理论和实践意义上讲，假设两个随机性假设，Markoff图中的路径问题在$ \ Mathbb {f} _Q $上都可以在次指定时间内解决，并且在$ Q-1 $中的困难和解决三个evceete logarith $ $ $ \ nmater的困难是无效的，并且在$ q-1 $中的困难中complience。
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 $X^2+Y^2+Z^2=XYZ$ in a finite field $\mathbb{F}_q$ 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 $\mathbb{F}_q$ 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 $\mathbb{F}_q^*$.
