1
$\begingroup$

In section 3.2 (page 10) of Vikram Singh's paper A practical Key Exchange for the internet using Lattice Cryptography, he gives the number of elements in each set for odd $q$. However, the results do not match my calculation of the number of elements in each set for odd $q$.

For example, given an odd prime $q=17$, you can see that calculated result does not match. Can anyone explain this discrepancy?

$\textbf{Randomized Rounding Procedure:}$

Let $q=17$. Thus $q\bmod 4 = 17\bmod 4 = 1 \implies q \equiv 1 \pmod4$

Now,

$$I_0 = \mathbb{Z}_q \cap \left[0,\tfrac{q}4\right) = \mathbb{Z}_q \cap \left[0,\tfrac{17}4\right) = \left[0,4\right)$$ $$I^{\prime}_1 = \mathbb{Z}_q \cap \left[\tfrac{q}4,\tfrac{q}2\right) = \left[\tfrac{17}4,\tfrac{17}2\right) = \left[4,8\right)$$ $$I^{\prime}_0 = \mathbb{Z}_q \cap \left[\tfrac{q}2,\tfrac{3q}4\right) = \left[\tfrac{17}2,\tfrac{51}4\right) = \left[8,12\right)$$ $$I_1 = \mathbb{Z}_q \cap \left[\tfrac{3q}4,q\right) = \left[\tfrac{51}4,17\right) = \left[12,17\right)$$

For odd $q$ the number of elements in each set is:

$$\left(\begin{array}{cc}\#I_1 & \#I_0 \\ \#I^{\prime}_0 & \#I^{\prime}_1\end{array}\right) = \left(\begin{array}{cc}\tfrac{q-1}4 & \tfrac{q+3}4 \\ \tfrac{q-1}4 & \tfrac{q-1}4\end{array}\right) \textrm{ for } q \equiv 1\pmod4$$ $$= \left(\begin{array}{cc}\tfrac{16}4 & \tfrac{20}4 \\ \tfrac{16}4 & \tfrac{16}4\end{array}\right)$$ $$= \left(\begin{array}{cc}4 & 5 \\ 4 & 4\end{array}\right)$$

But $I_0 = \left[0,4\right) = \left\{0,1,2,3\right\}$ (No. of elements is not 5), and $I_1 = \left[12,17\right) = \left\{12,13,14,15,16\right\}$ (No. of elements is not 4)

So, the number of elements in $I_0$ is not 5. Why?

$\endgroup$
1
$\begingroup$

$4 < 17/4 = 4.25$, so $4 \in [0, 17/4) = [0, 4.25)$. Hence $I_0 = \{0,1,2,3,4\}$, not $\{0,1,2,3\}$.

$\endgroup$
  • $\begingroup$ Also, On page number 10/11, there is count array representing the relative probability of each set $\endgroup$ – vivek Mar 15 '18 at 4:46
  • $\begingroup$ On page number 10 and 11, there is count array representing the relative probability of each set as $$ \begin{pmatrix} (q+1)/4 & (q-1)/4\\ (q-1)/4 & (q+1)/4\\ \end{pmatrix} $$ How is this matrix calculated?? $\endgroup$ – vivek Mar 15 '18 at 4:52

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.