2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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?" $\endgroup$ Jul 28, 2017 at 10:11
  • $\begingroup$ $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. $\endgroup$ Jul 29, 2017 at 10:50
  • $\begingroup$ 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. $\endgroup$ Jul 29, 2017 at 13:32

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.