IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.9 SEPTEMBER 2010

1650

PAPER

Strongly Secure Privacy Amplification Cannot Be Obtained by
Encoder of Slepian-Wolf Code∗Shun WATANABE†a) , Ryutaroh MATSUMOTO††b) , Members, and Tomohiko UYEMATSU††c) , Senior Member

SUMMARY
Privacy amplification is a technique to distill a secret key
from a random variable by a function so that the distilled key and eavesdropper’s random variable are statistically independent. There are threekinds of security criteria for the key distilled by privacy amplification: thenormalized divergence criterion, which is also known as the weak security
criterion, the variational distance criterion, and the divergence criterion,
which is also known as the strong security criterion. As a technique to distill a secret key, it is known that the encoder of a Slepian-Wolf (the source
coding with full side-information at the decoder) code can be used as afunction for privacy amplification if we employ the weak security criterion.
In this paper, we show that the encoder of a Slepian-Wolf code cannot be
used as a function for privacy amplification if we employ the criteria otherthan the weak one.
key words: privacy amplification, secret key agreement, Slepian-Wolf coding, strong security, variational distance, weak security

1.

Introduction

One of the fundamental problems in the cryptography is
the key agreement in which the legitimate parties, usuallyreferred to as Alice and Bob, share a secret key that is
not known by the eavesdropper, usually referred to as Eve.
The problems on the key agreement in the information theory was initiated by Maurer [14], and was also studied by
Ahlswede and Csiszár [1]. In their formulation, Alice, Bob,
and Eve have correlated random variables X n , Y n , and Z n respectively. Then, Alice and Bob generate a secret key from(X n , Y n ) by using the public (authenticated) communication.
Typically, a key agreement protocol consists of two
procedures: information reconciliation [3], [4] and privacy
amplification [2], [3]. The purpose of the information reconciliation for Alice and Bob is to share an identical randomvariable (with high probability) by using the public communication. Privacy amplification is a technique to distill a secret key from the shared random variable by using a function
so that Eve’s knowledge and the secret key are statisticallyindependent. In order to focus on privacy amplification, we
Manuscript received June 15, 2009.
Manuscript revised April 2, 2010.
†
The author is with the Department of Information Science andIntelligent Systems, Tokushima University, Tokushima-shi, 7708506 Japan.
††
The authors are with the Department of Communications andIntegrated Systems, Tokyo Institute of Technology, Tokyo, 1528552 Japan.
∗
A part of this paper was presented at 2009 IEEE International
Symposium on Information Theory in Seoul, Korea.
a) E-mail: shun-wata@is.tokushima-u.ac.jpb) E-mail: ryutaroh@rmatsumoto.orgc) E-mail: uyematsu@ieee.org
DOI: 10.1587/transfun.E93.A.1650

assume that Alice and Bob initially share the random variables X n = Y n in the rest of this paper.
As for the security of the secret key distilled by privacy amplification, there are three kinds of security criteria:
the normalized divergence criterion, which is also known
as the weak security criterion, the variational distance criterion, and the divergence criterion, which is also known
as the strong security criterion. The normalized divergencecriterion requires that the key and Eve’s knowledge Z n is(almost) statistically independent in the sense that the divergence divided by n (normalized divergence), or equivalently
the mutual information divided by n, is negligible. On theother hand, the variational distance criterion and the divergence criterion require that the key and Eve’s knowledge is(almost) statistically independent in the sense that the variational distance and the divergence are negligible respectively.
Traditionally, the normalized divergence criterion was
employed in the study of the key agreement (e.g. [1], [14]).
However, as pointed out by Maurer [15] and independently
by Csiszár [7], Eve might know a large part of the key even if
the key satisfies the normalized divergence criterion. Therefore, we should use the divergence criterion. Indeed, recent
studies on the key agreement employ the divergence criterion (e.g. [9], [19]).
As one of techniques to distill a secret key, it is
known that the encoder of a Slepian-Wolf (the source codingwith full side-information at the decoder) code [26] can beused as a function for privacy amplification. For example,
Ahlswede and Csiszár used this technique implicitly [1], andMuramatsu used this technique explicitly [18].
To describe the technique more precisely, let us consider the Slepian-Wolf code system such that X n is the principal source and Z n is the side-information. Then, the output of the encoder, which is regarded as the key, satisfies
the normalized divergence criterion if the coding rate of thecode is close to the compression limit and the decoding error probability of the code is negligible. However, it has
not been clarified whether this technique can be used for thedivergence criterion.
In this paper, we show that above mentioned techniquecannot be used for the divergence criterion. Actually, √weshow that the divergence grows infinitely in the order of n,which suggests that Eve might know a large part of the key.
In √order to show that the divergence grows in the order of n, the second order converse coding theorem of
the Slepian-Wolf code system (Theorem 4) plays an im-

c 2010 The Institute of Electronics, Information and Communication Engineers
Copyright WATANABE et al.: STRONGLY SECURE PRIVACY AMPLIFICATION CANNOT BE OBTAINED

1651

portant role. The second order source coding (without
side-information) was studied by several authors [12], [13],[22], and Theorem 4 can be regarded as a generalization of
Hayashi’s result [12] to the Slepian-Wolf code system. During the process of the review, Nomura and Matsushima published the result [21] concerning the second order asymptotic of the Slepian-Wolf code system (the source codingwith full side-information at the decoder)† .
The diﬀerence between this paper and [21] is summarized as follows. Since the main purpose of this paper is
to show that Slepian-Wolf codes cannot be used as strongly
secure privacy amplification, we only showed the converse
coding theorem. On the other hand, the main purpose of [21]is to show the second order coding theorem of the SlepianWolf code system, and they showed both the direct and converse parts. Although the independent and identically distributed (i.i.d.) source is exclusively treated in this paper,
the slightly wider class of sources, i.e., the sources such thatthe conditional self-information has an asymptotic normality, is treated in [21]. It should be noted that the approach in[21] is diﬀerent from that in this paper and is similar to theapproach in [22].
Although the divergence criterion is the strongest notion of security among the above mentioned three criteria,some researchers (e.g. [25]) deem that the variational distance criterion is appropriate notion of security because itmatches with the universally composable security [5], which
requires that the actual distribution of the key and Eve’s
knowledge is indistinguishable from the ideal distribution
with which the key is uniformly distributed and independentof Eve’s knowledge. Therefore, it is worthwhile clarifying
whether the key obtained by the above mentioned techniquesatisfies the variational distance criterion or not. In this paper, we show that the key obtained by the technique does notsatisfy the variational distance criterion. Actually, we showthat the variational distance converges to one (the maximum
amount), which means that the actual distribution and theideal distribution are completely distinguishable.
The results in this paper are also interesting from theview point other than privacy amplification. The above mentioned technique can be regarded as the Slepian-Wolf version of the folklore theorem shown by Han [11]. Recently,
Hayashi [12] showed that the folklore theorem does not holdif we employ the variational distance criterion nor the divergence criterion instead of the normalized divergence criterion. Our results can be regarded as a generalization of
Hayashi’s results for the Slepian-Wolf code.
The rest of this paper is organized as follows: In
Sect. 2, we review the basic notations, privacy amplification,and the above mentioned technique. In Sect. 3, we show ourmain results concerning the divergence criterion and their
proofs. In Sect. 4, we show our main results concerning thevariational distance criterion and their proofs. In Sect. 5, weconclude the paper.
Finally, it should be noted that the results on the divergence criterion and the variational distance criterion cannot
be derived from each other, though a weak version of theresult on the divergence criterion, i.e., the fact that the divergence does not converge to zero (Corollary 13), can be derived as a corollary of the results on the variational distancecriterion. The weak version only suggests that Eve mightknow a few bits about the key whose length grows infinitely
as n goes to infinity, which is not a serious problem in practice. On the other hand, the result in Sect. 3 suggests that
Eve’s knowledge about the key also grows infinitely as thelength of the key goes to infinity, which is a serious problem
in practice. Therefore, we need to treat both the divergencecriterion and the variational distance criterion separately.
2.

Preliminaries

2.1 Privacy Amplification
In this section, we review the basic notations related to privacy amplification. Suppose that Alice and Bob have a random variable X n on Xn , and Eve has a random variable Z n on
Zn , where (X n , Z n ) are independently identically distributed(i.i.d.) according to the probability distribution PXZ . In thispaper, we assume that X and Z are finite sets.
Privacy amplification [2], [3] is a technique to distill asecret key S n from X n by using a function
fn : Xn → Mn = {1, . . . , Mn }so that the key and Eve’s information Z n are statistically independent and the key is uniformly distributed on the keyalphabet Mn . The joint probability distribution of the key
and Eve’s information is given by
PS n Z n (s, zn ) =PX n Z n (xn , zn )(1)
xn ∈ fn−1 (s)for (s, zn ) ∈ Mn × Zn , where we defined fn−1 (s) ={xn : fn (xn ) = s}.
For probability distributions P and Q on A, let1
d(P, Q) =|P(a) − Q(a)|
(2)
2 a∈A
= P(B) − Q(B)(3)

be the variational distance (divided by 2) [6], where B ⊂ A
is a set satisfying P(a) ≥ Q(a) for a ∈ B and P(a) ≤ Q(a)for a ∈ A\B. LetP(a)P(a) log
D(P Q) =Q(a)a∈Abe the divergence [6], where we take the base of the logarithm to be e throughout the paper. By using these twoquantities, we introduce three kinds of security criteria on
privacy amplification.
Definition 1 If a sequence of functions { fn } satisfies
†

[20].

The case in which both sources are encoded was published in

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.9 SEPTEMBER 2010

1652

lim

1

n→∞ n

D( fn ) = 0

φn : Xn → Mn

(4)and the decoderforψn : Mn × Zn → Xn ,D( fn ) = D(PS n Z n PUn × PZ n ),then we define privacy amplification by { fn } to be securewith respect to the normalized divergence criterion, where
PUn is the uniform distribution on Mn .
Definition 2 If a sequence of functions { fn } satisfies
lim Δ( fn ) = 0

n→∞

(5)

and we denote the code as Φn = (φn , ψn ). The error probability of the code is defined asε(Φn ) = PX n Z n ({(xn , zn ) : ψn (φn (xn ), zn )  xn }).
For any real number R > 0, the rate R is said to beachievable if there exists a sequence of codes {Φn } that satisfies

forlim supn→∞Δ( fn ) = d(PS n Z n , PU × PZ n ),Definition 3 If a sequence of functions { fn } satisfies
lim D( fn ) = 0,

(6)then we define privacy amplification by { fn } to be securewith respect to the divergence criterion.

We can show that Eq. (6) implies Eq. (5) by using
Pinsker’s inequality [6]. We can also show that Eq. (5) implies Eq. (4) by using [9, Lemma 1].
The security criteria in Definitions 1 and 3 are equivalent to the weak security criterion and the strong security
criterion defined in [16]. The security criterion in Definition 2 is widely used recently (e.g. [25]) because it matcheswith the universally composable security [5], which requiresthat the actual distribution PS n Z n and the ideal distribution
PUn × PZ n are indistinguishable. Although the divergenceis also related to the distinguishability between distributions, the variational distance is directly related to the distinguishability because the optimized average probability of
the correct discrimination is given by1
max [PS Z n (A) + PUn Z n (Ac )]2 A⊂Mn ×Zn n1= [1 + d(PS n Z n , PUn × PZ n )],2(8)Then, we define the compression limit asthen we define privacy amplification by { fn } to be securewith respect to the variational distance criterion.


n→∞

1
log Mn ≤ R and lim ε(Φn ) = 0.
n→∞
n

(7)

which is a straightforward consequence of the definition of
the variational distance [6], where the superscript c designate the complement of the set.
2.2 Privacy Amplification by an Encoder of Slepian-Wolf
CodeIn this section, we explain the Slepian-Wolf code, and thenreview the relation between privacy amplification and the
Slepian-Wolf code. We consider the Slepian-Wolf code system in which X n is the principal source and Z n is the sideinformation. The code system consists of the encoder

R f (X|Z) = inf{R : R is achievable}.
It is well known that the compression limit coincides withthe conditional entropy [26], i.e., R f (X|Z) = H(X|Z).
If a sequence of codes {Φn } satisfies
lim

1

n→∞ n

log Mn = H(X|Z)

(9)

and
lim ε(Φn ) = 0,

n→∞

(10)

then we call the sequence of codes {Φn } compression limit
achieving codes. When {Φn } satisfies Eq. (9), it should be
noted that the error probability depends on the second orMn
. For later use, we present the conder rate √1n log enH(X|Z)
verse coding theorem concerning the tradeoﬀ between theerror probability and the second order rate. The theorem isa Slepian-Wolf coding version of the result on the second
order asymptotic of the source coding [12].
Theorem 4 Let b ∈ R be an arbitrary real number. For any
code sequence {Φn }, if the error probability satisfies
 
b
,
(11)
lim sup ε(Φn ) < 1 − Gσn→∞then the rate satisfies
1
Mn
lim inf √ log nH(X|Z) ≥ b,
n→∞
e
n
where
G(t) =

(12)

 t

1
2
√ e−u /2 du−∞
2π

is the cumulative distribution function of the Gaussian distribution with mean 0 and variance 1, and where we set


1
2
.
(13)
σ = Var log
PX|Z (X|Z)
WATANABE et al.: STRONGLY SECURE PRIVACY AMPLIFICATION CANNOT BE OBTAINED

1653

This theorem is a straight forward consequence of thecentral limit theorem, and we show a proof in Appendix A.
In order to show the relation between privacy amplification and the Slepian-Wolf code, we consider the situationin which Alice and Bob share the principal source X n and
Eve has the side-information Z n . Then, Alice and Bob use
the encoder φn as a function for privacy amplification, andwe regard the output S n = φn (X n ) of the encoder as a secret key. The following proposition states that the encodersof compression limit achieving codes can be used as functions for privacy amplification if we employ the normalized
divergence criterion.
Proposition 5 If a sequence of codes {Φn = (φn , ψn )} satisfies Eqs. (9) and (10), then we have
lim

1

n→∞ n

D(φn ) = 0.
This proposition can be proved almost in a similar manner to [18, Theorem 1]. The proposition can be also dirived
as a special case of Eq. (18) in Remark 7. Note that Proposition 5 can be regarded as the Slepian-Wolf version of thefolklore theorem [11] (see also [10, Theorem 2.6.4]).
3.

Divergence Criterion

3.1 Statement of Result
In this section, we show our main result concerning the divergence criterion, which is proved in Sect. 3.2. In Sect. 2.2,
we showed that the encoders of compression limit achieving
codes can be used as functions for secure privacy amplification in the sense of the normalized divergence criterion. The
following theorem states √that the divergence actually grows
infinitely in the order of n (Eq. (16)), which suggests that
Eve might know a large part of the key.
Theorem 6 Suppose that a sequence of functions, fn :Xn → {1, . . . , Mn } for n = 1, 2, . . ., satisfies Eq. (9), andletThen, we have
 b

σ

−∞

(b − σu)g(u)du,lim sup ε(Φn ) < 1.

(14)

where
1
2
g(u) = √ e−u /22π
is the density function of the Gaussian distribution withmean 0 and variance 1, and where σ2 is the variance definedin Eq. (13).


(15)

n→∞

Then, there exists a real number b ∈ R such that blim sup ε(Φn ) < 1 − G.
σn→∞Since the right hand side of Eq. (14) is an increasing function of b and is positive for any b ∈ R, Theorem 4 and Theorem 6 imply that there exists a constant K > 0 and an integer
n0 such that√D(φn ) ≥ nK
(16)
for every n ≥ n0 .
Remark 7 When the Slepian-Wolf code sequence satisfies
Eq. (9), i.e., the first order rate is equal to the compression
limit, and also satisfies √Eq. (15), we showed above that thedivergence divided by n is lower bounded by a constant
asymptotically,i.e., the divergence grows infinitely in the√order of n. On the other hand, when the first order rateis strictly larger than the compression limit, we can showthat the normalized divergence is lower bounded by a constant asymptotically (Eq. (17)), i.e., the divergence grows infinitely in the order of n. Furthermore, for a given first orderrate, we can show that the lower bound on the normalized
divergence can be achieved by using encoders of SlepianWolf codes (Eq. (18)). It should be noted that Proposition 5
can be derived as a special case of Eq. (18). Equations (17)and (18) are proved in Appendix B.4.
Let fn : Xn → {1, . . . , Mn } for n = 1, 2, . . ., be a sequence of functions (not necessarily encoders of SlepianWolf codes) that satisfies
R = lim inf
n→∞1
log Mn > H(X|Z).
n

Then, the inequality
1
lim inf D( fn ) ≥ R − H(X|Z)
n→∞ n

1
Mn
b = lim inf √ log nH(X|Z) .
n→∞
e
n

1
lim inf √ D( fn ) ≥n→∞n

The theorem can be regarded as a generalization of [12,Theorem 8] for the Slepian-Wolf code.
Suppose that the Slepian-Wolf code sequence {Φn =(φn , ψn )} satisfies Eq. (9) and(17)

implies that the divergence grows infinitely in the order ofn.
Let {Φn = (φn , ψn )} be a sequence of Slepian-Wolf
codes satisfying Eq. (8). Then, we have1
lim sup D(φn ) ≤ R − H(X|Z).
n→∞ n

(18)

Equations (17) and (18) clarify the optimal trade-oﬀ
between the (first order) rate of the secret key and the normalized divergence. Equation (18) also states that the optimal trade-oﬀ can be achieved by encoders of Slepian-Wolf
codes. Evaluation of the trade-oﬀ between the so-called

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.9 SEPTEMBER 20101654

equivocation rate, which is essentially equivalent to the normalized divergence, and the rate of transmitted message waswell studied in the context of the wire-tap channel in the literatures (e.g. [8], [27]).
and (20), we have the assertion of the lemma.
Proof of Theorem 6
By using Lemma 8, we have1
√ D( fn )n1= √ log Mn − H(S n |Z n )n1≥ √ log Mnn−PX n Z n (xn , zn ) log

3.2 Proof of Theorem 6
In order to show a proof of Theorem 6, we need the following lemma.
Lemma 8 Let

Tn = (xn , zn ) :


1
b
1
−
nH(X|Z)≤.
√ log
PX n |Z n (xn |zn )
σ
σ n

1
P
(xn |zn )(xn ,zn )∈Tncc
− PX n Z n (Tn ){log Mn − log PXn Z n (Tn )}Then, we haveH(S n |Z n )
PX n Z n (xn , zn ) log≤(xn ,zn )∈Tn

+P

Xn Zn

1
PX n |Z n (xn |zn )(xn ,zn )∈Tn11
− nH(X|Z)√ log
PX n |Z n (xn |zn )σ n1+ √ PX n Z n (Tnc ) log PX n Z n (Tnc ).
n
Proof. Let

By taking the limit of both sides and using the central limit
theorem with respect to the cumulative distribution function



1
1
−
nH(X|Z)
≤u ,
Pr
log
√
PX n |Z n (X n |Z n )σ nMn = Mn ∪ Xn ,and let fn : Xn × Zn → Mn be the function defined by
fn (xn ) if (xn , zn )  Tnn n.
fn (x , z ) =xn
if (xn , zn ) ∈ Tn

we have

We set the random variable S n = fn (X n , Z n ). Then, we have1
lim inf √ D( fn )
n→∞
n
 
 b
σ
b
ug(u)du
≥ bG
−σ
σ
−∞
 b
σ
=
(b − σu)g(u)du,n(xn ,zn )∈Tn

+(s,zn )∈Mn ×Zn

1
PX n |Z n (xn |zn )PS n Z n (s, zn ) log

1.
PS n |Z n (s|zn )

−∞

(19)
By using the log-sum inequality [6], we can upperbound the last term in Eq. (19) asPZ n (zn )PS n Z n (s, zn ) log
PS n Z n (s, zn )(s,zn )∈M ×Znn≤ PX n Z n (Tnc )[log Mn − log PX n Z n (Tnc )].

X n |Z n

Mn
1= PX n Z n (Tn ) √ log nH(X|Z)
en
−σPX n Z n (xn , zn )(Tnc )[log Mn − log PX n Z n (Tnc )].

H(S n |Z )

PX n Z n (xn , zn ) log
=



(20)

Let fn : Mn → Mn be the function defined bys
if s ∈ Mn.
fn (s) =fn (s) if s ∈ Xn
Then, we have S n = fn (S n ). Since the conditional entropy
does not increase by a function [6], by combining Eqs. (19)which completes the proof
4.



Variational Distance Criterion

4.1 Statement of Results
In this section, we show our main results concerning thevariational distance criterion, which are proved in Sects. 4.2
and 4.3. First, we define the quantity δ(PX n Z n ) as follows.
Definition 9 Let 1 ≤ Mn ≤ |X|n be an integer, and Cn ={Czn }zn ∈Zn be a family of sets such that each Czn ⊂ Xn satisfies |Czn | = Mn , where |A| means the cardinality of a set A.
We define the distribution PCn on Xn × Zn as

WATANABE et al.: STRONGLY SECURE PRIVACY AMPLIFICATION CANNOT BE OBTAINED

1655


PCn (xn , zn ) =1nn
Mn PZ (z )0if xn ∈ Czn.
else

provided that σ2 > 0.

Then, we defineδ(PX n Z n ) = min d(PX n Z n , PCn ),
Cn

(21)

where the minimization is taken over all possible choices of
Cn for arbitrary 1 ≤ Mn ≤ |X|n .

In Sect. 2.2, we showed that the encoders of compression limit achieving codes can be used as functions for secure privacy amplification in the sense of the normalized
divergence criterion. However, the following Theorem 10shows a trade-oﬀ (with some exceptions) between the error
probability ε(Φn ) and the security parameter Δ(φn ) for any
code Φn .
Theorem 10 For arbitrary Slepian-Wolf code Φn(φn , ψn ), we have=ε(Φn ) + Δ(φn ) ≥ δ(PX n Z n ).

The corollary only suggests that Eve might know a few
bits about the long key, which is not a serious problem inpractice. On the other hand, the stronger result suggests that
Eve’s knowledge about the key grows infinitely as the lengthof the key goes to infinity, which is a serious problem inpractice.
Theorems 10 and 11 can be regarded as a generalization of [12, Theorem 4] for the Slepian-Wolf code. Therefore, Theorems 10 and 11 can also interpreted as that the
Slepian-Wolf version of the folklore theorem does not holdfor the variational distance criterion.
Remark 14 For a distribution PXZ with σ = 0, we can easily show that δ(PX n Z n ) = 0 for any n by taking Czn as thesupport of PX n |Z n (xn |zn ).
Remark 15 It should be noted that Theorem 10 holds not
only for i.i.d. random variables (X n , Z n ), but also for any(X n , Z n ).

Theorem 11 If the variance σ2 defined in Eq. (13) is positive, then we havelim δ(PX n Z n ) = 1.

n→∞

(22)


The combination of Theorems 10 and 11 states that wecannot use the encoders of any (good) Slepian-Wolf codes
as functions for secure privacy amplification if we employ
the variational distance criterion.
Corollary 12 For arbitrary Slepian-Wolf code Φn(φn , ψn ), if=n→∞then we havelim Δ(φn ) = 1n→∞From Eq. (7), Corollary 12 means that the actual distribution PS n Z n and the ideal distribution PUn × PZ n are completely distinguishable asymptotically.
The combination of Pinsker’s inequality and Corollary
12 implies the following corollary, which states that the keys
obtained by the encoders of any (good) Slepian-Wolf codes
do not satisfy the divergence criterion, although we haveshown stronger result (Theorem 6) in Sect. 3.
Corollary 13 For any sequence of Slepian-Wolf codes{Φn = (φn , ψn )} such that limn→∞ ε(Φn ) = 0, we have
lim inf D(φn ) ≥
n→∞

2
ln 2

Before we show a proof of Theorem 10, we introduce thefollowing lemma.
Lemma 16 For arbitrary code Φn = (φn , ψn ), there exists a
code Φn = (φn , ψn ) that satisfiesε(Φn ) ≤ ε(Φn )(23)φn (ψn (s, zn )) = s ∀(s, zn ) ∈ Mn × Zn .

(24)

and



lim ε(Φn ) = 0,

provided that σ2 > 0.

4.2 Proof of Theorem 10

Proof.
We construct a decoder ψn as follows. If
φn (ψn (s, zn ))  s, then we set ψn (s, zn ) = x̃n for arbitrarilynnchosen x̃n ∈ φ−1n (s). Otherwise, we set ψn (s, z ) = ψn (s, z ).
From the construction of this decoder, it is obvious that thecode Φn = (φn , ψn ) satisfies Eqs. (23) and (24).
Proof of Theorem 10
From Lemma 16, it suﬃces to prove Theorem 10 forcodes satisfying Eq. (24). Therefore, we assume that a code
Φn satisfies Eq. (24) in the rest of this section.
By using the decoder ψn , we construct the map
ψn (s, zn ) = (ψn (s, zn ), zn ).

(25)

Since the decoder satisfies the condition in Eq. (24), ψn is aninjection map from Mn × Zn into Xn × Zn .
For the extended code Φn = (φn , ψn ), we define theerror probabilityε(Φn ) = PX n Z n ({(xn , zn ) : ψn (φn (xn ), zn )  (xn , zn )}).

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.9 SEPTEMBER 2010

1656

Obviously, we have ε(Φn ) = ε(Φn ).
Next, we define the distribution PUn × PZ n , which is theembedding of PUn × PZ n into Xn × Zn , as follows:δ(PX n Z n )⎡1 ⎢⎢⎢⎢ = ⎢⎢⎣|PX n Z n (xn , zn ) − PCn (xn , zn )|2 (xn ,zn )∈A++|PX n Z n (xn , zn ) − PCn (xn , zn )|−1

PUn × PZ n (xn , zn ) = PUn × PZ n (ψn (xn , zn ))for (xn , zn ) ∈ ψn (Mn × Zn ), and PUn × PZ n (xn , zn ) = 0 forother (xn , zn ). Similarly, we define the distribution PS n Z n ,which is the embedding of PS n Z n into Xn × Zn .
Since the decoder ψn satisfies Eq. (24), we have
PX n Z n (xn , zn ) ≤PX n Z n ( x̃n , zn )(xn ,zn )∈A− ∩Cn++(xn ,zn )∈A0(26)d(PX n Z n , PS n Z n )= PX n Z n ((Xn × Zn )\ψn (Mn × Zn )).

where, at the inequality, we used the relation|P(a) − Q(a)|a∈B√

PCn (A+ ) ≤ e−b n ,Finally, from the definition of δ(PX n Z n ) and the triangular inequality, we haveδ(PX n Z n ) ≤ d(PX n Z n , PUn × PZ n )PX n Z n (A− ∩ Cn ) ≤ e
and≤ d(PX n Z n , PS n Z n )+d(PS n Z n , PUn × PZ n )= ε(Φn ) + Δ(φn ),

4.3 Proof of Theorem 112b
2C1  ρ 3,
PX n Z n (A0 ) ≤ √
+ √
n σ
2πσ

(30)

(31)

n→∞

b→0

n→∞

PX n Z n (A− ∩ Cn ) + PX n Z n (A0 )]= 1.

√
PX n |Z n (xn |zn ) ≤ Mn−1 e−b n },which is the support of PCn .
We bound δ(PX n Z n ) as follows:,≥ 1 − lim sup lim sup[PCn (A+ ) +A+ = {(xn , zn ) : Mn−1 eb n < PX n |Z n (xn |zn )},{(xn , zn ) : xn ∈ Czn },(29)

lim inf δ(PX n Z n )√zn ∈Zn√−b nwhere C1 is a constant that does not depend on n and ρ isthe third moment of − log PX|Z (X|Z). We will prove theseinequalities in Appendices B.1, B.2, and B.3 respectively.
From Eqs. (29)–(31) and the fact that b > 0 is arbitrary,
we haveLet {Cn } be the sequence of the families such thatd(PX n Z n , PCn ) = δ(PX n Z n ) for each n. For arbitrary positive
constant b > 0, we divide Xn × Zn into the following threesubsets:

Cn =n

for any distributions P and Q on A ⊃ B, and we also used
the facts PCn (A− ∩ Cn ) = PCn (A− ) and PCn (A− \Cn ) = 0.
We use the following inequalities= d(PX n Z n , PS n Z n ).

and A0 = (Xn × Zn )\(A+ ∪ A− ). Letn≥ max[P(B) − Q(B), Q(B) − P(B)]ε(Φn ) = PX n Z n ((Xn × Zn )\ψn (Mn × Zn ))A− = {(xn , zn ) :n= 1 − (PCn (A+ ) + PX n Z n (A− ∩ Cn )+PX n Z n (A0 )),(28)

By using Eq. (28), we can rewrite ε(Φn ) as

which completes the proof of Theorem 10.

⎤⎥⎥⎥|PX n Z n (x , z ) − PCn (x , z )|⎥⎥⎥⎦n+PX n Z n (A− \Cn )+(PCn (A0 ) − PX n Z n (A0 ))](27)

for (xn , zn ) ∈ (Xn × Zn )\ψn (Mn × Zn ). Noting Eqs. (26) and(27) and using Eq. (3), we have1
≥ [(PX n Z n (A+ ) − PCn (A+ ))2+(PCn (A− ) − PX n Z n (A− ∩ Cn ))for (xn , zn ) ∈ ψn (Mn × Zn ), where the equality in Eq. (26)follows from Eq. (1) and the definition of PS n Z n . On the other
hand, we have
PX n Z n (xn , zn ) ≥ PS n Z n (xn , zn ) = 0|PX n Z n (xn , zn ) − PCn (xn , zn )|(xn ,zn )∈A− \Cnnx̃n ∈φ−1n (φn (x ))= PS n Z n (xn , zn )Since the variational distance (divided by 2) is smaller than1, we have the statement of theorem.
5.

Conclusion

In this paper, we showed that the encoders of (good)
Slepian-Wolf codes cannot be used as functions for secure

WATANABE et al.: STRONGLY SECURE PRIVACY AMPLIFICATION CANNOT BE OBTAINED

1657

privacy amplification in the sense of the variational distancecriterion nor the divergence criterion. The consequence ofour results is that we must use privacy amplification notbased on the Slepian-Wolf code (e.g. [2], [9], [16], [24]) if
we want to employ the criteria other than the weak one (thenormalized divergence criterion).
Acknowledgment
The authors would like to thank Dr. Jun Muramatsu forcomments. The first author also would like to thank Prof.
Yasutada Oohama for his support. We also thank the anonymous reviewers for their constructive comments and suggestions. This research is partly supported by the Japan Societyof Promotion of Science under Grants-in-Aid No. 00197137
and by Grant-in-Aid for Young Scientists (Start-up): KAKENHI 21860064.
References[1] R. Ahlswede and I. Csiszár, “Common randomness in information
theory and cryptography — Part I: Secret sharing,” IEEE Trans. Inf.
Theory, vol.39, no.4, pp.1121–1132, July 1993.
[2] C.H. Bennett, G. Brassard, C. Crépeau, and U. Maurer, “Generalized privacy amplification,” IEEE Trans. Inf. Theory, vol.41, no.6,
pp.1915–1923, Nov. 1995.
[3] C.H. Bennett, G. Brassard, and J.M. Robert, “Privacy amplification
by public discussion,” SIAM J. Comput., vol.17, no.2, pp.210–229,
April 1988.
[4] G. Brassard and L. Salvail, “Secret-key reconciliation by public discussion,” Advances in Cryptology — EUROCRYPT’93,
ed. T. Helleseth, Lecture Notes in Computer Science, vol.765,
pp.410–423, Lofthus, Norway, 1994.
[5] R. Canetti, “Universally composable security: A new paradigm for
cryptographic protocols,” Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp.136–145, Oct. 2001.
[6] T.M. Cover and J.A. Thomas, Elements of Information Theory,
2nd ed., John Wiley & Sons, 2006.
[7] I. Csiszár, “Almost independence and secrecy capacity,” Problemsof Information Transmission, vol.32, no.1, pp.40–47, 1996.
[8] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Trans. Inf. Theory, vol.IT-24, no.3, pp.339–348, May
1979.
[9] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,” IEEE Trans. Inf. Theory, vol.50, no.12, pp.3047–3061, Dec.
2004.
[10] T.S. Han, Information-Spectrum Methods in Information Theory,
Springer, 2003.
[11] T.S. Han, “Folklore in source coding: Information-spectrum approach,” IEEE Trans. Inf. Theory, vol.51, no.2, pp.747–753, Feb.
2005.
[12] M. Hayashi, “Second-order asymptotics in fixed-length source coding and intrinsic randomness,” IEEE Trans. Inf. Theory, vol.54,
no.10, pp.4619–4637, Oct. 2008. arXiv:cs/0503089v2[13] I. Kontoyiannis, “Second-order noiseless source coding theorems,”
IEEE Trans. Inf. Theory, vol.43, no.4, pp.1339–1341, July 1997.
[14] U. Maurer, “Secret key agreement by public discussion from common information,” IEEE Trans. Inf. Theory, vol.39, no.3, pp.733–
742, May 1993.
[15] U. Maurer, “The strong secret key rate of discrete random triples,”in Communication and Cryptography — Two Sides of One Tapestry,
pp.271–285, Kluwer Academic Publishers, 1994.
[16] U. Maurer and S. Wolf, “Infromation-theoretic key agreement:

From weak to strong secrecy for free,” Advances in Cryptology —EUROCRYPT 2000, Lecture Notes in Computer Science, vol.1807,
pp.351–368, Springer-Verlag, 2000.
[17] S. Miyake and F. Kanaya, “Coding theorems on correlated generalsources,” IEICE Trans. Fundamentals, vol.E78-A, no.9, pp.1063–
1070, Sept. 1995.
[18] J. Muramatsu, “Secret key agreement from correlated source outputs using low density parity check matrices,” IEICE Trans.
Fundamentals, vol.E89-A, no.7, pp.2036–2046, July 2006.
doi:10.1093/ietfec/e89-a.7.2036[19] M. Naito, S. Watanabe, R. Matsumoto, and T. Uyematsu, “Secretkey agreement by soft-decision of signals in Gaussian Maurer’s
model,” IEICE Trans. Fundamentals, vol.E92-A, no.2, pp.525–534,
Feb. 2008. arXive:0804.2940v1[20] R. Nomura and T. Matsushima, “A note on noiseless separate coding theorems for correlated sources,” Proc. 2009 Shannon Theory
Workshop, pp.41–47, 2009.
[21] R. Nomura and T. Matsushima, “A note on the second order separate source coding theorem for sources with side information,”
Proc. 32nd Symposium on Information Theory and its Applications,pp.637–642, 2009.
[22] R. Nomura, T. Matsushima, and S. Hirasawa, “A note on the overflow probability of lossless codes,” IEICE Trans. Fundamentals,
vol.E90-A, no.12, pp.2965–2970, Dec. 2007.
[23] M.M. Rao and R.J. Swift, Probability Theory with Applications,
2nd ed., Springer, 2005.
[24] R. Renner, Security of Quantum Key Distribution, Ph.D. Thesis,
Dipl. Phys. ETH, Switzerland, Feb. 2005. arXiv:quant-ph/0512258,
also available from International Journal of Quantum Information,
vol.6, no.1, pp.1–127, Feb. 2008.
[25] R. Renner and S. Wolf, “Simple and tight bound for information reconciliation and privacy amplification,” Advances in Cryptology —ASIACRYPT 2005, Lecture Notes in Computer Science, vol.3788,
pp.199–216, Springer-Verlag, 2005.
[26] D. Slepian and J.K. Wolf, “Noiseless coding of correlated information sources,” IEEE Trans. Inf. Theory, vol.IT-19, no.4, pp.471–480,
July 1973.
[27] A.D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol.54,
no.8, pp.1355–1387, 1975.

Appendix A: Proof of Theorem 4
In order to show a proof of Theorem 4, we need the following lemma [17] (see also [10]).
Lemma 17 For any Slepian-Wolf code Φn = (φn , ψn ), wehave
ε(Φn )

≥ PX n Z nlog(xn , zn ) :1≥ αn
PX n |Z n (xn |zn )− Mn e−αn ,where αn is arbitrary real number.



For arbitrarily fixed γ > 0, suppose that there exists a
code sequence {Φn } that satisfies Eq. (11) and1Mn
lim inf √ log nH(X|Z) ≤ b − 2γ.
n→∞enThen, there exists a increasing sequence {ni }∞i=1 such that

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.9 SEPTEMBER 2010

1658

Mni
1
√ log ni H(X|Z) ≤ b − γnie

B.3 Proof of Eq. (31)for every i.
√
By using Lemma 17 for αni = ni b + ni H(X|Z), wehave

To simplify the notation, we introduce the random variable
Wn =ε(Φni )


≥ PX ni Z ni (xni , zni ) :


1
1
−
n
H(X|Z)√ logi
PX ni |Z ni (xni |zni )
σ ni

√
b
≥
− e−γ niσ1Mnlim inf √ log nH(X|Z) > b − 2γ.
n→∞enSince γ > 0 is arbitrary, we have the assertion of the theorem.


≤e

.

From the definitions of PCn and A− , we have
PX n Z n (A− ∩ Cn )
PX n Z n (xn , zn )=(xn ,zn )∈A− ∩Cn=(xn ,zn )∈A− ∩Cn
√
−b n

≤e

.



Hence, we have
PX n Z n (A0 ) ≤(xn ,zn )∈A− ∩Cn

≤

and
Pr

B.2 Proof of Eq. (30)

By using the central limit theorem [23, Corollary 6],
we haveWn − nH(X|Z) log Mn − nH(X|Z) b
<
+
Pr
√
√
σ
σ n
σ n
b
 log Mn −nH(X|Z)


√
+
σ
σ n
C1 ρ 3≤g(u)du + √n σ−∞
Wn − nH(X|Z) log Mn − nH(X|Z) b
<
−
√
√
σ
σ n
σ n
b
 log Mn −nH(X|Z)


√
−
σ
σ n
C1 ρ 3≥g(u)du − √
.
n σ
−∞

(xn ,zn )∈A+
√
−b n

n

PX n Z n (A0 )√√= Pr{log Mn − b n ≤ Wn < log Mn + b n}
log Mn − nH(X|Z) b
−
= Pr
√
σ
σ n
Wn − nH(X|Z)≤√σ nlog Mn − nH(X|Z) b
<
+
√
σ
σ n

Wn − nH(X|Z)
= Pr
√
σ n
log Mn − nH(X|Z) b
<
+
√
σ
σ n

Wn − nH(X|Z)
− Pr
√
σ n
log Mn − nH(X|Z) b
−
<
.
√
σ
σ n

which contradicts Eq. (11). Therefore, if the code sequence{Φn } satisfies Eq. (11), then it satisfies

From the definitions of PCn and A+ , we have1
PCn (A+ ) ≤PZ n (zn )Mnnn(x ,z )∈A+√≤
PX n Z n (xn , zn )e−b n1
PX|Z (Xi |Zi )for (X , Z ) = ((X1 , Z1 ), . . . , (Xn , Zn )). Then, we can rewrite
the left hand side of Eq. (31) as

lim sup ε(Φn ) ≥ lim sup ε(Φni )
n→∞
i→∞
 
b
≥ 1−G
,
σ

B.1 Proof of Eq. (29)

log

i=1
n

for every i. By using the central limit theorem, we have

Appendix B

n


√
1
PZ n (zn )e−b n
Mn√

PCn (xn , zn )e−b n log Mn −nH(X|Z)
√
+b
σ n

σ

log Mn −nH(X|Z) b
√
−σ
σ n

2C1  ρ 3
g(u)du + √.
n σ

Since the interval of the integral is 2b
σ and the height of g(u)is lower than 1, we have Eq. (31).
B.4 Proofs of Eqs. (17) and (18)
Equation (17) is derived by the inequality
D( fn ) = log Mn − H(S n |Z n )WATANABE et al.: STRONGLY SECURE PRIVACY AMPLIFICATION CANNOT BE OBTAINED

1659≥ log Mn − H(X n |Z n )= log Mn − nH(X|Z).
On the other hand, Eq. (18) is derived by the inequality
D(φn ) = log Mn − H(X n |Z n )+[H(X n |Z n ) − H(S n |Z n )]= log Mn − nH(X|Z) + H(X n |S n , Z n )≤ log Mn − nH(X|Z)+nε(Φn ) log |X| + h(ε(Φn )),(A· 1)(A· 2)

where we used the fact that S n is a function of X n in
Eq. (A· 1), we used Fano’s inequality [6] in Eq. (A· 2), andh(·) is the binary entropy function [6].

Shun Watanabe
received the B.E., M.E.,
and Ph.D. degrees from Tokyo Institute of Technology in 2005, 2007, and 2009 respectively.
He is currently an Assistant Professor in the Department of Information Science and Intelligent
Systems of Tokushima University. His current
research interests are in the areas of information
theory, quantum information theory, and quantum cryptography.

Ryutaroh Matsumoto
was born in Nagoya,Japan, on November 29, 1973. He received the
B.E. degree in computer science, the M.E. degree in information processing, and the Ph.D.
degree in electrical and electronic engineering,
all from Tokyo Institute of Technology, Japan,
in 1996, 1998, 2001, respectively. He was an
Assistant Professor from 2001 to 2004, and has
been an Associate Professor since 2004 in the
Department of Communications and Integrated
Systems of Tokyo Institute of Technology. His
research interest includes error-correcting codes, quantum information theory, and communication theory. Dr. Matsumoto received the Young Engineer Award from IEICE and the Ericsson Young Scientist Award from
Ericsson Japan in 2001. He received the Best Paper Awards from IEICE in
2001 and 2008.

Tomohiko Uyematsu
received the B.E.,
M.E. and Dr.Eng. degrees from Tokyo Instituteof Technology in 1982, 1984 and 1988, respectively. From 1984 to 1992, he was with the Department of Electrical and Electronic Engineering of Tokyo Institute of Technology, first as research associate, next as lecturer, and lastly as
associate professor. From 1992 to 1997, he waswith School of Information Science of Japan
Advanced Institute of Science and Technology
as associate professor. Since 1997, he returnedto Tokyo Institute of Technology as associate professor, and currently heis with the Department of Communications and Integrated Systems as professor. In 1992 and 1996, he was a visiting researcher at the Centre National de la Recherche Scientifique, France and Delft University of Technology, Netherlands, respectively. He received the Achievement Award in
2008, and the Best Paper Award in 1993, 1996, 2002 and 2007 both fromIEICE. His current research interests are in the areas of information theory, especially Shannon theory and multi-terminal information theory. Dr.
Uyematsu is a senior member of IEEE.