How decode works in CCA1 scheme based on MP12 construction?

Question

In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have:

$S = \begin{pmatrix} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\\ 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 0\\ 4 & 8 & 16 & 32 & 64 & 128 & 256 & 0 & 0\\ 8 & 16 & 32 & 64 & 128 & 256 & 0 & 0 & 0\\ 16 & 32 & 64 & 128 & 256 & 0 & 0 & 0 & 0\\ 32 & 64 & 128 & 256 & 0 & 0 & 0 & 0 & 0\\ 64 & 128 & 256 & 0 & 0 & 0 & 0 & 0 & 0\\ 128 & 256 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 256 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

I used very simple parameters: $q=512$, $k=9$, $n=1$, $m=18$. I set $H$ and $R$ to the identity matrix.This way I have that $A_u = [A' \mid -A' + G]$. Therefore, I have that $encode([1, 0, 0, 0, 0, 0, 0, 0, 0]) = [1, 2, 4, 8, 16, 32, 64, 128, 256] = G$. Fixing $s=1$, I computed $2s.A_u + e + encode(m) = [2.A' \mid -2A' + 2.G] + [0 \mid G] + e = [2.A' \mid -2A' + 3.G] + e \pmod{2q}$.

The inversion oracle returns $z=3$ and a big error $e'$ (but such that $e'.[R \mid I]^t = e.[R \mid I]^t \pmod{q}$). The decryption algorithm returns $m=[1, 1, 0, 0, 0, 0, 0, 0]$.

In general I have that $m$ is being added to $2s$, so the decryption algorithm returns the binary decomposition of $DecimalRepresentation(m)+2s$, instead of only $m$.

In Lemma 6.2, we have that $v^t.[R \mid I]^t = 2(sG \pmod{q}) + encode(m) \pmod{2q}$. Therefore I reached this point successfully. Hence I guess my Decode algorithm is wrong. In order to decode, I am multiplying by $Inverse(S)$. Afterwards I divide the obtained vector by $q^{k-1}$.

What am I doing wrong?

Answer 1

After some time I revisited the problem and found out that before decoding it is necessary to reduce modulo the fundamental region to find a coset, then we have that in the example I gave the internal value $2s+m$ is equal to $[1, 1, \dots]$, and after reduction it turns out to be equivalent to $[1, 0, \dots]$, which is $m$, as needed.