# KDM Security IBE Based on LWE beyond Affine Functions
## 4 Our Basic KDM-IBE Scheme  
Based on the extended LWE assumption, we proposed a basic KDM-IBE scheme in which the challenge function ensemble included the affine functions of the user's secret key and presented the parameter range, correctness analysis, and security proof values. Then, in the subsequent section, we used the challenge function ensemble amplification technique to amplify the relevant challenge function ensemble to the polynomial function of the user's secret key. The following presents our construction scheme:  
**Parameters. ** Let \(n=poly(\lambda)\), \(m\geq n\text{log}\,q+2\lambda-2\), \(q=p^{2}\), \(p=\gamma.poly(n)\) as a sufficiently large \(poly(n)\) item to ensure correctness,\(\gamma=r^{\omega(1)}\), and \(r\geq O(\sqrt{md})\cdot\omega(\sqrt{\log n})^{2}\). **Correctness. ** Let \(\mathbf{e}^{t}=\left[\left(\mathbf{e}^{(1)}\right)^{t}\right]\left(\mathbf{e}^{(2)}\right) ^{t}\right]\). For identity \(u\), message \(\mu\), ciphertext \(\mathbf{C}=(\mathbf{c}_{1},c_{2})\), and secret key \(\mathbf{sk}_{u}\), we obtain:  
\(c_{2}-\mathbf{c}_{1}^{t}\mathbf{sk}_{u}=\mathbf{s}^{t}\mathbf{y}_{u}+\mathbf{e}^{t}\cdot p\cdot\mu- \mathbf{s}^{t}\mathbf{A}_{u}\mathbf{sk}_{u}-\mathbf{e}^{t}\mathbf{sk}_{u}=p\cdot\mu+\mathbf{e}^{t}\mathbf{sk }_{u}\). By Lemma 1, \(\left|\mathbf{e}^{t}+\mathbf{e}^{t}\mathbf{sk}_{u}\right|<\left|\mathbf{e}^{t}\right|+\left| \mathbf{e}^{t}\mathbf{sk}_{u}\right|\leq\gamma\cdot\left(\omega\left(\sqrt{\log n} \right)+\omega\right)+r^{2}md<\frac{p}{2}\). Therefore, we obtain the correct message with overwhelming probability. **Theorem 1**. : _For the abovementioned parameters, our basic KDM-IBE scheme was selective identity KDM-CPA-secure with respect to the affine functions over \(\mathbb{Z}_{p}\), under the KDM-CPA security of the scheme described in Section 3.3 and the LWE assumption._  
Proof of Theorem 1.: Our proof started with game \(\mathbf{G}_{0}\), it was the actual attack game we described in Section 3.3. In game \(\mathbf{G}_{1}\), unlike \(\mathbf{G}_{0}\), the master public key in \(\mathbf{G}_{1}\) was not uniformly selected at random, but was generated using the all-but-trapdoor construction and was statistically indistinguishable from \(\mathbf{G}_{0}\). In game \(\mathbf{G}_{2}\), we played an actual KDM-CPA-secure PKE attack game obtained from [10], and used its outputs to simulate \(\mathbf{G}_{1}\). \(\mathbf{G}_{0}\): This was the actual attack game we described in Section 3.3. Similar to the abovementioned scheme, we selected the master public key uniformly at random. For KDM queries \((f_{0},f_{1},i)\), \(\beta\in\{0,1\}\), where \(i\in[l]\) and \(f_{0}\), \(f_{1}\) are affine functions, we letmessage \(m=f_{\beta}(\mathbf{sk}_{1},\cdots,\mathbf{sk}_{l})\), and encrypted \(m\) under identity \(u_{i}\). Then, we responded to the adversary with ciphertext \(\mathbf{C}=(\mathbf{c}_{1},c_{2})\), where  
\[\mathbf{c}_{1}^{t}=\mathbf{s}^{t}\left[\overset{\rightarrow}{u_{i}} \cdot\mathbf{A}\left|\overset{\rightarrow}{u_{i}}\cdot\overset{\rightarrow} {\mathbf{A}}\right]+\left[\left(\mathbf{e}^{(1)}\right)^{t}\left|\left(\mathbf{e}^{(2) }\right)^{t}\right|,\;c_{2}=\mathbf{s}^{t}\left[\overset{\rightarrow}{u_{i}} \cdot\mathbf{y}\right]+e^{\prime}+p\cdot m\right.\]  
\(\mathbf{G}_{1}\): In this game, we generated a master public key and punctured it at each of the challenge identities by using the all-but-d trapdoor construction we describe in Section 3.6. First, we chose \(\mathbf{R}\leftarrow\mathcal{D}_{\mathbb{Z},\omega(\sqrt{\log n})}^{\text{m} \times\omega}\) as the master secret key and for \(i=0\)_to \(d-1\)_; we chose uniform random matrices \(\mathbf{A}_{i}^{*}\leftarrow\mathbb{Z}_{q}^{n\times md}\), let the secret key of identity \(u_{i}\) be \(\mathbf{z}_{i}\leftarrow\mathcal{D}_{\mathbb{Z},r}^{md+\omega}\), and sets \(\mathbf{y}_{i}^{*}=[\mathbf{A}_{i}^{*}|-\mathbf{A}_{i}^{*}\mathbf{R}]\mathbf{z}_{ i}\).