# How decode works in CCA1 scheme based on MP12 construction?

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?

• Welcome to Cryptography. In this site, $\LaTeX / MathJax$ is enabled. You can click edit and edit your question. – kelalaka Mar 8 '20 at 17:00
• Are you sure about your basis $S$? Do you have $G = I \otimes g$? – Mark Mar 10 '20 at 19:46
• Since $n=1$, then $G = g^t = [1, 2, 4, 8, 16, 32, 64, 128, 256]$. I am not sure about basis $S$. I tried $S = \begin{pmatrix} 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ -1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & -1 & 2 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & -1 & 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & -1 & 2 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & -1 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & -1 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 2\\ \end{pmatrix}$ – Eduardo Morais Mar 11 '20 at 12:55
• But in this case we have that $encode(m) = [2, -1, 0, 0, 0, 0, 0, 0, 0]$, which gets mixed with error $e$. Therefore message $m$ either gets mixed with $s$ or with $e$. – Eduardo Morais Mar 11 '20 at 13:04
• If you think everything is right up to the decoding step, it might be worthwhile to look at section 5 of that paper. They generalize the decoding step to other moduli, and give explicit algorithms for decoding. – Mark Mar 11 '20 at 16:22

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.