## 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 deﬁne 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

satisﬁes the security under the decisional Diﬃe-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 deﬁnition of leaking the randomness is diﬀerentfrom 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 deﬁne the security notions of public-key encryption in the presence of
the leakage of the randomness used in the encryption algorithm. The deﬁnitions
are similar to those of the secret-key leakage introduced in [1, 11]. We deﬁne 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 theﬁrst 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 deﬁne 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 Diﬃe-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 ﬁrstscheme 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 ﬁrst 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 identiﬁcation, 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 diﬀerent 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*), where

*sk *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, deﬁnitions, 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 Diﬃe-Hellman Assumption**
Let

*G*(1

*n*) be a group sampling algorithm which, on input 1

*n*, 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 of

*G*.

The decisional Diﬃe-Hellman (DDH) assumption is that the ensembles

*{*(G

*, g*1

*, g*2

*, gr, gr*)

*}*
*n∈*N and

*{*(G

*, g*1

*, g*2

*, gr*1
tinguishable, where G

*← G*(1

*n*), the elements

*g*1

*, g*2 are randomly selected gener-ator of

*G*, and

*r, r*1

*, r*2

*∈ *Z

*p *are chosen independently and uniformly at random.

**Randomness Extraction**
The

*statistical distance *between two random variables

*X *and

*Y *over a ﬁnite
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(max

*x *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 *deﬁned 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 *2

*r 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 deﬁnition naturally generalizes the standard deﬁnition of strongextractors to the setting of the average min-entropy.

**Deﬁnition 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 eﬃcient 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 deﬁnition of KEM and DEM is as follows:

**Deﬁnition 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 *1

*n, 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(1

*n*)

*and any random string r,*
*where *(

*c, K*)

*← *KEM

*.*Enc(

*pk, r*)

*.*
**Deﬁnition 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 *1

*n, 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 deﬁne 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 ﬁvePPT 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 deﬁne 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 function

*f *:

*{*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

*f*is 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 aﬀect our deﬁnitions of randomness leakage as discussedin [1].

**Deﬁnition 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 = (

*A*1

*, A*2

*, A*3)

*, it holds that*
Advapriori(

*n*) := Pr Exptapriori(0) = 1

*− *Pr Exptapriori(1) = 1

*is negligible in n, where the experiment *Exptapriori(

*b*)

*is deﬁned as follows.*
*1. *(

*pk, sk*)

*← *Gen(1

*n*)

*.*

2. Choose r ← U (

*n*)

*.*

3. st1

*← A*RandLeak(

*r*)(1

*n*)

*.*
*4. *(

*m*0

*, m*1

*, st*2)

*← A*2(

*pk, st*1)

*such that |m*0

*| *=

*|m*1

*|.*

5. c ← Enc(

*pk, mb, r*)

*.*

6. b ← A3(

*c, st*2)

*.*

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 deﬁned as follows.*
Gen

*∗***: ***On input *1

*n, choose s ← Ut*(

*n*)

*, compute *(

*pk, sk*)

*← *Gen(1

*n*)

*, 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(1

*n*), choose

*r ← Uk*(

*n*),

*s ← Ut*(

*n*), and

*z ← Um*(

*n*). Let

*P K *= (

*pk, s*) and

*SK *=

*sk*.

3. (

*m*0

*, m*1

*, st*2)

*← A*2(

*P K, st*1) such that

*|m*0

*| *=

*|m*1

*|*.

4.

*c ← *Enc(

*pk, mb, z*).

5.

*b ← A*3(

*c, st*2).

6. Output

*b *.

From Deﬁnition 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 deﬁne 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 deﬁne the security in a similar way as in Deﬁnition 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

*A*before receiving the challenge ciphertext.

**Deﬁnition 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 = (

*A*1

*, A*2)

*, it holds that*
Advaposteriori(

*n*) := Pr Exptaposteriori(0) = 1

*− *Pr Exptaposteriori(1) = 1

*is negligible in n. The experiment *Exptaposteriori(

*b*)

*is deﬁned as follows:*
*1. *(

*pk, sk*)

*← *Gen(1

*n*)

*.*

2. Choose r ← U (

*n*)

*.*

3. (

*m*0

*, m*1

*, st*1)

*← A*RandLeak(

*r*)(

*pk*)

*such that |m*
*4. c ← *Enc(

*pk, mb, r*)

*.*

5. b ← A2(

*c, st*1)

*.*

6. Output b .
We show that no public-key encryption scheme achieves Deﬁnition 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

*m*0

*, m*1 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, m*1

*, ·*)

*}*. 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

*m*0 and that of

*m*1 are diﬀerent 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 deﬁne 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 deﬁnition 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 eﬃciently 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 that

*A *queries is at most

*λ*(

*n*).

**Deﬁnition 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 *= (

*A*1

*, A*2)

*it holds that,*
AdvRandLeak(

*n*) := Pr[ExptRandLeak(0) = 1]

*− *Pr[ExptRandLeak(1) = 1]

*is negligible in n, where *ExptRandLeak(

*b*)

*is deﬁned as follows.*
*1. *(

*pk, sk*)

*← *KEM

*.*Gen(1

*n*)

*.*
*2. Choose r ∈ R uniformly at random.*

3. (

*c, K*)

*← *KEM

*.*Enc(

*pk, r*)

*.*

4. (

*m*0

*, m*1

*, st*1)

*← A*Leak(

*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

*m*0 and

*m*1. This means the abovedeﬁnition 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 ﬁrst deﬁne 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 eﬃ-ciently computable function whose output length is restricted.

**Deﬁnition 8. ***A*
(KEM

*.*Gen

*, *KEM

*.*Enc

*, *KEM

*.*Dec)
entropically secure against

*λ*(

*n*)-randomness-leakage attack

*if there exists aneﬃciently samplable distribution P K∗ that is computationally indistinguishablefrom the distribution {pk | *(

*pk, sk*)

*← *KEM

*.*Gen(1

*n*)

*}, and*
*H∞*(

*K∗|pk∗, c∗, f*(

*r*))

*≥ κ*(

*n*)

*,*
*where pk∗ ← P K∗, *(

*c∗, K∗*)

*← *KEM

*.*Enc(

*pk∗, r*)

*, and f is an arbitrary eﬃcientlycomputable 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 Deﬁnition 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 deﬁned 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 *= (

*d*1

*, d*2)

*, output*
*M *= Ext(

*K, d*2)

*⊕ d*1

*.*
*Proof (Proof of Theorem 2). *We deﬁne the experiments ExptRandLeak

*∗ *(

*b*) and
(

*b*) for

*b ∈ {*0

*, *1

*} *as follows.

1. Choose

*pk∗ *from

*P K∗*, where

*P K∗ *is the distribution deﬁned in Deﬁnition 8.

2. Choose

*r ∈ R *uniformly at random, where

*R *is the domain of the randomness
3. (

*c∗, K∗*)

*← *KEM

*.*Enc

*∗*(

*pk∗, r*).

4. (

*m*0

*, m*1

*, st*1)

*← A*Leak(

*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 ← A*Leak (

*r *)(

*d, st*
1. Choose

*pk∗ *from

*P K∗*.

2. Choose

*r ∈ R *uniformly at random.

3. (

*c∗, K∗*)

*← *KEM

*.*Enc

*∗*(

*pk∗, r*).

4. (

*m*0

*, m*1

*, st*1)

*← A*
5. Choose

*r ∈ R *uniformly at random.

6. Choose

*r∗ ← Um*, and set

*d *= (

*r∗ ⊕ mb, r *).

7.

*b ← A*Leak (

*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 ﬁrst show an upper bound on the terms (1) and (5). Note that, the
diﬀerence 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(1

*n*)

*} *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 diﬀerence 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 diﬀerence 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 deﬁned as*

follows.
KEM

*.*Gen :

*On input a security parameter *1

*n, choose x*1

*∈ *Z

*p and g*1

*, g*2

*∈ G*
*uniformly at random. Output a pair of keys *(

*pk, sk*)

*as*
*pk *= (

*g*1

*, g*2

*, gx*1

*, gx*1 )

*,*
KEM

*.*Enc :

*On input a public key pk *= (

*g*1

*, g*2

*, pk*1

*, pk*2)

*, choose r*1

*, r*2

*∈ *Z

*p*
*uniformly at random, and output the ciphertext c and the symmetric key Kas*
*c *=

*gr*1

*gr*2

*,*
1)

*r*1 (

*pk*2)

*r*2

*.*
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 *=

*gr*1

*gr*2 ,

*pk*
and

*pk*2 =

*gx*1 , then

*K *= (

*pk*
)

*r*1 (

*gx*1 )

*r*2 = (

*gr*1

*gr*2 )

*x*1 =

*cx*1 .

1)

*r*1 (

*pk*2)

*r*2 = (

*gx*1
Next, we show the security of the scheme.

**Theorem 3. ***The KEM scheme deﬁned 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 that

*P K∗ *is computationally indistinguishable from the distribution

*{pk | pk ←*KEM

*.*Enc(1

*n*)

*}*, 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 eﬃciently-computablefunction whose output length is at most

*λ*(

*n*).

We deﬁne

*P K∗ *as follows.

*P K∗***: **Choose

*x*1

*, x*2

*∈ *Z

*p *with

*x*1 =

*x*2 and

*g*1

*, g*2

*∈ G *uniformly at random.

Then output

*pk∗ *= (

*g*1

*, g*2

*, gx*1

*, gx*2 ).

It follows from the DDH assumption that the distribution

*P K∗ *and the distri-bution

*{pk | pk ← *KEM

*.*Enc(1

*n*)

*} *=

*{*(

*g*1

*, g*2

*, gx*1

*, gx*1)

*| x*
1

*∈ *Z

*p, g*1

*, g*2

*∈ 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

*x*1

*, x*2

*, r*1

*, r*2

*∈ *Z

*p *with

*x*1 =

*x*2 and

*g*1

*, g*2

*∈ G *uniformly at random,

and compute

*c∗ *=

*gr*1

*gr*2 and

*K∗ *= (

*gx*1 )

*r*1 (

*gx*2 )

*r*2 . 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 any

*K∗ ∈ G*, there is a unique pair (

*r*1

*, r*2)

*∈ *Z

*p × *Z

*p *that satisﬁes

*gr*1

*gr*2 =

*c∗*
and (

*gx*1 )

*r*1 (

*gx*2 )

*r*2 =

*K∗*. We can write

*g*
*, c∗ *=

*gy*1 , and

*K∗ *=

*gy*2
for some

*α, y*1

*, y*2

*∈ *Z

*p*. Then it holds that

*c∗ *=

*gy*1 =

*gr*1+

*αr*2 and that

*K∗ *=

*gy*2 =

*gx*1

*r*1+

*αx*2

*r*2 . Hence, we have two equations

*y*
*y*2 =

*x*1

*r*1 +

*αx*2

*r*2. Since

*x*1 =

*x*2 and

*α *= 0 (otherwise,

*g*2 is not a generator of

*G*), there is a unique solution (

*r*1

*, r*2) 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 *1

*n, choose x*1

*∈ *Z

*p and g*1

*, g*2

*∈ G*
*uniformly at random, and output the public key pk *= (

*g*1

*, g*2

*, gx*1

*, gx*1 )

*and*
*the secret key sk *=

*x*1

*.*
KEM

*.*Enc :

*On input a public key pk *= (

*g*1

*, g*2

*, pk*1

*, pk*2)

*, choose r*1

*, r*2

*∈ *Z

*p*
*uniformly at random, and output the ciphertext c *=

*gr*1

*gr*2

*and the symmetric*
*key K *= (

*pk*1)

*r*1 (

*pk*2)

*r*2

*.*
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 *= (

*d*1

*, d*2)

*, output*
*the message M *= Ext(

*K, d*2)

*⊕ d*1

*.*
**Acknowledgments**
This work was supported in part by NTT Information Sharing Platform Labo-ratories and Grant-in-Aid for Scientiﬁc 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 of

*Lecture 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

NHS National Institute for Clinical Excellence Tacrolimus and pimecrolimus for atopic eczema Understanding NICE guidance – information for people with atopic eczema, their families and carers, and the public Information about NICE Technology Appraisal 82 Tacrolimus and pimecrolimus for atopic eczema Understanding NICE guidance – information for people with atopic eczem

Fachausschuss Varizellen der Deutschen Vereinigung zur Bekämpfung der Viruskrankheiten e.V. Druckerei Kempkes, Offset- und Buchdruck GmbH, 35075 GladenbachVarizellen sind eine akute, hochkontagiö-se Viruserkrankung, die weltweit auftritt. Subklinische Infektionen sind selten. Eine tion latent in den spinalen und zentralen Ganglien persistierenden Varicella-Zoster-rone und Satellitenzelle