Matrix Inversion and Homomorphic Verification

Linear algebra gives us a direct way to solve a system of equations. Exponentiation gives us a way to carry its additive relationships into a multiplicative group. Together, they make a useful worked example of homomorphic verification.

We will solve the system, calculate its exponentiated values, and check the resulting equations. We will also examine the original exercise's request to demonstrate knowledge of the solution while keeping the variables private. In this example, the public equations themselves reveal the unique solution, which limits that privacy goal from the outset.

1. Write the system as a matrix equation

Start with

\begin{aligned} 2x + 8y &= 7944, \\ 5x + 3y &= 4764. \end{aligned}

Define the coefficient matrix, the unknown vector, and the right-hand-side vector:

A = \begin{bmatrix} 2 & 8 \\ 5 & 3 \end{bmatrix}, \qquad \mathbf{v} = \begin{bmatrix}x \\ y\end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix}7944 \\ 4764\end{bmatrix}.

The system becomes

A\mathbf{v} = \mathbf{b},

or, explicitly,

\begin{bmatrix} 2 & 8 \\ 5 & 3 \end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix} = \begin{bmatrix}7944 \\ 4764\end{bmatrix}.

We first solve this equation using ordinary rational arithmetic. Modular arithmetic enters later, when we exponentiate the solution.

2. Compute the inverse

For a two-by-two matrix, the inverse formula is

\begin{bmatrix}a & b \\ c & d\end{bmatrix}^{-1} = \frac{1}{ad-bc} \begin{bmatrix}d & -b \\ -c & a\end{bmatrix}, \qquad ad-bc \ne 0.

For our matrix,

\det(A) = 2\cdot 3 - 8\cdot 5 = 6-40 = -34.

The determinant is nonzero, so the inverse exists over the rationals:

\begin{aligned} A^{-1} &= \frac{1}{-34} \begin{bmatrix} 3 & -8 \\ -5 & 2 \end{bmatrix} \\ &= \begin{bmatrix} -\frac{3}{34} & \frac{8}{34} \\ \frac{5}{34} & -\frac{2}{34} \end{bmatrix}. \end{aligned}

Multiplying the original equation on the left by this inverse gives

\mathbf{v} = A^{-1}\mathbf{b}.

3. Calculate and verify the solution

The first row of the inverse gives

\begin{aligned} x &= -\frac{3}{34}\cdot 7944 + \frac{8}{34}\cdot 4764 \\ &= \frac{-23832 + 38112}{34} \\ &= \frac{14280}{34} \\ &= 420. \end{aligned}

The second row gives

\begin{aligned} y &= \frac{5}{34}\cdot 7944 - \frac{2}{34}\cdot 4764 \\ &= \frac{39720 - 9528}{34} \\ &= \frac{30192}{34} \\ &= 888. \end{aligned}

Therefore,

\boxed{ \mathbf{v} = \begin{bmatrix}420 \\ 888\end{bmatrix}. }

Substituting into both original equations confirms the result:

\begin{aligned} 2\cdot 420 + 8\cdot 888 &= 840 + 7104 = 7944, \\ 5\cdot 420 + 3\cdot 888 &= 2100 + 2664 = 4764. \end{aligned}

4. Move the equations into the exponent

Use the example parameters

g = 5, \qquad n = 2147483629.

Here $n$ is prime and $g$ is a nonzero residue modulo $n$ . Define the two transmitted values as

X = g^x \bmod n, \qquad Y = g^y \bmod n.

The uppercase names distinguish the encoded values from the exponents $x$ and $y$ .

The relevant homomorphism is exponentiation:

\begin{aligned} \phi(a) &= g^a \bmod n, \\ \phi(a+b) &\equiv \phi(a)\phi(b) \pmod n, \\ \phi(ka) &\equiv \phi(a)^k \pmod n. \end{aligned}

Thus addition in the exponent becomes multiplication of group elements, while multiplying an exponent by an integer becomes raising its encoding to that power.

Applied to the first equation,

\begin{aligned} X^2Y^8 &\equiv (g^x)^2(g^y)^8 \pmod n \\ &\equiv g^{2x+8y} \pmod n \\ &\equiv g^{7944} \pmod n. \end{aligned}

Applied to the second equation,

\begin{aligned} X^5Y^3 &\equiv (g^x)^5(g^y)^3 \pmod n \\ &\equiv g^{5x+3y} \pmod n \\ &\equiv g^{4764} \pmod n. \end{aligned}

These are the two homomorphic checks from the original exercise.

5. Evaluate the checks numerically

For the solution we found,

\begin{aligned} X &= 5^{420} \bmod 2147483629 = 1208230776, \\ Y &= 5^{888} \bmod 2147483629 = 122735854. \end{aligned}

The verifier receives $X$ and $Y$ and computes both sides of each check:

\begin{aligned} X^2Y^8 \bmod n &= 1634636351, \\ g^{7944} \bmod n &= 1634636351, \\ X^5Y^3 \bmod n &= 124876100, \\ g^{4764} \bmod n &= 124876100. \end{aligned}

Both comparisons succeed. The encoded values satisfy the exponentiated relations.

6. Distinguish the modulus from the exponent order

There are two different moduli to keep track of. Group elements are represented modulo $n$ . Exponents repeat modulo the order of $g$ .

Let

m = \operatorname{ord}_n(g),

the smallest positive integer for which

g^m \equiv 1 \pmod n.

For the supplied parameters, exact computation gives

\begin{aligned} n-1 &= 2^2\cdot 3^2\cdot 59652323, \\ m &= 1073741814 \\ &= 2\cdot 3^2\cdot 59652323. \end{aligned}

Consequently,

g^a \equiv g^b \pmod n \quad\Longleftrightarrow\quad a \equiv b \pmod m.

For values $X=g^x$ and $Y=g^y$ , the verifier's checks therefore establish the congruences

\begin{aligned} 2x+8y &\equiv 7944 \pmod m, \\ 5x+3y &\equiv 4764 \pmod m. \end{aligned}

An integer solution satisfies these congruences. The reverse implication needs additional restrictions to rule out wraparound.

For example, take

x' = 420+m = 1073742234, \qquad y' = 888.

Then

g^{x'} \equiv g^{420} \pmod n,

so the transmitted values and both homomorphic checks are unchanged. But the integer sums have increased by $2m$ and $5m$ , respectively. These new integers fail the original equalities.

There is a related matrix distinction: the inverse computed earlier used division by $-34$ over the rationals. That division is unavailable modulo $m$ because

\gcd(34,m) = 2.

The determinant has no multiplicative inverse modulo the exponent order, so the rational matrix inverse cannot be reused as a modular inverse in this example.

7. Assess the privacy and knowledge claims

The public system already determines the variables

Anyone who knows $A$ and $\mathbf{b}$ can compute

\mathbf{v} = A^{-1}\mathbf{b} = \begin{bmatrix}420 \\ 888\end{bmatrix}.

Sending only $X$ and $Y$ avoids placing the variables directly in those two messages. The public equations still disclose them through a short calculation. Increasing the size of $n$ would leave that calculation unchanged.

Zero knowledge concerns information disclosed by a proof beyond what the public statement already reveals. This statement already makes recovering the intended integer solution easy, so it provides no meaningful secrecy for that solution.

Algebraic consistency does not establish a knowledge protocol

The two static comparisons check relationships between supplied group elements. The exercise supplies no additional mechanism demonstrating the sender's possession of the corresponding exponents. A valid pair of encoded values can also be copied and submitted again.

For a comparison with an actual knowledge protocol, RFC 8235, Section 2.2 describes Schnorr's three-pass construction: a fresh randomized group element, a verifier challenge, and a response involving the secret exponent. Its verification checks both group membership and the response equation. This is a separate protocol layer that would require an appropriate group and a precisely defined statement.

The example's approximately 31-bit modulus and small candidate exponents also make it unsuitable for protecting secrets. A guessed exponent can be checked simply by exponentiating it. The numbers here serve as arithmetic demonstration parameters.

If the intended goal is a private witness, first choose a public statement that leaves that witness hard to recover. Then use a suitable proof system to establish knowledge and the desired relation, with explicit treatment of the exponent domain and any integer bounds.

8. Reproduce the arithmetic in Python

This example uses only Python's standard library. Fraction keeps the matrix solution exact, and the three-argument form of pow performs modular exponentiation directly.

from fractions import Fraction
from math import gcd, isqrt


def is_prime(value):
    if value < 2:
        return False
    return all(value % d != 0 for d in range(2, isqrt(value) + 1))


# Solve the original system using exact rational arithmetic.
det = 2 * 3 - 8 * 5
assert det == -34

x = Fraction(3 * 7944 - 8 * 4764, det)
y = Fraction(-5 * 7944 + 2 * 4764, det)
assert (x, y) == (420, 888)
assert x.denominator == y.denominator == 1
x, y = int(x), int(y)

assert 2 * x + 8 * y == 7944
assert 5 * x + 3 * y == 4764

# Parameters from the source document, used for demonstration.
g = 5
n = 2147483629
m = 1073741814

assert is_prime(n)
assert is_prime(59652323)
assert n - 1 == 4 * 9 * 59652323
assert m == 2 * 9 * 59652323

# These checks certify that g has order exactly m.
assert pow(g, m, n) == 1
for prime_factor in (2, 3, 59652323):
    assert pow(g, m // prime_factor, n) != 1
assert gcd(34, m) == 2

X = pow(g, x, n)
Y = pow(g, y, n)
assert (X, Y) == (1208230776, 122735854)

left_1 = pow(X, 2, n) * pow(Y, 8, n) % n
right_1 = pow(g, 7944, n)
left_2 = pow(X, 5, n) * pow(Y, 3, n) % n
right_2 = pow(g, 4764, n)

assert left_1 == right_1 == 1634636351
assert left_2 == right_2 == 124876100

# Passing the modular checks does not force integer equality.
x_wrapped = x + m
assert pow(g, x_wrapped, n) == X
assert 2 * x_wrapped + 8 * y != 7944
assert 5 * x_wrapped + 3 * y != 4764

print(f"Solution: x={x}, y={y}")
print(f"Encodings: X={X}, Y={Y}")
print(f"First check: {left_1} == {right_1}")
print(f"Second check: {left_2} == {right_2}")
print(f"Order of g: {m}")

Expected output:

Solution: x=420, y=888
Encodings: X=1208230776, Y=122735854
First check: 1634636351 == 1634636351
Second check: 124876100 == 124876100
Order of g: 1073741814

The example demonstrates two useful operations: recovering a solution by matrix inversion and transporting linear equations through an exponentiation homomorphism. Its privacy interpretation depends on what the public equations reveal, while the meaning of its verification checks depends on the exponent order.

Editorial note: Adapted from the one-page document “Solving and Verifying a System of Linear Equations with Matrix Inversion and Homomorphic Verification.” All original numbers, the inverse, the solution, and both verification equations are preserved. The source's right-hand-side vector $B$ is written as $\mathbf{b}$ , and its encodings $gx$ and $gy$ are written as $X$ and $Y$ . The numerical residues, exponent-order analysis, executable checks, and clarification of the source's privacy claim were added during review.