JP4459526B2 - Quantum key distribution method and communication apparatus - Google Patents

Description

【００３５】
つぎに、パリティ検査行列生成部１０では、上記決定したパラメータｕ，ｕ＋１，ｂ_u，ｂ_u+1によって（上記行の分割処理によって）更新された行の重みの比率ρ_u´，ρ_u+1´を（３）式により求める（ステップＳ２５）。
【００３６】
【数２】

【００３７】
つぎに、パリティ検査行列生成部１０では、ガウス近似法による最適化を用いて、さらに上記で求めたｕ，ｕ＋１，ρ_u´，ρ_u+1´を固定のパラメータとして、暫定的に、列の重み配分λ（γ_i）を求める（ステップＳ２６）。なお、重みγ_iはγ_i≧２の整数であり、λ（γ_i）は列における重みγ_iの割合を表す。また、列数が１以下となる重み（λ（γ_i）≦γ_i／ｗ_t，ｉは正の整数）を候補から削除する。ただし、ｗ_tはＡＧ（２，２^s）に含まれる１の総数を表す。
【００３８】
つぎに、上記で求めた重み配分を満たし、かつ下記（４）式を満たす、列の重み候補のセット｛γ₁，γ₂，…γ_l（γ_l≦２^s）｝を選択する（ステップＳ２７）。そして、下記の（４）式を満たさない列の重みγ_iが存在する場合には、その列の重みを候補から削除する。
【００３９】
【数３】

【００４０】
なお、各ａは、列の重み２^sを構成するための｛γ₁，γ₂，…γ_l｝に対する非負の整数となる係数を表し、ｉ，ｊは正の整数であり、γ_iは列の重みを表し、γ_lは列の最大重みを表す。
【００４１】
つぎに、パリティ検査行列生成部１０では、ガウス近似法による最適化を用いて、さらに上記で求めたｕ，ｕ＋１，ρ_u´，ρ_u+1´と｛γ₁，γ₂，…γ_l｝を固定パラメータとして、列の重み配分λ（γ_i）と行の重み配分ρ_uを求める（ステップＳ２８）。
【００４２】
つぎに、パリティ検査行列生成部１０では、分割処理を行う前に、列の重み配分λ（γ_i）と行の重み配分ρ_uを調整する（ステップＳ２９）。なお、調整後の各重みの配分は、可能な限りガウス近似法で求めた値に近い値にする。図５は、ステップＳ２９における最終的な列の重み配分λ（γ_i）と行の重み配分ρ_uを示す図である。
【００４３】
最後に、パリティ検査行列生成部１０では、有限アフィン幾何における行および列を分割して（ステップＳ３０）、ｎ×ｋのパリティ検査行列Ｈを生成する。本発明における有限アフィン幾何符号の分割処理は、規則的に分割するのではなく、各行または各列から「１」の番号をランダムに抽出する（後述するランダム分割の具体例を参照）。なお、この抽出処理は、ランダム性が保持されるのであればどのような方法を用いてもよい。
【００４４】
具体的にいうと、ＥＧ（２，２⁵）における１列中の「１」の行番号が、
Ｂ_l（ｘ）＝｛1 32 114 136 149 223 260 382 402 438 467 507 574 579 588 622 634 637 638 676 717 728 790 851 861 879 947 954 971 977 979 998｝
の場合、分割後の行列における１〜４列目Ｒ_m（ｎ）は、Ｂ_l（ｘ）から「１」の番号がランダムに抽出され、たとえば、
Ｒ₁（ｎ）＝｛1 114 574 637 851 879 977 979｝
Ｒ₂（ｎ）＝｛32 136 402 467 588 728 861 971｝
Ｒ₃（ｎ）＝｛149 260 382 438 579 638 717 998｝
Ｒ₄（ｎ）＝｛223 507 622 634 676 790 947 954｝
となる。
【００４５】
ここで、上記ランダム分割の一例、すなわち、上記「乱数系列のラテン方陣を用いた分割方法」を詳細に説明する。ここでは、ランダム分割を行う場合のランダム系列を容易かつ確定的に生成する。この方法による利点は、送信側と受信側が同じランダム系列を生成できることにある。
【００４６】
（１）基本のランダム系列を作成する。ここでは、有限アフィン幾何ＡＧ（２，２^s）を用い、ＰをＰ≧２^sを満たす最小の素数とした場合の、基本のランダム系列Ｃ（ｉ）を（５）式にしたがって作成する。
Ｃ（１）＝１
Ｃ（ｉ＋１）＝Ｇ₀×Ｃ（ｉ） ｍｏｄ Ｐ …（５）
なお、ｉ＝０，１，…，Ｐ−２とし、Ｇ₀はガロア体ＧＦ（Ｐ）の原始元である。また、系列長が２^sとなるように、２^sより大きい数をＣ（ｉ）の中から削除し、削除後のＣ（ｉ）を基本のランダム系列とする。
【００４７】
（２）基本のランダム系列Ｃ（ｉ）を一定間隔で読み出すためにスキップ間隔Ｓ（ｊ）を以下の（６）式のように定義する。
Ｓ（ｊ）＝ｊ ｊ＝１，２，…，２^s …（６）
【００４８】
（３）以下の（７）式で置換パターンＬＢ_j（ｉ）を作成する。
ＬＢ_j（ｉ）＝（（Ｓ（ｊ）×ｉ） ｍｏｄ Ｐ）＋１
ｊ＝１，２，…，２^s
ｉ＝１，２，…，Ｐ−１ …（７）
なお、ＬＢ_j（ｉ）も２^sより大きい数字は削除する。
【００４９】
（４）ｑ列ｉ行でｊ番目のラテン方陣行列Ｌ_jq（ｉ）を以下の（８）式で算出する。
Ｌ_jq（ｉ）＝ＬＢ_j（（（ｑ＋ｉ−２） ｍｏｄ ２^s）＋１）
ｊ＝１，２，…，２^s
ｉ＝１，２，…，２^s
ｑ＝１，２，…，２^s …（８）
【００５０】
（５）ラテン方陣行列Ｌ_jq（ｉ）にしたがって列と行を分割する。列の分割では、ｇ₀，ｇ₀，…，ｇ_n-1をパリティ検査行列Ｈの列ベクトルとし、ｇ_c´（ｋ）をｇ_c，ｃ＝０，１，…，ｎ−１の列の中のｋ番目の「１」とする。また、ｇ_cの中の「１」の位置の集合をＧ_cとする（（９）式参照）。
Ｇ_c＝｛ｇ_c´（ｋ），ｋ＝１，２，…，２^s｝ …（９）
たとえば、ＡＧ（２，２³）のｃ＝１番目の列の「１」の行番号は、Ｇ₁＝｛1 3 8 20 23 24 34 58｝となる。そして、このｃ列目の列ベクトルをｇ_c´（ｋ）で表現すると、（１０）式のように表すことができる。
ｇ_c´（１）＝（（ｃ−１）＋１）ｍｏｄ（２^2s−１）
ｇ_c´（２）＝（ｇ_c´（１）＋２）ｍｏｄ（２^2s−１）
ｇ_c´（３）＝（ｇ_c´（２）＋５）ｍｏｄ（２^2s−１）
ｇ_c´（４）＝（ｇ_c´（３）＋１２）ｍｏｄ（２^2s−１）
ｇ_c´（５）＝（ｇ_c´（４）＋３）ｍｏｄ（２^2s−１）
ｇ_c´（６）＝（ｇ_c´（５）＋１）ｍｏｄ（２^2s−１）
ｇ_c´（７）＝（ｇ_c´（６）＋１０）ｍｏｄ（２^2s−１）
ｇ_c´（８）＝（ｇ_c´（７）＋２４）ｍｏｄ（２^2s−１） …（１０）
【００５１】
ここで、パリティ検査行列Ｈの各列ｇ_cを、上記（４）式を満たす列の次数と係数に基づいて、新しい列ｇ_c,eに分割する。そして、ｇ_c,e´（ｒ）を新しい列ｇ_c,eの中のｒ行目の「１」とする。また、ｇ_c,eの中の「１」の位置の集合をＧ_c,eとする（（１１）式参照）。
Ｇ_c,e＝｛ｇ_c,e´（ｒ），ｒ＝１，２，…｝ …（１１）
【００５２】
そして、ラテン方陣行列群を用いて、下記（１２）式にしたがって分割するエッジの選択を行う。なお、ａ_t,1，ａ_t,2，…，ａ_t,lとγ₁，γ₂，…，γ_lは、上記式(４)を満たす係数と次数である。また、ｔは（４）式の係数行列の行番号を示している。また、ｔ行目の式で分割する有限アフィン平面の列数をｎ_tとし、係数行列の行番号の最大値をｔ_mとすると、ｔは（１３）式で表すことができる。
【００５３】
【数４】

【００５４】
【数５】

【００５５】
つぎに、上記（１）〜（４）の分割処理を、具体例を挙げて説明する。例として、ＡＧ（２，２³）のｃ＝１６番目の列の「１」の行番号をＧ₁₆＝｛10 16 18 23 35 38 39 49｝と定義する。図６は、ランダム系列のラテン方陣行列による分割手順を示す図である。図示のラテン方陣行列Ｌ_jq（ｉ）の結果を用いて手順（５）を実行すると、新しい列ｇ_16,eの中の「１」は（１４）式のように表すことができる。
ｇ_16,1´（１）＝ｇ₁₆´（Ｌ_2,8（１））＝ｇ₁₆´（３）＝１８
ｇ_16,1´（２）＝ｇ₁₆´（Ｌ_2,8（２））＝ｇ₁₆´（２）＝１６
ｇ_16,2´（１）＝ｇ₁₆´（Ｌ_2,8（３））＝ｇ₁₆´（８）＝４９
ｇ_16,2´（２）＝ｇ₁₆´（Ｌ_2,8（４））＝ｇ₁₆´（７）＝３９
ｇ_16,3´（１）＝ｇ₁₆´（Ｌ_2,8（５））＝ｇ₁₆´（６）＝３８
ｇ_16,3´（２）＝ｇ₁₆´（Ｌ_2,8（６））＝ｇ₁₆´（１）＝１０
ｇ_16,4´（１）＝ｇ₁₆´（Ｌ_2,8（７））＝ｇ₁₆´（４）＝２３
ｇ_16,4´（２）＝ｇ₁₆´（Ｌ_2,8（８））＝ｇ₁₆´（５）＝３５ …（１４）
【００５６】
その結果、１６番目の列は以下のように分割される。
Ｇ_16,1＝｛18 16｝
Ｇ_16,2＝｛49 39｝
Ｇ_16,3＝｛38 10｝
Ｇ_16,4＝｛23 35｝
【００５７】
このように、本実施の形態では、上記有限アフィン幾何に基づく「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」の構成法（図２、ステップＳ１）を実行することによって、確定的で特性が安定した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列Ｈ（ｎ×ｋ）を生成することができる。
【００５８】
上記のように、パリティ検査行列Ｈ，生成行列Ｇ，Ｇ^-1（Ｇ^-1・Ｇ＝Ｉ：単位行列）を生成後、つぎに、送信側の通信装置では、乱数発生部１１が、乱数列ｍ_a（１，０の列：送信データ）を発生し、さらに送信コード（＋：水平垂直方向に偏光された光を識別可能な測定器に対応したコード，×：斜め方向に偏光された光を識別可能な測定器に対応したコード）をランダムに決定する（ステップＳ２）。一方、受信側の装置では、乱数発生部３１が、受信コード（＋：水平垂直方向に偏光された光を識別可能な測定器に対応したコード，×：斜め方向に偏光された光を識別可能な測定器に対応したコード）をランダムに決定する（ステップＳ１２）。
【００５９】
つぎに、送信側の通信装置では、光子生成部１２が、上記乱数列ｍ_aと送信コードの組み合わせで自動的に決まる偏光方向で光子を送信する（ステップＳ３）。たとえば、０と＋の組み合わせで水平方向に偏光された光を、１と＋の組み合わせで垂直方向に偏光された光を、０と×の組み合わせで４５°方向に偏光された光を、１と×の組み合わせで１３５°方向に偏光された光を、量子通信路にそれぞれ送信する（送信信号）。
【００６０】
光子生成部１２にて生成した光信号を受け取った受信側の通信装置の光子受信部３２では、量子通信路上の光を測定する（受信信号）。そして、受信コードと受信信号の組み合わせによって自動的に決まる受信データｍ_bを得る（ステップＳ１３）。ここでは、受信データｍ_bとして、水平方向に偏光された光と＋の組み合わせで０を、垂直方向に偏光された光と＋の組み合わせで１を、４５°方向に偏光された光と×の組み合わせで０を、１３５°方向に偏光された光と×の組み合わせで０を、それぞれ得る。なお、受信データｍ_bは、確率情報付きの硬判定値とする。
【００６１】
つぎに、受信側の通信装置では、上記測定が正しい測定器で行われたものかどうかを調べるために、乱数発生部３１が、受信コードを、公開通信路を介して送信側の通信装置に対して送信する（ステップＳ１３）。受信コードを受け取った送信側の通信装置では、上記測定が正しい測定器で行われたものかどうかを調べ、その結果を、公開通信路を介して受信側の通信装置に対して送信する（ステップＳ３）。そして、受信側の通信装置および送信側の通信装置では、正しい測定器で受信した受信信号に対応するデータだけを残し、その他を捨てる（ステップＳ３，Ｓ１３）。その後、残ったデータをメモリ等に保存し、その先頭から順にｎビットを読み出し、これを、正式な送信データｍ_Aと受信データｍ_B（ｍ_Bは伝送路上で雑音等の影響を受けたｍ_A：ｍ_B＝ｍ_A＋ｅ（雑音等））とする。すなわち、ここでは、必要に応じてつぎのｎビットを読み出して、送信データｍ_Aと受信データｍ_Bを生成する。本実施の形態では、残ったデータのビット位置が、送信側の通信装置と受信側の通信装置との間で共有できている。なお、ｍ_Bは、上記ｍ_b同様、確率情報付きの硬判定値である。
【００６２】
つぎに、送信側の通信装置では、シンドローム生成部１４が、パリティ検査行列Ｈ（ｎ×ｋ）と送信データｍ_Aを用いてｍ_AのシンドロームＳ_A＝Ｈｍ_Aを計算し、その結果を、公開通信路通信部１３，公開通信路を介して受信側の通信装置に通知する（ステップＳ４）。この段階で、ｍ_AのシンドロームＳ_A（ｋビット分の情報）は盗聴者に知られる可能性がある。一方、受信側の通信装置では、公開通信路通信部３４にてｍ_AのシンドロームＳ_Aを受信し、それをシンドローム復号部３３に通知する（ステップＳ１４）。
【００６３】
シンドローム復号部３３では、本実施の形態のシンドローム復号法を用いて、雑音等による確率情報付きの硬判定値ｍ_Bの誤りを訂正することによって元の送信データｍ_Aを推定する（ステップＳ１５）。ここでは、「Ｓ_A＝Ｈｍ_C」を満たすｍ_Cを確率情報付きの硬判定値ｍ_Bから推定し、その推定結果ｍ_Cを共有情報ｍ_Aとする。以下、本実施の形態のシンドローム復号法を詳細に説明する。
【００６４】
図７は、本実施の形態のシンドローム復号法を示すフローチャートである。なお、上記のように、２元のｎ（列）×ｋ（行）の検査行列Ｈを想定した場合、ｉ列（１≦ｉ≦ｎ）ｊ行（１≦ｊ≦ｋ）目の要素をＨ_ijと表記する。また、受信データｍ_Bをｍ_B＝（ｍ_B1，ｍ_B2，…，ｍ_Bn）とし、推定語（硬判定値）ｍ_Cをｍ_C＝（ｍ_C1，ｍ_C2，…，ｍ_Cn）とする。また、ｍ_AのシンドロームＳ_AをＳ_A＝（Ｓ_A1，Ｓ_A2，…，Ｓ_Ak）、また、通信路としては、条件付確率Ｐ（ｍ_B｜ｍ_C＝ｍ_A）で記述される無記憶通信路を想定する。
【００６５】
まず、シンドローム復号部３３では、初期設定として、Ｈ_ij＝１を満たす全ての列と行の組み合わせ（ｉ，ｊ）の事前値をｑ_ij（０）＝１／２，ｑ_ij（１）＝１／２とする。ｑ_ij（０）はＨ_ijが「０」である確率を表し、ｑ_ij（１）はＨ_ijが「１」である確率を表す。そして、復号の反復回数を示すカウンタ値をｌ＝１（イテレーション：１回）とし、さらに、最大反復回数ｌ_maxを設定する（ステップＳ３１）。
【００６６】
つぎに、シンドローム復号部３３では、ｊ＝１，２，…，ｋの順に、Ｈ_ij＝１を満たす全ての列と行の組み合わせ（ｉ，ｊ）について外部値ｒ_ij（０）とｒ_ij（１）を更新する（ステップＳ３２）。本実施の形態においては、たとえば、ｊ（１≦ｊ≦ｋ）番目のシンドロームＳ_Ajが「０」の場合、更新式（１５），更新式（１６）を用いて外部値ｒ_ij（０）とｒ_ij（１）を更新する。
【００６７】
【数６】

【００６８】
【数７】

【００６９】
一方、ｊ（１≦ｊ≦ｋ）番目のシンドロームＳ_Ajが「１」の場合は、更新式（１７），更新式（１８）を用いて外部値ｒ_ij（０）とｒ_ij（１）を更新する。
【００７０】
【数８】

【００７１】
【数９】

【００７２】
なお、上記Ｋは、「ｒ_ij（０）＋ｒ_ij（１）＝１」が成り立つように規定された値（正規化するための値）とする。また、上記Ｐ（ｍ_B｜ｍ_C）は、条件付確率、すなわち、推定語ｍ_Cが「０」または「１」の場合における受信データｍ_Bの確率を表す。また、上記部分集合Ａ（ｉ）は、検査行列Ｈのｉ列目において「１」が立っている行インデックスの集合を表し、部分集合Ｂ（ｊ）は、検査行列Ｈのｊ行目において「１」が立っている列インデックスの集合を表す。
【００７３】
上記更新処理を具体的に記載すると、たとえば、Ｓ_Aj＝０，ｊ＝１，かつＨ_i1＝１を満たす全ての列と行の組み合わせが（ｉ，１）＝（３，１）（４，１）（５，１）の場合、式（１５），式（１６）が適用され、外部値ｒ₃₁（０），ｒ₃₁（１）が式（１９），式（２０）のように更新される。すなわち、Ｈ₃₁以外のＨ₄₁，Ｈ₅₁を用いて、外部値ｒ₃₁（０），ｒ₃₁（１）を更新する。ここでは、検査行列Ｈの３列１行目が「０」である確率と「１」である確率をそれぞれ求めている。
【００７４】
【数１０】

【００７５】
【数１１】

【００７６】
つぎに、シンドローム復号部３３では、ｉ＝１，２，…，ｎの順に、Ｈ_ij＝１を満たす全ての列と行の組み合わせ（ｉ，ｊ）について事前値ｑ_ij（０）とｑ_ij（１）を更新する（ステップＳ３３）。この更新処理は、式（２１），式（２２）にて表すことができる。
【００７７】
【数１２】

【００７８】
【数１３】

【００７９】
なお、上記Ｋ´は、「ｑ_ij（０）＋ｑ_ij（１）＝１」が成り立つように規定された値（正規化するための値）とする。
【００８０】
上記更新処理を具体的に記載すると、たとえば、ｉ＝３，かつＨ_1j＝１を満たす全ての列と行の組み合わせが（３，ｊ）＝（３，１）（３，２）（３，３）の場合、式（２１），式（２２）が適用され、事前値ｑ₃₁（０），ｑ₃₁（１）が式（２３），式（２４）のように更新される。すなわち、Ｈ₃₁以外のＨ₃₂，Ｈ₃₃を用いて、事前値ｑ₃₁（０），ｑ₃₁（１）を更新する。
【００８１】
【数１４】

【００８２】
【数１５】

【００８３】
つぎに、シンドローム復号部３３では、事後確率（条件付確率×事前値）Ｑ_i（０），Ｑ_i（１）を求め、この事後確率から一時推定語ｍ_C´＝（ｍ_C1´，ｍ_C2´，…，ｍ_Cn´）を求める（ステップＳ３４）。すなわち、式（２５），式（２６）の計算結果に基づいて、式（２７）における一時推定語を得る。ここでは、イテレーション１回毎に判定処理を行う。
【００８４】
【数１６】

【００８５】
【数１７】

【００８６】
【数１８】

【００８７】
なお、上記Ｋ´´は、「Ｑ_i（０）＋Ｑ_i（１）＝１」が成り立つように規定された値（正規化するための値）とする。また、条件付確率Ｐ（ｍ_B｜ｍ_C＝０）は、式（２８），式（２９）のように定義され、ｐはビット誤り率を表す。
【００８８】
【数１９】

【００８９】
【数２０】

【００９０】
つぎに、シンドローム復号部３３では、一時推定語ｍ_C´が送信データｍ_Aといえるかどうかを検査する（ステップＳ３５）。ここでは、たとえば、ｍ_C´＝（ｍ_C1´，ｍ_C2´，…，ｍ_Cn´）が「ｍ_C´×Ｈ^T＝Ｓ _A 」という条件を満たしていれば（ステップＳ３６、Ｙｅｓ）、当該ｍ_C´を推定語ｍ_C＝（ｍ_C1，ｍ_C2，…，ｍ_Cn）として、すなわち、元の送信データｍ_A＝（ｍ_A1，ｍ_A2，…，ｍ_An）として出力し、このアルゴリズムを終了する。
【００９１】
一方、上記条件を満たさない場合で、かつｌ＜ｌ_maxの場合は（ステップＳ３６、Ｎｏ）、カウンタ値ｌをインクリメントし、ステップＳ３２の処理を上記更新された値を用いて再度実行する。以降、上記条件を満たすまで（ｌ＜ｌ_maxの範囲で）、更新された値を用いてステップＳ３２〜Ｓ３６の処理を繰り返し実行する。
【００９２】
このように、上記本実施の形態の量子鍵配送で採用するシンドローム復号法においては、従来技術にて記載した誤り訂正で発生していた「エラービットを特定するための膨大な回数のパリティのやりとり（二分探索）」を排除し、極めて高い特性（誤り訂正能力）をもつＬＤＰＣ符号用のパリティ検査行列を用いて誤り訂正を行うこととした。これにより、短時間で伝送路上におけるデータ誤りを訂正しつつ、高度に安全性の保証された共通鍵を生成することができる。
【００９３】
また、本実施の形態においては、受信データｍ_Bおよびｍ_bを確率情報付きの硬判定値としたが、これに限らず、たとえば、軟判定値としてもよい。
【００９４】
最後に、受信側の通信装置では、共有鍵生成部３５が、公開された誤り訂正情報（盗聴された可能性のある上記ｋビット分の情報：Ｓ_A）に応じて共有情報（ｍ_A）の一部を捨てて、ｎ−ｋビット分の情報量を備えた暗号鍵ｒを生成する（ステップＳ１６）。すなわち、共有鍵生成部３５では、先に計算しておいたＧ^-1（ｎ×（ｎ−ｋ））を用いて下記（３０）式により暗号鍵ｒを生成する。受信側の通信装置は、この暗号鍵ｒを送信側の通信装置との共有鍵とする。
ｒ＝Ｇ^-1ｍ_A …（３０）
【００９５】
一方、送信側の通信装置においても、共有鍵生成部１５が、公開された誤り訂正情報（盗聴された可能性のある上記ｋビット分の情報：Ｓ_A）に応じて共有情報（ｍ_A）の一部を捨てて、ｎ−ｋビット分の情報量を備えた暗号鍵ｒを生成する（ステップＳ５）。すなわち、共有鍵生成部１５では、先に計算しておいたＧ^-1（ｎ×（ｎ−ｋ））を用いて上記（３０）式により暗号鍵ｒを生成する（ステップＳ５）。送信側の通信装置は、この暗号鍵ｒを受信側の通信装置との共有鍵とする。
【００９６】
なお、本実施の形態においては、さらに、正則なランダム行列Ｒを用いて上記共有鍵を並べ替える構成としてもよい。これにより、秘匿性を増強させることができる。具体的には、まず、送信側の通信装置が、正則なランダム行列Ｒ（（ｎ−ｋ）×（ｎ−ｋ））を生成し、さらに、当該Ｒを、公開通信路を介して受信側の通信装置に通知する。なお、この処理は、受信側の通信装置で行うこととしてもよい。その後、送信側および受信側の通信装置が、先に計算しておいたＧ^-1（ｎ×（ｎ−ｋ））とランダム行列Ｒを用いて下記（３１）式により暗号鍵ｒを生成する。
ｒ＝ＲＧ^-1ｍ_A …（３１）
【００９７】
このように、本実施の形態おいては、確定的で特性が安定した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用のパリティ検査行列を用いて共有情報のデータ誤りを訂正し、公開された誤り訂正情報に応じて共有情報の一部を捨てる構成とした。これにより、エラービットを特定／訂正するための膨大な回数のパリティのやりとりがなくなり、誤り訂正情報を送信するだけで誤り訂正制御が行われるため、誤り訂正処理にかかる時間を大幅に短縮できる。また、公開された情報に応じて共有情報の一部を捨てているので、高度に安全性の保証された共通鍵を生成することができる。
【００９８】
なお、本実施の形態では、ＨＧ＝０を満たす生成行列Ｇ（（ｎ−ｋ）×ｎ）から、Ｇ^-1・Ｇ＝Ｉ（単位行列）となる逆行列Ｇ^-1（ｎ×（ｎ−ｋ））を生成し、当該逆行列Ｇ^-1を用いて共有情報（ｎ）の一部（ｋ）を捨てて、ｎ−ｋビット分の情報量を備えた暗号鍵ｒを生成することとしたが、これに限らず、共有情報（ｎ）の一部を捨てて、ｍ（ｍ≦ｎ−ｋ）ビット分の情報量を備えた暗号鍵ｒを生成することとしてもよい。具体的にいうと、ｎ次元ベクトルをｍ次元ベクトルに写す写像Ｆ（・）を想定する。Ｆ（・）は、共有鍵の安全性を保証するために、「任意のｍ次元ベクトルｖに対して、写像Ｆと生成行列Ｇの合成写像Ｆ・Ｇにおける逆像（Ｆ・Ｇ）^-1（ｖ）の元の個数がｖによらず一定（２^n-k-m）である」、という条件を満たす必要がある。このとき、共有鍵ｒは、ｒ＝Ｆ（ｍ_A）となる。
【００９９】
また、本実施の形態においては、ステップＳ５，Ｓ１６の処理で、生成行列Ｇ^-1を用いずに、パリティ検査行列Ｈの特性を用いて共有情報の一部を捨てる構成としてもよい。具体的には、まず、共有鍵生成部１５，３５が、上記ステップＳ１，Ｓ１１で生成したパリティ検査行列Ｈの列に対してランダム置換を行う。そして、通信装置間で捨てるビットに関する情報を、公開通信路を介して交換する。たとえば、元の有限アフィン幾何ＡＧ（２，２^s）の１列目の中から特定の「１」を選び、その位置を、公開通信路を介して交換する。その後、共有鍵生成部１５，３５が、上記置換後のパリティ検査行列から上記「１」に対応する分割後の位置、および巡回シフトされた各列における上記「１」に対応する分割後の位置を特定し、その特定した位置に対応する共有情報ｍ_A内のビットを捨てて、残りのデータを暗号鍵ｒとする。これにより、複雑な生成行列Ｇ，Ｇ^-1の演算処理を削除することができる。
【０１００】
【発明の効果】
以上、説明したとおり、本発明によれば、量子暗号システムを構成する通信装置が、従来技術における誤り訂正で発生していた「エラービットを特定するための膨大な回数のパリティのやりとり（二分探索）」を排除し、極めて高い特性をもつＬＤＰＣ符号用のパリティ検査行列を用いて誤り訂正を行うこととした（上記シンドローム復号法に相当）。これにより、短時間で伝送路上におけるデータ誤りを訂正しつつ、高度に安全性の保証された共通鍵を生成することができる、という効果を奏する。
【図面の簡単な説明】
【図１】 本発明にかかる量子暗号システムの構成を示す図である。
【図２】 量子鍵配送を示すフローチャートである。
【図３】 有限アフィン幾何に基づく「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」の構成法を示すフローチャートである。
【図４】 有限アフィン幾何符号ＡＧ（２，２²）のマトリクスを示す図である。
【図５】 最終的な列の重み配分λ（γ_i）と行の重み配分ρ_uを示す図である。
【図６】 ランダム系列のラテン方陣行列による分割手順を示す図である。
【図７】 シンドローム復号法を示すフローチャートである。
【図８】 従来の量子鍵配送の概要を示す図である。
【符号の説明】
１，３ 暗号鍵生成部、２，４ 通信部、１０，３０ パリティ検査行列生成部、１１，３１ 乱数発生部、１２ 光子生成部、１３，３４ 公開通信路通信部、１４ シンドローム生成部、１５，３５ 共有鍵生成部、２１，４２ 暗号化部、２２，４１ 送受信部、３２ 光子受信部、３３ シンドローム復号部。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a quantum key distribution method capable of generating a highly secure common key, and in particular, a quantum key distribution method capable of correcting a data error using an error correction code and The present invention relates to a communication device capable of realizing quantum key distribution.
[0002]
[Prior art]
Hereinafter, a conventional quantum cryptography system will be described. In recent years, optical communication is widely used as a high-speed and large-capacity communication technology. In such an optical communication system, communication is performed by turning on / off light, and a large number of photons are transmitted when turned on. Therefore, it is not a communication system in which the quantum effect appears directly.
[0003]
On the other hand, in a quantum cryptography system, photons are used as a communication medium, and 1-bit information is transmitted by one photon so that a quantum effect such as an uncertainty principle occurs. At this time, if the eavesdropper appropriately selects a base without knowing the quantum state such as polarization and phase and measures a photon, the quantum state changes. Therefore, on the receiving side, it is possible to recognize whether or not the transmission data has been wiretapped by confirming the change in the quantum state of the photon.
[0004]
FIG. 8 is a diagram showing an outline of conventional quantum key distribution using polarized light. For example, a measuring instrument capable of discriminating horizontal and vertical polarization correctly discriminates between light polarized in the horizontal direction (0 °) and light polarized in the vertical direction (90 °) on the quantum communication path. On the other hand, a measuring device capable of discriminating polarized light in an oblique direction (45 °, 135 °) correctly identifies light polarized in the 45 ° direction and light polarized in the 135 ° direction on the quantum communication path.
[0005]
In this way, each measuring device can correctly recognize light polarized in a prescribed direction, but can identify light polarized in an oblique direction in the horizontal and vertical directions (0 °, 90 °), for example. When measured with a simple measuring instrument, light polarized in the horizontal and vertical directions is randomly identified with a probability of 50%. That is, when a measuring instrument that does not correspond to an identifiable polarization direction is used, even if the measurement result is analyzed, the polarized direction cannot be correctly identified.
[0006]
In the conventional quantum key distribution shown in FIG. 8, a key is shared between a sender and a receiver without being known to an eavesdropper by utilizing the uncertainty (randomness) (for example, Non-Patent Document 1). reference.). In addition, the sender and the receiver can use the public communication channel in addition to the quantum communication channel.
[0007]
Here, a key sharing procedure will be described. First, the sender generates a random number sequence (sequence of 1, 0: transmission data), and further transmits a transmission code (+: corresponds to a measuring device that can identify light polarized in the horizontal and vertical directions, x: in an oblique direction (Corresponding to a measuring device capable of discriminating polarized light) is determined at random. The combination of the random number sequence and the transmission code automatically determines the polarization direction of the transmitted light. Here, the light polarized in the horizontal direction by the combination of 0 and +, the light polarized in the vertical direction by the combination of 1 and +, the light polarized in the 45 ° direction by the combination of 0 and x, 1 The light polarized in the 135 ° direction by the combination of and x is transmitted to the quantum communication path (transmission signal).
[0008]
  Next, the receiver randomly determines a reception code (+: a measuring device that can discriminate light polarized in the horizontal and vertical directions, x: a measuring device that can discriminate light polarized in the oblique direction), and quantum The light on the communication path is measured (received signal). Then, received data is obtained by a combination of the received code and the received signal. Here, as received data, a combination of light polarized in the horizontal direction and + is 0, a combination of light polarized in the vertical direction and + is 1, and a combination of light polarized in the 45 ° direction and x is x. 0 with a combination of light polarized in the 135 ° direction and x1Respectively.
[0009]
Next, the receiver transmits the reception code to the sender via the public communication path in order to check whether or not the measurement is performed by the correct measuring device. The sender who has received the reception code checks whether or not the transmission is performed by a correct measuring device, and returns the result to the receiver via the public communication path.
[0010]
Next, the receiver leaves only the received data corresponding to the received signal received by the correct measuring instrument and discards the others. At this point, the remaining received data can be reliably shared between the sender and the receiver.
[0011]
Next, the sender and the receiver transmit a predetermined number of data selected from the shared data to the respective communication partners via the public communication path. Then, it confirms whether the received data matches the data it has. For example, if at least one of the confirmed data does not match, it is determined that there is an eavesdropper, the shared data is discarded, and the key sharing procedure is restarted from the beginning. On the other hand, if all the confirmed data matches, it is determined that there is no eavesdropper, the data used for confirmation is discarded, and the remaining shared data is used as a shared key between the sender and the receiver.
[0012]
On the other hand, as an application of the conventional quantum key distribution method, for example, there is a quantum key distribution method capable of correcting a data error on a transmission path (see, for example, Non-Patent Document 2).
[0013]
In this method, in order to detect a data error, the sender divides transmission data into a plurality of blocks and transmits the parity for each block on the public communication path. The receiver then checks the data error by comparing the parity for each block received via the public communication path with the parity of the corresponding block in the received data. At this time, when there are different parities, the receiver returns information indicating which blocks have different parities on the public communication path. Then, the transmitter further divides the corresponding block into a first half block and a second half block, and returns, for example, the first half parity on the public communication path (binary search). Thereafter, the sender and the receiver specify the position of the error bit by repeatedly executing the binary search, and the receiver finally corrects the bit.
[0014]
Further, the sender assumes that there is parity determined to be correct due to an even number of errors even though there is an error in the data, and rearranges the transmission data randomly (random replacement). Dividing into blocks, the error correction processing by the binary search is performed again. All the data errors are corrected by repeatedly executing this error correction process by random replacement.
[0015]
[Non-Patent Document 1]
Bennett, C. H. and Brassard, G .: Quantum Cryptography: Public Key Distribution and Coin Tossing, In Proceedings of IEEE Conference on Computers, System and Signal Processing, Bangalore, India, pp.175-179 (DEC.1984).
[Non-Patent Document 2]
Brassard, G. and Salvail, L. 1993 Secret-Key Reconciliation by Public Discussion, In Advances in Cryptology-EUROCRYPT'93, Lecture Notes in Computer Science 765, 410-423.
[0016]
[Problems to be solved by the invention]
However, the conventional quantum key distribution shown in FIG. 8 does not assume an error communication path, so if there is an error, the common data (common key) is discarded as if there is an eavesdropping action. There is a problem that the generation efficiency of the common key becomes very poor depending on the transmission path.
[0017]
In addition, in the quantum key distribution method capable of correcting data errors on the transmission path, a huge number of parity exchanges occur in order to specify error bits, and error correction processing by random replacement is performed a predetermined number of times. Therefore, there is a problem that a great deal of time is spent on error correction processing.
[0018]
The present invention has been made in view of the above, and generates a highly secure common key while correcting a data error on a transmission path using an error correction code having extremely high characteristics. The purpose is to obtain a quantum key distribution method capable of
[0019]
[Means for Solving the Problems]
In order to solve the above-described problems and achieve the object, the quantum key distribution method according to the present invention can correctly identify the polarization direction included in the data obtained from the measurement result of the photons on the quantum communication path. As a method of estimating the original transmission data by correcting the error of the reception data with probability information measured by the measuring device, for example, the communication device on the transmission side and the reception side have the same parity check matrix (the element is A check matrix generation step for generating a matrix of “0” or “1”, and the transmission-side communication apparatus receives the error correction information based on the parity check matrix and the transmission data via the public communication path An error correction information notifying step for notifying the communication device on the side, and the communication device on the receiving side transmits the transmission data based on the error correction information and the reception data with the probability information. Characterized in that it comprises a, and an error correction step of estimating.
[0020]
According to the present invention, a communication device constituting a quantum cryptography system corrects a data error on a transmission path in a short time by performing error correction using a parity check matrix for an LDPC code having extremely high characteristics, Furthermore, a highly secure common key is generated.
[0021]
DETAILED DESCRIPTION OF THE INVENTION
Embodiments of a quantum key distribution method according to the present invention will be described below in detail with reference to the drawings. Note that the present invention is not limited to the embodiments. In the following, quantum key distribution using polarized light will be described as an example. However, the present invention can be applied to, for example, those using phase and those using frequency. There is no particular limitation on the use.
[0022]
Embodiment 1 FIG.
Quantum key distribution is a key distribution method that guarantees security regardless of the computational capability of an eavesdropper. For example, in order to generate a shared key more efficiently, data generated by passing through a transmission path is used. It is necessary to remove the mistake. Therefore, in this embodiment, quantum key distribution in which error correction is performed using a low-density parity check (LDPC) code that is known to have extremely high characteristics will be described.
[0023]
FIG. 1 is a diagram showing a configuration of a quantum cryptography system (transmission apparatus on the transmission side and reception side) according to the present invention. This quantum cryptography system has information m_aAnd a communication device on the transmission side having a function of transmitting a message and information m affected by noise on the transmission line_aI.e. information m_bAnd a communication device on the receiving side having a function of receiving
[0024]
In addition, the communication device on the transmission side transmits information m via the quantum communication path._aSyndrome S via public communication path_AThe encryption key generation unit 1 that generates an encryption key (common key with the receiving side) based on the transmission information, and the data encrypted by the encryption unit 21 based on the encryption key are transmitted and received by the transmission / reception unit 22. A communication unit 2 that communicates via a public communication path, and the communication device on the receiving side transmits information m via the quantum communication path._bSyndrome S via public communication channel_AThe encryption key generation unit 3 generates an encryption key (a common key with the transmission side) based on the received information, and the transmission / reception unit 41 transmits the data encrypted by the encryption unit 42 based on the encryption key. Includes a communication unit 4 that communicates via a public communication path.
[0025]
In the transmission-side communication device, information m to be transmitted on the quantum communication path_aAs described above, light polarized in a predetermined direction using a polarizing filter (see FIG. 8) is transmitted to the communication device on the receiving side. On the other hand, the communication device on the receiving side uses a measuring device that can identify polarized light in the horizontal and vertical directions (0 °, 90 °) and a measuring device that can identify polarized light in the oblique direction (45 °, 135 °), Discriminate between light polarized in the horizontal direction (0 °), light polarized in the vertical direction (90 °), light polarized in the 45 ° direction, and light polarized in the 135 ° direction on the quantum channel. . Note that each measuring device can correctly recognize light polarized in a prescribed direction, but for example, measurement capable of distinguishing polarized light in the horizontal and vertical directions (0 °, 90 °) from light polarized in an oblique direction. When measured with the instrument, light polarized in the horizontal and vertical directions is randomly identified with a probability of 50%. That is, when a measuring instrument that does not correspond to an identifiable polarization direction is used, even if the measurement result is analyzed, the polarized direction cannot be correctly identified.
[0026]
Hereinafter, the operation of each communication apparatus in the quantum cryptography system, that is, the quantum key distribution in the present embodiment will be described in detail. FIG. 2 is a flowchart showing an outline of quantum key distribution according to the present embodiment. Specifically, (a) shows processing of the communication device on the transmission side, and (b) shows processing of the communication device on the reception side. Show.
[0027]
First, in the communication device on the transmission side and the communication device on the reception side, the parity check matrix generation units 10 and 30 obtain a parity check matrix H (n × k) of a specific linear code. A generator matrix G ((n−k) × n) that satisfies “HG = 0” is obtained.^-1Inverse matrix G of G where G = I (unit matrix)^-1(N × (n−k)) is obtained (step S1, step S11). In the present embodiment, quantum key distribution in the case where an LDPC code having excellent characteristics very close to the Shannon limit is used as the specific linear code will be described. In this embodiment, the LDPC code is used as the error correction method. However, the present invention is not limited to this, and another linear code such as a turbo code may be used. Further, for example, error correction information (syndrome) described later has an appropriate matrix H and transmission data m._A(Information m_aProduct Hm_A(For example, an error correction protocol corresponding to “quantum key distribution capable of correcting data errors on a transmission path” described in the prior art), that is, error correction information and transmission data m._AIf the linearity is ensured, the matrix H may be used.
[0028]
Here, the configuration method of the “Irregular-LDPC code” based on the finite affine geometry (details of step S1 in FIG. 2) will be described in detail with respect to the configuration method of the LDPC code in the parity check matrix generation unit 10. FIG. 3 is a flowchart showing a configuration method of an “Irregular-LDPC code” based on finite affine geometry. Note that the parity check matrix generation unit 30 operates in the same manner as the parity check matrix generation unit 10, and thus the description thereof is omitted. Moreover, the parity check matrix generation unit 10 may perform the parity check matrix generation processing according to the present embodiment, for example, according to a set parameter, or may be performed by another control device (such as a computer) outside the communication device. It may be executed. When the check matrix generation processing in the present embodiment is executed outside the communication device, the generated check matrix is stored in the communication device. In the following embodiments, the case where the parity check matrix generation unit 10 executes the above process will be described.
[0029]
First, the parity check matrix generation unit 10 uses a finite affine geometric code AG (2, 2) that is a base of a check matrix for the “Irregular-LDPC code”.^s) Is selected (step S21 in FIG. 3). Here, the row weight and the column weight are 2 respectively.^sIt becomes. FIG. 4 shows, for example, a finite affine geometric code AG (2, 2²) Is a diagram (blank represents 0).
[0030]
Next, in the parity check matrix generation unit 10, the maximum column weight r_l(2 <r_l≦ 2^s) Is determined (step S22). Then, the coding rate (1 syndrome length / key length) is determined (step S22).
[0031]
Next, the parity check matrix generation unit 10 tentatively uses column-weight distribution λ (γ (γ) using Gaussian approximation (Gaussian Approximation)._i) And line weight distribution ρ_uIs obtained (step S23). Note that the generation function ρ (x) of the row weight distribution is ρ (x) = ρ_ux^u-1+ (1-ρ_u) X^uAnd The weight u is an integer of u ≧ 2, and ρ_uRepresents the ratio of the weight u in a row.
[0032]
Next, the parity check matrix generation unit 10 selects row weights {u, u + 1} that can be configured by dividing the rows of finite affine geometry, and further, a partition coefficient {b that satisfies equation (1)_u, B_{u + 1}} Is obtained (step S24). B_u, B_{u + 1}Is a non-negative integer.
b_u+ B_{u + 1}(U + 1) = 2^s      ... (1)
[0033]
Specifically, from equation (2) below, b_uAnd b from the above equation (1)_{u + 1}Ask for.
[0034]
[Expression 1]

[0035]
Next, the parity check matrix generation unit 10 determines the parameters u, u + 1, b determined above._u, B_{u + 1}The weight ratio ρ of the row updated by_u´, ρ_{u + 1}'Is obtained from the equation (3) (step S25).
[0036]
[Expression 2]

[0037]
Next, the parity check matrix generation unit 10 further uses u, u + 1, ρ obtained above using optimization by the Gaussian approximation method._u´, ρ_{u + 1}Temporarily, the column weight distribution λ (γ_i) Is obtained (step S26). The weight γ_iIs γ_i≧ 2 and λ (γ_i) Is the weight γ in the sequence_iThe ratio of Also, the weight (λ (γ_i) ≦ γ_i/ W_t, I is a positive integer). However, w_tIs AG (2, 2^s) Represents the total number of 1s included in.
[0038]
Next, a set of column weight candidates {γ satisfying the above-described weight distribution and satisfying the following expression (4):₁, Γ₂, ... γ_l(Γ_l≦ 2^s)} Is selected (step S27). The weight γ of the column that does not satisfy the following equation (4)_iIs present, the column weight is deleted from the candidates.
[0039]
[Equation 3]

[0040]
Each a is a column weight 2^sTo construct {γ₁, Γ₂, ... γ_l} Represents a non-negative integer coefficient, i and j are positive integers, and γ_iRepresents the weight of the column and γ_lRepresents the maximum weight of the column.
[0041]
Next, the parity check matrix generation unit 10 further uses u, u + 1, ρ obtained above using optimization by the Gaussian approximation method._u´, ρ_{u + 1}´ and {γ₁, Γ₂, ... γ_l} As a fixed parameter, the column weight distribution λ (γ_i) And line weight distribution ρ_uIs obtained (step S28).
[0042]
Next, the parity check matrix generation unit 10 performs the column weight distribution λ (γ before performing the division process._i) And line weight distribution ρ_uIs adjusted (step S29). Note that the distribution of the weights after adjustment is as close to the value obtained by the Gaussian approximation method as possible. FIG. 5 shows the final column weight distribution λ (γ in step S29._i) And line weight distribution ρ_uFIG.
[0043]
Finally, the parity check matrix generation unit 10 divides the rows and columns in the finite affine geometry (step S30), and generates an n × k parity check matrix H. In the finite affine geometric code division processing according to the present invention, the number “1” is randomly extracted from each row or each column instead of regular division (see a specific example of random division described later). Note that this extraction process may use any method as long as the randomness is maintained.
[0044]
Specifically, EG (2, 2^Five) Row number of “1” in one column in
B_l(X) = {1 32 114 136 149 223 260 382 402 438 467 507 574 579 588 622 634 637 638 676 717 728 790 851 861 879 947 954 971 977 979 998}
In the case of the first to fourth columns R in the matrix after division_m(N) is B_lThe number “1” is randomly extracted from (x), for example,
R₁(N) = {1 114 574 637 851 879 977 979}
R₂(N) = {32 136 402 467 588 728 861 971}
R_Three(N) = {149 260 382 438 579 638 717 998}
R_Four(N) = {223 507 622 634 676 790 947 954}
It becomes.
[0045]
Here, an example of the random division, that is, the “division method using a random square Latin square” will be described in detail. Here, a random sequence for performing random division is generated easily and deterministically. An advantage of this method is that the same random sequence can be generated on the transmission side and the reception side.
[0046]
(1) Create a basic random sequence. Here, the finite affine geometry AG (2, 2^s) And P is P ≧ 2^sA basic random sequence C (i) in the case where the minimum prime number satisfying is satisfied is created according to the equation (5).
C (1) = 1
C (i + 1) = G₀× C (i) mod P (5)
Note that i = 0, 1,..., P-2, and G₀Is the primitive element of the Galois field GF (P). The sequence length is 2^s2 so that^sA larger number is deleted from C (i), and C (i) after deletion is set as a basic random sequence.
[0047]
(2) In order to read out the basic random sequence C (i) at regular intervals, the skip interval S (j) is defined as the following equation (6).
S (j) = j j = 1, 2,..., 2^s      (6)
[0048]
(3) Substitution pattern LB in the following formula (7)_jCreate (i).
LB_j(I) = ((S (j) × i) mod P) +1
j = 1, 2,..., 2^s
i = 1, 2,..., P-1 (7)
LB_j(I) 2^sRemove larger numbers.
[0049]
(4) j-th Latin square matrix L with q columns and i rows_jq(I) is calculated by the following equation (8).
L_jq(I) = LB_j(((Q + i-2) mod 2^s) +1)
j = 1, 2,..., 2^s
i = 1, 2,..., 2^s
q = 1, 2,..., 2^s          ... (8)
[0050]
(5) Latin square matrix L_jqDivide columns and rows according to (i). For column splitting, g₀, G₀, ..., g_n-1Is a column vector of the parity check matrix H and g_c'(K) to g_c, C = 0, 1,..., N−1, the kth “1” in the column. G_cA set of positions “1” in G_c(See equation (9)).
G_c= {G_c′ (K), k = 1, 2,..., 2^s} (9)
For example, AG (2, 2^Three) C = 1, the row number of “1” in the first column is G₁= {1 3 8 20 23 24 34 58}. The column vector of the c-th column is g_cWhen expressed by ′ (k), it can be expressed as in equation (10).
g_c′ (1) = ((c−1) +1) mod (2^2s-1)
g_c'(2) = (g_c'(1) +2) mod (2^2s-1)
g_c'(3) = (g_c'(2) +5) mod (2^2s-1)
g_c'(4) = (g_c'(3) +12) mod (2^2s-1)
g_c'(5) = (g_c'(4) +3) mod (2^2s-1)
g_c'(6) = (g_c'(5) +1) mod (2^2s-1)
g_c'(7) = (g_c'(6) +10) mod (2^2s-1)
g_c'(8) = (g_c'(7) +24) mod (2^2s-1) ... (10)
[0051]
Here, each column g of the parity check matrix H_cOn the basis of the order and coefficient of the column satisfying the above equation (4), a new column g_{c, e}Divide into And g_{c, e}'(R) is the new column g_{c, e}“1” in the r-th row in FIG. G_{c, e}A set of positions “1” in G_{c, e}(See equation (11)).
G_{c, e}= {G_{c, e}'(R), r = 1, 2, ...} (11)
[0052]
Then, using the Latin square matrix group, an edge to be divided is selected according to the following equation (12). A_{t, 1}, A_{t, 2}, ..., a_{t, l}And γ₁, Γ₂, ..., γ_lIs a coefficient and order satisfying the above equation (4). Further, t represents the row number of the coefficient matrix of the equation (4). In addition, the number of columns of the finite affine plane divided by the expression of the t-th row is n_tAnd the maximum row number of the coefficient matrix is t_mThen, t can be expressed by equation (13).
[0053]
[Expression 4]

[0054]
[Equation 5]

[0055]
Next, the division processes (1) to (4) will be described with specific examples. As an example, AG (2, 2^Three) C = the row number of “1” in the 16th column is G₁₆= {10 16 18 23 35 38 39 49} FIG. 6 is a diagram illustrating a division procedure using a Latin square matrix of a random sequence. The illustrated Latin square matrix L_jqWhen procedure (5) is performed using the result of (i), a new column g_{16, e}“1” in can be expressed as in equation (14).
g_16,1'(1) = g₁₆'(L_2,8(1)) = g₁₆'(3) = 18
g_16,1'(2) = g₁₆'(L_2,8(2)) = g₁₆'(2) = 16
g_16,2'(1) = g₁₆'(L_2,8(3)) = g₁₆'(8) = 49
g_16,2'(2) = g₁₆'(L_2,8(4)) = g₁₆'(7) = 39
g_16,3'(1) = g₁₆'(L_2,8(5)) = g₁₆'(6) = 38
g_16,3'(2) = g₁₆'(L_2,8(6)) = g₁₆'(1) = 10
g_16,4'(1) = g₁₆'(L_2,8(7)) = g₁₆'(4) = 23
g_16,4'(2) = g₁₆'(L_2,8(8)) = g₁₆'(5) = 35 (14)
[0056]
As a result, the 16th column is divided as follows.
G_16,1= {18 16}
G_16,2= {49 39}
G_16,3= {38 10}
G_16,4= {23 35}
[0057]
As described above, in this embodiment, the “Irregular-LDPC code” having a deterministic and stable characteristic is performed by executing the “Irregular-LDPC code” based on the finite affine geometry (FIG. 2, step S1). Can be generated.
[0058]
As described above, parity check matrix H, generator matrices G, G^-1(G^-1Next, after generating G = I: unit matrix), in the communication device on the transmission side, the random number generation unit 11 performs the random number sequence m_a(Column of 1, 0: transmission data) and transmission code (+: code corresponding to a measuring device that can discriminate light polarized in the horizontal and vertical directions, x: discriminate light polarized in the oblique direction A code corresponding to a possible measuring instrument) is randomly determined (step S2). On the other hand, in the receiving apparatus, the random number generator 31 can identify the received code (+: code corresponding to a measuring device that can discriminate light polarized in the horizontal and vertical directions, x: light polarized in the oblique direction) (Corresponding to the measuring instrument) is randomly determined (step S12).
[0059]
Next, in the communication device on the transmission side, the photon generator 12 performs the random number sequence m._aAnd photons are transmitted in the polarization direction automatically determined by the combination of the transmission code (step S3). For example, light polarized in the horizontal direction with a combination of 0 and +, light polarized in the vertical direction with a combination of 1 and +, and light polarized in the 45 ° direction with a combination of 0 and x The light polarized in the 135 ° direction with the combination of × is transmitted to the quantum communication path (transmission signal).
[0060]
  Photon generator 12Generated byThe photon receiver 32 of the receiving communication device that has received the optical signal measures the light on the quantum communication path (received signal). The received data m automatically determined by the combination of the received code and the received signal_bIs obtained (step S13). Here, received data m_bAs follows: 0 for a combination of horizontally polarized light and +, 1 for a combination of vertically polarized light and +, 0 for a combination of 45 ° polarized light and x, 135 ° 0 is obtained for each combination of light polarized in the direction and x. Received data m_bIs a hard decision value with probability information.
[0061]
Next, in the communication device on the receiving side, in order to check whether or not the above measurement has been performed by a correct measuring device, the random number generator 31 sends the received code to the communication device on the transmitting side via the public communication path. It transmits to (step S13). Upon receiving the received code, the transmitting communication device checks whether the above measurement is performed by a correct measuring device, and transmits the result to the receiving communication device via the public communication path (step S3). Then, the communication device on the reception side and the communication device on the transmission side leave only the data corresponding to the received signal received by the correct measuring instrument and discard the others (steps S3 and S13). Thereafter, the remaining data is stored in a memory or the like, n bits are read in order from the head, and this is converted into the formal transmission data m._AAnd received data m_B(M_BIs affected by noise on the transmission line._A: M_B= M_A+ E (noise etc.)). That is, here, if necessary, the next n bits are read and the transmission data m_AAnd received data m_BIs generated. In the present embodiment, the bit positions of the remaining data can be shared between the communication device on the transmission side and the communication device on the reception side. M_BIs the above m_bSimilarly, it is a hard decision value with probability information.
[0062]
Next, in the communication device on the transmission side, the syndrome generation unit 14 performs a parity check matrix H (n × k) and transmission data m._ATo m_ASyndrome S_A= Hm_AAnd the result is notified to the communication device on the receiving side via the public communication channel communication unit 13 and the public communication channel (step S4). At this stage, m_ASyndrome S_A(Information for k bits) may be known to an eavesdropper. On the other hand, in the communication device on the receiving side, the public communication channel communication unit 34_ASyndrome S_AIs notified to the syndrome decoding unit 33 (step S14).
[0063]
The syndrome decoding unit 33 uses the syndrome decoding method according to the present embodiment to make a hard decision value m with probability information due to noise or the like._BThe original transmission data m is corrected by correcting the error of_AIs estimated (step S15). Here, “S_A= Hm_CM_CHard decision value m with probability information_BAnd the estimation result m_CShared information m_AAnd Hereinafter, the syndrome decoding method of the present embodiment will be described in detail.
[0064]
FIG. 7 is a flowchart showing the syndrome decoding method of the present embodiment. As described above, when a binary n (column) × k (row) parity check matrix H is assumed, an i-th column (1 ≦ i ≦ n) j-th row (1 ≦ j ≦ k) element is H_ijIs written. Received data m_BM_B= (M_B1, M_B2, ..., m_Bn) And estimated word (hard decision value) m_CM_C= (M_C1, M_C2, ..., m_Cn). M_ASyndrome S_AS_A= (S_A1, S_A2, ..., S_Ak) In addition, the conditional probability P (m_B｜ m_C= M_A) Is assumed to be a memoryless communication path.
[0065]
First, the syndrome decoding unit 33 sets H as an initial setting._ijQ is the prior value of all column and row combinations (i, j) satisfying = 1_ij(0) = 1/2, q_ij(1) = 1/2. q_ij(0) is H_ijRepresents the probability that is “0”, q_ij(1) is H_ijRepresents the probability of “1”. The counter value indicating the number of decoding iterations is set to l = 1 (iteration: once), and the maximum number of iterations l_maxIs set (step S31).
[0066]
Next, in the syndrome decoding unit 33, H = 1, 2,._ij= 1 for all column and row combinations (i, j) that satisfy = 1_ij(0) and r_ij(1) is updated (step S32). In the present embodiment, for example, j (1 ≦ j ≦ k) th syndrome S_AjIs “0”, the external value r using the update formula (15) and the update formula (16)_ij(0) and r_ijUpdate (1).
[0067]
[Formula 6]

[0068]
[Expression 7]

[0069]
On the other hand, the j (1 ≦ j ≦ k) th syndrome S_AjIs “1”, the external value r using the update formula (17) and the update formula (18)_ij(0) and r_ijUpdate (1).
[0070]
[Equation 8]

[0071]
[Equation 9]

[0072]
The above K is “r”._ij(0) + r_ijA value (value for normalization) defined so that (1) = 1 ”holds. In addition, P (m_B｜ m_C) Is the conditional probability, ie the estimated word m_CReceived data m when is "0" or "1"_BRepresents the probability of. The subset A (i) represents a set of row indexes where “1” stands in the i-th column of the parity check matrix H, and the subset B (j) represents “a” in the j-th row of the parity check matrix H. 1 ”represents a set of column indexes.
[0073]
When the above update process is specifically described, for example, S_Aj= 0, j = 1, and H_i1When the combination of all the columns and rows satisfying = 1 is (i, 1) = (3,1) (4,1) (5,1), the expressions (15) and (16) are applied, and the external Value r₃₁(0), r₃₁(1) is updated as shown in equations (19) and (20). That is, H₃₁H other than₄₁, H₅₁Using the external value r₃₁(0), r₃₁Update (1). Here, the probability that the third column and first row of the parity check matrix H is “0” and the probability that it is “1” are obtained.
[0074]
[Expression 10]

[0075]
## EQU11 ##

[0076]
Next, in the syndrome decoding unit 33, H = 1, 2,._ijA priori value q for all column and row combinations (i, j) that satisfy = 1_ij(0) and q_ij(1) is updated (step S33). This update process can be expressed by equations (21) and (22).
[0077]
[Expression 12]

[0078]
[Formula 13]

[0079]
The above K ′ is “q_ij(0) + q_ijA value (value for normalization) defined so that (1) = 1 ”holds.
[0080]
Specifically describing the update process, for example, i = 3 and H_1jWhen the combination of all the columns and rows satisfying = 1 is (3, j) = (3,1) (3,2) (3,3), Expressions (21) and (22) are applied, and Value q₃₁(0), q₃₁(1) is updated as shown in equations (23) and (24). That is, H₃₁H other than₃₂, H₃₃Using the prior value q₃₁(0), q₃₁Update (1).
[0081]
[Expression 14]

[0082]
[Expression 15]

[0083]
Next, in the syndrome decoding unit 33, the posterior probability (conditional probability × prior value) Q_i(0), Q_i(1) is obtained, and from this posterior probability, the temporary estimated word m_C'= (M_C1', M_C2', ..., m_Cn') Is obtained (step S34). That is, the temporary estimated word in Expression (27) is obtained based on the calculation results of Expression (25) and Expression (26). Here, the determination process is performed for each iteration.
[0084]
[Expression 16]

[0085]
[Expression 17]

[0086]
[Expression 18]

[0087]
The above K ″ is “Q_i(0) + Q_iA value (value for normalization) defined so that (1) = 1 ”holds. The conditional probability P (m_B｜ m_C= 0) is defined as in Expression (28) and Expression (29), and p represents a bit error rate.
[0088]
[Equation 19]

[0089]
[Expression 20]

[0090]
  Next, in the syndrome decoding unit 33, the temporary estimated word m_C'Is the transmission data m_AIs inspected (step S35). Here, for example, m_C'= (M_C1', M_C2', ..., m_Cn') Is "m_C'× H^T=S _A ”(Step S36, Yes), m_C'Is the estimated word m_C= (M_C1, M_C2, ..., m_Cn), That is, the original transmission data m_A= (M_A1, M_A2, ..., m_An) And finish this algorithm.
[0091]
On the other hand, when the above condition is not satisfied, and l <l_maxIn the case of (No in step S36), the counter value l is incremented, and the process in step S32 is executed again using the updated value. Thereafter, until the above condition is satisfied (l <l_maxThe process of steps S32 to S36 is repeatedly executed using the updated value.
[0092]
As described above, in the syndrome decryption method employed in the quantum key distribution according to the present embodiment, a large number of parity exchanges for specifying an error bit occurred in the error correction described in the prior art. (Binary search) ”is excluded, and error correction is performed using a parity check matrix for an LDPC code having extremely high characteristics (error correction capability). This makes it possible to generate a common key with a high degree of security while correcting data errors on the transmission path in a short time.
[0093]
In the present embodiment, the received data m_BAnd m_bIs a hard decision value with probability information, but is not limited thereto, and may be a soft decision value, for example.
[0094]
Finally, in the communication device on the receiving side, the shared key generation unit 35 makes public error correction information (information about the k bits that may have been wiretapped: S_A) Shared information (m_A) Is discarded, and an encryption key r having an amount of information of n−k bits is generated (step S16). That is, in the shared key generation unit 35, the previously calculated G^-1Using (n × (n−k)), the encryption key r is generated by the following equation (30). The communication device on the reception side uses this encryption key r as a shared key with the communication device on the transmission side.
r = G^-1m_A              ... (30)
[0095]
On the other hand, also in the communication device on the transmission side, the shared key generation unit 15 performs public error correction information (information about the k bits that may have been wiretapped: S_A) Shared information (m_A) Is discarded, and an encryption key r having an information amount of n−k bits is generated (step S5). That is, the shared key generation unit 15 uses the previously calculated G^-1Using (n × (n−k)), the encryption key r is generated by the above equation (30) (step S5). The communication device on the transmission side uses this encryption key r as a shared key with the communication device on the reception side.
[0096]
In the present embodiment, the shared keys may be rearranged using a regular random matrix R. Thereby, confidentiality can be strengthened. Specifically, first, the communication device on the transmission side generates a regular random matrix R ((n−k) × (n−k)), and further, the R is transmitted to the reception side via the public communication path. To the communication device. Note that this processing may be performed by a communication device on the receiving side. After that, the transmitter and receiver communication devices calculate G^-1Using (n × (n−k)) and the random matrix R, the encryption key r is generated by the following equation (31).
r = RG^-1m_A              ... (31)
[0097]
As described above, in the present embodiment, the data error of the shared information is corrected using the parity check matrix for the “Irregular-LDPC code” that is deterministic and stable in characteristics, and is in accordance with the published error correction information. Therefore, a part of the shared information is discarded. This eliminates an enormous number of parity exchanges for identifying / correcting error bits, and error correction control is performed only by transmitting error correction information, so that the time required for error correction processing can be greatly reduced. In addition, since a part of the shared information is discarded according to the disclosed information, a highly secure common key can be generated.
[0098]
In the present embodiment, from a generator matrix G ((n−k) × n) that satisfies HG = 0, G^-1Inverse matrix G where G = I (unit matrix)^-1(N × (n−k)) is generated and the inverse matrix G^-1Is used to generate part of the shared information (n) by discarding part (k) and generating an encryption key r having an amount of information of n−k bits. However, the present invention is not limited to this, and the shared information (n) It is also possible to generate an encryption key r having an information amount of m (m ≦ n−k) bits by discarding a part of More specifically, a map F (•) that maps an n-dimensional vector to an m-dimensional vector is assumed. In order to guarantee the security of the shared key, F (•) is “an inverse image (F • G) in the combined map F • G of the mapping F and the generator matrix G for an arbitrary m-dimensional vector v^-1The original number of (v) is constant regardless of v (2^nkm) ”Is necessary. At this time, the shared key r is r = F (m_A)
[0099]
In the present embodiment, the generator matrix G is obtained by the processing of steps S5 and S16.^-1A configuration may be adopted in which a part of the shared information is discarded using the characteristics of the parity check matrix H without using. Specifically, first, shared key generation units 15 and 35 perform random replacement on the columns of parity check matrix H generated in steps S1 and S11. And the information regarding the bit thrown away between communication apparatuses is exchanged via a public communication path. For example, the original finite affine geometry AG (2, 2^s) To select a specific “1” from the first column and exchange the position via the public communication path. After that, the shared key generation units 15 and 35 perform the divided position corresponding to “1” from the parity check matrix after replacement, and the divided position corresponding to “1” in each cyclically shifted column. And the shared information m corresponding to the specified position_AAre discarded, and the remaining data is used as the encryption key r. As a result, complex generator matrices G and G^-1Can be deleted.
[0100]
【The invention's effect】
As described above, according to the present invention, a communication device that constitutes a quantum cryptography system has received a huge number of parity exchanges (binary search for specifying error bits) that occurred in error correction in the prior art. ) ”And error correction is performed using a parity check matrix for LDPC codes having extremely high characteristics (corresponding to the above syndrome decoding method). As a result, it is possible to generate a common key with a high degree of security while correcting a data error on the transmission path in a short time.
[Brief description of the drawings]
FIG. 1 is a diagram showing a configuration of a quantum cryptography system according to the present invention.
FIG. 2 is a flowchart showing quantum key distribution.
FIG. 3 is a flowchart showing a configuration method of “Irregular-LDPC code” based on finite affine geometry;
FIG. 4 is a finite affine geometric code AG (2, 2²FIG.
FIG. 5 shows the final column weight distribution λ (γ_i) And line weight distribution ρ_uFIG.
FIG. 6 is a diagram showing a procedure for dividing a random sequence by a Latin square matrix;
FIG. 7 is a flowchart showing a syndrome decoding method.
FIG. 8 is a diagram showing an outline of conventional quantum key distribution.
[Explanation of symbols]
1, 3 Encryption key generation unit, 2, 4 communication unit, 10, 30 Parity check matrix generation unit, 11, 31 Random number generation unit, 12 Photon generation unit, 13, 34 Public channel communication unit, 14 Syndrome generation unit, 15 , 35 shared key generation unit, 21, 42 encryption unit, 22, 41 transmission / reception unit, 32 photon reception unit, 33 syndrome decryption unit.

Claims (5)

Estimate the original transmitted data by correcting the error in the received data with probability information measured by a measuring device that can correctly identify the polarization direction, included in the data obtained from the measurement results of photons on the quantum channel In the quantum key distribution method,
A check matrix generation step in which the communication device on the transmission side and the reception side generate the same parity check matrix (a matrix whose elements are “0” or “1”);
An error correction information notifying step in which the transmission side communication device notifies the reception side communication device of error correction information based on the parity check matrix and the transmission data via a public communication path;
An error correction step in which the communication device on the receiving side estimates the transmission data based on the error correction information and the reception data with the probability information; and
Based on the regular random matrix shared with the communication device on the transmission side and the estimation result of the transmission data, the communication device on the reception side generates an encryption key shared with the communication device on the transmission side. A shared key generation step to be generated; and
A quantum key distribution method comprising: In the error correction step,
As an initial setting, an initial setting step for setting a prior value corresponding to the element “1” in the parity check matrix;
A process of updating the external value corresponding to the element “1” in the parity check matrix using the prior value corresponding to the other element “1” in the same row and the probability information according to the error correction information; An external value update step that executes for each row,
A prior value for executing, in column units, a process of updating a prior value corresponding to element “1” in the parity check matrix using the updated external value corresponding to another element “1” in the same column An update step;
A posterior probability is calculated based on the probability information and the updated prior value, and a temporary estimation word is obtained from the posterior probability (hard decision), a temporary estimation step;
When the temporary estimated word satisfies a predetermined condition established between the temporary check word and the parity check matrix, the temporary estimated word is used as transmission data, and when the predetermined condition is not satisfied, the condition is satisfied until the condition is satisfied. A transmission data estimation step that repeatedly executes the external value update step, the prior value update step, and the temporary estimation step using the updated value;
The quantum key distribution method according to claim 1, comprising: The error correction step, when soft decision information is received as reception data with probability information, the transmission data is estimated based on the error correction information and the soft decision information. 3. The quantum key distribution method according to 1 or 2. Estimate the original transmitted data by correcting the error in the received data with probability information measured by a measuring device that can correctly identify the polarization direction, included in the data obtained from the measurement results of photons on the quantum channel In communication equipment,
The same parity check matrix (matrix whose element is “0” or “1”) generated in advance, the parity check matrix received from the communication device on the transmission side via the public communication path, and the transmission data decoding means for estimating the transmission data based error correction information, and the probability information with the received data, the based,
Based on a regular random matrix shared with the communication device on the transmission side and an estimation result of the transmission data, a shared key generation unit that generates an encryption key shared with the communication device on the transmission side,
A communication device comprising: The decoding means includes
As an initial setting, a prior value corresponding to the element “1” in the parity check matrix is set,
A process of updating the external value corresponding to the element “1” in the parity check matrix using the prior value corresponding to the other element “1” in the same row and the probability information according to the error correction information; Is executed line by line,
A process of updating the prior value corresponding to the element “1” in the parity check matrix using the updated external value corresponding to the other element “1” in the same column, in units of columns;
A posteriori probability is calculated based on the probability information and the updated prior value, and a temporary estimated word is obtained from the posteriori probability (hard decision process),
When the temporary estimated word satisfies a predetermined condition established between the temporary check word and the parity check matrix, the temporary estimated word is used as transmission data, and when the predetermined condition is not satisfied, the condition is satisfied until the condition is satisfied. The communication apparatus according to claim 4, wherein the external value update process, the prior value update process, and the hard decision process are repeatedly executed using the updated value.

Images