Linear Algebra

Linear algebra over finite fields shows up in many cryptographic constructions (matrix-based schemes, codes, lattices, and any system that exponentiates a matrix). A few structural properties of matrices are useful when attacking such systems.

Tricks

Jordan blocks keep their structure under exponentiation
A matrix $M$ and any power $M^n$ share the same eigenvectors, so the eigen-structure of the base (including whether it is defective, i.e. has a repeated eigenvalue with too few eigenvectors) is preserved by exponentiation. This is what makes a Jordan block leak information when it is raised to a power:
$\begin{pmatrix}\lambda & 1\\\\ 0 & \lambda\end{pmatrix}^{n} = \begin{pmatrix}\lambda^{n} & n\,\lambda^{n-1}\\\\ 0 & \lambda^{n}\end{pmatrix}$
The ratio (off-diagonal / diagonal) of the result is exactly $n / \lambda$ , so the exponent $n$ is readable directly, even when no discrete logarithm is feasible. If a base is diagonalizable but has a repeated eigenvalue, you can also plant such a block by adding a rank-1 perturbation aligned to that eigenspace ( $M + P E P^{-1}$ where $P$ holds the eigenvectors and $E$ couples the repeated pair), using only the eigenvectors and not the eigenvalues.

Recovering a secret from a linear oracle

When an oracle returns a linear function of a secret vector $s$ (for example the dot product $\langle x, s \rangle$ of a known vector $x$ with the secret), each call gives one linear equation over the field. Collecting as many independent equations as the dimension $n$ of the secret makes the system invertible, and the secret is recovered with a single matrix solve. Random vectors are independent with overwhelming probability over a large field, so $n$ random queries are enough.

Stacking the query vectors $x_i$ as the rows of a matrix $Y$ and the results $b_i = \langle x_i, s \rangle$ as a vector $b$ , the secret is the solution of $Y s = b$ . This is the core of breaking the inner-product Functional Encryption scheme when the key oracle leaks both $x$ and $\langle x, s \rangle$ .

from sage.all import *

p = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551  # field order
F = GF(p)
n = 256                                              # length of the secret

s = vector(F, [F.random_element() for _ in range(n)])   # secret, unknown to us
def oracle(x):                                        # leaks x and the linear function <x, s>
    return x, x * s

rows, rhs = [], []
for _ in range(n):                                   # n independent queries
    x = vector(F, [randint(0, 1) for _ in range(n)]) # random (binary) query vector
    xi, bi = oracle(x)
    rows.append(xi)
    rhs.append(bi)

Y = matrix(F, rows)                                  # each row is a query vector x_i
b = vector(F, rhs)                                   # each entry is <x_i, s>
recovered = Y.solve_right(b)                         # solve Y * s = b
assert recovered == s

Functional Encryption