# Efficient Lattice-Based Cryptosystems with Key Dependent Message Security
###### Abstract  
Key-dependent message (KDM) security is of great research significance, to better analyse and solve the potential security problems in complex application scenarios. Most of the current KDM security schemes are based on traditional hard mathematical problems, where the public key and ciphertext are not compact enough, and make the ciphertext size grow linearly with the degree of the challenge functions. To solve the above problems and the inefficient ciphertext operation, the authors propose a compact lattice-based cryptosystem with a variant of the RLWE problem, which applies an invertible technique to obtain the RLWE\({  
Similarly, the ACPS scheme has post-quantum security and its challenge functions are affine functions. At Crypto 2010, [PERSON] and [PERSON] et al. [9] extended the technique in [7] and proposed further construction of KDM-secure schemes, so that the security of the scheme could be based on more mathematically hard problems, mainly the QR (Quadratic Residuosity) problem [10] and the DCR (Decisional Composite Residuosity) problem [11]. The KDM security of this scheme can be attributed to the indecipherable (IND) security. However, the encryption method in [9] is similar to the circular security assumption which encrypts the message in bit. Therefore, the KDM-secure scheme constructed according to the above method has the disadvantages of not being compact as well as inefficient encryption and decryption. At Eurocrypt 2010, under the standard model and standard assumption, [PERSON] et al. [12] constructed a KDM-CPA secure scheme based on the DDH or LWE assumption. For arbitrary but fixed polynomials \(L\) and \(N\), given the size of the secret key \(k\), the adversary can attack at most \(N(k)\) public keys and a circuit of size \(L(k)\), namely, the set of challenge functions contains a Boolean circuit with polynomial size. Therefore, it is also known as a bounded KDM-secure scheme, which is inefficient and the ciphertext includes a garbled circuit of the same size as its set of challenge functions. In 2011, [PERSON], [PERSON] et al. [13] proposed a KDM-secure public key encryption scheme with respect to polynomial functions with a degree less than \(d\), where \(d\) is a constant. The KDM-CPA security follows from the DDH or LWE assumption. Since the construction of the scheme still follows the construction of [7], the ciphertext is not compact enough and the ciphertext size is an exponential function related to \(d\). In the same year, [PERSON] et al. [14] proposed a public key encryption scheme based on the DCR assumption with KDM-CPA security. The ciphertext size is a linear function related to \(d\), which improves the efficiency of the above scheme. With an increase of application scenarios, the KDM-secure encryption scheme also has a significant role in identity authentication. Under the LWE assumption, [PERSON] et al. [15] proposed the first identity-based encryption scheme with KDM security, where the challenger can answer encryption queries with respect to affine functions. In 2019, [PERSON] et al. [16] focused on the KDM security of an identity-based encryption scheme, proposing a generic way to reach it from public key encryption, so that it remained KDM secure. Most of the discussed schemes directly encrypt the secret key, but in practice, the set of challenge functions may be composed of the secret key in more complex forms. At Asiacrypt 2020, [PERSON] et al. [17] proved an encryption scheme with circular security that can be transformed into a KDM-secure encryption scheme, in which circular security is the most basic form of KDM security, that is, it can securely encrypt a secret key in bit. Therefore, the question of how to face more complex encryption scenarios, as well as constructing compact ciphertext, is worth intensive study. Motivation.