Algorithm 4: Generating Algorithm for Public Key without Noises

· Let $I_i=\langle {\alpha }_i\rangle$ ( $1\le i\le m$ ) be pairwise relatively prime, and

$d_i\left(x\right)={\displaystyle {\displaystyle \prod }}_{j=1,j\ne i}^m{\tau }^{-1}\left({\alpha }_i\right),1\le i\le m,$

where the secret key $I_i=\langle {\alpha }_i\rangle$ ( $1\le i\le m$ ), and ${\tau }^{-1}$ is the inverse mapping of $\tau$ given by (2.1).

Since $d_i\left(x\right)$ and ${\tau }^{-1}\left({\alpha }_i\right)$ are relatively prime polynomial in quotient ring $\mathbb{Z}\left[x\right]/\langle \varphi \left(x\right)\rangle$ , it follows that

$\langle d_i\left(x\right)\rangle +\langle {\tau }^{-1}\left({\alpha }_i\right)\rangle =\mathbb{Z}\left[x\right]/\langle \varphi \left(x\right)\rangle \mathrm{.}$

Therefore, there is a polynomial ${\mathcal{D}}_i\left(x\right)$ such that

$d_i\left(x\right){\mathcal{D}}_i\left(x\right)\equiv 1\left(\mathrm{mod}{\tau }^{-1}\left({\alpha }_i\right)\right)\mathrm{.}$

We put ${\mathcal{D}}_i=\tau \left({\mathcal{D}}_i\left(x\right)\right)$ , and $A_i=d_i\otimes {\mathcal{D}}_i$ , $1\le i\le m$ .