暗号化装置、復号化装置、暗号化方法及び復号化方法
【課題】 McEliece暗号方式において、暗号文を平文に対して冗長化する割合を低減することのできる暗号化装置を提供する。
【解決手段】 Ｎビットの平文ｐを公開鍵ＰＧＳで符号化してＭ（＞Ｎ）ビットの冗長化ベクトルを生成する符号化手段１５を有したMcEliece暗号方式の暗号化装置１０において、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、式（１）に基づいて、圧縮行列Ｈで冗長化ベクトルを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に公開鍵ＰＧＳで訂正できるレベルのベクトルを選択する圧縮手段１６を備える構成とした。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ…（１）
【解決手段】 Ｎビットの平文ｐを公開鍵ＰＧＳで符号化してＭ（＞Ｎ）ビットの冗長化ベクトルを生成する符号化手段１５を有したMcEliece暗号方式の暗号化装置１０において、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、式（１）に基づいて、圧縮行列Ｈで冗長化ベクトルを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に公開鍵ＰＧＳで訂正できるレベルのベクトルを選択する圧縮手段１６を備える構成とした。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ…（１）
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、McEliece暗号方式を改良した暗号方式を利用する暗号化装置、復号化装置、暗号化方法及び復号化方法に関する。
【背景技術】
【０００２】
公開鍵暗号方式として有名なＲＳＡ（Rivest Shamir Adleman）暗号方式では、素因数分解が困難であることに、安全性の基礎を置いている。この素因数分解に費やす計算量は、通常の計算機で実行すると膨大な時間を要するものである。したがって、この素因数分解は現実的には実行不可能と言われている。しかし、ＲＳＡ暗号方式には、他の攻撃法が存在する可能性が指摘されている。また、将来、飛躍的に計算速度の速い量子計算機などが開発された場合、安全性の基礎である素因数分解が容易に実行されてしまう危惧がある。そこで、ＲＳＡ暗号方式を代替する有望な公開暗号方式として、McEliece（マクリース）暗号方式が提案されている（例えば非特許文献１、非特許文献２）。
【０００３】
このMcEliece暗号方式は、ＲＳＡ暗号方式とは全く異なった立場で構成されており、Ｇｏｐｐａ（ゴッパ）符号やＬＤＰＣ（Low Density Parity Check Code）符号と呼ばれる線形の誤り訂正符号を利用したものである。具体的には、McEliece暗号方式は、暗号文の形式が所定の条件を満足する場合にだけ復号でき、暗号化の際に、平文を公開鍵で符号化した後、復号時に訂正できる範囲でノイズを付加して暗号文を生成する。なお、このノイズはある程度小さい（ノイズを表すベクトルの要素として「１」の個数が少ない）ものである。
【０００４】
また、McEliece暗号方式は、線形符号の復号が困難であることに、安全性の基礎を置いている。このMcEliece暗号方式では、（１）線形符号である公開鍵の因数分解が困難（構造的攻撃）である、（２）公開鍵のままでの復号が困難（復号攻撃）であるという２つの側面から研究されているが、どちらも現実的な計算資源による攻撃法が発見されていない。
【非特許文献１】R. McEliece， A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, 1978,vol.42-44,114-116
【非特許文献２】R. L. Rivest, A. Shamir,and L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM,21(2):120-126,February 1978
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のMcEliece暗号方式では、暗号化する際に冗長化される割合が非常に大きい。つまり、暗号文が平文より極端に長くなるという問題がある。そして、McEliece暗号方式では、圧縮そのものができなかった。
【０００６】
そこで、本発明では、前記した問題を解決し、McEliece暗号方式において、暗号文を平文に対して冗長化する割合を低減することのできる暗号化装置及び暗号化方法を提供することを目的とする。
また、本発明では、前記した暗号化装置または暗号化方法で暗号化された暗号文を復号することのできる復号化装置及び復号化方法を提供することを他の目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、請求項１に記載の暗号化装置は、第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化手段と、前記符号化データに基づいて暗号文を生成する暗号文生成手段とを有したMcEliece暗号方式の暗号化装置において、前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、前記暗号文生成手段は、式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択することを特徴とする。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【０００８】
かかる構成によれば、暗号化装置は、符号化手段によって、第１のビット長（Ｎ）を有する平文を、線形符号で符号化することにより、第１のビット長（Ｎ）よりも長い第２のビット長（Ｍ）を有する符号化データを生成する。そして、暗号化装置は、暗号文生成手段によって、予め定められている圧縮行列を用いて符号化データを歪みあり圧縮して、暗号文を生成する。生成される暗号文のビット長は圧縮行列の列数と等しいのでＹビットとなる。
その結果、従来の暗号化装置が、符号化データに対してこの符号化データと同じビット数のノイズを加えて第２のビット長（Ｍ）を有する暗号文を生成する場合と比較して、本発明の暗号化装置は、暗号文のビット長（Ｙ）を小さくすることができる。
【０００９】
ここで、式（１）は、暗号文ｃの定義式となっている。この式（１）における線形符号ＰＧＳは、公開鍵として公開されるが、この公開鍵を構成する行列要素であるＰ，Ｇ，Ｓは、それぞれ復号側以外には秘密にされる。
また、式（１）において、符号化データ（ＰＧＳ）ｐと歪みｎは共にＭビットであり、暗号文ｃに圧縮行列Ｈを作用させて生成するＨｃもＭビットである。この圧縮行列Ｈは縦長行列なので、圧縮行列Ｈを作用させると暗号文ｃは冗長化する（ビット数が大きくなる）ことになる。換言すれば、暗号化装置で生成される暗号文ｃは、圧縮行列Ｈに基づいて歪みあり圧縮されることとなる。
【００１０】
また、暗号文生成手段は、式（１）に基づいて、符号化データ（ＰＧＳ）ｐと圧縮行列Ｈとを利用して暗号文ｃを生成する際に、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に線形符号で訂正できるレベルのベクトルを選択する。このとき、歪みを示すベクトルｎは零ベクトルに近似して「０」の要素を多数含むものであり、暗号文生成手段は、歪みｎと暗号文ｃとの最適な組を選択する。また、このようにできるように、圧縮行列の次元（行数、列数）や要素を予め定めておく。また、ベクトルｎができるだけ零ベクトルに近似するようにするための距離の尺度としてハミング距離を利用する。なお、訂正とは、従来のMcEliece暗号方式で付加するノイズに相当する「歪み」を訂正することを意味する。また、歪みあり圧縮は、不可逆圧縮または損失性圧縮を意味する。
【００１１】
請求項２に記載の暗号化装置は、請求項１に記載の暗号化装置において、前記暗号文生成手段が、前記符号化データの要素の値をイジング型の値に変換する第１データ変換手段と、前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出手段と、前記圧縮要素の符号をイジング型の値に変換する符号変換手段と、前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換手段とを備えることを特徴とする。
【００１２】
かかる構成によれば、暗号化装置において、暗号文生成手段は、第１データ変換手段によって、符号化データの要素として例えば２進の論理値で表された「０」と「１」を、統計力学で用いるイジング型のアップスピン及びダウンスピンの値に対応した「＋１」と「−１」にそれぞれ変換する。そして、暗号文生成手段は、圧縮要素算出手段によって、イジング型の値に変換された要素、圧縮行列、及び、所定値に基づいて、符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する。ここで、所定値は、歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化されている。このように最適化するためには、例えばスピングラスなどにおいて、自由エネルギー等を算出する際の統計力学的な手法を用いることができる。そして、暗号文生成手段は、符号変換手段によって、圧縮要素の符号をイジング型の値に変換する。この符号変換手段は、例えば入力値の符号が正ならば「＋１」、入力値の符号が負ならば「−１」をそれぞれ出力する。そして、暗号文生成手段は、第２データ変換手段によって、イジング型の値として変換された符号を論理型の値に変換する。これによって、歪みあり圧縮された暗号文を生成することができる。
【００１３】
請求項３に記載の復号化装置は、請求項１または請求項２に記載の暗号化装置を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置であって、前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元手段と、前記復元されたビット長の復元データを、前記線形符号で復号化する復号化手段とを有することを特徴とする。
【００１４】
かかる構成によれば、復号化装置は、復元手段によって、暗号文に圧縮行列を作用させた復元データを生成することにより、暗号文のビット長（Ｙ）を、符号化データのビット長（Ｍ）に復元する。そして、復号化装置は、復号化手段によって、復元されたビット長（Ｍ）の復元データを、線形符号で復号化する。これにより、線形符号で暗号化される前の平文を生成することができる。ここで、暗号文に圧縮行列を作用させるには、前記した式（１）に基づいて、圧縮行列Ｈを暗号文ｃに左からかける。この演算により容易に圧縮を解除することができる。
【００１５】
請求項４に記載の暗号化方法は、第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化ステップと、前記符号化データに基づいて暗号文を生成する暗号文生成ステップとを有したMcEliece暗号方式の暗号化装置の暗号化方法において、前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、前記暗号文生成ステップは、式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択することを特徴とする。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【００１６】
このような手順によれば、暗号化装置は、符号化ステップで、第１のビット長（Ｎ）を有する平文を、線形符号で符号化することにより、第１のビット長（Ｎ）よりも長い第２のビット長（Ｍ）を有する符号化データを生成する。そして、暗号化装置は、暗号文生成ステップで、予め定められている圧縮行列を用いて符号化データを歪みあり圧縮して、暗号文を生成する。生成される暗号文のビット長は圧縮行列の列数と等しいのでＹビットとなる。
その結果、従来の暗号化方法において、符号化データに対してこの符号化データと同じビット数のノイズを加えて第２のビット長（Ｍ）を有する暗号文を生成する場合と比較して、本発明の暗号化方法は、暗号文のビット数（Ｙ）を小さくすることができる。
【００１７】
請求項５に記載の暗号化方法は、請求項４に記載の暗号化方法において、前記暗号文生成ステップが、前記符号化データの要素の値をイジング型の値に変換する第１データ変換ステップと、前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出ステップと、前記圧縮要素の符号をイジング型に変換する符号変換ステップと、前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換ステップとをさらに有することを特徴とする。
【００１８】
このような手順によれば、暗号化装置は、暗号文生成ステップにおいて、第１データ変換ステップで、符号化データの要素として例えば２進の論理値で表された「０」と「１」を、統計力学で用いるイジング型のアップスピン及びダウンスピンの値に対応した「＋１」と「−１」に変換する。続いて、暗号化装置は、圧縮要素算出ステップで、イジング型の値に変換された要素、圧縮行列、及び、所定値に基づいて、符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する。そして、暗号化装置は、符号変換ステップで、圧縮要素の符号をイジング型の値に変換する。続いて、暗号化装置は、第２データ変換ステップで、イジング型の値として変換された符号を論理型の値に変換する。これによって、歪みあり圧縮された暗号文を生成することができる。
【００１９】
請求項６に記載の復号化方法は、請求項４または請求項５に記載の暗号化方法を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置の復号化方法であって、前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元ステップと、前記復元されたビット長の復元データを、前記線形符号で復号化する復号化ステップとを有することを特徴とする。
【００２０】
このような手順によれば、復号化装置は、復元ステップで、暗号文に圧縮行列を作用させた復元データを生成することにより、暗号文のビット長（Ｙ）を、符号化データのビット長（Ｍ）に復元する。続いて、復号化ステップで、復元されたビット長（Ｍ）の復元データを、線形符号で復号化する。これにより、線形符号で暗号化される前の平文を生成することができる。
【発明の効果】
【００２１】
本発明によれば、McEliece暗号方式において、暗号文を平文に対して冗長化する割合を低減することができる。その結果、暗号文を送信する際の通信コストを低減することができる。また、本発明によれば、平文に対して冗長化する割合を低減した暗号文を容易に復号することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態について、適宜図面を参照しながら説明する。図１は、本発明の実施形態に係る暗号化装置と復号化装置とを含む通信システムの構成例を示す図である。
［通信システムの構成］
図１に示すように、この通信システム１では、例えばインターネット等の通信路２を介して、暗号化装置１０と、復号化装置２０とが接続されている。これらの各装置１０，２０は、一般的なコンピュータ（計算機）であり、例えば、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ＨＤＤ（Hard Disk Drive）と、ＫＢ／ＣＲＴ（Key Board／Cathode Ray Tube）と、通信インタフェースとを含んで構成されている。以下に、各装置１０，２０の機能を詳細に説明する。
【００２３】
［暗号化装置の機能］
暗号化装置１０は、次式（１）に基づいて、式（２）で示される暗号化演算ｆを実行し、平文ｐから暗号文ｃを生成するものである。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
ｆ（ｐ｜ＰＧＳ，Ｈ）∈｛∃ｎ，（ＰＧＳ）ｐ＋ｎ＝Ｈｃ｝…（２）
ここで、平文ｐのビット長（第１のビット長）をＮ、Ｎより大きいビット長（第２のビット長）をＭ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、線形符号をＰＧＳ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨ、歪みあり圧縮で生じる歪みをｎとした。
【００２４】
暗号化装置１０は、図１に示すように、入力手段１１と、記憶手段（ＲＡＭ等）１２と、制御手段（ＣＰＵ等）１３と、出力手段１４とを備える。
入力手段１１は、平文ｐを入力し、制御手段１３に出力するものである。
記憶手段１２は、半導体メモリや磁気メモリなどの書き換え可能な記憶手段であり、制御手段１３による演算処理等に利用されると共に、入力手段１１を介して取得した情報等を記憶するものである。
制御手段１３は、前記した入力手段１１、記憶手段１２及び出力手段１４を制御すると共に、平文ｐから暗号文ｃを生成するものである。
出力手段１４は、生成された暗号文ｃを復号化装置２０に送信するものである。
【００２５】
制御手段１３は、図１に示すように、符号化手段１５と、圧縮手段１６とを備える。
符号化手段１５は、入力された平文ｐを公開鍵Ｇ′（＝線形符号ＰＧＳ）で符号化することによりビット長が長くなった（冗長化された）冗長化ベクトル（符号化データ）Ａを生成するものである。この冗長化ベクトルＡは、前記した式（１）の（ＰＧＳ）ｐと等しいものである。ここで、公開鍵Ｇ′は例えばＧｏｐｐａ符号やＬＤＰＣ（Low Density Parity Check Code）符号等である。なお、公開鍵Ｇ′はＬＤＰＣ符号の場合、疎行列（行列内の多くの要素が「０」である行列）である。
【００２６】
圧縮手段（暗号文生成手段）１６は、予め定められた圧縮行列Ｈに基づいて、冗長化ベクトルＡを歪みあり圧縮することにより、暗号文ｃを生成する（圧縮処理を実行する）ものである。この圧縮手段１６は、暗号文ｃを生成する際に、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に公開鍵Ｇ′で訂正できるレベルのベクトルを選択する。
なお、前記した符号化手段１５及び圧縮手段１６は、ＣＰＵが記憶手段１２のＲＯＭに格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００２７】
［圧縮手段の機能］
次に、図１に示した圧縮手段１６の機能を説明する。この圧縮手段１６は、前記した式（１）の別の表現である式（１ａ）で示される方程式で、暗号文ｃを生成する。
Ｈｃ＝Ａ＋ｎ …（１ａ）
式（１ａ）に示した冗長化ベクトルＡは、現実的には例えば数千〜数万ビットの長さを有している。しかしながら、式（１ａ）を簡単に説明するために、以下では、暗号化装置１０は、符号化手段１５によって、２ビット（Ｎ＝２）の平文ｐを符号化して４ビット（Ｎ＝４）の冗長化ベクトルＡを生成したと仮定する場合を例示する。ここで、圧縮行列Ｈは、式（３）で示されるように要素「１」が配置された４×３型の行列とする（Ｙ＝３）。また、冗長化ベクトルＡは式（４）で示される。
【００２８】
【数１】
【００２９】
【数２】
【００３０】
この場合に、圧縮手段１６は、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に公開鍵Ｇ′で訂正できるレベルのベクトルを選択するために、式（１ａ），式（３）及び式（４）に基づいて、暗号文ｃを示すベクトルと共に、歪みを示すベクトルｎとして、零ベクトルに近似して「０」の要素を多数含むものを選択する。すなわち、ベクトルｎができるだけ零ベクトルに近づくようにする。そして、圧縮手段１６は、最適な組として、式（５）で示される暗号文ｃと、式（６）で示される歪みｎとを選択する。この場合、ベクトルｎの大きさ（「１」の個数）が冗長化ベクトルＡと、式（１ａ）の左辺のベクトルＨｃとのハミング距離（Hamming distance）になっている。
【００３１】
【数３】
【００３２】
【数４】
【００３３】
つまり、圧縮手段１６は、４ビットの冗長化ベクトルＡから、３ビット（Ｙ＝３）に圧縮された暗号文ｃを生成する。そして、この圧縮された暗号文ｃが復号化装置２０に送信される。
この例では、式（１ａ）は、式（７）のように表現されることになる。
【００３４】
【数５】
【００３５】
一方、この例では、従来のMcEliece暗号方式は、４ビットの冗長化ベクトルＡに対して、式（６）で示した４ビットのノイズを付加するものに相当する。すなわち、式（７）の最右辺で表される４ビットのベクトルを暗号文として送信することになる。なお、従来のMcEliece暗号方式において付加するノイズと、本実施形態において歪みあり圧縮で生じる歪みｎとは、同一視できるが、それぞれの候補は複数あり、単純に一対一に対応しているものではない。
【００３６】
したがって、式（２）で特徴付けられる暗号化演算ｆを実行する暗号化装置１０は、暗号文ｃを平文ｐに対して冗長化する割合を、従来のMcEliece暗号方式で暗号化する場合と比較して低減することができる。その結果、暗号文を送信する際の通信コストを低減できるという効果を奏する。
【００３７】
［圧縮手段の構成例］
次に、図１に示した圧縮手段１６の構成例を説明する。図２は、図１に示した圧縮手段の構成例を示すブロック図である。
この例では、圧縮手段１６は、前記した式（１ａ）の方程式を統計力学的手法を用いて解くことにより、入力する冗長化ベクトルＡから最適な暗号文ｃを生成するものであり、図２に示すように、第１データ変換手段３１と、圧縮要素算出手段３２と、符号変換手段３３と、第２データ変換手段３４とを備える。
【００３８】
第１データ変換手段３１は、符号化手段１５の出力する冗長化ベクトルＡの要素として例えば２進の論理値で表された「０」と「１」を、統計力学で用いるイジング型のアップスピン及びダウンスピンの値に対応した「＋１」と「−１」にそれぞれ変換するものである。なお、冗長化ベクトルＡの変換されたｉ番目の要素をｑiと表記する。
【００３９】
圧縮要素算出手段３２は、イジング型の値に変換された要素、圧縮行列Ｈ、及び、歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値β，γに基づいて、冗長化ベクトルＡを圧縮した１次元配列データｍの要素である圧縮要素をそれぞれ算出するものである。ここで、１次元配列データｍのｊ番目の圧縮要素をｍjと表記する。また、所定値βを最適化するとは、前記した式（１ａ）においてベクトルｎが零ベクトルに最も近似する形に最適化されていることに相当する。
【００４０】
具体的には、この圧縮要素算出手段３２は、１次元配列データの圧縮要素ｍjを算出するために、式（８），（９）でそれぞれ示される変数
【数６】
（ｍijハット）及びｍijと共に利用される式（１０）を逐次更新的に用いる。
【００４１】
【数７】
【００４２】
【数８】
【００４３】
【数９】
【００４４】
式（８）〜（１０）において、ｍj，ｍij，およびｍij（ハット）は毎回更新される動的変数である。所定値β，γは、歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化されている。このように最適化するためには、例えばスピングラスなどにおいて、自由エネルギー等を算出する際の統計力学的な手法を用いることができる。
【００４５】
圧縮要素算出手段３２で利用する圧縮行列Ｈは、ＬＤＰＣ行列であり、そのｉ行ｊ列の要素をｈijと表記する。圧縮行列Ｈは、非ゼロ要素として各行Ｋ個の「１」と、各列Ｃ個の「１」だけを有し、その他の要素は「０」である。すなわち、圧縮率ＲはＫ／Ｃである。
また、前記した式（８）において、集合Ｍ（ｉ）は、次式（１１）で定義されている。なお、記号＼（バックスラッシュ）は要素の排除を意味する。
【００４６】
Ｍ（ｉ）＝｛ｊ｜ｈij＝１｝ …（１１）
【００４７】
また、前記した式（９）及び（１０）において、集合Ｌ（ｊ）は、次式（１２）で定義されている。なお、記号＼（バックスラッシュ）は要素の排除を意味する。
【００４８】
Ｌ（ｊ）＝｛ｉ｜ｈij＝１｝ …（１２）
【００４９】
符号変換手段３３は、次式（１３）に基づいて、１次元配列データの圧縮要素ｍjの符号をイジング型の値にそれぞれ変換するものである。圧縮要素ｍjはそれぞれ、「−１」と「１」の間の任意の値をとる。ここで、変換されたｊ番目の要素をｗjと表記する。また、関数ｓｉｇｎは、引数の符号が正ならば「＋１」、引数の符号が負ならば「−１」をそれぞれ出力するものである。
【００５０】
ｗj＝ｓｉｇｎ（ｍj） …（１３）
【００５１】
第２データ変換手段３４は、イジング型の値として変換された要素ｗjの値「＋１」及び「−１」を、論理型の値「０」と「１」にそれぞれ変換し、暗号文ｃ（ベクトル）の要素（暗号文ｃのｊ番目の要素をｃjと表記する）を生成するものである。
【００５２】
［復号化装置の機能］
図１に戻って、復号化装置２０の機能を説明する。
復号化装置２０は、暗号化装置１０を用いて圧縮行列Ｈで歪みあり圧縮により生成された暗号文ｃを復号化して平文ｐを生成するものであり、入力手段２１と、記憶手段（ＲＡＭ等）２２と、制御手段（ＣＰＵ等）２３と、出力手段２４とを備える。
入力手段２１は、暗号文ｃを入力し、制御手段２３に出力するものである。
記憶手段２２は、半導体メモリや磁気メモリなどの書き換え可能な記憶手段であり、制御手段２３による演算処理等に利用されると共に、入力手段２１を介して取得した情報等を記憶するものである。
制御手段２３は、前記した入力手段２１、記憶手段２２及び出力手段２４を制御すると共に、暗号文ｃから平文ｐを生成するものである。
出力手段２４は、生成された平文ｐを出力するものである。
【００５３】
制御手段２３は、図１に示すように、復元手段２５と、復号化手段２６とを備える。
復元手段２５は、受信した暗号文ｃに圧縮行列Ｈをかけて、冗長化ベクトルＡの次元に復元することにより、暗号文ｃのビット長（Ｙ）を、冗長化ベクトルＡのビット長（Ｍ）に復元するものである。この復元手段２５は、具体的には、前記した式（１ａ）の左辺で示される演算を実行する。
復号化手段２６は、復元されたビット長（Ｍ）のベクトル（復元データ）Ｈｃを、公開鍵Ｇ′で復号化し、元のビット長（Ｎ）の平文ｐを生成するものである。
なお、前記した復元手段２５及び復号化手段２６は、ＣＰＵが記憶手段２２のＲＯＭに格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００５４】
［暗号化装置の動作］
次に、暗号化装置の動作について図３を参照（適宜図１参照）して説明する。図３は、図１に示した暗号化装置の動作を示すフローチャートである。
暗号化装置１０は、入力手段１１によって、平文ｐを入力し（ステップＳ１）、符号化手段１５によって、入力された平文ｐを公開鍵Ｇ′で冗長化し、冗長化ベクトルＡを生成し（ステップＳ２：符号化ステップ）、圧縮手段１６に出力する。
【００５５】
続いて、暗号化装置１０は、圧縮手段１６によって、圧縮処理を実行する（ステップＳ３：暗号文生成ステップ）。すなわち、圧縮手段１６は、冗長化ベクトルＡを歪みあり圧縮することにより、Ｙビットの暗号文ｃを生成する。そして、暗号化装置１０は、出力手段１４によって、暗号文ｃを復号化装置２０に送信する（ステップＳ４）。
【００５６】
［圧縮手段の動作］
次に、前記したステップＳ３の圧縮処理について図４を参照（適宜図２参照）して説明する。図４は、図３に示した圧縮処理を示すフローチャートである。
圧縮手段１６は、第１データ変換手段３１によって、入力データ（冗長化ベクトルＡ）の要素の値（０，１）をイジング型の値（−１，１）に変換し（ステップＳ１１：第１データ変換ステップ）、圧縮要素算出手段３２に出力する。
【００５７】
圧縮要素算出手段３２は、イジング型の値に変換された要素ｑi、圧縮行列Ｈ、及び、所定値β，γに基づいて、冗長化ベクトルＡを圧縮した１次元配列データの要素である圧縮要素ｍjをそれぞれ算出し（ステップＳ１２：圧縮要素算出ステップ）、符号変換手段３３に出力する。このとき、圧縮要素算出手段３２は、前記した式（８）〜式（１０）で示されるｍijハット，ｍij及び圧縮要素ｍjを逐次更新的に用いて圧縮要素ｍjをそれぞれ算出する。
【００５８】
そして、符号変換手段３３は、入力した１次元配列データの圧縮要素ｍjの符号をそれぞれ、前記した式（１３）に基づいて、イジング型の値（−１，１）に変換し（ステップＳ１３：符号変換ステップ）、第２データ変換手段３４に出力する。そして、第２データ変換手段３４によって、イジング型の値（−１，１）に変換された符号（−１，１）を論理型の値（０，１）に変換し、暗号文ｃ（ベクトル）の要素を生成する（ステップＳ１４：第２データ変換ステップ）。
【００５９】
［復号化装置の動作］
次に、復号化装置の動作について図５を参照（適宜図１参照）して説明する。図５は、図１に示した復号化装置の動作を示すフローチャートである。
復号化装置２０は、入力手段２１によって、暗号文ｃを入力し（ステップＳ２１）、復元手段２５によって、受信した暗号文ｃに圧縮行列Ｈをかけて、冗長化ベクトルＡの次元に復元することにより、暗号文ｃのビット長（Ｙ）を、冗長化ベクトルＡのビット長（Ｍ）に復元し（ステップＳ２２：復元ステップ）、復号化手段２６に出力する。このとき、復元手段２５は、前記した式（１ａ）の左辺の演算を実行し、例えば前記した式（７）の最右辺で表されるようなベクトルを生成する。
【００６０】
続いて、復号化装置２０は、復号化手段２６によって、復元されたビット長（Ｍ）のベクトル（復元データ）Ｈｃを公開鍵Ｇ′で復号化し、元のビット長（Ｎ）の平文ｐを生成する（ステップＳ２３：復号化ステップ）。そして、復号化装置２０は、出力手段２４によって、生成した平文ｐを出力する（ステップＳ２４）。
【００６１】
なお、ベクトルＨｃを公開鍵Ｇ′で復号化する操作ｇ′は公知の手法を用いて以下のように実行される。まず、第１段階では次式（１４）の関係式で示される操作を実行する。すなわち、ＭビットのベクトルＨｃを、公開鍵Ｇ′の構成要素である置換行列Ｐで前処理してベクトル（Ｐ-1Ｈｃ）を生成する。なお、この前処理（置換行列Ｐによる操作）は、歪みｎのレベルを保存する。
【００６２】
Ｐ-1Ｈｃ＝Ｇ（Ｓｐ）＋Ｐ-1ｎ …（１４）
【００６３】
次に、第２段階では次式（１５）の関係式で示される操作を実行する。すなわち、前記した式（１４）の左辺で示した生成ベクトル（Ｐ-1Ｈｃ）を、公開鍵Ｇ′の構成要素である生成行列Ｇによって復号する復号操作ｇを実行することによって所定範囲で歪みｎを除去し、さらに、公開鍵Ｇ′の構成要素である生成行列Ｇによって元のビット数（Ｎ）の平文ｐを逆算する。なお、この復号操作ｇは非公開の生成行列Ｇにのみ有効である。
【００６４】
ｐ＝ｇ′（Ｈｃ｜Ｇ′）＝Ｓ-1［ｇ（Ｐ-1Ｈｃ｜Ｇ）］ …（１５）
【００６５】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、本実施形態では、暗号化装置１０の符号化手段１５は、公開鍵Ｇ′をＧｏｐｐａ符号やＬＤＰＣ符号等で符号化するものとして説明したが、例示した従来から実装される線形符号に限定されず、任意の線形符号を利用することができる。
また、暗号化装置１０の圧縮手段１６は、圧縮要素算出手段３２によって、予め最適化された所定値βを利用して１次元配列データの圧縮要素ｍjを算出するものとして説明したが、所定値βを最適化する処理を実行する構成を付加するようにしてもよい。
【図面の簡単な説明】
【００６６】
【図１】本発明の実施形態に係る暗号化装置と復号化装置とを含む通信システムの構成例を示す図である。
【図２】図１に示した圧縮手段の構成例を示すブロック図である。
【図３】図１に示した暗号化装置の動作を示すフローチャートである。
【図４】図３に示した圧縮処理を示すフローチャートである。
【図５】図１に示した復号化装置の動作を示すフローチャートである。
【符号の説明】
【００６７】
１ 通信システム
２ 通信路
１０ 暗号化装置
１１ 入力手段
１２ 記憶手段
１３ 制御手段
１４ 出力手段
１５ 符号化手段
１６ 圧縮手段（暗号文生成手段）
２０ 復号化装置
２１ 入力手段
２２ 記憶手段
２３ 制御手段
２４ 出力手段
２５ 復元手段
２６ 復号化手段
３１ 第１データ変換手段
３２ 圧縮要素算出手段
３３ 符号変換手段
３４ 第２データ変換手段
【技術分野】
【０００１】
本発明は、McEliece暗号方式を改良した暗号方式を利用する暗号化装置、復号化装置、暗号化方法及び復号化方法に関する。
【背景技術】
【０００２】
公開鍵暗号方式として有名なＲＳＡ（Rivest Shamir Adleman）暗号方式では、素因数分解が困難であることに、安全性の基礎を置いている。この素因数分解に費やす計算量は、通常の計算機で実行すると膨大な時間を要するものである。したがって、この素因数分解は現実的には実行不可能と言われている。しかし、ＲＳＡ暗号方式には、他の攻撃法が存在する可能性が指摘されている。また、将来、飛躍的に計算速度の速い量子計算機などが開発された場合、安全性の基礎である素因数分解が容易に実行されてしまう危惧がある。そこで、ＲＳＡ暗号方式を代替する有望な公開暗号方式として、McEliece（マクリース）暗号方式が提案されている（例えば非特許文献１、非特許文献２）。
【０００３】
このMcEliece暗号方式は、ＲＳＡ暗号方式とは全く異なった立場で構成されており、Ｇｏｐｐａ（ゴッパ）符号やＬＤＰＣ（Low Density Parity Check Code）符号と呼ばれる線形の誤り訂正符号を利用したものである。具体的には、McEliece暗号方式は、暗号文の形式が所定の条件を満足する場合にだけ復号でき、暗号化の際に、平文を公開鍵で符号化した後、復号時に訂正できる範囲でノイズを付加して暗号文を生成する。なお、このノイズはある程度小さい（ノイズを表すベクトルの要素として「１」の個数が少ない）ものである。
【０００４】
また、McEliece暗号方式は、線形符号の復号が困難であることに、安全性の基礎を置いている。このMcEliece暗号方式では、（１）線形符号である公開鍵の因数分解が困難（構造的攻撃）である、（２）公開鍵のままでの復号が困難（復号攻撃）であるという２つの側面から研究されているが、どちらも現実的な計算資源による攻撃法が発見されていない。
【非特許文献１】R. McEliece， A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, 1978,vol.42-44,114-116
【非特許文献２】R. L. Rivest, A. Shamir,and L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM,21(2):120-126,February 1978
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のMcEliece暗号方式では、暗号化する際に冗長化される割合が非常に大きい。つまり、暗号文が平文より極端に長くなるという問題がある。そして、McEliece暗号方式では、圧縮そのものができなかった。
【０００６】
そこで、本発明では、前記した問題を解決し、McEliece暗号方式において、暗号文を平文に対して冗長化する割合を低減することのできる暗号化装置及び暗号化方法を提供することを目的とする。
また、本発明では、前記した暗号化装置または暗号化方法で暗号化された暗号文を復号することのできる復号化装置及び復号化方法を提供することを他の目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、請求項１に記載の暗号化装置は、第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化手段と、前記符号化データに基づいて暗号文を生成する暗号文生成手段とを有したMcEliece暗号方式の暗号化装置において、前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、前記暗号文生成手段は、式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択することを特徴とする。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【０００８】
かかる構成によれば、暗号化装置は、符号化手段によって、第１のビット長（Ｎ）を有する平文を、線形符号で符号化することにより、第１のビット長（Ｎ）よりも長い第２のビット長（Ｍ）を有する符号化データを生成する。そして、暗号化装置は、暗号文生成手段によって、予め定められている圧縮行列を用いて符号化データを歪みあり圧縮して、暗号文を生成する。生成される暗号文のビット長は圧縮行列の列数と等しいのでＹビットとなる。
その結果、従来の暗号化装置が、符号化データに対してこの符号化データと同じビット数のノイズを加えて第２のビット長（Ｍ）を有する暗号文を生成する場合と比較して、本発明の暗号化装置は、暗号文のビット長（Ｙ）を小さくすることができる。
【０００９】
ここで、式（１）は、暗号文ｃの定義式となっている。この式（１）における線形符号ＰＧＳは、公開鍵として公開されるが、この公開鍵を構成する行列要素であるＰ，Ｇ，Ｓは、それぞれ復号側以外には秘密にされる。
また、式（１）において、符号化データ（ＰＧＳ）ｐと歪みｎは共にＭビットであり、暗号文ｃに圧縮行列Ｈを作用させて生成するＨｃもＭビットである。この圧縮行列Ｈは縦長行列なので、圧縮行列Ｈを作用させると暗号文ｃは冗長化する（ビット数が大きくなる）ことになる。換言すれば、暗号化装置で生成される暗号文ｃは、圧縮行列Ｈに基づいて歪みあり圧縮されることとなる。
【００１０】
また、暗号文生成手段は、式（１）に基づいて、符号化データ（ＰＧＳ）ｐと圧縮行列Ｈとを利用して暗号文ｃを生成する際に、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に線形符号で訂正できるレベルのベクトルを選択する。このとき、歪みを示すベクトルｎは零ベクトルに近似して「０」の要素を多数含むものであり、暗号文生成手段は、歪みｎと暗号文ｃとの最適な組を選択する。また、このようにできるように、圧縮行列の次元（行数、列数）や要素を予め定めておく。また、ベクトルｎができるだけ零ベクトルに近似するようにするための距離の尺度としてハミング距離を利用する。なお、訂正とは、従来のMcEliece暗号方式で付加するノイズに相当する「歪み」を訂正することを意味する。また、歪みあり圧縮は、不可逆圧縮または損失性圧縮を意味する。
【００１１】
請求項２に記載の暗号化装置は、請求項１に記載の暗号化装置において、前記暗号文生成手段が、前記符号化データの要素の値をイジング型の値に変換する第１データ変換手段と、前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出手段と、前記圧縮要素の符号をイジング型の値に変換する符号変換手段と、前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換手段とを備えることを特徴とする。
【００１２】
かかる構成によれば、暗号化装置において、暗号文生成手段は、第１データ変換手段によって、符号化データの要素として例えば２進の論理値で表された「０」と「１」を、統計力学で用いるイジング型のアップスピン及びダウンスピンの値に対応した「＋１」と「−１」にそれぞれ変換する。そして、暗号文生成手段は、圧縮要素算出手段によって、イジング型の値に変換された要素、圧縮行列、及び、所定値に基づいて、符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する。ここで、所定値は、歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化されている。このように最適化するためには、例えばスピングラスなどにおいて、自由エネルギー等を算出する際の統計力学的な手法を用いることができる。そして、暗号文生成手段は、符号変換手段によって、圧縮要素の符号をイジング型の値に変換する。この符号変換手段は、例えば入力値の符号が正ならば「＋１」、入力値の符号が負ならば「−１」をそれぞれ出力する。そして、暗号文生成手段は、第２データ変換手段によって、イジング型の値として変換された符号を論理型の値に変換する。これによって、歪みあり圧縮された暗号文を生成することができる。
【００１３】
請求項３に記載の復号化装置は、請求項１または請求項２に記載の暗号化装置を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置であって、前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元手段と、前記復元されたビット長の復元データを、前記線形符号で復号化する復号化手段とを有することを特徴とする。
【００１４】
かかる構成によれば、復号化装置は、復元手段によって、暗号文に圧縮行列を作用させた復元データを生成することにより、暗号文のビット長（Ｙ）を、符号化データのビット長（Ｍ）に復元する。そして、復号化装置は、復号化手段によって、復元されたビット長（Ｍ）の復元データを、線形符号で復号化する。これにより、線形符号で暗号化される前の平文を生成することができる。ここで、暗号文に圧縮行列を作用させるには、前記した式（１）に基づいて、圧縮行列Ｈを暗号文ｃに左からかける。この演算により容易に圧縮を解除することができる。
【００１５】
請求項４に記載の暗号化方法は、第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化ステップと、前記符号化データに基づいて暗号文を生成する暗号文生成ステップとを有したMcEliece暗号方式の暗号化装置の暗号化方法において、前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、前記暗号文生成ステップは、式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択することを特徴とする。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【００１６】
このような手順によれば、暗号化装置は、符号化ステップで、第１のビット長（Ｎ）を有する平文を、線形符号で符号化することにより、第１のビット長（Ｎ）よりも長い第２のビット長（Ｍ）を有する符号化データを生成する。そして、暗号化装置は、暗号文生成ステップで、予め定められている圧縮行列を用いて符号化データを歪みあり圧縮して、暗号文を生成する。生成される暗号文のビット長は圧縮行列の列数と等しいのでＹビットとなる。
その結果、従来の暗号化方法において、符号化データに対してこの符号化データと同じビット数のノイズを加えて第２のビット長（Ｍ）を有する暗号文を生成する場合と比較して、本発明の暗号化方法は、暗号文のビット数（Ｙ）を小さくすることができる。
【００１７】
請求項５に記載の暗号化方法は、請求項４に記載の暗号化方法において、前記暗号文生成ステップが、前記符号化データの要素の値をイジング型の値に変換する第１データ変換ステップと、前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出ステップと、前記圧縮要素の符号をイジング型に変換する符号変換ステップと、前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換ステップとをさらに有することを特徴とする。
【００１８】
このような手順によれば、暗号化装置は、暗号文生成ステップにおいて、第１データ変換ステップで、符号化データの要素として例えば２進の論理値で表された「０」と「１」を、統計力学で用いるイジング型のアップスピン及びダウンスピンの値に対応した「＋１」と「−１」に変換する。続いて、暗号化装置は、圧縮要素算出ステップで、イジング型の値に変換された要素、圧縮行列、及び、所定値に基づいて、符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する。そして、暗号化装置は、符号変換ステップで、圧縮要素の符号をイジング型の値に変換する。続いて、暗号化装置は、第２データ変換ステップで、イジング型の値として変換された符号を論理型の値に変換する。これによって、歪みあり圧縮された暗号文を生成することができる。
【００１９】
請求項６に記載の復号化方法は、請求項４または請求項５に記載の暗号化方法を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置の復号化方法であって、前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元ステップと、前記復元されたビット長の復元データを、前記線形符号で復号化する復号化ステップとを有することを特徴とする。
【００２０】
このような手順によれば、復号化装置は、復元ステップで、暗号文に圧縮行列を作用させた復元データを生成することにより、暗号文のビット長（Ｙ）を、符号化データのビット長（Ｍ）に復元する。続いて、復号化ステップで、復元されたビット長（Ｍ）の復元データを、線形符号で復号化する。これにより、線形符号で暗号化される前の平文を生成することができる。
【発明の効果】
【００２１】
本発明によれば、McEliece暗号方式において、暗号文を平文に対して冗長化する割合を低減することができる。その結果、暗号文を送信する際の通信コストを低減することができる。また、本発明によれば、平文に対して冗長化する割合を低減した暗号文を容易に復号することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態について、適宜図面を参照しながら説明する。図１は、本発明の実施形態に係る暗号化装置と復号化装置とを含む通信システムの構成例を示す図である。
［通信システムの構成］
図１に示すように、この通信システム１では、例えばインターネット等の通信路２を介して、暗号化装置１０と、復号化装置２０とが接続されている。これらの各装置１０，２０は、一般的なコンピュータ（計算機）であり、例えば、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ＨＤＤ（Hard Disk Drive）と、ＫＢ／ＣＲＴ（Key Board／Cathode Ray Tube）と、通信インタフェースとを含んで構成されている。以下に、各装置１０，２０の機能を詳細に説明する。
【００２３】
［暗号化装置の機能］
暗号化装置１０は、次式（１）に基づいて、式（２）で示される暗号化演算ｆを実行し、平文ｐから暗号文ｃを生成するものである。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
ｆ（ｐ｜ＰＧＳ，Ｈ）∈｛∃ｎ，（ＰＧＳ）ｐ＋ｎ＝Ｈｃ｝…（２）
ここで、平文ｐのビット長（第１のビット長）をＮ、Ｎより大きいビット長（第２のビット長）をＭ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、線形符号をＰＧＳ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨ、歪みあり圧縮で生じる歪みをｎとした。
【００２４】
暗号化装置１０は、図１に示すように、入力手段１１と、記憶手段（ＲＡＭ等）１２と、制御手段（ＣＰＵ等）１３と、出力手段１４とを備える。
入力手段１１は、平文ｐを入力し、制御手段１３に出力するものである。
記憶手段１２は、半導体メモリや磁気メモリなどの書き換え可能な記憶手段であり、制御手段１３による演算処理等に利用されると共に、入力手段１１を介して取得した情報等を記憶するものである。
制御手段１３は、前記した入力手段１１、記憶手段１２及び出力手段１４を制御すると共に、平文ｐから暗号文ｃを生成するものである。
出力手段１４は、生成された暗号文ｃを復号化装置２０に送信するものである。
【００２５】
制御手段１３は、図１に示すように、符号化手段１５と、圧縮手段１６とを備える。
符号化手段１５は、入力された平文ｐを公開鍵Ｇ′（＝線形符号ＰＧＳ）で符号化することによりビット長が長くなった（冗長化された）冗長化ベクトル（符号化データ）Ａを生成するものである。この冗長化ベクトルＡは、前記した式（１）の（ＰＧＳ）ｐと等しいものである。ここで、公開鍵Ｇ′は例えばＧｏｐｐａ符号やＬＤＰＣ（Low Density Parity Check Code）符号等である。なお、公開鍵Ｇ′はＬＤＰＣ符号の場合、疎行列（行列内の多くの要素が「０」である行列）である。
【００２６】
圧縮手段（暗号文生成手段）１６は、予め定められた圧縮行列Ｈに基づいて、冗長化ベクトルＡを歪みあり圧縮することにより、暗号文ｃを生成する（圧縮処理を実行する）ものである。この圧縮手段１６は、暗号文ｃを生成する際に、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に公開鍵Ｇ′で訂正できるレベルのベクトルを選択する。
なお、前記した符号化手段１５及び圧縮手段１６は、ＣＰＵが記憶手段１２のＲＯＭに格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００２７】
［圧縮手段の機能］
次に、図１に示した圧縮手段１６の機能を説明する。この圧縮手段１６は、前記した式（１）の別の表現である式（１ａ）で示される方程式で、暗号文ｃを生成する。
Ｈｃ＝Ａ＋ｎ …（１ａ）
式（１ａ）に示した冗長化ベクトルＡは、現実的には例えば数千〜数万ビットの長さを有している。しかしながら、式（１ａ）を簡単に説明するために、以下では、暗号化装置１０は、符号化手段１５によって、２ビット（Ｎ＝２）の平文ｐを符号化して４ビット（Ｎ＝４）の冗長化ベクトルＡを生成したと仮定する場合を例示する。ここで、圧縮行列Ｈは、式（３）で示されるように要素「１」が配置された４×３型の行列とする（Ｙ＝３）。また、冗長化ベクトルＡは式（４）で示される。
【００２８】
【数１】
【００２９】
【数２】
【００３０】
この場合に、圧縮手段１６は、歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に公開鍵Ｇ′で訂正できるレベルのベクトルを選択するために、式（１ａ），式（３）及び式（４）に基づいて、暗号文ｃを示すベクトルと共に、歪みを示すベクトルｎとして、零ベクトルに近似して「０」の要素を多数含むものを選択する。すなわち、ベクトルｎができるだけ零ベクトルに近づくようにする。そして、圧縮手段１６は、最適な組として、式（５）で示される暗号文ｃと、式（６）で示される歪みｎとを選択する。この場合、ベクトルｎの大きさ（「１」の個数）が冗長化ベクトルＡと、式（１ａ）の左辺のベクトルＨｃとのハミング距離（Hamming distance）になっている。
【００３１】
【数３】
【００３２】
【数４】
【００３３】
つまり、圧縮手段１６は、４ビットの冗長化ベクトルＡから、３ビット（Ｙ＝３）に圧縮された暗号文ｃを生成する。そして、この圧縮された暗号文ｃが復号化装置２０に送信される。
この例では、式（１ａ）は、式（７）のように表現されることになる。
【００３４】
【数５】
【００３５】
一方、この例では、従来のMcEliece暗号方式は、４ビットの冗長化ベクトルＡに対して、式（６）で示した４ビットのノイズを付加するものに相当する。すなわち、式（７）の最右辺で表される４ビットのベクトルを暗号文として送信することになる。なお、従来のMcEliece暗号方式において付加するノイズと、本実施形態において歪みあり圧縮で生じる歪みｎとは、同一視できるが、それぞれの候補は複数あり、単純に一対一に対応しているものではない。
【００３６】
したがって、式（２）で特徴付けられる暗号化演算ｆを実行する暗号化装置１０は、暗号文ｃを平文ｐに対して冗長化する割合を、従来のMcEliece暗号方式で暗号化する場合と比較して低減することができる。その結果、暗号文を送信する際の通信コストを低減できるという効果を奏する。
【００３７】
［圧縮手段の構成例］
次に、図１に示した圧縮手段１６の構成例を説明する。図２は、図１に示した圧縮手段の構成例を示すブロック図である。
この例では、圧縮手段１６は、前記した式（１ａ）の方程式を統計力学的手法を用いて解くことにより、入力する冗長化ベクトルＡから最適な暗号文ｃを生成するものであり、図２に示すように、第１データ変換手段３１と、圧縮要素算出手段３２と、符号変換手段３３と、第２データ変換手段３４とを備える。
【００３８】
第１データ変換手段３１は、符号化手段１５の出力する冗長化ベクトルＡの要素として例えば２進の論理値で表された「０」と「１」を、統計力学で用いるイジング型のアップスピン及びダウンスピンの値に対応した「＋１」と「−１」にそれぞれ変換するものである。なお、冗長化ベクトルＡの変換されたｉ番目の要素をｑiと表記する。
【００３９】
圧縮要素算出手段３２は、イジング型の値に変換された要素、圧縮行列Ｈ、及び、歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値β，γに基づいて、冗長化ベクトルＡを圧縮した１次元配列データｍの要素である圧縮要素をそれぞれ算出するものである。ここで、１次元配列データｍのｊ番目の圧縮要素をｍjと表記する。また、所定値βを最適化するとは、前記した式（１ａ）においてベクトルｎが零ベクトルに最も近似する形に最適化されていることに相当する。
【００４０】
具体的には、この圧縮要素算出手段３２は、１次元配列データの圧縮要素ｍjを算出するために、式（８），（９）でそれぞれ示される変数
【数６】
（ｍijハット）及びｍijと共に利用される式（１０）を逐次更新的に用いる。
【００４１】
【数７】
【００４２】
【数８】
【００４３】
【数９】
【００４４】
式（８）〜（１０）において、ｍj，ｍij，およびｍij（ハット）は毎回更新される動的変数である。所定値β，γは、歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化されている。このように最適化するためには、例えばスピングラスなどにおいて、自由エネルギー等を算出する際の統計力学的な手法を用いることができる。
【００４５】
圧縮要素算出手段３２で利用する圧縮行列Ｈは、ＬＤＰＣ行列であり、そのｉ行ｊ列の要素をｈijと表記する。圧縮行列Ｈは、非ゼロ要素として各行Ｋ個の「１」と、各列Ｃ個の「１」だけを有し、その他の要素は「０」である。すなわち、圧縮率ＲはＫ／Ｃである。
また、前記した式（８）において、集合Ｍ（ｉ）は、次式（１１）で定義されている。なお、記号＼（バックスラッシュ）は要素の排除を意味する。
【００４６】
Ｍ（ｉ）＝｛ｊ｜ｈij＝１｝ …（１１）
【００４７】
また、前記した式（９）及び（１０）において、集合Ｌ（ｊ）は、次式（１２）で定義されている。なお、記号＼（バックスラッシュ）は要素の排除を意味する。
【００４８】
Ｌ（ｊ）＝｛ｉ｜ｈij＝１｝ …（１２）
【００４９】
符号変換手段３３は、次式（１３）に基づいて、１次元配列データの圧縮要素ｍjの符号をイジング型の値にそれぞれ変換するものである。圧縮要素ｍjはそれぞれ、「−１」と「１」の間の任意の値をとる。ここで、変換されたｊ番目の要素をｗjと表記する。また、関数ｓｉｇｎは、引数の符号が正ならば「＋１」、引数の符号が負ならば「−１」をそれぞれ出力するものである。
【００５０】
ｗj＝ｓｉｇｎ（ｍj） …（１３）
【００５１】
第２データ変換手段３４は、イジング型の値として変換された要素ｗjの値「＋１」及び「−１」を、論理型の値「０」と「１」にそれぞれ変換し、暗号文ｃ（ベクトル）の要素（暗号文ｃのｊ番目の要素をｃjと表記する）を生成するものである。
【００５２】
［復号化装置の機能］
図１に戻って、復号化装置２０の機能を説明する。
復号化装置２０は、暗号化装置１０を用いて圧縮行列Ｈで歪みあり圧縮により生成された暗号文ｃを復号化して平文ｐを生成するものであり、入力手段２１と、記憶手段（ＲＡＭ等）２２と、制御手段（ＣＰＵ等）２３と、出力手段２４とを備える。
入力手段２１は、暗号文ｃを入力し、制御手段２３に出力するものである。
記憶手段２２は、半導体メモリや磁気メモリなどの書き換え可能な記憶手段であり、制御手段２３による演算処理等に利用されると共に、入力手段２１を介して取得した情報等を記憶するものである。
制御手段２３は、前記した入力手段２１、記憶手段２２及び出力手段２４を制御すると共に、暗号文ｃから平文ｐを生成するものである。
出力手段２４は、生成された平文ｐを出力するものである。
【００５３】
制御手段２３は、図１に示すように、復元手段２５と、復号化手段２６とを備える。
復元手段２５は、受信した暗号文ｃに圧縮行列Ｈをかけて、冗長化ベクトルＡの次元に復元することにより、暗号文ｃのビット長（Ｙ）を、冗長化ベクトルＡのビット長（Ｍ）に復元するものである。この復元手段２５は、具体的には、前記した式（１ａ）の左辺で示される演算を実行する。
復号化手段２６は、復元されたビット長（Ｍ）のベクトル（復元データ）Ｈｃを、公開鍵Ｇ′で復号化し、元のビット長（Ｎ）の平文ｐを生成するものである。
なお、前記した復元手段２５及び復号化手段２６は、ＣＰＵが記憶手段２２のＲＯＭに格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００５４】
［暗号化装置の動作］
次に、暗号化装置の動作について図３を参照（適宜図１参照）して説明する。図３は、図１に示した暗号化装置の動作を示すフローチャートである。
暗号化装置１０は、入力手段１１によって、平文ｐを入力し（ステップＳ１）、符号化手段１５によって、入力された平文ｐを公開鍵Ｇ′で冗長化し、冗長化ベクトルＡを生成し（ステップＳ２：符号化ステップ）、圧縮手段１６に出力する。
【００５５】
続いて、暗号化装置１０は、圧縮手段１６によって、圧縮処理を実行する（ステップＳ３：暗号文生成ステップ）。すなわち、圧縮手段１６は、冗長化ベクトルＡを歪みあり圧縮することにより、Ｙビットの暗号文ｃを生成する。そして、暗号化装置１０は、出力手段１４によって、暗号文ｃを復号化装置２０に送信する（ステップＳ４）。
【００５６】
［圧縮手段の動作］
次に、前記したステップＳ３の圧縮処理について図４を参照（適宜図２参照）して説明する。図４は、図３に示した圧縮処理を示すフローチャートである。
圧縮手段１６は、第１データ変換手段３１によって、入力データ（冗長化ベクトルＡ）の要素の値（０，１）をイジング型の値（−１，１）に変換し（ステップＳ１１：第１データ変換ステップ）、圧縮要素算出手段３２に出力する。
【００５７】
圧縮要素算出手段３２は、イジング型の値に変換された要素ｑi、圧縮行列Ｈ、及び、所定値β，γに基づいて、冗長化ベクトルＡを圧縮した１次元配列データの要素である圧縮要素ｍjをそれぞれ算出し（ステップＳ１２：圧縮要素算出ステップ）、符号変換手段３３に出力する。このとき、圧縮要素算出手段３２は、前記した式（８）〜式（１０）で示されるｍijハット，ｍij及び圧縮要素ｍjを逐次更新的に用いて圧縮要素ｍjをそれぞれ算出する。
【００５８】
そして、符号変換手段３３は、入力した１次元配列データの圧縮要素ｍjの符号をそれぞれ、前記した式（１３）に基づいて、イジング型の値（−１，１）に変換し（ステップＳ１３：符号変換ステップ）、第２データ変換手段３４に出力する。そして、第２データ変換手段３４によって、イジング型の値（−１，１）に変換された符号（−１，１）を論理型の値（０，１）に変換し、暗号文ｃ（ベクトル）の要素を生成する（ステップＳ１４：第２データ変換ステップ）。
【００５９】
［復号化装置の動作］
次に、復号化装置の動作について図５を参照（適宜図１参照）して説明する。図５は、図１に示した復号化装置の動作を示すフローチャートである。
復号化装置２０は、入力手段２１によって、暗号文ｃを入力し（ステップＳ２１）、復元手段２５によって、受信した暗号文ｃに圧縮行列Ｈをかけて、冗長化ベクトルＡの次元に復元することにより、暗号文ｃのビット長（Ｙ）を、冗長化ベクトルＡのビット長（Ｍ）に復元し（ステップＳ２２：復元ステップ）、復号化手段２６に出力する。このとき、復元手段２５は、前記した式（１ａ）の左辺の演算を実行し、例えば前記した式（７）の最右辺で表されるようなベクトルを生成する。
【００６０】
続いて、復号化装置２０は、復号化手段２６によって、復元されたビット長（Ｍ）のベクトル（復元データ）Ｈｃを公開鍵Ｇ′で復号化し、元のビット長（Ｎ）の平文ｐを生成する（ステップＳ２３：復号化ステップ）。そして、復号化装置２０は、出力手段２４によって、生成した平文ｐを出力する（ステップＳ２４）。
【００６１】
なお、ベクトルＨｃを公開鍵Ｇ′で復号化する操作ｇ′は公知の手法を用いて以下のように実行される。まず、第１段階では次式（１４）の関係式で示される操作を実行する。すなわち、ＭビットのベクトルＨｃを、公開鍵Ｇ′の構成要素である置換行列Ｐで前処理してベクトル（Ｐ-1Ｈｃ）を生成する。なお、この前処理（置換行列Ｐによる操作）は、歪みｎのレベルを保存する。
【００６２】
Ｐ-1Ｈｃ＝Ｇ（Ｓｐ）＋Ｐ-1ｎ …（１４）
【００６３】
次に、第２段階では次式（１５）の関係式で示される操作を実行する。すなわち、前記した式（１４）の左辺で示した生成ベクトル（Ｐ-1Ｈｃ）を、公開鍵Ｇ′の構成要素である生成行列Ｇによって復号する復号操作ｇを実行することによって所定範囲で歪みｎを除去し、さらに、公開鍵Ｇ′の構成要素である生成行列Ｇによって元のビット数（Ｎ）の平文ｐを逆算する。なお、この復号操作ｇは非公開の生成行列Ｇにのみ有効である。
【００６４】
ｐ＝ｇ′（Ｈｃ｜Ｇ′）＝Ｓ-1［ｇ（Ｐ-1Ｈｃ｜Ｇ）］ …（１５）
【００６５】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、本実施形態では、暗号化装置１０の符号化手段１５は、公開鍵Ｇ′をＧｏｐｐａ符号やＬＤＰＣ符号等で符号化するものとして説明したが、例示した従来から実装される線形符号に限定されず、任意の線形符号を利用することができる。
また、暗号化装置１０の圧縮手段１６は、圧縮要素算出手段３２によって、予め最適化された所定値βを利用して１次元配列データの圧縮要素ｍjを算出するものとして説明したが、所定値βを最適化する処理を実行する構成を付加するようにしてもよい。
【図面の簡単な説明】
【００６６】
【図１】本発明の実施形態に係る暗号化装置と復号化装置とを含む通信システムの構成例を示す図である。
【図２】図１に示した圧縮手段の構成例を示すブロック図である。
【図３】図１に示した暗号化装置の動作を示すフローチャートである。
【図４】図３に示した圧縮処理を示すフローチャートである。
【図５】図１に示した復号化装置の動作を示すフローチャートである。
【符号の説明】
【００６７】
１ 通信システム
２ 通信路
１０ 暗号化装置
１１ 入力手段
１２ 記憶手段
１３ 制御手段
１４ 出力手段
１５ 符号化手段
１６ 圧縮手段（暗号文生成手段）
２０ 復号化装置
２１ 入力手段
２２ 記憶手段
２３ 制御手段
２４ 出力手段
２５ 復元手段
２６ 復号化手段
３１ 第１データ変換手段
３２ 圧縮要素算出手段
３３ 符号変換手段
３４ 第２データ変換手段
【特許請求の範囲】
【請求項１】
第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化手段と、前記符号化データに基づいて暗号文を生成する暗号文生成手段とを有したMcEliece暗号方式の暗号化装置において、
前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、
前記暗号文生成手段は、
式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択する、
ことを特徴とする暗号化装置。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【請求項２】
前記暗号文生成手段は、
前記符号化データの要素の値をイジング型の値に変換する第１データ変換手段と、
前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出手段と、
前記圧縮要素の符号をイジング型の値に変換する符号変換手段と、
前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換手段と、
を備えることを特徴とする請求項１に記載の暗号化装置。
【請求項３】
請求項１または請求項２に記載の暗号化装置を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置であって、
前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元手段と、
前記復元されたビット長の復元データを、前記線形符号で復号化する復号化手段と、
を有することを特徴とする復号化装置。
【請求項４】
第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化ステップと、前記符号化データに基づいて暗号文を生成する暗号文生成ステップとを有したMcEliece暗号方式の暗号化装置の暗号化方法において、
前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、
前記暗号文生成ステップは、
式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択する、
ことを特徴とする暗号化方法。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【請求項５】
前記暗号文生成ステップは、
前記符号化データの要素の値をイジング型の値に変換する第１データ変換ステップと、
前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出ステップと、
前記圧縮要素の符号をイジング型の値に変換する符号変換ステップと、
前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換ステップと、
をさらに有することを特徴とする請求項４に記載の暗号化方法。
【請求項６】
請求項４または請求項５に記載の暗号化方法を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置の復号化方法であって、
前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元ステップと、
前記復元されたビット長の復元データを、前記線形符号で復号化する復号化ステップと、
を有することを特徴とする復号化方法。
【請求項１】
第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化手段と、前記符号化データに基づいて暗号文を生成する暗号文生成手段とを有したMcEliece暗号方式の暗号化装置において、
前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、
前記暗号文生成手段は、
式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択する、
ことを特徴とする暗号化装置。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【請求項２】
前記暗号文生成手段は、
前記符号化データの要素の値をイジング型の値に変換する第１データ変換手段と、
前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出手段と、
前記圧縮要素の符号をイジング型の値に変換する符号変換手段と、
前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換手段と、
を備えることを特徴とする請求項１に記載の暗号化装置。
【請求項３】
請求項１または請求項２に記載の暗号化装置を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置であって、
前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元手段と、
前記復元されたビット長の復元データを、前記線形符号で復号化する復号化手段と、
を有することを特徴とする復号化装置。
【請求項４】
第１のビット長を有する平文を線形符号で符号化することにより、前記第１のビット長よりも長い第２のビット長を有する符号化データを生成する符号化ステップと、前記符号化データに基づいて暗号文を生成する暗号文生成ステップとを有したMcEliece暗号方式の暗号化装置の暗号化方法において、
前記第１のビット長をＮ、前記第２のビット長をＭ、前記平文をｐ、Ｍ×Ｍ型の置換行列をＰ、Ｍ×Ｎ型の生成行列をＧ、Ｎ×Ｎ型の可逆行列をＳ、前記線形符号をＰＧＳ、前記符号化データを（ＰＧＳ）ｐ、縦長のＭ×Ｙ（Ｎ＜Ｙ＜Ｍ）型の圧縮行列をＨとしたときに、
前記暗号文生成ステップは、
式（１）に基づいて、前記圧縮行列Ｈで前記符号化データ（ＰＧＳ）ｐを歪みあり圧縮することにより、暗号文ｃを生成し、この暗号文ｃを生成する際に、前記歪みあり圧縮で生じる歪みを示すベクトルｎとして、復号時に前記線形符号ＰＧＳで訂正できるレベルのベクトルを選択する、
ことを特徴とする暗号化方法。
（ＰＧＳ）ｐ＋ｎ＝Ｈｃ …（１）
【請求項５】
前記暗号文生成ステップは、
前記符号化データの要素の値をイジング型の値に変換する第１データ変換ステップと、
前記イジング型の値に変換された要素、前記圧縮行列、及び、前記歪みあり圧縮で生じる歪みがランダムに分布するように予め最適化された所定値に基づいて、前記符号化データを圧縮した１次元配列データの要素である圧縮要素をそれぞれ算出する圧縮要素算出ステップと、
前記圧縮要素の符号をイジング型の値に変換する符号変換ステップと、
前記イジング型の値として変換された符号を論理型の値に変換する第２データ変換ステップと、
をさらに有することを特徴とする請求項４に記載の暗号化方法。
【請求項６】
請求項４または請求項５に記載の暗号化方法を用いて圧縮行列で歪みあり圧縮により生成された暗号文を復号化する復号化装置の復号化方法であって、
前記暗号文に前記圧縮行列を作用させた復元データを生成することにより、前記暗号文のビット長を、前記符号化データのビット長に復元する復元ステップと、
前記復元されたビット長の復元データを、前記線形符号で復号化する復号化ステップと、
を有することを特徴とする復号化方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００６−３３０２６６（Ｐ２００６−３３０２６６Ａ）
【公開日】平成１８年１２月７日（２００６．１２．７）
【国際特許分類】
【出願番号】特願２００５−１５２３９５（Ｐ２００５−１５２３９５）
【出願日】平成１７年５月２５日（２００５．５．２５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１８年１２月７日（２００６．１２．７）
【国際特許分類】
【出願日】平成１７年５月２５日（２００５．５．２５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]