9
$\begingroup$

Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.

Suppose we are given $p$, $A$, $x$, and $y$. The goal is to find a $k$ that satisfies $A^k x = y$. Is there an efficient algorithm that solves this problem? You can assume you are promised that at least one solution exists, if you want.

More generally, what is the complexity of this problem? How does its hardness relate to the hardness of the standard discrete log problem modulo $p$? I'm pretty sure the answer will depend upon the matrix $A$. Can we classify for which matrices $A$ this is as hard as the standard discrete log problem, for which it is harder, for which it is easier, for which it can be solved in polynomial time?

$\endgroup$
1
  • 1
    $\begingroup$ If you could solve that problem for any matrix A, you could solve the DL mod p problem; and also that other problem of yours, I think. $\endgroup$
    – fgrieu
    Commented Sep 20, 2012 at 6:04

1 Answer 1

8
$\begingroup$

The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$). In this question we are given less information, but similar techniques should still apply.

Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix. Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form. This means that $A$ can be expressed as a concatenation of Jordan blocks: $$A = \begin{pmatrix} J_1 \\&\ddots\\ &&J_n\end{pmatrix}.$$

Each Jordan block gives us an independent system of equations, so let me look at a single Jordan block at a time. We can break this down into cases, based upon the size of the Jordan block $J$:

  1. A size-1 Jordan block. Suppose $J$ is a $1\times 1$ Jordan block, i.e., $$J=\begin{pmatrix} \lambda \end{pmatrix}.$$ Then it is easy to see that the problem is exactly as hard as the discrete log to base $\lambda$ (unless $x=0$ in this component, in which case it is unsolvable for information-theoretic reasons).

  2. A size-2 Jordan block. Suppose $J$ is a $2\times 2$ Jordan block, i.e., $$J = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$ where $\lambda \ne 0$. A simple induction shows that $$J^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$ Let $P^{-1}x=(x_1, x_2)$ and $P^{-1}y=(y_1, y_2)$. Then we obtain the linear equations \begin{align*} \lambda^k x_1 + k\lambda^{k-1} x_2 &= y_1\\ \lambda^k x_2 &= y_2 \end{align*} which has the solution $$k = \lambda (y_1 - x_1 y_2/x_2)/y_2.$$ We see that as long as $x_2 \ne 0$, the problem is easy and we can solve for $k$ with a little bit of arithmetic (no discrete log needed). If $x_2=0$, I'd conjecture that this case is hard.

  3. A larger Jordan block. If we have a larger Jordan block, say $m \times m$, basically the same thing happens. The top row of $J^k$ is $(\lambda^k, k \lambda^{k-1}, {k \choose 2} \lambda^{k-2}, \dots)$, and each subsequent row is a right-shift of the one before it. Then, as long as $(x_2,x_3,\dots,x_m) \ne (0,0,\dots,0)$, we can solve for $k$ easily as in the $2\times 2$ case.

So, each Jordan block gives us a chance to solve for $k$. If any of the Jordan blocks are easy, we learn $k$. If all of the Jordan blocks are hard, learning $k$ is hard.

In summary: If the Jordan normal form of $A$ is diagonal, and at least one of the diagonal elements is such that discrete log to that base is hard, then this problem is as hard as the discrete log. On the other hand, if the Jordan normal form is not diagonal---i.e., if it has at least one Jordan block of size $>1$---then the problem is easy (except in corner cases where the wrong components of $x$ happens to be zero).

$\endgroup$
4
  • $\begingroup$ Note that "easy" recovery only gives $k \mod p$. For a full-size $k$, no easy solution it seems. Even worse, JNF does not always exist over GF(p), we may need to consider a field extension and do discrete log there. $\endgroup$
    – Fractalice
    Commented Jul 21, 2021 at 6:49
  • $\begingroup$ @Fractalice, oh gosh. Sounds like my answer is completely wrong, then. Thank you so much for explaining that to me. Would you recommend that I delete this answer? Might you be able to provide an answer? $\endgroup$
    – D.W.
    Commented Jul 21, 2021 at 20:51
  • $\begingroup$ @D.W. No, I would just suggest to add that the JNF may require considering the matrix over the extension field $GF(p^k)$ (where all the eigenvalues exist). Each eigenvalue can be considered separately (leading to a discrete log instance in the field where the eigenvalue lives). And that the "easy" trick only reveals the solution mod p (besides the discrete log part). I think as long as length of each Jordan block is at most p, this is actually complete, i.e. we can recover full discrete log in this way. $\endgroup$
    – Fractalice
    Commented Jul 22, 2021 at 11:34
  • $\begingroup$ Could there still be some advantages in utilizing discrete logs of matrices as a crypto primitive versus standard or elliptic curve discrete logs? In particular, could we use a smaller field while maintaining similar difficulty as the standard discrete log of a larger field? I suspect the answer is “No” as computing the Jordan form is “trivial” in comparison to the log, but perhaps someone has already analyzed this problem in depth. $\endgroup$ Commented Sep 15, 2023 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.