# US 7,609,839 B2 · Quantum key distribution method and communication device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,609,839 B2
- Document ID: US7609839B2
- Status: Granted
- Kind: B2
- Application number: 10/528,075
- Filed: 2003-09-12
- Published: 2006-03-16
- Granted: 2009-10-27
- Earliest claimed: 2002-09-18
- Assignees: Mitsubishi Electric Corporation
- Inventors: Youdai Watanabe; Wataru Matsumoto
- Web page: https://patentgrep.com/patent/US7609839B2

## CPC

- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take precedence)}
- H03M 13/1151: {Algebraically constructed LDPC codes, e.g. LDPC codes derived from Euclidean geometries [EG-LDPC codes] (H03M13/116, H03M13/1174 take precedence)}
- H04L 9/0858: {Details about key distillation or coding, e.g. reconciliation, error correction, privacy amplification, polarisation coding or phase coding}
- G11B 20/00086: {Circuits for prevention of unauthorised reproduction or copying, e.g. piracy (indicating unauthorised use of record carriers in general G11B23/28; scrambling for television signal recording H04N5/913; network architectures or network protocols for network security H04L63/00; cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00)}
- G11B 20/0021: {involving encryption or decryption of contents recorded on or reproduced from a record carrier}
- G11B 20/00927: {wherein said defects or errors are generated on purpose, e.g. intended scratches}
- G11B 20/18: Error detection or correction; Testing {, e.g. of drop-outs}
- H03M 13/11: using multiple parity bits
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)

## Abstract

In order to create a highly-secured common key while a data error on a transmission path is corrected by an error correction code having remarkably high characteristics, in a quantum key distribution method of the invention, at first a communication apparatus on a reception side corrects the data error of reception data by a deterministic, stable-characteristics parity check matrix for a “Irregular-LDPC code.” The communication apparatus on the reception side and a communication apparatus on a transmission side discard a part of pieces of the common information according to public error correction information.

## Claims

### Claim 1

A quantum key distribution method employed on a quantum cryptosystem including a first communication apparatus that transmits photons onto a quantum communication path and a second communication apparatus that measures the photons, comprising:
a check matrix creation step of each of the first communication apparatus and the second communication apparatus creating the same parity check matrices H(n×k);
a random number generation step of the first communication apparatus generating a random number sequence (transmission data) and randomly determining a predetermined transmission code (base) by the first communication apparatus, and the second communication apparatus randomly determining a predetermined reception code (base);
a photon transmission step of the first communication apparatus transmitting a photon onto the quantum communication path while the photon is in a quantum state specified by a combination of the transmission data and the transmission code;
a photon reception step of the second communication apparatus measuring the photon transmitted on the quantum communication path to obtain reception data specified by the combination of the reception code and measurement result;
a data deletion step of each of the first communication apparatus and the second communication apparatus deciding whether the measuring has been performed with an appropriate measuring apparatus, saving the reception data of n bits if the measuring has been performed with the appropriate measuring apparatus and transmission data that corresponds to the reception data, and discarding other pieces of the data;
an error correction information notification step of the first communication apparatus notifying the second communication apparatus through a public communication path of error correction information of k bits based on the parity check matrix H and the transmission data of n bits;
an error correction step of the second communication apparatus correcting the error of the reception data based on the parity check matrix H, the reception data of n bits, and the error correction information; and
a cryptographic key creation step of each of the first communication apparatus and the second communication apparatus discarding a part of pieces of the common information after correction according to public error correction information, creating a cryptographic key using information that has remained after discarding, wherein the amount of information remaining is n−k bits, and setting the cryptographic key as a common key which is shared between first communication apparatus and the second communication apparatus.

### Claim 2 (depends on 1)

The quantum key distribution method according to claim 1, wherein the check matrix creation step includes:
weight searching step of using finite affine geometry as a basic matrix and searching optimum row and column weight distributions of the parity check matrix by performing optimization of Gaussian approximation; and
dividing step of dividing randomly the row and column weights of the finite affine geometry based on the optimum weight distribution by a predetermined procedure, and creating the parity check matrix H of a low-density parity check code in which both the row and column weights or one of the row and column weights is not uniform.

### Claim 3 (depends on 2)

The quantum key distribution method according to claim 2, wherein the cryptographic key creation step includes performing random permutation to the column of the parity check matrix H, selecting specific “1” in the first column of finite affine geometry AG(2,2S) of a creation element of the parity check matrix H, exchanges a position of “1” through a public communication path, specifying the position (column) after the division corresponding to “1” from the parity check matrix after the random permutation and the position (column) after the division corresponding to “1” in each cyclically shifted column, and discarding the part of pieces of the common information corresponding to the specified position (column).

### Claim 4 (depends on 3)

The quantum key distribution method according to claim 3, wherein the cryptographic key creation step includes:
one of the communication apparatuses, out of the first communication apparatus and the second communication apparatus, creating a nonsingular random matrix R((n−k)×(n−k)) to act on the cryptographic key after discarding the part of pieces of the common information and informing the nonsingular random matrix R to other one of the communication apparatuses through the public communication path,
the first communication apparatus and the second communication apparatus using the nonsingular random matrix R to create the cryptographic key.

### Claim 5 (depends on 1)

The quantum key distribution method according to claim 1, wherein the check matrix creation step includes creating an inverse matrix G−1(n×(n−k)), which satisfies G−1·G=I (unit matrix), from a creation matrix G((n−k)×n) satisfying “HG=0;” and
the cryptographic key creation step includes discarding the part of pieces of the common information by the inverse matrix G−1.

### Claim 6 (depends on 5)

The quantum key distribution method according to claim 5, wherein the cryptographic key creation step includes:
one of the communication apparatuses, out of the first communication apparatus and the second communication apparatus, creating a nonsingular random matrix R((n−k)×(n−k)) to act on the cryptographic key after discarding the part of pieces of the common information and informing the nonsingular random matrix R to other one of the communication apparatuses through the public communication path,
the first communication apparatus and the second communication apparatus using the nonsingular random matrix R to create the cryptographic key.

### Claim 7 (depends on 1)

The quantum key distribution method according to claim 1, wherein the check matrix creation step includes creating a mapping F to map an n-dimensional vector to an m-dimensional vector (m≦n−k), the mapping F being one in which the number of elements of a reverse image (F·G)−1(v) in a composition mapping F·G of the mapping F and the creation matrix G satisfying “HG=0” is independent of an arbitrary m-dimensional vector v and is constant(2n−k−m), and
the cryptographic key creation step includes discarding the part of pieces of the common information by the mapping F.

### Claim 8 (depends on 7)

The quantum key distribution method according to claim 7, wherein the cryptographic key creation step includes:
one of the communication apparatuses, out of the first communication apparatus and the second communication apparatus, creating a nonsingular random matrix R((n−k)×(n−k)) to act on the cryptographic key after discarding the part of pieces of the common information and informing the nonsingular random matrix R to other one of the communication apparatuses through a public communication path,
the first communication apparatus and the second communication apparatus using the nonsingular random matrix R to create the cryptographic key.

### Claim 9

A communication apparatus on transmission side that transmits photons onto a quantum communication path, comprising:
a check matrix creation unit that creates a parity check matrix H(n×k) identical to a communication apparatus on reception side;
a transmission unit that generates a random number sequence (transmission data), randomly determines a predetermined transmission code (base), transmits the photon onto the quantum communication path while the photon is in a quantum state specified by a combination of the transmission data and the transmission code, decides whether the measuring has been performed with an appropriate measuring apparatus in the communication apparatus on the reception side, saves the transmission data of n bits if the measuring has been performed with the appropriate measuring apparatus, and discards other pieces of the transmission data;
an error correction information notifying unit that notifies the communication apparatus on the reception side of error correction information of k bits based on the parity check matrix H and the transmission data of n bits through a public communication path; and
a cryptographic key creation unit that discards a part (k) of pieces of the common information after error correction according to public error correction information, creates a cryptographic key using information that has remained after discarding, wherein the amount of information remaining is n−k bits, and sets the cryptographic key as a common key which is shared with the communication apparatus on the reception side.

### Claim 10 (depends on 9)

The communication apparatus according to claim 9, wherein the check matrix creation unit uses finite affine geometry as a basic matrix, searches optimum row and column weight distributions of the parity check matrix by performing optimization of Gaussian approximation;
divides randomly the row and column weights of the finite affine geometry based on the optimum weight distribution by a predetermined procedure; and
creates the parity check matrix H of a low-density parity check code in which both the row and column weights or one of the row and column weights is not uniform.

### Claim 11 (depends on 10)

The communication apparatus according to claim 10, wherein the cryptographic key creation unit performs random permutation to the column of the parity check matrix H, selects specific “1” in the first column of finite affine geometry AG(2,2S) of a creation element of the parity check matrix H, exchanges a position of “1” through the public communication path, specifies the position (column) after the division corresponding to “1” from the parity check matrix after the random permutation and the position (column) after the division corresponding to “1” in each cyclically shifted column, and discards the part of pieces of the common information corresponding to the specified position (column).

### Claim 12 (depends on 11)

The communication apparatus according to claim 11, wherein the cryptographic key creation unit uses a nonsingular random matrix R((n−k)×(n−k)) as the cryptographic key after discarding the part of pieces of the common information.

### Claim 13 (depends on 9)

The communication apparatus according to claim 9, wherein the check matrix creation unit further creates an inverse matrix G−1(n×(n−k)), which satisfies G−1·G=I (unit matrix), from a creation matrix G((n−k)×n) satisfying “HG=0;” and
the cryptographic key creation unit discards the part of pieces of the common information by the inverse matrix G−1.

### Claim 14 (depends on 13)

The communication apparatus according to claim 13, wherein the cryptographic key creation unit uses a nonsingular random matrix R((n−k)×(n−k)) as the cryptographic key after discarding a part of pieces of the common information.

### Claim 15 (depends on 9)

The communication apparatus according to claim 9, wherein the check matrix creation unit further creates a mapping F to map an n-dimensional vector to an m-dimensional vector (m≦n−k), the mapping F being one in which the number of elements of a reverse image (F·G)−1(v) in a composition mapping F·G of the mapping F and the creation matrix G satisfying “HG=0” is independent of an arbitrary m-dimensional vector v and is constant(2n−k−m); and
the cryptographic key creation unit discards the part of pieces of the common information by the mapping F.

### Claim 16 (depends on 15)

The communication apparatus according to claim 15, wherein the cryptographic key creation unit uses a nonsingular random matrix R((n−k)×(n−k)) as the cryptographic key after discarding the part of pieces of the common information.

### Claim 17

A communication apparatus on reception side that measures photons on a quantum communication path, comprising:
a check matrix creation unit that creates a parity check matrix H(n×k) identical to a communication apparatus on transmission side;
a receiving unit that randomly determines a predetermined reception code (base), measures the photons on the quantum communication path, reproduces reception data specified by a combination of the reception code and measurement result, decides whether the measuring has been performed with an appropriate measuring apparatus, saves the reception data of n bits if the measuring has been performed with the appropriate measuring apparatus, and discards other pieces of the reception data;
an error correction unit that corrects the error of reception data based on error correction information of k bits received through a public communication path, the parity check matrix H, and the reception data of n bits; and
a cryptographic key creation unit that discards a part of pieces of the common information after error correction according to public error correction information, creates a cryptographic key using information that has remained after discarding, wherein the amount of information remaining is n−k bits, and sets the cryptographic key as a common key which is shared with the communication apparatus on the transmission side.

### Claim 18 (depends on 17)

The communication apparatus according to claim 17, wherein the check matrix creation unit uses finite affine geometry as a basic matrix, searches optimum row and column weight distributions of the parity check matrix by performing optimization of Gaussian approximation;
divides randomly the row and column weights of the finite affine geometry based on the optimum weight distribution by a predetermined procedure; and
creates the parity check matrix H of a low-density parity check code in which both the row and column weights or one of the row and column weights is not uniform.

### Claim 19 (depends on 18)

The communication apparatus according to claim 18, wherein the cryptographic key creation unit performs random permutation to the column of the parity check matrix H, selects specific “1” in the first column of finite affine geometry AG(2,2S) of a creation element of the parity check matrix H, exchanges a position of “1” through the public communication path, specifies the position (column) after the division corresponding to “1” from the parity check matrix after the random permutation and the position (column) after the division corresponding to “1” in each cyclically shifted column, and discards a part of pieces of the common information corresponding to the specified position (column).

### Claim 20 (depends on 19)

The communication apparatus according to claim 19, wherein the cryptographic key creation unit uses a nonsingular random matrix R((n−k)×(n−k)) as the cryptographic key after discarding the part of pieces of the common information.

### Claim 21 (depends on 17)

The communication apparatus according to claim 17, wherein the check matrix creation unit further creates an inverse matrix G−1(n×(n−k)), which satisfies G−1·G=I (unit matrix), from a creation matrix G((n−k)×n) satisfying “HG=0;” and
the cryptographic key creation unit discards a part of pieces of the common information by the inverse matrix G−1.

### Claim 22 (depends on 21)

The communication apparatus according to claim 21, wherein the cryptographic key creation unit uses a nonsingular random matrix R((n−k)×(n−k)) as the cryptographic key after discarding a part of pieces of the common information.

### Claim 23 (depends on 17)

The communication apparatus according to claim 17, wherein the check matrix creation unit further creates a mapping F to map an n-dimensional vector to an m-dimensional vector (m≦n−k), the mapping F being one in which the number of elements of a reverse image (F·G)−1(v) in a composition mapping F·G of the mapping F and the creation matrix G satisfying “HG=0” is independent of an arbitrary m-dimensional vector v and is constant(2n−k−m); and
the cryptographic key creation unit discards the part of pieces of the common information by the mapping F.

### Claim 24 (depends on 23)

The communication apparatus according to claim 23, wherein the cryptographic key creation unit uses a nonsingular random matrix R((n−k)×(n−k)) as the cryptographic key after discarding the part of pieces of the common information.