# KDM Security IBE Based on LWE beyond Affine Functions
## 4 Our Basic KDM-IBE Scheme
By Lemma 1, \(\mathbf{y}_{i}^{*}\) generated using this method was statistically indistinguishable from \(\mathbf{y}_{i}^{*}\) generated by selections performed uniformly and at random; then, we sampled \(\mathbf{z}_{i}\) from \(\mathcal{D}_{\mathbf{A}_{i}^{*}[\mathbf{A}_{i}^{*}|-\mathbf{A}_{i}^{*}\mathbf{ R}]\mathbf{z}^{\prime})}\). Let \(I=\left\{u_{1}^{*},\cdots,u_{i}^{*}\right\}\) denote the list of target identities, where \(l\leq d\), and, as in [2], we defined the monic degree-d polynomial \(f(x)=x^{d-l}\cdot\prod\limits_{u_{i}^{*}\in I}\left(x-u_{i}^{*}\right)=c_{0 }+c_{1}x+\cdots+c_{d-1}x^{d-1}+x^{d}\). Then, we invoked the all-but-d trapdoor construction on \(\mathbf{A}_{i}^{*},\mathbf{y}_{i}^{*}\), \(\mathbf{R}\), \(f(x)\) and identities \(u_{i}\) for \(i=0\)_to \(d-1\)_, and received \(\mathbf{A}_{i}\), \(\mathbf{y}_{i}\). Let \(\widetilde{\mathbf{A}}_{i}=-\mathbf{A}_{i}\mathbf{R}+c_{i}\mathbf{G}\). Let \(\mathbf{A}\) denote the stack of matrices \(\mathbf{A}_{i}\), \(\mathbf{y}\) denote the stack of matrices \(\widetilde{\mathbf{y}}_{i}\), and \(\widetilde{\mathbf{A}}\) denote the stack of matrices \(\widetilde{\mathbf{A}}_{i}\); then, \((\mathbf{A},\widetilde{\mathbf{A}},\mathbf{y})\) as the master public key was sent to the adversary, where \(\overset{\rightarrow}{u_{i}}=(u_{i}^{0},u_{i}^{1},\cdots,u_{i}^{d-1})\), \(\mathbf{A}_{i}^{*}=\overset{\rightarrow}{u_{i}}\cdot\mathbf{A}\), \(\mathbf{y}_{i}^{*}=\overset{\rightarrow}{u_{i}}\cdot\mathbf{y}\). Therefore, \(\mathbf{A},\mathbf{y}\) were statistically uniformly random because \(\mathbf{A}_{i}^{*},\mathbf{y}_{i}^{*}\) were uniformly (by Lemma 4). Then, the user public key for identity \(\mathbf{u}\) was \(\mathbf{A}_{u_{i}}=\left[\overset{\rightarrow}{u_{i}}\cdot\mathbf{A}|u_{i}^ {d}\mathbf{G}+\overset{\rightarrow}{u_{i}}\cdot\overset{\rightarrow}{ \mathbf{A}}_{i}\right]=\left[\mathbf{A}_{i}^{*}\right]\left|u_{i}^{d}\mathbf{G} +\overset{\rightarrow}{u_{i}}\cdot\left(-\mathbf{A}\mathbf{R}+[c_{0},\cdots,c_{d-1}]^{t}\mathbf{G}\right)\right]=\left[\mathbf{A}_{i}^{*}|-\mathbf{A}_{i} ^{*}\mathbf{R}+f(u_{i})\mathbf{G}\right]\), if \(u_{i}\in I\), \(f(u_{i})=0\), \(\mathbf{A}_{u_{i}}=[\mathbf{A}_{i}^{*}|-\mathbf{A}_{i}^{*}\mathbf{R}]\). In this game, for the KDM query \((f_{0},f_{1},i)\), \(\beta\in\{0,1\}\), where \(i\in[i]\) and \(f_{0}\), \(f_{1}\) are affine functions, we let message \(m=f_{\beta}(\mathbf{sk}_{1},\cdots,\mathbf{sk}_{l})\) and encrypted \(m\) under identity \(u_{i}\). We responded to the adversary with ciphertext \(\mathbf{C}=(\mathbf{c}_{1},\mathbf{c}_{2})\), where  
\[\mathbf{c}_{1}^{t}=\mathbf{s}^{t}[\mathbf{A}_{i}^{*}|-\mathbf{A}_{i}^{*}\mathbf{R}]+ \left[\left(\mathbf{e}^{(1)}\right)^{t}\left|\left(\mathbf{e}^{(2)}\right)^{t}\right|,\;c_{2}=\mathbf{s}^{t}[\mathbf{y}_{i}^{*}]+e^{\prime}+p\cdot m\]  
Ciphertext \(\mathbf{c}\) in \(\mathbf{G}_{1}\) was statistically indistinguishable from \(\mathbf{G}_{0}\). Note that when \(u_{i}\in I\), \(f(u_{i})=0\), \(\mathbf{A}_{u_{i}}=[\mathbf{A}_{i}^{*}|-\mathbf{A}_{i}^{*}\mathbf{R}]\), such that \(\mathbf{A}_{u_{i}} \begin{bmatrix}\mathbf{R}\\ \mathbf{I}\end{bmatrix} =0\), then \(\mathbf{R}\) is not the trapdoor for \(\mathbf{A}_{u_{i}}\); we \"puncture\" the public key at target identities. \(\mathbf{G}_{2}\): in game \(\mathbf{G}_{2}\), we used the output values of the challenger in an actual KDM-CPA-secure PKE attack game from [10] to simulate game \(\mathbf{G}_{1}\). Our IBE secret keys and ciphertexts had lager dimensions than the PKE scheme presented in [10] because of an additive term of \(\omega\) (the width of \"gadget\" matrix \(\mathbf{G}\)). Therefore, when we constructed the IBE ciphertexts and secret keys from the PKE scheme, we needed to add the missing dimensions so that the ciphertexts and secret keys we constructed were statistically indistinguishable from those presented in \(\mathbf{G}_{1}\). This created a super-polynomial modulus \(q\). The filling technology we used in the study was similar to [2]; we omitted the details from this study.