# KDM Security IBE Based on LWE beyond Affine Functions
## 1 Introduction
### Motivation  
The first KDM-IBE scheme was proposed by [PERSON] and [PERSON] et al. [2] in 2012, which was proven to be KDM-CPA-secure under the standard model based on the learning with errors (LWE) assumption. However, the efficiency of the scheme was suboptimal [10], and its challenge function ensemble was limited to the affine functions of the secret key, resulting in a weak security outcome.  
Subsequent works [10; 11; 12; 13; 14; 15] in the literature aimed to improve the KDM-IBE scheme by enhancing its different security attributes, such as selective opening, master key, and adaptive security methods. However, the challenge function ensembles in their schemes were restricted to affine functions. Only [16] was able to achieve a limited number of polynomial functions, and the construction presented in [16] was complex. For further details, see Related Works.  
This represents a major vulnerability factor, as it implies that the existing KDM-IBE schemes cannot maintain the secrecy of the message \(m=f(sk_{1},\cdots,sk_{l})\), in the case where \(f\) is a polynomial function. The security of current KDM-IBE schemes is, therefore, compromised.  
Given this limitation, it is crucial to develop a novel KDM-IBE scheme that can achieve a higher level of security with respect to functions or even arbitrary functions.  
In the context of a KDM-IBE scheme, the security proof and trapdoor function play pivotal roles. However, the existing schemes are limited to affine functions, and it is challenging to propose a universal security proof and trapdoor function that can apply to polynomials of different degrees. At present, no solutions to this problem have been proposed in the literature.  
Therefore, to achieve KDM-IBE security with respect to polynomial functions or even arbitrary functions, it is necessary to address two major obstacles: (1) the need for intricate security proofs and (2) the development of a new suitable trapdoor function.  
_How do we address these two obstacles?_ We do not directly construct the KDM-IBE scheme with respect to polynomial functions, but by using the KDM-IBE scheme with respect to affine functions as a basis.  
We applied the randomized encoding of functions technology to amplify its challenge function ensemble from affine to polynomial functions, or even the arbitrary function, to obtain a new and safer KDM-IBE scheme. The security of our KDM-IBE scheme can be reduced to the basis, thus avoiding intricate security proofs and the construction of new trapdoor functions.  
To enable KDM-IBE with respect to polynomial or even arbitrary functions, the randomized encoding of functions technology was utilized in our scheme.  
1. We use \(f(x)\) to perform the randomized encoding of \(g(x)\), where \(f(x)\) is an affine function and \(g(x)\) is a polynomial function. This encoding step can generate mappings of \(\mathbf{Sim}\) and \(\mathbf{R}\) between \(f(x)\) and \(g(x)\) via \(\mathbf{Sim}\) and \(\mathbf{R}\), such that \(\mathbf{Sim}(g(x))=f(x)\) and \(\mathbf{R}(f(x))=g(x)\).
2. Suppose we can securely encrypt message \(m=f(x)\) (since \(f(x)\) is an affine function, this can be easily implemented).
3. When we want to encrypt message \(m=g(x)\), we can use \(\mathbf{Sim}(g(x))\) to obtain \(f(x)\), then encrypt \(m^{\prime}=f(x)\).
4. When we want to decrypt message \(m=g(x)\), we will decrypt \(m^{\prime}=f(x)\),then use \(\mathbf{R}(f(x))=g(x)\) to obtain the original message \(m=g(x)\).  
This process enables us to use the KDM-IBE scheme with respect to affine functions as a basis and extend it to polynomial functions (or arbitrary functions) through the use of randomized encoding of functions technology.