C-4.2 Example

Suppose we have the following LWE setup:

$t=4$

$q=64$

$n=4$

$\mathrm{\Delta }={\displaystyle \frac{q}{t}}=16$

$m=1\in {\mathbb{Z}}_t$

$S=(s_0,s_1,s_2,s_3)=(0,1,1,0)\in {\{-1,0,1\}}^4$

$A=(a_0,a_1,a_2,a_3)=(-25,12,-3,7)\in {\mathbb{Z}}_q^4$

$e=1\in {\mathbb{Z}}_q$

$b=a_0{s}_0+a_1{s}_1+a_2{s}_2+a_3{s}_3+\mathrm{\Delta }m+e=26\in {\mathbb{Z}}_q$

${\mathsf{\text{𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }m+e)=\mathsf{\text{𝖼𝗍}}=(a_0,a_1,a_2,a_3,b)=(-25,12,-3,7,26)\in {\mathbb{Z}}_q^{n+1}$

Now, suppose we want modulus switching from $q=64$ to $\widehat{q}=32$, which gives:

$\widehat{\mathrm{\Delta }}=\mathrm{\Delta }\cdot {\displaystyle \frac{32}{64}}=8$

$\widehat{e}=\lceil 1\cdot {\displaystyle \frac{32}{64}}\rfloor =1$

${\mathsf{\text{𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{\mathrm{\Delta }}m+\widehat{e}+{𝜖}_{\mathit{\text{𝑎𝑙𝑙}}})=\widehat{\mathsf{\text{𝖼𝗍}}}=(\widehat{a_0},\widehat{a_1},\widehat{a_2},\widehat{a_3},\widehat{b})$

$=\left(\lceil -25\cdot {\displaystyle \frac{32}{64}}\rfloor ,\lceil 12\cdot {\displaystyle \frac{32}{64}}\rfloor ,\lceil -3\cdot {\displaystyle \frac{32}{64}}\rfloor ,\lceil 7\cdot {\displaystyle \frac{32}{64}}\rfloor ,\lceil 26\cdot {\displaystyle \frac{32}{64}}\rfloor \right)$

$=(-12,6,-1,4,13)\in {\mathbb{Z}}_{\widehat{q}}^{n+1}$

Now, verify if the following LWE constraint holds:

$\widehat{b}={\widehat{a}}_0{s}_0+{\widehat{a}}_1{s}_1+{\widehat{a}}_2{s}_2+{\widehat{a}}_3{s}_3+\widehat{\mathrm{\Delta }}m+\widehat{e}\in {\mathbb{Z}}_{32}$

$13=0+6-1+0+8\cdot 1+1\in {\mathbb{Z}}_{32}$

$13\approx 14\in {\mathbb{Z}}_{32}$

We got this small difference of 1 due to the rounding drift error of:

$\widehat{a_0}=\lceil -12.5\rfloor =-12$, $\widehat{a_2}=\lceil -1.5\rfloor =-1$, $\widehat{a_3}=\lceil 3.5\rfloor =4$, and $\widehat{e}=\lceil 0.5\rfloor =1$

If we solve the LWE decryption formula:

$\widehat{b}-({\widehat{a}}_0{s}_0+{\widehat{a}}_1{s}_1+{\widehat{a}}_2{s}_2+{\widehat{a}}_3{s}_3)=13-(0(-12)+1(6)+1(-1)+0(4))=13-(6-1)=8=\widehat{m}+\widehat{e}\in {\mathbb{Z}}_{32}$

$m=\lceil {\displaystyle \frac{8}{\widehat{\mathrm{\Delta }}}}\rfloor =\lceil {\displaystyle \frac{8}{8}}\rfloor =1$, which is correct.