# Found a mistake in a proof about when GGH will decrypt incorrectly

The proof is here on page 66, lemma 20. I found the same mistake in other sources also.

It claims that GGH decryption will fail only if $\lceil R^{-1}e\rfloor \not =0$. Here $R$ is the "good" private basis for the lattice and $e$ is the small random vector. Rounding symbol means just that every coordinate of the vector will be rounded to the nearest integer.

In the proof they use the "fact" that $B^{-1}R$ is an unimodular matrix. They come to this conclusion from the fact that the two bases are connected by a unimodular matrix $U$ like this

$$B=UR.$$

This is correct. However from this they deduce that $$U^{-1}=B^{-1}R.$$ This is clearly false. Actually $$U^{-1}=RB^{-1}.$$ There is no guarantee that $B^{-1}R$ is unimodular.

Have any of you come across another way to prove this result?

• The original paper writes $T = B^{-1}{R}$, so I think this $U^{-1}$ is a typo on the PDF you linked. Take a look at Lemma 4, page 7. Moreover, $U^{-1}$ is not really used. Therefore, your question may be simplified to "Why is $B^{-1}{R}$ unimodular?" Jul 28, 2017 at 10:11
• $B^{-1}R$ isn't necessarily unimodular. This is the heart of the problem. Let $$R=\begin{Bmatrix} 1& 0 \\ 0& 2 \end{Bmatrix}$$ and $$U=\begin{Bmatrix} 1& 0 \\ 1& 1 \end{Bmatrix}.$$ $U$ is unimodular, so $$B=UR=\begin{Bmatrix} 1& 0 \\ 1& 2 \end{Bmatrix}.$$ Now $$R^{-1}B=\begin{Bmatrix} 1& 0 \\ 0& \frac{1}{2} \end{Bmatrix}\begin{Bmatrix} 1& 0 \\ 1& 2 \end{Bmatrix}=\begin{Bmatrix} 1& 0 \\ \frac{1}{2}& 1 \end{Bmatrix},$$ which is not unimodular and neither is it's inverse $B^{-1}R$. Hopefully you see what I'm getting at. Jul 29, 2017 at 10:50
• Yes, I had already understood that when I posted my comment. But maybe the original paper chooses $R$ with some extra properties to force this product to be unimodular. It is a good idea to check that. Jul 29, 2017 at 13:32

Okay, this was a really stupid mistake by me. I got confused because some sources use notation where $R$ and $B$ have the basis vectors as rows. However Goldreich, Goldwasser and Halevi have the basis vectors as columns so $$B=RU\implies U=R^{-1}B.$$ Hence the matrix is unimodular and the proof works. Sorry about the inconvience.