1

I have a question for the algorithm gen public key of The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem. GenKey Algorithm as described in the paper:

Pick a matrix $R'$ which is uniformly distributed in $\{-l,\ldots,l\}$ and then compute $R = R' + k\cdot I$. Then we have $R$ a private basis. And $I$ know a basis of the lattice is linearly independent vectors.

I want to know why $R$ is the basis of lattice when it maybe isn't linearly independent vectors?

kelalaka
  • 1,637
Phương Thu
  • 11
  • https://en.wikipedia.org/wiki/GGH_encryption_scheme – kelalaka Mar 18 '21 at 17:46
  • Did you read the next sentence? The larger the value of $k$ is, this process generates a basis with smaller dual orthogonality factor, so it may be possible to choose a larger value of $\sigma$ So it's try and find one. – kelalaka Mar 18 '21 at 18:57
  • @kelalaka Thank you so much and i have another question. The once mothod gen private basis is choose a matrix R which is uniformly distributed in {- l,.., +l} for some integer bound l. R is choose random, so how can i make sure det(R) is non-zero to inverse R? – – Phương Thu Mar 20 '21 at 19:00

0 Answers0