Algorithm 3: Generating Algorithm for Secret Key

$•$ First Step. Randomly select an non-zero vector $\alpha \in {\mathbb{Z}}^n$ as input, and the output is the following relatively prime two ideal $I_1$ and $I_2$ , where

$I_1=\langle \alpha \rangle \mathrm{,}\text{and}{I}_2=\langle e-\alpha \rangle \mathrm{.}$

$•$ Second Step. Randomly select two non-zero vectors ${\alpha }_1\in I_1$ and ${\alpha }_2\in I_2$ as

input, and the output is the following ideal $I_3$ , where

$I_3=\langle e-{\alpha }_1\otimes {\alpha }_2\rangle \mathrm{.}$

It is easy to see that $I_1\mathrm{,}{I}_2\mathrm{,}{I}_3$ are pairwise relatively prime ideals.

$•$ Last Step. Suppose that $m-1$ pairwise relatively prime ideals $I_1\mathrm{,}{I}_2\mathrm{,}\cdots \mathrm{,}{I}_{m-1}$ are selected, then one randomly finds ${\alpha }_1\in I_1$ , ${\alpha }_2\in I_2$ , $\cdots$ , ${\alpha }_{m-1}\in I_{m-1}$ , ${\alpha }_i\ne 0$ , and the output ideal $I_m$ given by

$I_m=\langle e-{\alpha }_1\otimes {\alpha }_2\otimes \cdots \otimes {\alpha }_{m-1}\rangle \mathrm{.}$

Obviously, $I_1\mathrm{,}{I}_2\mathrm{,}\cdots \mathrm{,}{I}_m$ are pairwise relatively prime ideals in ${\mathbb{Z}}^n$ .