(57)【特許請求の範囲】
【請求項１】
長さｎの入力ビット列で構成される入力ｘと、長さｋのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する際に、有限体ＧＦ（２ｋ）上の乗算処理を実行する行列演算処理部を備えた秘匿性増強装置であって、
いずれも正の整数である前記長さｎ、前記長さｋ、前記長さｍは、
ｋ＝ｎ−ｍ
ｎ＝ｋｔ    ただし、ｔは、３以上の整数
の条件を満たし、
前記行列演算処理部は、有限体乗算を行うに当たり、有限体ＧＦ（２ｋ）上において、ｉ＝１、・・・、ｔ−１について、
ｙｉ＝ｘｉ＋ｒｉｘｔ
の演算を行い、前記出力ｙを、
ｙ＝（ｙ１、・・・、ｙｔ−１）
により生成し、長さｍ＝（ｔ−１）ｋのビット列として出力する
秘匿性増強装置。
【請求項２】
長さｎの入力ビット列で構成される入力ｘと、長さｕのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する際に、有限体ＧＦ（２ｋ）上の乗算処理を実行する行列演算処理部を備えた秘匿性増強装置であって、
前記長さｎ、前記長さｕ、前記長さｍは、いずれも正の整数であり、ｕ、ｍがｋの整数倍であるという条件を満たし、
前記行列演算処理部は、有限体乗算を行うに当たり、
長さｋが、ｋ＋１が奇素数であり、有限体ＧＦ（ｋ＋１）の乗法群ＧＦ（ｋ＋１）×において、２が生成元となる
というさらなる条件を満たす際に、ＧＦ（２ｋ）の元ａ、ｂを
ａ＝（ａ０、・・・、ａｋ−１）
ｂ＝（ｂ０、・・・、ｂｋ−１）
と表し、ａ、ｂそれぞれのパリティを
ａｋ＝ａ０＋・・・＋ａｋ−１  ｍｏｄ  ２
ｂｋ＝ｂ０＋・・・＋ｂｋ−１  ｍｏｄ  ２
として算出し、
ａｋ、ｂｋをａ、ｂに連接したベクトルを
Ａ＝（ａ０、・・・、ａｋ−１、ａｋ）
Ｂ＝（ｂ０、・・・、ｂｋ−１、ｂｋ）
とおき、ビット列Ｘを第一行としてもつ、ｋ×ｋ巡回行列を、下式で示される行列Ｍ（Ａ）
【数１】
0006049589.tif 000003
として、前記行列Ｍ（Ａ）とベクトルＢとを掛け合わせ、ｋ＋１ビットのベクトルＣ
Ｃ＝（ｃ０、ｃ１、・・・、ｃｋ）＝ＢＭ（Ａ）
を生成し、前記ベクトルＣの最後の成分ｃｋを削除した
ｃ＝（ｃ０、・・・、ｃｋ−１）
を乗算結果として算出し、前記出力ｙとする
秘匿性増強装置。
【請求項３】
請求項１に記載の秘匿性増強装置において、
前記行列演算処理部は、
ｍ−ｎ＋１が奇素数であり、有限体ＧＦ（ｍ−ｎ＋１）の乗法群ＧＦ（ｍ−ｎ＋１）×において、２が生成元となるように、ｍ、ｎを選ぶ
というさらなる条件を満たす際に、
前記出力ｙを生成するに当たって、請求項２に記載の有限体乗算方式を採用する
秘匿性増強装置。
【請求項４】
請求項２に記載の秘匿性増強装置において、
前記行列演算処理部は、有限体乗算を用いた従来型のユニバーサルハッシュ関数を用いた秘匿性増強装置において出力ｙを生成するに当たって、請求項２に記載の有限体乗算方式を採用する
秘匿性増強装置。
【請求項５】
長さｎの入力ビット列で構成される入力ｘと、長さｋのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する行列演算処理部を備えた秘匿性増強装置によって実行される秘匿性増強データ処理方法であって、
いずれも正の整数である前記長さｎ、前記長さｋ、前記長さｍは、
ｋ＝ｎ−ｍ
ｎ＝ｋｔ    ただし、ｔは、３以上の整数
の条件を満たし、
前記行列演算処理部において、有限体乗算を行うに当たり、
有限体ＧＦ（２ｋ）上において、ｉ＝１、・・・、ｔ−１について、
ｙｉ＝ｘｉ＋ｒｉｘｔ
の演算を行い、前記出力ｙを、
ｙ＝（ｙ１、・・・、ｙｔ−１）
により生成し、長さｍ＝（ｔ−１）ｋのビット列として出力するステップ
を備える秘匿性増強データ処理方法。
【請求項６】
長さｎの入力ビット列で構成される入力ｘと、長さｕのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する行列演算処理部を備えた秘匿性増強装置によって実行される秘匿性増強データ処理方法であって、
前記長さｎ、前記長さｕ、前記長さｍは、いずれも正の整数であり、ｕ、ｍがｋの整数倍であるという条件を満たし、
前記行列演算処理部において、有限体乗算を行うに当たり、
長さｋが、ｋ＋１が奇素数であり、有限体ＧＦ（ｋ＋１）の乗法群ＧＦ（ｋ＋１）×において、２が生成元となる
というさらなる条件を満たす際に、ＧＦ（２ｋ）の元ａ、ｂを
ａ＝（ａ０、・・・、ａｋ−１）
ｂ＝（ｂ０、・・・、ｂｋ−１）
と表し、ａ、ｂそれぞれのパリティを
ａｋ＝ａ０＋・・・＋ａｋ−１  ｍｏｄ  ２
ｂｋ＝ｂ０＋・・・＋ｂｋ−１  ｍｏｄ  ２
として算出する第１ステップと、
ａｋ、ｂｋをａ、ｂに連接したベクトルを
Ａ＝（ａ０、・・・、ａｋ−１、ａｋ）
Ｂ＝（ｂ０、・・・、ｂｋ−１、ｂｋ）
とおき、ビット列Ｘを第一行としてもつ、ｋ×ｋ巡回行列を、下式で示される行列Ｍ（Ａ）
【数２】
0006049589.tif 000004
として、前記行列Ｍ（Ａ）とベクトルＢとを掛け合わせ、ｋ＋１ビットのベクトルＣ
Ｃ＝（ｃ０、ｃ１、・・・、ｃｋ）＝ＢＭ（Ａ）
を生成する第２ステップと、
前記ベクトルＣの最後の成分ｃｋを削除した
ｃ＝（ｃ０、・・・、ｃｋ−１）
を乗算結果として算出し、前記出力ｙとする第３ステップと
を備える秘匿性増強データ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿性増強（ｐｒｉｖａｃｙ  ａｍｐｌｉｆｉｃａｔｉｏｎ：ＰＡ）と呼ばれるデータ処理方式の改良に関するものであり、特に、演算処理速度の向上あるいは乱数消費量の低減による有限体乗算処理の性能向上を図った秘匿性増強装置および秘匿性増強データ処理方法に関する。
【背景技術】
【０００２】
秘匿性増強の応用先としては、量子暗号、人工物メトリクス、生体認証など、様々な分野がある。以下では、説明の便のため、量子暗号の場合を中心に述べるが、本発明の秘匿性増強装置および秘匿性増強データ処理方法に関する技術は、それ以外の分野にも適用可能である。
【０００３】
量子暗号（ｑｕａｎｔｕｍ  ｃｒｙｐｔｏｇｒａｐｈｙ）は、秘密通信に用いる秘密鍵を共有するための暗号方式であり、量子鍵配送（ｑｕａｎｔｕｍ  ｋｅｙ  ｄｉｓｔｒｉｂｕｔｉｏｎ）とも呼ばれる。代表的な方式として、ＢＢ８４方式、ＳＡＲＧ０４方式、Ｂ９２方式、ＢＢＭ９２方式などがある。
【０００４】
これらの方式による量子暗号装置は、大別すると、光子の送信と受信を行う量子通信部分と、そこから出力された乱数列（ふるい鍵、篩鍵、ｓｉｆｔｅｄ  ｋｅｙと呼ばれる）に対しデータ処理を行う鍵蒸留部分の２つの機能を備えている。
【０００５】
そして、後者の鍵蒸留の機能をさらに二分すると、誤り訂正と秘匿性増強に分けられる。誤り訂正は、通信路や検出器で生じた雑音を、ふるい鍵から除去するためのものである。訂正されたふるい鍵は、訂正鍵（ｒｅｃｏｎｃｉｌｅｄ  ｋｅｙ）と呼ばれる。
【０００６】
一方で、秘匿性増強は、通信路の盗聴によって第三者（盗聴者）に漏洩した可能性のある情報を、訂正鍵からキャンセルするために行われる。そして、その出力は、秘密鍵（ｓｅｃｒｅｔ  ｋｅｙ）、または最終鍵（ｆｉｎａｌ  ｋｅｙ）と呼ばれる。
【０００７】
秘密鍵の内容は、盗聴者にとって全く推測不可能であり、正規の送信者と受信者は、秘密鍵を秘密通信用の鍵として、そのまま利用することができる。ただし、この高い秘密性の代償として、秘密鍵の長さは、通常、訂正鍵よりも短くなる。いわば訂正鍵の弱い秘密性を、短く圧縮して秘密鍵を得ていることになる。
【０００８】
これまでの量子暗号の研究や実装では、秘匿性増強には、もっぱらユニバーサルハッシュ関数（ｕｎｉｖｅｒｓａｌ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ）と呼ばれる種類の関数が用いられてきた。そして、代表的なユニバーサルハッシュ関数として、テープリッツ（Ｔｏｅｐｌｉｔｚ）行列を用いるものが知られている（例えば、特許文献１参照）。また、この方式は、高速フーリエ変換（ＦＦＴ）アルゴリズムを用いることにより、高速に実行できることが知られている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００７−８６１７０号公報
【特許文献２】特開２０１２−４９７６５号公報
【非特許文献】
【００１０】
【非特許文献１】T. Tsurumaru and M. Hayashi “Dual universality of hash functions and its application to quantum key distribution、” IEEE Transactions on Information Theory、 Volume 59、 Issue 7、 4700 - 4717 (2013); arXiv:1101.0064 [quant-ph].
【非特許文献２】M. Hayashi、 “Large deviation analysis for classical and quantum security via approximate smoothing、” arXiv:1202.0322 [quant-ph].
【非特許文献３】J. H. Silverman、 “A Friendly Introduction to Number Theory、 3rd. Ed.、” (Pearson Education、 New Jersey、 2006); 邦訳：「はじめての数論 原著第３版」、株式会社ピアソン桐原、2007年．
【非特許文献４】G. H. Golub and C. F. Van Loan、 “Matrix Computations、 3rd. Ed.、” (The John Hopkins University Press、 Maryland、 1996)．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、従来技術には、以下のような課題がある。
上述したように、秘匿性増強アルゴリズムとして、テープリッツ行列を用いるものが広く知られている。この方式では、入力ビット列（訂正鍵）をベクトルとみなし、それにテープリッツ行列をかけることにより、出力ビット列（秘密鍵）を得る。また、特許文献１では、テープリッツ行列の代わりに、単位行列とテープリッツ行列を連接した行列（以下、この行列を、変形テープリッツ行列と称す）を使う方式が提案されている。
【００１２】
いずれのアルゴリズムを用いる場合でも、量子暗号の無条件安全性を保証するためには、テープリッツ行列あるいは変形テープリッツ行列のサイズを大きくとる必要がある（一般的には、列数を１０６程度以上にする必要がある）。これは、量子暗号の安全性証明の理論からくる要請であり、いわゆる有限長効果が原因となっている。
【００１３】
このように、テープリッツ行列あるいは変形テープリッツ行列のサイズが大きい場合には、乗算に時間がかかり、量子暗号装置全体としての鍵生成速度が遅くなるという問題点が生じる。また、テープリッツ行列あるいは変形テープリッツ行列は、秘匿性増強を行うたびに新たに選び直す必要があるので、その際の乱数消費量（すなわち、乱数発生器の実装コスト）も同様に大きくなるという問題点も生じる。
【００１４】
本発明は、前記のような課題を解決するためになされたものであり、秘匿性増強データ処理を実行するに当たり、有限体乗算処理の性能向上を実現できる秘匿性増強アルゴリズムを備えた秘匿性増強装置および秘匿性増強データ処理方法を得ることを目的とする。
【課題を解決するための手段】
【００１５】
本発明に係る秘匿性増強装置は、長さｎの入力ビット列で構成される入力ｘと、長さｋのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する際に、有限体ＧＦ（２ｋ）上の乗算処理と加算処理を実行する行列演算処理部を備えた秘匿性増強装置であって、いずれも正の整数である長さｎ、長さｋ、長さｍは、
ｋ＝ｎ−ｍ
ｎ＝ｋｔ    ただし、ｔは、３以上の整数
の条件を満たし、行列演算処理部は、有限体乗算を行うに当たり、長さｋのビット列ｒをＧＦ（２ｋ）の元と同一視する。また、ｘをｋビットのブロックに分割して
ｘ＝（ｘ１、・・・、ｘｔ）
とし、各ｘｉをＧＦ（２ｋ）の元と同一視する。さらに、行列演算処理部は、有限体乗算を行うに当たり、有限体ＧＦ（２ｋ）上において、ｉ＝１、・・・、ｔ−１について、
ｙｉ＝ｘｉ＋ｒｉｘｔ
の演算を行い、出力ｙを、
ｙ＝（ｙ１、・・・、ｙｔ−１）
により生成し、長さｍ＝（ｔ−１）ｋのビット列として出力するものである。
なお、ｒの上つき添え字ｒｉは、有限体ＧＦ（２ｋ）上のｒのｉ乗を示すものである。
【００１６】
また、本発明に係る秘匿性増強装置は、長さｎの入力ビット列で構成される入力ｘと、長さｕのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する際に、有限体ＧＦ（２ｋ）上の乗算処理を実行する行列演算処理部を備えた秘匿性増強装置であって、ｕ、ｍがｋの整数倍であるという条件を満たし、行列演算処理部は、有限体乗算を行うに当たり、
長さｋが、ｋ＋１が奇素数であり、有限体ＧＦ（ｋ＋１）の乗法群ＧＦ（ｋ＋１）×において、２が生成元となる
というさらなる条件を満たす際に、ＧＦ（２ｋ）の元ａ、ｂを
ａ＝（ａ０、・・・、ａｋ−１）
ｂ＝（ｂ０、・・・、ｂｋ−１）
と表し、ａ、ｂそれぞれのパリティを
ａｋ＝ａ０＋・・・＋ａｋ−１  ｍｏｄ  ２
ｂｋ＝ｂ０＋・・・＋ｂｋ−１  ｍｏｄ  ２
として算出し、ａｋ、ｂｋをａ、ｂに連接したベクトルを
Ａ＝（ａ０、・・・、ａｋ−１、ａｋ）
Ｂ＝（ｂ０、・・・、ｂｋ−１、ｂｋ）
とおき、ビット列Ｘを第一行としてもつ、ｋ×ｋ巡回行列を、後述する式（１）で示される行列Ｍ（Ａ）として、行列Ｍ（Ａ）とベクトルＢとを掛け合わせ、ｋ＋１ビットのベクトルＣ
Ｃ＝（ｃ０、ｃ１、・・・、ｃｋ）＝ＢＭ（Ａ）
を生成し、ベクトルＣの最後の成分ｃｋを削除した
ｃ＝（ｃ０、・・・、ｃｋ−１）
を乗算結果として算出し、出力ｙとするものである。
【００１７】
また、本発明に係る秘匿性増強データ処理方法は、長さｎの入力ビット列で構成される入力ｘと、長さｋのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する行列演算処理部を備えた秘匿性増強装置によって実行される秘匿性増強データ処理方法であって、いずれも正の整数である長さｎ、長さｋ、長さｍは、
ｋ＝ｎ−ｍ
ｎ＝ｋｔ    ただし、ｔは、３以上の整数
の条件を満たし、行列演算処理部は、有限体乗算を行うに当たり、長さｋのビット列ｒをＧＦ（２ｋ）の元と同一視する。また、ｘをｋビットのブロックに分割して
ｘ＝（ｘ１、・・・、ｘｔ）
とし、各ｘｉをＧＦ（２ｋ）の元と同一視する。さらに、行列演算処理部は、有限体乗算を行うに当たり、有限体ＧＦ（２ｋ）上において、ｉ＝１、・・・、ｔ−１について、
ｙｉ＝ｘｉ＋ｒｉｘｔ
の演算を行い、出力ｙを、
ｙ＝（ｙ１、・・・、ｙｔ−１）
により生成し、長さｍ＝（ｔ−１）ｋのビット列として出力するステップを備えるものである。
なお、ｒの上つき添え字ｒｉは、有限体ＧＦ（２ｋ）上のｒのｉ乗を示すものである。
【００１８】
さらに、本発明に係る秘匿性増強データ処理方法は、長さｎの入力ビット列で構成される入力ｘと、長さｕのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する際に、有限体ＧＦ（２ｋ）上の乗算処理を実行する行列演算処理部を備えた秘匿性増強装置であって、ｕ、ｍがｋの整数倍であるという条件を満たし、行列演算処理部は、有限体乗算を行うに当たり、
長さｋが、ｋ＋１が奇素数であり、有限体ＧＦ（ｋ＋１）の乗法群ＧＦ（ｋ＋１）×において、２が生成元となる
というさらなる条件を満たす際に、ＧＦ（２ｋ）の元ａ、ｂを
ａ＝（ａ０、・・・、ａｋ−１）
ｂ＝（ｂ０、・・・、ｂｋ−１）
と表し、ａ、ｂそれぞれのパリティを
ａｋ＝ａ０＋・・・＋ａｋ−１  ｍｏｄ  ２
ｂｋ＝ｂ０＋・・・＋ｂｋ−１  ｍｏｄ  ２
として算出する第１ステップと、ａｋ、ｂｋをａ、ｂに連接したベクトルを
Ａ＝（ａ０、・・・、ａｋ−１、ａｋ）
Ｂ＝（ｂ０、・・・、ｂｋ−１、ｂｋ）
とおき、ビット列Ｘを第一行としてもつ、ｋ×ｋ巡回行列を、後述する式（１）で示される行列Ｍ（Ａ）として、行列Ｍ（Ａ）とベクトルＢとを掛け合わせ、ｋ＋１ビットのベクトルＣ
Ｃ＝（ｃ０、ｃ１、・・・、ｃｋ）＝ＢＭ（Ａ）
を生成する第２ステップと、ベクトルＣの最後の成分ｃｋを削除した
ｃ＝（ｃ０、・・・、ｃｋ−１）
を乗算結果として算出し、出力ｙとする第３ステップとを備えるものである。
【発明の効果】
【００１９】
本発明によれば、長さｎの入力ビット列で構成される入力ｘと、長さｋのビット列で構成される乱数ｒとを用いて、長さｍの出力ビット列で構成される出力ｙを生成する際に、それぞれの長さｎ、ｋ、ｍに特定の制限を持たせることにより、秘匿性増強データ処理を実行するに当たり、有限体乗算処理の性能向上を実現できる秘匿性増強アルゴリズムを備えた秘匿性増強装置および秘匿性増強データ処理方法を得ることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態４における高速乗算アルゴリズムを、秘匿性増強アルゴリズムを用いた量子暗号装置の受信機に適用した場合の構成例を示した図である。
【発明を実施するための形態】
【００２１】
以下、本発明の秘匿性増強装置および秘匿性増強データ処理方法の好適な実施の形態につき図面を用いて説明する。
【００２２】
まず始めに、本発明の概念について説明する。
有限体乗算処理の性能向上を実現する本発明のポイントとしては、以下の２点が挙げられる。
（ポイント１）双対ユニバーサルハッシュ関数の性質により、乱数の消費量を削減する。
（ポイント２）有限体乗算を巡回行列の乗算に変換し、計算量を削減する。
【００２３】
本発明の方式が成立する背景には、２０１１年に提案されている、ε−概「双対」ユニバーサルハッシュ関数（ε−ａｌｍｏｓｔ  ｄｕａｌ  ｕｎｉｖｅｒｓａｌ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ）という概念がある（例えば、非特許文献１参照）。このε−概「双対」ユニバーサルハッシュ関数は、安全性を損なわずに、従来のε−概ユニバーサルハッシュ関数を拡張する方法を示したものである。そして、この概念に従えば、従来方式では想定されていなかった関数を使用しつつ、無条件安全性を達成することができる。
【００２４】
実際、後述する関数は、ε−概双対ユニバーサルハッシュ関数であるが、従来のε−概ユニバーサルハッシュ関数には属さない。そして、無条件安全性は、保証しつつ、実装性能では、従来方式を凌駕している。
【００２５】
なお、以下では、量子暗号への応用を中心に述べるが、本方式は、それ以外にも、人工物メトリクス、生体認証など様々なセキュリティ分野に適用可能である（例えば、非特許文献２参照）。
【００２６】
本発明では、行列やベクトルの成分は、すべて有限体Ｆ２の元であるとする。したがって、値は、すべて０か１であり、乗算や加算は、ｍｏｄｕｌｏ  ２で行うとする。
【００２７】
以上の概念を踏まえ、本発明の具体的な構成を、実施の形態１〜５として、以下に詳述する。なお、以下の説明において用いる変数ｉ、ｊ、ｋ、ｌ、ｍ、ｎ、ｓ、ｔ、ｕは、０以上の整数を意味している。
【００２８】
実施の形態１．（有限体乗算による双対ユニバーサルハッシュ関数）
量子暗号を含む様々な暗号において、秘匿性増強と呼ばれるデータ処理が重要である。秘匿性増強には、従来、ユニバーサルハッシュ関数がもっぱら広く用いられてきた。これに対し、本願の発明者は、上述したように、２０１１年に非特許文献１において、「双対」ユニバーサルハッシュ関数という、より広いクラスのハッシュ関数を提案した。そして、さらに、この双対ユニバーサルハッシュ関数が、従来のユニバーサルハッシュ関数に勝るとも劣らない安全性を保証できることを示した。
【００２９】
そこで、本実施の形態１では、有限体乗算を用いた新たな双対ユニバーサルハッシュ関数の具体例について記述する。この方式を用いることにより、秘匿性増強における乱数消費量が、従来方式に比べ削減される。
【００３０】
なお、本実施の形態１の「双対」ユニバーサルハッシュ関数は、従来のユニバーサルハッシュ関数の条件を満たしておらず、従来のユニバーサルハッシュ関数の枠組みを外れた、真に新しいハッシュ関数である。
【００３１】
（方式の説明）
まず、入力は、長さｎのビット列ｘとし、出力は、長さｍのビット列ｙとする。ここで、ｎは、ｋ＝ｎ−ｍで割り切れ、ｎ＝ｔｋ、かつｔ＞２と表されるとする。また、本実施の形態１における方式のハッシュ関数は、長さｋのビット列ｒにより指定される。したがって、本ハッシュ関数を秘匿性増強に適用する場合には、秘匿性増強を行うたびに、長さｋの乱数ｒが消費される。
【００３２】
（ステップ１：入力ビット列の整形）
このようにして得られたビット列ｘを、長さｋのビット列に分割し、
ｘ＝（ｘ１、・・・、ｘｔ）
ｘｉ＝（ｘｉ１、・・・、ｘｉｋ）
とする。ここで、ｘｉは、長さｋのビット列、ｘｉｊは、ビット値である。
【００３３】
（ステップ２：有限体上の乗算）
長さｋのビット列ｘ１、・・・、ｘｔ、およびｒを、有限体ＧＦ（２ｋ）の元とみなし、ｉ＝１、・・・、ｔ−１について、ＧＦ（２ｋ）上で
ｙｉ＝ｘｉ＋ｒｉｘｔ
の演算を行い、ＧＦ（２ｋ）の元ｙ１、・・・、ｙｔ−１を得る。なお、ここで、ｒｉは、ｒのｉ乗を表す。
【００３４】
（ステップ３：出力）
再びｙ１、・・・、ｙｔ−１を長さｋのビット列とし、このビット列を連接して得られる長さｍ＝（ｔ−１）ｋのビット列
ｙ＝（ｙ１、・・・、ｙｔ−１）
をハッシュ関数の出力とする。
【００３５】
（実施の形態１の効果）
このハッシュ関数を秘匿性増強に用いた場合、消費する乱数のビット長は、ｎ−ｍ、つまり入力長と出力長ｍの差程度になる。一方で、従来用いられてきた方式（テープリッツ行列や有限体乗算を用いるもの）では、長さｍ程度の乱数が必要となる。したがって、ハッシュ関数の圧縮率ｍ／ｎが１／２より十分大きい場合に、乱数の消費量が劇的に削減される。
【００３６】
実施の形態２．（巡回行列を用いた有限体乗算アルゴリズム）
有限体の乗算は、ユニバーサルハッシュ関数を始め、様々な暗号アルゴリズムで広く用いられている。そこで、本実施の形態２では、この有限体の乗算を高速に実行する新たなアルゴリズムについて説明する。
【００３７】
有限体ＧＦ（２ｋ）の乗算には、通常の方式では、Ｏ（ｋ２）の時間がかかる。これに対して、本方式を用いると、Ｏ（ｋ  ｌｏｇ  ｋ）の時間で有限体乗算の演算処理が可能となる。ただし、サイズｋは、任意ではなく、以下の条件を満たす必要がある。
【００３８】
（有限体に対する条件）
本方式では、有限体ＧＦ（２ｋ）のうち、整数ｋが、以下の性質を持つものを対象とする。
・ｋ＋１が奇素数であり、有限体ＧＦ（ｋ＋１）の乗法群ＧＦ（ｋ＋１）×において、２が生成元となる。
なおＡｒｔｉｎ予想により、このようなｋは、無数に存在するとされている（例えば、非特許文献３の第２１章参照）。
また、コンピュータによる探索も容易に実行でき、１０５０以下の元であれば、通常のパーソナルコンピュータ上でＭａｔｈｅｍａｔｉｃａを用いて、１秒以下で生成できる。たとえば、このような整数ｋのうち、１０ｉ（ｉ＝１、．．．、１２）を下回らない最小の元を求めると、それぞれ
ｋ＝１０、
１００、
１０３  ＋  １８、
１０４  ＋  ３６、
１０５  ＋  ２、
１０６  ＋  ２、
１０７  ＋  １３８、
１０８  ＋  ３６、
１０９  ＋  ２０、
１０１０  ＋  １８、
１０１１  ＋  ２、
１０１２  ＋  ９０
であることがわかる。
【００３９】
（アルゴリズムの記述）
ＧＦ（２ｋ）の元ａ、ｂを入力し、その積ｃ＝ａｂを出力する。
【００４０】
ステップ１：入力ビット列の整形
ａ、ｂをビット列で表したものを
ａ＝（ａ０、・・・、ａｋ−１）
ｂ＝（ｂ０、・・・、ｂｋ−１）
とする。これらのパリティ
ａｋ＝ａ０＋・・・＋ａｋ−１  ｍｏｄ  ２
ｂｋ＝ｂ０＋・・・＋ｂｋ−１  ｍｏｄ  ２
を算出する。
【００４１】
そして、ａｋ、ｂｋをａ、ｂに連接したものを
Ａ＝（ａ０、・・・、ａｋ−１、ａｋ）
Ｂ＝（ｂ０、・・・、ｂｋ−１、ｂｋ）
とおく。
以下では、このようなビット列を、横ベクトルと同一視する。
【００４２】
ステップ２：行列とベクトルの乗算
まず、ビット列Ｘを第一行としてもつ、ｋ×ｋ巡回行列を、Ｍ（Ａ）とおく。Ｍ（Ａ）の具体的な成分は、下式の通りである。
【００４３】
【数１】
0006049589.tif 000002
【００４４】
この行列Ｍ（Ａ）とベクトルＢとを掛け合わせ、ｋ＋１ビットのベクトルＣを得る。
Ｃ＝（ｃ０、ｃ１、・・・、ｃｋ）＝ＢＭ（Ａ）
なお、この巡回行列とベクトルの乗算は、高速フーリエ変換を用いて、（Ｏ（ｋ  ｌｏｇ  ｋ）の計算時間で、高速に実行可能である（例えば、非特許文献４参照）。
【００４５】
ステップ３：出力ビット列の整形
ビット列Ｃの最後の成分ｃｋを削除した
ｃ＝（ｃ０、・・・、ｃｋ−１）
を乗算の結果として出力する。
【００４６】
（動作原理）
上述した方法で、ＧＦ（２ｋ）の乗算が実行できる理由について、以下に説明する。
ＧＦ（２ｋ）上の多項式
Ｆ（Ｘ）＝Ｘｋ＋１＋１
は、常に
Ｆ（Ｘ）＝（Ｘ＋１）（Ｘｋ＋Ｘｋ−１＋…＋Ｘ＋１）
＝（Ｘ＋１）Ｇ（Ｘ）
と分解できる。
【００４７】
そして、整数ｋが本方式の条件を満たす場合、Ｆ（Ｘ）の２つ目の因子Ｇ（Ｘ）が既約多項式になることを示すことができる。これに、中国人剰余定理を適用すると、ｍｏｄｕｌｏ  Ｆ（Ｘ）の多項式の乗算を実行することは、ｍｏｄｕｌｏ  Ｘ＋１の乗算とｍｏｄｕｌｏ  Ｇ（Ｘ）の乗算を同時に実行することと等価になることがわかる。
つまり、ｋ次以下の多項式
Ａ（Ｘ）＝Σｉ＝０ｋａｉＸｉ、Ｂ（Ｘ）＝Σｉ＝０ｋｂｉＸｉ
を掛け合わせて
Ａ（Ｘ）Ｂ（Ｘ）≡Ｃ（Ｘ）  ｍｏｄｕｌｏ  Ｆ（Ｘ）
という乗算を実行することは、
Ａ（Ｘ）Ｂ（Ｘ）≡Ｃ（Ｘ）  ｍｏｄｕｌｏ  Ｘ＋１
Ａ（Ｘ）Ｂ（Ｘ）≡Ｃ（Ｘ）  ｍｏｄｕｌｏ  Ｇ（Ｘ）
という２種類の乗算を実行することと等価である。
【００４８】
ｍｏｄｕｌｏ  Ｆ（Ｘ）の乗算は、巡回行列の乗算と等価である。また、Ｇ（Ｘ）がｋ次の既約多項式であることから、ｍｏｄｕｌｏ  Ｇ（Ｘ）の乗算は、ＧＦ（２ｋ）上の乗算と等価である。
一方で、ｍｏｄｕｌｏ  Ｘ＋１の乗算は常に０×０≡０という自明な結果を与える。なぜなら多項式Ａ（Ｘ）、Ｂ（Ｘ）の係数ａｉ、ｂｉは、段落００４０〜００４１の方法で生成されるため、それらのハミング重みは常に偶数であり、
Ａ（Ｘ）≡Ｂ（Ｘ）≡０  ｍｏｄｕｌｏ  Ｘ＋１
が成り立ち、その積Ｃ（Ｘ）も
Ｃ（Ｘ）≡０  ｍｏｄｕｌｏ  Ｘ＋１
を常に満たすからである。
したがって、巡回行列の乗算を実行することにより、ＧＦ（２ｋ）の乗算が実行できることになる。これが、本方式の動作原理である。
【００４９】
（実施の形態２の効果）有限体乗算の高速化
ＧＦ（２ｋ）の乗算には、通常、Ｏ（ｋ２）の時間がかかるが、本方式を用いると、Ｏ（ｋ  ｌｏｇ  ｋ）の時間で有限体乗算の実行が可能となる。これにより、ユニバーサルハッシュ関数を始め、様々な暗号アルゴリズムの処理を高速化できる。
【００５０】
実施の形態３．（双対ユニバーサルハッシュ関数の高速実装）
本実施の形態３では、先の実施の形態１と実施の形態２の方式を組み合わせ、乱数使用量と演算時間の両方の削減を実現する方式について説明する。
【００５１】
具体的には、実施の形態１における出力長ｍ、入力長ｎを適切に選び、ｋ＝ｍ−ｎが本実施の形態３で指定される次の条件を満たすようにする。つまり、「ｍ−ｎ＋１が奇素数であり、有限体ＧＦ（ｍ−ｎ＋１）の乗法群ＧＦ（ｍ−ｎ＋１）×において、２が生成元となるように、ｍ、ｎを選ぶ」という条件を満たしているとする。
【００５２】
そして、実施の形態１に含まれるＧＦ（２ｋ）上の乗算に、実施の形態２の高速アルゴリズムを使用する。また、加算を行うには、ＧＦ（２ｋ）の元をビット列表示したものを排他的論理和する。
【００５３】
実施の形態４．（従来型ユニバーサルハッシュ関数の高速実装１）
本実施の形態４では、有限体乗算を用いた従来型のユニバーサルハッシュ関数に、先の実施の形態２の高速乗算アルゴリズムを適用する場合について説明する。
【００５４】
（方式の説明）
入力は、長さｎのビット列ｘとし、それを有限体の元とみなして、長さｕのビット列で構成される乱数ｒを用いて演算を行い、長さｍのビット列ｙを得る。ここで、出力ビット数ｍは、先の実施の形態２におけるｋと同様の条件を満たすとする。つまり、「ｍ＋１が奇素数であり、有限体ＧＦ（ｍ＋１）の乗法群ＧＦ（ｍ＋１）×において２が生成元となる」という条件を満たしているとする。また、入力長ｎは、ｎ＞ｍを満たしているとし、ｓをｎ／ｍ以上の最小の整数とする。また、ｕがｍの整数倍であるとする。
【００５５】
このとき、本実施の形態４における方式のハッシュ関数は、長さ（ｓ−１）ｍのビット列ｒにより指定される。したがって、本ハッシュ関数を秘匿性増強に適用する場合には、秘匿性増強を行うたびに、長さ（ｓ−１）ｍの乱数列ｒが消費される。
【００５６】
（ステップ１：入力ビット列の整形）
入力ビットｘの長さｎが、ｍの倍数でないときは、ｍの倍数になるまでｘに０を連接する。このようにして得られたｘを、長さｍのビット列に分割し、
ｘ＝（ｘ０、・・・、ｘｓ−１）
ｘｉ＝（ｘｉ１、・・・、ｘｉｍ）
とする。ここで、ｘｉは、長さｍのビット列、ｘｉｊは、単一のビットである。
【００５７】
同様にして、乱数ｒを長さｍのビット列に分割し、
ｒ＝（ｒ１、・・・、ｒｓ−１）
ｒｉ＝（ｒｉ１、・・・、ｒｉｍ）
とする。
【００５８】
（ステップ２：有限体上の乗算）
長さｍのビット列ｘ１、・・・、ｘｓ、および乱数のビット列ｒ１、・・・、ｒｓ−１を、有限体ＧＦ（２ｍ）の元とみなして、以下の演算を行い、ＧＦ（２ｍ）の元ｙを得る。
ｙ＝ｘ０＋Σｉ＝１ｓ−１ｒｉｘｉ
＝ｘ０＋ｒ１ｘｌ＋ｒ２ｘ２＋…＋ｒｓ−１ｘｓ−１
【００５９】
この乗算において、先の実施の形態２のアルゴリズムを用いる。また、加算を行うには、ＧＦ（２ｍ）の元をビット列表示したものを、排他的論理和する。
【００６０】
（ステップ３：出力）
ｙを長さｍのビット列として出力する。
【００６１】
（実施の形態４の効果）秘匿性増強の処理速度の向上
有限体の乗算を用いた従来型のユニバーサルハッシュでは、乗算のためにＯ（ｍ２）の時間がかかるとされていた。これに対して、本方式では、高速乗算アルゴリズムを使用することで、計算量がＯ（ｍ  ｌｏｇ  ｍ）に削減されている。
【００６２】
次に、本実施の形態４で説明した高速乗算アルゴリズムの具体的な適用例について、図面を用いて説明する。図１は、本発明の実施の形態４における高速乗算アルゴリズムを、秘匿性増強アルゴリズムを用いた量子暗号装置の受信機に適用した場合の構成例を示した図である。図１に示した量子暗号装置１０は、光ファイバなどからなる量子通信路２０を介して、送信者とつながっている。
【００６３】
そして、量子暗号装置１０は、量子通信装置１１、誤り訂正装置１２、乱数生成器１３、および行列演算処理部１４を備えて構成されている。ここで、本実施の形態４で説明した高速乗算アルゴリズムは、行列演算処理部１４において用いられることとなる。
【００６４】
量子通信装置１１は、光子変調器や光子検出器からなる装置であり、量子通信路２０から送られてきた光信号を変調したうえで検出し、ふるい鍵をビット列として出力する。
【００６５】
誤り訂正装置１２は、量子通信路２０や量子通信装置１１の雑音に起因してふるい鍵に生じた誤りを、誤り訂正符号を用いて訂正するための計算機であり、パーソナルコンピュータ（ＰＣ）やＦＰＧＡからなる。そして、誤り訂正装置１２は、誤り訂正した結果として、訂正鍵ｋｒｅｃをビット列として出力する。この訂正鍵ｋｒｅｃをビット列が、上述した長さｎの入力ビットｘに相当する。
【００６６】
乱数生成器１３は、巡回行列Ｍ（Ｒｉ）を指定するための乱数ビット列を出力するためのもので（なお、Ｒｉは、ｍビットの乱数列ｒｉを、段落００４０の操作によりｍ＋１ビットに伸ばしたものを指す）、物理乱数発生器、もしくはＰＣやＦＰＧＡ上に実装した疑似乱数生成器からなる。ここで、乱数生成器１３は、上述した乱数のビット列ｒ１、・・・、ｒｓ−１を生成すればよい。
【００６７】
行列演算処理部１４は、乱数生成器１３で生成された乱数のビット列ｒ１、・・・、ｒｓ−１を、有限体ＧＦ（２ｍ）の元とみなして、上述した演算を行い、ＧＦ（２ｍ）の元ｙを得る。そして、行列演算処理部１４は、長さｍのビット列ｙを、秘密鍵ｋｓｅｃとして出力する。このようにして、秘匿性増強の処理速度の向上を図ることができる。
【００６８】
実施の形態５．（従来型ユニバーサルハッシュ関数の高速実装２）
本実施の形態５では、先の実施の形態４と同様に、有限体乗算を用いた従来型のユニバーサルハッシュ関数に、先の実施の形態２の高速乗算アルゴリズムを適用する場合の、別の具体例について説明する。
【００６９】
（方式の説明）
入力長ｎ、出力長ｍに対する条件、およびｓの定義は、先の実施の形態４と同様である。
【００７０】
一方で、本実施の形態５における方式のハッシュ関数は、長さｍのビット列ｒひとつのみで指定される。そして、本実施の形態５では、先の実施の形態４におけるｒｉ（ｉ＝１、・・・、ｓ−１で、各ｒｉは、ｍビットだったもの）のかわりに、ｒｉ（ｒのｉ乗のもの）を使用する。したがって、このようなハッシュ関数を秘匿性増強に適用する場合には、秘匿性増強を行うたびに、長さｍの乱数列ｒのみが消費される。
【００７１】
（ステップ１：入力ビット列の整形）
入力ビットｘに対する操作は、先の実施の形態４と同様である。つまり、入力ビットｘの長さｎが、ｍの倍数でないときは、ｍの倍数になるまでｘに０を連接する。このようにして得られたｘを、長さｍのビット列に分割し、
ｘ＝（ｘ０、・・・、ｘｓ−１）
ｘｉ＝（ｘｉ１、・・・、ｘｉｍ）
とする。ここで、ｘｉは、長さｍのビット列、ｘｉｊは、単一のビットである。
【００７２】
一方で、本実施の形態５における乱数ｒは、長さｍのビット列である。
ｒ＝（ｒ１、・・・、ｒｍ）
【００７３】
（ステップ２：有限体上の乗算）
長さｍのビット列ｘ１、・・・、ｘｓ、および乱数ｒを、有限体ＧＦ（２ｍ）の元とみなして、以下の演算を行い、ＧＦ（２ｍ）の元ｙを得る。
ｙ＝Σｉ＝０ｓ−１ｒｉｘｉ
＝ｘ０＋ｒｘｌ＋ｒ２ｘ２＋…＋ｒｓ−１ｘｓ−１
ここで、ｒｉは、ｒのｉ乗をあらわす。
【００７４】
この乗算において、先の実施の形態２のアルゴリズムを用いる。また、加算を行うには、ＧＦ（２ｍ）の元をビット列表示したものを、排他的論理和する。
【００７５】
（ステップ３：出力）
ｙを長さｍのビット列として出力する。
【００７６】
（実施の形態５の効果）秘匿性増強の処理速度の向上
有限体の乗算を用いた従来型のユニバーサルハッシュでは、乗算のためにＯ（ｍ２）の時間がかかるとされていた。これに対して、本方式では、高速乗算アルゴリズムを使用することで、計算量がＯ（ｍ  ｌｏｇ  ｍ）に削減されている。
【００７７】
なお、以上の説明では、標数２の有限体、つまりＧＦ（２ｋ）上の方式について説明したが、本発明は、これに限定されない。標数２を、一般の標数ｐ（ただし、ｐは、素数）の有限体ＧＦ（ｐｋ）上の方式に変更して、本願発明を適用することも可能である。
【符号の説明】
【００７８】
１０  量子暗号装置、１１  量子通信装置、１２  誤り訂正装置、１３  乱数生成器、１４  行列演算処理部、２０  量子通信路。
【図１】
0006049589.tif 000005