The discrete logarithm problem in cokernels of ${\mathcal{O}}_K$-matrices

Abstract

In 2009 and 2010, Blackburn and Shokrieh independently found that the discrete logarithm can be computed efficiently on the sandpile group of a graph, meaning that sandpile groups are not secure for cryptography. We generalize this problem to cokernels of matrices with entries in the ring of integers ${\mathcal{O}}_K$ of a number field $K$. When $K$ has nontrivial class group, the failure of the Euclidean algorithm in ${\mathcal{O}}_K$ is an obstacle to generalizing previous methods. For $M$ in ${\mathrm{M}}_{n\times m}({\mathcal{O}}_K)$, we overcome this obstacle to efficiently compute discrete logarithms in $\mathrm{cok}(M)={\mathcal{O}}_K^n/M{\mathcal{O}}_K^m$. In particular, we find an algorithm with time complexity $\tilde{O}((m+n{)}^{\ddot{I}‰+1})$, where $\ddot{I}‰$ is an exponent of matrix multiplication, to compute discrete logarithms in $\mathrm{cok}(M)$ when $\mathrm{cok}(M)$ is viewed either as an ${\mathcal{O}}_K$-module or as a group. When $M$ is Hermitian with respect to a Galois involution $\ddot{I}ƒ$ and nonsingular, we improve the time complexity to $\tilde{O}(n^{\ddot{I}}‰)$.

7 pages