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)^{ω+1})$, where $ω$ 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 $σ$ and nonsingular, we improve the time complexity to $\tilde{O}(n^ω)$.

Disclosure

“n an earlier draft, we used methods similar to Section 3 to solve Problem 1.3 in the torsion submodule of cok(M ), where M is a (possibly singular) Hermitian matrix in Mn (O), in Õ(nω+1 ) operations. When prompted with that earlier draft, ChatGPT 5.4 Pro generalized this result to rectangular matrices and simplified its proof, which has become Theorem 1.5. So, the main proof idea in Section 2 comes from ChatGPT. We have independently verified all results in this paper. We briefl”

PDF page 3

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-24T00:28:51.963Z

Structural counts