# Leaking Remainders and Breaking GGH

The GGH scheme was one of the first public key cryptosystems proposed after Ajtai’s work on generating hard instances of lattice problems. It didn’t take long before the scheme was completely broken due to an attack by Nguyen. Nevertheless, its analysis is valuable as much of the state of the art builds upon its core ideas.

## The Scheme

The scheme is based on a trapdoor function where the one-way computation is perturbing a lattice point and the trapdoor information is a reduced basis for the lattice.

Private keys are a randomly generated reduced basis $R$ and public keys are a non-reduced basis for the same lattice of the form $B = R \cdot U_1 \cdot U_2 \cdots U_m$ for some random unimodular matricies $U_i$. The encryption of a message $\textbf{m} \in \mathbb{Z}^{n}$ is $\mathbf{c} = \mathbf{m}B + \mathbf{e}$ where \(\mathbf{e} \in \{\pm \sigma\}^{n}\) (security parameter $\sigma$) is a random noise vector. The decryption of $\mathbf{c}$ is its nearest lattice point.

The picture above illustrates this in two dimensions. The public and private bases of the lattice are in red and green respectively. Decrypting $\mathbf{c}$ is equivalent to solving the closest vector problem.

## The Flaw

The flaw here lies in the error distribution. If all of the noise terms \(\mathbf{e} \in \{\pm \sigma\}^{n}\) are congruent to $\sigma \pmod{2\sigma}$, then adding another multiple of $\sigma$ completely cancels out the noise.

That is, adding $\mathbf{s} = (\sigma, \dots, \sigma) \in \mathbb{Z}^{n}$ to any ciphertext $\mathbf{c} = \mathbf{m}B + \mathbf{e}$ gives us

\[\mathbf{c} + \mathbf{s} = \mathbf{m}B \pmod{2\sigma}\]If $B$ is invertible mod $2\sigma$, then we immediately obtain $m_{2\sigma} = m \pmod{2\sigma}$. Rewrite

\[\mathbf{c} = \mathbf{m}B + \mathbf{e}\] \[\implies \mathbf{c} - \mathbf{m}_{2\sigma}B = (\mathbf{m} - \mathbf{m}_{2\sigma})B + \mathbf{e}\]This reduces to a much easier CVP problem of the form

\[\Sigma = \mathbf{m}^{\prime} B + \frac{1}{2\sigma} \mathbf{e}\]Where $\Sigma$ is a known quantity \(\frac{1}{2\sigma} (\mathbf{c} - \mathbf{m}_{2\sigma}B)\) and $\mathbf{m}^{\prime} = \frac{1}{2\sigma} (\mathbf{m} - \mathbf{m}_{2\sigma})$.

What makes this CVP instance easier than the original one? Notice that the length of the new error term $\lVert \frac{1}{2\sigma} \mathbf{e} \rVert = \frac{\sqrt n}{2} < \lVert \mathbf{e} \rVert$ is much smaller and no longer depends on $\sigma$. This simplified problem can then be solved with an approximation algorithm like Kannan’s embedding technique.

## Recovering the Scheme

The GGH scheme was proposed with no proof of security at the time. Instead, the authors published a set of ciphertexts as challenges over varying dimension. Nguyen used this technique for plaintext recovery up to dimension 400. The most obvious way to address the structure of the noise terms is to ensure that entries don’t share the same absolute value. Subsequent cryptosystems have addressed this flaw.