Www2.isit.or.jp

Randomness Leakage in
the KEM/DEM Framework
Hitoshi Namiki1, Keisuke Tanaka2, and Kenji Yasunaga2 Abstract. Recently, there have been many studies on constructing cryp-
tographic primitives that are secure even if some secret information leaks.
In this paper, we consider the problem of constructing public-key en-
cryption schemes that are resilient to leaking the randomness used in the
encryption algorithm. In particular, we consider the case in which public-
key encryption schemes are constructed from the KEM/DEM framework,
and the leakage of randomness in the encryption algorithms of KEM and
DEM occurs independently. For this purpose, we define a new security
notion for KEM. Then we provide a generic construction of a public-key
encryption scheme that is resilient to randomness leakage from any KEM
scheme satisfying this security. Also we construct a KEM scheme that
satisfies the security under the decisional Diffie-Hellman assumption.
Introduction
Recently, many studies have been devoted to construct encryption schemes thatare secure even if some of the secret information leaks [4, 7, 1, 11, 2, 3]. In [4, 7,1, 11, 2], they mainly considered the case of leaking a secret key. In particular,studies in [1, 11, 2] considered the case that any of the secret-key informationleaks, and the restriction is only the amount of the leaked information. Thisleakage model captures many realistic attacks including side-channel attack andcold-boot attack [8]. Naor and Segev [11] also studied the case of leaking the ran-domness used in the key generation algorithm. They proved that their proposedencryption scheme, which is resilient to the secret-key leakage, is also resilientto the leakage of the randomness used in the key generation algorithm.
Bellare et al. [3] considered the case of leaking the randomness used in the encryption algorithm. Their definition of leaking the randomness is differentfrom those of other studies of information leakage. They considered the casethat random strings are sampled from not a uniformly random distribution butan entropically guaranteed distribution.
In this work, we investigate the possibility of constructing public-key en- cryption schemes that are secure even if the randomness information used in theencryption algorithm leaks. The restriction we consider is only the amount ofthe leaked information.
First we define the security notions of public-key encryption in the presence of the leakage of the randomness used in the encryption algorithm. The definitions are similar to those of the secret-key leakage introduced in [1, 11]. We define tworandomness-leakage attacks, a priori randomness-leakage attack and a posteri-ori randomness-leakage attack. In the a priori randomness-leakage attack, theadversary can obtain the leakage information on the randomness before she re-ceives a public key. In the a posteriori randomness-leakage attack, the adversarycan obtain the leakage information after receiving the public key. Then we showthat a secure public-key encryption scheme against a priori randomness-leakageattack can be constructed from any secure public-key encryption scheme. Thisis proved by a similar argument to the case of key leakage in [11]. However, forthe a posteriori randomness-leakage attack, we show that no public-encryptionscheme can achieve the security. This situation is contrast to the case of secret-key leakage. Indeed, it is shown that a secure scheme for key leakage can beconstructed from any hash proof system [11]. The results are summarized inTable 1, in which we compare the results of randomness leakage with that of keyleakage.
Table 1. Comparison between Key Leakage and Randomness Leakage.
After receiving the public key Hash Proof Systems [11] Next, we focus on public-key encryption schemes based on the framework of key-encapsulation mechanism (KEM) and data-encapsulation mechanism(DEM). Since no scheme can achieve the randomness-leakage resilience if theleakage occurs after the adversary receives the public key, we restrict the wayof leakage as follows. (1) The leakage of randomness used in KEM and that inDEM occurs independently, and (2) the leakage of randomness used in DEMoccurs after the adversary selected two challenge messages. The situation of thefirst condition arises when the computation of KEM and that of DEM are im-plemented by two independent computer chips. The second condition is due tosome technical reason. Hence, removing the second condition can be consideredfuture work of this study. Regarding the leakage amount, we restrict the amountof the randomness leakage only for the encryption of KEM, and not for DEM.
Namely, the adversary can learn the entire random bits used in the encryptionof DEM. Note that we allow an encryption algorithm of DEM to be randomized,while it is usually deterministic.
To construct a public-key encryption scheme secure against randomness leak- age attack, we define a new security notion for KEM. We call it the entropicsecurity against randomness-leakage attack. A KEM scheme is entropically se-cure against randomness-leakage attack if there are fake public-keys such thatthe distribution of real public-keys and that of fake public-keys are computa-tionally indistinguishable, and if a fake key is used instead of a real key, the symmetric key has high entropy even if the randomness leakage occurs. Then,we provide a generic construction of a public-key encryption scheme that is re-silient to randomness leakage from any KEM scheme that is entropically secureagainst randomness-leakage attack.
Also we construct a KEM scheme that is entropically secure against randomness-leakage attack under the decisional Diffie-Hellman (DDH) assump-tion. The scheme is a simple variant of the ElGamal KEM scheme.
In Table 2, we summarize the results of information leakage on public-key encryption schemes. Note that the scheme proposed in this work is the firstscheme that achieves the security against randomness leakage after receiving thepublic key.
Table 2. Information Leakage in Public-Key Encryption Schemes.
References Leakage information Assumption Lossy TDF Before receiving the public key Related Work. The key-leakage security in which the adversary can learn any
information on the secret key was first formalized by Akavia, Goldwasser, and
Vaikuntanathan [1]. In addition, they showed that Regev’s lattice-based scheme
is resilient to the key leakage. Naor and Segev [11] extended the notion of [1], and
they proposed a general construction of public-key encryption schemes that are
resilient to key leakage based on universal hash proof systems. In addition, they
applied the notion of leakage to the randomness used in the key-generation algo-
rithm. Alwen, Dodis, and Wichs [2] constructed varieties of key-leakage resilient
public-key cryptosystems, such as identification, signature, and authenticated
key agreement. Recently, Halevi and Lin [9] have studied a realizable security of
public-key encryption schemes in which the leakage occurs after the adversary
receives the ciphertext.
There are several studies related to the leakage of the randomness used in the encryption algorithm. Bellare et al. [3] considered the situation in which therandomness used in the encryption algorithm is not uniformly random, but isentropically guaranteed. They introduced a security notion such that even if therandomness is not chosen uniformly at random, the scheme is secure as long asthe joint distribution of the message and the randomness has high entropy. Notethat the distribution of the randomness is chosen without using the informationon the public key, which is different from the setting of our work.
Kamara and Katz [10] studied another type of randomness leakage in symmetric-key encryption. In their setting, the adversary can control the ran-domness of the ciphertext except that of the challenge ciphertext.
There are other formalization of information leakage. Dizembowski and Pietrzak [7] considered the key leakage under the assumption that only thecomputation leaks information, and constructed leakage-resilient stream-ciphers.
Dodis, Tauman Kalai, and Lovett [6] studied symmetric-key encryption schemesunder key-leakage attack. They considered the leakage of the form f (sk), wheresk is the secret key and f is any exponentially-hard one-way function, and donot restrict the entropy of the secret key.
Preliminaries
In this section, we present notions, definitions, and tools that are used in ourconstructions. Let n be the security parameter on all of the schemes in this paper,and Ut the uniform distribution over {0, 1}t, where t ∈ N. For a distribution X,we write x ← X to indicate that x is chosen according to X. We say an algorithmis PPT if it runs by a probabilistic polynomial-time Turing machine.
The Decisional Diffie-Hellman Assumption
Let G(1n) be a group sampling algorithm which, on input 1n, outputs a tuple of G = (p, G, g) where p is a prime, G is a group of order p, and g is a generator ofG.
The decisional Diffie-Hellman (DDH) assumption is that the ensembles {(G, g1, g2, gr, gr)} n∈N and {(G, g1, g2, gr1 tinguishable, where G ← G(1n), the elements g1, g2 are randomly selected gener-ator of G, and r, r1, r2 ∈ Zp are chosen independently and uniformly at random.
Randomness Extraction
The statistical distance between two random variables X and Y over a finite domain Ω is ∆(X, Y ) := 1 |Pr[X = ω] − Pr[Y = ω]|. We say that two variables are -close if their statistical distance is at most . The min-entropy ofa random variable X is H∞(X) := − log(maxx Pr[X = x]). The min-entropy isa standard notion of entropy used in cryptography since it measures the worstcase predictability of X. We also use the average min-entropy defined as follows: H∞(X|Y ) := − log Ey←Y 2−H∞(X|Y =y) The average min-entropy represents the optimal predictability of X, given knowl-edge of Y . The following lemma was proved by Dodis, Ostrovsky, Reyzin, andSmith [5], which will be used in this paper.
Lemma 1. Let r ∈ R. If Y has 2r possible values and Z is any random variable,
then for a random variable X, ˜
H∞(X|(Y, Z)) ≥ H∞(X|Z) − r. We use a strong randomness extractor as a main tool in our constructions.
The following definition naturally generalizes the standard definition of strongextractors to the setting of the average min-entropy.
Definition 1. A function Ext : {0, 1}k × {0, 1}t → {0, 1}m is an average-case
(n, )-strong extractor if for all the pairs of random variables (X, I) such that
X ∈ {0, 1}k, and ˜
H∞(X|I) ≥ n, it holds that ∆ ((Ext(X, Ut), Ut, I), (Um, Ut, I)) ≤ . Dodis et al. proved the following variant of the leftover hash lemma. Any familyof pairwise independent hash functions is indeed an average-case strong extrac-tor [5].
Lemma 2. Let X, Y
H∞(X|Y ) ≥ k. Let H be a family of pairwise independent hash functions from {0, 1}n to {0, 1}m. Then for h ∈ H chosen uniformly at random, it holds that ∆((Y, h, h(X)), (Y, h, Um)) ≤ as long as m ≤ k − 2 log(1/ ). The KEM/DEM Framework
We present the framework of key-encapsulation mechanism (KEM) and data-encapsulation mechanism (DEM). The KEM/DEM paradigm is a simple way ofconstructing efficient and practical public-key encryption schemes. KEM is usedas public-key encryption used for encrypting a random symmetric key K togetherwith its ciphertext. The symmetric key is used for encrypting the message usingDEM. A formal definition of KEM and DEM is as follows: Definition 2. Key encapsulation mechanism is a tuple of PPT algorithms
KEM = (KEM.Gen, KEM.Enc, KEM.Dec) such that
KEM.Gen : On input a security parameter 1n, output a pair of keys (pk, sk).
KEM.Enc : On input a public key pk and a random string r from some underlying randomness space, output a ciphertext c and a symmetric key K. KEM.Dec : On input a secret key sk and a ciphertext c, output a symmetric key It is required that for any (pk, sk) ← KEM.Gen(1n) and any random string r, where (c, K) ← KEM.Enc(pk, r). Definition 3. Data encapsulation mechanism is a tuple of PPT algorithms
DEM = (DEM.Gen, DEM.Enc, DEM.Dec) such that
DEM.Gen : On input a security parameter 1n, output a symmetric key K.
DEM.Enc : On input a symmetric key K, a message m, and a random string r, DEM.Dec : On input a symmetric key K and a ciphertext c, output a message Note that we define DEM.Enc as a randomized algorithm, while it is usuallydeterministic. We provide a KEM/DEM construction in Section 5 in which theencryption algorithm of DEM is randomized.
In this paper, we only consider the case in which a public-key encryption scheme is constructed from KEM/DEM paradigm. KEM is used for exchanginga symmetric key K. The message is encrypted using DEM with the symmetrickey K. Thus, a public-key encryption scheme can be written as a tuple of fivePPT algorithms (KEM.Gen, KEM.Enc, KEM.Dec, DEM.Enc, DEM.Dec).
Randomness Leakage in Public-Key Encryption
Akavia et al. [1] introduced the security of public-key encryption schemes in the presence of secret-key leakage. We formalize the security in the presence ofrandomness leakage based on their notion. In particular, we consider the leakageof the randomness used in the encryption algorithm.
We define two randomness-leakage attacks, a priori randomness-leakage at- tack and a posteriori randomness-leakage attack. In the a priori randomness-leakage attack, the adversary can have access to the leakage oracle before sheobtains a public key. In the a posteriori randomness-leakage attack, the adversarycan have access to the leakage oracle after she obtains the public key.
A Priori Randomness-Leakage Attack
Let Π = (Gen, Enc, Dec) be a public-key encryption scheme, and (n) the lengthof the randomness used in the encryption algorithm Enc, where n is the securityparameter. The leakage oracle, denoted by RandLeak(r), takes as input a functionf : {0, 1} (n) → {0, 1}∗ and outputs f (r), where r is the randomness used in Enc.
We call the adversary A is an a priori λ(n)-randomness-leakage adversary if thesum of the output length of RandLeak that A queries is at most λ(n), and fis chosen by A before she receives the public key. Note that, although we mayconsider adaptive leakage, in which the adversary can access to the leakage oracleadaptively, it does not affect our definitions of randomness leakage as discussedin [1].
Definition 4. A public-key encryption scheme Π = (Gen, Enc, Dec) is a pri-
ori λ(n)-randomness-leakage resilient if for any PPT a priori λ(n)-randomness-
leakage adversary A = (A1, A2, A3), it holds that
Advapriori(n) := Pr Exptapriori(0) = 1 − Pr Exptapriori(1) = 1 is negligible in n, where the experiment Exptapriori(b) is defined as follows. 1. (pk, sk) ← Gen(1n).
2. Choose r ← U (n).
3. st1 ← ARandLeak(r)(1n). 4. (m0, m1, st2) ← A2(pk, st1) such that |m0| = |m1|.
5. c ← Enc(pk, mb, r).
6. b ← A3(c, st2).
7. Output b . We provide a construction of public-key encryption scheme that is resilient to a priori randomness-leakage attack based on any IND-CPA secure scheme.
The construction is similar to that of [1] for the case of the secret-key leakage.
Construction 5 Let Π = (Gen, Enc, Dec) be a public-key encryption scheme,
(n) the length of the random string used in Enc, and Ext : {0, 1}k(n) × {0, 1}t(n) → {0, 1} (n) an average-case extractor. The scheme Π∗ =(Gen∗, Enc∗, Dec∗) is defined as follows. Gen∗: On input 1n, choose s ← Ut(n), compute (pk, sk) ← Gen(1n), and output
P K = (pk, s) and SK = sk. Enc∗: On input a message m and a public key P K = (pk, s), choose r ← Uk(n)
and output Enc(pk, m, Ext(r, s)). Dec∗: On input a ciphertext c and a secret key SK = sk, output Dec(sk, c).
Theorem 1. Let Π = (Gen, Enc, Dec) be an IND-CPA secure public-key en-
cryption scheme and Ext : {0, 1}k(n) × {0, 1}t(n) → {0, 1}m(n) an average-case
(k(n) − λ(n), (n))-strong extractor for some negligible function (n). Then, the
encryption scheme Π∗ is a priori λ(n)-randomness-leakage resilient.
Proof. We show that for any adversary A, there exists an adversary A such that Advapriori(n) ≤ AdvCPA (n) + 2 (n), where the AdvIND−CPA(n) the advantage of A in the IND-CPA game with Π.
1. (pk, sk) ← Gen(1n), choose r ← Uk(n), s ← Ut(n), and z ← Um(n). Let P K = (pk, s) and SK = sk.
3. (m0, m1, st2) ← A2(P K, st1) such that |m0| = |m1|.
4. c ← Enc(pk, mb, z).
5. b ← A3(c, st2).
6. Output b .
From Definition 4 and the triangle inequality, it follows that Advapriori(n) = Pr Exptapriori(0) = 1 − Pr Exptapriori(1) = 1 ≤ Pr Exptapriori(0) = 1 − Pr Expt (1) = 1 − Pr Exptapriori(1) = 1 . (b) is identical to the experiment Exptapriori(b), except for the fact that Enc uses a truly random input z, not Ext(r, s). Note that, fromLemma 1, given the information of f (r), the average min-entropy of r is at least(k − λ). Therefore the average-case strong extractor guarantees that the statis-tical distance between the view of the adversary in these two experiments is at most (n). This implies that Pr Expt (b) = 1 − Pr Exptapriori (b) = 1 (n) for b ∈ {0, 1}. Since Expt (b) is the same as the IND-CPA experi- ment ExptIND−CPA(b), we can construct the IND-CPA adversary A for which A Posteriori Randomness-Leakage Attack
In this section, we define a posteriori randomness-leakage attack. Consequently,we show that there is no public-key encryption scheme that is a posteriorirandomness-leakage resilient even if the leakage information is only one bit.
We define the security in a similar way as in Definition 4. An adversary A is called a posteriori λ(n)-randomness-leakage adversary if the sum of the outputlengths of RandLeak is at most λ(n), and a leakage function f is chosen by Abefore receiving the challenge ciphertext.
Definition 6. A public-key encryption scheme Π = (Gen, Enc, Dec) is a pos-
teriori λ(n)-randomness-leakage resilient if for any PPT a posteriori λ(n)-
randomness-leakage adversary A = (A1, A2), it holds that
Advaposteriori(n) := Pr Exptaposteriori(0) = 1 − Pr Exptaposteriori(1) = 1 is negligible in n. The experiment Exptaposteriori(b) is defined as follows: 1. (pk, sk) ← Gen(1n).
2. Choose r ← U (n).
3. (m0, m1, st1) ← ARandLeak(r)(pk) such that |m 4. c ← Enc(pk, mb, r).
5. b ← A2(c, st1).
6. Output b . We show that no public-key encryption scheme achieves Definition 6. We con- struct an adversary A that breaks the a posteriori randomness-leakage resilience,where λ(n) = 1. The strategy of A is as follows. First, A makes two challengemessages m0, m1 arbitrary, and randomly chooses 1 ≤ i ≤ d(n), where d(n) isthe maximum length of the possible ciphertexts. Then A asks the leakage oraclewith f (·) = {the i-th bit of the output of Enc(pk, m1, ·)}. After A receives thechallenge ciphertext c, she checks whether the i-th bit of c and f (r) are the sameor not. If they are, she outputs 1, and otherwise outputs 0. There exists at leastone position where the ciphertext of m0 and that of m1 are different becauseof the correctness of the scheme. If i is such a position, then A can correctly predict the challenge message. The probability it occurs is at least 1/d(n), which is a lower bound of the probability Pr Exptaposteriori(0) = 0 . On the other hand, Advaposteriori(n) = Pr Exptaposteriori(0) = 1 − Pr Exptaposteriori(1) = 1 Randomness Leakage in KEM/DEM
In this section, we define randomness-leakage attack for KEM/DEM-basedpublic-key encryption schemes. As discussed in Section 3, there is no public-keyencryption that achieves a posteriori randomness-leakage. Therefore, we restrictthe leakage of randomness such that the leaking of random bits used in KEM.Encand DEM.Enc occur independently. Also when the adversary chooses two chal-lenge messages, she is not allowed to access to the leakage information of randombits in DEM.Enc.
We describe the formal definition of the randomness-leakage attack in KEM/DEM. The randomness-leakage oracle for KEM.Enc, denoted by Leak,takes as input a function f : R → {0, 1}∗ and outputs f (r), where R is thedomain of the randomness used in KEM.Enc and r is the random bits generatedin KEM.Enc. We restrict the function f to be efficiently computable. The leakageoracle for DEM.Enc, denoted by Leak , takes as input a function g : R → {0, 1}∗and output g(r ), where R is the domain of the randomness used in DEM.Encand r is the random bits generated in DEM.Enc. We restrict the amount ofthe leaked bits for r but not for r . Namely, the adversary can learn the entirerandom bits r , which are generated in DEM.Enc. We call an adversary A is aλ(n)-randomness-leakage adversary if the sum of the output length of Leak thatA queries is at most λ(n).
Definition 7. A
(KEM.Gen, KEM.Enc, KEM.Dec, DEM.Enc, DEM.Dec) against λ(n)-randomness-leakage attack if for any PPT λ(n)-randomness-leakage adversary A = (A1, A2) it holds that, AdvRandLeak(n) := Pr[ExptRandLeak(0) = 1] − Pr[ExptRandLeak(1) = 1] is negligible in n, where ExptRandLeak(b) is defined as follows. 1. (pk, sk) ← KEM.Gen(1n). 2. Choose r ∈ R uniformly at random.
3. (c, K) ← KEM.Enc(pk, r).
4. (m0, m1, st1) ← ALeak(r)(pk, c) such that |m 5. Choose r ∈ R uniformly at random.
6. d ← DEM.Enc(mb, K, r ).
7. b ← ALeak (r )(d, st Note that the ciphertext c generated by KEM.Enc is given to the adversary before she submits the challenge messages m0 and m1. This means the abovedefinition captures a stronger security than the standard KEM/DEM framework.
The randomness r in DEM.Enc leaks only after the adversary chose the challengemessages.
(c, K) ← KEM.Enc(pk, r) Fig. 1. Experiment ExptRandLeak(b).
Randomness-Leakage Resilient Schemes from
Entropically-Secure KEM
In this section, we first define a new security notion for KEM. Then, we constructa public-key encryption scheme that is IND-CPA secure against randomness-leakage attack from any KEM scheme satisfying this security.
For a KEM scheme, we require that the symmetric key K still has high average min-entropy even if the adversary knows the public key pk, the cipher-text c, and any partial information f (r) of the random string r. We considera distribution P K∗ that is computationally indistinguishable from the real dis-tribution of pk, where pk is generated from the encryption algorithm of KEM.
Given pk∗ ∈ P K∗, c∗, and f (r), we require that K∗ has enough entropy, where(c∗, K∗) is generated according to KEM.Enc(pk∗, r) and f is an arbitrary effi-ciently computable function whose output length is restricted.
Definition 8. A
(KEM.Gen, KEM.Enc, KEM.Dec) entropically secure against λ(n)-randomness-leakage attack if there exists anefficiently samplable distribution P K∗ that is computationally indistinguishablefrom the distribution {pk | (pk, sk) ← KEM.Gen(1n)}, and H∞(K∗|pk∗, c∗, f(r)) ≥ κ(n), where pk∗ ← P K∗, (c∗, K∗) ← KEM.Enc(pk∗, r), and f is an arbitrary efficientlycomputable function whose output length is at most λ(n). We can construct a public-key encryption scheme secure against randomness- leakage attack from any KEM scheme satisfying Definition 8.
Theorem 2. Let
{0, 1}m be an average- case (κ(n), (n))-strong extractor for some negligible function (KEM.Gen, KEM.Enc, KEM.Dec) be a KEM scheme that is κ(n)-entropicallysecure against λ(n)-randomness-leakage attack. Then, the following schemeΠ∗ = (KEM.Gen∗, KEM.Enc∗, KEM.Dec∗, DEM.Enc∗, DEM.Dec∗) is a public-keyencryption scheme that is IND-CPA secure against λ(n)-randomness-leakage at-tack. Construction 9 The algorithms KEM.Gen∗, KEM.Enc∗, and KEM.Dec∗ are
the same as KEM.Gen, KEM.Enc, and KEM.Dec, respectively. The algorithms
DEM.Enc∗, DEM.Dec∗ are defined as follows.
DEM.Enc∗: On input a symmetric key K and a message M ∈ {0, 1}m, choose
r ∈ {0, 1}t uniformly at random. Output the ciphertext d = (Ext(K, r ) ⊕ M, r ). DEM.Dec∗ On input a symmetric key K and a ciphertext d = (d1, d2), output M = Ext(K, d2) ⊕ d1. Proof (Proof of Theorem 2). We define the experiments ExptRandLeak∗ (b) and (b) for b ∈ {0, 1} as follows.
1. Choose pk∗ from P K∗, where P K∗ is the distribution defined in Definition 8.
2. Choose r ∈ R uniformly at random, where R is the domain of the randomness 3. (c∗, K∗) ← KEM.Enc∗(pk∗, r).
4. (m0, m1, st1) ← ALeak(r)(pk∗, c∗) such that |m 5. Choose r ∈ R uniformly at random, where R is the domain of the random- ness used in DEM.Enc∗.
6. d ← DEM.Enc∗(mb, K∗, r ).
7. b ← ALeak (r )(d, st 1. Choose pk∗ from P K∗.
2. Choose r ∈ R uniformly at random.
3. (c∗, K∗) ← KEM.Enc∗(pk∗, r).
4. (m0, m1, st1) ← A 5. Choose r ∈ R uniformly at random.
6. Choose r∗ ← Um, and set d = (r∗ ⊕ mb, r ).
7. b ← ALeak (r )(d, st Using the triangle inequality, for any adversary A it holds that = Pr[ExptRandLeak(0) = 1] − Pr[ExptRandLeak(1) = 1] ≤ Pr[ExptRandLeak(0) = 1] − Pr[ExptRandLeak∗(0) = 1] + Pr[ExptRandLeak∗ (0) = 1] − Pr[Expt (1) = 1] − Pr[ExptRandLeak∗(1) = 1] + Pr[ExptRandLeak∗ (1) = 1] − Pr[ExptRandLeak(1) = 1] . We first show an upper bound on the terms (1) and (5). Note that, the difference between ExptRandLeak(b) and ExptRandLeak∗ (b) is only the distribu- tion of choosing public keys. Since the distribution P K∗ and {pk | (pk, sk) ←KEM.Gen(1n)} are computationally indistinguishable, there is some negligiblefunction AdvComp(n) that is an upper bound on both (1) and (5).
Second, we show an upper bound on (2) and (4). The difference between (b) and ExptRandLeak∗ (b) is only the mask string for m Ext(K∗, r ) and r∗, respectively. From the assumption of Theorem 2, we have that H∞(K∗|pk∗, c∗, f(r)) ≥ κ(n). Since r is chosen from Ut and Ext is an average-case (κ(n), (n))-strong extractor, the adversary can distinguish the distributionbetween (Ext(K∗, r ), r , pk∗, c∗, f (r)) and (r∗, r , pk∗, c∗, f (r)) with probabilityat most (n). Thus, (n) is an upper bound on both (2) and (4).
Finally, we show the term (3) is equal to zero. The difference between b for b ∈ {0, 1}. Since mb is masked by a uniformly random string r∗, the experiments Expt are the same. Thus, (3) is equal to zero.
Therefore, we have that AdvRandLeak(n) ≤ 2(AdvComp(n) + (n)), which is The Construction of Entropically-Secure KEM
In this section, we provide a construction of entropically secure KEM based onthe DDH assumption.
Construction 10 Let G be a group of prime order p, and λ(n) a leakage pa-
rameter. Then, the KEM scheme (KEM.Gen, KEM.Enc, KEM.Dec) is defined as
follows.
KEM.Gen : On input a security parameter 1n, choose x1 ∈ Zp and g1, g2 ∈ G uniformly at random. Output a pair of keys (pk, sk) as pk = (g1, g2, gx1 , gx1 ), KEM.Enc : On input a public key pk = (g1, g2, pk1, pk2), choose r1, r2 ∈ Zp uniformly at random, and output the ciphertext c and the symmetric key Kas c = gr1 gr2 , 1)r1 (pk2)r2 . KEM.Dec : On inputs a secret key sk and a ciphertext c, output the symmetric The correctness of the scheme immediately follows since if c = gr1 gr2 , pk and pk2 = gx1 , then K = (pk )r1 (gx1 )r2 = (gr1 gr2 )x1 = cx1 .
1)r1 (pk2)r2 = (gx1 Next, we show the security of the scheme.
Theorem 3. The KEM scheme defined in Construction 10 is (log p − λ(n))-
entropically secure against λ(n)-randomness-leakage attack under the DDH as-
sumption.
Proof. We need to show that there exists a distribution P K∗ such thatP K∗ is computationally indistinguishable from the distribution {pk | pk ←KEM.Enc(1n)}, and that ˜ H∞(K∗|pk∗, c∗, f(r∗)) ≥ log p − λ(n), where pk∗ ← P K∗, (c∗, K∗) ← KEM.Enc(pk∗, r), and f is an arbitrary efficiently-computablefunction whose output length is at most λ(n).
We define P K∗ as follows.
P K∗: Choose x1, x2 ∈ Zp with x1 = x2 and g1, g2 ∈ G uniformly at random.
Then output pk∗ = (g1, g2, gx1 , gx2 ).
It follows from the DDH assumption that the distribution P K∗ and the distri-bution {pk | pk ← KEM.Enc(1n)} = {(g1, g2, gx1, gx1) | x 1 ∈ Zp, g1, g2 ∈ G} are H∞(K∗|pk∗, c∗, f(r∗)) ≥ log p − λ(n). If pk∗ is chosen from P K∗, then the distribution {K∗ | (c∗, K∗) ← KEM.Enc(pk∗, r)} is equal to
the following distribution K∗.
K∗: Choose x1, x2, r1, r2 ∈ Zp with x1 = x2 and g1, g2 ∈ G uniformly at random,
and compute c∗ = gr1 gr2 and K∗ = (gx1 )r1 (gx2 )r2 . Then output K∗.
We show that, given pk∗ and c∗, the distribution K∗ is the uniform dis- tribution on G. To prove this fact, we show that, given pk∗ and c∗, for anyK∗ ∈ G, there is a unique pair (r1, r2) ∈ Zp × Zp that satisfies gr1gr2 = c∗ and (gx1 )r1 (gx2 )r2 = K∗. We can write g , c∗ = gy1 , and K∗ = gy2 for some α, y1, y2 ∈ Zp. Then it holds that c∗ = gy1 = gr1+αr2 and that K∗ = gy2 = gx1r1+αx2r2 . Hence, we have two equations y y2 = x1r1 + αx2r2. Since x1 = x2 and α = 0 (otherwise, g2 is not a generator ofG), there is a unique solution (r1, r2) of these equations.
From the above, we have that H∞(K∗|pk∗, c∗) = log p. Then it follows from H∞(K∗|pk∗, c∗, f(r)) ≥ H∞(K∗|pk∗, c∗) − λ(n) = log p − λ(n).
In summary, from Theorems 2 and 3, we can construct a public-key encryp- tion scheme secure against randomness-leakage attack.
Theorem 4. Let G be a group of prime order p, and Ext : G × {0, 1}t →
{0, 1}m an average-case (log p − λ(n), (n))-strong extractor for some negli-gible function (n). Then, the following public-key encryption scheme Π = (KEM.Gen, KEM.Enc, KEM.Dec, DEM.Enc, DEM.Dec) is IND-CPA secure againstλ(n)-randomness-leakage attack under the DDH assumption. KEM.Gen : On input a security parameter 1n, choose x1 ∈ Zp and g1, g2 ∈ G uniformly at random, and output the public key pk = (g1, g2, gx1 , gx1 ) and the secret key sk = x1. KEM.Enc : On input a public key pk = (g1, g2, pk1, pk2), choose r1, r2 ∈ Zp uniformly at random, and output the ciphertext c = gr1 gr2 and the symmetric key K = (pk1)r1 (pk2)r2 . KEM.Dec : On inputs a secret key sk and a ciphertext c, output the symmetric DEM.Enc : On input a symmetric key K and a message M ∈ {0, 1}m, choose r ∈ {0, 1}t uniformly at random, and output the ciphertext d = (Ext(K, r )⊕M, r ). DEM.Dec : On input a symmetric key K and a ciphertext d = (d1, d2), output the message M = Ext(K, d2) ⊕ d1. Acknowledgments
This work was supported in part by NTT Information Sharing Platform Labo-ratories and Grant-in-Aid for Scientific Research.
References
1. A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks.
Cryptography, 6th Theory of Cryptography Conference, TCC 2009, volume 5444 ofLecture Notes in Computer Science, pages 474–495, New York, USA, March 2009.
Springer-Verlag.
2. J. Alwen, Y. Dodis, and D. Wichs. Leakage-resilient public-key cryptography in the bounded-retrieval model. In Advances in Cryptology – CRYPTO 2009, LectureNotes in Computer Science, pages 36–54, Santa Barbara, California, USA, August2009. Springer.
3. M. Bellare, Z. Brakerski, M. Naor, T. Ristenpart, G. Segev, H. Schacham, and S. Yilek. Hedged public-key encryption: How to protect against bad randomness.
In M. Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, volume 5912of Lecture Notes in Computer Science, pages 232–249, Tokyo, Japan, December2009. Springer.
4. R. Canneti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-resilient functions and all-or-nothing transforms. In B. Preneel, editor, Advances in Cryp-tology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science,pages 453–469, Bruges, Belgium, May 2000. Springer-Verlag.
5. Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy extractors: How to gener- ate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97–139, 2008.
6. Y. Dodis, Y. Tauman Kalai, and S. Lovett. On cryptography with auxiliary input.
In M. Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium onTheory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009,pages 621–630. ACM, 2009.
7. S. Dziembowski and K. Pietrzak. Leakage-resilient cryptography. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 293–302, Philadelphia, PA, USA, October 2008. IEEE Computer Society.
8. J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calan- drino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: Coldboot attacks on encryption keys. In USENIX Security Symposium, pages 45–60,2008.
9. S. Halevi and H. Lin. After-the-fact leakage in public-key encryption. In Y. Ishai, editor, TCC, volume 6597 of Lecture Notes in Computer Science, pages 107–124.
Springer, 2011.
10. S. Kamara and J. Katz. How to encrypt with a malicious random number gen- erator. In K. Nyberg, editor, FSE, volume 5086 of Lecture Notes in ComputerScience, pages 303–315, Lausanne, Switzerland, February 2008. Springer-Verlag.
Public-key cryptosystems resilient to key leakage.
Advances in Cryptology – CRYPTO 2009, Lecture Notes in Computer Science,pages 18–35, Santa Barbara, California, USA, August 2009. Springer.

Source: http://www2.isit.or.jp/lab2/member/yasunaga/paper/randleak.pdf