1. Introduction
With the rise of cloud computing and cloud storage technology, some application scenarios also need to encrypt the secret key and its related information. In 1984, Goldwasser and Michali [
1] first introduced the concept of key-dependent message security, which ensures the security of message
directly calculated from the secret key
. The KDM (Key-dependent message)-secure public key encryption scheme was originally applied to the hard disk encryption process, and the secret key and user’s data were encrypted together. Later, it has also been widely used in formal proof [
2,
3], homomorphic encryption [
4] and some advanced cryptographic protocols [
5].
At Eurocrypt 2001, Camenisch and Lysyanskaya [
5] presented a circular-secure encryption scheme of provable security under the random oracle model, and the KDM attack capability of the adversary is defined by the set of challenge functions that can be queried. In 2002, Black, Rogaway and Shrimp-ton [
6] considered such a situation, that is, in the application process of hard disk encryption, an adversary was allowed to obtain a ciphertext, which was encrypted by the secret key
related function
of the user
under the public key
. Compared with semantic security, the KDM security model has stronger security and a higher research value, which mainly depends on its efficiency and the set of challenge functions that can be queried. However, various KDM-secure public key encryption schemes are different in construction. Until 2008, Boneh et al. [
7] proposed a public key encryption scheme based on the DDH (decisional Diffie–Hellman) assumption, and proved the KDM-CPA (Chosen Plaintext Attack) security of the scheme under the standard model. After that, Applebaum et al. [
8] proposed the first lattice-based public key encryption scheme of KDM-CPA security, which was named the ACPS scheme. The security follows from the LWE (Learning with Error) assumption, because of its good linear structure, and has compact ciphertexts and a high level of computational efficiency. Similarly, the ACPS scheme has post-quantum security and its challenge functions are affine functions.
At Crypto 2010, Brakerski and Goldwasser 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, Barakerski et al. [
12] constructed a KDM-CPA secure scheme based on the DDH or LWE assumption. For arbitrary but fixed polynomials
and
, given the size of the secret key
, the adversary can attack at most
public keys and a circuit of size
, 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, Brakerski, Goldwasser et al. [
13] proposed a KDM-secure public key encryption scheme with respect to polynomial functions with a degree less than
, where
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
. In the same year, Malkin 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
, 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, Peikert 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, Chen 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, Kitagawa 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. Through the above comparison, we can observe three urgent problems in KDM-secure public key encryption schemes: (1) how to securely encrypt the complex functions of the secret key (not only itself); (2) how to construct the public-key encryption scheme with compact ciphertexts, and independent of the challenge functions, and (3) The existing compact cryptosystems are all based on lattice problems. A question is raised of how to modify the LWE problem to improve the efficiency of encryption and decryption.
Our Results. In this paper, we analyse the KDM security of the public-key encryption scheme, and choose to use the RLWE (Ring-Learning with error) problem to build the compact cryptosystems. First, we apply the invertible technique [
18] to obtain the
problem, then provide a new version by scaling the noise, and proving that it remains hard after the above modification. After that, we give a useful transformation to obtain the
assumption-Hermite normal form (HNF), namely, the secret chooses form error distribution. As it happens, through noise scaling, the secret key just fits into the message space
, so our scheme can securely encrypt the linear functions of its secret key. Therefore, we easily construct a compact public-key scheme, analyze its correctness, and prove its key-dependent message security under the
assumption.
In particular, through the proof of KDM-CPA security, we observe that the ciphertexts are pseudorandom with encrypting the secret key directly. If we do not expand the message space by scaling the noise, then it is possible to construct a symmetric-key scheme for KDM security by directly encrypting the secret key to its linear functions. Therefore, we further improve the problem, propose its variant - problem, and demonstrate its hardness. For the message space , given a small enough Hamming weight and making large enough, we can obtain a binary secret symmetric-key scheme with less ciphertext noise. Finally, we prove that our scheme is KDM-CPA secure under the special - assumption and the cost of encryption and decryption is only bit operations per message symbol.
Organization. In
Section 2, we describe some important lemmas and give the formal definition of KDM-secure cryptosystems. In
Section 3, we first introduce the
problem and a HNF (Hermite normal form) transformation, then construct a compact public-key scheme with KDM-CPA security. In
Section 4, similarly to the previous section, the variant
-
problem and symmetric-key scheme are presented. In
Section 5, we provide a detailed performance comparison. Finally, the conclusion is given in
Section 6.
2. Preliminaries
2.1. Basic Notation
In this paper, we use the following notation and lemmas. We will use a ring . In our concrete instantiations, we prefer to use either (the integers) or the polynomial ring , where is a power of 2. For integer , we use to denote . Sometimes we will use abuse notation and use to denote the set of -elements with binary coefficients, when , may denote , and when is a polynomial ring, may denote those polynomials that have coefficients. For , we use the notation to refer to mod , with coefficients reduced into the range .
For the security parameter , denote a negligible function . For some distribution , writing means that is distributed according to , the error distribution is the discrete gaussian distribution for some . The usual norm over the reals equals . The norm is defined as .
Lemma 1. (see [
19]).
Let . For any real number , we have Lemma 2. (see [
20]).
Let . For any real number ,and any , the statistical distance between the distributions and is at most .
Lemma 3. (see [
21]).
Let .
, and let and let . For any , and .
2.2. The RLWE Problem
This simple version of the RLWE problem comes from [
22], and the LWE problem can choose the secret from the noise distribution by the transformation
.
Definition 1. (RLWE). For security parameter , let f(x) = xd + 1 where is a power of . Let be an integer. Let and let . Let be a distribution over . The problem is to distinguish the following two distributions: In the first distribution, one samples uniformly from . In the second distribution, one first draws uniformly and then samples by sampling uniformly, and setting , let this distribution be . The assumption is that the problem is infeasible.
Lemma 4. (see [
8]).
Let be a prime power. There is a deterministic polynomial-time transformation that, for arbitrary and error distribution , maps to where , and maps to itself. The transformation also produces an invertible square matrix and that, when mapping to , satisfy .
Theorem 1. (see [
23]).
Let be the th cyclotomic number field having dimension and be its ring of integers. Let , and let , be a -bounded prime such that .
Then there is a polynomial-time quantum reduction from -approximate SIVP (
or SVP)
on ideal lattices in to -. Alternatively, for any , we can replace the target problem by the problem of solving - given only samples, where .
2.3. Key-Dependent Message Security
We now define key-dependent message security by a game played between the challenger and the adversary , and KDM security guarantees the direct encryption of the secret key and its correlation function . The KDM attack capability of the adversary is mainly determined by the collection of secret key functions that it can query, expressed as , where and are the secret key space and message space of the encryption scheme. Given public keys and encryption of the key-dependent message , the adversary cannot effectively distinguish it from the ciphertext that is encrypted by the message , and so we can call the scheme KDM-CPA secure with respect to . is a family of sets of functions parameterized by the security parameter and the number of users . The game proceeds as follows:
1. The challenger chooses a bit . Run the scheme’s key generation algorithm times. It gives to the adversary .
2. Adversary
makes encryption queries of the form
, where
and
. To process a query, the challenger computes
, then computes the challenge ciphertexts and returns to the adversary
.
3. Adversary attempts to guess and outputs .
The scheme is KDM-CPA secure if for every probabilistic polynomial-time adversary , the distinguishing advantage . This shows that the scheme can securely encrypt any functions of its own secret key, taking the place of a message.
The KDM-CPA security definition of the symmetric-key scheme is similar. In the first stage, the challenger generates the secret key without giving anything to the adversary . In the second stage, it uses the secret key for encryption (and uses it as the input of ). Everything else is just the same.
3. Compact Public-Key Cryptosystem with KDM Security
In this section, we will describe the construction of a public-key scheme based on the variant of the RLWE problem. At first, we introduce the problem by applying the invertible technique, and then give the new version by scaling the noise. After that, to ensure that the secret chooses form error distribution, a useful transformation is given to obtain the assumption-Hermite normal form. Finally, we construct a compact public-key scheme, analyze its correctness, and prove its key-dependent message security.
3.1. The Invertible Version of RLWE Problem
According to [
18], authors presented a variant of RLWE problem, defined as the
problem. It is similar to the RLWE problem except that
chooses from
, in which
is the ser of invertible elements of
. Therefore, we call
the invertible variant.
problem. For
and error distribution
, we define
as the distribution obtained by sampling the pair
, where
denote the set of invertible elements of
. The Decision
problem is to distinguish between
and
. Please note that for
, [
23] claim that for any
, the fraction of invertible elements in
is at least
. Moreover, ref. [
18] further shows that as long as
, an element choosing from
is invertible with overwhelming probability. Hence, the RLWE problem remains hard even when applying the invertible technique.
Scaling the noise. This technique was first formally proposed in [
24] and generated the
samples as
; security is not affected when
and
are relatively prime, and other parameters are as above.
Definition 2. (Decision ). The average-case decision version of the problem, denoted , is to distinguish the following two distributions with non-negligible advantage: In the first distribution, one samples uniformly from . In the second distribution, one first draws uniformly and then samples by sampling uniformly, where denote the set of invertible elements of , and .
3.2. A Generic Transformation
In this section, we make a useful transformation to sampling . There is no loss of security, and it is ensured that the secret can be placed in the message space. The transformation lemma follows.
Lemma 5. For modulus, arbitraryand the error distribution, there is a deterministic polynomial-time transformation, which mapstowhere, and mapsto itself.
Proof. The transformation
to access the distribution
over , possibly
or . Then, we prove it in two steps.
The first step. Transformation
generates the sample
by drawing from the distribution . When , we have , where .
The second step. To transform samples from
into samples from a different distribution, the sample
from
will be transformed into , where , .
Especially
is uniform due to
being invertible modulo
and
chooses from
. If
, then
is also subject to
. If
D , then
, so we have
where
, therefore,
is subject to
, as desired. □
Definition 3. (The
assumption-Hermite normal form).
As in the previous definition, for all security parameters , the assumption suggests that, for any , we havein which is sampled from the noise distribution , and other parameters remain unchanged. 3.3. Basic -Based Encryption Scheme
For security parameter , let and relatively prime, in which . Let be an error distribution with and ; we sampled from error distribution , so all with overwhelming probability when the secret chooses from error distribution. Let , where and is a power of 2.
: Sample . Output . Sample uniformly, and set , where and denote the set of invertible elements of . Output the public key .
: Notice that , due to the lemma by the noise scaling. Sample . Compute , , output the ciphertext .
: Input the corresponding secret key and ciphertext, then output .
The correctness of the scheme is obvious, compute
, according to the Lemma 3, we have
if
q , where
, the ciphertext can be decrypted correctly.
The KDM-CPA security follows from the assumption by noting the pseudorandom distribution . Observe that , where all choose from error distribution. The ciphertext is indistinguishable from uniform even if is replaced with any linear function of the scheme’s own secret key.
Theorem 2. Letand, where,. Under theassumption, the above cryptosystem RPKE1 aboutsatisfies KDM-CPA security.
Proof. For any probabilistic polynomial-time adversary , we use a three-step hybrid game to prove that the ciphertext with key-dependent message in the RPKE1 scheme is computationally indistinguishable from one that carries no information on the message. Therefore, the distinguishing advantage of the adversary is negligible.
Game: Let
, the remaining parameters are as above, and Hybrid game
is mainly used to generate the challenge ciphertexts.
Game Similar to the hybrid game
, hybrid game
generates the challenge ciphertexts related to
in different ways.
where
,
and
Observe that
,
and
choose from the error distribution
, just like the ciphertext
without scaling the noise, hence
is indistinguishable from
. In addition, observe
, compute
define
, then
. By Lemma 1 and Lemma 2, we have
Let
,
, compute
By Lemma 3,
is statistically indistinguishable from
, it holds that
, and therefore, the challenge ciphertext
is indistinguishable from
. To sum up, the distinguishing advantage between the
and
is negligible, namely
Game: Hybrid game
generates the challenge ciphertext from
when
. Everything else is exactly the same.
where
chooses from
. Observe the hybrid game
,
is indistinguishable from uniform,
just happens to be an instance of the RLWE problem. Therefore,
is pseudorandom, and then
Since the challenge ciphertext
, thus we have
Finally, we conclude that
This proves the KDM-CPA security of the RPKE1 scheme. □
4. Efficient Symmetric-Key Encryption Scheme
The above public-key scheme expands the message space due to the noise scaling, resulting in low efficiency. In this section, we will introduce a KDM secure symmetric-key scheme without scaling the noise. For the symmetric-key scheme, we can generate the following ciphertext by the problem, where . If secret key replaces message , consider the ciphertext , we will have that . If we define , then is an instance of the RLWE problem, so the challenge ciphertext is pseudorandom, and it is easy to prove the KDM security. By way of the above, we can easily extend to any linear function about , just like , where and . Then, we will obtain a challenge ciphertext , therefore, for the sake of convenience, we might wish to define the following problem.
4.1. The Variant of Problem
Definition 4. (-). As in the previous Definition 2, the - problem is to distinguish the following two distributions with non-negligible advantage: In the first distribution, one samples uniformly from . In the second distribution, one samples by sampling uniformly, where , and setting , let this distribution be .
Observe that the - problem, when , is a complete problem. If ,we give a probability polynomial-time reduction to prove that the - problem remains hard, even when is respectively replaced by .
Lemma 6. For any,, and error distribution, there is a probability polynomial-time reduction fromto the-that reduces the advantage by at most.
Proof. Given a sample and a sample from the given oracle, the reduction outputs a new instance .
If samples and are chosen from , then and are uniform in , and is pseudorandom by RLWE problem, the reduction outputs a uniform sample , up to statistical distance .
If sample is chosen from and the distribution of is , then is uniform in , and is pseudorandom, the reduction outputs a uniform sample , up to statistical distance . In addition, a sample from and a sample from are the same as above.
On the other hand, if given samples and from the distribution , the equation . Let , we notice that is exactly a k- instance, the reduction outputs a sample from , up to statistical distance .
To sum up, if the problem is infeasible, then the - problem is also infeasible—namely, is indistinguishable from uniform, as desired. □
After that, we also give the Hermite normal form of the - problem, this modification makes the secret short and useful in the following symmetric-key scheme.
Lemma 7. For modulus, arbitraryand the error distribution, there is a deterministic polynomial-time transformation, which mapstowhere, and mapsto itself.
Definition 5. (The
-
assumption-Hermite normal form).
As in the previous definition 4, for any , the -
assumptionholds that, where sampling , other parameters remain unchanged. 4.2. Symmetric-Key Scheme with KDM Security
As in the previous section, given the security parameter
, let
, and an error distribution
. Let
,
where
and
is a power of 2. We demonstrate a symmetric-key scheme based on the
-
problem. In order to reduce the norm of ciphertext noise, [
25] uses a binary secret
, which shows that the scheme is secure under this optimization, as long as the Hamming weight
is small enough and
is large enough. In the final results, they construct a somewhat homomorphic encryption scheme by setting
,
and
, where
. Therefore, as a symmetric-key scheme, the security is not affected when the results for the RLWE setting continue to the
-
setting.
: Sample . Output as the secret key.
: To encrypt a message , sample uniformly, and set . Output the ciphertext .
: Compute , then output .
According to the encryption algorithm, , compared with the previous public-key encryption scheme, the ciphertext noise is small, that is , namely , then the ciphertext can be decrypted correctly.
The KDM-CPA security is similar to that of
Section 3.3, except that there is no public key. Although the message space is reduced to
, there still exists a linear function
to realize KDM security.
Theorem 3. Sampleuniformly and, where. There exists a linear functionthat makes the RSKE2 scheme satisfy KDM-CPA security, assuming that-is hard.
Proof. The proof of Theorem 2 is similar to RPK1. Therefore, this section gives a brief narrative. First, by replacing , we generate the challenge ciphertext , where and . Observe that , defining and , then we have the challenge ciphertext , which is exactly an instance of the - problem. It means that the challenge ciphertext is pseudorandom, namely the adversary cannot distinguish it from the ciphertext that is encrypted by the message . Therefore, the above RSK2 scheme is KDM-CPA under the - problem. □
5. Performance
In this section, we give a detailed performance comparison between our RPKE1 scheme, RSKE2 scheme and the ACPS scheme [
8]. For the same security parameter
, through the analysis of the ACPS scheme, it is easy to see the difference between the lattice problems on which these schemes are based. Firstly, our scheme has replaced LWE through RLWE, which improves its application efficiency. Secondly, about the noise distribution, in order to obtain the appropriate key-dependent ciphertexts, the ACPS scheme introduces the noise flooding technique (namely,
), which leads to the growth of the modulo
and the decline of efficiency. Due to the problem of quantum reduction of the LWE problem, the standard deviation of the additional noise distribution is
, where
, and
,
,
. As shown in
Table 1, we have the same standard deviation
, but no extra noise distribution
in the ciphertext generation. The
in the hybrid game is irrelevant, because this does not affect the efficiency of the scheme at all. In addition, we also greatly reduce the message space
and the modulo size
, where
. Note the last line, adding the symmetry scheme; ACPS also gave a symmetric-key cryptosystem similar to it. Although different in types, as a variant of RPKE1 it also highlights its advantages.
Finally, we estimate the concrete parameters for our scheme. Compared with ACPS, we have greatly improved its efficiency; the cost of encryption and decryption is only
bit operations per message symbol. By these parameters including modulus
, degree
and error distribution
, we can obtain concrete secret key size, public key and ciphertext size. For example, the public key size of the ACPS scheme is
, the ciphertext size is
and the secret key for ACPS and RPKE1 are
(both
). Performance comparison of ACPS and our scheme are listed in
Table 2. All sizes are in bits.
There are many encryption schemes for KDM security, not only ACPS, but also many schemes based on traditional mathematical problems. However, in terms of computational efficiency, the lattice-based cryptosystems are still safer and more efficient. Additionally, the ciphertext operations mainly consist of encryption and decryption, but other schemes do not have compact ciphertexts. Hence, from the usability perspective, our schemes are superior to previous schemes.