Secret Communication System And Method Based On Network Coding

Abstract

Information is efficiently communicated while high secrecy is maintained in a network in which eavesdropping, error, and falsification occur. A control device of a communication network including a plurality of nodes and links each connecting two of the nodes includes a first instruction unit 110 configured to instruct a source node among the plurality of nodes whether to perform MRD encoding when the source node performs transmission, a random number transmission unit 120 configured to transmit a random number in accordance with a maximum number of links susceptible to eavesdropping among the links to the source node in a case in which the source node is instructed to perform MRD encoding by the first instruction unit, and a second instruction unit 130 configured to instruct each of the plurality of nodes whether to perform OTP encryption when the node performs transmission to another node.

Claims

1. A control device of a communication network including a plurality of nodes and links each connecting two of the nodes, the control device comprising: a first instruction unit configured to instruct a source node among the plurality of nodes whether to perform MRD encoding when the source node performs transmission; a random number transmission unit configured to transmit a random number in accordance with a maximum number of links susceptible to eavesdropping among the links to the source node in a case in which the source node is instructed to perform MRD encoding by the first instruction unit; and a second instruction unit configured to instruct each of the plurality of nodes whether to perform OTP encryption when the node performs transmission to another node.

2. The control device according to claim 1, wherein the communication network is a key management network in a quantum key distribution network.

3. The control device according to claim 1, wherein the communication network is a service layer of a user network in a quantum cryptographic communication network.

4. A communication network system comprising: the control device according to claim 1; the plurality of nodes; and the links each connecting two of the nodes.

5. A source node in a communication network including a plurality of nodes and links each connecting two of the nodes, the source node comprising: an MRD encoding unit configured to generate an MRD-encoded message by performing MRD encoding of a message by using a random number in accordance with a maximum number of links susceptible to eavesdropping among the links; an OTP encrypting unit configured to generate an OTP-encrypted message by performing OTP encryption of the MRD-encoded message by using a key for OTP encryption; and a transmission unit configured to transmit the OTP-encrypted message to another node connected to the source node through a corresponding one of the links.

6. A communication network comprising: the source node according to claim 5; a terminal node that is a final transmission destination of the message; and a relay node that performs relay between the source node and the terminal node.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0018] FIG. 1 is an explanatory diagram of network coding and secure network coding.

[0019] FIG. 2 is an explanatory diagram illustrating a quantum cryptographic communication network.

[0020] FIG. 3 is an explanatory diagram illustrating a basic process of key relay.

[0021] FIG. 4 is an explanatory diagram illustrating a quantum cryptographic communication network to which a new highly secure network coding as a combination of an MRD code and OTP encryption is applied.

[0022] FIG. 5 is an explanatory diagram illustrating the status of cryptographic key accumulation in a multi-node network.

[0023] FIG. 6 is an explanatory diagram illustrating a communication path model of secure network coding using an MRD code and a sub MRD code.

[0024] FIG. 7 is an explanatory diagram illustrating an exemplary network configuration of a highly distributed key relay system.

[0025] FIG. 8 is a block diagram of a control device of a communication network.

[0026] FIG. 9 is an explanatory diagram illustrating an exemplary computer hardware configuration of a node.

MODE FOR CARRYING OUT THE INVENTION

[0027] The present invention will be described below based on illustrated embodiments. However, the present invention is not limited by the embodiments described below.

[0028] The inventor of the present invention first diligently discussed network coding and secure network coding, and a quantum cryptographic communication network as described below.

1. Network Coding and Secure Network Coding

[0029] It has been known for a long time that the amount of information that can be transferred in a constant time between two optional nodes in a network is determined by the minimum cut capacity of a directed graph model of the network (C. E. Shannon, A Note on the Maximum Flow Through a Network, 1956). However, the maximum capacity in multicast communication cannot be achieved by an accumulation and forwarding method performed at a conventional relay node, in other words, a method of receiving pieces of information, determining a path to a destination for each piece of the information in order of reception, and forwarding (routing) the information to the next relay node.

[0030] In 2000, R. Ahlswede, et al., introduced the concept of network coding and showed that the maximum capacity of a network can be achieved by combining and converting (encoding) a plurality of pieces of information collected at a relay node into other information and then forwarding the information. In 2003, S. Y. R. Li, et al., showed that the maximum capacity of a network can be achieved.

[0031] Authentication and key exchange by public key cryptography and data communication encryption by symmetric key cryptography are currently commonly used as methods of ensuring security of communication in a network. In these encryption technologies, a mathematical problem that is difficult to solve is used to create a situation in which a third party who does not know a cryptographic key needs an enormous amount of calculation to decrypt the original information from a cipher text, thereby, in effect, preventing eavesdropping and falsification. However, since the risk of decryption increases with the progress of computing technologies, it is periodically necessary to elongate the length of a cryptographic key and update a cryptographic scheme.

[0032] In addition, methods of guaranteeing security that cannot be decrypted by any computer (information-theoretic security) are known. With these cryptographic schemes based on information-theoretic security, it is possible in principle to guarantee security for an ultralong duration without update of cryptographic specifications.

[0033] One example of the cryptographic schemes based on information-theoretic security is a method called secure network coding in which randomization with a true random number is included in network coding. In this method, information is transmitted from a node (transmission end; source node) in a network to another node (reception end; terminal node) through a plurality of relay nodes. The source node and the relay node each include a true random number source and an encoding device, generate a necessary true random number, and perform appropriate encoding. Typically, a plurality of output links extend from the source node, and information is distributed among these links and transmitted. In a case of multicast communication, a plurality of terminal nodes exist. Each terminal node is connected to a plurality of input links and performs decryption upon accumulation of necessary information from relay nodes. For example, a method based on a maximum rank distance code (MRD code) or the like is known as a specific code configuration method of secure network coding.

[0034] FIG. 1 illustrates an overview of network coding and secure network coding. A network NW1 is expressed with a plurality of nodes and a set of links (also referred to as edges) each connecting two of the nodes. In this example, each node is expressed by a unique index, and each link is expressed by a pair of two node indexes at end points. For example, a link connecting a source node s and a relay node s.sub.1 is referred to as a link (s, s.sub.1), and a message flowing through the link (s, s.sub.1) is referred to as x (s, s.sub.1).

[0035] The source node s encodes m input messages u.sub.0, u.sub.1, . . . , u.sub.m1 into n output messages x(s, s.sub.1), x(s, s.sub.2), . . . , x(s, s.sub.n) and transmits the output messages to the first relay nodes s.sub.1, s.sub.2, . . . , s.sub.n, respectively. Various usages are assumed such as a case in which the source node transmits a message to one terminal node and a case in which the source node multicasts messages to a plurality of terminal nodes.

[0036] In the network NW1, messages are subjected to encoding processing through a plurality of additional relay nodes in accordance with usage and are transmitted to a terminal node t. Typically, a relay node v converts a plurality of messages x(v.sub.1, v), x(v.sub.2, v), . . . , x(v.sub.1, v) from input links into messages x(v, v.sub.1), x(v, v.sub.2), . . . , x(v, v.sub.O) through linear network coding processing described next.

[00001]$\begin{array}{cc}\left[\mathrm{Formula}1\right]& \\ \left[\begin{array}{c}x\left(v,v_1^{}\right)\\ x\left(v,v_2^{}\right)\\ .Math.\\ x\left(v,v_O^{}\right)\end{array}\right]=R^{\left(v\right)}\left[\begin{array}{c}x\left(v_1,v\right)\\ x\left(v_2,v\right)\\ .Math.\\ x\left(v_I,v\right)\end{array}\right],& \left(1\right)\end{array}$$\begin{array}{cc}{R}^{\left(v\right)}=\left[\begin{array}{cccc}{r}_{v_1^{}{v}_1}^{\left(v\right)}& r_{v_1^{}{v}_2}^{\left(v\right)}& .Math.& r_{v_1^{}{v}_I}^{\left(v\right)}\\ r_{v_2^{}{v}_1}^{\left(v\right)}& r_{v_2^{}{v}_2}^{\left(v\right)}& .Math.& r_{v_2^{}{v}_I}^{\left(v\right)}\\ .Math.& .Math.& & .Math.\\ r_{v_O^{}{v}_1}^{\left(v\right)}& r_{v_O^{}{v}_2}^{\left(v\right)}& .Math.& r_{v_O^{}{v}_I}^{\left(v\right)}\end{array}\right],& \left(2\right)\end{array}$

[0037] In the expressions, the matrix R.sup.(v) is a linear network code matrix. Expressions (1) and (2) can be expressed as follows.

[00002]$\begin{array}{cc}\left[\mathrm{Formula}2\right]& \\ x\left(v,v_1^{}\right)=r_{v_1^{}{v}_1}^{\left(v\right)}x\left(v_1,v\right)+r_{v_1^{}{v}_2}^{\left(v\right)}x\left(v_2,v\right)+.Math.+r_{v_1^{}{v}_I}^{\left(v\right)}x\left(v_I,v\right)& \end{array}$$x\left(v,v_2^{}\right)=r_{v_2^{}{v}_1}^{\left(v\right)}x\left(v_1,v\right)+r_{v_2^{}{v}_2}^{\left(v\right)}x\left(v_2,v\right)+.Math.+r_{v_2^{}{v}_I}^{\left(v\right)}x\left(v_I,v\right)$$.Math.$$x\left(v,v_O^{}\right)=r_{v_O^{}{v}_1}^{\left(v\right)}x\left(v_1,v\right)+r_{v_O^{}{v}_2}^{\left(v\right)}x\left(v_2,v\right)+.Math.+r_{v_O^{}{v}_I}^{\left(v\right)}x\left(v_I,v\right)$

[0038] In this manner, the messages x(v, v.sub.1), x(v, v.sub.2), . . . , x(v, v.sub.O) are each expressed as a linear combination of the elements of the linear network code matrix R.sup.(v) and the plurality of messages x(v.sub.1, v), x(v.sub.2, v), . . . , x(v.sub.1, v) from input links.

[0039] The relay node v transmits the messages x(v, v.sub.1), x(v, v.sub.2), . . . , x(v, v.sub.O) obtained through the linear network coding processing toward the next nodes v.sub.1, v.sub.2, . . . , v.sub.O, respectively.

[0040] Note that the same processing at the relay node v is performed also at the relay nodes s.sub.1, s.sub.2, . . . , s.sub.n, the relay nodes v.sub.1, v.sub.2, . . . , v.sub.I, the relay nodes v.sub.1, v.sub.2, . . . , v.sub.o, and the relay nodes t.sub.1, t.sub.2, . . . , t.sub.l.

[0041] Lastly, the terminal node t receives l messages x(t.sub.1, t), x(t.sub.2, t), . . . , x(t.sub.l, t) and decrypts the m messages u.sub.0, u.sub.1, . . . , u.sub.m1 from the source node s.

2. Quantum Cryptographic Communication Network

[0042] A method (quantum cryptography) of encrypting data communication by a one time pad (OTP) scheme by using a cryptographic key shared by quantum key distribution is known as another method of guaranteeing information-theoretic security. Quantum key distribution (QKD) is a method of sharing a common true random number string (denoted by K) with information-theoretic security as a cryptographic key between two separate places connected through an optical channel. Encryption is performed through the logical sum (exclusive OR operation) between a transmission message U and the cryptographic key K prepared in the same size as the message U:

[00003]$\begin{array}{cc}\left[\mathrm{Formula}3\right]& \\ X=UK& \end{array}$

cryptographic key The cipher text X is transferred to a receiver through a communication channel (line different from the optical line for quantum key distribution). The receiver decrypts the message U through the logical sum of the received cipher text X and the cryptographic key K in hand:

[00004]$\begin{array}{cc}\left[\mathrm{Formula}4\right]& \\ U=XK& \end{array}$

Information-theoretically secure cryptographic communication can be achieved by not reusing, but instead discarding the cryptographic key K after used once (one time pad scheme).

[0043] Key generation speed of a pair of QKD link systems connecting two places decreases as transmission distance increases, and the key generation speed for a standard installed optical fiber is several hundreds of kbps at 50 km, and several kbps at 100 km. Thus, a quantum key distribution network (QKDN) as a large scale network is constructed by preparing a plurality of trusted nodes at the interval of 50 to 60 km and concatenating QKD devices (QKD modules) in the respective trusted nodes.

[0044] In each trusted node, a key manager (KM) is prepared separately from the QKD module, and a cryptographic key generated by the QKD module is transferred to and stored in the KM. The KMs are connected to each other through a classical channel (KM link) and perform management and operation of a cryptographic key by, for example, performing capsule relay of the cryptographic key when needed.

[0045] A cryptographic key shared in this manner can be used in, for example, key supply to various cryptographic applications, such as applications of perfectly secret communication by one time pad (OTP), symmetric key cryptography, and secret sharing and storage, existing in existing communication networks and encryption infrastructure (user network in FIG. 2, to be described later). Functional elements, that is, a QKDN controller and a QKDN manager are introduced to perform path control of capsule relay of the cryptographic key, management of the entire QKDN, and the like. A network including a QKDN and a user network in which cryptographic applications are executed is referred to as a quantum cryptographic communication network.

[0046] FIG. 2 illustrates a conceptual structure of a quantum cryptographic communication network NW2. The quantum cryptographic communication network NW2 includes a quantum key distribution network QKDN2 and a user network UN2. The quantum key distribution network QKDN2 includes a plurality of trusted nodes TN and four functional layers L1 to L4.

[0047] The quantum layer L1 is a set of QKD links continuously provided through QKD modules QM in respective trusted node. Each QKD link is a one-to-one link. One QKD module in a trusted node and one QKD module in another trusted node are connected to each other through a QKD link. Each QKD link independently generates a cryptographic key. The generated cryptographic key is transferred to the key manager KM in the trusted node and managed and operated.

[0048] The key management layer L2 includes the key managers KM in the respective trusted nodes, and KM links connecting key managers KM. Each key manager KM accumulates cryptographic keys generated in the quantum layer L1 and shares the cryptographic keys among necessary ends by key capsule relay with OTP encryption. Each key manager KM performs general key management such as supply of a cryptographic key to a cryptographic application in the user network UN2.

[0049] FIG. 3 illustrates a basic process of key capsule relay with OTP encryption. A key manager A is connected to a key manager C, and the key manager C is connected to a key manager B. The key managers A and C have a cryptographic key K.sub.1 (a pair of secret random number strings shared between the nodes by QKD; so called a symmetric key) generated by the corresponding QKD modules. The key managers C and B have a cryptographic key K.sub.2 generated by the corresponding QKD modules. The key manager A transfers the cryptographic key K.sub.1 to the key manager C. The key manager C transfers the exclusive OR of the cryptographic key K.sub.1 received from the key manager A and the cryptographic key K.sub.2:

[00005]$\begin{array}{cc}\left[\mathrm{Formula}5\right]& \\ K_1{K}_2& \end{array}$

to the key manager B. The exclusive OR of the cryptographic key K.sub.1 and the cryptographic key K.sub.2 corresponds to encapsulation of the cryptographic key K.sub.1 with the cryptographic key K.sub.2. The cryptographic key K.sub.2 used for the encapsulation is used by what is called OTP so that, once used, the key is discarded and is not used again.

[0050] The QKDN control layer L3 includes one or more QKDN controllers CT that perform service control of the entire QKDN.

[0051] The QKDN management layer L4 includes a QKDN manager MG1. The QKDN manager MG has a function to collect performance information from each of the layers L1 to L3, monitor whether services are appropriately operational, and instruct the QKDN control layer L3 to perform control as necessary.

[0052] The user network UN2 includes a service layer L5 as a functional layer in which a plurality of user terminals UD exist, and a user network management layer L6. The plurality of user terminals UD in the service layer L5 perform cryptographic communication by using keys supplied from corresponding key managers KM and cryptographic applications. A network manager MG2 in the user network management layer L6 performs communication with the QKDN manager MG1 and management of the user terminals UD.

3. Embodiment of the Present Invention

3.1. New Highly Secure Network Coding as Combination of MRD Code and OTP Encryption

[0053] An embodiment of the present invention based on the above-described discussion relates to new highly secure network coding for combining an MRD code and OTP encryption to compensate for disadvantages of the conventional secure network coding and the conventional quantum cryptographic communication network and synergize their advantages. According to the present embodiment, it is possible to communicate information with high efficiency while maintaining high secrecy in a network in which eavesdropping, error, and falsification occur, without losing reliability.

[0054] FIG. 4 illustrates a quantum cryptographic communication network NW3 in which communication is performed by using highly secure network coding according to the present embodiment. The quantum cryptographic communication network NW3 includes a quantum key distribution network QKDN3 and a user network UN3.

[0055] Similarly to the quantum key distribution network QKDN2, the quantum key distribution network QKDN3 includes a plurality of trusted nodes TN, and also includes a quantum layer, a key management layer, a QKDN control layer, and a QKDN management layer.

[0056] Similarly to the user network UN2, the user network UN3 includes a service layer as a functional layer in which a plurality of user terminals UD exists, and a user network management layer. Note that illustration of the user network management layer is omitted in FIG. 4.

[0057] A new highly secure network coding as a combination of the MRD code and OTP encryption is introduced in the service layer of the user network UN3 and the key management layer of the quantum key distribution network QKDN3. Secrecy and reliability are improved in a balanced manner in networks while the combination of the MRD code and the OTP encryption and specifications of the MRD code are appropriately controlled in accordance with the status of cryptographic key accumulation at each node in the quantum key distribution network QKDN3 and the status of cryptographic key request in the service layer of the user network UN3. The OTP encryption is performed by using a cryptographic key generated by QKD.

[0058] A multicast communication as illustrated in FIG. 5 is considered as an exemplary multi-node network pattern in which highly secure network coding is applied. In a multi-node network pattern NW4, message packets u.sub.1 and u.sub.2 are secretly multicast from the two source nodes s.sub.11 and s.sub.12, respectively, to the four terminal nodes t.sub.11, t.sub.12, t.sub.13, and t.sub.14 through some of the relay nodes v.sub.11 to v.sub.14, v.sub.21 to v.sub.25, v.sub.31 to v.sub.34, v.sub.41 to v.sub.45, and v.sub.51 to v.sub.55. The multi-node network pattern in the diagram is applied to the service layer of the user network UN3 as well as the key management layer of the quantum key distribution network QKDN3. In the latter case, the message packets u.sub.1 and u.sub.2 correspond to cryptographic keys (group keys). Solid lines and dotted lines in FIG. 5 each represent a link connecting two nodes. Each solid line represents a link with which a pair of cryptographic keys necessary for OTP encryption can be prepared, and each dotted line represents a link for which a sufficient number of cryptographic keys is not available. Note that each link is expressed as, for example, (v.sub.11, v.sub.12) by using a pair of nodes at respective ends.

[0059] In such a situation, secret multicast is impossible until sufficient cryptographic keys are accumulated at each link of a dotted line, and a QKD link system with relatively low key generation speed largely limits communication function of the entire network. In such a case, the following effects are obtained by performing secure network coding based on the MRD code at each source node. [0060] (1) Confidential communication with information-theoretic security maintained in the entire network can be performed even when OTP encryption cannot be executed at some links. [0061] (2) Error propagation resistance can be improved by using rank error correction capability of the MRD code. [0062] (3) Threshold value assumption to be satisfied by the MRD code is likely to be guaranteed by performing OTP encryption, not at all links, but at a large number of links. [0063] (4) Confidentiality and reliability, and thus availability, can be improved in a balanced manner while cryptographic keys are efficiently used in the entire network.

[0064] In integrated operation of secure network coding using the MRD code and a quantum cryptographic communication network using OTP encryption, further optimum control of secrecy and reliability is possible when QKDN controllers, key managers, and cryptographic applications closely cooperate and appropriately adjust specifications of secure network coding based on the MRD code in accordance with the consumption amount of cryptographic keys at cryptographic applications and KMs and the accumulation amount of cryptographic keys at KMs.

3.1.1 Basic Requirements and Definitions

[0065] In the present embodiment, new highly secure network coding is achieved by integrating the following functions used in secure network coding. [0066] (i) Capability of deceiving eavesdroppers by introducing appropriate randomness to nodes [0067] (ii) Function to correct any unauthorized falsification and error of a message [0068] (iii) The following functions of QKDN [0069] Function to generate a cryptographic key with information-theoretic security [0070] Function to relay and distribute the above-described cryptographic key [0071] Function to accumulate, manage, and operate cryptographic keys [0072] Function to control QKDN in accordance with the above-described situation

[0073] Terms are defined as follows. [0074] 1) A node at the starting point of relay is referred to as a source node, and a node at the end point is referred to as a terminal node. The source node and the terminal node are typically connected to each other, not by a single path, but by a distributed network through a plurality of nodes and links. [0075] 2) Information to be delivered from the source node to the terminal node is referred to as a message in the following description. In a key management layer, a cryptographic key is regarded as a message. [0076] 3) The source node performs secure network coding for transmitting the message in a distributed manner to a plurality of links by adding random number information for deceiving eavesdroppers and parity check information for error correction and falsification detection to a message. The message, the random number information, and the examination information are sequences constituted by symbols in a finite field GF(q) (q is the number of elements and the power of a prime number of two or more) of multiple elements. [0077] 4) A sequence as a collection of message, random number information, and parity check information transmitted in each link is referred to as a packet in the following description. The size (sequence length) of the packet is referred to as N.

[0078] Network topology having resistance against eavesdropping and falsification desirably has as many relay nodes n per hop as possible. For example, n is four in FIG. 5.

3.1.2. Basic Parameters and Code Configuration Overview

[0079] FIG. 6 illustrates a communication path model of secure network coding using an MRD code and a sub MRD code.

[0080] Note that OTP encryption (step ST2 in FIG. 6) is not performed at all links. As mentioned above, OTP encryption is not performed at a link (for example, a dotted line in FIG. 5) with no cryptographic key (pair of symmetric secret random number strings) necessary for OTP encryption.

[0081] Details will be described below.

[0082] As described above, an output from a node v is expressed as a linear combination of packets in input links to the node with the elements of the linear network code matrix as coefficients.

[00006]$\begin{array}{cc}\left[\mathrm{Formula}6\right]& \\ x\left(v,v_1^{}\right)=r_{v_1^{}{v}_1}^{\left(v\right)}x\left(v_1,v\right)+r_{v_1^{}{v}_2}^{\left(v\right)}x\left(v_2,v\right)+.Math.+r_{v_1^{}{v}_I}^{\left(v\right)}x\left(v_I,v\right)& \end{array}$$x\left(v,v_2^{}\right)=r_{v_2^{}{v}_1}^{\left(v\right)}x\left(v_1,v\right)+r_{v_2^{}{v}_2}^{\left(v\right)}x\left(v_2,v\right)+.Math.+r_{v_2^{}{v}_I}^{\left(v\right)}x\left(v_I,v\right)$$.Math.$$x\left(v,v_O^{}\right)=r_{v_O^{}{v}_1}^{\left(v\right)}x\left(v_1,v\right)+r_{v_O^{}{v}_2}^{\left(v\right)}x\left(v_2,v\right)+.Math.+r_{v_O^{}{v}_I}^{\left(v\right)}x\left(v_I,v\right)$

[0083] In a case in which the link (v, v.sub.1) connecting the nodes v and v.sub.1 is a link that performs OTP encryption, the node v transmits, to the node v.sub.1, a message obtained by encrypting a message x(v, v.sub.1) by using a cryptographic key K(v, v.sub.1) shared between the nodes v and v.sub.1 in advance. The message transmitted to the node v.sub.1 is as follows.

[00007]$\begin{array}{cc}\left[\mathrm{Formula}7\right]& \\ x\left(v,v_1^{}\right)K\left(v,v_1^{}\right)& \end{array}$

[0084] After having received the message, the node v.sub.1 decrypts the message by using the cryptographic key K(v, v.sub.1). Thereafter, the node v.sub.1 discards the cryptographic key K(v, v.sub.1).

[0085] Similarly, OTP encryption is performed by using a cryptographic key K(v, v.sub.j) for a link connecting the node v and a node v.sub.j sharing a cryptographic key of a sufficient length with the node v.

[0086] In a case in which a cryptographic key of a sufficient length is not shared between the nodes v and v.sub.k, a message x(v, v.sub.k) is directly transmitted to the node v.sub.k without encryption through a link (v, v.sub.k). Alternatively, symmetric key cryptography prepared as a backup mode in advance may be activated for the above-described link (v, v.sub.k) for which a cryptographic key of a sufficient length cannot be prepared, a cryptographic key K(v, v.sub.k) may be input as a seed key to a transmitter of symmetric key cryptography at the node v, and encryption may be performed by symmetric key cryptography with key expansion.

[0087] Basic parameters N, n, , , , m, and l and variables related to models of attack and perilous situations and secure network coding are described below. [0088] 1) The number of relay nodes per hop to be traversed in distributed relay is n. [0089] 2) Eavesdroppers can eavesdrop packets (step ST3 in FIG. 6) and can inject error packets:

[00008]$\begin{array}{cc}\left[\mathrm{Formula}8\right]& \\ z=\left[\begin{array}{c}{z}_0\\ z_1\\ .Math.\\ z_{-1}\end{array}\right]=\left[\begin{array}{cccc}{z}_0^{\left(0\right)}& z_1^{\left(0\right)}& .Math.& z_{N-1}^{\left(0\right)}\\ z_0^{\left(1\right)}& z_1^{\left(1\right)}& .Math.& z_{N-1}^{\left(1\right)}\\ .Math.& .Math.& & .Math.\\ z_0^{\left(-1\right)}& u_1^{\left(-1\right)}& .Math.& z_{N-1}^{\left(-1\right)}\end{array}\right].& \left(3\right)\end{array}$

from an optional place in a network (step ST4 in FIG. 6).

[0090] In addition, assumptions are set as follows. [0091] i) Nn [0092] ii) 0<mn2 [0093] 3) A loss of packets can occur in a network. However, in the following description, a case of no loss is considered with =0. [0094] 4) Messages transferred from a source node are m cryptographic keys of a length N and expressed as follows.

[00009]$\begin{array}{cc}\left[\mathrm{Formula}9\right]& \\ u=\left[\begin{array}{c}{u}_0\\ u_1\\ .Math.\\ u_{m-1}\end{array}\right]=\left[\begin{array}{cccc}{u}_0^{\left(0\right)}& u_1^{\left(0\right)}& .Math.& u_{N-1}^{\left(0\right)}\\ u_0^{\left(1\right)}& u_1^{\left(1\right)}& .Math.& u_{N-1}^{\left(1\right)}\\ .Math.& .Math.& & .Math.\\ u_0^{\left(m-1\right)}& u_1^{\left(m-1\right)}& .Math.& u_{N-1}^{\left(m-1\right)}\end{array}\right]& \left(4\right)\end{array}$

[0095] In the following description, the messages are referred to as message packets. Each message packet u.sub.i is an element of a Galois extension field:

[00010]$\begin{array}{cc}{}_{q^N}& \left[\mathrm{Formula}10\right]\end{array}$

In other words,

[00011]$\begin{array}{cc}{u}_i{}_{q^N}& \left[\mathrm{Formula}11\right]\end{array}$

[0096] The Galois extension field:

[00012]$\begin{array}{cc}{}_{q^N}& \left[\mathrm{Formula}12\right]\end{array}$

can be regarded as an N-dimensional vector space in a field:

[00013]$\begin{array}{cc}{}_q& \left[\mathrm{Formula}13\right]\end{array}$

[0097] A set of all m-dimensional vectors in the Galois extension field:

[00014]$\begin{array}{cc}{}_{q^N}& \left[\mathrm{Formula}14\right]\end{array}$

is expressed as:

[00015]$\begin{array}{cc}{}_{q^N}^m& \left[\mathrm{Formula}15\right]\end{array}$

[0098] The message u transferred from the source node is an element of an m-dimensional vector space in the Galois extension field:

[00016]$\begin{array}{cc}{}_{q^N}& \left[\mathrm{Formula}16\right]\end{array}$

In other words,

[00017]$\begin{array}{cc}u{}_{q^N}^m& \left[\mathrm{Formula}17\right]\end{array}$ [0099] 5) At the source node, random-number packets (the length of each packet is N) for deceiving eavesdroppers are generated, and appropriate secure network coding with error correction and concealing functions is performed together with given message packets of m:

[00018]$\begin{array}{cc}\left[\mathrm{Formula}18\right]& \\ u{}_{q^N}^m& \end{array}$

To guarantee information-theoretic security, a random number needs to be a physical random number. Secure network coding is performed with a maximum rank distance code (MRD code). Thus, over:

[00019]$\begin{array}{cc}{}_{q^N}& \left[\mathrm{Formula}19\right]\end{array}$

[n, m+] MRD code:

[00020]$\begin{array}{cc}& \left[\mathrm{Formula}20\right]\end{array}$

is considered. In the expression, n is the code length of the MRD code, m is an information symbol length to be transmitted from the source node toward a terminal node, and is the symbol length of a random number added as countermeasures against eavesdropping of or fewer links. Note that m and are information from a viewpoint of error correction code. Thus, m+ is an information part of the error correction code, parity check symbols are added to it, and encoding of length n is performed.
The generation matrix of:

[00021]$\begin{array}{cc}& \left[\mathrm{Formula}21\right]\end{array}$

is:

[00022]$\begin{array}{cc}\left[\mathrm{Formula}22\right]& \\ G{}_{q^N}^{\left(m+\right)n}& \end{array}$

The lowest rows of the generation matrix G constitute the generation matrix:

[00023]$\begin{array}{cc}\left[\mathrm{Formula}24\right]& \\ G_{\sec }{}_{q^N}^n& \end{array}$

of a [n, ] MRD code in:

[00024]$\begin{array}{cc}{}_{q^N}& \left[\mathrm{Formula}23\right]\end{array}$

In other words,

[00025]$\begin{array}{cc}\left[\mathrm{Formula}25\right]& \\ G=\left[\begin{array}{c}{G}^{}\\ G_{\sec }\end{array}\right].& \left(5\right)\end{array}$

where:

[00026]$\begin{array}{cc}\left[\mathrm{Formula}26\right]& \\ G^{}{}_{q^N}^{mn}& \end{array}$

[0100] Note that the generation matrix of a Gabidulin code as an example of the MRD code has a property that continuous rows constitute the generation matrix of an MRD sub code.

[0101] Typically, an parity check matrix of a [n, k] MRD code is provided in the following form.

[00027]$\begin{array}{cc}\left[\mathrm{Formula}27\right]& \\ H=\left[\begin{array}{cccc}{h}_0^{\left[0\right]}& h_1^{\left[0\right]}& .Math.& h_{n-1}^{\left[0\right]}\\ h_0^{\left[1\right]}& h_1^{\left[1\right]}& .Math.& h_{n-1}^{\left[1\right]}\\ .Math.& .Math.& & .Math.\\ h_0^{\left[n-k-1\right]}& h_1^{\left[n-k-1\right]}& .Math.& h_{n-1}^{\left[n-k-1\right]}\end{array}\right].& \left(6\right)\end{array}$

[0102] In the expression, [i] represents q.sup.i. In the finite field GF(q), h.sub.0, . . . , h.sub.n1GF(q.sup.N) are linearly independent. The minimum rank distance is d=nk+1.

[0103] The generation matrix is provided in the following form.

[00028]$\begin{array}{cc}\left[\mathrm{Formula}28\right]& \\ G=\left[\begin{array}{cccc}{g}_0^{\left[0\right]}& g_1^{\left[0\right]}& .Math.& g_{n-1}^{\left[0\right]}\\ g_0^{\left[1\right]}& g_1^{\left[1\right]}& .Math.& g_{n-1}^{\left[1\right]}\\ .Math.& .Math.& & .Math.\\ g_0^{\left[k-1\right]}& g_1^{\left[k-1\right]}& .Math.& g_{n-1}^{\left[k-1\right]}\end{array}\right].& \left(7\right)\end{array}$

In the finite field GF(q), g.sub.0, . . . , g.sub.n1GF(q.sup.N) are linearly independent. Typically, h.sub.0, . . . , h.sub.n1 and g.sub.0, . . . , g.sub.n1 are normal bases in the extension field GF(q.sup.N).

Encoding Procedure

[0104] As illustrated in step ST1 in FIG. 6, for the given message packets:

[00029]$\begin{array}{cc}\left[\mathrm{Formula}29\right]& \\ u{}_{q^N}^m& \end{array}$

an encoder first selects random-number packets:

[00030]$\begin{array}{cc}\left[\mathrm{Formula}30\right]& \\ v{}_{q^N}^{}& \end{array}$

independently from the message packet u and uniformly at random, and subsequently uses the generation matrix:

[00031]$\begin{array}{cc}\left[\mathrm{Formula}31\right]& \\ G{}_{q^N}^{\left(m+\right)n}& \end{array}$

to generate a code word:

[00032]$\begin{array}{cc}\left[\mathrm{Formula}32\right]& \\ x=G^T\left[\begin{array}{c}u\\ v\end{array}\right]& \left(8\right)\end{array}$

Each packet forming the code word is made of a sequence of information symbols of the length N in the finite field:

[00033]$\begin{array}{cc}{}_q& \left[\mathrm{Formula}33\right]\end{array}$

The i-th packet is expressed as:

[00034]$\begin{array}{cc}\left[\mathrm{Formula}34\right]& \\ x_{i-1}=\left(x_0^{\left(i-1\right)},x_1^{\left(i-1\right)},.Math.,x_{N-1}^{\left(i-1\right)}\right)& \end{array}$

In the expression, Nn. A code word made of n packets is expressed as:

[00035]$\begin{array}{cc}\left[\mathrm{Formula}35\right]& \\ x=\left[\begin{array}{c}{x}_0\\ x_1\\ .Math.\\ x_{n-1}\end{array}\right]=\left[\begin{array}{cccc}{x}_0^{\left(0\right)}& x_1^{\left(0\right)}& .Math.& x_{N-1}^{\left(0\right)}\\ x_0^{\left(1\right)}& x_1^{\left(1\right)}& .Math.& x_{N-1}^{\left(1\right)}\\ .Math.& .Math.& & .Math.\\ x_0^{\left(n-1\right)}& x_1^{\left(n-1\right)}& .Math.& x_{N-1}^{\left(n-1\right)}\end{array}\right].& \left(9\right)\end{array}$

In most cases, N>>n. Typically, a typical unit size of a cryptographic key handled in a key management layer is N=1 kbits to 100 kbits but may be a shorter size as necessary. Typically, the number of nodes is n=3 to 10. [0105] 6) To achieve secrecy and integrity,

[00036]$\begin{array}{cc}\left[\mathrm{Formula}36\right]& \\ m++2+n& \left(10\right)\end{array}$

needs to be satisfied. [0106] 7) At step ST7 in FIG. 6, the terminal node collects 1 packets:

[00037]$\begin{array}{cc}\left[\mathrm{Formula}37\right]& \\ y=\mathrm{Ax}+\mathrm{Bz}& \left(11\right)\end{array}$

from among links through relay nodes and decrypts the message packet. In the expression,

[00038]$\begin{array}{cc}\left[\mathrm{Formula}38\right]& \\ y=\left[\begin{array}{c}{y}_0\\ y_1\\ .Math.\\ y_{l-1}\end{array}\right]=\left[\begin{array}{cccc}{y}_0^{\left(0\right)}& y_1^{\left(0\right)}& .Math.& y_{N-1}^{\left(0\right)}\\ y_0^{\left(1\right)}& y_1^{\left(1\right)}& .Math.& y_{N-1}^{\left(1\right)}\\ .Math.& .Math.& & .Math.\\ y_0^{\left(l-1\right)}& y_1^{\left(l-1\right)}& .Math.& y_{N-1}^{\left(l-1\right)}\end{array}\right].& \left(12\right)\end{array}$$\begin{array}{cc}A=\left[\begin{array}{cccc}{A}_{00}& A_{01}& .Math.& A_{0,n-1}\\ A_{10}& A_{11}& .Math.& A_{1,n-1}\\ .Math.& .Math.& .Math.& .Math.\\ A_{l-1,0}& A_{l-1,1}& .Math.& A_{l-1,n-1}\end{array}\right].& \left(13\right)\end{array}$$\begin{array}{cc}B=\left[\begin{array}{cccc}{B}_{00}& B_{01}& .Math.& B_{0,-1}\\ B_{10}& B_{11}& .Math.& B_{1,-1}\\ .Math.& .Math.& .Math.& .Math.\\ B_{l-1,0}& B_{l-1,1}& .Math.& B_{l-1,-1}\end{array}\right].& \left(14\right)\end{array}$

The decoding is performed by an operation called minimum rank distance decryption to output a code word:

[00039]$\begin{array}{cc}\hat{y}& \left[\mathrm{Formula}39\right]\end{array}$

having the shortest rank distance to a received code word (matrix y). The rank distance between the matrices a and b is defined as d.sub.R(a, b)=rank(ab). Note that the minimum rank distance of the maximum rank distance code [n, m+] is d=nm+1. [0107] 7) Eavesdroppers can eavesdrop, from any places in a network, packets in the form:

[00040]$\begin{array}{cc}\left[\mathrm{Formula}40\right]& \\ w=\mathrm{Dx}& \left(15\right)\end{array}$

(step ST3 in FIG. 6). In the expression,

[00041]$\begin{array}{cc}\left[\mathrm{Formula}41\right]& \\ \begin{array}{c}w=\left[\begin{array}{c}{w}_0\\ w_1\\ .Math.\\ w_{-1}\end{array}\right]\\ =\left[\begin{array}{cccc}{w}_0^{\left(0\right)}& w_1^{\left(0\right)}& .Math.& w_{N-1}^{\left(0\right)}\\ w_0^{\left(1\right)}& w_1^{\left(1\right)}& .Math.& w_{N-1}^{\left(1\right)}\\ .Math.& .Math.& & .Math.\\ w_0^{\left(-1\right)}& w_1^{\left(-1\right)}& .Math.& w_{N-1}^{\left(-1\right)}\end{array}\right].\end{array}& \left(16\right)\end{array}$$\begin{array}{cc}\left[\mathrm{Formula}42\right]& \\ D=\left[\begin{array}{cccc}{D}_{00}& D_{01}& .Math.& D_{0,n-1}\\ D_{10}& D_{11}& .Math.& D_{1,n-1}\\ .Math.& .Math.& .Math.& .Math.\\ D_{-1,0}& D_{-1,1}& .Math.& D_{-1,n-1}\end{array}\right].& \left(17\right)\end{array}$

3.1.3 Decoding Process

[0108] The decryption (step ST7 in FIG. 6) is performed through processes described below. [0109] 1) The terminal node collects the vector y made of 1 packets and performs decoding of secure network code to estimate the message x transmitted from the source node.

[0110] As in Expression (11), the 1 packets are expressed as:

[00042]$\begin{array}{cc}\left[\mathrm{Formula}43\right]& \\ y=\mathrm{Ax}+\mathrm{Bz}& \end{array}$

(step ST6 in FIG. 6), where Bz in the expression is falsified packets inserted at step ST4 in FIG. 6. The receiver (terminal node) does not know of the existence of Bz and performs decoding of secure network code for a falsified y (y in which Bz is injected; hereinafter referred to as y). Thus, the decoding is to estimate the message x, which is transmitted from the source node, by using the 1 packets y collected by the terminal node and a coefficient matrix A used in the secure network code:

[00043]$\begin{array}{cc}\left[\mathrm{Formula}44\right]& \\ y^{}=\mathrm{Ax}& \end{array}$$y^{}=\left[\begin{array}{c}{y}_0^{}\\ y_1^{}\\ .Math.\\ y_{l-1}^{}\end{array}\right]$$\left[\begin{array}{c}{y}_0^{}\\ y_1^{}\\ .Math.\\ y_{l-1}^{}\end{array}\right]=\left[\begin{array}{cccc}{A}_{00}& A_{01}& .Math.& A_{0,n-1}\\ A_{10}& A_{11}& .Math.& A_{1,n-1}\\ .Math.& .Math.& .Math.& .Math.\\ A_{l-1,0}& A_{l-1,1}& .Math.& A_{l-1,n-1}\end{array}\right]\left[\begin{array}{c}{x}_0\\ x_1\\ .Math.\\ x_{n-1}\end{array}\right]$

In the expressions, the packet y and the matrix A are known numbers and x.sub.0, x.sub.1, . . . , x.sub.n1 are n unknown numbers, and thus, the above expression is the problem of finding solutions for 1 simultaneous equations including n unknown numbers. When the rank of the matrix A is n, x can be calculated. In particular, the inverse matrix A.sup.1 of A exists when the rank of the matrix A is n with n=1. The inverse matrix A.sup.1 of the matrix A can be calculated by the Gauss-Jordan method and the message x can be estimated through matrix calculation with the packet y as described below. An estimated value of the message x is denoted by x.

[00044]$\begin{array}{cc}\left[\mathrm{Formula}45\right]& \\ x^{}=A^{-1}{y}^{}& \end{array}$ [0111] 2) MRD decoding for the estimated x is performed to calculate u and v.

[0112] As understood from Expression (8), x is the code word of an MRD code and is generated by a sequence made of the given message packet:

[00045]$\begin{array}{cc}u{}_{q^N}^m& \left[\mathrm{Formula}46\right]\end{array}$

and the random-number packet:

[00046]$\begin{array}{cc}v{}_{q^N}^{}& \left[\mathrm{Formula}47\right]\end{array}$

MRD code decryption is performed for the estimated x to calculate u and v. Decoding of the Gabidulin code as a typical example of an MRD code will be described below.

[0113] An parity-check matrix H of the Gabidulin code is constituted by using a normal basis [.sup.[0], .sup.[1], .sup.[2], . . . , .sup.[n1]] in the extension field GF(q.sup.N). Decoding is restoration of the code word x (code length n) of the Gabidulin code from the received word x. When rank error e is added to x, x is expressed as follows:

[00047]$\begin{array}{cc}{x}^{}=x+e& \left[\mathrm{Formula}48\right]\end{array}$

[0114] The error vector e can be decomposed as follows.

[00048]$\begin{array}{cc}\begin{array}{c}e=\left(e_0,.Math.,e_{n-1}\right){}_{q^N}^n\\ =a\end{array}& \left[\mathrm{Formula}49\right]\end{array}$$a=\left(a_0,.Math.,a_{-1}\right){}_{q^N}^{}$${}_q^n$

In the expression, a is called an error span of rank error in GF(q.sup.N) and is one of the bases of an error space. In addition, is called an error coefficient and corresponds to a so-called error locator of a Reed-Solomon code. Decoding starts with syndrome calculation, calculates the error span a and the error coefficient , and estimates the error vector e.

[0115] Procedure 1: a syndrome is calculated from x and the parity-check matrix H. The syndrome:

[00049]$\begin{array}{cc}{S}_l{}_{q^N},l=0,.Math.,n-k-1& \left[\mathrm{Formula}50\right]\end{array}$

is defined as follows:

[00050]$\begin{array}{cc}{S}_l\stackrel{\mathrm{def}}{=}{\mathrm{Hx}}^{}& \left[\mathrm{Formula}51\right]\end{array}$

[0116] Procedure 2: a coefficient y of an error locator polynomial (ELP) and an estimated number of rank errors are calculated from the syndrome S.sub.1 by using a Berlekamp-Massey method. The ELP is given by the expression below.

[00051]$\begin{array}{cc}\left(x\right)={}_0{x}^{\left[0\right]}+{}_1{x}^{\left[1\right]}+{}_2{x}^{\left[2\right]}+.Math.+{}_{}{x}^{\left[\right]}& \left[\mathrm{Formula}52\right]\end{array}$

[0117] Procedure 3: the root (d) of the ELP is calculated by using a Gaussian elimination method. The root d is obtained by solving the expression below for x.

[00052]$\begin{array}{cc}\left(x\right)=0& \left[\mathrm{Formula}53\right]\end{array}$${}_0{x}^{\left[0\right]}+{}_1{x}^{\left[1\right]}+{}_2{x}^{\left[2\right]}+.Math.+{}_{}{x}^{\left[\right]}=0$$-{}_{0}x={}_1{x}^{\left[1\right]}+{}_2{x}^{\left[2\right]}+.Math.+{}_{}{x}^{\left[\right]}$$-{}_{0}x={.Math.}_{w=1}^{}{}_w{x}^{\left[w\right]}$

[0118] Procedure 4: the error coefficient is calculated from d. The error coefficient can be calculated from d by using the relationship of the expression below.

[00053]$\begin{array}{cc}{d}_j={.Math.}_{i=0}^{n-1}{}_{i,j}{}^{\left[k+i\right]}j=0,1,.Math.,-1& \left[\mathrm{Formula}54\right]\end{array}$

[0119] Procedure 5: the error span a is calculated from d. The error span a can be calculated from d by using the relationship of the expression below.

[00054]$\begin{array}{cc}{S}_l={.Math.}_{j=0}^{-1}{a}_j{d}_j^{\left[l\right]}& \left[\mathrm{Formula}55\right]\end{array}$

[0120] Procedure 6: an error vector is estimated from the error span a and the error coefficient .

[00055]$\begin{array}{cc}\hat{e}=a& \left[\mathrm{Formula}56\right]\end{array}$

[0121] Procedure 7: an estimated code word is calculated by subtracting the estimated error vector from x.

[00056]$\begin{array}{cc}\hat{x}=x^{}-\hat{e}& \left[\mathrm{Formula}57\right]\end{array}$

[0122] Procedure 8: the message u is calculated from the estimated code word. The expression below separates u and v.

[00057]$\begin{array}{cc}x=G^{}\left[\begin{array}{c}u\\ v\end{array}\right]& \left[\mathrm{Formula}58\right]\end{array}$

[0123] The source node performs step ST1 in FIG. 6 (concealment and error correction encoding). Specifically, at step ST1, the source node generates the code word x by using the message packet u, the random number v, and the generation matrix G and then splits the code word x into n of packets. Subsequently, the source node subjects the above-described packets to OTP encryption (step ST2) and transmits the OTP-encrypted packets to relay nodes adjacent to the source node or directly transmits the above-described packets to relay nodes without performing OTP encryption.

[0124] Each relay node receives the packets from a plurality of respective nodes connected through input links. In a case in which the received packets are OTP-encrypted, the relay node performs OTP decryption (step ST5). The OTP-decrypted packets are subject to the following linear combination processing. In a case in which the received packets are not OTP-encrypted, the received packets are directly subject to the following linear combination processing. The relay node then performs the linear combination processing of the above-described packets with the linear network code matrix.

[0125] The terminal node receives the packets from a plurality of respective relay nodes connected through input links. In a case in which the received packets are OTP-encrypted, the terminal node performs OTP decryption (step ST5), and assembles the received code word. The OTP-decrypted code words are input code words to the following calculation at step ST6. In a case in which the received packets are not OTP-encrypted, the received packets are input code word to the following calculation at step ST6. Subsequently, the terminal node performs the calculation at step ST6 by using the above-described input code words. The terminal node further performs error correction decoding and undoing of concealment (step ST7) on a calculation result obtained at step ST6.

[0126] Through the above-described process, rank error added in a network can be corrected. Moreover, information-theoretic security is maintained by the effect of the random-number packets v even if packets are eavesdropped at links in a number equal to or less than a threshold value (the threshold value depends on the number of the random-number packets v). This means that it is possible to perform secret communication with information-theoretic security maintained in the entire network even if OTP encryption cannot be executed at some links.

4. Example of Use

[0127] The Gabidulin code in the field GF(q.sup.N) can be applied to an advanced distributed key relay system using secure network coding.

[0128] Consider a case in which the packet size is 64 bits. In a case of q=16, N is 16. In addition, consider a network configuration in which a transmitted message is divided into four as illustrated in FIG. 7. In this case, n is four.

[0129] In a communication network NW5 illustrated in FIG. 7, a source node s is connected to relay nodes s.sub.0 to s.sub.3 through links. In addition, the relay nodes s.sub.0 to s.sub.3 are each connected to relay nodes v.sub.0 to v.sub.3 through links. Furthermore, the relay nodes v.sub.0 to v.sub.3 are each connected to terminal nodes t.sub.0 to t.sub.3 through links.

[0130] The notation [1] illustrated above each of the relay nodes s.sub.0 to s.sub.3 means that coefficients of linear combination are 1. Specifically, the relay node s.sub.0 transmits intact a packet x.sub.0 received from the source node s to the relay nodes v.sub.0 to v.sub.3. Similarly, the relay node s.sub.1 transmits intact a packet x.sub.1 received from the source node s to the relay nodes v.sub.0 to v.sub.3, the relay node s.sub.2 transmits intact a packet x.sub.2 received from the source node s to the relay nodes v.sub.0 to v.sub.3, and the relay node s.sub.3 transmits intact a packet x.sub.3 received from the source node s to the relay nodes v.sub.0 to v.sub.3.

[0131] The relay nodes v.sub.0 to v.sub.3 each receive the packet x.sub.0 from the relay node s.sub.0, receive the packet x.sub.1 from the relay node s.sub.1, receive the packet x.sub.2 from the relay node s.sub.2, and receive the packet x.sub.3 from the relay node s.sub.3.

[0132] Subsequently, the relay node v.sub.0 performs linear combination processing with elements A.sub.00, A.sub.01, A.sub.02, and A.sub.03 of a linear network code matrix and the received packets x.sub.0 to x.sub.3. Specifically, the relay node v.sub.0 obtains a packet y.sub.0 by performing the calculation below.

[00058]$y_0=A_{00}*x_0+A_{01}*x_1+A_{02}*x_2+A_{03}*x_3$

[0133] The relay node v.sub.0 transmits the packet y.sub.0 to each of the terminal nodes t.sub.0 to t.sub.3.

[0134] Similarly, the relay nodes v.sub.1 to v.sub.3 perform linear combination processing with the elements of the linear network code matrix and the received packets x.sub.0 to x.sub.3. In the linear combination processing, the relay node v.sub.1 uses elements A.sub.10, A.sub.11, A.sub.12, and A.sub.13 of the linear network code matrix, the relay node v.sub.2 uses elements A.sub.20, A.sub.21, A.sub.22, and A.sub.23 of the linear network code matrix, and the relay node v.sub.3 uses elements A.sub.30, A.sub.31, A.sub.32, and A.sub.33 of the linear network code matrix. The relay nodes v.sub.1 to v.sub.3 obtain packets y.sub.1 to y.sub.3, respectively, through the linear combination processing. The relay node v.sub.1 transmits the packet y.sub.1 to each of the terminal nodes t.sub.0 to t.sub.3, the relay node v.sub.2 transmits the packet y.sub.2 to each of the terminal nodes t.sub.0 to t.sub.3, and the relay node v.sub.3 transmits the packet y.sub.3 to each of the terminal nodes t.sub.0 to t.sub.3.

[0135] The 44 matrix A constituted by [A.sub.00 A.sub.01 A.sub.02 A.sub.03], [A.sub.10 A.sub.11 A.sub.12 A.sub.13], [A.sub.20 A.sub.21 A.sub.22 A.sub.23], and [A.sub.30 A.sub.31 A.sub.32 A.sub.33] is the linear network code matrix in the present example. The elements of the linear network code matrix are often generated such that the linear network code matrix is of full rank, and can be typically generated even at random.

[0136] Each of the terminal nodes t.sub.0 to t.sub.3 receives the packet y.sub.0 from the relay node v.sub.0, receives the packet y.sub.1 from the relay node v.sub.1, receives the packet y.sub.2 from the relay node v.sub.2, and receives the packet y.sub.3 from the relay node v.sub.3. Subsequently, each of the terminal nodes t.sub.0 to t.sub.3 calculates the product of the inverse matrix A.sup.1 of the linear network code matrix A and a vector made of the received packets y.sub.0 to y.sub.3, thereby obtaining the original packets x.sub.0 to x.sub.3.

[0137] Consider, as the Gabidulin code applied to the network, a code with a code length of four and an information symbol number of two. The information symbols of two include the message packets transmitted from the source node s of the number m=1 and the random-number packets of the number =1. A code word of n=4 is obtained with parity check added to the information symbols of two. The code word is constituted by the four packets x.sub.0 to x.sub.3, and the four packets are transmitted in a distributed manner to the relay nodes s.sub.0 to s.sub.3, respectively. Then, after linear combination is performed at the relay nodes, the packets finally reach the terminal nodes t.sub.0 to t.sub.3. In this manner, the packets transmitted from the source node s are transmitted to the terminal nodes t.sub.0 to t.sub.3 through the relay nodes s.sub.0 to s.sub.3 and the relay nodes v.sub.0 to v.sub.3.

[0138] In the Gabidulin code, =1 and =0 satisfy the condition for achieving secrecy and integrity, which is indicated in Expression (10). Accordingly, information-theoretic security is maintained even if packets are eavesdropped at one link (=1). Simultaneously, one rank error can be corrected (=1).

[0139] A combination of OTP encryption and the Gabidulin code is considered next. The dotted line in FIG. 7 represents a link at which OTP encryption cannot be performed. Information leaks when packets are eavesdropped at a link that is not OTP-encrypted, but information-theoretic security is maintained with application of the Gabidulin code even when packets are eavesdropped at the link.

[0140] Consider a case in which a message transmitted from the source node s is u=89A1CE37508C00E9 and a random-number packet is v=ACDD3AC51A8C5E87. The combination of u and v is input to a Gabidulin encoder.

[00059]$\begin{array}{cc}\left[\begin{array}{c}u\\ v\end{array}\right]=\left[\begin{array}{c}89A1\mathrm{CE}37508C00E9\\ \mathrm{ACCD}3\mathrm{AC}51A8C5E87\end{array}\right]& \left[\mathrm{Formula}59\right]\end{array}$

[0141] The generation matrix is given by the expression below.

[00060]$\begin{array}{cc}\text{?}& \left[\mathrm{Formula}60\right]\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0142] Gabidulin encoding can be performed as follows.

[00061]$\begin{array}{cc}\begin{array}{c}x=G^{}\left[\begin{array}{c}u\\ v\end{array}\right]=\left[\begin{array}{cc}606A606A606A606A& 06A606A606A606A6\\ 06A606A606A606A6& 6A606A606A606A60\\ 6A606A606A606A60& A606A606A606A606\\ A606A606A606A606& 606A606A606A606A\end{array}\right]\left[\begin{array}{c}89A1\mathrm{CE}37508C00E9\\ \mathrm{ACDD}3\mathrm{AC}51A8C5E87\end{array}\right]\\ =\left[\begin{array}{c}\mathrm{EF}8B4\mathrm{FEC}5\mathrm{BF}236\mathrm{AA}\\ E62E6\mathrm{BDCE}953\mathrm{DD}2C\\ 6\mathrm{AC}388A42\mathrm{EE}42A96\\ B5\mathrm{DE}05390045A455\end{array}\right]\end{array}& \left[\mathrm{Formula}61\right]\end{array}$

[0143] In a distributed key relay system network, x generated by Gabidulin encoding is distributed into four packets, and transmission relay to terminal nodes is performed.

[0144] The terminal nodes t.sub.0 to t.sub.3 collect four packets from among links through relay nodes. However, for example, one error packet is injected at a link in the network by an eavesdropper. In this example, an error packet (1918EB1300152F8F) is injected at the link s.sub.1.fwdarw.v.sub.1 in the network.

[0145] Packets y collected by the terminal nodes are as follows. The packets y are affected by the error packet.

[00062]$\begin{array}{cc}{y}^{}=\left[\begin{array}{c}F002E48B36202368\\ F8949E1F42709344\\ \mathrm{CDE}0\mathrm{DDD}08\mathrm{EEA}8B4E\\ 0607C825\mathrm{DD}7C7\mathrm{BA}8\end{array}\right]& \left[\mathrm{Formula}62\right]\end{array}$

[0146] In the secure network decoding, x is calculated from the expression below.

[00063]$\begin{array}{cc}{y}^{}=\mathrm{Ax}=\left[\begin{array}{cccc}{A}_{00}& A_{01}& A_{02}& A_{03}\\ A_{10}& A_{11}& A_{12}& A_{13}\\ A_{20}& A_{21}& A_{22}& A_{23}\\ A_{30}& A_{31}& A_{32}& A_{33}\end{array}\right]x& \left[\mathrm{Formula}63\right]\end{array}$$\mathrm{With}:$$\begin{array}{cc}A=\left[\begin{array}{cccc}9& 4& B& 4\\ 2& 9& D& 6\\ F& B& 3& 1\\ B& F& D& 2\end{array}\right]& \left[\mathrm{Formula}64\right]\end{array}$

the inverse matrix of A is given by the expression below.

[00064]$\begin{array}{cc}{A}^{-1}=\left[\begin{array}{cccc}E& F& A& 8\\ 2& 6& 3& 6\\ 2& C& D& C\\ 6& 2& 7& 9\end{array}\right]& \left[\mathrm{Formula}65\right]\end{array}$

A secure network decoding result x is calculated as follows.

[00065]$\begin{array}{cc}\begin{array}{c}{x}^{}=A^{-1}{y}^{}\\ =\left[\begin{array}{cccc}E& F& A& 8\\ 2& 6& 3& 6\\ 2& C& D& C\\ 6& 2& 7& 9\end{array}\right]\left[\begin{array}{c}F002E48B36202368\\ F8949E1F42709344\\ \mathrm{CDE}0\mathrm{DDD}08\mathrm{EEA}8B4E\\ 0607C825\mathrm{DD}7C7\mathrm{BA}8\end{array}\right]\\ =\left[\begin{array}{c}0862F70D5B11C33F\\ \mathrm{DE}1575E9E96\mathrm{CBF}9E\\ 09A6A7\mathrm{CE}2E89\mathrm{EEC}2\\ \mathrm{ACC}6\mathrm{EE}2A00508\mathrm{BDA}\end{array}\right]\end{array}& \left[\mathrm{Formula}66\right]\end{array}$

Comparison between x and x shows that all packets of x are errors.

[0147] Hereinafter, Gabidulin decoding is performed for x to correct the errors that occurred.

[0148] Procedure 1: syndromes S.sub.0 and S.sub.1 are calculated from x and the parity-check matrix H. When the parity-check matrix is the expression below:

[00066]$\begin{array}{cc}\begin{array}{c}H=\left[\begin{array}{cccc}{h}_0^{\left[0\right]}& h_1^{\left[0\right]}& h_2^{\left[0\right]}& h_3^{\left[0\right]}\\ h_0^{\left[1\right]}& h_1^{\left[1\right]}& h_2^{\left[1\right]}& h_3^{\left[1\right]}\end{array}\right]\\ =\left[\begin{array}{cccc}0100010001000100& 1000100010001000& 0001000100010001& 0010001000100010\\ 1000100010001000& 0001000100010001& 0010001000100010& 0100010001000100\end{array}\right]\end{array}& \left[\mathrm{Formula}67\right]\end{array}$

the syndromes can be calculated as follows.

[00067]$\begin{array}{cc}\begin{array}{c}\left[\begin{array}{c}{S}_0\\ S_1\end{array}\right]={\mathrm{Hx}}^{}\\ =\left[\begin{array}{c}9836\mathrm{FDA}882A126E8\\ 281\mathrm{DEAE}133D9\mathrm{CE}8F\end{array}\right]\end{array}& \left[\mathrm{Formula}68\right]\end{array}$

[0149] Procedure 2: coefficients .sub.0 and .sub.1 of an error locator polynomial (ELP) and the estimated number of rank errors are calculated from the syndromes by using the Berlekamp-Massey method.

[00068]$\begin{array}{cc}{}_0=1111111111111111& \left[\mathrm{Formula}69\right]\end{array}$${}_1=A7E1A7E1A7E1A7E1$$=1$

[0150] Procedure 3: the root (d.sub.0) of the ELP is calculated by using the Gaussian elimination method. The root d.sub.0 is obtained by solving the expression below for x.

[00069]$\begin{array}{cc}{}_{0}x+{}_1{x}^{\left[1\right]}=0& \left[\mathrm{Formula}70\right]\end{array}$$d_0=\left[\begin{array}{c}2\\ E\\ B\\ 1\end{array}\right]$

[0151] Procedure 4: an error coefficient .sub.0 is calculated from d.sub.0.

[00070]$\begin{array}{cc}{}_0=\left[\begin{array}{c}B\\ 1\\ 2\\ E\end{array}\right]& \left[\mathrm{Formula}71\right]\end{array}$

[0152] Procedure 5: an error span a.sub.0 is calculated from d.sub.0.

[00071]$\begin{array}{cc}{a}_0=383B1E35003F62B2& \left[\mathrm{Formula}72\right]\end{array}$

[0153] Procedure 6: an error vector is estimated from the error span a.sub.0 and the error coefficient .sub.0.

[00072]$\begin{array}{cc}\begin{array}{c}\hat{e}={}_0{a}_0\\ =\left[\begin{array}{c}B\\ 1\\ 2\\ E\end{array}\right]\left[383B1E35003F62B2\right]\\ =\left[\begin{array}{c}E7E9B8E100E3F595\\ 383B1E35003F62B2\\ 63652F6A006\mathrm{DC}454\\ 1918\mathrm{EB}1300152F8F\end{array}\right]\end{array}& \left[\mathrm{Formula}73\right]\end{array}$

[0154] Procedure 7: an estimated code word is calculated by subtracting the estimated error vector from x.

[00073]$\begin{array}{cc}\begin{array}{c}x=x^{}-\hat{e}\\ =\left[\begin{array}{c}0862F70D5B11C33F\\ \mathrm{DE}1575E9E96\mathrm{CBF}9E\\ 09A6A7\mathrm{CE}2E89\mathrm{EEC}2\\ \mathrm{ACC}6\mathrm{EE}2A00508\mathrm{BDA}\end{array}\right]-\left[\begin{array}{c}E7E9B8E100E3F595\\ 383B1E35003F62B2\\ 63652F6A006\mathrm{DC}454\\ 1918\mathrm{EB}1300152F8F\end{array}\right]\\ =\left[\begin{array}{c}\mathrm{EF}8B4\mathrm{FEC}5\mathrm{BF}236\mathrm{AA}\\ E62E6\mathrm{BDCE}953\mathrm{DD}2C\\ 6\mathrm{AC}388A42\mathrm{EE}42A96\\ B5\mathrm{DE}05390045A455\end{array}\right]\end{array}& \left[\mathrm{Formula}74\right]\end{array}$

[0155] Procedure 8: the message u is calculated from the estimated code word. The expression below separates u and v.

[00074]$\begin{array}{cc}x=G^{}\left[\begin{array}{c}u\\ v\end{array}\right]& \left[\mathrm{Formula}75\right]\end{array}$$\left[\begin{array}{c}\mathrm{EF}8B4\mathrm{FEC}5\mathrm{BF}236\mathrm{AA}\\ E62E6\mathrm{BDCE}953\mathrm{DD}2C\\ 6\mathrm{AC}388A42\mathrm{EE}42A96\\ B5\mathrm{DE}05390045A455\end{array}\right]=\left[\begin{array}{cc}606A606A606A606A& 06A606A606A606A6\\ 06A606A606A606A6& 6A606A606A606A60\\ 6A606A606A606A60& A606A606A606A606\\ A606A606A606A606& 606A606A606A606A\end{array}\right]\left[\begin{array}{c}u\\ v\end{array}\right]$$u=89A1\mathrm{CE}37508C00E9$$v=\mathrm{ACDD}3\mathrm{AC}51A8C5E87$

[0156] Accordingly, error is corrected and the correct message u is obtained even though one error packet is injected at a link in the network by an eavesdropper.

[0157] The present example shows that, in a case in which OTP encryption cannot be performed at one link in a network and an eavesdropper eavesdrops and injects an error packet at the link, secret communication can be realized with information-theoretic security maintained in the entire network, and also, the injected error can be corrected.

[0158] In a case in which only OTP encryption is used, secret communication with information-theoretic security maintained cannot be performed when cryptographic keys are insufficient. It is necessary to wait for generation of a new cryptographic key, and thus communication speed decreases.

[0159] In a case in which only the Gabidulin code is used without OTP encryption, eavesdropping at a small number of links can be handled, but secret communication with information-theoretic security maintained cannot be realized when eavesdropping occurs at a large number of links. In the present example, information-theoretic security is maintained even when packets are eavesdropped at one link (=1). Increase of u enables handling of eavesdropping at a larger number of links but leads to decrease of the number of transmitted messages m. This means degradation of communication efficiency, and it is difficult to handle eavesdropping at a large number of links with only the Gabidulin code. Furthermore, in a case in which the number of links in a network is large, the number of eavesdropped links tends to increase, and it is more difficult to handle eavesdropping with only the Gabidulin code.

[0160] With the combination of OTP encryption and the Gabidulin code as in the present example, secret communication with information-theoretic security maintained can be realized without decrease of communication speed even when a large number of links is potentially eavesdropped.

[0161] According to the above-described embodiment, new advanced secure network coding for compensating disadvantages of the conventional secure network coding and the conventional quantum cryptographic communication network, and synergizing their advantages can be achieved by combining the MRD code as one kind of secure network coding and OTP encryption.

[0162] Note that the present invention is not limited to a quantum cryptographic communication network, but may be performed in any communication network in which a source node is connected to terminal nodes through relay nodes. The MRD code is suitable for correction of rank error that is likely to occur in a communication network in which linear network coding is performed, but the present invention is also applicable to a communication network in which linear network coding is not performed.

[0163] FIG. 8 illustrates a control device 100 of the communication network NW5 illustrated in FIG. 7. The control device 100 is configured to be able to communicate with each node in the communication network NW5 and includes a first instruction unit 110, a random number transmission unit 120, and a second instruction unit 130. The communication network NW5 and the control device 100 may be collectively referred to as a communication network system.

[0164] The first instruction unit 110 instructs a source node s among a plurality of nodes in the communication network NW5 whether to perform MRD encoding when the source node s performs transmission. For example, the first instruction unit 110 may determine whether there are sufficient keys for performing OTP encryption at each link of the communication network NW5, determine that MRD encoding is needed in a case in which sufficient keys are not available, and determine that MRD encoding is not needed in a case in which sufficient keys are available. Alternatively, another entity other than the control device 100 in the communication network system may perform the determination and transmit a result of the determination to the first instruction unit 110. The entity is, for example, the QKDN manager MG1, the network manager MG2, or the QKDN controller CT.

[0165] The random number transmission unit 120 transmits a random number in accordance with the maximum number of links susceptible to eavesdropping to the source node s in a case in which the source node s is instructed to perform MRD encoding by the first instruction unit 110. The maximum number of links susceptible to eavesdropping is determined in accordance with the network status of the communication network NW5. The determination may be performed by the random number transmission unit 120 or may be performed by the above-described entity and then a result of the determination may be transmitted to the random number transmission unit 120.

[0166] The second instruction unit 130 instructs each node in the communication network NW5 whether to perform OTP encryption when the node performs transmission to another node.

[0167] The second instruction unit 130 may be configured to instruct all nodes that perform transmission through links where cryptographic keys necessary for OTP encryption are prepared to perform OTP encryption in a case in which it is determined by the first instruction unit 110 that MRD encoding is needed.

[0168] Alternatively, the second instruction unit 130 may be configured to instruct, in accordance with security request of information to be communicated, at least one node that performs transmission not to perform OTP encryption in a case in which it is determined by the first instruction unit 110 that MRD encoding is needed. In this case, cryptographic key consumption can be reduced.

[0169] A second control unit 130 may be configured to instruct all nodes that perform transmission to perform OTP encryption in a case in which it is determined by the first instruction unit 110 that MRD encoding is not needed.

[0170] Alternatively, MRD encoding and OTP encryption may be constantly performed at a source node in a communication network including a plurality of nodes and links each connecting two of the nodes. Specifically, the source node in this case includes an MRD encoding unit configured to generate an MRD-encoded message by performing MRD encoding of a message by using a random number in accordance with a maximum number of links susceptible to eavesdropping among the links, an OTP encrypting unit configured to generate an OTP-encrypted message by performing OTP encryption of the MRD-encoded message by using a key for OTP encryption, and a transmission unit configured to transmit the OTP-encrypted message to another node connected to the source node through a corresponding one of the links.

[0171] In addition, it is possible to configure a communication network including the above-described source node, a terminal node that is a final transmission destination of the message, and a relay node that performs relay between the source node and the terminal node.

[0172] A plurality of relay nodes may be provided on a communication path between the source node and the terminal node. The number of random numbers used for MRD encoding and the number of relay nodes that perform OTP encryption at relaying are determined in accordance with the number of links where a pair of cryptographic keys necessary for OTP encryption cannot be prepared (in other words, the number of links where communication security is potentially not maintained when eavesdropped).

[0173] FIG. 9 illustrates an exemplary computer hardware configuration of the control device 100. The control device 100 includes a CPU 351, an interface device 352, a display device 353, an input device 354, a drive device 355, an auxiliary storage device 356, and a memory device 357, and these components are mutually connected through a bus 358.

[0174] A program that implements functions of the control device 100 is provided by a recording medium 359 such as a CD-ROM. When the recording medium 359 in which the program is recorded is set to the drive device 355, the program is installed from the recording medium 359 onto the auxiliary storage device 356 through the drive device 355. Alternatively, the installation of the program does not necessarily need to be performed through the recording medium 359, but may be performed through a network. The auxiliary storage device 356 stores the installed program, and also stores necessary files, data, and the like.

[0175] When an instruction is made to activate the program, the memory device 357 reads and stores the program from the auxiliary storage device 356. The CPU 351 implements the functions of the control device 100 in accordance with the program stored in the memory device 357. The interface device 352 is used as an interface for connection to other computers through a network. The display device 353 displays a graphical user interface (GUI) or the like of the program. The input device 354 is a keyboard, a mouse, or the like.

[0176] Note that each node in the communication network has the same computer hardware configuration as the control device 100.

[0177] The above-described embodiment has not only an aspect as a device, but also an aspect as a method, and an aspect as a computer program.

[0178] The following supplements are disclosed for the above-described embodiment.

Supplement 1

[0179] A control device of a communication network including a plurality of nodes and links each connecting two of the nodes, the control device including: [0180] a first instruction unit configured to instruct a source node among the plurality of nodes whether to perform MRD encoding when the source node performs transmission; [0181] a random number transmission unit configured to transmit a random number in accordance with a maximum number of links susceptible to eavesdropping among the links to the source node in a case in which the source node is instructed to perform MRD encoding by the first instruction unit; and [0182] a second instruction unit configured to instruct each of the plurality of nodes whether to perform OTP encryption when the node performs transmission to another node.

Supplement 2

[0183] The control device according to Supplement 1, in which the communication network is a key management network in a quantum key distribution network.

Supplement 3

[0184] The control device according to Supplement 1, in which the communication network is a service layer of a user network in a quantum cryptographic communication network.

Supplement 4

[0185] A communication network system including: [0186] the control device according to any one of Supplements 1 to 3; [0187] the plurality of nodes; and [0188] the links each connecting two of the nodes.

Supplement 5

[0189] A source node in a communication network including a plurality of nodes and links each connecting two of the nodes, the source node including: [0190] an MRD encoding unit configured to generate an MRD-encoded message by performing MRD encoding of a message by using a random number in accordance with a maximum number of links susceptible to eavesdropping among the links; [0191] an OTP encrypting unit configured to generate an OTP-encrypted message by performing OTP encryption of the MRD-encoded message by using a key for OTP encryption; and [0192] a transmission unit configured to transmit the OTP-encrypted message to another node connected to the source node through a corresponding one of the links.

Supplement 6

[0193] A communication network including: [0194] the source node according to Supplement 5; [0195] a terminal node that is a final transmission destination of the message; and [0196] a relay node that performs relay between the source node and the terminal node.

[0197] Although an embodiment of the present invention is described above, the present invention is not limited to the above-described embodiment, and various modifications and changes based on the technical idea of the present invention may be made.

REFERENCE SIGNS LIST

[0198] NW1 to NW5 communication network [0199] QM QKD module [0200] TN trusted node [0201] KM key manager [0202] CT QKDN controller [0203] MG1 QKDN manager [0204] MG2 network manager [0205] UD user terminal [0206] 100 control device [0207] 110 first instruction unit [0208] 120 random number transmission unit [0209] 130 second instruction unit