1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Welcome to Cryptography. In this site, $\LaTeX / MathJax$ is enabled. You can click edit and edit your question. $\endgroup$ – kelalaka Mar 8 '20 at 17:00
  • $\begingroup$ Are you sure about your basis $S$? Do you have $G = I \otimes g$? $\endgroup$ – Mark Mar 10 '20 at 19:46
  • $\begingroup$ 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}$ $\endgroup$ – Eduardo Morais Mar 11 '20 at 12:55
  • $\begingroup$ 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$. $\endgroup$ – Eduardo Morais Mar 11 '20 at 13:04
  • $\begingroup$ 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. $\endgroup$ – Mark Mar 11 '20 at 16:22
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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