# KDM Security IBE Based on LWE beyond Affine Functions
## 5 Our Full KDM-IBE Scheme
\begin{tabular}{l} \hline \hline \(\text{{Setup}}_{full}(\text{{\text@underline{1}}}^{\text{\text@underline{1}}} \text{{\text@underline{3}}},d)\) \\ \hline \(\text{Choose }\mathbf{R}\leftarrow\mathcal{D}_{\mathcal{Z},\omega(\sqrt{\log \log n})}^{\text{\text@underline{m}}\times\omega}\), for \(i=0,\cdots,d-1\), choose \(\mathbf{A}_{i}\leftarrow\mathbb{Z}_{q}^{n\times md}\), \(\mathbf{y}_{i}\leftarrow\mathbb{Z}_{q}^{n}\) uniformly and at random; let \(\widetilde{\mathbf{A}}_{i}=-\mathbf{A}_{i}\mathbf{R}\in\mathbb{Z}_{q}^{n\times \omega}\): \\ \(\mathbf{A}:=\begin{bmatrix}\mathbf{A}_{0}\\ \vdots\\ \mathbf{A}_{d-1}\end{bmatrix}\), \(\widetilde{\mathbf{A}}:=\begin{bmatrix}\widetilde{\mathbf{A}}_{0}\\ \vdots\\ \widetilde{\mathbf{A}}_{d-1}\end{bmatrix}=-\mathbf{A}\mathbf{R}\), \(\mathbf{y}=\begin{bmatrix}\mathbf{y}_{0}\\ \vdots\\ \mathbf{y}_{d-1}\end{bmatrix}\) \\ \(\text{Return master public key MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}},\mathbf{y}\right)\); master secret key \(\text{MSK}=\mathbf{R}\). \\ \hline \(\text{{Ext}}_{full}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}}, \mathbf{y}\right),\text{MSK}=\mathbf{R},\mu)\) \\ \hline \(\text{{Let}}\overset{\rightarrow\text{{\text@underline{1}}}}{\text{{u}}}^{ \text{\text@underline{1}}}:=\left(\text{{u}}^{0},\text{{u}}^{1},\cdots,\text{{u }}^{d-1}\right)\epsilon\mathbf{R}^{d}\), \(\widetilde{\mathbf{A}}_{u}=\overset{\rightarrow\text{{\text@underline{1}}}}{ \text{{u}}}^{\text{\text@underline{1}}}\mathbf{A}\), \(\mathbf{y}_{u}=\overset{\rightarrow\text{{\text@underline{1}}}}{\text{{u}}}^{ \text{\text@underline{1}}}\cdot\mathbf{y}\), and \(\mathbf{A}_{u}=\left[\overset{\rightarrow\text{{\text@underline{1}}}}{\text{{u}}} ^{\text{\text@underline{1}}}\cdot\mathbf{A}\right]\) \\ \(\text{By pre-image sample algorithm }(\text{Lemma 3})\), sample \(\mathbf{t}_{u}\leftarrow\mathcal{D}_{\widetilde{\mathbf{A}}_{u}^{\widetilde{ \mathbf{A}}_{u}}(\mathbf{A}_{u}),r}\) \\ \(\text{Let}\ \mathbf{s}\mathbf{k}_{u}=\mathbf{t}_{u}\); return secret key \(\mathbf{s}\mathbf{k}_{u}\) for identity \(u\). \\ \hline \(\text{{Enc}}_{full}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}}, \mathbf{y}\right),u,\mu=g(\mathbf{s}\mathbf{k}))\), \(g(x)\in G_{poly}\) \\ \hline \(\text{{Let}}\ \mu^{\prime}=Sim(g(\mathbf{s}\mathbf{k}))=\hat{f}(\mathbf{s} \mathbf{k};r)\), invoke \(\text{{Enc}}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}},\mathbf{y} \right),u,\mu^{\prime})\) (encryption algorithm in basic scheme) \\ \(\text{{Let}}\ \mathbf{C}=\text{{Enc}}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}}, \mathbf{y}\right),u,\mu^{\prime})\) \\ \(\text{{Return ciphertext }}\ \mathbf{C}\). \\ \hline \(\text{{Dec}}_{full}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}}, \mathbf{y}\right),\mathbf{s}\mathbf{k}_{u},\mathbf{C})\) \\ \hline \(\text{Invoke }\mathbf{Dec}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}}, \mathbf{y}\right),\mathbf{s}\mathbf{k}_{u},\mathbf{C})\) (decryption algorithm in basic scheme), so that \(\mu^{\prime}=\mathbf{Dec}(\text{MPK}=\left(\mathbf{A},\widetilde{\mathbf{A}}, \mathbf{y}\right),\mathbf{s}\mathbf{k}_{u},\mathbf{C})=\hat{f}(\mathbf{s} \mathbf{k};r)\) \\ \(\text{Invoke algorithm }D(\mu^{\prime})=\mu=g(\mathbf{s}\mathbf{k})\) Return \(\mu\). \\ \hline \end{tabular}   
In the full KDM-IBE scheme, only the encryption and decryption algorithms differ from the basic scheme. In the basic scheme, we can preserve secrecy when the message \(\mu=f(\mathbf{s}\mathbf{k})\), where \(f\in F_{aff}\). When the message \(\mu=g(\mathbf{s}\mathbf{k})\), \(function\)\(g\in G_{poly}\), the basic scheme will fail to work. Therefore, we use a randomized encoding simulator to convert \(g(\mathbf{s}\mathbf{k})\) to \(\hat{f}(\mathbf{s}\mathbf{k};r)\)i.e., \(u^{\prime}=Sim(g(\mathbf{sk}))=\hat{f}(\mathbf{sk};r)\), when \(r\) is determined, function \(\hat{f}\in F_{aff}\). The basic scheme will work on \(\mu^{\prime}\). In encryption algorithm, we encrypt \(\mu^{\prime}\). Upon decryption and obtaining \(\mu^{\prime}\), we invoke algorithm \(D(\mu^{\prime})=\mu=g(\mathbf{sk})\).