# Finite-block-length analysis in classical and quantum information theory.

I. Introduction

A fundamental problem in information processing is to transmit a message correctly via a noisy channel, where the noisy channel is mathematically described by a probabilistic relation between input and output symbols. To address this problem, we employ channel coding, which is composed of two parts: an encoder and a decoder. The key point of this technology is the addition of redundancy to the original message to protect it from corruption by the noise. The simplest channel coding is transmitting the same information three times as shown in Fig. 1. That is, when we need to send one bit of information, 0 or 1, we transmit three bits, 0, 0, 0 or 1, 1, 1. When an error occurs in only one of the three bits, we can easily recover the original bit. The conversion from 0 or 1 to 0, 0, 0 or 1, 1, 1 is called an encoder and the conversion from the noisy three bits to the original one bit is called a decoder. A pair of an encoder and a decoder is called a code.

In this example, the code has a large redundancy and the range of correctable errors is limited. For example, if two bits are flipped during the transmission, we cannot recover the original message. For practical use, we need to improve on this code, that is, decrease the amount of redundancy and enlarge the range of correctable errors.

The reason for the large redundancy in the simple code described above is that the block-length (the number of bits in one block) of the code is only 3. In 1948, Shannon (1) discovered that increasing the block-length n can improve the redundancy and the range of correctable errors. In particular, he clarified the minimum redundancy required to correct an error with probability almost 1 with an infinitely large block-length n. To discuss this problem, for a probability distribution P, he introduced the quantity H(P), which is called the (Shannon) entropy and expresses the uncertainty of the probability distribution P. He showed that we can recover the original message by a suitable code when the noise of each bit is independently generated subject to the probability distribution P, the rate of redundancy is the entropy H(P), and the block-length n is infinitely large. This fact is called the channel coding theorem. Under these conditions, the limit of the minimum error probability depends only on whether the rate of the redundancy is larger than the entropy H(P) or not.

We can consider a similar problem when the channel is given as additive white Gaussian noise. In this case, we cannot use the term redundancy because its meaning is not clear. In the following, instead of this term, we employ the transmission rate, which expresses the number of transmitted bits per one use of the channel, to characterize the speed of the transmission. In the case of an additive white Gaussian channel, the channel coding theorem is that the optimal transmission rate is j log(1 + S/N), where S/N is the signal-noise ratio [2, Theorem 7.4.4]. However, we cannot directly apply the channel coding theorem to actual information transmission because this theorem guarantees only the existence of a code with the above ideal performance. To construct a practical code, we need another type of theory, which is often called coding theory. Many practical codes have been proposed, depending on the strength of the noise in the channel, and have been used in real communication systems. However, although these codes realize a sufficiently small error probability, no code could attain the optimal transmission rate. Since the 1990s, turbo codes and low-density parity check (LDPC) codes have been actively studied as useful codes. (3,4) It was theoretically shown that they can attain the optimal transmission rate when the block-length n goes to infinity. However, still no actually constructed code could attain the optimal transmission rate. Hence, many researchers have doubted what the real optimal transmission rate is. Here, we should emphasize that any actually constructed code has a finite block-length and will not necessarily attain the conventional asymptotic transmission rate.

On the other hand, in 1962, Strassen (5) addressed this problem by discussing the coefficient with the order 1/[square root of n] of the transmission rate, which is called the second-order asymptotic theory. The calculation of the second-order coefficient approximately gives the solution of the above problem, that is, the real optimal transmission rate with finite block-length n. Although he derived the second-order coefficient for the discrete channel, he could not derive it for the additive white Gaussian channel. Also, in spite of the importance of his result, many researchers overlooked his result because his paper was written in German. Therefore, the successive researchers had to recover his result without use of his derivation. The present paper explains how this problem has been resolved even for additive white Gaussian channel by tracing the long history of classical and quantum information theory.

Currently, finite block-length theory is one of hottest topics in information theory and is discussed more precisely for various situations elsewhere. (6-17) Interestingly, in the study of finite-block-length theory, the formulation of quantum information theory becomes closer to that of classical information theory. (18)

In addition to reliable information transmission, information theory studies data compression (source coding) and (secure) uniform random number generation. In these problems, we address a code with block-length n. When the information source is subject to the distribution P and the block-length n is infinitely large, the optimal conversion rate is H(P) in both problems. Finite-length analysis also plays an important role in secure information transmission. Typical secure information transmission methods are quantum cryptography and physical layer security. The aim of this paper is to review the finite-length analysis in these various topics in information theory. Further, finite-length analysis has been developed in conjunction with an unexpected effect from the theory of quantum information transmission, which is often called quantum information theory. Hence, we explain the relation between the finite-length analysis and quantum information theory.

The remained of the paper is organized as follows. First, Section II outlines the notation used in information theory. Then, Section III explains how the quantum situation is formulated as a preparation for later sections. Section IV reviews the idea of an information spectrum, which is a general method used in information theory. The information spectrum plays an important role for developing the finite-length analysis later. Section V discusses folklore source coding, which is the first application of finite-length analysis. Then, Section VI addresses quantum cryptography, which is the first application to an implementable communication system. After a discussion of quantum cryptography, Section VII deals with second-order channel coding, which gives a fundamental bound for finite-length of codes. Finally, Section VIII discusses the relation between finitelength analysis and physical layer security.

II. Basics of information theory

As a preparation for the following discussion, we provide the minimum mathematical basis for a discussion of information theory. To describe the uncertainty of a random variable X subject to the distribution [P.sub.X] on a finite set X, Shannon introduced the Shannon entropy H([P.sub.X]) := - [summation].sub.x [member of] [chi]] [P.sub.X] (x) log [P.sub.X] (x), which is often written as H(X). When--log [P.sub.X](x) is regarded as a random variable, H([P.sub.X]) can be regarded as its expectation under the distribution [P.sub.X]. When two distributions P and Q are given the entropy is concave, that is, [lambda]H(P) + (1 - [lambda])H(Q) [less than or equal to] H( [lambda]P + (1 - [lambda])Q) for 0 < [lambda] <1. Due to the concavity, the maximum of the entropy is log [absolute value of X], where [absolute value of X] is the size of X. To discuss the channel coding theorem, we need to consider the conditional distribution [P.sub.Y|X](y|x) = [P.sub.Y|X=x] (y) where Y is a random variable in the finite set Y, which describes the channel with input system X and output system Y. In other words, the distribution of the value of the random variable Y depends on the value of the random variable X. In this case, we have the entropy H([P.sub.Y|X=x]) dependent on the input symbol x [member of] X.

Now, we fix a distribution [P.sub.X] on the input system X, taking the average of the entropy H([P.sub.Y|X=x]), we obtain the conditional entropy [[summation].sub.x[member of]X] [P.sub.X](x)[H.sub.(PY|X=x]), which is often written as H(Y|X). That is, the conditional entropy H(Y|X) can be regarded as the uncertainty of the system Y when we know the value on X. On the other hand, when we do not know the value on X, the distribution [P.sub.Y] on Y is given as [P.sub.Y](y) := [[summation].sub.x[member of]X] [P.sub.X](x)[P.sub.Y|X=x](y). Then, the uncertainty of the system Y is given as the entropy H(Y) := H([P.sub.y]), which is larger than the conditional entropy H(Y|X) due to the concavity of the entropy. So, the difference H(Y) - H(Y|X) can be regarded as the amount of knowledge in the system Y when we know the value on the system X. Hence, this value is called the mutual information between the two random variables X and Y, and is usually written as I(X; Y). Here, however, we denote it by I ([P.sub.X], [P.sub.Y|X]) to emphasize the dependence on the distribution [P.sub.X] over the input system X.

In channel coding, we usually employ the same channel [P.sub.Y|X] repetitively and independently (n times). The whole channel is written as the conditional distribution

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [x.sup.n] = ([x.sub.i], ..., [x.sub.n]) [member of] [X.sup.n] and [y.sup.n] = ([y.sub.1],...,[y.sub.n]) [member of] [y.sup.n]. This condition is called the memoryless condition. In information theory, information intended to be sent to a receiver is called a message, and is distinguished from other types of information. We consider the case that the sender sends a message, which is one element of the set [M.sub.n] := {1, ..., [M.sub.n]}, where [M.sub.n] expresses the number of elements in the set. Then, the encoder [E.sub.n] is written as a map from [M.sub.n] to [X.sup.n], and the decoder [D.sub.n] is written as a map from [y.sup.n] to [M.sub.n]. The pair of the encoder [E.sub.n] and the decoder [D.sub.n] is called a code.

Under this formulation, we focus on the decoding error probability [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which" expresses the performance of a code ([E.sub.n], [D.sub.n]). As another measure of the performance of a code ([E.sub.n], [D.sub.n]), we focus on the size [M.sub.n], which is denoted by [absolute value of ([E.sub.n], [D.sub.n])] later. Now, we impose the condition [epsilon]([E.sub.n], [D.sub.n]) [less than or equal to] [epsilon] on our code ([E.sub.n],[D.sub.n]), and maximize the size [absolute value of ([E.sub.n],[D.sub.n])]. That is, we focus on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this context, the quantity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] expresses the maximum transmission rate under the above conditions. The channel coding theorem characterizes the maximum transmission rate as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [1]

The maximum value of the mutual information is called the capacity. To characterize the mutual information, we introduce the relative entropy between two distributions P and Q as D(P [parallel] Q) := [[summation].sub.x [member of] X] P(x) log P(x)/Q(x). When we introduce the joint distribution [P.sub.XY](x, y) := [P.sub.X](x)[P.sub.Y|X](y|x) and the product distribution ([P.sub.X] x [P.sub.Y]) (x,y) := [P.sub.X](x) [P.sub.Y](y), the mutual information is characterized as (1,2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [2]

That is, the capacity is given as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [3]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [4]

The final equation can be shown by using the mini-max theorem. On the other hand, it is known that the relative entropy D(P [parallel] Q) characterizes the performance of statistical hypothesis testing when both hypotheses are given as distributions P and Q. Hence, we can expect an interesting relation between channel coding and statistical hypothesis testing.

As a typical channel, we focus on an additive channel. When the input and output systems X and Y are given as the module Z/dZ, given the input X [member of] Z/dZ, the output Y [member of] Z/dZ is given as Y = X D Z, where Z is the random variable describing the noise and is subject to the distribution [P.sub.Z] on Z/dZ. Such a channel is called an additive channel or an additive noise channel. In this case, the conditional entropy H(Y|X) is H([P.sub.Z]), because the entropy H([P.sub.Y|X=x]) equals H(Pz) for any input x [member of] X, and the mutual information I ([P.sub.X], [P.sub.Y|X]) is given by H([P.sub.Y]) - H([P.sub.Z]). When the input distribution [P.sub.X] is the uniform distribution, the output distribution [P.sub.Y] is the uniform distribution and achieves the maximum entropy log d. So, the maximum mutual information [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given as log d - H([P.sub.Z]). That is, the maximum transmission equals log d - H([P.sub.Z]). If we do not employ the coding, the transmission rate is log d. Hence, the entropy H([P.sub.Z]) can be regarded as the loss of the transmission rate due to the coding. In this coding, we essentially add the redundancy H([P.sub.Z]) in the encoding stage.

It is helpful to explain concrete constructions of codes with the case of d = 2, in which Z/2Z becomes the finite field F2, which is the set {0,1} with the operations of modular addition and multiplication, when the additive noise [Z.sup.n] = ([Z.sub.1], ..., [Z.sub.n]) is subject to the n-fold distribution [P.sup.n.sub.Z] of n independent and identical distributed copies of Z ~ [P.sub.Z]. (From now on, we call such distributions "iid distributions" for short.) The possible transmissions are then elements of [F.sup.n.sub.2] which is the set of n-dimensional vectors whose entries are either 0 or 1. In this case, we can consider the inner product in the vector space [F.sup.n.sub.2] using the multiplicative and additive operations of [F.sub.2]. When [P.sub.Z](1) = p, the entropy H([P.sub.Z]) is written as h(p), where the binary entropy is defined as h(p) := - p log p - (1 - p)log (1 - p). Since [X.sup.n] = [F.sup.n.sub.2], we choose a subspace C of [F.sup.n.sub.2] with respect to addition and we identify the message set [M.sub.n] with C. The encoder is given as a natural imbedding of C. To find a suitable decoder, for a given element [y] of the coset [F.sup.n.sub.2]/C, we seek the most probable element [GAMMA]([y]) among x + C. Hence, when we receive y [member of] [F.sup.n.sub.2], we decode it to y - [GAMMA]([y]). It is typical to employ this kind of decoder. To identify the subspace C, we often employ a parity check matrix K, in which, the subspace C is given as the kernel of K. Using the parity check matrix K, the element of the coset [F.sup.n.sub.2]/C can be identified using the image of the parity check matrix K, which is called the syndrome. In this case, we denote the encoder by [E.sub.k].

Alternatively, when [GAMMA]([y]) realizes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the decoder is called the maximum likelihood decoder. This decoder also gives the minimum decoding error [epsilon]([E.sub.T], D). As another decoder, we can choose [GAMMA]([y]) such that [GAMMA]([y]) realizes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [absolute value of [x.sup.n]] is the number of appearances of 1 among n entries. This decoder is called the minimum distance decoder. When [P.sub.Z](0) > [P.sub.Z](1), the maximum likelihood decoder is the same as the minimum distance decoder. We denote the minimum distance decoder by [D.sub.K,min]. This type of code is often called an error correcting code.

When most of the entries of the parity check matrix K are zero, the parity check matrix K is called an LDPC matrix. When the subspace C is given as the kernel of an LDPC matrix, the code is called the LDPC code. In this case, it is known that a good decoder can be realized with a small calculation complexity. (3,4) Hence, an LDPC code is used for practical purposes.

III. Information transmission via quantum coding

To discuss the information transmission problem, we eventually need to address the properties of the physical media carrying the information. When we approach the ultimate limit of the information transmission rate as a theoretical problem, we need to consider the case when individual particles express each bit of information. That is, we focus on the information transmission rate under such an extreme situation. To realize the ultimate transmission rate, we need to use every photon (or every pulse) to describe one piece of information. Since the physical medium used to transmit the information behaves quantum mechanically under such conditions, the description of the information system needs to reflect this quantum nature.

Several researchers, such as Takahasi, (19) started to consider the limit of optical communication in the 1960s. In 1967, Helstrom (20,21) started to systematically formulate this problem as a new type of information processing system based on quantum theory instead of an information transmission system based on classical mechanical input and output, which obeys conventional probability theory. The study of information transmission based on such quantum media is called quantum information theory. In particular, research on channel coding for quantum media is called quantum channel coding. In contrast, information theory based on the conventional probability theory is called classical information theory when we need to distinguish it from quantum information theory, even when the devices employ quantum effects in their insides, because the input and the output are based on classical mechanics. Quantum information theory in its earlier stage has been studied more deeply by Holevo and is systematically summarized in his book (22) in 1980.

Here, we point out that current optical communication systems are treated in the framework of classical information theory. However, optical communication can be treated in both classical and quantum information theory as follows (Figs. 2 and 3). Because the framework of classical information theory cannot deal with a quantum system, to consider optical communication within classical information theory, we need to fix the modulator converting the input signal to the input quantum state and the detector converting the output quantum state to the outcome, as shown in Fig. 2. Once we fix these, we have the conditional distribution connecting the input and output symbols, which describes the channel in the framework of classical information theory. That is, we can apply classical information theory to the classical channel. The encoder is the process converting the message (to be sent) to the input signal, and the decoder is the process recovering the message from the outcome.

On the other hand, when we discuss optical communication within the framework of quantum information theory as shown in Fig. 3, we focus on the quantum channel, whose input and output are given as quantum states. When the quantum system is characterized by the Hilbert space H, a quantum state is given as a density matrix [rho] on H, which is a positive-semi definite matrix with trace 1. Within this framework, we combine a classical encoder and a modulator into a quantum encoder, in which the message is directly converted to the input quantum state. Similarly, we combine a classical encoder and a detector into a quantum decoder, in which the message is directly recovered from the output quantum state. Once the optical communication is treated in the framework of quantum information theory, our coding operation is given as the combination of a quantum encoder and a quantum decoder. This framework allows us to employ physical processes across multiple pulses as a quantum encoder or decoder, so quantum information theory clarifies how much such a correlating operation enhances the information transmission speed. It is also possible to fix only the modulator and discuss the combination of a classical encoder and a quantum decoder, which is called classical-quantum channel coding, as shown in Fig. 4. A classical-quantum channel is given as a map from an element x of the input classical system X to an output quantum state [[rho].sub.x], which is given as a density matrix on the output quantum system H.

Here, we remark that the framework of quantum information theory mathematically contains the framework of classical information theory as the commutative special case, that is, the case when all [[rho].sub.x] commute with each other. This character is in contrast to the fact that a quantum Turing machine does not contain the conventional Turing machine as the commutative special case. Hence, when we obtain a novel result in quantum information theory and it is still novel even in the commutative special case, it is automatically novel in classical information theory. This is a major advantage and became a driving force for later unexpected theoretical developments.

A remarkable achievement of the early stage was made by Holevo in 1979, who obtained a partial result for the classical-quantum channel coding theorem. (23,24) However, this research direction entered a period of stagnation in the 1980s. In the 1990s, quantum information theory entered a new phase and was studied from a new viewpoint. For example, Schumacher introduced the concept of a typical sequence in a quantum system. (25) This idea brought us new developments and enabled us to extend data compression to the quantum setting. (25) Based on this idea, Holevo (26) and Schumacher and Westmoreland (27) independently proved the classical-quantum channel coding theorem, which had been unsolved until that time.

Unfortunately, a quantum operation in the framework of quantum information theory is not necessarily available with the current technology. Hence, these achievements remain more theoretical than classical channel coding theorem. However, such theoretical results have, in a sense, brought us more practical results, as we shall see later.

Now, we give a formal statement of the quantum channel coding theorem for the classical-quantum channel x [??] [[rho].sub.X]. For this purpose, we introduce the von Neumann entropy H([rho]) := - Tr [rho] log [rho] for a given density matrix [rho]. It is known that the von Neumann entropy is also concave just as in the classical case. When we employ the same classical-quantum channel n times, the total classical-quantum channel is given as a map [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. While an encoder is given as the same way as the classical case, a decoder is defined in a different way because it is given by using a quantum measurement on the output quantum system H. The most general description of a quantum measurement on the output quantum system H is given by using a positive operator-valued measure [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], in which, each [[PI].sub.m] is a positive-semi definite matrix on H and the condition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds. As explained in [35, (4.7)][115, (8.48)], the decoding error probability is given as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, we can define the maximum transmission size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the other hand, the mutual information is defined as I ([P.sub.X], [rho]) := H ([[summation].sub.x][P.sub.X](x)[[rho].sub.x]) - [[summation].sub.x][P.sub.X] (x)H([[rho].sub.x]). So, the maximum transmission rate is characterized by the quantum channel coding theorem as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [5]

To characterize the mutual information I([P.sub.X], [rho]), we denote the classical system X by using the quantum system [H.sub.X] spanned by |x> and introduce the density matrix [[rho].sub.XY] := [[summation].sub.x [member of] X] [P.sub.X](x) |x><x| [[rho].sub.x] on the joint system [H.sub.X] [cross product] H and the density matrix [[rho].sub.Y] := [[summation].sub.x [member of] X] [P.sub.X](x)[[rho].sub.X] on the quantum system H. In this notation, we regard [P.sub.X] as the density matrix [[summation].sub.x [member of] X][P.sub.X](x)[absolute value of x><x] on [H.sub.X]. Using the quantum relative entropy D([rho] [parallel] [sigma]) := Tr [rho](log [rho] - log [sigma]) between two density matrices [rho] and [sigma], the mutual information is written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [6]

So, the capacity is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [7]

Here, it is necessary to discuss the relation between classical and quantum information theory. For this purpose, we focus on information transmission via communication on an optical fiber. When we employ coding in classical information theory, we choose a code based on classical information devices, which are the input and the output of the classical channel shown in Fig. 2. In contrast, when we employ coding in quantum information theory, we choose a code based on quantum information devices, which are the input and the output of the quantum channel shown in Fig. 3. In the case of Fig. 4, we address the classical-quantum channel so that we focus on the output system as a quantum information device. That is, the choice between classical and quantum information theory is determined by the choice of a classical or quantum information device, respectively.

IV. Information spectrum

The early stage of the development of finite block-length studies started from a completely different motivation and used the information spectrum method introduced by Han and Verdu. (28,31) Conventional studies in information theory usually impose the iid or memoryless condition on the information source or the channel. However, neither the information source nor the channel is usually independent in the actual case and they often have correlations. Hence, information theory needed to be adapted for such a situation.

To resolve such a problem, Verdu and Han have discussed optimal performance in the context of several topics in classical information theory, including channel coding, by using the behavior of the logarithmic likelihood, as shown in Fig. 5. (30) However, they have discussed only the case when the block-length n approaches infinity, and have not studied the case with finite block-length. It is notable that this study clarified that the analysis of the iid case can be reduced to the law of large numbers. In this way, the information spectrum method has clarified the mathematical structures of many topics in information theory, which has worked as a silent trigger for further developments.

Another important contribution of the information spectrum method the connection of simple statistical hypothesis testing to many topics in classical information theory. (31) Here, simple statistical hypothesis testing is the problem of deciding which candidate is the true distribution with an asymmetric treatment of two kinds of errors when two candidates for the true distribution are given. In particular, the information spectrum method has revealed that the performances of data compression and uniform random number generation are given by the behavior of the logarithmic likelihood.

Here, we briefly discuss the idea of the information spectrum approach in the case of uniform random number generation. Let [X.sub.n] be the original system, where n is an index. The product set [X.sup.n] is a typical example of this notation. In uniform random number generation, we prepare another set [y.sub.n], in which, we generate an approximate uniform random number [Y.sub.n]. In this formulation, we focus on the initial distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on [X.sub.n]. Then, our operation is given as a map [[phi].sub.n] from [X.sub.n] to [Y.sub.n]. The resultant distribution on [Y.sub.n] is given as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. To discuss the quality of the resultant uniform random number, we employ the uniform distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the error of the operation [[phi].sub.n] is given as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now we define the maximum size of the uniform random number with error [epsilon] as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Vembu and Verdu [29, Section V] showed that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [8]

This fact shows that the generation rate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is essentially described by the random variable - [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When [X.sub.n] is [X.sup.n] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the iid distribution [P.sup.n.sub.X] of [P.sub.X], the random variable [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges to the entropy H([P.sub.X]) in probability due to the law of large numbers. In the iid case, the generation rate equals the entropy H([P.sub.X]).

In the channel coding case, we focus on a general conditional distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the channel. Then, Verdu and Han (30) derived the maximum transmission rate as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [9]

Although we can derive the formula [1] from this general formulation, it is not so easy because the above formula contains the maximization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of the input distribution on the large system [X.sub.n]. When the channel [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given as the additive channel with the additive noise distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the above formula can be simplified as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [10]

Note that [Z.sub.n] is the same set as [X.sub.n] and [y.sub.n] when the channel is additive.

As already mentioned, the information spectrum approach was started as a result of a motivation different from the above. When Han and Verdu (28) introduced this method, they considered identification codes, which were initially introduced by Ahlswede and Dueck. (137) To resolve this problem, Han and Verdu introduced another problem--channel resolvability--which discusses the approximation of a given output distribution by the input uniform distribution on a small subset. That is, they consider

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [11]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [12]

where [[phi].sub.n] is chosen as a function from [T.sub.n] to [X.sub.n]. They showed that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [13]

By considering this problem, they introduced the new concept of channel resolvability, which later played an important role in a completely different topic.

In the next stage, Nagaoka and the author extended the information spectrum method to the quantum case. (32,33) In this extension, their contribution is not only the non-commutative extension but also the redevelopment of information theory. In particular, they have given a deeper clarification of the explicit relation between simple statistical hypothesis testing and channel coding, which is called the dependence test bound in the later study [33, Remark 15]. In this context, Nagaoka (34) has developed another explicit relation between simple statistical hypothesis testing and channel coding, which is called the meta converse inequality [1]. These two clarifications of the relation between simple statistical hypothesis testing and channel coding work as a preparation for the next step of finite-length analysis.

Now, to grasp the essence of these contributions, we revisit the classical setting because the quantum situation is more complicated. To explain the notation of classical hypothesis testing, we consider testing between two distributions [P.sub.1] and [P.sub.0] on the same system X. Generally, our testing method is written by using a function T from X to [0,1] as follows. When we observe x [member of] X, we support [P.sub.1] with the probability T(x), and support [P.sub.0] with the probability 1 - T(x). When the function T takes values only in {0,1}, our decision is deterministic. In this problem, we have two types of error probability. The first one is the probability for erroneously supporting [P.sub.1] while the true distribution is [P.sub.0], which is given as [alpha](T|[P.sub.0] [parallel] [P.sub.1]) := [[summation].sub.x [member of] X] T(x)[P.sub.0](x). The second one is the probability for erroneously supporting [P.sub.0] while the true distribution is [P.sub.1], which is given as [beta](T|[P.sub.0] [parallel] [P.sub.1]) := [[summation].sub.x [member of] X](1 - T(x))[P.sub.1](x). Then, we consider the minimum second error probability under the constraint of a constant probability for the first error as [beta]([epsilon]|[P.sub.0] [parallel] [P.sub.1]) := [min.sub.T]{[beta](T|[P.sub.0] [parallel] [P.sub.1])|[alpha](T|[P.sub.0] [parallel] [P.sub.1]) [less than or equal to] [epsilon]}.

To overcome the problem with respect to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [9], for a given channel [P.sub.Y|X], Nagaoka (34) derived the meta converse inequality:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [14]

for any distribution [Q.sub.Y] on Y.

Also, the author and Nagaoka derived the dependence test bound as follows [33, Remark 15]. For a given distribution on [P.sub.X] on X and a positive integer N, there exists a code (E, D) such that [absolute value of (E,D)] = N [2]

[epsilon](E, D) [less than or equal to] [epsilon] + N[beta]([epsilon]|[P.sub.XY] [parallel] [P.sub.X] x [P.sub.Y]). [15]

That is, for any [delta] > 0 and [epsilon] > 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [16]

Here, [16] follows from [15] by putting [delta] = N[beta]([epsilon]|[P.sub.XY] [parallel] [P.sub.X] x [P.sub.Y]).

Then, using [16], the author and Nagaoka derived the [greater than or equal to] part of [9] including the quantum extension. Also, using [14], the author and Nagaoka derived another expression for [9]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [17]

While [17] seems more complicated than [9], [17] is more useful for proving the impossibility part for the following reason. In [9], the distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a complicated form in general. Hence, it is quite difficult to evaluate the behavior of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When we derive the upper bound of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it is enough to consider the case with a special [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. That is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be chosen to be a distribution for iid random variables so that the random variable [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be factorized. Then, the impossibility part of the channel coding theorem can be easily shown via [17].

Indeed, since the classical case is not so complicated, it is possible to recover several important results from [9]. However, use of the formula [17] is needed in the quantum case because everything becomes more complicated.

V. Folklore in source coding

When the information source is subject to the iid distribution [P.sup.n.sub.X] of [P.sub.X], the compression rate and the uniform random number generation rate have the same value of H([P.sub.X]) asymptotically. Hence, we can expect that the data compressed up to the entropy rate H([P.sub.X]) would be the uniform random number. However, this argument does not work as a proof of the statement, so this conjecture has the status of folklore in source coding, and its validity remained unconfirmed for a long time.

Han (36) tackled this problem by using the method of information spectrum. Han focused on the normalized relative entropy [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the criterion to measure the difference of the generated random number from a uniform random number, and showed that the folklore in source coding is valid. (36) However, the normalized relative entropy is too loose a criterion to guarantee the quality of the uniform random number because it is possible to distinguish a generated random number from a truly uniform random number even though the random number is considered to be uniform by this criterion. In particular, when a random number is used for cryptography, we need to employ a more rigorous criterion to judge the quality of its uniformity.

In contrast, the criterion [gamma]([[phi].sub.n]) is the most popular criterion which gives the statistical distinguishability between a truly uniform random number and a given random number. (37) That is, when this criterion takes the value 0, the random number must be truly uniform. Hence, when we use a random number for cryptography, we need to accept only a random number passing this criterion. Also, Han (36) has proved that the folklore conjecture in source coding is not valid when we adopt the variational distance as our criterion.

On the other hand, to clarify the incompatibility between data compression and uniform random number generation, the author (8) developed a theory for finite-block-length codes for both topics. In this analysis, he applied the method of information spectrum to the second-order [square root of n] term, as shown in Fig. 5. That is, by using the varentropy V([P.sub.X]) := [[summation].sub.x [member of] X] [P.sub.X](x)(- log [P.sub.X](x) - H([P.sub.X])) (2), the central limit theorem guarantees that

[P.sup.n.sub.X]{[x.sup.n] [member of] [X.sup.n]|(log [P.sup.n.sub.X]([x.sup.n]) - nH([P.sub.X]))/[square root of n] [less than or equal to] [epsilon]} = [square root of (V([P.sub.X])] [[PHI].sup.-1]([epsilon]), [18]

where the cumulative distribution function [PHI] of the standard Gaussian distribution is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the generation length log S([epsilon]|[P.sup.n.sub.X]) is asymptotically expanded as

log S([epsilon]|[P.sup.n.sub.X]) = nH ([P.sub.X] ) + [square root of n] [square root of (V[P.sub.X])][[PHI].sup.-1]([epsilon]) + o([square root of n]). [19]

Now, we consider data compression, in which we define the minimum compressed size R([epsilon]|[P.sup.n.sub.X]) with decoding error [epsilon] in the same way. Then, the asymptotic expansion is (5,8)

log R([epsilon]|[P.sup.n.sub.X]) = nH ([P.sub.X]) - [square root of n] [square root of ([P.sub.X])][[PHI].sup.-1]([epsilon]) + o([square root of n]). [20]

That is, when the converted length has the asymptotic expansion nH([P.sub.X]) - [square root of n][square root of (V([P.sub.X])]R, the errors of both settings are illustrated in Fig. 6.

Now, we fix the conversion rate up to the second-order 1/[square root of n]. When we apply an operation from the system [X.sup.n] to a system with size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the sum of the errors of the data compression and the uniform random number generation almost equals to 1. This trade-off relation shows that data compression and uniform random number generation are incompatible to each other. Indeed, since the task of data compression has the direction opposite to that of uniform random number generation, the second-order analysis explicitly clarifies that there is a trade-off relation for their errors rather than compatibility.

Although the evaluation of optimal performance up to the second-order coefficient gives an approximation of the finite-length analysis, it also shows the existence of their trade-off relation. This application shows the importance of the second-order analysis. Because the evaluation of the uniformity of a random number is closely related to security, this type evaluation has been applied to security analysis. (38) This trade-off relation also plays an important role when we use the compressed data as the scramble random variable for another piece of information. (39)

VI. Quantum cryptography

A. Single-photon pulse without noise. Section III has explained that the problem of the ultimate performance of optical communication can be treated as quantum channel coding. When the communication media has quantum properties, it opens the possibility of a new communication style that cannot be realized with the preceding technology. Quantum cryptography was proposed by Bennett and Brassard (40) in 1984 as a technology to distribute secure keys by using quantum media. Even when the key is eavesdropped during the distribution, this method enables us to detect the existence of the eavesdropper with high probability. Hence, this method realizes secure key distribution, and is called quantum key distribution (QKD).

Now, we explain the original QKD protocol based on single-photon transmission. In the QKD, the sender, Alice, needs to generate four kinds of states in the two-dimensional system [C.sup.2], namely, |0>, |1>, and |[+ or -]> := 1/[square root of 2] (|10> [+ or -] |1>) [3]. Here, {|10>, |1>} is called the bit basis, and { |[+ or -]>} is called the phase basis. Also, the receiver, Bob, needs to measure the received quantum state by using either the bit basis or the phase basis.

The original QKD protocol (40) is the following.

(1) [Preparation] Alice randomly chooses one of four states, and sends it to Bob.

(2) [Transmission] Bob randomly chooses one of two bases, and measures the received state using the chosen basis. Alice and Bob repeat Steps (1) and (2) several times.

(3) [Detection] Alice and Bob exchange their basis information via a public channel, and they discard bits with disagreed bases.

(4) [Error check] Alice and Bob randomly choose check bits from among the remaining bits, and they exchange their values via a public channel. If they find an error, they stop the protocol because the error might be caused by eavesdropping. Otherwise, they use the remaining bits as keys, which are called raw keys.

In this protocol, if the eavesdropper, Eve, performs a measurement during transmission, the quantum state would be destroyed with non-negligible probability because she does not know the basis of the transmitted quantum state a priori. When the number of qubits measured by Eve is not so small, Alice and Bob will find disagreements in step (4). So, the existence of eavesdropping will be discovered by Alice and Bob with high probability.

B. Random hash functions. The original protocol supposes noiseless quantum communication by a single photon. So, the raw keys are not necessarily secure when the channel has noise. To realize secure communication even with a noisy channel, we need a method to generate secure keys from keys partially leaked to Eve. Such a process is called privacy amplification. In this process, we apply a hash function, which maps from a larger set to a smaller set. In the security analysis, we often employ a hash function whose choice is determined by a random variable (a random hash function). A typical class of random hash functions is the following class. A random hash function [f.sub.R] from [F.sup.n.sub.2] to [F.sup.m.sub.2] is called [universal.sub.2] (64,65) when

Pr{[f.sub.R](x) = [f.sub.R](x')} [less than or equal to] [2.sup.-m] [21]

for distinct elements x and x' in [F.sup.n.sub.2]. A typical example of a surjective [universal.sub.2] hash function is the concatenated Toeplitz matrix, which is given as follows. When an m x (n - m) matrix [T.sub.R] = ([T.sub.i,j]) is given as [T.sub.i,j] = [R.sub.i+j-i] by using n - 1 random variables [R.sub.j], it is called a Toeplitz matrix. Let T = {[T.sub.R]|r [member of] I} be the set of all m x (n - m) Toeplitz matrices. Then let [M.sub.r] = ([T.sub.R], [I.sub.m]) be an m x n matrix defined by a concatenation of [T.sub.R] and the m-dimensional identity matrix [I.sub.m]. Then, the concatenated Toeplitz matrix [M.sub.R] maps an input x [member of] [F.sup.n.sub.2] to the output y = [M.sub.r]x [member of] [F.sup.m.sub.2]. The concatenated Toeplitz matrix [M.sub.R] is [universal.sub.2] when R is a uniform random number. (For a proof, see, e.g., [96, Appendix II].)

This class can be relaxed as follows. A random hash function [f.sub.R] from [F.sup.n.sub.2] to [F.sup.m.sub.2] is called [delta]-almost [universal.sub.2] when

Pr{[f.sub.R](x) = [f.sub.R](x')} [less than or equal to] [delta][2.sup.-m] [22]

for distinct elements x and x' in [F.sup.n.sub.2]. Here, Pr{C} expresses the probability that the condition C holds. When [delta]=1, it is [universal.sub.2]. Here, R denotes the random variable identifying the hash function. When a random hash function [f.sub.R] is linear, it is [delta]-almost [universal.sub.2] if and only if

Pr{x [member of] Ker [f.sub.R]} [less than or equal to] [delta][2.sup.-m] [23]

for any non-zero element x [member of] [F.sup.n.sub.2]. Here, Ker f is the kernel of the linear function f. Considering the space [(Ker f).sup.[perpendicular to]] orthogonal to Ker f in [F.sup.n.sub.2], we introduce another class of random hash functions. A linear random surjective hash function [f.sub.R] from [F.sup.n.sub.2] to [F.sup.m.sub.2] is called [delta]-almost dual [universal.sub.2] when

Pr{x [member of] [(Ker [f.sub.R]).sup.[perpendicular to]] L} [less than or equal to] [delta][2.sup.-n+m] [24]

for any non-zero element x [member of] [F.sup.n.sub.2]. As examples of [delta]-almost dual universal hash functions, the paper (56) proposed hash functions whose calculation complexity and random seeds are smaller than existing functions for practical use, as shown in Fig. 7.

When R is not a uniform random number the above concatenated Toeplitz matrix [M.sub.R] is not [universal.sub.2]; fortunately, it is [delta]-almost dual [universal.sub.2]. So, we can evaluate security in the framework of [delta]-almost dual [universal.sub.2] hash functions. That is, for a realistic setting, the concept of [delta]-almost dual [universal.sub.2] works well. Note that there exists a 2-almost [universal.sub.2] hash function whose resultant random number is insecure (Fig. 7). Hence, the concept of [delta]-almost dual universal is more useful than [delta]-almost [universal.sub.2].

C. Single-photon pulse with noise. To realize the security even with a noisy quantum channel, we need to modify the original QKD protocol. Since this modified protocol is related to error correction, finite-length analysis plays an important role to guarantee the security of the real QKD system. Here, for simplicity, we discuss only the finite-length security analysis with the Gaussian approximation.

The modified QKD protocol is the following. Steps (1), (2), and (3) are the same as in the original.

(4) [Error estimation] Alice and Bob randomly choose check bits from among the remaining bits, and they exchange their values via a public channel.

(*) In the following, we give a protocol for the bit basis. Here, we denote the number of remaining bits with the bit basis measurement by n, and we denote the numbers of check bits with the phase and bit basis measurements by l and l'. We denote the numbers of observed errors among check bits in the phase and bit basis measurements by c and c'.

(5) [Error correction] Alice and Bob apply error correction based on a k-dimensional subspace C and obtain k corrected bits. That is, Alice sends her syndrome to Bob via a public channel, and Bob corrects his error. Here, the length k and a code C are chosen by the observed error rate c'/l' with the bit basis measurement.

(6) [Privacy amplification] Alice and Bob apply a [delta]-almost dual [universal.sub.2] hash function from [F.sup.k.sub.2] to [F.sup.k-[bar.k].sub.2]. This protocol sacrifices [bar.k] bits, which is called the sacrifice bit length and is determined by the observed error rate c/l with the phase basis measurement. Then, Alice and Bob obtain final keys with length s := k - [bar.k].

To perform the finite-length security analysis approximately, we consider the following items.

(i) The virtual decoding phase error probability of a code C with an arbitrary decoder gives the amount of leaked information with privacy amplification by a hash function whose kernel is [C.sup.[perpendicular to]]. In this correspondence, the privacy amplification in the bit basis by a [delta]-almost dual [universal.sub.2] hash function [F.sup.k.sub.2] to [F.sup.k-k.sub.2] essentially realizes an error correction code in the phase basis whose parity check matrix is a [delta]-almost [universal.sub.2] hash function from [F.sup.n.sub.2] to [F.sup.[bar.k].sub.2]; [52, Lemmas 2 & 4][54, Theorem 2][57, (54)][115, Section 9.4.3][116, Section 5.6.2] [4].

(ii) When the total number of bits is n d l, the total number of errors is b, and we randomly choose l bits as the observed bits, the number of observed errors c is subject to the hypergeometric distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the value (c - lb/n+l]) / [square root of l] approximately obeys the Gaussian distribution with variance bn(n+l-b)/[(n+l).sup.2](n+l-1)].

(iii) When the parity check matrix is given by a [delta]-almost [universal.sub.2] hash function from [F.sup.n.sub.2] to [F.sup.[bar.k].sub.2], the decoder is the minimum distance decoder, and the support of the distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of errors on [F.sup.n.sub.2] is included in the set {[x.sup.n] [member of] [F.sup.n.sub.2][parallel][x.sup.n]| = b - c}, the average decoding error probability is evaluated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [25]

where [E.sub.R] denotes the expectation with respect to the random variable R [52, Lemma 1][54, Theorem 3] [57, (37)].

(iv) The real distribution of error in the phase basis for n remaining qubits with the bit basis measurement and l check qubits with the phase basis measurement (n + l qubits in total) is written as a probabilistic mixture of distributions [P.sub.[bar.k]], where [P.sub.[bar.k]] is a distribution on {[x.sup.n] [member of] [F.sup.n+l.sub.2][parallel] [x.sup.n]|] = [bar.k]} [52, Section IV-B][54, Section III-C|[53, (18)]. (Any distribution on [F.sup.n.sub.2] satisfies this condition. In the memoryless case, the coefficients form a binomial distribution.)

To give our security criterion, we denote the information transmitted via the public channel by u, and introduce its distribution [P.sub.pub]. Depending on the public information u, we denote the state on the composite system of Alice's and Eve's systems, the state on Alice's system, the state on Eve's system, and the length of the final key length by [[rho].sub.A,E|u], [[rho].sub.A|u], [[rho].sub.E|u], and s(u), respectively. We denote the completely mixed state with length s(u) by [[rho].sub.A,mix|s(u)]. Then, similar to the security criterion is given in [53, (3)]

[1/2] [summation over u][P.sub.pub](u)[[parallel][[rho].sub.A,E|u] - [[rho].sub.A,mix|s(u)] [cross product] [[rho].sub.E|u][parallel].sub.1] [26]

Now, as a security condition, we impose the condition that [26] is smaller than [epsilon].

Combining the above four items, depending on c, we can derive the sacrifice bit length [bar.k](c). Although the exact formula of [bar.k](c) is complicated, it can be asymptotically expanded as [53, (53)]

[bar.k](c)=nh(c/l) - [square root of n]/2 h'(c/l)[square root of (c/l(1 - c/l)(1 + l/n)[n/l])] [[PHI].sup.-1]([epsilon].sup.2]/2) + o([square root of n]). [27]

Here, we should remark that this security analysis does not assume the memoryless condition for the quantum channel. To avoid this assumption, we introduce a random permutation and the effect of random sampling, which allows us to consider that the errors in both bases are subject to the hyper-geometric distribution. However, due to the required property of hash functions, we do not need to apply the random permutation in the real protocol. That is, we need to apply only random sampling to estimate the error rates of the phase basis.

Here, we need to consider the reliability, that is, the agreement of the final keys. For this purpose, we need to attach a key verification step as follows [122, Section VIII].

(7) [Key verification] Alice and Bob apply a [universal.sub.2] hash function from [F.sup.k-[bar.k].sub.2] to [F.sup.[??].sub.2] to the final keys. They exchange their results via a public channel. They discard their final [??] bits if they do not agree. Otherwise, they consider that their remaining keys agree.

However, the amount of leaked information for the final keys cannot be estimated by a similar method. So, the security analysis is more important than the agreement of the keys.

D. Weak coherent pulse with noise. Next, we discuss a weak coherent pulse with noise, whose device is illustrated in Fig. 8. Since the above protocol assumes single-photon pulses, when the pulse contains multiple photons even occasionally, the above protocol cannot guarantee security. Since it is quite difficult to generate a single-photon pulse, we usually employ weak coherent pulses with phase randomization, whose states are written as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [micro] is called the intensity. That is, weak coherent pulses contain multiple-photon pulses, as shown in Fig. 9. In this case, there are several multiple-photon pulses among n received pulses. In optical communication, only a small fraction of pulses arrive at the receiver side. That is, the ratio of multiple-photon states of Alice's side is different from that of Bob's side. This is because the detection ratio on Bob's side depends on the number of photons.

As the first step in the security analysis, we need to estimate the ratios of vacuum pulses, single-photon pulses, and multiple-photon pulses among n received pulses. Indeed, there is a possibility that Bob erroneously detects the pulse even with a vacuum pulse. To obtain this estimate, we remark that the ratio of multiple-photon pulses depends on the intensity [mu]. Hence, it is possible to estimate the detection ratios of vacuum pulses, single-photon pulses, and multiple-photon at Bob's side from the detection ratios of more than 3 different intensities, which are obtained by solving simultaneous equations. (44-50,113) Observing the error rate of each pulse depending on the intensity and the basis, we can estimate the error rates of both bases for vacuum pulses, single-photon pulses, and multiple-photons. This idea is called the decoy method. Based on this discussion, we change steps (1), (2), (3), and (4). However, we do not need to change steps (5) and (6), in which we choose the error correcting code and the sacrifice bit length.

As the second step of the security analysis, when n received pulses are composed of [n.sub.0] vacuum pulses, [n.sub.1] single-photon pulses, and [n.sub.2] multiple-photon pulses, we need to estimate the leaked information after the privacy amplification with sacrifice bit length [bar.k]. In the current case, we replace items (i) and (iii) by the following.

(i') When n received pulses are composed of [n.sub.0] vacuum pulses, [n.sub.1] single-photon pulses, and [n.sub.2] multiple-photon pulses, then, [n.sub.0] vacuum pulses are converted to noiseless single-photon pulses and [n.sub.2] multiple-photon pulses are converted to noiseless single-photon pulses whose error distribution is the uniform distribution [54, Section III-B]. Then, we have the same statement as (i).

(iii') Assume that the parity check matrix is given by a [delta]-almost [universal.sub.2] hash function from [F.sup.n.sub.2] to [F.sup.[bar.k].sub.2] We also make an assumption for the distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; [n.sub.0] bits have no error, there are [t.sub.1] errors among the [n.sub.1] bits, and the distribution of errors on the [n.sub.2] bits is the uniform distribution. So, the decoder [GAMMA]([y]) is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [28]

where (*) is the condition that all of entries among the above [n.sub.0] bits are 0, and [parallel] [x.sup.n] [parallel] is the number of bits with entry 1 among the above [n.sub.1] bits. Then, the average decoding error probability is evaluated as [54, Theorem 3]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [29]

Finally, we combine the original items (ii) and

(iv) with the above modified items (i') and (iii'). However, due to the complicated estimation process for the partition [n.sub.0], [n.sub.1], [n.sub.2] of n qubits, we need a very complicated discussion. Based on such an analysis, after long calculation, we obtain a formula for the sacrifice bit length, as shown in Fig. 10.

E. History of developments of QKD. Because the raw keys are not necessarily secure when the channel has noise or two photons are transmitted, many studies have been done to find a way to guarantee security when the communication device has such imperfections. For this purpose, we need to consider a partial information leakage whose amount is bounded by the amount of the imperfection. Shor and Preskill (41) and Mayers (42) showed that privacy amplification generates secure final keys even when the channel has noise when the light source correctly generates a singlephoton. Gottesman et al. (43) showed that these final keys can be secure even when the light source occasionally generates multiple photons if the fraction of multiple photon pulses is sufficiently is small. The light source used in the actual quantum optical communication is the weak coherent light, which probabilistically generates some multiple photon pulses, as shown in Fig. 9. Hence, this kind of extension had been required for practical use. Hwang (44) proposed an efficient method to estimate the fraction of multiple photon pulses, called the decoy method, in which the sender randomly chooses pulses with different intensities.

Until this stage, the studies of QKD were mainly done by individual researchers. However, project style research is needed for a realization of QKD because the required studies need more interactions between theorists and experimentalists. A Japanese project, the ERATO Quantum Computation and Information Project, tackled the problem of guaranteeing the security of a real QKD system. Since this project contained an experimental group as well as theoretical groups, this project naturally proceeded to a series of studies of QKD from a more practical viewpoint. First, one project member, Hamada (109,110) studied the relation between the quantum error correcting code and the security of QKD more deeply. Then, another project member, Wang (46,48) extended the decoy method, which was developed independently by a group at Toronto University. (45,47) Tsurumaru (50) and the author (49) have further extended the method. These extended decoy methods give a design for the choice of the intensity of transmitted pulses. Further, jointly with the Japanese company NEC, the experimental group demonstrated QKD with spools of standard telecom fiber over 100 km. (111)

Here, we note that the theoretical results above assume the combination of error correction and privacy amplification for an infinitely large block-length in steps (5) and (6). They did not give a quantitative evaluation of the security with finite-block-length. They also did not address the construction of privacy amplification so these results are not sufficient for realization of a quantum key distribution system. To resolve this issue, as a member of this project, the author (52) approximately evaluated the security with finite-block-length n when the channel has noise and the light source correctly generates a single photon. This idea has two key points. The first contribution is the evaluation of information leakage via the phase error probability of virtual error correction in the phase basis, which is summarized as item (i). This evaluation is based on the duality relation in quantum theory, which typically appears in the relation between position and momentum. The other contribution is the approximate evaluation of the phase error probability via the application of the central limit theorem, which is obtained by the combination of items (iii) and (iv). This analysis is essentially equivalent to the derivation of the coefficient of the transmission rate up to the second-order 1/[square root of n]. However, this analysis assumed a single-photon source. Under this assumption, the author discussed the optimization for the ratio of check bits. (112) Based on a strong request from the project leader of the ERATO project and helpful suggestions by the experimental group, using the decoy method, he extended a part of his analysis to the case when the light source sometimes generates multiple photons (54) by replacing item (iv) by (iv'). Based on this analytical result, the ERATO project made an experimental demonstration of QKD with weak coherent pulses on a real optical fiber, whose security is quantitatively guaranteed in the Gaussian approximation. (51)

Another Japanese project of the National Institute of Information and Communication Technology (NICT) has continuously made efforts toward a realization of QKD. After the ERATO project, the author joined the NICT project from 2011 to 2016. The NICT organized a project in Tokyo (Tokyo QKD Network) by connecting QKD devices operated by NICT, NEC, Mitsubishi Electric, NTT, Toshiba Research Europe, ID Quantique, the Austrian Institute of Technology, the Institute of Quantum Optics and Quantum Information and the University of Vienna in 2010. (59) Also, as a part of the NICT project, NEC developed a QKD system, as shown in Fig. 8, and performed a long-term evaluation experiment in 2015. (58)

After the above ERATO project, two main theoretical problems remained, and their resolutions had been strongly required by the NICT project because they are linked to the security evaluation of these installed QKD systems. The first one was the complete design of privacy amplification. Indeed, in the above security analysis based on the phase error probability, the range of possible random hash functions was not clarified. That is, only one example of a hash function was given in the paper, (54) and we had only a weaker version of item (ii) at that time. To resolve this problem, as members of the NICT project, Tsurumaru and the author clarified what kind of hash functions can be used to guarantee the security of a QKD system, (57) which yields the current item (ii). They introduced [delta]-almost dual [universal.sub.2] hash functions, as explained in Section VI-B. In these studies, Tsurumaru taught the author the practical importance of the construction of hash functions from an industrial viewpoint based on his experience obtained as a researcher at Mitsubishi Electric.

The second problem was to remove the Gaussian approximation in (52) from the finite-length analysis. Usually, security analysis requires rigorous evaluation without approximation. Hence, this requirement was essential for the security evaluation. In Hayashi and Tsurumaru, (53) we succeeded in removing this approximation and obtained a rigorous security analysis for the single-photon case. Also, the paper (53) clarified the security criterion and simplified the derivation in the discussion given in Subsection VI-C. Based on a strong request by the NICT project, the author extended the finite-length analysis to the case with multiple photons by employing the decoy method and performing a complicated statistical analysis. (55) The transmission rate in the typical case is shown in Fig. 10. This study clarified the requirements for physical devices to apply the obtained security formula. In this study, (55) the author also improved an existing decoy protocol. Under the improved protocol, he optimizes the choice of intensities. (113) Finally, we should remark that only such a mathematical analysis can guarantee the security of QKD. This is quite similar to the situation that conventional security measures, like RSA, can be guaranteed by mathematical analysis of the computational complexity. (108) In this way QKD is different from conventional communication technology.

Here, we should address the security analysis based on the leftover hash lemma (62,63) as another research stream of QKD. This method came from cryptography theory and was started by the Renner group at the Swiss Federal Institute of Technology in Zurich (ETH). (66) The advantage of this method is the direct evaluation of information leakage without needing to evaluate the virtual phase error probability. This method also enables a security analysis with finite-block-length. (67) However, their finite-block-length analysis is looser than our analysis in Hayashi and Tsurumaru (53) because their bound (67) cannot yield the second-order rate based on the central limit theorem whereas it can be recovered from the bound in Hayashi and Tsurumaru. (53) Further, while their method is potentially precise, it has very many parameters to be estimated in the finite-block-length analysis. Although their method improves the asymptotic generation rate, (114) the increase in the number of parameters to be estimated enlarges the error of channel estimation in the finite-length setting. Hence, they need to decrease the number of parameters to be estimated. In their finite-block-length analysis, they simplified their analysis so that only the virtual phase error probability has to be estimated. This simplification improves the approach based on the leftover hash lemma because it gives a security evaluation based on the virtual phase error probability more directly. However, this approach did not consider security with weak coherent pulses. As another merit, the approach based on the leftover hash lemma later influenced the security analysis in the classical setting. (76,96-99)

To discuss the future of QKD, we now describe other QKD projects. Several projects were organized in Hefei in 2012 and in Jinan in 2013. (60) In 2013, a US company, Battelle, implemented a QKD system for commercial use in Ohio using a device from ID Quantique. (61) Battelle has a plan to establish a QKD system between Ohio and Washington, DC, over a distance of 700km. (61) Also, in China, the Beijing-Shanghai project almost established a QKD system connecting Shanghai, Hefei, Jinan, and Beijing with over a distance of 2,000 km. (60) Indeed, these implemented QKD networks are composed of a collection of QKD communications over relatively short distance. However, quite recently, a Chinese group has succeeded in realizing a satellite for quantum communications. Since most of these developments are composed of networks of quantum communication channels, it is necessary to develop theoretical results to exploit the properties of quantum networks for a QKD system.

VII. Second-order channel coding

Now, we return to classical channel coding with the memoryless condition. In the channel coding, it is important to clarify the difference between the asymptotic transmission rate and the actual optimal transmission rate dependent on the block-length, as shown in Fig. 11. This is because many researchers had mistakenly thought that the actual optimal transmission rate equals the asymptotic transmission rate for a long time.

When the channel [P.sub.Y|X] is given as a binary additive noise subject to the distribution [P.sub.Z] and the channel [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the product distribution of the channel [P.sub.Y|X], the simple combination of [10] and [18] yields the asymptotic expansion of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [30]

because Eq. [10] does not contain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] like [9]. In the general case, using the formulas [16] or [9] with order [absolute value of n], we can derive the [greater than or equal to] part of the following inequality.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [31]

where V([P.sub.Y|X]) is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [32]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [33]

and the minimum and maximum are taken over the [P.sub.X] satisfying I([P.sub.X], [P.sub.Y|X]) = [max.sub.Q] I(Q, [P.sub.Y|X]). However, it is difficult to derive the [less than or equal to] part of inequality [32] by using [9] due to the maximization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To resolve this problem, we choose [P.sub.X] as the distribution realizing the minimum in [33] or the maximum in [32] and substitute [P.sup.n.sub.X] into [Q.sub.n] in the formula [17]. Then, we can derive the [less than or equal to] part of the inequality [31]. Although this expansion was firstly derived by Strassen (5) in 1962, this derivation is much simpler, which shows the effectiveness of the method of information spectrum.

The author applied this method to an additive white Gaussian noise channel and succeeded in deriving the second-order coefficient of its transmission rate, which had been unknown until that time; this was published in 2009. (9) In fact, he obtained only a rederivation of Strassen's result. When he presented this result in a domestic meeting, (69) Uyematsu pointed out Strassen's result. To go beyond Strassen's result, he applied this idea to the additive white Gaussian noise channel, and obtained the following expansion, which appears as a typical situation in wireless communication.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [34]

where M ([epsilon] | S, N) is the maximum size of transmission when the variance of the Gaussian noise is N and the power constraint is S.

In fact, a group in Princeton University, mainly Verdu and Polyanskiy, tackled this problem independently. In their papers, (6,7) they considered the relation between channel coding and simple statistical hypothesis testing, and independently derived two relations, the dependence test bound and the meta converse inequality, which are the same as in the classical special case considered in the author and Nagaoka (33) and Nagaoka. (34) Since their results (6) are limited to the classical case, the applicable region of their results is narrower than that of the preceding results in. (33,34) Then, Verdu and Polyanskiy rederived Strassen's result, without use of the method of information spectrum, by the direct evaluation of these two bounds. They also independently derived the second-order coefficient of the optimal transmission rate for the additive white Gaussian noise channel in 2010. (6) Since the result by this group at Princeton had a large impact in the information theory community at that time, their paper received the best paper award of IEEE Information theory society in 2011 jointly with the preceding paper by the author. (9)

As explained above, the Japanese group obtained some of the same results several years before the Princeton group but had much weaker publicity than the Princeton group. Thus, the Princeton group met the demand in the information theory community, and they presented their results very effectively. In particular, since their research activity was limited to the information theory community, their audiences were suitably concentrated so that they could create a scientific boom in this direction. In contrast to the Princeton group, the Japanese group studied the same topic far from the demand of the community because their study originated in quantum information theory. In particular, their research funds were intended for the study of quantum information so they had to present their work to quantum information audiences who are less interested in their results. Also, because their work was across too wide a research area to explain their results effectively, they could not devote sufficient efforts to explain their results to the proper audiences at that time. Hence, their papers attracted less attention. For example, few Japanese researchers knew the paper (9) when it received the IEEE award in 2011. After this award, this research direction became much more popular and was applied to very many topics in information theory. (10-14,17,71,72,76) In particular, the third-order analysis has been applied to channel coding. (15) These activities were reviewed in a recent book. (74)

Although this research direction is attracting much attention, we need to be careful about evaluating its practical impact. These studies consider finite-block-length analysis for the optimal rate with respect to all codes including those with too high a calculation complexity to implement. Hence, the obtained rate cannot necessarily be realized with implementable codes. To resolve this issue, we need to discuss the optimal rate among codes whose calculation complexity is not so high. Because no existing study discusses this type of finite-block-length analysis, such a study is strongly recommend for the future. Also, a realistic system is not necessarily memoryless; so, we need to discuss memory effects. To resolve this issue, jointly with Watanabe, the author extended this work to channels with additive Markovian noise, which covers the case when Markovian memory exists in the channel. (71) While this model covers many types of realistic channel, it is not trivial to apply the results in (71) to the realistic case of wireless communication because it is complicated to address the effect of fading in the coefficients. This is an interesting future problem.

After this breakthrough, the Princeton group extended their idea to many topics in channel coding and data compression. (10,11,14,70) On the other hand, in addition to the above Markovian extension, the author, jointly with Tomamichel, extended this work to the quantum system, (73) providing a unified framework for the second-order theory in the quantum system for data compression with side information, secure uniform random number generation, and simple hypothesis testing. At the same time, Li (75) directly derived the second-order analysis for simple statistical hypothesis testing in the quantum case. However, the second-order theory for simple statistical hypothesis testing has less meaning in itself; it is more meaningful in relation to other topics in information theory.

VIII. Extension to physical layer security

A. Wire-tap channel and its variants. The quantum cryptography explained above offers secure key distribution based on physical laws.

The classical counterpart of quantum cryptography is physical layer security, which offers information theoretical security based on several physical assumptions from classical mechanics. As its typical mode, Wyner (77) formulated the wire-tap channel model, which was more deeply investigated by Csiszar and Koner. (78) This model assumes two channels, as shown in Fig. 12: a channel [P.sub.Y|X] from the authorized sender (Alice) to the authorized receiver (Bob) and a channel [P.sub.Z|X] from the authorized sender to the eavesdropper (Eve). When the original signal of Alice has stronger correlation with the received signal than that with Eve, that is, a suitable input distribution [P.sub.X] satisfies the condition I([P.sub.X], [P.sub.Y|X]) > I([P.sub.X], [P.sub.Z|X]), the authorized users can communicate without any information leakage by using a suitable code. More precisely, secure communication is available if and only if there exists a suitable joint distribution [P.sub.VX] between the input system X and another system V such that the condition I([P.sub.V], [P.sub.Y|V]) > I([P.sub.V], [P.sub.Z|V]) holds, where [P.sub.Y|V](y|v) := [[summation].sub.x [member of] X] [P.sub.Y|X] (y|x) [P.sub.X|V] (x|v) and [P.sub.Z|V] is defined in the same way.

Although we often assume that the channel is stationary and memoryless, the general setting can be discussed by using information spectrum. (95) This paper explicitly pointed out that there is a relation between the wire-tap channel and the channel resolvability discussed in Section IV. This idea has been employed in many subsequent studies. (126,138,139,142) Watanabe and the author (123) discussed the second-order asymptotic for the channel resolvability. Also, extending the idea of the meta converse inequality to the wire-tap channel, Tyagi, Watanabe, and the author showed a relation between the wire-tap channel and hypothesis testing. (125) Based on these results, Yang et al. (124) investigated finite-block-length bounds for wiretap channels without Gaussian approximation. Also, taking into account the construction complexity, the author and Matsumoto [128, Section XI] proposed another type of finite-length analysis for wire-tap channels. Its quantum extension has also been discussed. (171,118) However, in the wire-tap channel model, we need to assume that Alice and Bob know the channel [P.sub.Z|X] to Eve. Hence, although it is a typical model for information theoretic security, this model is somewhat unrealistic because Alice and Bob cannot identify Eve's behavior. That is, it is assumed that Eve has weaker connection to Alice than Bob does, as shown in Fig. 12. So, it is quite hard to find a realistic situation where the original wire-tap channel model is applicable.

Fortunately, this model has more realistic derivatives: one is secret sharing, (135,136) and another is secure network coding. (81-85,129)) In secret sharing, there is one sender, Alice, and k receivers, Bob1, ..., Bobk. Alice splits her information into k parts, and sends them to the respective Bobs such that a subset of Bobs cannot recover the original message. For example, assume that there are two Bobs, [X.sub.1] is the original message and [X.sub.2] is an independent uniform random number. If Alice sends the exclusive or of [X.sub.1] and [X.sub.2] to Bob1 and sends [X.sub.2] to Bob2, neither Bob can recover the original message. When both Bobs cooperate, however, they can recover it. In the general case, for any given numbers [k.sub.1] < [k.sub.2] < k, we manage our code such that any set of [k.sub.1] Bobs cannot recover the original message but any set of [k.sub.2] Bobs can. (130)

Secure network coding is a more difficult task. In secure network coding, Alice sends her information to the receiver via a network, and the information is transmitted to the receiver via intermediate links. That is, each intermediate link transfers a part of the information. Secure network coding is a method to guarantee security when some of the intermediate links are eavesdropped by Eve. Such a method can be realized by applying the wire-tap channel to the case when Eve obtains the information from some of intermediate links. (81-85,129) When each intermediate link has the same amount of information, the required task can be regarded as a special case of secret sharing.

However, this method depends on the structure of the network, and it is quite difficult for Alice to know this structure. Hence, it is necessary to develop a coding method that does not depend on the structure of the network. Such a coding is called universal secure network coding, and has been developed by several researchers. (86,131-134) These studies assume only that the information processes on each node are linear and the structure of network does not change during transmission. In particular, the security evaluation can be made even with finite block-length codes. (86,133,134) Since it is quite hard to tap all of the links, this kind of security is sufficiently useful for practical use by ordinary people based on the cost-benefit analysis of performance. To understand the naturalness of this kind of assumption, let us consider the daily-life case in which an important message is sent by dividing it into two e-mails, the first of which contains the message encrypted by a secure key, and the second one contains the secure key. This situation assumes that only one of two links is eavesdropped.

B. Secure key distillation. As another type of information theoretical security, Ahlswede and Csiszar (80) and Maurer (79) proposed secure key distillation. Assume that two authorized users, Alice and Bob, have random variables X and Y, and the eavesdropper, Eve, has another random variable Z. When the mutual information I(X; Y) between Alice and Bob is larger than the mutual information 1(X; Z) or 1(Y; Z) between one authorized user and Eve, and when their information is given as the n-fold iid distribution of a given joint distribution [P.sub.XYZ], Alice and Bob can extract secure final keys.

Recently, secure key distillation has been developed in a more practical way by importing the methods developed for or motivated by quantum cryptography. (38,76,96-100) In particular, its finite-block-length analysis has been much developed, including the Markovian case, when Alice's random variable agrees with Bob's random variable. (76,96-99) Such a analysis has been extended to a more general case in which Alice's random variable does not necessarily agree with Bob's random variable. (127) Although some of the random hash functions were originally constructed for quantum cryptography, they can be used for privacy amplification even in secure key distillation. (56,64,65) Hence, under several natural assumptions for secure key distillation, it is possible to precisely evaluate the security based on finite-block-length analysis.

We assume that X is a binary information, and all information is given as the n-fold iid distribution of a given joint distribution [P.sub.XYZ]. In this case, the protocol is essentially given by steps (5) and (6) of QKD, where the code C, its dimension k, and the sacrifice bit length [bar.k] are determined a priori according to the joint distribution [P.sub.XYZ]. Now, we denote the information exchanged via the public channel by u and its distribution by [P.sub.pub]. The security is evaluated by the criterion;

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [35]

where [P.sub.R] is the distribution of the random variable R used to choose our hash function [f.sub.R]. To evaluate this criterion, we introduce the conditional Renyi entropy [5]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [36]

Then, the criterion is evaluated as ([98, (54) and Lemma 22] and [119, (21)] [6])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [37]

Its quantum extension has also been discussed in. (119,120)

Here, we should remark that the evaluation [37] can be realized by a random hash function with small calculation complexity. This is because the inequality holds for an arbitrary linear code and an arbitrary [delta]-almost dual [universal.sub.2] hash function. Since the paper (56) proposed several efficient [delta]-almost dual [universal.sub.2] hash functions, the bound has operational meaning even when we take into account the calculation complexity for its construction.

So, one might consider that secure key distillation is the same as QKD. However, QKD is different from secure key distillation even with the quantum extension due to the following points. The advantage of QKD is that it does not assume anything except for the basic laws of quantum theory. Hence, QKD usually does not allow us to make any additional assumptions, in particular, the iid assumption. In contrast, in secure key generation, we often make the iid assumption. As another difference, we are assumed to know the joint distribution or the density matrix on the whole system in secure key distillation whereas we need to estimate only the density matrix on the whole system in QKD.

The finite-block-length analysis of secure key distillation is different from that for channel coding in the following point. The obtained finite-block-length analysis for channel coding discusses only the optimal performance among all codes, including impractical codes whose calculation complexity is too high. However, in the finite-block-length analysis for physical layer security, the obtained bound can be attained by a practical protocol whose calculation complexity is linear in the block-length.

C. Application to wireless communication. Recently, along with the growing use of wireless communication, secure wireless communication has been very actively studied. (88-94) Physical layer security has been considered as a good candidate for secure wireless communication. (140,141) Typically, we assume the quasi-static condition, which allows us to assume the memoryless condition in one coding block-length. Even with this condition, a simple application of the wire-tap channel cannot guarantee secure communication when Eve set up her antenna between Alice and Bob. However, when the noise in Bob's output signal is independent of the noise in Eve's output signal, the mutual information between Alice and Bob is larger than that between Eve and Bob even in this situation. In this case, when they apply secure distillation in the opposite way after the initial wireless communication from Alice to Bob, they can generate secure keys. The assumption of the independence between Bob's and Eve's outputs is too strong and unrealistic for a practical use because there is a possibility of interference between the two channels. Hence, a more realistic assumption is needed.

To resolve this problem, the author had the following idea based on the experience of interactions with experimentalists studying QKD. It is natural to assume that the noises generated inside each detector are independent and Gaussian, and only the noise generated outside the detector is correlated to Eve's output. In this situation, even when all of the intermediate space between Alice and Bob is under the control of Eve and Eve injects artificial noise into Bob's observation, as in Fig. 13, when the noise is sufficiently small, the author showed that Alice and Bob can still generate secure keys. (87) Here, after the communication via the noisy wireless channel, Alice and Bob need to estimate the noise by random sampling. Once the random sampling guarantees that the noise is sufficiently small, they apply the secure key generation protocol. This is a protocol to generate secure keys between Alice and Bob under reasonable assumptions for secure wireless communication. Although the paper (87) gives such a protocol with a small calculation complexity for construction, the real performance of this protocol has not been studied in real situations. A future task is to estimate the performance of the proposed method in a realistic situation by taking into account several complicated realistic effects, including fading.

Here, we summarize the advantages over modern cryptography based on computation complexity. (92) When cryptography based on computation complexity is broken by a computer, any information transmitted with this cryptography can be eavesdropped by using that computer. To break physical layer security of the above type, Eve has to set up an antenna for each communication. Furthermore, each antenna must be very expensive because it must break the above assumption. Maybe, it is not impossible to break a limited number of specific communications for a very limited number of persons. However, due to the cost constraint, it is impossible to eavesdrop on all communications in a realistic situation. In this way, physical layer security offers a different type of security from computational security.

IX. Conclusions and future prospects

In this review article, we have discussed developments of finite-block-length theory in classical and quantum information theory: classical and quantum channel coding, data compression, (secure) random number generation, quantum cryptography, and physical layer security. These subareas have been developed with strong interactions with each other in unexpected ways.

The required future studies for channel coding and data compression are completely different from those needed for security topics. In the former topics, existing finite-block-length theory discusses only the minimum error among all codes without considering the calculation complexity of its construction. Hence, for practical use, we need a finite-block-length theory for realizable codes whose construction has less calculation complexity. Such finite-block-length theory is urgently required. Fortunately, the latest results obtained for these two topics (71,72) cover the case when a Markovian memory effect exists. However, their applications to a realistic situation have not been sufficiently studied, and such practical applications are interesting open problems.

In contrast, in the latter topics, the established finite-block-length theory already takes into account the calculation complexity of its construction; hence, it is more practical. However, these types of security protocols have not been realized for the following reasons. In the case of quantum cryptography, we need more development on the device side. Also, to realize secure communication for distances over 2000 km, we might need another type of information-scientific combinatorics. In the case of physical layer security, we need more studies to fill the gap between information theoretical security analysis and device development. There has recently been one such study. (87)

Furthermore, the idea of finite-block-length theory is fundamental and can be extended to areas beyond information theory. For example, it has been applied to a statistical mechanical rederivation of thermodynamics, (101,102) the conversion of entangled states, (103-106) and the analysis of the gap between two classes of local operations. (107) Therefore, we can expect more applications of finite-block-length theory to other areas.

Acknowledgments

The works reported here were supported in part by a MEXT Grant-in-Aid for Scientific Research (A) No. 23246071, a JSPS Grant-in-Aid for Young Scientists (A) No. 20686026, a JSPS Grant-in-Aid for Young Scientists (B) No. 14750330, a JSPS Grant-in-Aid for Scientific Research on Priority Area "Deepening and Expansion of Statistical Mechanical Informatics (DEX-SMI)" No. 18079014, ERATO (-SORST) Quantum Computation and Information Project of the Japan Science and Technology Agency (JST), the Brain Science Institute of RIKEN, the National Institute of Information and Communication Technology (NICT), Japan, the Okawa Research Grant, and the Kayamori Foundation of Informational Science Advancement. The author is grateful to Professor Akihisa Tomita, who is an expert on the physical implementation of QKD systems, for discussing the physical model for a real QKD system. He is also thankful to Dr. Toyohiro Tsurumaru and Dr. Kiyoshi Tamaki, who are working on QKD from an industrial perspective, for discussing the physical assumptions for the decoy model. He is also grateful to Professor Angeles Vazquez-Castro, Professor Hideichi Sasaoka, and Professor Hisato Iwai, who are experts in wireless communication, for discussing the validity of the model of the paper (87) for secure wireless communication. He is also thankful to Dr. Ken-ichiro Yoshino in NEC for providing the picture of the QKD device (Fig. 8).

References

(1) Shannon, C.E. (1948) A mathematical theory of communication. Bell Syst. Tech. J. 27, 623-656.

(2) Gallager, R.G. (1968) Information Theory and Reliable Communication. New York, Wiley.

(3) Berrou, C., Glavieux, A. and Thitimajshima, P. (1993) Near Shannon limit error-correcting coding and decoding: Turbo-codes 1. Communications. ICC '93 Geneva. Technical Program, Conference Record, IEEE International Conference on (Volume 2) pp. 1064-1070.

(4) MacKay, D.J.C. and Neal, R.M. (1996) Near Shannon limit performance of low density parity check codes. Electron. Lett. 32, 1645-1646.

(5) Strassen, V. (1962) Asymptotische Abschatzugen in Shannon's Informationstheorie, In Transactions of the Third Prague Conference on Information Theory etc., Czechoslovak Academy of Sciences, Prague, pp. 689-723. (In German); English translation in 2009 is available at http://www.math.cornell.edu/pmlut/strassen.pdf.

(6) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2010) Channel coding rate in the finite blocklength regime. IEEE Trans. Inf. Theory 56, 2307-2359.

(7) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2008) New channel coding achievability bounds. In Proceeding of 2008 IEEE Int. Symposium on Information Theory. Toronto, Ontario, Canada, pp. 1763-1767.

(8) Hayashi, M. (2008) Second-order asymptotics in fixed-length source coding and intrinsic randomness. IEEE Trans. Inf. Theory 54, 4619-4637.

(9) Hayashi, M. (2009) Information spectrum approach to second-order coding rate in channel coding. IEEE Trans. Inf. Theory 55, 4947-4966.

(10) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2011) Feedback in the non-asymptotic regime. IEEE Trans. Inf. Theory 57, 4903-4925.

(11) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2011) Dispersion of the Gilbert-Elliott channel. IEEE Trans. Inf. Theory 57, 1829-1848.

(12) Tan, V.Y.F. and Kosut, O. (2014) On the dis persions of three network information theory problems. IEEE Trans. Inf. Theory 60, 881-903.

(13) Watanabe, S., Kuzuoka, S. and Tan, V.Y.F. (2015) Nonasymptotic and second-order achievability bounds for coding with side-information. IEEE Trans. Inf. Theory 61, 1574-1605.

(14) Kostina, V. and Verdu, S. (2012) Fixed-length lossy compression in the finite blocklength regime. IEEE Trans. Inf. Theory 58, 3309-3338.

(15) Tomamichel, M. and Tan, V.Y.F. (2013) A tight upper bound for the third-order asymptotics for most discrete memoryless channels. IEEE Trans. Inf. Theory 59, 7041-7051.

(16) Han, T.-S. (2016) Celebrating Receipt of JSPS Prize and Japan Academy Medal by Prof. Masahito Hayashi His Personality and Tracks of Research Activites. EICE ESS Fundamentals Review 10, 100-103 (in Japanese).

(17) Yagi, H., Han, T.S. and Nomura, R. (2016) First and second-order coding theorems for mixed memoryless channels with general mixture. IEEE Transactions on Information Theory 62, 4395-4412.

(18) Hayashi, M. (2016) Role of quantum information theory in information theory beyond the non-commutative extension. IEICE ESS Fundamentals Review 10, 4-13 (in Japanese).

(19) Takahasi, H. (1965) Information theory of quantum mechanical channels. Adv. Commun. Systems 1, 227-310.

(20) Helstrom, C.W. (1967) Detection theory and quantum mechanics. Inf. Constr. 10, 254-291.

(21) Helstrom, C.W. (1967) Minimum mean-square error estimation in quantum statistics. Phys. Lett. 25A, 101-102.

(22) Holevo, A.S. (1982) Probabilistic and Statistical Aspects of Quantum Theory. North-Holland, Amsterdam; originally published in Russian (1980).

(23) Holevo, A.S. (1973) Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii 9, 3-11 (in Russian). (English translation: Probl. Inf. Transm. 9, 177-183 (1975)).

(24) Holevo, A.S. (1979) On the capacity of quantum communication channel. Problemly Peredachi Informatsii 15, 3-11 (in Russian). (English translation: Probl. Inf. Transm. 15, 247-253).

(25) Schumacher, B. (1995) Quantum coding. Phys. Rev. A 51, 2738-2747.

(26) Holevo, A.S. (1998) The capacity of the quantum channel with general signal states. IEEE Trans. Inf. Theory 44, 269.

(27) Schumacher, B. and Westmoreland, M.D. (1997) Sending classical information via noisy quantum channels. Phys. Rev. A 56, 131.

(28) Han, T.S. and Verdu, S. (1993) Approximation theory of output statistics. IEEE Trans. Inf. Theory 39, 752-772.

(29) Vembu, S. and Verdu, S. (1995) Generating random bits from an arbitrary source: Fundamental limits. IEEE Trans. Inf. Theory 41, 1322-1332.

(30) Verdu, S. and Han, T.S. (1994) A general formula for channel capacity. IEEE Trans. Inf. Theory 40, 1147-1157.

(31) Han, T.-S. (2003) Information-Spectrum Methods in Information Theory. Springer, Berlin. (Original Japanese version was published from Baifukan in 1998).

(32) Nagaoka, H. and Hayashi, M. (2007) An information-spectrum approach to classical and quantum hypothesis testing. IEEE Trans. Inf. Theory 53, 534-549.

(33) Hayashi, M. and Nagaoka, H. (2003) General formulas for capacity of classical-quantum channels. IEEE Trans. Inf. Theory 49, 1753-1768.

(34) Nagaoka, H. (2001) Strong converse theorems in quantum information theory. Proc. ERATO Conference on Quantum Information Science (EQIS) 2001, 33. (also appeared as Chap. 3 of Asymptotic Theory of Quantum Statistical Inference, M. Hayashi eds.).

(35) Hayashi, M. (2006) Quantum Information: An Introduction. Springer. (Original Japanese version was published from Saiensu-sha in 2004).

(36) Han, T.S. (2005) Folklore in source coding: in formation-spectrum approach. IEEE Trans. Inf. Theory 51, 747-753.

(37) Renner, R. and Konig, R. (2005) Universally composable privacy amplification against quantum adversaries. In Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005 (ed. Kilian, J.). Lecture Notes in Computer Science, vol. 3378, Springer Verlag, pp. 407-425.

(38) Watanabe, S., Matsumoto, R. and Uyematsu, T. (2010) Strongly secure privacy amplification cannot be obtained by encoder of Slepian-Wolf code. IEICE Trans. Fundamentals EA-93, 1650-1659.

(39) Hayashi, M. and Matsumoto, R. (2016) Secure multiplex coding with dependent and non-uniform multiple messages. IEEE Trans. Inf. Theory 62, 2355-2409.

(40) Bennett, C.H. and Brassard, G. (1984) Quantum cryptography: public key distribution and coin tossing. In Proc. IEEE International Conference on Computers, Systems and Signal Processing. Bangalore, India, pp. 175-179.

(41) Shor, P.W. and Preskill, J. (2000) Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett. 85, 441-444.

(42) Mayers, D. (2001) Unconditional security in quantum cryptography. J. Assoc. Comput. Mach. 48, 351.

(43) Gottesman, D., Lo, H.-K., Lutkenhaus, N. and Preskill, J. (2004) Security of quantum key distribution with imperfect devices. Quant. Inf. Comput. 5, 325-360.

(44) Hwang, W.-Y. (2003) Quantum key distribution with high loss: toward global secure communication. Phys. Rev. Lett. 91, 057901.

(45) Lo, H.-K., Ma, X. and Chen, K. (2005) Decoy state quantum key distribution. Phys. Rev. Lett. 94, 230504.

(46) Wang, X.-B. (2005) Beating the photon-number splitting attack in practical quantum cryptography. Phys. Rev. Lett. 94, 230503.

(47) Ma, X.-F., Qi, B., Zhao, Y. and Lo, H.-K. (2005) Practical decoy state for quantum key distribution. Phys. Rev. A 72, 012326.

(48) Wang, X.-B. (2005) A decoy-state protocol for quantum cryptography with four intensities of coherent states. Phys. Rev. A 72, 012322.

(49) Hayashi, M. (2007) General theory for decoy-state quantum key distribution with an arbitrary number of intensities. New J. Phys. 9, 284.

(50) Tsurumaru, T., Soujaeff, A. and Takeuchi, S. (2008) Exact minimum and maximum of yield with a finite number of decoy light intensities. Phys. Rev. A 77, 022319.

(51) Hasegawa, J., Hayashi, M., Hiroshima, T., Tanaka, A. and Tomita, A. (2007) Experimental decoy state quantum key distribution with unconditional security incorporating finite statistics. arXiv:0705.3081.

(52) Hayashi, M. (2006) Practical evaluation of security for quantum key distribution. Phys. Rev. A 74 022307.

(53) Hayashi, M. and Tsurumaru, T. (2012) Concise and tight security analysis of the Bennett-Brassard 1984 protocol with finite key lengths. New J. Phys. 14, 093014.

(54) Hayashi, M. (2007) Upper bounds of eavesdropper's performances in finite-length code with the decoy method. Phys. Rev. A 76, 012329; Phys. Rev. A, 79, 019901(E), 2009.

(55) Hayashi, M. and Nakayama, R. (2014) Security analysis of the decoy method with the Bennett-Brassard 1984 protocol for finite key lengths. New J. Phys. 16, 063009.

(56) Hayashi, M. and Tsurumaru, T. (2016) More efficient privacy amplification with less random seeds via dual universal hash function. IEEE Trans. Inf. Theory 62, 2213-2223.

(57) Tsurumaru, T. and Hayashi, M. (2013) Dual universality of hash functions and its applications to quantum cryptography. IEEE Trans. Inf. Theory 59, 4700-4717.

(58) http://jpn.nec.com/press/201509/20150928_03.html.

(59) The project UQCC http://www.uqcc.org/ QKDnetwork/.

(60) Courtland, R. (2016) hina's 2,000-km Quantum Link Is Almost Complete. IEEE Spectrum, 26 Oct, http://spectrum.ieee.org/telecom/security/ chinas-2000km-quantum-link-is-almost-complete.

(61) http:// www.battelle.org/our-work/national-security/ cyber-innovations/quantum-key-distribution.

(62) Bennett, C.H., Brassard, G., Crepeau, C. and Maurer, U.M. (1995) Generalized privacy amplification. IEEE Trans. Inf. Theory 41, 1915-1923.

(63) Hastad, J., Impagliazzo, R., Levin, L.A. and Luby, M. (1999) A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 1364.

(64) Carter, L. and Wegman, M. (1979) Universal classes of hash functions. J. Comput. Syst. Sci. 18, 143-154.

(65) Wegman, M.N. and Carter, J.L. (1981) New hash functions and their use in authentication and set inequality. J. Comput. Syst. Sci. 22, 265-279.

(66) Renner, R. (2005) Security of Quantum Key Distribution," Ph.D. thesis, Dipl. Phys. ETH, Switzerland, arXiv:quantph/0512258.

(67) Tomamichel, M., Lim, C.C.W., Gisin, N. and Renner, R. (2012) Tight finite-key analysis for quantum cryptography. Nat. Commun. 3, 634.

(68) Tomamichel, M., Schaffner, C., Smith, A. and Renner, R. (2011) Leftover hashing against quantum side information. IEEE Trans. Inf. Theory 57, 5524-5535.

(69) Hayashi, M. (2008) Second-order asymptotics in channel capacity. IEICE Tech. Rep. 108, 23-28.

(70) Kontoyiannis, I. and Verdu, S. (2014) Optimal lossless data compression: Non-asymptotics and asymptotics. IEEE Trans. Inf. Theory 60, 777-795.

(71) Hayashi, M. and Watanabe, S. (2013) Non-asymptotic bounds on fixed length source coding for Markov chains. In Proceedings of 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton House. Monticello, Illinois, USA, pp. 875-882.

(72) Hayashi, M. and Watanabe, S. (2014) Non-asymptotic and asymptotic analyses on Markov chains in several problems. In Proceedings of 2014 Information Theory and Applications Workshop, Catamaran Resort, San Diego, USA, pp. 1-10.

(73) Tomamichel, M. and Hayashi, M. (2013) A hierarchy of information quantities for finite block length analysis of quantum tasks. IEEE Trans. Inf. Theory 59, 7693-7710.

(74) Tan, V.Y.F. (2014) Asymptotic estimates in information theory with non-vanishing error probabilities. Found. Trends Commun. Inf. Theory 11, 1-184.

(75) Li, K. (2014) Second-order asymptotics for quantum hypothesis testing. Ann. Stat. 42, 171-189.

(76) Hayashi, M. and Watanabe, S. (2016) Uniform random number generation from Markov chains: Non-asymptotic and asymptotic analyses. IEEE Trans. Inf. Theory 62, 1795-1822.

(77) Wyner, A.D. (1975) The wire-tap channel. Bell Syst. Tech. J. 54, 1355-1387.

(78) Csiszar, I. and Korner, J. (1978) Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24, 339-348.

(79) Maurer, U. (1993) Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39, 733-742.

(80) Ahlswede, R. and Csiszar, I. (1993) Common randomness in information theory and cryptography part I: Secret sharing. IEEE Trans. Inf. Theory 39, 1121-1132.

(81) Bhattad, K. and Narayanan, K.R. (2005) Weakly secure network coding. In Proc. NetCod 2005. Riva del Garda, Italy.

(82) Cai, N. and Chan, T. (2011) Theory of secure network coding. Proc. IEEE 99, 421-437.

(83) Cai, N. and Yeung, R.W. (2002) Secure network coding. In Proc. 2002 IEEE ISIT, Lausanne, Switzerland, p. 323. [Online]. Available: http:// iest2.ie.cuhk.edu.hk/whyeung/publications/ secure. pdf.

(84) Cai, N. and Yeung, R.W. (2007) A security condition for multi-source linear network coding. In Proc. 2007 IEEE ISIT. Nice, France, pp. 561-565.

(85) Cai, N. and Yeung, R.W. (2011) Secure network coding on a wiretap network. IEEE Trans. Inf. Theory 57, 424-435.

(86) Matsumoto, R. and Hayashi, M. (2011) Secure Multiplex Network Coding. In Proceedings of 2011 International Symposium on Network Coding (NetCod). Beijing, China. (DOI: 10.1109/ ISNETCOD.2011.5979076).

(87) Hayashi, M. (2016) Secure wireless communication under spatial and local Gaussian noise assumptions, http://arxiv.org/abs/1604.00635.

(88) Ye, C., Mathur, S., Reznik, A., Shah, Y., Trappe, W. and Mandayam, N.B. (2010) Information-theoretically secret key generation for fading wireless channels. IEEE Trans. Inf. Forensics Security 5, 240-254.

(89) Wallace, J.W. and Sharma, R.K. (2010) Automatic secret keys from reciprocal MIMO wireless channels: Measurement and analysis. IEEE Trans. Inf. Forensics Security 5, 381-392.

(90) Premnath, S.N., Jana, S., Croft, J. and Gowda, P.L. (2013) Secret key extraction from wireless signal strength in real environments. IEEE Trans. Mobile Comput. 12, 917-930.

(91) Chen, C. and Jensen, M.A. (2011) Secret key establishment using temporally and spatially correlated wireless channel coefficients. IEEE Trans. Mobile Comput. 10, 205-215.

(92) Trappe, W. (2015) The challenges facing physical layer security. IEEE Commun. Mag. 53, 16-20.

(93) Zeng, K. (2015) Physical layer key generation in wireless networks: Challenges and opportunities. IEEE Commun. Mag. 53, 33-39.

(94) Wang, H.-M. and Xia, X.-G. (2015) Enhancing wireless secrecy via cooperation: Signal design and optimization. IEEE Commun. Mag. 53, 47-53.

(95) Hayashi, M. (2006) General non-asymptotic and asymptotic formulas in channel resolvability and identification capacity and its application to wiretap channel. IEEE Trans. Inf. Theory 52, 1562-1575.

(96) Hayashi, M. (2011) Exponential decreasing rate of leaked information in universal random privacy amplification. IEEE Trans. Inf. Theory 57, 3989-4001.

(97) Hayashi, M. (2013) Tight exponential analysis of universally composable privacy amplification and its applications. IEEE Trans. Inf. Theory 59, 7728-7746.

(98) Hayashi, M. (2016) Security analysis of e-almost dual [universal.sub.2] hash functions: Smoothing of min entropy vs. smoothing of Renyi entropy of order 2. IEEE Trans. Inf. Theory 62, 3451-3476.

(99) Hayashi, M. and Tan, V. (2015) Equivocations and exponents under various Renyi information measures. In IEEE International Symposium on Information Theory (ISIT2015). Hong Kong, pp. 281-285.

(100) Bloch, M., Hayashi, M. and Thangaraj, A. (2015) Error-control coding for physical-layer secrecy. Proc. IEEE 103, 1725-1746.

(101) Tajima, H. and Hayashi, M. (2014) Optimal efficiency of heat engines with finite-size heat baths, arXiv:1405.6457.

(102) Hayashi, M. and Tajima, H. (2015) Measurement based formulation of quantum heat engine, arXiv:1504.06150.

(103) Kumagai, W. and Hayashi, M. (2013) Entanglement concentration is irreversible. Phys. Rev. Lett. 111, 130407.

(104) Kumagai, W. and Hayashi, M. (2013) A new family of probability distributions and asymptotics of classical and LOCC conversions, arXiv:1306.4166.

(105) Kumagai, W. and Hayashi, M. (2014) Random number conversion and LOCC conversion via restricted storage, arXiv:1401.3781.

(106) Ito, K., Kumagai, W. and Hayashi, M. (2015) Asymptotic compatibility between local operations and classical communication conversion and recovery. Phys. Rev. A 92, 052308.

(107) Hayashi, M. and Owari, M. (2015) Tight asymptotic bounds on local hypothesis testing between a pure bipartite state and the white noise state. In Proceedings of IEEE International Symposium on Information Theory (ISIT2015). Hong Kong, pp. 691-695.

(108) Rivest, R.L., Shamir, A. and Adelman, L. (1977) A method for obtaining digital signature and public-key cryptsystems. MIT Laboratory for Computer Science; Thechnical Memo LCS/TM82.

(109) Hamada, M. (2002) Lower bounds on the quantum capacity and highest error exponent of general memoryless channels. IEEE Trans. Inf. Theory 48, 2547-2557.

(110) Hamada, M. (2003) Notes on the fidelity of symplectic quantum error-correcting codes. Int. J. Quant. Inf. 1, 443-463.

(111) Nambu, Y., Yoshino, K. and Tomita, A. (2006) One-way quantum key distribution system based on planar lightwave circuits. Jpn. J. Appl. Phys. 45, 5344-5348.

(112) Hayashi, M. (2009) Optimal ratio between phase basis and bit basis in quantum key distributions. Phys. Rev. A 79, 020303(R).

(113) Hayashi, M. (2016) Optimal decoy intensity for decoy quantum key distribution. J. Phys. A 49, 165301.

(114) Watanabe, S., Matsumoto, R. and Uyematsu, T. (2008) Tomography increases key rates of quantum-key-distribution protocols. Phys. Rev. A 78, 042316.

(115) Hayashi, M., Ishizaka, S., Kawachi, A., Kimura, G. and Ogawa, T. (2014) Introduction to Quantum Information Science. Graduate Texts in Physics, Springer.

(116) Hayashi, M. (2016) A Group Theoretic Approach to Quantum Information. Springer.

(117) Devetak, I. (2005) The private classical capacity and quantum capacity of a quantum channel. IEEE Trans. Inf. Theory 51, 44-55.

(118) Hayashi, M. (2015) Quantum wiretap channel with non-uniform random number and its exponent and equivocation rate of leaked information. IEEE Trans. Inf. Theory 61, 5595-5622.

(119) Hayashi, M. (2014) Large deviation analysis for quantum security via smoothing of Renyi entropy of order 2. IEEE Trans. Inf. Theory 60, 67026732.

(120) Devetak, I. and Winter, A. (2005) Distillation of secret key and entanglement from quantum states. Proc. R. Soc. Lond. A 461, 207-235.

(121) Arimoto, S. (1975) Information measures and capacity of order a for discrete memoryless channels. In Colloquia Mathematica Societatis Janos Bolya. Kestheley, Hungary, pp. 41-52.

(122) Fung, C.-H.F., Ma, X. and Chau, H.F. (2010) Practical issues in quantum-key-distribution post-processing. Phys. Rev. A 81, 012318.

(123) Watanabe, S. and Hayashi, M. (2014) Strong converse and second-order asymptotics of channel resolvability. In IEEE International Symposium on Information Theory (ISIT2014). Honolulu, HI, USA, pp. 1882.

(124) Yang, W., Schaefer, R.F. and Poor, H.V. (2016) Finite-blocklength bounds for wiretap channels. In IEEE International Symposium on Information Theory (ISIT2016). Barcelona, Spain, pp. 3087-3091.

(125) Hayashi, M., Tyagi, H. and Watanabe, S. (2014) Strong converse for a degraded wiretap channel via active hypothesis testing. Proc. Allerton Conf. Commun., Contr., Comput., Monticello, IL, USA, pp. 148-151.

(126) Tan, V.Y.F. (2012) Achievable second-order coding rates for the wiretap channel. In Proc. IEEE Int. Conf. Comm. Syst. (ICCS). Singapore.

(127) Hayashi, M., Tyagi, H. and Watanabe, S. (2016) Secret key agreement: General capacity and second-order asymptotics. IEEE Trans. Inf. Theory 62, 3796-3810.

(128) Hayashi, M. and Matsumoto, R. (2016) Secure multiplex coding with dependent and non-uniform multiple messages. IEEE Trans. Inf. Theory 62, 2355-2409.

(129) Harada, K. and Yamamoto, H. (2008) Strongly secure linear network coding. IEICE Trans. Fundamentals E91-A, 2720-2728.

(130) Yamamoto, H. (1985) Secret sharing system using (k, L, n) threshold scheme. IECE Trans. Fundamentals, J68-A, 945-952 (in Japanese). (English Translation: Scripta Technica, Inc., Electronics and Comm. in Japan, Part 1, vol. 69, no. 9, pp. 46-54, 1986.).

(131) Silva, D. and Kschischang, F.R. (2009) Universal weakly secure network coding. Proc. ITW 2009. Volos, Greece, pp. 281-285.

(132) Silva, D. and Kschischang, F.R. (2011) Universal secure network coding via rank-metric codes. IEEE Trans. Inf. Theory 57, 1124-1135.

(133) Kurihara, J., Matsumoto, R. and Uyematsu, T. (2015) Relative generalized rank weight of linear codes and its applications to network coding. IEEE Trans. Inf. Theory 61, 3912-3936.

(134) Kurosawa, K., Ohta, H. and Des Kakuta, K. (2017) How to make a linear network code (strongly) secure. Des. Codes Cryptogr., 82, 559-582.

(135) Blakley, G.R. (1979) Safeguarding cryptographic keys. In Proceedings of the National Computer Conference 48. pp. 313-317.

(136) Shamir, A. (1979) How to share a secret. Commun. ACM 22, 612-613.

(137) Ahlswede, R. and Dueck, G. (1989) Identification via channels. IEEE Trans. Inf. Theory 35, 15-29.

(138) Bloch, M.R. and Laneman, J.N. (2013) Strong secrecy from channel resolvability. IEEE Trans. Inf. Theory 59, 8077-8098.

(139) Hou, J. and Kramer, G. (2014) Effective secrecy: Reliability, confusion and stealth. In IEEE International Symposium on Information Theory. pp. 601-605.

(140) Bloch, M., Barros, J., Rodrigues, M.R. and McLaughlin, S.W. (2008) Wireless information-theoretic security. IEEE Trans. Inf. Theory 54, 2515-2534.

(141) Liang, Y., Poor, H.V. and Shamai, S. (2008) Secure communication over fading channels. IEEE Trans. Inf. Theory 54, 2470-2492.

(142) Han, T.S., Endo, H. and Sasaki, M. (2014) Reliability and secrecy functions of the wiretap channel under cost constraint. IEEE Trans. Inf. Theory 60, 6819-6843.

(Received Oct. 8, 2016; accepted Dec. 26, 2016)

Profile

Masahito Hayashi was born in Japan in 1971. He received the B.S. degree from the Faculty of Sciences in Kyoto University, Japan, in 1994 and M.S. and Ph.D. degrees in Mathematics from Kyoto University, Japan, in 1996 and 1999, respectively. He worked in Kyoto University as a Research Fellow of the Japan Society for the Promotion of Science (JSPS) from 1998 to 2000, in the Laboratory for Mathematical Neuroscience, Brain Science Institute, RIKEN from 2000 to 2003, and in the ERATO Quantum Computation and Information Project, Japan Science and Technology Agency (JST) as Research Head from 2000 to 2006. He also worked in the Superrobust Computation Project Information Science and Technology Strategic Core (21st Century COE by MEXT) Graduate School of Information Science and Technology, The University of Tokyo as Adjunct Associate Professor from 2004 to 2007. He worked in the Graduate School of Information Sciences, Tohoku University as Associate Professor from 2007 to 2012. In 2012, he joined the Graduate School of Mathematics, Nagoya University as Professor. He also worked as Visiting Research Associate Professor from 2009 to 2012 and as Visiting Research Professor from 2012 to the present in the Centre for Quantum Technologies, National University of Singapore. In 2011, he received the Information Theory Society Paper Award (2011) for his paper "Information-Spectrum Approach to Second-Order Coding Rate in Channel Coding". In 2016, he received the Japan Academy Medal from the Japan Academy and the JSPS Prize from the Japan Society for the Promotion of Science. In 2017, he was elevated to the status of an IEEE fellow.

In 2006, he published the book "Quantum Information: An Introduction" with Springer; the revised version was published as "Quantum Information Theory: Mathematical Foundation" in the Graduate Texts in Physics series by Springer in 2016. In 2016, he published other two books: "Group Representation for Quantum Theory" and "A Group Theoretic Approach to Quantum Information" with Springer. He is on the Editorial Board of the International Journal of Quantum Information and the International Journal On Advances in Security. His research interests include classical and quantum information theory and classical and quantum statistical inference.

[1] Unfortunately, due to page limitations, the present paper cannot give a detailed derivation. However, a detailed discussion is available in Section 4.6 of the book. (35)

[2] In the quantum case, they found a slightly weaker inequality. However, we can trivially derive [16] from their derivation in the commutative case.

[3] In the study of cryptography, We call the authorized sender, the authorized receiver, and the eavesdropper Alice, Bob, and Eve, respectively.

[4] To explain this point, we need to discuss a [delta]-almost [universal.sub.2] hash function for [F.sup.n.sub.2]/[C.sup.[perpendicular to]], which requires more work. To avoid this difficulty, we give only a simplified discussion here.

[5] Indeed, two kinds of conditional Renyi entropy are known. This type is often called the Gallager (2) or Arimoto type. (121)

[6] For its detail derivation, see [87, Section V-D].

By Masahito HAYASHI * [1], * [2] ([dagger])

(Communicated by Makoto NAGAO, M.J.A.)

* [1] Graduate School of Mathematics, Nagoya University, Chikusa-ku, Nagoya, Japan.

* [2] Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore.

([dagger]) Correspondence should be addressed: M. Hayashi, Graduate School of Mathematics, Nagoya University, Furocho, Chikusa-ku, Nagoya 464-8602, Japan (e-mail: masahito@math. nagoya-u.ac.jp).

doi: 10.2183/pjab.93.007 Caption: Fig. 1. Channel coding with three-bit code.

Caption: Fig. 2. Classical channel coding for optical communication. Dashed thick arrows indicate quantum state transmission. Normal thin arrows indicate classical information.

Caption: Fig. 3. Quantum channel coding for optical communication. Dashed thick arrows indicate quantum state transmission. Normal thin arrows indicate classical information.

Caption: Fig. 4. Classical-quantum channel coding for optical communication. Dashed thick arrows indicate quantum state transmission. Normal thin arrows indicate classical information.

Caption: Fig. 5. Structure of information spectrum: The information spectrum method discusses the problem in steps. One is the step to connect the information source and the behavior of the logarithmic likelihood. The other is the step to connect the behavior of the logarithmic likelihood and the optimal performances in the respective tasks.

Caption: Fig. 6. Asymptotic trade-off relation between errors of data compression and uniform random number generation: When we focus on the second-order coding rate, the minimum error of data compression is the probability of the exclusive event of the minimum error of uniform random number generation.

Caption: Fig. 7. Classes of (dual) [universal.sub.2] hash functions and security: A hash function is used to realize privacy amplification. This picture shows the relations between classes of hash functions and security. In cryptography theory, strong security is considered a requirement for a hash function. The class of [universal.sub.2] hash functions was proposed in. (64,65) Using the leftover hash lemma, (62,63) Renner (66) proposed to use this class for quantum cryptography. Tomamichel et al, (68) proposed to use the class of [delta]-almost [universal.sub.2] hash functions when [delta] is close to 1. Tsurumaru et al. (57) proposed the use of [delta]-almost dual [universal.sub.2] hash functions when [delta] is constant or increases polynomially. As an example of a [delta]-almost dual [universal.sub.2] hash function, the author with his collaborators (56) constructed a secure Hash Function with a less random seed and less calculation. Although the security analysis in (67) is based on [universal.sub.2] hash functions, that in (53-55) is based on [delta]-almost dual [universal.sub.2] hash functions.

Caption: Fig. 8. QKD system developed by NEC. Copyright (2015) by NEC: This device was used for a long-term evaluation demonstration in 2015 by the "Cyber Security Factory" (core facility for counter-cyber-attack activities in NEC). (58)

Caption: Fig. 9. Multiple photons in a weak coherent pulse: A weak coherent pulse contains multiple photons with a certain probability, which depends on the intensity of the pulse.

Caption: Fig. 11. Relation between the asymptotic transmission rate and the actual transmission rate dependent on the block-length: Usually, the actual transmission rate is smaller than the asymptotic key generation rate. As the block-length increases, the actual transmission rate becomes closer to the asymptotic key generation rate.

Caption: Fig. 12. Wire-tap channel model. Eve is assumed to have a weaker connection to Alice than Bob does.

Caption: Fig. 13. Model of Eve's attack for secure wireless communication. Eve can inject artificial noise into Bob's observation. It is also assumed that Eve has noise in her detector like Bob. It is natural to assume that these detector noises are independent of other random variables.

A fundamental problem in information processing is to transmit a message correctly via a noisy channel, where the noisy channel is mathematically described by a probabilistic relation between input and output symbols. To address this problem, we employ channel coding, which is composed of two parts: an encoder and a decoder. The key point of this technology is the addition of redundancy to the original message to protect it from corruption by the noise. The simplest channel coding is transmitting the same information three times as shown in Fig. 1. That is, when we need to send one bit of information, 0 or 1, we transmit three bits, 0, 0, 0 or 1, 1, 1. When an error occurs in only one of the three bits, we can easily recover the original bit. The conversion from 0 or 1 to 0, 0, 0 or 1, 1, 1 is called an encoder and the conversion from the noisy three bits to the original one bit is called a decoder. A pair of an encoder and a decoder is called a code.

In this example, the code has a large redundancy and the range of correctable errors is limited. For example, if two bits are flipped during the transmission, we cannot recover the original message. For practical use, we need to improve on this code, that is, decrease the amount of redundancy and enlarge the range of correctable errors.

The reason for the large redundancy in the simple code described above is that the block-length (the number of bits in one block) of the code is only 3. In 1948, Shannon (1) discovered that increasing the block-length n can improve the redundancy and the range of correctable errors. In particular, he clarified the minimum redundancy required to correct an error with probability almost 1 with an infinitely large block-length n. To discuss this problem, for a probability distribution P, he introduced the quantity H(P), which is called the (Shannon) entropy and expresses the uncertainty of the probability distribution P. He showed that we can recover the original message by a suitable code when the noise of each bit is independently generated subject to the probability distribution P, the rate of redundancy is the entropy H(P), and the block-length n is infinitely large. This fact is called the channel coding theorem. Under these conditions, the limit of the minimum error probability depends only on whether the rate of the redundancy is larger than the entropy H(P) or not.

We can consider a similar problem when the channel is given as additive white Gaussian noise. In this case, we cannot use the term redundancy because its meaning is not clear. In the following, instead of this term, we employ the transmission rate, which expresses the number of transmitted bits per one use of the channel, to characterize the speed of the transmission. In the case of an additive white Gaussian channel, the channel coding theorem is that the optimal transmission rate is j log(1 + S/N), where S/N is the signal-noise ratio [2, Theorem 7.4.4]. However, we cannot directly apply the channel coding theorem to actual information transmission because this theorem guarantees only the existence of a code with the above ideal performance. To construct a practical code, we need another type of theory, which is often called coding theory. Many practical codes have been proposed, depending on the strength of the noise in the channel, and have been used in real communication systems. However, although these codes realize a sufficiently small error probability, no code could attain the optimal transmission rate. Since the 1990s, turbo codes and low-density parity check (LDPC) codes have been actively studied as useful codes. (3,4) It was theoretically shown that they can attain the optimal transmission rate when the block-length n goes to infinity. However, still no actually constructed code could attain the optimal transmission rate. Hence, many researchers have doubted what the real optimal transmission rate is. Here, we should emphasize that any actually constructed code has a finite block-length and will not necessarily attain the conventional asymptotic transmission rate.

On the other hand, in 1962, Strassen (5) addressed this problem by discussing the coefficient with the order 1/[square root of n] of the transmission rate, which is called the second-order asymptotic theory. The calculation of the second-order coefficient approximately gives the solution of the above problem, that is, the real optimal transmission rate with finite block-length n. Although he derived the second-order coefficient for the discrete channel, he could not derive it for the additive white Gaussian channel. Also, in spite of the importance of his result, many researchers overlooked his result because his paper was written in German. Therefore, the successive researchers had to recover his result without use of his derivation. The present paper explains how this problem has been resolved even for additive white Gaussian channel by tracing the long history of classical and quantum information theory.

Currently, finite block-length theory is one of hottest topics in information theory and is discussed more precisely for various situations elsewhere. (6-17) Interestingly, in the study of finite-block-length theory, the formulation of quantum information theory becomes closer to that of classical information theory. (18)

In addition to reliable information transmission, information theory studies data compression (source coding) and (secure) uniform random number generation. In these problems, we address a code with block-length n. When the information source is subject to the distribution P and the block-length n is infinitely large, the optimal conversion rate is H(P) in both problems. Finite-length analysis also plays an important role in secure information transmission. Typical secure information transmission methods are quantum cryptography and physical layer security. The aim of this paper is to review the finite-length analysis in these various topics in information theory. Further, finite-length analysis has been developed in conjunction with an unexpected effect from the theory of quantum information transmission, which is often called quantum information theory. Hence, we explain the relation between the finite-length analysis and quantum information theory.

The remained of the paper is organized as follows. First, Section II outlines the notation used in information theory. Then, Section III explains how the quantum situation is formulated as a preparation for later sections. Section IV reviews the idea of an information spectrum, which is a general method used in information theory. The information spectrum plays an important role for developing the finite-length analysis later. Section V discusses folklore source coding, which is the first application of finite-length analysis. Then, Section VI addresses quantum cryptography, which is the first application to an implementable communication system. After a discussion of quantum cryptography, Section VII deals with second-order channel coding, which gives a fundamental bound for finite-length of codes. Finally, Section VIII discusses the relation between finitelength analysis and physical layer security.

II. Basics of information theory

As a preparation for the following discussion, we provide the minimum mathematical basis for a discussion of information theory. To describe the uncertainty of a random variable X subject to the distribution [P.sub.X] on a finite set X, Shannon introduced the Shannon entropy H([P.sub.X]) := - [summation].sub.x [member of] [chi]] [P.sub.X] (x) log [P.sub.X] (x), which is often written as H(X). When--log [P.sub.X](x) is regarded as a random variable, H([P.sub.X]) can be regarded as its expectation under the distribution [P.sub.X]. When two distributions P and Q are given the entropy is concave, that is, [lambda]H(P) + (1 - [lambda])H(Q) [less than or equal to] H( [lambda]P + (1 - [lambda])Q) for 0 < [lambda] <1. Due to the concavity, the maximum of the entropy is log [absolute value of X], where [absolute value of X] is the size of X. To discuss the channel coding theorem, we need to consider the conditional distribution [P.sub.Y|X](y|x) = [P.sub.Y|X=x] (y) where Y is a random variable in the finite set Y, which describes the channel with input system X and output system Y. In other words, the distribution of the value of the random variable Y depends on the value of the random variable X. In this case, we have the entropy H([P.sub.Y|X=x]) dependent on the input symbol x [member of] X.

Now, we fix a distribution [P.sub.X] on the input system X, taking the average of the entropy H([P.sub.Y|X=x]), we obtain the conditional entropy [[summation].sub.x[member of]X] [P.sub.X](x)[H.sub.(PY|X=x]), which is often written as H(Y|X). That is, the conditional entropy H(Y|X) can be regarded as the uncertainty of the system Y when we know the value on X. On the other hand, when we do not know the value on X, the distribution [P.sub.Y] on Y is given as [P.sub.Y](y) := [[summation].sub.x[member of]X] [P.sub.X](x)[P.sub.Y|X=x](y). Then, the uncertainty of the system Y is given as the entropy H(Y) := H([P.sub.y]), which is larger than the conditional entropy H(Y|X) due to the concavity of the entropy. So, the difference H(Y) - H(Y|X) can be regarded as the amount of knowledge in the system Y when we know the value on the system X. Hence, this value is called the mutual information between the two random variables X and Y, and is usually written as I(X; Y). Here, however, we denote it by I ([P.sub.X], [P.sub.Y|X]) to emphasize the dependence on the distribution [P.sub.X] over the input system X.

In channel coding, we usually employ the same channel [P.sub.Y|X] repetitively and independently (n times). The whole channel is written as the conditional distribution

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [x.sup.n] = ([x.sub.i], ..., [x.sub.n]) [member of] [X.sup.n] and [y.sup.n] = ([y.sub.1],...,[y.sub.n]) [member of] [y.sup.n]. This condition is called the memoryless condition. In information theory, information intended to be sent to a receiver is called a message, and is distinguished from other types of information. We consider the case that the sender sends a message, which is one element of the set [M.sub.n] := {1, ..., [M.sub.n]}, where [M.sub.n] expresses the number of elements in the set. Then, the encoder [E.sub.n] is written as a map from [M.sub.n] to [X.sup.n], and the decoder [D.sub.n] is written as a map from [y.sup.n] to [M.sub.n]. The pair of the encoder [E.sub.n] and the decoder [D.sub.n] is called a code.

Under this formulation, we focus on the decoding error probability [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which" expresses the performance of a code ([E.sub.n], [D.sub.n]). As another measure of the performance of a code ([E.sub.n], [D.sub.n]), we focus on the size [M.sub.n], which is denoted by [absolute value of ([E.sub.n], [D.sub.n])] later. Now, we impose the condition [epsilon]([E.sub.n], [D.sub.n]) [less than or equal to] [epsilon] on our code ([E.sub.n],[D.sub.n]), and maximize the size [absolute value of ([E.sub.n],[D.sub.n])]. That is, we focus on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this context, the quantity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] expresses the maximum transmission rate under the above conditions. The channel coding theorem characterizes the maximum transmission rate as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [1]

The maximum value of the mutual information is called the capacity. To characterize the mutual information, we introduce the relative entropy between two distributions P and Q as D(P [parallel] Q) := [[summation].sub.x [member of] X] P(x) log P(x)/Q(x). When we introduce the joint distribution [P.sub.XY](x, y) := [P.sub.X](x)[P.sub.Y|X](y|x) and the product distribution ([P.sub.X] x [P.sub.Y]) (x,y) := [P.sub.X](x) [P.sub.Y](y), the mutual information is characterized as (1,2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [2]

That is, the capacity is given as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [3]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [4]

The final equation can be shown by using the mini-max theorem. On the other hand, it is known that the relative entropy D(P [parallel] Q) characterizes the performance of statistical hypothesis testing when both hypotheses are given as distributions P and Q. Hence, we can expect an interesting relation between channel coding and statistical hypothesis testing.

As a typical channel, we focus on an additive channel. When the input and output systems X and Y are given as the module Z/dZ, given the input X [member of] Z/dZ, the output Y [member of] Z/dZ is given as Y = X D Z, where Z is the random variable describing the noise and is subject to the distribution [P.sub.Z] on Z/dZ. Such a channel is called an additive channel or an additive noise channel. In this case, the conditional entropy H(Y|X) is H([P.sub.Z]), because the entropy H([P.sub.Y|X=x]) equals H(Pz) for any input x [member of] X, and the mutual information I ([P.sub.X], [P.sub.Y|X]) is given by H([P.sub.Y]) - H([P.sub.Z]). When the input distribution [P.sub.X] is the uniform distribution, the output distribution [P.sub.Y] is the uniform distribution and achieves the maximum entropy log d. So, the maximum mutual information [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given as log d - H([P.sub.Z]). That is, the maximum transmission equals log d - H([P.sub.Z]). If we do not employ the coding, the transmission rate is log d. Hence, the entropy H([P.sub.Z]) can be regarded as the loss of the transmission rate due to the coding. In this coding, we essentially add the redundancy H([P.sub.Z]) in the encoding stage.

It is helpful to explain concrete constructions of codes with the case of d = 2, in which Z/2Z becomes the finite field F2, which is the set {0,1} with the operations of modular addition and multiplication, when the additive noise [Z.sup.n] = ([Z.sub.1], ..., [Z.sub.n]) is subject to the n-fold distribution [P.sup.n.sub.Z] of n independent and identical distributed copies of Z ~ [P.sub.Z]. (From now on, we call such distributions "iid distributions" for short.) The possible transmissions are then elements of [F.sup.n.sub.2] which is the set of n-dimensional vectors whose entries are either 0 or 1. In this case, we can consider the inner product in the vector space [F.sup.n.sub.2] using the multiplicative and additive operations of [F.sub.2]. When [P.sub.Z](1) = p, the entropy H([P.sub.Z]) is written as h(p), where the binary entropy is defined as h(p) := - p log p - (1 - p)log (1 - p). Since [X.sup.n] = [F.sup.n.sub.2], we choose a subspace C of [F.sup.n.sub.2] with respect to addition and we identify the message set [M.sub.n] with C. The encoder is given as a natural imbedding of C. To find a suitable decoder, for a given element [y] of the coset [F.sup.n.sub.2]/C, we seek the most probable element [GAMMA]([y]) among x + C. Hence, when we receive y [member of] [F.sup.n.sub.2], we decode it to y - [GAMMA]([y]). It is typical to employ this kind of decoder. To identify the subspace C, we often employ a parity check matrix K, in which, the subspace C is given as the kernel of K. Using the parity check matrix K, the element of the coset [F.sup.n.sub.2]/C can be identified using the image of the parity check matrix K, which is called the syndrome. In this case, we denote the encoder by [E.sub.k].

Alternatively, when [GAMMA]([y]) realizes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the decoder is called the maximum likelihood decoder. This decoder also gives the minimum decoding error [epsilon]([E.sub.T], D). As another decoder, we can choose [GAMMA]([y]) such that [GAMMA]([y]) realizes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [absolute value of [x.sup.n]] is the number of appearances of 1 among n entries. This decoder is called the minimum distance decoder. When [P.sub.Z](0) > [P.sub.Z](1), the maximum likelihood decoder is the same as the minimum distance decoder. We denote the minimum distance decoder by [D.sub.K,min]. This type of code is often called an error correcting code.

When most of the entries of the parity check matrix K are zero, the parity check matrix K is called an LDPC matrix. When the subspace C is given as the kernel of an LDPC matrix, the code is called the LDPC code. In this case, it is known that a good decoder can be realized with a small calculation complexity. (3,4) Hence, an LDPC code is used for practical purposes.

III. Information transmission via quantum coding

To discuss the information transmission problem, we eventually need to address the properties of the physical media carrying the information. When we approach the ultimate limit of the information transmission rate as a theoretical problem, we need to consider the case when individual particles express each bit of information. That is, we focus on the information transmission rate under such an extreme situation. To realize the ultimate transmission rate, we need to use every photon (or every pulse) to describe one piece of information. Since the physical medium used to transmit the information behaves quantum mechanically under such conditions, the description of the information system needs to reflect this quantum nature.

Several researchers, such as Takahasi, (19) started to consider the limit of optical communication in the 1960s. In 1967, Helstrom (20,21) started to systematically formulate this problem as a new type of information processing system based on quantum theory instead of an information transmission system based on classical mechanical input and output, which obeys conventional probability theory. The study of information transmission based on such quantum media is called quantum information theory. In particular, research on channel coding for quantum media is called quantum channel coding. In contrast, information theory based on the conventional probability theory is called classical information theory when we need to distinguish it from quantum information theory, even when the devices employ quantum effects in their insides, because the input and the output are based on classical mechanics. Quantum information theory in its earlier stage has been studied more deeply by Holevo and is systematically summarized in his book (22) in 1980.

Here, we point out that current optical communication systems are treated in the framework of classical information theory. However, optical communication can be treated in both classical and quantum information theory as follows (Figs. 2 and 3). Because the framework of classical information theory cannot deal with a quantum system, to consider optical communication within classical information theory, we need to fix the modulator converting the input signal to the input quantum state and the detector converting the output quantum state to the outcome, as shown in Fig. 2. Once we fix these, we have the conditional distribution connecting the input and output symbols, which describes the channel in the framework of classical information theory. That is, we can apply classical information theory to the classical channel. The encoder is the process converting the message (to be sent) to the input signal, and the decoder is the process recovering the message from the outcome.

On the other hand, when we discuss optical communication within the framework of quantum information theory as shown in Fig. 3, we focus on the quantum channel, whose input and output are given as quantum states. When the quantum system is characterized by the Hilbert space H, a quantum state is given as a density matrix [rho] on H, which is a positive-semi definite matrix with trace 1. Within this framework, we combine a classical encoder and a modulator into a quantum encoder, in which the message is directly converted to the input quantum state. Similarly, we combine a classical encoder and a detector into a quantum decoder, in which the message is directly recovered from the output quantum state. Once the optical communication is treated in the framework of quantum information theory, our coding operation is given as the combination of a quantum encoder and a quantum decoder. This framework allows us to employ physical processes across multiple pulses as a quantum encoder or decoder, so quantum information theory clarifies how much such a correlating operation enhances the information transmission speed. It is also possible to fix only the modulator and discuss the combination of a classical encoder and a quantum decoder, which is called classical-quantum channel coding, as shown in Fig. 4. A classical-quantum channel is given as a map from an element x of the input classical system X to an output quantum state [[rho].sub.x], which is given as a density matrix on the output quantum system H.

Here, we remark that the framework of quantum information theory mathematically contains the framework of classical information theory as the commutative special case, that is, the case when all [[rho].sub.x] commute with each other. This character is in contrast to the fact that a quantum Turing machine does not contain the conventional Turing machine as the commutative special case. Hence, when we obtain a novel result in quantum information theory and it is still novel even in the commutative special case, it is automatically novel in classical information theory. This is a major advantage and became a driving force for later unexpected theoretical developments.

A remarkable achievement of the early stage was made by Holevo in 1979, who obtained a partial result for the classical-quantum channel coding theorem. (23,24) However, this research direction entered a period of stagnation in the 1980s. In the 1990s, quantum information theory entered a new phase and was studied from a new viewpoint. For example, Schumacher introduced the concept of a typical sequence in a quantum system. (25) This idea brought us new developments and enabled us to extend data compression to the quantum setting. (25) Based on this idea, Holevo (26) and Schumacher and Westmoreland (27) independently proved the classical-quantum channel coding theorem, which had been unsolved until that time.

Unfortunately, a quantum operation in the framework of quantum information theory is not necessarily available with the current technology. Hence, these achievements remain more theoretical than classical channel coding theorem. However, such theoretical results have, in a sense, brought us more practical results, as we shall see later.

Now, we give a formal statement of the quantum channel coding theorem for the classical-quantum channel x [??] [[rho].sub.X]. For this purpose, we introduce the von Neumann entropy H([rho]) := - Tr [rho] log [rho] for a given density matrix [rho]. It is known that the von Neumann entropy is also concave just as in the classical case. When we employ the same classical-quantum channel n times, the total classical-quantum channel is given as a map [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. While an encoder is given as the same way as the classical case, a decoder is defined in a different way because it is given by using a quantum measurement on the output quantum system H. The most general description of a quantum measurement on the output quantum system H is given by using a positive operator-valued measure [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], in which, each [[PI].sub.m] is a positive-semi definite matrix on H and the condition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] holds. As explained in [35, (4.7)][115, (8.48)], the decoding error probability is given as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, we can define the maximum transmission size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the other hand, the mutual information is defined as I ([P.sub.X], [rho]) := H ([[summation].sub.x][P.sub.X](x)[[rho].sub.x]) - [[summation].sub.x][P.sub.X] (x)H([[rho].sub.x]). So, the maximum transmission rate is characterized by the quantum channel coding theorem as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [5]

To characterize the mutual information I([P.sub.X], [rho]), we denote the classical system X by using the quantum system [H.sub.X] spanned by |x> and introduce the density matrix [[rho].sub.XY] := [[summation].sub.x [member of] X] [P.sub.X](x) |x><x| [[rho].sub.x] on the joint system [H.sub.X] [cross product] H and the density matrix [[rho].sub.Y] := [[summation].sub.x [member of] X] [P.sub.X](x)[[rho].sub.X] on the quantum system H. In this notation, we regard [P.sub.X] as the density matrix [[summation].sub.x [member of] X][P.sub.X](x)[absolute value of x><x] on [H.sub.X]. Using the quantum relative entropy D([rho] [parallel] [sigma]) := Tr [rho](log [rho] - log [sigma]) between two density matrices [rho] and [sigma], the mutual information is written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [6]

So, the capacity is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [7]

Here, it is necessary to discuss the relation between classical and quantum information theory. For this purpose, we focus on information transmission via communication on an optical fiber. When we employ coding in classical information theory, we choose a code based on classical information devices, which are the input and the output of the classical channel shown in Fig. 2. In contrast, when we employ coding in quantum information theory, we choose a code based on quantum information devices, which are the input and the output of the quantum channel shown in Fig. 3. In the case of Fig. 4, we address the classical-quantum channel so that we focus on the output system as a quantum information device. That is, the choice between classical and quantum information theory is determined by the choice of a classical or quantum information device, respectively.

IV. Information spectrum

The early stage of the development of finite block-length studies started from a completely different motivation and used the information spectrum method introduced by Han and Verdu. (28,31) Conventional studies in information theory usually impose the iid or memoryless condition on the information source or the channel. However, neither the information source nor the channel is usually independent in the actual case and they often have correlations. Hence, information theory needed to be adapted for such a situation.

To resolve such a problem, Verdu and Han have discussed optimal performance in the context of several topics in classical information theory, including channel coding, by using the behavior of the logarithmic likelihood, as shown in Fig. 5. (30) However, they have discussed only the case when the block-length n approaches infinity, and have not studied the case with finite block-length. It is notable that this study clarified that the analysis of the iid case can be reduced to the law of large numbers. In this way, the information spectrum method has clarified the mathematical structures of many topics in information theory, which has worked as a silent trigger for further developments.

Another important contribution of the information spectrum method the connection of simple statistical hypothesis testing to many topics in classical information theory. (31) Here, simple statistical hypothesis testing is the problem of deciding which candidate is the true distribution with an asymmetric treatment of two kinds of errors when two candidates for the true distribution are given. In particular, the information spectrum method has revealed that the performances of data compression and uniform random number generation are given by the behavior of the logarithmic likelihood.

Here, we briefly discuss the idea of the information spectrum approach in the case of uniform random number generation. Let [X.sub.n] be the original system, where n is an index. The product set [X.sup.n] is a typical example of this notation. In uniform random number generation, we prepare another set [y.sub.n], in which, we generate an approximate uniform random number [Y.sub.n]. In this formulation, we focus on the initial distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on [X.sub.n]. Then, our operation is given as a map [[phi].sub.n] from [X.sub.n] to [Y.sub.n]. The resultant distribution on [Y.sub.n] is given as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. To discuss the quality of the resultant uniform random number, we employ the uniform distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the error of the operation [[phi].sub.n] is given as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now we define the maximum size of the uniform random number with error [epsilon] as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Vembu and Verdu [29, Section V] showed that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [8]

This fact shows that the generation rate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is essentially described by the random variable - [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When [X.sub.n] is [X.sup.n] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the iid distribution [P.sup.n.sub.X] of [P.sub.X], the random variable [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges to the entropy H([P.sub.X]) in probability due to the law of large numbers. In the iid case, the generation rate equals the entropy H([P.sub.X]).

In the channel coding case, we focus on a general conditional distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the channel. Then, Verdu and Han (30) derived the maximum transmission rate as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [9]

Although we can derive the formula [1] from this general formulation, it is not so easy because the above formula contains the maximization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of the input distribution on the large system [X.sub.n]. When the channel [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given as the additive channel with the additive noise distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the above formula can be simplified as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [10]

Note that [Z.sub.n] is the same set as [X.sub.n] and [y.sub.n] when the channel is additive.

As already mentioned, the information spectrum approach was started as a result of a motivation different from the above. When Han and Verdu (28) introduced this method, they considered identification codes, which were initially introduced by Ahlswede and Dueck. (137) To resolve this problem, Han and Verdu introduced another problem--channel resolvability--which discusses the approximation of a given output distribution by the input uniform distribution on a small subset. That is, they consider

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [11]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [12]

where [[phi].sub.n] is chosen as a function from [T.sub.n] to [X.sub.n]. They showed that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [13]

By considering this problem, they introduced the new concept of channel resolvability, which later played an important role in a completely different topic.

In the next stage, Nagaoka and the author extended the information spectrum method to the quantum case. (32,33) In this extension, their contribution is not only the non-commutative extension but also the redevelopment of information theory. In particular, they have given a deeper clarification of the explicit relation between simple statistical hypothesis testing and channel coding, which is called the dependence test bound in the later study [33, Remark 15]. In this context, Nagaoka (34) has developed another explicit relation between simple statistical hypothesis testing and channel coding, which is called the meta converse inequality [1]. These two clarifications of the relation between simple statistical hypothesis testing and channel coding work as a preparation for the next step of finite-length analysis.

Now, to grasp the essence of these contributions, we revisit the classical setting because the quantum situation is more complicated. To explain the notation of classical hypothesis testing, we consider testing between two distributions [P.sub.1] and [P.sub.0] on the same system X. Generally, our testing method is written by using a function T from X to [0,1] as follows. When we observe x [member of] X, we support [P.sub.1] with the probability T(x), and support [P.sub.0] with the probability 1 - T(x). When the function T takes values only in {0,1}, our decision is deterministic. In this problem, we have two types of error probability. The first one is the probability for erroneously supporting [P.sub.1] while the true distribution is [P.sub.0], which is given as [alpha](T|[P.sub.0] [parallel] [P.sub.1]) := [[summation].sub.x [member of] X] T(x)[P.sub.0](x). The second one is the probability for erroneously supporting [P.sub.0] while the true distribution is [P.sub.1], which is given as [beta](T|[P.sub.0] [parallel] [P.sub.1]) := [[summation].sub.x [member of] X](1 - T(x))[P.sub.1](x). Then, we consider the minimum second error probability under the constraint of a constant probability for the first error as [beta]([epsilon]|[P.sub.0] [parallel] [P.sub.1]) := [min.sub.T]{[beta](T|[P.sub.0] [parallel] [P.sub.1])|[alpha](T|[P.sub.0] [parallel] [P.sub.1]) [less than or equal to] [epsilon]}.

To overcome the problem with respect to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [9], for a given channel [P.sub.Y|X], Nagaoka (34) derived the meta converse inequality:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [14]

for any distribution [Q.sub.Y] on Y.

Also, the author and Nagaoka derived the dependence test bound as follows [33, Remark 15]. For a given distribution on [P.sub.X] on X and a positive integer N, there exists a code (E, D) such that [absolute value of (E,D)] = N [2]

[epsilon](E, D) [less than or equal to] [epsilon] + N[beta]([epsilon]|[P.sub.XY] [parallel] [P.sub.X] x [P.sub.Y]). [15]

That is, for any [delta] > 0 and [epsilon] > 0, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [16]

Here, [16] follows from [15] by putting [delta] = N[beta]([epsilon]|[P.sub.XY] [parallel] [P.sub.X] x [P.sub.Y]).

Then, using [16], the author and Nagaoka derived the [greater than or equal to] part of [9] including the quantum extension. Also, using [14], the author and Nagaoka derived another expression for [9]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [17]

While [17] seems more complicated than [9], [17] is more useful for proving the impossibility part for the following reason. In [9], the distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a complicated form in general. Hence, it is quite difficult to evaluate the behavior of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. When we derive the upper bound of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it is enough to consider the case with a special [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. That is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be chosen to be a distribution for iid random variables so that the random variable [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be factorized. Then, the impossibility part of the channel coding theorem can be easily shown via [17].

Indeed, since the classical case is not so complicated, it is possible to recover several important results from [9]. However, use of the formula [17] is needed in the quantum case because everything becomes more complicated.

V. Folklore in source coding

When the information source is subject to the iid distribution [P.sup.n.sub.X] of [P.sub.X], the compression rate and the uniform random number generation rate have the same value of H([P.sub.X]) asymptotically. Hence, we can expect that the data compressed up to the entropy rate H([P.sub.X]) would be the uniform random number. However, this argument does not work as a proof of the statement, so this conjecture has the status of folklore in source coding, and its validity remained unconfirmed for a long time.

Han (36) tackled this problem by using the method of information spectrum. Han focused on the normalized relative entropy [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the criterion to measure the difference of the generated random number from a uniform random number, and showed that the folklore in source coding is valid. (36) However, the normalized relative entropy is too loose a criterion to guarantee the quality of the uniform random number because it is possible to distinguish a generated random number from a truly uniform random number even though the random number is considered to be uniform by this criterion. In particular, when a random number is used for cryptography, we need to employ a more rigorous criterion to judge the quality of its uniformity.

In contrast, the criterion [gamma]([[phi].sub.n]) is the most popular criterion which gives the statistical distinguishability between a truly uniform random number and a given random number. (37) That is, when this criterion takes the value 0, the random number must be truly uniform. Hence, when we use a random number for cryptography, we need to accept only a random number passing this criterion. Also, Han (36) has proved that the folklore conjecture in source coding is not valid when we adopt the variational distance as our criterion.

On the other hand, to clarify the incompatibility between data compression and uniform random number generation, the author (8) developed a theory for finite-block-length codes for both topics. In this analysis, he applied the method of information spectrum to the second-order [square root of n] term, as shown in Fig. 5. That is, by using the varentropy V([P.sub.X]) := [[summation].sub.x [member of] X] [P.sub.X](x)(- log [P.sub.X](x) - H([P.sub.X])) (2), the central limit theorem guarantees that

[P.sup.n.sub.X]{[x.sup.n] [member of] [X.sup.n]|(log [P.sup.n.sub.X]([x.sup.n]) - nH([P.sub.X]))/[square root of n] [less than or equal to] [epsilon]} = [square root of (V([P.sub.X])] [[PHI].sup.-1]([epsilon]), [18]

where the cumulative distribution function [PHI] of the standard Gaussian distribution is defined as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the generation length log S([epsilon]|[P.sup.n.sub.X]) is asymptotically expanded as

log S([epsilon]|[P.sup.n.sub.X]) = nH ([P.sub.X] ) + [square root of n] [square root of (V[P.sub.X])][[PHI].sup.-1]([epsilon]) + o([square root of n]). [19]

Now, we consider data compression, in which we define the minimum compressed size R([epsilon]|[P.sup.n.sub.X]) with decoding error [epsilon] in the same way. Then, the asymptotic expansion is (5,8)

log R([epsilon]|[P.sup.n.sub.X]) = nH ([P.sub.X]) - [square root of n] [square root of ([P.sub.X])][[PHI].sup.-1]([epsilon]) + o([square root of n]). [20]

That is, when the converted length has the asymptotic expansion nH([P.sub.X]) - [square root of n][square root of (V([P.sub.X])]R, the errors of both settings are illustrated in Fig. 6.

Now, we fix the conversion rate up to the second-order 1/[square root of n]. When we apply an operation from the system [X.sup.n] to a system with size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the sum of the errors of the data compression and the uniform random number generation almost equals to 1. This trade-off relation shows that data compression and uniform random number generation are incompatible to each other. Indeed, since the task of data compression has the direction opposite to that of uniform random number generation, the second-order analysis explicitly clarifies that there is a trade-off relation for their errors rather than compatibility.

Although the evaluation of optimal performance up to the second-order coefficient gives an approximation of the finite-length analysis, it also shows the existence of their trade-off relation. This application shows the importance of the second-order analysis. Because the evaluation of the uniformity of a random number is closely related to security, this type evaluation has been applied to security analysis. (38) This trade-off relation also plays an important role when we use the compressed data as the scramble random variable for another piece of information. (39)

VI. Quantum cryptography

A. Single-photon pulse without noise. Section III has explained that the problem of the ultimate performance of optical communication can be treated as quantum channel coding. When the communication media has quantum properties, it opens the possibility of a new communication style that cannot be realized with the preceding technology. Quantum cryptography was proposed by Bennett and Brassard (40) in 1984 as a technology to distribute secure keys by using quantum media. Even when the key is eavesdropped during the distribution, this method enables us to detect the existence of the eavesdropper with high probability. Hence, this method realizes secure key distribution, and is called quantum key distribution (QKD).

Now, we explain the original QKD protocol based on single-photon transmission. In the QKD, the sender, Alice, needs to generate four kinds of states in the two-dimensional system [C.sup.2], namely, |0>, |1>, and |[+ or -]> := 1/[square root of 2] (|10> [+ or -] |1>) [3]. Here, {|10>, |1>} is called the bit basis, and { |[+ or -]>} is called the phase basis. Also, the receiver, Bob, needs to measure the received quantum state by using either the bit basis or the phase basis.

The original QKD protocol (40) is the following.

(1) [Preparation] Alice randomly chooses one of four states, and sends it to Bob.

(2) [Transmission] Bob randomly chooses one of two bases, and measures the received state using the chosen basis. Alice and Bob repeat Steps (1) and (2) several times.

(3) [Detection] Alice and Bob exchange their basis information via a public channel, and they discard bits with disagreed bases.

(4) [Error check] Alice and Bob randomly choose check bits from among the remaining bits, and they exchange their values via a public channel. If they find an error, they stop the protocol because the error might be caused by eavesdropping. Otherwise, they use the remaining bits as keys, which are called raw keys.

In this protocol, if the eavesdropper, Eve, performs a measurement during transmission, the quantum state would be destroyed with non-negligible probability because she does not know the basis of the transmitted quantum state a priori. When the number of qubits measured by Eve is not so small, Alice and Bob will find disagreements in step (4). So, the existence of eavesdropping will be discovered by Alice and Bob with high probability.

B. Random hash functions. The original protocol supposes noiseless quantum communication by a single photon. So, the raw keys are not necessarily secure when the channel has noise. To realize secure communication even with a noisy channel, we need a method to generate secure keys from keys partially leaked to Eve. Such a process is called privacy amplification. In this process, we apply a hash function, which maps from a larger set to a smaller set. In the security analysis, we often employ a hash function whose choice is determined by a random variable (a random hash function). A typical class of random hash functions is the following class. A random hash function [f.sub.R] from [F.sup.n.sub.2] to [F.sup.m.sub.2] is called [universal.sub.2] (64,65) when

Pr{[f.sub.R](x) = [f.sub.R](x')} [less than or equal to] [2.sup.-m] [21]

for distinct elements x and x' in [F.sup.n.sub.2]. A typical example of a surjective [universal.sub.2] hash function is the concatenated Toeplitz matrix, which is given as follows. When an m x (n - m) matrix [T.sub.R] = ([T.sub.i,j]) is given as [T.sub.i,j] = [R.sub.i+j-i] by using n - 1 random variables [R.sub.j], it is called a Toeplitz matrix. Let T = {[T.sub.R]|r [member of] I} be the set of all m x (n - m) Toeplitz matrices. Then let [M.sub.r] = ([T.sub.R], [I.sub.m]) be an m x n matrix defined by a concatenation of [T.sub.R] and the m-dimensional identity matrix [I.sub.m]. Then, the concatenated Toeplitz matrix [M.sub.R] maps an input x [member of] [F.sup.n.sub.2] to the output y = [M.sub.r]x [member of] [F.sup.m.sub.2]. The concatenated Toeplitz matrix [M.sub.R] is [universal.sub.2] when R is a uniform random number. (For a proof, see, e.g., [96, Appendix II].)

This class can be relaxed as follows. A random hash function [f.sub.R] from [F.sup.n.sub.2] to [F.sup.m.sub.2] is called [delta]-almost [universal.sub.2] when

Pr{[f.sub.R](x) = [f.sub.R](x')} [less than or equal to] [delta][2.sup.-m] [22]

for distinct elements x and x' in [F.sup.n.sub.2]. Here, Pr{C} expresses the probability that the condition C holds. When [delta]=1, it is [universal.sub.2]. Here, R denotes the random variable identifying the hash function. When a random hash function [f.sub.R] is linear, it is [delta]-almost [universal.sub.2] if and only if

Pr{x [member of] Ker [f.sub.R]} [less than or equal to] [delta][2.sup.-m] [23]

for any non-zero element x [member of] [F.sup.n.sub.2]. Here, Ker f is the kernel of the linear function f. Considering the space [(Ker f).sup.[perpendicular to]] orthogonal to Ker f in [F.sup.n.sub.2], we introduce another class of random hash functions. A linear random surjective hash function [f.sub.R] from [F.sup.n.sub.2] to [F.sup.m.sub.2] is called [delta]-almost dual [universal.sub.2] when

Pr{x [member of] [(Ker [f.sub.R]).sup.[perpendicular to]] L} [less than or equal to] [delta][2.sup.-n+m] [24]

for any non-zero element x [member of] [F.sup.n.sub.2]. As examples of [delta]-almost dual universal hash functions, the paper (56) proposed hash functions whose calculation complexity and random seeds are smaller than existing functions for practical use, as shown in Fig. 7.

When R is not a uniform random number the above concatenated Toeplitz matrix [M.sub.R] is not [universal.sub.2]; fortunately, it is [delta]-almost dual [universal.sub.2]. So, we can evaluate security in the framework of [delta]-almost dual [universal.sub.2] hash functions. That is, for a realistic setting, the concept of [delta]-almost dual [universal.sub.2] works well. Note that there exists a 2-almost [universal.sub.2] hash function whose resultant random number is insecure (Fig. 7). Hence, the concept of [delta]-almost dual universal is more useful than [delta]-almost [universal.sub.2].

C. Single-photon pulse with noise. To realize the security even with a noisy quantum channel, we need to modify the original QKD protocol. Since this modified protocol is related to error correction, finite-length analysis plays an important role to guarantee the security of the real QKD system. Here, for simplicity, we discuss only the finite-length security analysis with the Gaussian approximation.

The modified QKD protocol is the following. Steps (1), (2), and (3) are the same as in the original.

(4) [Error estimation] Alice and Bob randomly choose check bits from among the remaining bits, and they exchange their values via a public channel.

(*) In the following, we give a protocol for the bit basis. Here, we denote the number of remaining bits with the bit basis measurement by n, and we denote the numbers of check bits with the phase and bit basis measurements by l and l'. We denote the numbers of observed errors among check bits in the phase and bit basis measurements by c and c'.

(5) [Error correction] Alice and Bob apply error correction based on a k-dimensional subspace C and obtain k corrected bits. That is, Alice sends her syndrome to Bob via a public channel, and Bob corrects his error. Here, the length k and a code C are chosen by the observed error rate c'/l' with the bit basis measurement.

(6) [Privacy amplification] Alice and Bob apply a [delta]-almost dual [universal.sub.2] hash function from [F.sup.k.sub.2] to [F.sup.k-[bar.k].sub.2]. This protocol sacrifices [bar.k] bits, which is called the sacrifice bit length and is determined by the observed error rate c/l with the phase basis measurement. Then, Alice and Bob obtain final keys with length s := k - [bar.k].

To perform the finite-length security analysis approximately, we consider the following items.

(i) The virtual decoding phase error probability of a code C with an arbitrary decoder gives the amount of leaked information with privacy amplification by a hash function whose kernel is [C.sup.[perpendicular to]]. In this correspondence, the privacy amplification in the bit basis by a [delta]-almost dual [universal.sub.2] hash function [F.sup.k.sub.2] to [F.sup.k-k.sub.2] essentially realizes an error correction code in the phase basis whose parity check matrix is a [delta]-almost [universal.sub.2] hash function from [F.sup.n.sub.2] to [F.sup.[bar.k].sub.2]; [52, Lemmas 2 & 4][54, Theorem 2][57, (54)][115, Section 9.4.3][116, Section 5.6.2] [4].

(ii) When the total number of bits is n d l, the total number of errors is b, and we randomly choose l bits as the observed bits, the number of observed errors c is subject to the hypergeometric distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, the value (c - lb/n+l]) / [square root of l] approximately obeys the Gaussian distribution with variance bn(n+l-b)/[(n+l).sup.2](n+l-1)].

(iii) When the parity check matrix is given by a [delta]-almost [universal.sub.2] hash function from [F.sup.n.sub.2] to [F.sup.[bar.k].sub.2], the decoder is the minimum distance decoder, and the support of the distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of errors on [F.sup.n.sub.2] is included in the set {[x.sup.n] [member of] [F.sup.n.sub.2][parallel][x.sup.n]| = b - c}, the average decoding error probability is evaluated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [25]

where [E.sub.R] denotes the expectation with respect to the random variable R [52, Lemma 1][54, Theorem 3] [57, (37)].

(iv) The real distribution of error in the phase basis for n remaining qubits with the bit basis measurement and l check qubits with the phase basis measurement (n + l qubits in total) is written as a probabilistic mixture of distributions [P.sub.[bar.k]], where [P.sub.[bar.k]] is a distribution on {[x.sup.n] [member of] [F.sup.n+l.sub.2][parallel] [x.sup.n]|] = [bar.k]} [52, Section IV-B][54, Section III-C|[53, (18)]. (Any distribution on [F.sup.n.sub.2] satisfies this condition. In the memoryless case, the coefficients form a binomial distribution.)

To give our security criterion, we denote the information transmitted via the public channel by u, and introduce its distribution [P.sub.pub]. Depending on the public information u, we denote the state on the composite system of Alice's and Eve's systems, the state on Alice's system, the state on Eve's system, and the length of the final key length by [[rho].sub.A,E|u], [[rho].sub.A|u], [[rho].sub.E|u], and s(u), respectively. We denote the completely mixed state with length s(u) by [[rho].sub.A,mix|s(u)]. Then, similar to the security criterion is given in [53, (3)]

[1/2] [summation over u][P.sub.pub](u)[[parallel][[rho].sub.A,E|u] - [[rho].sub.A,mix|s(u)] [cross product] [[rho].sub.E|u][parallel].sub.1] [26]

Now, as a security condition, we impose the condition that [26] is smaller than [epsilon].

Combining the above four items, depending on c, we can derive the sacrifice bit length [bar.k](c). Although the exact formula of [bar.k](c) is complicated, it can be asymptotically expanded as [53, (53)]

[bar.k](c)=nh(c/l) - [square root of n]/2 h'(c/l)[square root of (c/l(1 - c/l)(1 + l/n)[n/l])] [[PHI].sup.-1]([epsilon].sup.2]/2) + o([square root of n]). [27]

Here, we should remark that this security analysis does not assume the memoryless condition for the quantum channel. To avoid this assumption, we introduce a random permutation and the effect of random sampling, which allows us to consider that the errors in both bases are subject to the hyper-geometric distribution. However, due to the required property of hash functions, we do not need to apply the random permutation in the real protocol. That is, we need to apply only random sampling to estimate the error rates of the phase basis.

Here, we need to consider the reliability, that is, the agreement of the final keys. For this purpose, we need to attach a key verification step as follows [122, Section VIII].

(7) [Key verification] Alice and Bob apply a [universal.sub.2] hash function from [F.sup.k-[bar.k].sub.2] to [F.sup.[??].sub.2] to the final keys. They exchange their results via a public channel. They discard their final [??] bits if they do not agree. Otherwise, they consider that their remaining keys agree.

However, the amount of leaked information for the final keys cannot be estimated by a similar method. So, the security analysis is more important than the agreement of the keys.

D. Weak coherent pulse with noise. Next, we discuss a weak coherent pulse with noise, whose device is illustrated in Fig. 8. Since the above protocol assumes single-photon pulses, when the pulse contains multiple photons even occasionally, the above protocol cannot guarantee security. Since it is quite difficult to generate a single-photon pulse, we usually employ weak coherent pulses with phase randomization, whose states are written as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [micro] is called the intensity. That is, weak coherent pulses contain multiple-photon pulses, as shown in Fig. 9. In this case, there are several multiple-photon pulses among n received pulses. In optical communication, only a small fraction of pulses arrive at the receiver side. That is, the ratio of multiple-photon states of Alice's side is different from that of Bob's side. This is because the detection ratio on Bob's side depends on the number of photons.

As the first step in the security analysis, we need to estimate the ratios of vacuum pulses, single-photon pulses, and multiple-photon pulses among n received pulses. Indeed, there is a possibility that Bob erroneously detects the pulse even with a vacuum pulse. To obtain this estimate, we remark that the ratio of multiple-photon pulses depends on the intensity [mu]. Hence, it is possible to estimate the detection ratios of vacuum pulses, single-photon pulses, and multiple-photon at Bob's side from the detection ratios of more than 3 different intensities, which are obtained by solving simultaneous equations. (44-50,113) Observing the error rate of each pulse depending on the intensity and the basis, we can estimate the error rates of both bases for vacuum pulses, single-photon pulses, and multiple-photons. This idea is called the decoy method. Based on this discussion, we change steps (1), (2), (3), and (4). However, we do not need to change steps (5) and (6), in which we choose the error correcting code and the sacrifice bit length.

As the second step of the security analysis, when n received pulses are composed of [n.sub.0] vacuum pulses, [n.sub.1] single-photon pulses, and [n.sub.2] multiple-photon pulses, we need to estimate the leaked information after the privacy amplification with sacrifice bit length [bar.k]. In the current case, we replace items (i) and (iii) by the following.

(i') When n received pulses are composed of [n.sub.0] vacuum pulses, [n.sub.1] single-photon pulses, and [n.sub.2] multiple-photon pulses, then, [n.sub.0] vacuum pulses are converted to noiseless single-photon pulses and [n.sub.2] multiple-photon pulses are converted to noiseless single-photon pulses whose error distribution is the uniform distribution [54, Section III-B]. Then, we have the same statement as (i).

(iii') Assume that the parity check matrix is given by a [delta]-almost [universal.sub.2] hash function from [F.sup.n.sub.2] to [F.sup.[bar.k].sub.2] We also make an assumption for the distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; [n.sub.0] bits have no error, there are [t.sub.1] errors among the [n.sub.1] bits, and the distribution of errors on the [n.sub.2] bits is the uniform distribution. So, the decoder [GAMMA]([y]) is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [28]

where (*) is the condition that all of entries among the above [n.sub.0] bits are 0, and [parallel] [x.sup.n] [parallel] is the number of bits with entry 1 among the above [n.sub.1] bits. Then, the average decoding error probability is evaluated as [54, Theorem 3]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [29]

Finally, we combine the original items (ii) and

(iv) with the above modified items (i') and (iii'). However, due to the complicated estimation process for the partition [n.sub.0], [n.sub.1], [n.sub.2] of n qubits, we need a very complicated discussion. Based on such an analysis, after long calculation, we obtain a formula for the sacrifice bit length, as shown in Fig. 10.

E. History of developments of QKD. Because the raw keys are not necessarily secure when the channel has noise or two photons are transmitted, many studies have been done to find a way to guarantee security when the communication device has such imperfections. For this purpose, we need to consider a partial information leakage whose amount is bounded by the amount of the imperfection. Shor and Preskill (41) and Mayers (42) showed that privacy amplification generates secure final keys even when the channel has noise when the light source correctly generates a singlephoton. Gottesman et al. (43) showed that these final keys can be secure even when the light source occasionally generates multiple photons if the fraction of multiple photon pulses is sufficiently is small. The light source used in the actual quantum optical communication is the weak coherent light, which probabilistically generates some multiple photon pulses, as shown in Fig. 9. Hence, this kind of extension had been required for practical use. Hwang (44) proposed an efficient method to estimate the fraction of multiple photon pulses, called the decoy method, in which the sender randomly chooses pulses with different intensities.

Until this stage, the studies of QKD were mainly done by individual researchers. However, project style research is needed for a realization of QKD because the required studies need more interactions between theorists and experimentalists. A Japanese project, the ERATO Quantum Computation and Information Project, tackled the problem of guaranteeing the security of a real QKD system. Since this project contained an experimental group as well as theoretical groups, this project naturally proceeded to a series of studies of QKD from a more practical viewpoint. First, one project member, Hamada (109,110) studied the relation between the quantum error correcting code and the security of QKD more deeply. Then, another project member, Wang (46,48) extended the decoy method, which was developed independently by a group at Toronto University. (45,47) Tsurumaru (50) and the author (49) have further extended the method. These extended decoy methods give a design for the choice of the intensity of transmitted pulses. Further, jointly with the Japanese company NEC, the experimental group demonstrated QKD with spools of standard telecom fiber over 100 km. (111)

Here, we note that the theoretical results above assume the combination of error correction and privacy amplification for an infinitely large block-length in steps (5) and (6). They did not give a quantitative evaluation of the security with finite-block-length. They also did not address the construction of privacy amplification so these results are not sufficient for realization of a quantum key distribution system. To resolve this issue, as a member of this project, the author (52) approximately evaluated the security with finite-block-length n when the channel has noise and the light source correctly generates a single photon. This idea has two key points. The first contribution is the evaluation of information leakage via the phase error probability of virtual error correction in the phase basis, which is summarized as item (i). This evaluation is based on the duality relation in quantum theory, which typically appears in the relation between position and momentum. The other contribution is the approximate evaluation of the phase error probability via the application of the central limit theorem, which is obtained by the combination of items (iii) and (iv). This analysis is essentially equivalent to the derivation of the coefficient of the transmission rate up to the second-order 1/[square root of n]. However, this analysis assumed a single-photon source. Under this assumption, the author discussed the optimization for the ratio of check bits. (112) Based on a strong request from the project leader of the ERATO project and helpful suggestions by the experimental group, using the decoy method, he extended a part of his analysis to the case when the light source sometimes generates multiple photons (54) by replacing item (iv) by (iv'). Based on this analytical result, the ERATO project made an experimental demonstration of QKD with weak coherent pulses on a real optical fiber, whose security is quantitatively guaranteed in the Gaussian approximation. (51)

Another Japanese project of the National Institute of Information and Communication Technology (NICT) has continuously made efforts toward a realization of QKD. After the ERATO project, the author joined the NICT project from 2011 to 2016. The NICT organized a project in Tokyo (Tokyo QKD Network) by connecting QKD devices operated by NICT, NEC, Mitsubishi Electric, NTT, Toshiba Research Europe, ID Quantique, the Austrian Institute of Technology, the Institute of Quantum Optics and Quantum Information and the University of Vienna in 2010. (59) Also, as a part of the NICT project, NEC developed a QKD system, as shown in Fig. 8, and performed a long-term evaluation experiment in 2015. (58)

After the above ERATO project, two main theoretical problems remained, and their resolutions had been strongly required by the NICT project because they are linked to the security evaluation of these installed QKD systems. The first one was the complete design of privacy amplification. Indeed, in the above security analysis based on the phase error probability, the range of possible random hash functions was not clarified. That is, only one example of a hash function was given in the paper, (54) and we had only a weaker version of item (ii) at that time. To resolve this problem, as members of the NICT project, Tsurumaru and the author clarified what kind of hash functions can be used to guarantee the security of a QKD system, (57) which yields the current item (ii). They introduced [delta]-almost dual [universal.sub.2] hash functions, as explained in Section VI-B. In these studies, Tsurumaru taught the author the practical importance of the construction of hash functions from an industrial viewpoint based on his experience obtained as a researcher at Mitsubishi Electric.

The second problem was to remove the Gaussian approximation in (52) from the finite-length analysis. Usually, security analysis requires rigorous evaluation without approximation. Hence, this requirement was essential for the security evaluation. In Hayashi and Tsurumaru, (53) we succeeded in removing this approximation and obtained a rigorous security analysis for the single-photon case. Also, the paper (53) clarified the security criterion and simplified the derivation in the discussion given in Subsection VI-C. Based on a strong request by the NICT project, the author extended the finite-length analysis to the case with multiple photons by employing the decoy method and performing a complicated statistical analysis. (55) The transmission rate in the typical case is shown in Fig. 10. This study clarified the requirements for physical devices to apply the obtained security formula. In this study, (55) the author also improved an existing decoy protocol. Under the improved protocol, he optimizes the choice of intensities. (113) Finally, we should remark that only such a mathematical analysis can guarantee the security of QKD. This is quite similar to the situation that conventional security measures, like RSA, can be guaranteed by mathematical analysis of the computational complexity. (108) In this way QKD is different from conventional communication technology.

Here, we should address the security analysis based on the leftover hash lemma (62,63) as another research stream of QKD. This method came from cryptography theory and was started by the Renner group at the Swiss Federal Institute of Technology in Zurich (ETH). (66) The advantage of this method is the direct evaluation of information leakage without needing to evaluate the virtual phase error probability. This method also enables a security analysis with finite-block-length. (67) However, their finite-block-length analysis is looser than our analysis in Hayashi and Tsurumaru (53) because their bound (67) cannot yield the second-order rate based on the central limit theorem whereas it can be recovered from the bound in Hayashi and Tsurumaru. (53) Further, while their method is potentially precise, it has very many parameters to be estimated in the finite-block-length analysis. Although their method improves the asymptotic generation rate, (114) the increase in the number of parameters to be estimated enlarges the error of channel estimation in the finite-length setting. Hence, they need to decrease the number of parameters to be estimated. In their finite-block-length analysis, they simplified their analysis so that only the virtual phase error probability has to be estimated. This simplification improves the approach based on the leftover hash lemma because it gives a security evaluation based on the virtual phase error probability more directly. However, this approach did not consider security with weak coherent pulses. As another merit, the approach based on the leftover hash lemma later influenced the security analysis in the classical setting. (76,96-99)

To discuss the future of QKD, we now describe other QKD projects. Several projects were organized in Hefei in 2012 and in Jinan in 2013. (60) In 2013, a US company, Battelle, implemented a QKD system for commercial use in Ohio using a device from ID Quantique. (61) Battelle has a plan to establish a QKD system between Ohio and Washington, DC, over a distance of 700km. (61) Also, in China, the Beijing-Shanghai project almost established a QKD system connecting Shanghai, Hefei, Jinan, and Beijing with over a distance of 2,000 km. (60) Indeed, these implemented QKD networks are composed of a collection of QKD communications over relatively short distance. However, quite recently, a Chinese group has succeeded in realizing a satellite for quantum communications. Since most of these developments are composed of networks of quantum communication channels, it is necessary to develop theoretical results to exploit the properties of quantum networks for a QKD system.

VII. Second-order channel coding

Now, we return to classical channel coding with the memoryless condition. In the channel coding, it is important to clarify the difference between the asymptotic transmission rate and the actual optimal transmission rate dependent on the block-length, as shown in Fig. 11. This is because many researchers had mistakenly thought that the actual optimal transmission rate equals the asymptotic transmission rate for a long time.

When the channel [P.sub.Y|X] is given as a binary additive noise subject to the distribution [P.sub.Z] and the channel [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the product distribution of the channel [P.sub.Y|X], the simple combination of [10] and [18] yields the asymptotic expansion of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [30]

because Eq. [10] does not contain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] like [9]. In the general case, using the formulas [16] or [9] with order [absolute value of n], we can derive the [greater than or equal to] part of the following inequality.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [31]

where V([P.sub.Y|X]) is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [32]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [33]

and the minimum and maximum are taken over the [P.sub.X] satisfying I([P.sub.X], [P.sub.Y|X]) = [max.sub.Q] I(Q, [P.sub.Y|X]). However, it is difficult to derive the [less than or equal to] part of inequality [32] by using [9] due to the maximization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To resolve this problem, we choose [P.sub.X] as the distribution realizing the minimum in [33] or the maximum in [32] and substitute [P.sup.n.sub.X] into [Q.sub.n] in the formula [17]. Then, we can derive the [less than or equal to] part of the inequality [31]. Although this expansion was firstly derived by Strassen (5) in 1962, this derivation is much simpler, which shows the effectiveness of the method of information spectrum.

The author applied this method to an additive white Gaussian noise channel and succeeded in deriving the second-order coefficient of its transmission rate, which had been unknown until that time; this was published in 2009. (9) In fact, he obtained only a rederivation of Strassen's result. When he presented this result in a domestic meeting, (69) Uyematsu pointed out Strassen's result. To go beyond Strassen's result, he applied this idea to the additive white Gaussian noise channel, and obtained the following expansion, which appears as a typical situation in wireless communication.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [34]

where M ([epsilon] | S, N) is the maximum size of transmission when the variance of the Gaussian noise is N and the power constraint is S.

In fact, a group in Princeton University, mainly Verdu and Polyanskiy, tackled this problem independently. In their papers, (6,7) they considered the relation between channel coding and simple statistical hypothesis testing, and independently derived two relations, the dependence test bound and the meta converse inequality, which are the same as in the classical special case considered in the author and Nagaoka (33) and Nagaoka. (34) Since their results (6) are limited to the classical case, the applicable region of their results is narrower than that of the preceding results in. (33,34) Then, Verdu and Polyanskiy rederived Strassen's result, without use of the method of information spectrum, by the direct evaluation of these two bounds. They also independently derived the second-order coefficient of the optimal transmission rate for the additive white Gaussian noise channel in 2010. (6) Since the result by this group at Princeton had a large impact in the information theory community at that time, their paper received the best paper award of IEEE Information theory society in 2011 jointly with the preceding paper by the author. (9)

As explained above, the Japanese group obtained some of the same results several years before the Princeton group but had much weaker publicity than the Princeton group. Thus, the Princeton group met the demand in the information theory community, and they presented their results very effectively. In particular, since their research activity was limited to the information theory community, their audiences were suitably concentrated so that they could create a scientific boom in this direction. In contrast to the Princeton group, the Japanese group studied the same topic far from the demand of the community because their study originated in quantum information theory. In particular, their research funds were intended for the study of quantum information so they had to present their work to quantum information audiences who are less interested in their results. Also, because their work was across too wide a research area to explain their results effectively, they could not devote sufficient efforts to explain their results to the proper audiences at that time. Hence, their papers attracted less attention. For example, few Japanese researchers knew the paper (9) when it received the IEEE award in 2011. After this award, this research direction became much more popular and was applied to very many topics in information theory. (10-14,17,71,72,76) In particular, the third-order analysis has been applied to channel coding. (15) These activities were reviewed in a recent book. (74)

Although this research direction is attracting much attention, we need to be careful about evaluating its practical impact. These studies consider finite-block-length analysis for the optimal rate with respect to all codes including those with too high a calculation complexity to implement. Hence, the obtained rate cannot necessarily be realized with implementable codes. To resolve this issue, we need to discuss the optimal rate among codes whose calculation complexity is not so high. Because no existing study discusses this type of finite-block-length analysis, such a study is strongly recommend for the future. Also, a realistic system is not necessarily memoryless; so, we need to discuss memory effects. To resolve this issue, jointly with Watanabe, the author extended this work to channels with additive Markovian noise, which covers the case when Markovian memory exists in the channel. (71) While this model covers many types of realistic channel, it is not trivial to apply the results in (71) to the realistic case of wireless communication because it is complicated to address the effect of fading in the coefficients. This is an interesting future problem.

After this breakthrough, the Princeton group extended their idea to many topics in channel coding and data compression. (10,11,14,70) On the other hand, in addition to the above Markovian extension, the author, jointly with Tomamichel, extended this work to the quantum system, (73) providing a unified framework for the second-order theory in the quantum system for data compression with side information, secure uniform random number generation, and simple hypothesis testing. At the same time, Li (75) directly derived the second-order analysis for simple statistical hypothesis testing in the quantum case. However, the second-order theory for simple statistical hypothesis testing has less meaning in itself; it is more meaningful in relation to other topics in information theory.

VIII. Extension to physical layer security

A. Wire-tap channel and its variants. The quantum cryptography explained above offers secure key distribution based on physical laws.

The classical counterpart of quantum cryptography is physical layer security, which offers information theoretical security based on several physical assumptions from classical mechanics. As its typical mode, Wyner (77) formulated the wire-tap channel model, which was more deeply investigated by Csiszar and Koner. (78) This model assumes two channels, as shown in Fig. 12: a channel [P.sub.Y|X] from the authorized sender (Alice) to the authorized receiver (Bob) and a channel [P.sub.Z|X] from the authorized sender to the eavesdropper (Eve). When the original signal of Alice has stronger correlation with the received signal than that with Eve, that is, a suitable input distribution [P.sub.X] satisfies the condition I([P.sub.X], [P.sub.Y|X]) > I([P.sub.X], [P.sub.Z|X]), the authorized users can communicate without any information leakage by using a suitable code. More precisely, secure communication is available if and only if there exists a suitable joint distribution [P.sub.VX] between the input system X and another system V such that the condition I([P.sub.V], [P.sub.Y|V]) > I([P.sub.V], [P.sub.Z|V]) holds, where [P.sub.Y|V](y|v) := [[summation].sub.x [member of] X] [P.sub.Y|X] (y|x) [P.sub.X|V] (x|v) and [P.sub.Z|V] is defined in the same way.

Although we often assume that the channel is stationary and memoryless, the general setting can be discussed by using information spectrum. (95) This paper explicitly pointed out that there is a relation between the wire-tap channel and the channel resolvability discussed in Section IV. This idea has been employed in many subsequent studies. (126,138,139,142) Watanabe and the author (123) discussed the second-order asymptotic for the channel resolvability. Also, extending the idea of the meta converse inequality to the wire-tap channel, Tyagi, Watanabe, and the author showed a relation between the wire-tap channel and hypothesis testing. (125) Based on these results, Yang et al. (124) investigated finite-block-length bounds for wiretap channels without Gaussian approximation. Also, taking into account the construction complexity, the author and Matsumoto [128, Section XI] proposed another type of finite-length analysis for wire-tap channels. Its quantum extension has also been discussed. (171,118) However, in the wire-tap channel model, we need to assume that Alice and Bob know the channel [P.sub.Z|X] to Eve. Hence, although it is a typical model for information theoretic security, this model is somewhat unrealistic because Alice and Bob cannot identify Eve's behavior. That is, it is assumed that Eve has weaker connection to Alice than Bob does, as shown in Fig. 12. So, it is quite hard to find a realistic situation where the original wire-tap channel model is applicable.

Fortunately, this model has more realistic derivatives: one is secret sharing, (135,136) and another is secure network coding. (81-85,129)) In secret sharing, there is one sender, Alice, and k receivers, Bob1, ..., Bobk. Alice splits her information into k parts, and sends them to the respective Bobs such that a subset of Bobs cannot recover the original message. For example, assume that there are two Bobs, [X.sub.1] is the original message and [X.sub.2] is an independent uniform random number. If Alice sends the exclusive or of [X.sub.1] and [X.sub.2] to Bob1 and sends [X.sub.2] to Bob2, neither Bob can recover the original message. When both Bobs cooperate, however, they can recover it. In the general case, for any given numbers [k.sub.1] < [k.sub.2] < k, we manage our code such that any set of [k.sub.1] Bobs cannot recover the original message but any set of [k.sub.2] Bobs can. (130)

Secure network coding is a more difficult task. In secure network coding, Alice sends her information to the receiver via a network, and the information is transmitted to the receiver via intermediate links. That is, each intermediate link transfers a part of the information. Secure network coding is a method to guarantee security when some of the intermediate links are eavesdropped by Eve. Such a method can be realized by applying the wire-tap channel to the case when Eve obtains the information from some of intermediate links. (81-85,129) When each intermediate link has the same amount of information, the required task can be regarded as a special case of secret sharing.

However, this method depends on the structure of the network, and it is quite difficult for Alice to know this structure. Hence, it is necessary to develop a coding method that does not depend on the structure of the network. Such a coding is called universal secure network coding, and has been developed by several researchers. (86,131-134) These studies assume only that the information processes on each node are linear and the structure of network does not change during transmission. In particular, the security evaluation can be made even with finite block-length codes. (86,133,134) Since it is quite hard to tap all of the links, this kind of security is sufficiently useful for practical use by ordinary people based on the cost-benefit analysis of performance. To understand the naturalness of this kind of assumption, let us consider the daily-life case in which an important message is sent by dividing it into two e-mails, the first of which contains the message encrypted by a secure key, and the second one contains the secure key. This situation assumes that only one of two links is eavesdropped.

B. Secure key distillation. As another type of information theoretical security, Ahlswede and Csiszar (80) and Maurer (79) proposed secure key distillation. Assume that two authorized users, Alice and Bob, have random variables X and Y, and the eavesdropper, Eve, has another random variable Z. When the mutual information I(X; Y) between Alice and Bob is larger than the mutual information 1(X; Z) or 1(Y; Z) between one authorized user and Eve, and when their information is given as the n-fold iid distribution of a given joint distribution [P.sub.XYZ], Alice and Bob can extract secure final keys.

Recently, secure key distillation has been developed in a more practical way by importing the methods developed for or motivated by quantum cryptography. (38,76,96-100) In particular, its finite-block-length analysis has been much developed, including the Markovian case, when Alice's random variable agrees with Bob's random variable. (76,96-99) Such a analysis has been extended to a more general case in which Alice's random variable does not necessarily agree with Bob's random variable. (127) Although some of the random hash functions were originally constructed for quantum cryptography, they can be used for privacy amplification even in secure key distillation. (56,64,65) Hence, under several natural assumptions for secure key distillation, it is possible to precisely evaluate the security based on finite-block-length analysis.

We assume that X is a binary information, and all information is given as the n-fold iid distribution of a given joint distribution [P.sub.XYZ]. In this case, the protocol is essentially given by steps (5) and (6) of QKD, where the code C, its dimension k, and the sacrifice bit length [bar.k] are determined a priori according to the joint distribution [P.sub.XYZ]. Now, we denote the information exchanged via the public channel by u and its distribution by [P.sub.pub]. The security is evaluated by the criterion;

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [35]

where [P.sub.R] is the distribution of the random variable R used to choose our hash function [f.sub.R]. To evaluate this criterion, we introduce the conditional Renyi entropy [5]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [36]

Then, the criterion is evaluated as ([98, (54) and Lemma 22] and [119, (21)] [6])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [37]

Its quantum extension has also been discussed in. (119,120)

Here, we should remark that the evaluation [37] can be realized by a random hash function with small calculation complexity. This is because the inequality holds for an arbitrary linear code and an arbitrary [delta]-almost dual [universal.sub.2] hash function. Since the paper (56) proposed several efficient [delta]-almost dual [universal.sub.2] hash functions, the bound has operational meaning even when we take into account the calculation complexity for its construction.

So, one might consider that secure key distillation is the same as QKD. However, QKD is different from secure key distillation even with the quantum extension due to the following points. The advantage of QKD is that it does not assume anything except for the basic laws of quantum theory. Hence, QKD usually does not allow us to make any additional assumptions, in particular, the iid assumption. In contrast, in secure key generation, we often make the iid assumption. As another difference, we are assumed to know the joint distribution or the density matrix on the whole system in secure key distillation whereas we need to estimate only the density matrix on the whole system in QKD.

The finite-block-length analysis of secure key distillation is different from that for channel coding in the following point. The obtained finite-block-length analysis for channel coding discusses only the optimal performance among all codes, including impractical codes whose calculation complexity is too high. However, in the finite-block-length analysis for physical layer security, the obtained bound can be attained by a practical protocol whose calculation complexity is linear in the block-length.

C. Application to wireless communication. Recently, along with the growing use of wireless communication, secure wireless communication has been very actively studied. (88-94) Physical layer security has been considered as a good candidate for secure wireless communication. (140,141) Typically, we assume the quasi-static condition, which allows us to assume the memoryless condition in one coding block-length. Even with this condition, a simple application of the wire-tap channel cannot guarantee secure communication when Eve set up her antenna between Alice and Bob. However, when the noise in Bob's output signal is independent of the noise in Eve's output signal, the mutual information between Alice and Bob is larger than that between Eve and Bob even in this situation. In this case, when they apply secure distillation in the opposite way after the initial wireless communication from Alice to Bob, they can generate secure keys. The assumption of the independence between Bob's and Eve's outputs is too strong and unrealistic for a practical use because there is a possibility of interference between the two channels. Hence, a more realistic assumption is needed.

To resolve this problem, the author had the following idea based on the experience of interactions with experimentalists studying QKD. It is natural to assume that the noises generated inside each detector are independent and Gaussian, and only the noise generated outside the detector is correlated to Eve's output. In this situation, even when all of the intermediate space between Alice and Bob is under the control of Eve and Eve injects artificial noise into Bob's observation, as in Fig. 13, when the noise is sufficiently small, the author showed that Alice and Bob can still generate secure keys. (87) Here, after the communication via the noisy wireless channel, Alice and Bob need to estimate the noise by random sampling. Once the random sampling guarantees that the noise is sufficiently small, they apply the secure key generation protocol. This is a protocol to generate secure keys between Alice and Bob under reasonable assumptions for secure wireless communication. Although the paper (87) gives such a protocol with a small calculation complexity for construction, the real performance of this protocol has not been studied in real situations. A future task is to estimate the performance of the proposed method in a realistic situation by taking into account several complicated realistic effects, including fading.

Here, we summarize the advantages over modern cryptography based on computation complexity. (92) When cryptography based on computation complexity is broken by a computer, any information transmitted with this cryptography can be eavesdropped by using that computer. To break physical layer security of the above type, Eve has to set up an antenna for each communication. Furthermore, each antenna must be very expensive because it must break the above assumption. Maybe, it is not impossible to break a limited number of specific communications for a very limited number of persons. However, due to the cost constraint, it is impossible to eavesdrop on all communications in a realistic situation. In this way, physical layer security offers a different type of security from computational security.

IX. Conclusions and future prospects

In this review article, we have discussed developments of finite-block-length theory in classical and quantum information theory: classical and quantum channel coding, data compression, (secure) random number generation, quantum cryptography, and physical layer security. These subareas have been developed with strong interactions with each other in unexpected ways.

The required future studies for channel coding and data compression are completely different from those needed for security topics. In the former topics, existing finite-block-length theory discusses only the minimum error among all codes without considering the calculation complexity of its construction. Hence, for practical use, we need a finite-block-length theory for realizable codes whose construction has less calculation complexity. Such finite-block-length theory is urgently required. Fortunately, the latest results obtained for these two topics (71,72) cover the case when a Markovian memory effect exists. However, their applications to a realistic situation have not been sufficiently studied, and such practical applications are interesting open problems.

In contrast, in the latter topics, the established finite-block-length theory already takes into account the calculation complexity of its construction; hence, it is more practical. However, these types of security protocols have not been realized for the following reasons. In the case of quantum cryptography, we need more development on the device side. Also, to realize secure communication for distances over 2000 km, we might need another type of information-scientific combinatorics. In the case of physical layer security, we need more studies to fill the gap between information theoretical security analysis and device development. There has recently been one such study. (87)

Furthermore, the idea of finite-block-length theory is fundamental and can be extended to areas beyond information theory. For example, it has been applied to a statistical mechanical rederivation of thermodynamics, (101,102) the conversion of entangled states, (103-106) and the analysis of the gap between two classes of local operations. (107) Therefore, we can expect more applications of finite-block-length theory to other areas.

Acknowledgments

The works reported here were supported in part by a MEXT Grant-in-Aid for Scientific Research (A) No. 23246071, a JSPS Grant-in-Aid for Young Scientists (A) No. 20686026, a JSPS Grant-in-Aid for Young Scientists (B) No. 14750330, a JSPS Grant-in-Aid for Scientific Research on Priority Area "Deepening and Expansion of Statistical Mechanical Informatics (DEX-SMI)" No. 18079014, ERATO (-SORST) Quantum Computation and Information Project of the Japan Science and Technology Agency (JST), the Brain Science Institute of RIKEN, the National Institute of Information and Communication Technology (NICT), Japan, the Okawa Research Grant, and the Kayamori Foundation of Informational Science Advancement. The author is grateful to Professor Akihisa Tomita, who is an expert on the physical implementation of QKD systems, for discussing the physical model for a real QKD system. He is also thankful to Dr. Toyohiro Tsurumaru and Dr. Kiyoshi Tamaki, who are working on QKD from an industrial perspective, for discussing the physical assumptions for the decoy model. He is also grateful to Professor Angeles Vazquez-Castro, Professor Hideichi Sasaoka, and Professor Hisato Iwai, who are experts in wireless communication, for discussing the validity of the model of the paper (87) for secure wireless communication. He is also thankful to Dr. Ken-ichiro Yoshino in NEC for providing the picture of the QKD device (Fig. 8).

References

(1) Shannon, C.E. (1948) A mathematical theory of communication. Bell Syst. Tech. J. 27, 623-656.

(2) Gallager, R.G. (1968) Information Theory and Reliable Communication. New York, Wiley.

(3) Berrou, C., Glavieux, A. and Thitimajshima, P. (1993) Near Shannon limit error-correcting coding and decoding: Turbo-codes 1. Communications. ICC '93 Geneva. Technical Program, Conference Record, IEEE International Conference on (Volume 2) pp. 1064-1070.

(4) MacKay, D.J.C. and Neal, R.M. (1996) Near Shannon limit performance of low density parity check codes. Electron. Lett. 32, 1645-1646.

(5) Strassen, V. (1962) Asymptotische Abschatzugen in Shannon's Informationstheorie, In Transactions of the Third Prague Conference on Information Theory etc., Czechoslovak Academy of Sciences, Prague, pp. 689-723. (In German); English translation in 2009 is available at http://www.math.cornell.edu/pmlut/strassen.pdf.

(6) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2010) Channel coding rate in the finite blocklength regime. IEEE Trans. Inf. Theory 56, 2307-2359.

(7) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2008) New channel coding achievability bounds. In Proceeding of 2008 IEEE Int. Symposium on Information Theory. Toronto, Ontario, Canada, pp. 1763-1767.

(8) Hayashi, M. (2008) Second-order asymptotics in fixed-length source coding and intrinsic randomness. IEEE Trans. Inf. Theory 54, 4619-4637.

(9) Hayashi, M. (2009) Information spectrum approach to second-order coding rate in channel coding. IEEE Trans. Inf. Theory 55, 4947-4966.

(10) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2011) Feedback in the non-asymptotic regime. IEEE Trans. Inf. Theory 57, 4903-4925.

(11) Polyanskiy, Y., Poor, H.V. and Verdu, S. (2011) Dispersion of the Gilbert-Elliott channel. IEEE Trans. Inf. Theory 57, 1829-1848.

(12) Tan, V.Y.F. and Kosut, O. (2014) On the dis persions of three network information theory problems. IEEE Trans. Inf. Theory 60, 881-903.

(13) Watanabe, S., Kuzuoka, S. and Tan, V.Y.F. (2015) Nonasymptotic and second-order achievability bounds for coding with side-information. IEEE Trans. Inf. Theory 61, 1574-1605.

(14) Kostina, V. and Verdu, S. (2012) Fixed-length lossy compression in the finite blocklength regime. IEEE Trans. Inf. Theory 58, 3309-3338.

(15) Tomamichel, M. and Tan, V.Y.F. (2013) A tight upper bound for the third-order asymptotics for most discrete memoryless channels. IEEE Trans. Inf. Theory 59, 7041-7051.

(16) Han, T.-S. (2016) Celebrating Receipt of JSPS Prize and Japan Academy Medal by Prof. Masahito Hayashi His Personality and Tracks of Research Activites. EICE ESS Fundamentals Review 10, 100-103 (in Japanese).

(17) Yagi, H., Han, T.S. and Nomura, R. (2016) First and second-order coding theorems for mixed memoryless channels with general mixture. IEEE Transactions on Information Theory 62, 4395-4412.

(18) Hayashi, M. (2016) Role of quantum information theory in information theory beyond the non-commutative extension. IEICE ESS Fundamentals Review 10, 4-13 (in Japanese).

(19) Takahasi, H. (1965) Information theory of quantum mechanical channels. Adv. Commun. Systems 1, 227-310.

(20) Helstrom, C.W. (1967) Detection theory and quantum mechanics. Inf. Constr. 10, 254-291.

(21) Helstrom, C.W. (1967) Minimum mean-square error estimation in quantum statistics. Phys. Lett. 25A, 101-102.

(22) Holevo, A.S. (1982) Probabilistic and Statistical Aspects of Quantum Theory. North-Holland, Amsterdam; originally published in Russian (1980).

(23) Holevo, A.S. (1973) Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii 9, 3-11 (in Russian). (English translation: Probl. Inf. Transm. 9, 177-183 (1975)).

(24) Holevo, A.S. (1979) On the capacity of quantum communication channel. Problemly Peredachi Informatsii 15, 3-11 (in Russian). (English translation: Probl. Inf. Transm. 15, 247-253).

(25) Schumacher, B. (1995) Quantum coding. Phys. Rev. A 51, 2738-2747.

(26) Holevo, A.S. (1998) The capacity of the quantum channel with general signal states. IEEE Trans. Inf. Theory 44, 269.

(27) Schumacher, B. and Westmoreland, M.D. (1997) Sending classical information via noisy quantum channels. Phys. Rev. A 56, 131.

(28) Han, T.S. and Verdu, S. (1993) Approximation theory of output statistics. IEEE Trans. Inf. Theory 39, 752-772.

(29) Vembu, S. and Verdu, S. (1995) Generating random bits from an arbitrary source: Fundamental limits. IEEE Trans. Inf. Theory 41, 1322-1332.

(30) Verdu, S. and Han, T.S. (1994) A general formula for channel capacity. IEEE Trans. Inf. Theory 40, 1147-1157.

(31) Han, T.-S. (2003) Information-Spectrum Methods in Information Theory. Springer, Berlin. (Original Japanese version was published from Baifukan in 1998).

(32) Nagaoka, H. and Hayashi, M. (2007) An information-spectrum approach to classical and quantum hypothesis testing. IEEE Trans. Inf. Theory 53, 534-549.

(33) Hayashi, M. and Nagaoka, H. (2003) General formulas for capacity of classical-quantum channels. IEEE Trans. Inf. Theory 49, 1753-1768.

(34) Nagaoka, H. (2001) Strong converse theorems in quantum information theory. Proc. ERATO Conference on Quantum Information Science (EQIS) 2001, 33. (also appeared as Chap. 3 of Asymptotic Theory of Quantum Statistical Inference, M. Hayashi eds.).

(35) Hayashi, M. (2006) Quantum Information: An Introduction. Springer. (Original Japanese version was published from Saiensu-sha in 2004).

(36) Han, T.S. (2005) Folklore in source coding: in formation-spectrum approach. IEEE Trans. Inf. Theory 51, 747-753.

(37) Renner, R. and Konig, R. (2005) Universally composable privacy amplification against quantum adversaries. In Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005 (ed. Kilian, J.). Lecture Notes in Computer Science, vol. 3378, Springer Verlag, pp. 407-425.

(38) Watanabe, S., Matsumoto, R. and Uyematsu, T. (2010) Strongly secure privacy amplification cannot be obtained by encoder of Slepian-Wolf code. IEICE Trans. Fundamentals EA-93, 1650-1659.

(39) Hayashi, M. and Matsumoto, R. (2016) Secure multiplex coding with dependent and non-uniform multiple messages. IEEE Trans. Inf. Theory 62, 2355-2409.

(40) Bennett, C.H. and Brassard, G. (1984) Quantum cryptography: public key distribution and coin tossing. In Proc. IEEE International Conference on Computers, Systems and Signal Processing. Bangalore, India, pp. 175-179.

(41) Shor, P.W. and Preskill, J. (2000) Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett. 85, 441-444.

(42) Mayers, D. (2001) Unconditional security in quantum cryptography. J. Assoc. Comput. Mach. 48, 351.

(43) Gottesman, D., Lo, H.-K., Lutkenhaus, N. and Preskill, J. (2004) Security of quantum key distribution with imperfect devices. Quant. Inf. Comput. 5, 325-360.

(44) Hwang, W.-Y. (2003) Quantum key distribution with high loss: toward global secure communication. Phys. Rev. Lett. 91, 057901.

(45) Lo, H.-K., Ma, X. and Chen, K. (2005) Decoy state quantum key distribution. Phys. Rev. Lett. 94, 230504.

(46) Wang, X.-B. (2005) Beating the photon-number splitting attack in practical quantum cryptography. Phys. Rev. Lett. 94, 230503.

(47) Ma, X.-F., Qi, B., Zhao, Y. and Lo, H.-K. (2005) Practical decoy state for quantum key distribution. Phys. Rev. A 72, 012326.

(48) Wang, X.-B. (2005) A decoy-state protocol for quantum cryptography with four intensities of coherent states. Phys. Rev. A 72, 012322.

(49) Hayashi, M. (2007) General theory for decoy-state quantum key distribution with an arbitrary number of intensities. New J. Phys. 9, 284.

(50) Tsurumaru, T., Soujaeff, A. and Takeuchi, S. (2008) Exact minimum and maximum of yield with a finite number of decoy light intensities. Phys. Rev. A 77, 022319.

(51) Hasegawa, J., Hayashi, M., Hiroshima, T., Tanaka, A. and Tomita, A. (2007) Experimental decoy state quantum key distribution with unconditional security incorporating finite statistics. arXiv:0705.3081.

(52) Hayashi, M. (2006) Practical evaluation of security for quantum key distribution. Phys. Rev. A 74 022307.

(53) Hayashi, M. and Tsurumaru, T. (2012) Concise and tight security analysis of the Bennett-Brassard 1984 protocol with finite key lengths. New J. Phys. 14, 093014.

(54) Hayashi, M. (2007) Upper bounds of eavesdropper's performances in finite-length code with the decoy method. Phys. Rev. A 76, 012329; Phys. Rev. A, 79, 019901(E), 2009.

(55) Hayashi, M. and Nakayama, R. (2014) Security analysis of the decoy method with the Bennett-Brassard 1984 protocol for finite key lengths. New J. Phys. 16, 063009.

(56) Hayashi, M. and Tsurumaru, T. (2016) More efficient privacy amplification with less random seeds via dual universal hash function. IEEE Trans. Inf. Theory 62, 2213-2223.

(57) Tsurumaru, T. and Hayashi, M. (2013) Dual universality of hash functions and its applications to quantum cryptography. IEEE Trans. Inf. Theory 59, 4700-4717.

(58) http://jpn.nec.com/press/201509/20150928_03.html.

(59) The project UQCC http://www.uqcc.org/ QKDnetwork/.

(60) Courtland, R. (2016) hina's 2,000-km Quantum Link Is Almost Complete. IEEE Spectrum, 26 Oct, http://spectrum.ieee.org/telecom/security/ chinas-2000km-quantum-link-is-almost-complete.

(61) http:// www.battelle.org/our-work/national-security/ cyber-innovations/quantum-key-distribution.

(62) Bennett, C.H., Brassard, G., Crepeau, C. and Maurer, U.M. (1995) Generalized privacy amplification. IEEE Trans. Inf. Theory 41, 1915-1923.

(63) Hastad, J., Impagliazzo, R., Levin, L.A. and Luby, M. (1999) A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 1364.

(64) Carter, L. and Wegman, M. (1979) Universal classes of hash functions. J. Comput. Syst. Sci. 18, 143-154.

(65) Wegman, M.N. and Carter, J.L. (1981) New hash functions and their use in authentication and set inequality. J. Comput. Syst. Sci. 22, 265-279.

(66) Renner, R. (2005) Security of Quantum Key Distribution," Ph.D. thesis, Dipl. Phys. ETH, Switzerland, arXiv:quantph/0512258.

(67) Tomamichel, M., Lim, C.C.W., Gisin, N. and Renner, R. (2012) Tight finite-key analysis for quantum cryptography. Nat. Commun. 3, 634.

(68) Tomamichel, M., Schaffner, C., Smith, A. and Renner, R. (2011) Leftover hashing against quantum side information. IEEE Trans. Inf. Theory 57, 5524-5535.

(69) Hayashi, M. (2008) Second-order asymptotics in channel capacity. IEICE Tech. Rep. 108, 23-28.

(70) Kontoyiannis, I. and Verdu, S. (2014) Optimal lossless data compression: Non-asymptotics and asymptotics. IEEE Trans. Inf. Theory 60, 777-795.

(71) Hayashi, M. and Watanabe, S. (2013) Non-asymptotic bounds on fixed length source coding for Markov chains. In Proceedings of 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton House. Monticello, Illinois, USA, pp. 875-882.

(72) Hayashi, M. and Watanabe, S. (2014) Non-asymptotic and asymptotic analyses on Markov chains in several problems. In Proceedings of 2014 Information Theory and Applications Workshop, Catamaran Resort, San Diego, USA, pp. 1-10.

(73) Tomamichel, M. and Hayashi, M. (2013) A hierarchy of information quantities for finite block length analysis of quantum tasks. IEEE Trans. Inf. Theory 59, 7693-7710.

(74) Tan, V.Y.F. (2014) Asymptotic estimates in information theory with non-vanishing error probabilities. Found. Trends Commun. Inf. Theory 11, 1-184.

(75) Li, K. (2014) Second-order asymptotics for quantum hypothesis testing. Ann. Stat. 42, 171-189.

(76) Hayashi, M. and Watanabe, S. (2016) Uniform random number generation from Markov chains: Non-asymptotic and asymptotic analyses. IEEE Trans. Inf. Theory 62, 1795-1822.

(77) Wyner, A.D. (1975) The wire-tap channel. Bell Syst. Tech. J. 54, 1355-1387.

(78) Csiszar, I. and Korner, J. (1978) Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24, 339-348.

(79) Maurer, U. (1993) Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39, 733-742.

(80) Ahlswede, R. and Csiszar, I. (1993) Common randomness in information theory and cryptography part I: Secret sharing. IEEE Trans. Inf. Theory 39, 1121-1132.

(81) Bhattad, K. and Narayanan, K.R. (2005) Weakly secure network coding. In Proc. NetCod 2005. Riva del Garda, Italy.

(82) Cai, N. and Chan, T. (2011) Theory of secure network coding. Proc. IEEE 99, 421-437.

(83) Cai, N. and Yeung, R.W. (2002) Secure network coding. In Proc. 2002 IEEE ISIT, Lausanne, Switzerland, p. 323. [Online]. Available: http:// iest2.ie.cuhk.edu.hk/whyeung/publications/ secure. pdf.

(84) Cai, N. and Yeung, R.W. (2007) A security condition for multi-source linear network coding. In Proc. 2007 IEEE ISIT. Nice, France, pp. 561-565.

(85) Cai, N. and Yeung, R.W. (2011) Secure network coding on a wiretap network. IEEE Trans. Inf. Theory 57, 424-435.

(86) Matsumoto, R. and Hayashi, M. (2011) Secure Multiplex Network Coding. In Proceedings of 2011 International Symposium on Network Coding (NetCod). Beijing, China. (DOI: 10.1109/ ISNETCOD.2011.5979076).

(87) Hayashi, M. (2016) Secure wireless communication under spatial and local Gaussian noise assumptions, http://arxiv.org/abs/1604.00635.

(88) Ye, C., Mathur, S., Reznik, A., Shah, Y., Trappe, W. and Mandayam, N.B. (2010) Information-theoretically secret key generation for fading wireless channels. IEEE Trans. Inf. Forensics Security 5, 240-254.

(89) Wallace, J.W. and Sharma, R.K. (2010) Automatic secret keys from reciprocal MIMO wireless channels: Measurement and analysis. IEEE Trans. Inf. Forensics Security 5, 381-392.

(90) Premnath, S.N., Jana, S., Croft, J. and Gowda, P.L. (2013) Secret key extraction from wireless signal strength in real environments. IEEE Trans. Mobile Comput. 12, 917-930.

(91) Chen, C. and Jensen, M.A. (2011) Secret key establishment using temporally and spatially correlated wireless channel coefficients. IEEE Trans. Mobile Comput. 10, 205-215.

(92) Trappe, W. (2015) The challenges facing physical layer security. IEEE Commun. Mag. 53, 16-20.

(93) Zeng, K. (2015) Physical layer key generation in wireless networks: Challenges and opportunities. IEEE Commun. Mag. 53, 33-39.

(94) Wang, H.-M. and Xia, X.-G. (2015) Enhancing wireless secrecy via cooperation: Signal design and optimization. IEEE Commun. Mag. 53, 47-53.

(95) Hayashi, M. (2006) General non-asymptotic and asymptotic formulas in channel resolvability and identification capacity and its application to wiretap channel. IEEE Trans. Inf. Theory 52, 1562-1575.

(96) Hayashi, M. (2011) Exponential decreasing rate of leaked information in universal random privacy amplification. IEEE Trans. Inf. Theory 57, 3989-4001.

(97) Hayashi, M. (2013) Tight exponential analysis of universally composable privacy amplification and its applications. IEEE Trans. Inf. Theory 59, 7728-7746.

(98) Hayashi, M. (2016) Security analysis of e-almost dual [universal.sub.2] hash functions: Smoothing of min entropy vs. smoothing of Renyi entropy of order 2. IEEE Trans. Inf. Theory 62, 3451-3476.

(99) Hayashi, M. and Tan, V. (2015) Equivocations and exponents under various Renyi information measures. In IEEE International Symposium on Information Theory (ISIT2015). Hong Kong, pp. 281-285.

(100) Bloch, M., Hayashi, M. and Thangaraj, A. (2015) Error-control coding for physical-layer secrecy. Proc. IEEE 103, 1725-1746.

(101) Tajima, H. and Hayashi, M. (2014) Optimal efficiency of heat engines with finite-size heat baths, arXiv:1405.6457.

(102) Hayashi, M. and Tajima, H. (2015) Measurement based formulation of quantum heat engine, arXiv:1504.06150.

(103) Kumagai, W. and Hayashi, M. (2013) Entanglement concentration is irreversible. Phys. Rev. Lett. 111, 130407.

(104) Kumagai, W. and Hayashi, M. (2013) A new family of probability distributions and asymptotics of classical and LOCC conversions, arXiv:1306.4166.

(105) Kumagai, W. and Hayashi, M. (2014) Random number conversion and LOCC conversion via restricted storage, arXiv:1401.3781.

(106) Ito, K., Kumagai, W. and Hayashi, M. (2015) Asymptotic compatibility between local operations and classical communication conversion and recovery. Phys. Rev. A 92, 052308.

(107) Hayashi, M. and Owari, M. (2015) Tight asymptotic bounds on local hypothesis testing between a pure bipartite state and the white noise state. In Proceedings of IEEE International Symposium on Information Theory (ISIT2015). Hong Kong, pp. 691-695.

(108) Rivest, R.L., Shamir, A. and Adelman, L. (1977) A method for obtaining digital signature and public-key cryptsystems. MIT Laboratory for Computer Science; Thechnical Memo LCS/TM82.

(109) Hamada, M. (2002) Lower bounds on the quantum capacity and highest error exponent of general memoryless channels. IEEE Trans. Inf. Theory 48, 2547-2557.

(110) Hamada, M. (2003) Notes on the fidelity of symplectic quantum error-correcting codes. Int. J. Quant. Inf. 1, 443-463.

(111) Nambu, Y., Yoshino, K. and Tomita, A. (2006) One-way quantum key distribution system based on planar lightwave circuits. Jpn. J. Appl. Phys. 45, 5344-5348.

(112) Hayashi, M. (2009) Optimal ratio between phase basis and bit basis in quantum key distributions. Phys. Rev. A 79, 020303(R).

(113) Hayashi, M. (2016) Optimal decoy intensity for decoy quantum key distribution. J. Phys. A 49, 165301.

(114) Watanabe, S., Matsumoto, R. and Uyematsu, T. (2008) Tomography increases key rates of quantum-key-distribution protocols. Phys. Rev. A 78, 042316.

(115) Hayashi, M., Ishizaka, S., Kawachi, A., Kimura, G. and Ogawa, T. (2014) Introduction to Quantum Information Science. Graduate Texts in Physics, Springer.

(116) Hayashi, M. (2016) A Group Theoretic Approach to Quantum Information. Springer.

(117) Devetak, I. (2005) The private classical capacity and quantum capacity of a quantum channel. IEEE Trans. Inf. Theory 51, 44-55.

(118) Hayashi, M. (2015) Quantum wiretap channel with non-uniform random number and its exponent and equivocation rate of leaked information. IEEE Trans. Inf. Theory 61, 5595-5622.

(119) Hayashi, M. (2014) Large deviation analysis for quantum security via smoothing of Renyi entropy of order 2. IEEE Trans. Inf. Theory 60, 67026732.

(120) Devetak, I. and Winter, A. (2005) Distillation of secret key and entanglement from quantum states. Proc. R. Soc. Lond. A 461, 207-235.

(121) Arimoto, S. (1975) Information measures and capacity of order a for discrete memoryless channels. In Colloquia Mathematica Societatis Janos Bolya. Kestheley, Hungary, pp. 41-52.

(122) Fung, C.-H.F., Ma, X. and Chau, H.F. (2010) Practical issues in quantum-key-distribution post-processing. Phys. Rev. A 81, 012318.

(123) Watanabe, S. and Hayashi, M. (2014) Strong converse and second-order asymptotics of channel resolvability. In IEEE International Symposium on Information Theory (ISIT2014). Honolulu, HI, USA, pp. 1882.

(124) Yang, W., Schaefer, R.F. and Poor, H.V. (2016) Finite-blocklength bounds for wiretap channels. In IEEE International Symposium on Information Theory (ISIT2016). Barcelona, Spain, pp. 3087-3091.

(125) Hayashi, M., Tyagi, H. and Watanabe, S. (2014) Strong converse for a degraded wiretap channel via active hypothesis testing. Proc. Allerton Conf. Commun., Contr., Comput., Monticello, IL, USA, pp. 148-151.

(126) Tan, V.Y.F. (2012) Achievable second-order coding rates for the wiretap channel. In Proc. IEEE Int. Conf. Comm. Syst. (ICCS). Singapore.

(127) Hayashi, M., Tyagi, H. and Watanabe, S. (2016) Secret key agreement: General capacity and second-order asymptotics. IEEE Trans. Inf. Theory 62, 3796-3810.

(128) Hayashi, M. and Matsumoto, R. (2016) Secure multiplex coding with dependent and non-uniform multiple messages. IEEE Trans. Inf. Theory 62, 2355-2409.

(129) Harada, K. and Yamamoto, H. (2008) Strongly secure linear network coding. IEICE Trans. Fundamentals E91-A, 2720-2728.

(130) Yamamoto, H. (1985) Secret sharing system using (k, L, n) threshold scheme. IECE Trans. Fundamentals, J68-A, 945-952 (in Japanese). (English Translation: Scripta Technica, Inc., Electronics and Comm. in Japan, Part 1, vol. 69, no. 9, pp. 46-54, 1986.).

(131) Silva, D. and Kschischang, F.R. (2009) Universal weakly secure network coding. Proc. ITW 2009. Volos, Greece, pp. 281-285.

(132) Silva, D. and Kschischang, F.R. (2011) Universal secure network coding via rank-metric codes. IEEE Trans. Inf. Theory 57, 1124-1135.

(133) Kurihara, J., Matsumoto, R. and Uyematsu, T. (2015) Relative generalized rank weight of linear codes and its applications to network coding. IEEE Trans. Inf. Theory 61, 3912-3936.

(134) Kurosawa, K., Ohta, H. and Des Kakuta, K. (2017) How to make a linear network code (strongly) secure. Des. Codes Cryptogr., 82, 559-582.

(135) Blakley, G.R. (1979) Safeguarding cryptographic keys. In Proceedings of the National Computer Conference 48. pp. 313-317.

(136) Shamir, A. (1979) How to share a secret. Commun. ACM 22, 612-613.

(137) Ahlswede, R. and Dueck, G. (1989) Identification via channels. IEEE Trans. Inf. Theory 35, 15-29.

(138) Bloch, M.R. and Laneman, J.N. (2013) Strong secrecy from channel resolvability. IEEE Trans. Inf. Theory 59, 8077-8098.

(139) Hou, J. and Kramer, G. (2014) Effective secrecy: Reliability, confusion and stealth. In IEEE International Symposium on Information Theory. pp. 601-605.

(140) Bloch, M., Barros, J., Rodrigues, M.R. and McLaughlin, S.W. (2008) Wireless information-theoretic security. IEEE Trans. Inf. Theory 54, 2515-2534.

(141) Liang, Y., Poor, H.V. and Shamai, S. (2008) Secure communication over fading channels. IEEE Trans. Inf. Theory 54, 2470-2492.

(142) Han, T.S., Endo, H. and Sasaki, M. (2014) Reliability and secrecy functions of the wiretap channel under cost constraint. IEEE Trans. Inf. Theory 60, 6819-6843.

(Received Oct. 8, 2016; accepted Dec. 26, 2016)

Profile

Masahito Hayashi was born in Japan in 1971. He received the B.S. degree from the Faculty of Sciences in Kyoto University, Japan, in 1994 and M.S. and Ph.D. degrees in Mathematics from Kyoto University, Japan, in 1996 and 1999, respectively. He worked in Kyoto University as a Research Fellow of the Japan Society for the Promotion of Science (JSPS) from 1998 to 2000, in the Laboratory for Mathematical Neuroscience, Brain Science Institute, RIKEN from 2000 to 2003, and in the ERATO Quantum Computation and Information Project, Japan Science and Technology Agency (JST) as Research Head from 2000 to 2006. He also worked in the Superrobust Computation Project Information Science and Technology Strategic Core (21st Century COE by MEXT) Graduate School of Information Science and Technology, The University of Tokyo as Adjunct Associate Professor from 2004 to 2007. He worked in the Graduate School of Information Sciences, Tohoku University as Associate Professor from 2007 to 2012. In 2012, he joined the Graduate School of Mathematics, Nagoya University as Professor. He also worked as Visiting Research Associate Professor from 2009 to 2012 and as Visiting Research Professor from 2012 to the present in the Centre for Quantum Technologies, National University of Singapore. In 2011, he received the Information Theory Society Paper Award (2011) for his paper "Information-Spectrum Approach to Second-Order Coding Rate in Channel Coding". In 2016, he received the Japan Academy Medal from the Japan Academy and the JSPS Prize from the Japan Society for the Promotion of Science. In 2017, he was elevated to the status of an IEEE fellow.

In 2006, he published the book "Quantum Information: An Introduction" with Springer; the revised version was published as "Quantum Information Theory: Mathematical Foundation" in the Graduate Texts in Physics series by Springer in 2016. In 2016, he published other two books: "Group Representation for Quantum Theory" and "A Group Theoretic Approach to Quantum Information" with Springer. He is on the Editorial Board of the International Journal of Quantum Information and the International Journal On Advances in Security. His research interests include classical and quantum information theory and classical and quantum statistical inference.

[1] Unfortunately, due to page limitations, the present paper cannot give a detailed derivation. However, a detailed discussion is available in Section 4.6 of the book. (35)

[2] In the quantum case, they found a slightly weaker inequality. However, we can trivially derive [16] from their derivation in the commutative case.

[3] In the study of cryptography, We call the authorized sender, the authorized receiver, and the eavesdropper Alice, Bob, and Eve, respectively.

[4] To explain this point, we need to discuss a [delta]-almost [universal.sub.2] hash function for [F.sup.n.sub.2]/[C.sup.[perpendicular to]], which requires more work. To avoid this difficulty, we give only a simplified discussion here.

[5] Indeed, two kinds of conditional Renyi entropy are known. This type is often called the Gallager (2) or Arimoto type. (121)

[6] For its detail derivation, see [87, Section V-D].

By Masahito HAYASHI * [1], * [2] ([dagger])

(Communicated by Makoto NAGAO, M.J.A.)

* [1] Graduate School of Mathematics, Nagoya University, Chikusa-ku, Nagoya, Japan.

* [2] Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore.

([dagger]) Correspondence should be addressed: M. Hayashi, Graduate School of Mathematics, Nagoya University, Furocho, Chikusa-ku, Nagoya 464-8602, Japan (e-mail: masahito@math. nagoya-u.ac.jp).

doi: 10.2183/pjab.93.007 Caption: Fig. 1. Channel coding with three-bit code.

Caption: Fig. 2. Classical channel coding for optical communication. Dashed thick arrows indicate quantum state transmission. Normal thin arrows indicate classical information.

Caption: Fig. 3. Quantum channel coding for optical communication. Dashed thick arrows indicate quantum state transmission. Normal thin arrows indicate classical information.

Caption: Fig. 4. Classical-quantum channel coding for optical communication. Dashed thick arrows indicate quantum state transmission. Normal thin arrows indicate classical information.

Caption: Fig. 5. Structure of information spectrum: The information spectrum method discusses the problem in steps. One is the step to connect the information source and the behavior of the logarithmic likelihood. The other is the step to connect the behavior of the logarithmic likelihood and the optimal performances in the respective tasks.

Caption: Fig. 6. Asymptotic trade-off relation between errors of data compression and uniform random number generation: When we focus on the second-order coding rate, the minimum error of data compression is the probability of the exclusive event of the minimum error of uniform random number generation.

Caption: Fig. 7. Classes of (dual) [universal.sub.2] hash functions and security: A hash function is used to realize privacy amplification. This picture shows the relations between classes of hash functions and security. In cryptography theory, strong security is considered a requirement for a hash function. The class of [universal.sub.2] hash functions was proposed in. (64,65) Using the leftover hash lemma, (62,63) Renner (66) proposed to use this class for quantum cryptography. Tomamichel et al, (68) proposed to use the class of [delta]-almost [universal.sub.2] hash functions when [delta] is close to 1. Tsurumaru et al. (57) proposed the use of [delta]-almost dual [universal.sub.2] hash functions when [delta] is constant or increases polynomially. As an example of a [delta]-almost dual [universal.sub.2] hash function, the author with his collaborators (56) constructed a secure Hash Function with a less random seed and less calculation. Although the security analysis in (67) is based on [universal.sub.2] hash functions, that in (53-55) is based on [delta]-almost dual [universal.sub.2] hash functions.

Caption: Fig. 8. QKD system developed by NEC. Copyright (2015) by NEC: This device was used for a long-term evaluation demonstration in 2015 by the "Cyber Security Factory" (core facility for counter-cyber-attack activities in NEC). (58)

Caption: Fig. 9. Multiple photons in a weak coherent pulse: A weak coherent pulse contains multiple photons with a certain probability, which depends on the intensity of the pulse.

Caption: Fig. 11. Relation between the asymptotic transmission rate and the actual transmission rate dependent on the block-length: Usually, the actual transmission rate is smaller than the asymptotic key generation rate. As the block-length increases, the actual transmission rate becomes closer to the asymptotic key generation rate.

Caption: Fig. 12. Wire-tap channel model. Eve is assumed to have a weaker connection to Alice than Bob does.

Caption: Fig. 13. Model of Eve's attack for secure wireless communication. Eve can inject artificial noise into Bob's observation. It is also assumed that Eve has noise in her detector like Bob. It is natural to assume that these detector noises are independent of other random variables.

Fig. 10. Key generation rate with weak coherent pulses: We employ two intensities: signal intensity and decoy intensity. Using the difference between detection rates of the pulses with two different intensities, we can estimate the fraction of multiple photons in the detected pulses. Here, we set the signal intensity to be 1. This graph shows the key generation rate dependent on the decoy intensity. This graph is based on the calculation formula given in. (55) Color Block-length for privacy amplification Blue Infinity Red [10.sup.10] Green [10.sup.9] Yellow [10.sup.8] Black [10.sup.7] Purple [10.sup.6]

Printer friendly Cite/link Email Feedback | |

Author: | Hayashi, Masahito |
---|---|

Publication: | Japan Academy Proceedings Series B: Physical and Biological Sciences |

Article Type: | Report |

Date: | Mar 1, 2017 |

Words: | 19692 |

Previous Article: | Getting to the heart of the matter in cancer: novel approaches to targeting cancer stem cells. |

Next Article: | Awarding ceremony of the Japan Academy Medal. |

Topics: |