IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.2 FEBRUARY 2009

525

PAPER

Secret Key Agreement by Soft-Decision of Signals in Gaussian
Maurer’s Model∗
Masashi NAITO†a) , Nonmember, Shun WATANABE††b) , Ryutaroh MATSUMOTO††c) ,and Tomohiko UYEMATSU††d) , Members

SUMMARY
We consider the problem of secret key agreement in Gaussian Maurer’s Model. In Gaussian Maurer’s model, legitimate receivers,
Alice and Bob, and a wire-tapper, Eve, receive signals randomly generated
by a satellite through three independent memoryless Gaussian channels respectively. Then Alice and Bob generate a common secret key from theirreceived signals. In this model, we propose a protocol for generating acommon secret key by using the result of soft-decision of Alice and Bob’s
received signals. Then, we calculate a lower bound on the secret key rate
in our proposed protocol. As a result of comparison with the protocol that
only uses hard-decision, we found that the higher rate is obtained by using
our protocol.
key words: advantage distillation, AWGN, information theoretic security,
key agreement, privacy amplification, public discussion

1.

Introduction

As one of fundamental problems in cryptography, we willconsider the problem of secret key agreement in this paper.
Following the studies on confidential message transmissions
over noisy channels [8], [14], [15], [24], the problem of the
key agreement in the information theory was formulated byMaurer [16] and independently by Ahlswede and Csisźar[1]. They considered the interactive model of secret key
agreement from an initially shared partially secret string bycommunication over a public channel. They also defined thesecret-key rate as the maximum of key rates, which are ratios between the length of shared secret keys and the lengthof the initially shared partially secret string. Then they derived a lower bound and upper bound of the secret-key rate.
As an example of the key agreement, Maurer [16] considered the following model. Two parties, Alice and Bob,
who want to share a secret key, and the wire-tapper, Eve,receive the bits randomly generated by a satellite over independent binary symmetric channels (BSC) respectively. We
call this model Maurer’s model. Maurer [16] proposed an
Manuscript received April 28, 2008.
Manuscript revised September 2, 2008.
†
The author is with the Department of Media Science Graduate
School of Information Science, Nagoya University, Nagoya-shi,
464-8601 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 2008 IEEE International
Symposium on Information Theory in Toronto, Canada.
a) E-mail: m-naito@sp.m.is.nagoya-u.ac.jpb) E-mail: shun-wata@it.ss.titech.ac.jpc) E-mail: ryutaroh@rmatsumoto.orgd) E-mail: uyematsu@ieee.org
DOI: 10.1587/transfun.E92.A.525

interactive key agreement protocol in his model, and showedthat the key generation rate of the interactive protocol can behigher than that of non-interactive key agreement protocols.
More precisely, he showed that the key rate of the interactive protocol can be positive even though the key rates of
non-interactive protocols are 0.
In Maurer’s original model and protocol, channels are
assumed to be BSC, and received signals are assumed to bedigital signals. However, signals in practical channels areanalogue. Recently, the key agreement over wireless channel is experimentally studied by Aono et al. [2]. However,information theoretic analysis of the key agreement overanalogue channels has not suﬃciently conducted. In order toclose the gap between Maurer’s results and the experimental study, we will modify Maurer’s model to use Gaussianchannels instead of BSC, which we call Gaussian Maurer’s
model. Then we analyze key rates of protocols in Gaussian
Maurer’s model. It should be noted that Wolf [22] considered a model in which a satellite sends a random bit to Alice, Bob, and Eve over independent analogue outputs channel (not necessarily Gaussian). By reducing his model to amodel in which Alice and Bob are connected to the satellite with BSCs and Eve is connected to the satellite with abinary symmetric and erasure channel, he showed that thesecret-key rate is positive if the conditional mutual information between Alice and Bob’s received analogue signals
conditioned by Eve’s received analogue signal is positive.
However, the key rate is not calculated explicitly.
In Gaussian Maurer’s model, Alice and Bob can use theresults of soft-decision of analogue received signals. They
can determine the reliability information from this results
and use it for generating a common secret key. In this paper,
we will propose a protocol for secret key agreement using
the reliability information. Then, we calculate key rates atwhich Alice and Bob can agree a secret key in our proposed
protocol. It should be noted that Maurer mentioned that Alice and Bob might be able to utilize the reliability information when they are connected to the satellite with Gaussianchannels [16, Sect. 5]. However, he did not clarify the key
rate of a protocol in which Alice and Bob utilize the reliability information.
Considering the situation that Alice, Bob, and Eve
hard-detect the signals that are sent out by the satellite, Maurer’s original model can be seen as the special case of Gaussian Maurer’s model. Thus, we can compare the protocol in
Gaussian Maurer’s model and one in BSC Maurer’s model.

c 2009 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.2 FEBRUARY 2009

526

In order to show advantage to use reliability information,
we will compare the key rate in our proposed protocol andthe key rate in Maurer’s protocol in which Alice and Bob
use only hard-decision. From the result of this comparison,
we will show that the higher key rate is obtained by using
our proposed protocol than the protocol that only uses harddecision.
In order to derive the key rate at which Alice and Bob
can agree a secret key in our proposed protocol (Theorem 1),
we show two lemmas. Lemma 1 is used to show that Alice’s
key and Bob’s key coincide with high probability. Lemma 2
is used to show that Eve’s knowledge about the key sharedby Alice and Bob is negligible. It should be noted that,during the process of the review, Nascimento et al. published the result [19] similar to Lemma 2. Their result isa generalization of the privacy amplification by Bennett etal. [3] for Eve with continuous random variables. Although
Lemma 2 is also a generalization of the privacy amplification for Eve with continuous random variables, the proof
method of Lemma 2 is diﬀerent from [3], [19]. The proof
of Lemma 2 is based on Lemma 4. Lemma 4 can be considered as a generalization of [11, Lemma 2.1.1] for conditional distributions conditioned by continuous random variables. Lemma 2.1.1 was used to show general formulae ofthe random number generation in the information spectrum
method [11].
Rest of this paper is organized as follows. In Sect. 2,
we will introduce Maurer’s model modified to use Gaussianchannels instead of BSC. In Sect. 3, we will show our proposed protocol using reliability information. In Sect. 4, we
will compare our proposed protocol and Maurer’s protocol
with hard-decision. In appendices, we will prove the lemmas that are needed for the proof of theorem that derives the
key rate at which Alice and Bob can agree a secret key inour proposed protocol.
2.

Secret Key Rate in Gaussian Maurer’s Model

Consider the following key agreement problem, which wecall Gaussian Maurer’s model. Assume that a satellite randomly generates signals and sends it to two parties Aliceand Bob who want to share secret key and the wire-tapper
Eve over three independent memoryless Gaussian channels.
Their noises at time i, denoted NA(i) , NB(i) , and NE(i) , are drawn
from independently identically distributed (i.i.d.) Gaussian distributions with mean 0 and variances VA , VB , andVE respectively. A sequence of signals that the satellite
generates at time 1 to n, denoted U n = [U (1) , . . . , U (n) ],is drawn from a distribution PU n on a signal set in Rn
andthis sequence of signals satisfies power constraint
1 n
(i) 2
n
i=1 (u ) ≤ 1 for all sequences u . Alice, Bob, and
n
n
(1)
(n)
n
Eve receive X = [X , . . . , X ], Y = [Y (1) , . . . , Y (n) ],andZ n = [Z (1) , . . . , Z (n) ], as outputs of these three channels attime 1 to n respectively. They are assumed to know the distribution PU n and noise variances VA , VB , and VE . Note that
capital letters denote random variables and corresponding
small letters denote realizations in this paper.

After Alice, Bob, and Eve receive signals, Alice andBob communicate over a public channel. This channel is assumed to be noiseless and discrete, and its capacity is finite.
Every messages communicated between Alice and Bob can
be intercepted by Eve, but it is assumed that Eve cannot insert fraudulent messages nor modify messages on this publicchannel without being detected. Let C be the entire communication held over this public channel. After enough communication over the public channel, Alice computes a secretkey S on a key alphabet S as a function of her received signals X n and all information C over the public channel. In asimilar way, Bob computes a secret key S  on S as a function of Y n and C. The secret key rate in this model is defined
as follows. Note that we will take all logarithms to be base2, and hence all the entropies will be measured in bits.
Definition 1 For given noise variances VA , VB , and VE , arate R is said to be achievable if for every  > 0 there exists
a protocol for suﬃciently large n satisfying
Pr[S  S  ] ≤ ,

(1)

H(S |CZ ) ≥ log |S| − 

(2)

n

and
1
log |S| ≥ R − ,nwhere |S| denotes the number of the elements in S.
Remark 1 In [1], [16], the security of the key is evaluatedby1
1
H(S |CZ n ) ≥ log |S| − ,nnwhich is called the weak security criteria, instead of Eq. (2),which is called the strong security criteria. Obviously, thestrong security criteria implies the weak security criteria.
For discrete random variables, Maurer and Wolf showed that
if a key rate is achievable for the weak security criteria then
the key rate is also achievable for the strong security criteria
[17].
3.

Secret Key Agreement by Soft-Decision of Signals

In this section, we will propose a protocol that uses reliability information of signals and show the key rate that isachievable by this protocol.
In our proposed protocol, the satellite selects input signal U (i) i.i.d. according to a distribution PU (1) = PU (−1) =
1
(i)
(i)
(i)
2 . Thus, the received signals X , Y , Z are also i.i.d. respectively.
Let a1 , . . . , aK be a positive and monotone increasing
sequence, and let E1 , . . . , E K be sets, where jth level set isdefined as E j = [−a j , a j ] ( j = 1, . . . , K).
The procedures of our proposed protocol is as follows.

NAITO et al.: SECRET KEY AGREEMENT BY SOFT-DECISION OF SIGNALS IN GAUSSIAN MAURER’S MODEL

527

1. From the received signal X (i) at time i, Alice determines
reliability information WA(i) as⎧⎪⎪
0 if X (i) ∈ E1
⎪
⎪
⎪
⎨
(i)
j if X (i) ∈ E cj \E cj+1 ( j = 1, . . . , K) ,WA = ⎪⎪⎪⎪⎪⎩K if X (i) ∈ E c
Kwhere the set E cj is the complement of the set E j in theset of real numbers R, and E cj \E cj+1 = E cj ∩ E j+1 is thediﬀerence set. Similarly, from the received signal Y (i)at time i, Bob determine reliability information WB(i) as⎧⎪⎪
0 if Y (i) ∈ E1
⎪
⎪
⎪
⎨
(i)
j if Y (i) ∈ E cj \E cj+1 ( j = 1, . . . , K) .
WB = ⎪⎪⎪⎪⎪⎩K if Y (i) ∈ E c
K
2. Alice and Bob send sequences WAn = [WA(1) , . . . , WA(n) ]and WBn = [WB(1) , . . . , WB(n) ] over the public channel.
From these messages, they can know the sets containing their received signals.
3. Alice and Bob quantize X n and Y n into discrete randomvariables X̃Δn and ỸΔn , where X̃Δ(i) is defined as⎧⎪⎪⎨1 if X (i) ≥ 0,(i)(3)
X̃Δ = ⎪⎪
⎩0 if X (i) < 0,and ỸΔ(i) is similarly defined as⎧⎪⎪⎨1 if Y (i) ≥ 0,(i)ỸΔ = ⎪⎪
⎩0 if Y (i) < 0.

(4)

For given (WA(i) , WB(i) ) = (wA , wB ), if Eve’s ambiguity
H(X̃Δ |Z, WA = wA , WB = wB ) about X̃Δ(i) is smaller thanBob’s ambiguity H(X̃Δ |Y, WA = wA , WB = wB ) about X̃Δ(i) ,then we should discard X̃Δ(i) in our protocol. Indeed, if wekeep X̃Δ(i) for such (WA(i) , WB(i) ) = (wA , wB ), then a negative
term is added to the lower bound on a secret key rate shownin Eq. (11). Furthermore, if the diﬀerence between Eve andBob’s ambiguity about X̃Δ(i) is smaller than the diﬀerence between Eve’s ambiguity H(ỸΔ |Z, WA = wA , WB = wB ) aboutỸΔ(i) and Alice’s ambiguity H(ỸΔ |X, WA = wA , WB = wB )about ỸΔ(i) , we should generate a secret key from ỸΔ(i) instead of X̃Δ(i) . For this purpose, we consider the sets A, B ⊂{1, . . . , K} × {1, . . . , K}, which are defined as
A = {(wA , wB )|H(X̃Δ |Z, WA = wA , WB = wB )− H(X̃Δ |Y, WA = wA , WB = wB )− H(ỸΔ |X, WA = wA , WB = wB )> max{0, H(X̃Δ |Z, WA = wA , WB = wB )− H(X̃Δ |Y, WA = wA , WB = wB )}}.
Note that Alice and Bob can calculate the conditional entropies that appear in the definitions of A and B respectively,
because we assumed that they know the noise variances VA ,VB , and VE . If given (WA(i) , WB(i) ) is in the set A, we use X̃Δ(i)for generating a secret key, otherwise we discard X̃Δ(i) . Similarly, if given (WA(i) , WB(i) ) is in the set B, we use ỸΔ(i) for
generating a secret key, otherwise we discard ỸΔ(i) . Thus, we
determine discrete random variables
⎧
(i)
(i)
(i)
⎪
⎪
⎨X̃Δ if (WA , WB ) ∈ A,(i)
XΔ = ⎪(5)⎪⎩0otherwise,and0

B = {(wA , wB )|H(ỸΔ |Z, WA = wA , WB = wB )if (WA(i) , WB(i) ) ∈ B,
otherwise,(6)

and we use them for generating a secret key instead of X̃Δ(i)and ỸΔ(i) .
4. According to the rule in Eq. (5), Alice determines XΔnfrom WAn , WBn , and X̃Δn . Similarly, Bob determines YΔnfrom WAn , WBn , and ỸΔn .
5. Alice compresses her bit sequence XΔn by an encoder
ϕn from {0, 1}n to a message set MA , and sends themessage MA = ϕn (XΔn ) to Bob over the public channel.
Similarly, Bob compresses his bit sequence YΔn into themessage MB on MB , and sends it to Alice over the public channel† .
6. Alice decodes MB , X n , and the reliability information(WA , WB ) into the estimation ŶΔn . Similarly, Bob decodes MA , Y n , and the reliability information (WA , WB ),into the estimation X̂Δn .
7. Let F be a set of universal hash function [5] (see also
Appendix B.1) from {0, 1}n × {0, 1}n to S. Alice randomly choose a hash function f ∈ F , and publicly tells
the choice to Bob. Then, Alice and Bob’s final keys are
S = f (XΔn , ŶΔn ) and S  = f (X̂Δn , YΔn ) respectively.
In order to guarantee that Alice and Bob can compute the same key in step 6, we set the rate 1n log |MA | and1
n log |M B | of the public messages (MA , M B ) according to thefollowing lemma, which is derived by modifying “SlepianWolf Coding” [21] for continuous random variables. The
lemma is proved in Appendix A.
Lemma 1 Suppose that we set
1
log |MA | > H(XΔ |YWA WB )n≥ max{0, H(ỸΔ |Z, WA = wA , WB = wB )− H(ỸΔ |X, WA = wA , WB = wB )}},

⎧

(i)
⎪
⎪
⎨ỸΔ
YΔ(i) = ⎪
⎪
⎩

(7)

and
†
For example, we can consider the encoder as a parity checkmatrix and the message as a syndrome.

IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.2 FEBRUARY 2009528

1
log |MB | > H(YΔ |XWA WB ),(8)nthen there exist encoders and decoders such that the decoding error probabilities Pr{X̂Δn  XΔn } and Pr{ŶΔn  YΔn } tend to
0 as n → ∞.
Thus, Eq. (1) is satisfied for suﬃciently large n.
In order to guarantee the security of the protocol, we
set the key rate 1n log |S | according to the following lemma,
which is derived by modifying the so-called “left over hashlemma” [3], [4], [12] for continuous random variables. The
lemma is proved in Appendix B.
Lemma 2 Suppose that we set
11
log |S | < H(XΔ YΔ |ZWA WB ) − log |MA ||MB |,
n
n

(9)

H(S |Z n WAn WBn MA MB F) ≥ log |S | − 

(10)

then

is satisfied for suﬃciently large n.
Note that F is a random variable on F , and all information C
over the public channel correspond to (WAn , WBn , MA , MB , F)
in this case.
From Eqs. (7)–(9), we obtain the following theorem
that gives the key rate that is achievable by this protocol.
Theorem 1 By using our proposed protocol, the key rate
H(XΔ YΔ |ZWA WB ) − H(XΔ |YWA WB )−H(YΔ |XWA WB ).

(11)

is achievable.
Note that from the rule in Eqs. (5), (6), we can rewrite theEq. (11) as

4.

Comparison to a Protocol with Hard-Decision

In this section, we numerically show the key rate that isachievable by our proposed protocol, i.e., Eq. (11). First, weshow the relation between signal-to-noise ratio (SNR) andthe key rate for several noise-to-noise ratio (NNR). In order to clarify the advantage to use the soft-decision, we also
show the comparisons between the key rate that is achievable by our proposed protocol and the key rate that is achievable by Maurer’s protocol in which Alice and Bob use only
hard-decision for generating a secret key.
The relation between (SNR) and the key rate for several NNR is presented in Fig. 1, where sets E1 , E2 , and E3
are determined from fixed a1 = 13 , a2 = 23 , a3 = 1 in our proposed protocol. Note that SNR is defined as V1A and NNR is
defined as VVEB , and we assume VA = VB . From this figure,
we observe that we do not obtain a high key rate when SNR
is too high or too low.
In order to show advantage to use soft-decision, we
compare the key rate that is achievable by our proposed protocol and the key rate that is achievable by Maurer’s protocol
in which Alice and Bob use only hard-decision for generating a secret key. Maurer’s protocol consists of an interactive
phase, which is the so-called advantage distillation† , and a
non-interactive key agreement phase. The key rate that isachievable by Maurer’s protocol depends on the number ofthe iteration of the interactive phase. For each NNR, wedetermined the number of the iteration optimally among 0
to 4. In our protocol, we determined the set from fixed
a1 = 13 , a2 = 23 , a3 = 1. The result of this comparison ispresented in Figs. 2(a)–(c). From these figures, we observethat we obtain a larger key rate by our proposed protocol

H(XΔ YΔ |ZWA WB ) − H(XΔ |YWA WB )−H(YΔ |XWA WB )
PWA WB (wA , wB )=wA ,wB× max{0, H(X̃Δ |Z, WA = wA , WB = wB )− H(X̃Δ |Y, WA = wA , WB = wB ),H(ỸΔ |Z, WA = wA , WB = wB )− H(ỸΔ |X, WA = wA , WB = wB )}.
For fixed (WA , WB ) = (wA , wB ), H(X̃Δ |Z, WA = wA , WB =wB ) − H(X̃Δ |Y, WA = wA , WB = wB ) is the key rate that isachievable when we use only X̃Δn for generating a secret key,
H(ỸΔ |Z, WA = wA , WB = wB ) − H(ỸΔ |X, WA = wA , WB =wB ) is the key rate that is achievable when we use only ỸΔnfor generating a secret key, and 0 is trivially achievable key
rate. By the rule in Eqs. (5), (6), we choose the maximum
among these key rates for each (wA , wB ) in order to make theachievable key rate as high as possible.
Note that encoding in step 5 and decoding in step 6 are
implementable by using low-density parity check codes [6],[18].

Fig. 1 The relation between SNR and the key rate in our proposed
protocol for several NNR.
†
There is two kinds of advantage distillation, the so-called
repeat-code protocol [16] and the parity-check protocol [10] (seealso [23]). The key rate of the parity-check protocol is slightly
higher than that of the repeat-code protocol. In the comparison, we
adopted the parity-check protocol. However, the diﬀerence of the
key rates for the repeat-code protocol and the parity-check protocol
is extremely small.

NAITO et al.: SECRET KEY AGREEMENT BY SOFT-DECISION OF SIGNALS IN GAUSSIAN MAURER’S MODEL

529

ation that Alice, Bob, and Eve hard-detect received signals
according to the similar rule as in Eqs. (3) and (4). In thissituation, we can convert three Gaussian channels into independent binary symmetric channels with error probabilities
A , B , E given by
⎛
⎛
⎞
⎞
⎜⎜⎜
⎜⎜⎜
1 ⎟⎟⎟
1 ⎟⎟⎟
1
1
A = erfc ⎝⎜B = erfc ⎝⎜
⎠⎟ ,
⎠⎟ ,
2
VA
2
VB
⎛
⎞
⎜⎜
1 ⎟⎟⎟
1
⎟⎠ ,
E = erfc ⎜⎜⎝
(12)
2
VE
(a) SNR = 1 [dB]

where the complementary error function erfc(z) is defined
as
 ∞
2
2
e−t .
(13)
erfc(z) = √π zNote that this way of the comparison gives Maurer’s protocol advantage because a wire-tapper in Gaussian Maurer’s model is more powerful than in BSC Maurer’s model† .
Hence, the key rate that is guaranteed to be achievable byMaurer’s protocol in Gaussian Maurer’s model is lower thanthat presented in Figs. 2(a)–(c).
5.

Conclusion(b) SNR = 5 [dB](c) SNR = 7 [dB]Fig. 2 The key rates that are achievable by our proposed protocol andMaurer’s protocol.

than by Maurer’s protocol with all value of NNR. Note thatin Gaussian Maurer’s model, we should calculate the key
rate by Maurer’s protocol for Eve who can use continuous
random variables Z n to guess the secret key. However, thenumerical calculation of the key rate by Maurer’s protocol
in Gaussian Maurer’s model is diﬃcult when the number ofthe iteration of the interactive phase is larger than 1. Thus,
we calculate the key rate in BSC Maurer’s model instead ofGaussian Maurer’s model when the number of the iterationof the interactive phase is larger than 1. In the calculation of
the key rate in BSC Maurer’s model, we consider the situ†
The wire-tapper in Gaussian Maurer’s model can use continuous random variables Z n to guess the secret key, but one in BSC
Maurer’s model can only use quantized versions of them.

In this paper, we have proposed Gaussian Maurer’s modeland the protocol with reliability information based on the
result of the soft-decision in this model. As a result, wehave obtained a higher key rate than Maurer’s protocol. Thisis because that the correlation between XΔ in Eq. (5) and Y
and between YΔ in Eq. (6) and X obtained by using the reliability information is stronger than the correlation between
X̃Δ in Eq. (3) and ỸΔ in Eq. (4) obtained by using the harddecision.
However, we do not know the optimal way to determine sets E1 , . . . , E K and its number K. Intuitively, one may
think that the more sets we use, the higher rate we obtain.
However, this intuition does not seem to be always true. We
determined the number of the sets to be 3 according to ourrule of thumb. Furthermore, we have to find the optimal signal constellation used by the satellite. These problems are
future research agenda.
Acknowledgments
We would like to thank Prof. Motohiko Isaka and Dr. Jun
Muramatsu for valuable discussions. We also thank theanonymous reviewers for their constructive comments andsuggestions. This research is also partly supported by theJapan Society for the Promotion of Science under Grantsin-Aid No. 00197137.
References[1] R. Ahlswede and I. Csiszar, “Common randomness in information
theory and cryptography — part 1: Secret sharing,” IEEE Trans. Inf.
Theory, vol.39, no.4, pp.1121–1132, 1993.

IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.2 FEBRUARY 2009530

[2] T. Aono, K. Higuchi, T. Ohira, B. Komiyama, and H. Sasaoka,“Wireless secret key generation exploiting reactance-domain scalar
response of multipat fading channel,” IEEE Trans. Antennas
Propag., vol.53, no.11, pp.3776–3784, Nov. 2005.
[3] 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.
[4] 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.
[5] J.L. Carter and M.N. Wegman, “Universal classes of hash functions,” J. Comput. Syst. Sci., vol.18, pp.143–154, 1979.
[6] T.P. Coleman, A.H. Lee, M. Médard, and M. Eﬀros, “Lowcomplexity approaches to Slepian & Wolf near-lossless distributed
data compression,” IEEE Trans. Inf. Theory, vol.52, no.8, pp.3546–
3561, Aug. 2006.
[7] T.M. Cover and J.A. Thomas, Elements of Information Theory,
2nd ed., John Wiley & Sons, 2006.
[8] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Trans. Inf. Theory, vol.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] M.J. Gander and U. Maurer, “On the secret-key rate of binary random variables,” IEEE International Symposium on Information Theory, p.351, 1994.
[11] T.S. Han, Information-Spectrum Methods in Information Theory,
Springer, 2003.
[12] R. Impagliazzo, L.A. Levin, and M. Luby, “Pseudo-random generation from one-way function,” Proc. 21st Annual ACM Symposiumon Theory of Computing (STO’89), pp.12–24, ACM Press, 1989.
[13] K. Itou, Introduction to probability theory, Cambridge University
Press, 1984.
[14] S.K. Leung-Yan-Cheong, Multi-User and Wire-tap Channels Including Feedback, Ph.D. Thesis, Stanford University, 1976.
[15] S.K. Leung-Yan-Cheong and M.E. Hellman, “The Gaussian wiretap channel,” IEEE Trans. Inf. Theory, vol.24, no.4, pp.451–456,
July 1978.
[16] U. Maurer, “Secret key agreement by public discussion from common information,” IEEE Trans. Inf. Theory, vol.39, no.3, pp.733–
742, May 1993.
[17] 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.
[18] J. Muramatsu, T. Uyematsu, and T. Wadayama, “Low-density
parity-check matrices for coding of correlated sources,” IEEE Trans.
Inf. Theory, vol.51, no.10, pp.3645–3654, Oct. 2005.
[19] A.C.A. Nascimento, J. Barros, S. Skludarek, and H. Imai, “The commitment capacity of the gaussian channel is infinite,” IEEE Trans.
Inf. Theory, vol.54, no.6, pp.2785–2789, July 2008.
[20] R. Renner, Security of quantum key distribution, Ph.D. Thesis, Dipl.
Phys. ETH, Switzerland, 2005. arXiv:quant-ph/0512258.
[21] D. Slepian and J.K. Wolf, “Noiseless coding of correlated information sources,” IEEE Trans. Inf. Theory, vol.19, no.4, pp.471–480,
July 1973.
[22] S. Wolf, Information-Theoretically and Computationally Secure
Key Agreement in Cryptography, Ph.D Thesis, Dipl. Math. ETH,
Switzerland, 1999.
[23] S. Wolf, “Unconditional security in cryptography,” Lectures on Data
Security, Lecture Notes in Computer Science, vol.1561, pp.217–
250, Springer, 1999.
[24] A.D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol.54,
no.8, pp.1355–1387, 1975.

Appendix A: Proof of Lemma 1
We only prove that if we set the rate 1n log |MA | of public
message according to Eq. (7), then there exist encoders anddecoders such that the decoding error probabilities Pr{X̂Δn 
XΔn } tends to 0 as n → ∞. The proof for the rate 1n log |MB |of public message follows by symmetry.
We use the so-called “bin coding” proposed by Cover[7] in this proof. The procedures of bin coding is as follows.
Assign every xnΔ ∈ XnΔ to one of |MA | bins independently according to the uniform distribution on MA .
Alice sends the index i of the bin to which xnΔ belongs.
Then let ϕ̄n (xnΔ ) = i.
For each (yn , wn ), we define the set S n (yn , wn ) ⊂ XnΔ as1
1
S n (yn , wn ) := xnΔ : lognn
PXΔ |Y n ,Wn (xnΔ |yn , wn )
≤ H(XΔ |YW) + γ ,where γ > 0 is an arbitrary fixed small constant, and wedenote the pair (WAn , WBn ) as Wn . Then, for given yn , wn , andthe received index i, declare ψ̄n (i, yn , wn ) = xnΔ if there is
one and only one pair (xnΔ , yn , wn ) such that ϕ¯n (xnΔ ) = i and
xnΔ ∈ S n (yn , wn ). Otherwise, declare an error.
We will evaluate the decoding error probability averaged over randomly chosen encoders as follows. We havean error if XΔn is not in S n (Y n , Wn ) or if there is another symbol x̂nΔ ∈ XnΔ in the same bin. Thus, we can define the eventsof error
En(0) := {XΔn  S n (Y n , Wn )},En(1) := ∃ x̂n  XΔn : ϕ¯n ( x̂nΔ ) = ϕ¯n (XΔn )
and x̂nΔ ∈ S n (Y n , Wn ) ,Then the decoding error probability averaged over randomly
chosen encoders Pr{XΔn  ψ¯n (ϕ¯n (XΔn ), Y n , Wn )} is upperbounded as
Pr{XΔn  ψ¯n (ϕ¯n (XΔn ), Y n , Wn )}= Pr{En(0) ∪ En(1) }≤ Pr{En(0) } + Pr{En(1) }.

(A· 1)

Pr{En(0) } is evaluated as
Pr{En(0) } = Pr{XΔn  S n (Y n , Wn )}11= Pr logn
PXΔn |Y n Wn (XΔn |Y n Wn )
> H(XΔ |YW) + γ
= Pr

n
1 

log

1

PXΔ |YW (XΔ(i) |Y (i) W(i) )> H(XΔ |YW) + γ ,n i=1(A· 2)

which tends to 0 as n → ∞ by the weak law of large numbers. To bound Pr{En(1) }, we rewrite it as

NAITO et al.: SECRET KEY AGREEMENT BY SOFT-DECISION OF SIGNALS IN GAUSSIAN MAURER’S MODEL

531

Pr{En(1) }= Pr ∃ x̂nΔ  XΔn : ϕ̄n ( x̂nΔ ) = ϕ̄n (XΔn )
and x̂nΔ ∈ S n (Y n , Wn )=
pY n (yn )YnP

XΔn Wn |yn(xnΔ ,wn )∈XnΔ ×WAn ×WnBn(xΔ , wn )gn (xnΔ , yn , wn ) dyn ,Appendix B: Proof of Lemma 2(A· 3)

where
gn (xnΔ , yn , wn )= Pr ∃ x̂nΔ  xnΔ : ϕ̄n ( x̂nΔ ) = ϕ̄n (xnΔ )and ( x̂nΔ ) ∈ S n (yn , wn ) .

(A· 4)

Furthermore, we can rewrite (A· 4) asgn (xnΔ , yn , wn ) =Pr{ϕ̄n ( x̂nΔ ) = ϕ̄n (xnΔ )}x̂n xnΔ Δ
x̂n ∈S n (yn ,wn )Δ=x̂n xnΔ Δ
x̂n ∈S n (yn ,wn )
Δ

≤

1
|MA |



1
|M
A|
x̂n ∈S (yn ,wn )Δn|S n (yn , wn )|=|MA |(A· 5)

If x̂nΔ ∈ S n (yn , wn ), then from the definition of S n (yn , wn ),we have
PXΔn |yn ,wn ( x̂nΔ ) ≥ 2−n(H(XΔ |YW)+γ) .
Thus, we have1≥x̂nΔ ∈S n (yn ,wn )PXΔn |Y n Wn (xnΔ |yn , wn )Hence, we have(A· 6)

From Eqs. (A· 3)–(A· 6), we upper bound Pr{En(1) } as

Pr{En(1) } ≤YnpY n (yn )(xnΔ ,wn )∈XnΔ ×WAn ×WnB

PXΔn Wn |yn (xnΔ , wn )2n(H(XΔ |YW)+γ) n
dy
|MA |

2n(H(XΔ |YW)+γ)≤|MA |= 2− log |MA | 2n(H(XΔ |YW)+γ) ,v∈V

B.1 Universal Hash Family
In order to extract an almost secret string (secret key S ) froma partially secret strings (a pair Rn of random variables XΔnand YΔn ), we use a universal hash family F . A set F offunctions f : XnΔ × YΔn → S is said to be a universal hashfamily if we have
1PF { f ∈ F | f (rn ) = f (r n )} ≤|S|

≥ |S n (yn , wn )|2−n(H(XΔ |YW)+γ) .

|S n (yn , wn )| ≤ 2n(H(XΔ |YW)+γ) .

In this Appendix, we will show the proof of lemma 2. In
Sect. B.1, we introduce a universal hash family, which isused for computation of a secret key. In Sect. B.2, we define the security of the protocol in the sense of the variational distance, and we show the relation between the security of the protocol in the sense of the variational distanceand the condition Eq. (10). This relation implies that if the
security of the protocol in the sense of the variational distance is satisfied, then the condition Eq. (10) is satisfied.
In Sect. B.3, we relate the size |S| of a secret key S andthe size |MA × MB | of public messages M = (MA , MB )to the security of the protocol, and we show that if we set
1
1
n ln |S| < H(XΔ YΔ |ZWA W B ) − n ln |MA × M B |, then there
exists at least one hash function f that satisfy Eq. (10) for
suﬃciently large n.
For the simplicity of notation, we denotes the integral
over Rn as unless otherwise specified, and we abbreviates
PRn Mn |Z n Wn (·, ·|zn , wn ) as PRn Mn |zn ,wn (·, ·). The variational distance P1 − P2  between the probability distribution P1 andP2 on V is defined asP1 − P2  :=|P1 (v) − P2 (v)|.
(A· 8)(A· 9)

for any rn  r n ∈ XnΔ × YΔn , where F denotes a randomvariable on F and PF denotes the uniform distribution on
F . For given Eve’s received signals zn ∈ Rn and reliability
information wn ∈ WA × WB , the jointly conditional distribution PS M|zn ,wn (s, m) of a secret key S = f (Rn ) and public
message M is given by
PS M|zn ,wn (s, m) :=PRn M|zn ,wn (rn , m)rn ∈ f −1 (s)= PRn M|zn ,wn ( f −1 (s), m),(A· 7)

which exponentially tends to 0 as n → ∞ if 1n log |MA | >H(XΔ |YW) + γ.
Since the decoding error probability Pr{XΔn ψ¯n (ϕ¯n (XΔn ), Y n , Wn )} of randomly chosen code tends to 0 as
n → ∞, there exist at least one pair of an encoder and a decoder such that the decoding error probability Pr{X̂Δn  XΔn }tends to 0 as n → ∞.

where f −1 (s) := {rn ∈ XnΔ × YΔn | f (rn ) = s} is the subset of a
set XnΔ × YΔn such that f (rn ) = s. Note that since S depends
on a hash function f , it should be referred as S f . But, we
use the above notation for convenience in this paper.
B.2 The Security of the Protocol in the Sense of the Variational DistanceIn order to prove lemma 2, we define the security of the protocol in the sense of the variational distance in this section.

IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.2 FEBRUARY 2009532

If a secret key S is independent of Eve’s information andits distribution PS is close to the uniform distribution PS̄ on
S, we decide that the secret key S is secure in the sense of
the variational distance. In the other words, we define thesecurity of the protocol as
pZ n (zn )PWn |zn (wn )Δ f :=
wn ∈WAn ×WnB

PS M|zn ,wn − PS̄ × PM|zn ,wn dzn ,(A· 10)where PM|zn ,wn is the marginal distribution of PS M|zn ,wn , andPS̄ × PM|zn ,wn is the product distribution of PS̄ and PM|zn ,wn
As an extension of [9, Lemma 1] to continuous randomvariable, the following lemma relates the security of the protocol in the sense of the variational distance to the securityof the protocol in the sense of the entropy shown in Eq. (2).
Lemma 3 The conditional entropy H(S |Z n Wn MF) is lower
bounded by
H(S |Z n Wn MF) ≥ (1 − E f [Δ f ]) ln |S|1−E f [Δ f ] log.
E f [Δ f ](A· 11)

Note that since Wn = (WAn , WBn ) and M = (MA , MB ),the conditional entropy H(S |Z n Wn MF) is equivalent toH(S |Z n WAn WBn MA , MB F) in Eq. (10). From this lemma, if
E f [Δ f ] is suﬃciently small, a secret key S is secure in thesense of the entropy.
Proof. Let
Δ f,m,zn ,wn := PS |m,zn ,wn − PS̄ .

pZ n (zn )Δ f,zn log

from Jensen’s inequality for f .

must be satisfied [13]. In this case, from the fact that 0 ≤Δ f,zn ≤ 2, this condition is satisfied.
B.3 The Relation between the Size of a Secret Key and the
Security of the Protocol
The following lemma relates the size |S| of a secret key S
and the size |MA ×MB | of public messages M to the securityof the protocol.
Lemma 4 For the size |S| of a secret key S , the size |MA ×
MB | of public messages M, and the security of the protocol
Δ f , we have
E f [Δ f ]H(S |M = m, Z n = zn , Wn = wn , F = f )|S|≥ log |S| − Δ f,m,zn ,wn log,
Δ f,m,zn ,wn(A· 14)

which follows from the continuity of entropy [7] in the similar way as [9, Lemma 1].
The second term of Eq. (A· 14) is upper bonded as follow. Since t log 1t is a concave function, we obtain
PMWn |zn (m, wn )Δ f,m,zn ,wn log

m,wn≤ Δ f,zn log

|S|
Δ f,z

|S|

rn ∈ XnΔ × YΔn |1n− log PRn |zn wn (r ) < α dzn ,n(A· 19)where E f denotes expectation for a uniform distribution on
F.
Proof. This proof is based on the techniques in [20, Chapter
5]. In the following, we will prove
E f [Δ f,zn ,wn ]≤Δ f,m,zn ,wn(A· 15)from Jensen’s inequality for wn , m, where we let Δ f,zn :=nm,wn PMWn |zn (m, w )Δ f,m,zn ,wn . Averaging Eq. (A· 15) overnz , we obtainwn

×PRn |zn wn(A· 13)For given zn ∈ Rn , wn ∈ WAn ×WnB , and m ∈ MA ×MB ,we obtain

|S||MA × MB |αn
 2 
+2 pnZ (zn )PWn |zn (wn )

PMWn |zn (m, w )Δ f,m,zn ,wn dzn

Note that when we use Jensen’s inequality for a continuous random variable, the condition of absolutely integrable
pZ n (zn )|Δ f,zn |dzn < ∞(A· 18)≤m,wnn(A· 16)from Jensen’s inequality for zn . Moreover, averaging
Eq. (A· 16) over f , we obtain


|S|
|S|
(A· 17)≤ E f [Δ f ] log
E f Δ f log
Δf
E f [Δ f ](A· 12)

Then, we can rewrite Δ f as
pZ n (zn )
Δf =

|S| n
|S|
dz ≤ Δ f log
n
Δ f,z
Δf

|S||MA × MB |2αn+2PRn |zn wn rn ∈ XnΔ × YΔn |1n− log PRn |zn wn (r ) < α ,n(A· 20)where
Δ f,zn ,wn = PS M|zn wn − PS̄ × PM|zn wn ,(A· 21)

NAITO et al.: SECRET KEY AGREEMENT BY SOFT-DECISION OF SIGNALS IN GAUSSIAN MAURER’S MODEL

533

Averaging Eq. (A· 20) over zn and wn , we obtain Eq. (A· 19).
For given zn ∈ Rn and wn ∈ WAn × WnB , we define theset An ⊂ XnΔ × YΔn as


1
n
n
n
n
n
n
n
An := r ∈ XΔ × YΔ | − log PR |z w (r ) ≥ α ,nand we define the set Acn as the complement of An on XnΔ ×
YΔn . Then, Δ f,zn ,wn for given f ∈ F is upper bounded by
PS M|zn wn − PS̄ × PM|zn wn =|PRn M|zn wn ( f −1 (s), m)−PS̄ (s)PRn M|zn wn (An , m)
+PRn M|zn wn ( f −1 (s) ∩ Acn , m)−PS̄ (s)PRn M|zn wn (Acn , m)|(A· 23)−1c≤hn (s, m) +PRn M|zn wn ( f (s) ∩ An , m)+s,m(Acn , m)(A· 24)hn (s, m) + 2PRn |zn wn (Acn ).

(A· 25)PS̄ (s)P

Rn M|zn wn

s,m

=


s,m

PRn M|zn wn ( f −1 (s) ∩ An , m)2

 1
m

|S|

PRn M|zn wn (An , m)2 ,(A· 28)1
where Eq. (A· 28) follows from the fact that PS̄ (s) = |S|
and

−1
n
n
n
n
n
n
s PR M|z w ( f (s) ∩ An , m) = PR M|z w (An , m). Then, we
can rewrite the first term of Eq. (A· 28) asPRn M|zn wn ( f −1 (s) ∩ An , m)2

PRn M|zn wn (rn , m)s,m rn ,rn ∈ f −1 (s)∩An(A· 22)

s,m



−

=

−PS̄ (s)PM|zn wn (m)|=|PRn M|zn wn ( f −1 (s) ∩ An , m)


s,m

s,m

s,m

s,m

=

=

PRn M|zn wn (r n , m) δ f (rn ), f (rn ) PRn M|zn wn (rn , m)m rn ,rn ∈An

PRn M|zn wn (r n , m),(A· 29)where δ f (rn ), f (rn ) is Kronecker’s delta. On the other hand,
we can rewrite the second term of Eq. (A· 28) as 1
PRn M|zn wn (An , m)2
|S|
m
  1
PRn M|zn wn (rn , m)
=
|S|
n
n
m r ,r ∈An

PRn M|zn wn (r n , m).

wherehn (s, m) = |PRn M|zn wn ( f −1 (s) ∩ An , m)−PS̄ (s)PRn M|zn wn (An , m)|.

(A· 26)Equation (A· 22) follows from the definition of the variational distance and f −1 (s). Eq. (A· 23) follows from the factthat ( f −1 (s) ∩ An ) ∩ ( f −1 (s) ∩ Acn ) = ∅, f −1 (s) = ( f −1 (s) ∩An ) ∪ ( f −1 (s) ∩ Acn ), and PM|zn wn (m) = PRn M|zn wn (An , m) +PRn M|zn wn (Acn , m). Eq. (A· 24) follows from the triangle inequality. Eq. (A· 25) follows from the fact that ∪ s∈S f −1 (s) =XnΔ × YΔn . By regarding the first term in Eq. (A· 25) as an
inner product, and by using the Cauchy-Schwarz inequality,
we can upper bound the first term in Eq. (A· 25) byhn (s, m) ≤ |S||MA × MB |hn (s, m)2 (A· 27)
s,m

s,m

(A· 30)Thus, averaging Eq. (A· 28) over f , we obtain


 
1
n
n
E f δ f (r ), f (r ) −|S|m rn ,rn ∈AnPRn M|zn wn (rn , m)PRn M|zn wn (r n , m).

(A· 31)Since f is chosen from a universal-hash-family, we obtain 
1
1 for rn = r n
E f δ f (rn ), f (rn ) −≤0 for rn  r n
|S|from its definition (shown in Eq. (A· 9)). Thus, Eq. (A· 31)
is upper bounded by
PRn M|zn wn (rn , m)PRn M|zn wn (rn , m)m rn ∈An

Furthermore, we can rewrite the inside of the root of
Eq. (A· 27) ashn (s, m)2
s,m

=



PRn M|zn wn ( f −1 (s) ∩ An , m)2s,m−1−2PRn M|zn wn ( f (s) ∩ An , m)
PS̄ (s)PRn M|zn wn (An , m)+PS̄ (s)2 PRn M|zn wn (An , m)2



1
PRn M|zn wn (rn , m) αn2m rn ∈An
1≤
PRn M|zn wn (rn , m) αn
2
rn ,m

≤

=

1
,
2αn

(A· 32)(A· 33)(A· 34)

where Eq. (A· 32) follows from the fact that PRn M|zn wn (rn , m)
≤ PRn |zn wn (rn ) ≤ 21αn for any rn ∈ An . Since the root function√· is concave function, by combining Eqs. (A· 22)–(A· 32)
and averaging over f , we obtain

IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.2 FEBRUARY 2009534

E f [Δ f,zn ,wn ]≤ |S||MA × MB |hn (s, m)2

Shun Watanabe
was born in Tokyo, Japan,
on February 2, 1983. He received the B.E. and
M.E. degrees from Tokyo Institute of Technology in 2005 and 2007 respectively. He is currently a doctoral student in the Department ofCommunications and Integrated Systems of Tokyo Institute of Technology. His current research interests are in the areas of information
theory, quantum information theory, and quantum cryptography.

s,m+2PRn |zn wn rn ∈ XnΔ × YΔn |1n− log PRn |zn wn (r ) < αn≤|S||MA × MB |2αn+2PRn |zn wn rn ∈ XnΔ × YΔn |1− log PRn |zn wn (rn ) < α .
n(A· 35)Corollary 1 Suppose that we set 1n log |S| = H(R|ZW) −1n log |MA × M B | − 2δ, E f [Δ f ] is exponentially small for
suﬃciently large n.
Proof. Suppose that we set α = H(R|ZW) − δ for δ > 0,
the second term of Eq. (A· 19) exponentially tends to 0 as
n → ∞ by using the Chernoﬀ bound [7]. On the other hand,
suppose that we set 1n log |S| = H(R|ZW) − 1n log |MA ×
MB | − 2δ, the first term of Eq. (A· 19) is e−δn and tends
to 0 as n → ∞. Thus, suppose that we set 1n log |S| =H(R|ZW) − 1n log |MA × MB | − 2δ, E f [Δ f ] exponentiallytends to 0 as n → ∞.

If E f [Δ f ] is exponentially small, then the security of the
protocol in the sense of entropy is guaranteed by lemma
3. From this fact and corollary 1, suppose that we set
1
1
n log |S| < H(XΔ YΔ |ZWA W B ) − n log |MA × M B |, Eq. (10)is satisfied for suﬃciently large n.

Masashi Naito
was born in Aichi, Japan,
on July 5, 1985. He received the B.E. degreefrom Tokyo Institute of Technology in 2008. He
is currently a master’s student in the Departmentof Media Science of the Graduate School of Information Science of Nagoya University. His
current research interests are in the areas of pattern recognition.

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 he iswith the Department of Communications and Integrated Systems as professor. In 1992 and 1996, he was a visiting researcher at the Centre Nationalde la Recherche Scientifique, France and Delft University of Technology,
Netherlands, respectively. He received Shinohara Memorial Young Engineer Award in 1989, and the Best Paper Award in 1993, 1996, 2002, and2007 all from IEICE. 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.