1
$\begingroup$

In this paper : https://eprint.iacr.org/2011/501.pdf There is an equality page 10, in the second paragraph considered by the authors as "easy to check". If someone could explain to me why the set at the left side is included in the set at the right side, I will be the happiest man on earth. All the definitions are given in the same page.

$\endgroup$
1
  • 1
    $\begingroup$ It will be better to make your question self-contained. $\endgroup$ Apr 12, 2016 at 11:19

1 Answer 1

1
$\begingroup$

We prove $\frac{1}{q}\Lambda(A^t)=\Lambda^\perp(A)^*$.

(1) $\frac{1}{q}\Lambda(A^t)\subset\Lambda^\perp(A)^*$: If $z=A^ts$ (mod $q$) then for any $y\in\Lambda^\perp(A)$, $\langle \frac{1}{q}z,y\rangle\in\frac{1}{q}\langle A^ts,y\rangle+\mathbb{Z}=\frac{1}{q}\langle s,Ay\rangle+\mathbb{Z}\in\mathbb{Z},$ since $Ay=0$ (mod $q$). So, $\frac{1}{q}z\in\Lambda^\perp(A)^*$.

(2) $ \Bigl(\frac{1}{q}\Lambda(A^t)\Bigr)^*\subset\Lambda^\perp(A)$: Suppose $\langle y,\frac{1}{q}\Lambda(A^t)\rangle\in\mathbb{Z}$. Then $\langle y,A^ts\rangle=\langle Ay,s\rangle=0$ (mod $q$), for all $s$, and so $Ay=0$ (mod $q$).

Finally, $\Lambda^\perp(A)^*\subset\frac{1}{q}\Lambda(A^t)$ follows from (2) and two simple general facts about dual lattices: 1) $\Lambda\subset\Gamma$ iff $\Gamma^*\subset\Lambda^*$ and 2) $\Lambda^{**}=\Lambda$.

$\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.