# KDM Security IBE Based on LWE beyond Affine Functions
## 5 Our Full KDM-IBE Scheme
Theorem 3.2: _Our full KDM-IBE scheme is selective identity KDM-CPA-secure with respect to \(G_{poly}\) over \(\mathbb{Z}_{p}\), under the KDM-CPA security of our basic IBE scheme and the security of randomized encoding of functions; the parameters in the full KDM-IBE scheme are the same as those of the basic IBE scheme._  
Proof of Theorem 3.2.: Our formal proof starts with the game \(\mathbf{G}_{0}\), which we prove in Section 4 to be KDM-CPA-secure. The game \(\mathbf{G}_{1}\) is the actual attack game from our full KDM-IBE scheme; we use its outputs to simulate \(\mathbf{G}_{0}\), and prove \(\mathbf{G}_{1}\) was statistically indistinguishable from \(\mathbf{G}_{0}\). \(\mathbf{G}_{0}\): This is the actual attack game we described in Section 4. 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.5. For master public key \(\text{MPK}=(\mathbf{A},\overset{\sim}{\mathbf{A}},\mathbf{y})\), KDM queriers \((f_{0},f_{1},i)\), \(\beta\in\{0,1\}\), where \(i\in[l]\) and \(f_{0}\), \(f_{1}\in F_{aff}\), we let message \(\mu=f_{\beta}(\mathbf{sk}_{1},\cdots,\mathbf{sk}_{l})\), and encrypted \(\mu\) under identity \(u_{i}\). Then, we responded to the adversary with ciphertext \(\mathbf{C}=(c_{1},c_{2})\), where  
\[c_{1}^{t}=\mathbf{s}^{t}\bigg{[}\overset{\to}{u_{i}}\cdot\mathbf{A}\bigg{|} \overset{\to}{u_{i}}\cdot\overset{\sim}{\mathbf{A}}\bigg{]}+\bigg{[}\Big{(} \mathbf{e}^{(1)}\Big{)}^{t}\bigg{|}\Big{(}\mathbf{e}^{(2)}\Big{)}^{t}\bigg{]},\ c_{2}= \mathbf{s}^{t}\bigg{[}\overset{\to}{u_{i}}\cdot\mathbf{y}\bigg{]}+e^{\prime}+ \mu\cdot m\]  
\(\mathbf{G}_{1}\): In \(\mathbf{G}_{1}\), the parameters are the same as \(\mathbf{G}_{0}\). \(\Box\)  
For master public key \(\text{MPK}=(\mathbf{A},\overset{\sim}{\mathbf{A}},\mathbf{y})\), KDM queries \((g_{0},g_{1},i)\), \(\beta\in\{0,1\}\), where \(i\in[l]\) and \(g_{0}\), \(g_{1}\in G_{poly}\), we let message \(\mu=g_{\beta}(\mathbf{sk}_{1},\cdots,\mathbf{sk}_{l})\), and encrypted \(\mu\) under identity \(u_{i}\). First, we invoke \(Sim\big{(}\mu=g_{\beta}(\mathbf{sk}_{1},\cdots,\mathbf{sk}_{l})\big{)}=\mu^{\prime}= \hat{f}_{\beta}(\mathbf{sk}_{1},\cdots,\mathbf{sk}_{l};r)\). When \(r\) is determined, \(\hat{f}_{\beta}\in F_{aff}\). Then, we responded to the adversary with ciphertext \(\mathbf{C}=(c_{1},c_{2})\), where  
\[c_{1}^{t}=\mathbf{s}^{t}\bigg{[}\overset{\to}{u_{i}}\cdot\mathbf{A}\bigg{|} \overset{\to}{u_{i}}\cdot\overset{\sim}{\mathbf{A}}\bigg{]}+\bigg{[}\Big{(} \mathbf{e}^{(1)}\Big{)}^{t}\bigg{|}\Big{(}\mathbf{e}^{(2)}\Big{)}^{t}\bigg{]}\]  
Despite the differing encrypted messages in \(\mathbf{G}_{0}\) and \(\mathbf{G}_{1}\), the ciphertext remains statistically indistinguishable. This is because both games employ the cryptographic scheme derived from \(\mathbf{G}_{0}\), and \(\mathbf{G}_{0}\) is proven to be KDM-CPA security; therefore, it guarantees the indistinguishability of the ciphertext. Finally, our focus shifts to ensuring the security of the message transformation process between \(\mu\) and \(\mu^{\prime}\) in \(\mathbf{G}_{1}\). The security of the transformation process depends on the security of the randomized encoding of functions technology. This technology is used in many cryptographic fields, and its security has also been proven in many papers. The detailed proof process can be found in [21; 22; 23]. The challenge function ensemble has successfully expanded from the affine function ensemble of the basic scheme to the polynomial function ensemble. Theoretically, randomized encoding of functions technology can be used to encode arbitrary functions in terms of affine functions. This means that our full KDM-IBE scheme can be used to encrypt and decrypt messages that are arbitrary functions. However, the efficiency of this approach may depend on the complexity of the original function and the accuracy of the encoding process. In practice, there may be limits to the complexity of the functions that can be encoded and efficiently encrypted using this scheme.