Constructing and attacking GGH public key cryptosystem¶
GGH cryptosystem named after it's authors - Goldwasser, Goldreich and Halevi is one of the earlier cryptosystems based on some lattice problem. In case for GGH the underlying problem is CVP (Closest Vector Problem). In order to construct a trapdoor, the concept of good and bad basis is created. Although the GGH has already been already successfully cryptanalyzed for practical parameters sizes, due to it's relative simplicity it serves as a good introduction to latticed based cryptography and cryptanalysis.
GGH Public Key Cryptosystem¶
The key concept behind the GGH cryptosystem is the notion of good and bad basis.
Good basis consists of relativly short and orthogonal lattice vectors, which allows (with correctly choosen parameters) for solving CVP with sufficiently good approximation.
Bad basis consists of long and highly non-orthogonal lattice vectors.
Key creation¶
Let's strart by choosing a set of linearly independent vectors that will server as a good basis (to check whether a basis is good we can calculate it's Hadamard ratio)
$$
v_1,...,v_n \in \mathbb{Z}^{n}
$$
Let $V$ be a $n$-by-$n$ matrix whose rows are the vectors $v_1, ..., v_n$
$$
\begin{bmatrix}
v_1 \newline
\vdots \newline
v_n
\end{bmatrix}
$$
In order to create the hardest possible basis that spans the same lattice we can use the Hermite normal form of the matrix $V$, which is an analogue of reduced echelon form for matrices over the integers $\mathbb{Z}$ and is the same for every basis of a given lattice.
Let
$$
W = \text{hnf}(V)
$$
The $V$ matrix is a good basis and will serve as a private key, while the matrix $W$ is a bad basis and will be used as public key.
import numpy as np
import lbpqc.primitives.lattice.fullrank as frl
from lbpqc.primitives.matrix import HNF
# let's choose the vectors for a good basis
v1 = np.array([-97, 19, 19])
v2 = np.array([-36, 30, 86])
v3 = np.array([-184, -64, 78])
V = np.array([v1, v2, v3])
print("Good basis V")
print(V)
print(f"Hadamard ratio for V: {frl.hadamard_ratio(V):.2f}")
print()
# Now let's calculate bad basis W as a Hermite normal form of V
W, *_ = HNF(V)
print("Bad basis W:")
print(W)
print(f"Hadamard ratio for W: {frl.hadamard_ratio(W)}")
Good basis V [[ -97 19 19] [ -36 30 86] [-184 -64 78]] Hadamard ratio for V: 0.75 Bad basis W: [[ 1 1 285737] [ 0 2 181486] [ 0 0 429758]] Hadamard ratio for W: 0.00033786260692220203
Encryption¶
Let $ m \in \mathbb{Z}^{n} $ be an integer vector representing plaintext that is to be encrypted and $r \in \mathbb{R}^{n}$ be a small perturbation vector that will act as a noise.
In order to encrypt vector $m$ using public key $W$ and noise vector $r$ we compute
$$
e = m \cdot W + r
$$
because we add noise vector $r$, the vector $e$ is not a lattice point itself, but it should be close to the lattice point $mW$ since $r$ is small.
The vector $e$ is our encrypted message.
r = np.array([-4, -3, 2])
m = np.array([86, -35, -32])
e = m @ W + r
print(f"Encrypted message e: {e}")
Encrypted message e: [ 82 13 4469118]
Decryption¶
In order to decrypt vector $e$ we wil use Babai's algorithm.
Given some lattice basis $B$ and some vector $w$, Babai's algorithm will find approxCVP in a following way
$$
\begin{aligned}
\text{1.} & \text{Write the vector} \; w \; \text{in coordinates of basis} \; B \; \text{by solving} \; w = x \cdot B.\newline
\text{2.} & \; x \in \mathbb{R}^{n} \; \text{so round it's coefficients to the nearest integer.}\newline
\text{3.} & \text{return x.}
\end{aligned}
$$
$$
x = \text{babai}(V,e)
$$
Vector $x$ is written using private basis, so to get to the message we need to change basis to public basis.
$$
d = (x \cdot V) \cdot W^{-1}
$$
Vector $d$ is the encrypted message.
x = frl.babai_cvp(e, V)
d = ((x @ V) @ np.linalg.inv(W)).astype(int)
print(f"Message m: {m}")
print(f"Decrypted message d: {d}")
assert np.all(m == d)
Message m: [ 86 -35 -32] Decrypted message d: [ 86 -35 -32]
Let's also try to decrypt the message using only public key $W$.
Then $ y = \text{babai}(W, e) \cdot W $.
y = frl.babai_cvp(e, W) @ W
print(f"Message m: {m}")
print(f"Decrypted message y: {y}")
Message m: [ 86 -35 -32] Decrypted message y: [ 82 14 4367170]
Because $W$ is a bad basis, Babai's algorithm gives a very bad approximation for CVP, hence the message is incorrectly decrypted.
Attacking the underlying problem¶
Unfortunetly GGH cryptosystem is not very secure. The only thing we need to break it, is to somehow transform a known bad basis $W$ into some better basis $M$. We can use the LLL algorithm to do just that.
from lbpqc.primitives.lattice.reductions import LLL
M = LLL(W)
print("LLL reduced basis M")
print(M)
print(f"Hadamard ratio for M: {frl.hadamard_ratio(M):.2f}")
s = frl.babai_cvp(e, M)
s = ((s @ M) @ np.linalg.inv(W)).astype(int)
print(f"Message m: {m}")
print(f"Decrypted message s: {s}")
assert np.all(m==s)
LLL reduced basis M [[ -36. 30. 86.] [ -61. -11. -67.] [ 10. -102. 40.]] Hadamard ratio for M: 0.96 Message m: [ 86 -35 -32] Decrypted message s: [ 86 -35 -32]
Using only public key $W$ we managed to decrypt the message $e$ by utilizing the LLL algorithm.