(57)【要約】【課題】  ナップザック暗号の安全性を高める。【解決手段】  秘密鍵ベクトルｖの一部をノイズ成分とし、Ｇをｕ行ｎ列(ｎ＞ｕ)の行列とし、Ｇ''−１をｕ行ｕ列の行列とする。ｕ次元の平文ｍを行列Ｇによりｎ次元に拡大し、公開鍵ベクトルａとの積和演算により暗号文Ｃとする。暗号文Ｃを中間平文Ｍに復号し、秘密鍵ベクトルｖの一部のｕ個の成分により復号し、行列Ｇ''−１と乗算して平文ｍへ復号する。【選択図】    図１
2007140095.tif 000002
【特許請求の範囲】
【請求項１】
ｕ次元の平文ベクトルを有限体上で線形符号化してｎ次元の拡大平文ベクトル(ｎ＞ｕ：ｎ，ｕは正整数)とし、この拡大平文ベクトルをｎ次元の公開鍵ベクトルと内積した暗号文を復号するために、
暗号文を受信するための通信装置と、
暗号文をモジュラ変換により中間平文に変換するためのモジュラ変換手段と、中間平文を、ｎ次元の秘密鍵ベクトルｖ中のｕ個の成分(ｎ＞ｕ)のみを用いて、ｕ次元の中間平文ベクトルへ復号するためのナップザック復号手段と、前記有限体上の正則な復号行列と中間平文ベクトルとの乗算によりｕ次元の平文ベクトルを復号するための行列乗算手段とを備えた復号装置、とを備えた暗号通信装置。
【請求項２】
公開鍵として、前記の公開鍵ベクトルａと拡大平文ベクトルへの線形符号化を行うためのデータとを記憶し、
秘密鍵として、前記の復号行列Ｇ'−１、前記の秘密鍵ベクトルｖ中のｕ個の成分、モジュラ変換用の秘密のパラメータｗ、秘密の法Ｐを記憶するための手段をさらに備え、
ｎ次置換群の元σに対し、  ｖ'≡ｗｖ modＰ；  ａ＝ｖ'σ  （σがｖ'のi番目の元  ｖ'iをj番目に移し、σ(i)＝j  の際に，ａのj番目の元ａjが  ａj＝ｖ'i  ）；
Ｇ'＝ＫＧσとして(Ｇは前記の線形符号化での符号語の生成行列で、σは行列Ｇの列の置換として作用し、Ｋは置換後の行列から列の順序を保ったまま所定個数の列を取り出して正則行列Ｇ'とする変換)  復号行列Ｇ'−１は行列Ｇ'の逆行列  との関係を充たすことを特徴とする、請求項１の暗号通信装置。
【請求項３】
前記線形符号化を行うためのデータが、前記生成行列Ｇもしくは線形符号の生成多項式であることを特徴とする、請求項２の暗号通信装置。
【請求項４】
前記モジュラ変換手段が、モジュラ変換を多段に行う多段モジュラ変換であることを特徴とする、請求項１〜３のいずれかの暗号通信装置。
【請求項５】
前記有限体がＧＦ(２ｋ)(ｋは２以上の自然数)であることを特徴とする、請求項１〜４のいずれかの暗号通信装置。
【請求項６】
前記秘密鍵ベクトルｖ中のｕ個の成分の一部が超増加性を備え、ｕ個の成分の残りが下位ビットの偶奇性によるトラップドアを備えていることを特徴とする、請求項１〜５のいずれかの暗号通信装置。
【請求項７】
デジタル情報処理装置で暗号通信を行うためのプログラムであって、
ｕ次元の平文ベクトルを有限体上で線形符号化してｎ次元の拡大平文ベクトル(ｎ＞ｕ：ｎ，ｕは正整数)とし、この拡大平文ベクトルとｎ次元の公開鍵ベクトルとを内積した暗号文を復号するために、
暗号文をモジュラ変換により中間平文に変換するためのモジュラ変換命令と、中間平文を、ｎ次元の秘密鍵ベクトルｖ中のｕ個の成分(ｎ＞ｕ)のみを用いて、ｕ次元の中間平文ベクトルへ復号するためのナップザック復号命令と、前記有限体上の正則な復号行列と中間平文ベクトルとの乗算によりｕ次元の平文ベクトルを復号するための行列乗算命令、とを備えたことを特徴とする暗号通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明はナップザック型の暗号通信装置とそのプログラムに関する。
【背景技術】
【０００２】
超増加数列を用いたナップザック型の暗号(非特許文献１)が知られている。また発明者らは、プリコーディングを用いて高密度なナップザック暗号を実現することを提案した(非特許文献２)。発明者はナップザック暗号の安全性をさらに高めることを検討して、この発明に到った。
【非特許文献１】R.C.Merkle and M.E.Hellman: "Hiding Information and signatures in trapdoor knapsacks" IEEE Trans.Inf.Theory,IT-24(5),p.p.525-530,September,1978
【非特許文献２】名迫  健，横山  晃子，村上  恭通："プリコーディングを用いた高密度ＭＨ型ナップザック暗号の提案"  ２００５年  暗号と情報セキュリティシンポジウム予稿集  p.p.949-954,Jan.2005
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の課題は、秘密鍵ベクトルがノイズ成分を含むため安全な、ナップザック暗号通信装置とそのプログラムを提供することにある。
この発明での副次的な課題は、暗号の安全性をさらに高めることにある。
この発明での他の副次的な課題は、暗号通信装置の具体的な構成を提供することにある。
【課題を解決するための手段】
【０００４】
この発明は、次元の平文ベクトルを有限体上で線形符号化してｎ次元の拡大平文ベクトル(ｎ＞ｕ：ｎ，ｕは正整数)とし、この拡大平文ベクトルをｎ次元の公開鍵ベクトルと内積した暗号文を復号するために、
暗号文を受信するための通信装置と、
暗号文をモジュラ変換により中間平文に変換するためのモジュラ変換手段と、中間平文を、ｎ次元の秘密鍵ベクトルｖ中のｕ個の成分(ｎ＞ｕ)のみを用いて、ｕ次元の中間平文ベクトルへ復号するためのナップザック復号手段と、前記有限体上の正則な復号行列と中間平文ベクトルとの乗算によりｕ次元の平文ベクトルを復号するための行列乗算手段とを備えた復号装置、とを備えた暗号通信装置にある。
【０００５】
好ましくは、公開鍵として、前記の公開鍵ベクトルａと拡大平文ベクトルへの線形符号化を行うためのデータとを記憶し、
秘密鍵として、前記の復号行列Ｇ'−１、前記の秘密鍵ベクトルｖ中のｕ個の成分、モジュラ変換用の秘密のパラメータｗ、秘密の法Ｐを記憶するための手段をさらに備え、
ｎ次置換群の元σに対し、  ｖ'≡ｗｖ modＰ；  ａ＝ｖ'σ  （σがｖ'のi番目の元  ｖ'iをj番目に移し、σ(i)＝j  の際に，ａのj番目の元ａjが  ａj＝ｖ'i  ）；
Ｇ'＝ＫＧσとして(Ｇは前記の線形符号化での符号語の生成行列で、σは行列Ｇの列の置換として作用し、Ｋは置換後の行列から列の順序を保ったまま所定個数の列を取り出して正則行列Ｇ'とする変換)  復号行列Ｇ'−１は行列Ｇ'の逆行列  との関係を充たす。
前記線形符号化を行うためのデータは、例えば前記生成行列Ｇもしくは線形符号の生成多項式である。
【０００６】
また好ましくは、前記モジュラ変換手段が、モジュラ変換を多段に行う多段モジュラ変換である。
【０００７】
好ましくは、前記有限体がＧＦ(２ｋ)(ｋは２以上の自然数)である。
【０００８】
好ましくは、前記秘密鍵ベクトルｖ中のｕ個の成分の一部が超増加性を備え、ｕ個の成分の残りが下位ビットの偶奇性によるトラップドアを備えている。
【０００９】
この発明はまた、デジタル情報処理装置で暗号通信を行うためのプログラムであって、
ｕ次元の平文ベクトルを有限体上で線形符号化してｎ次元の拡大平文ベクトル(ｎ＞ｕ：ｎ，ｕは正整数)とし、この拡大平文ベクトルとｎ次元の公開鍵ベクトルとを内積した暗号文を復号するために、
暗号文をモジュラ変換により中間平文に変換するためのモジュラ変換命令と、中間平文を、ｎ次元の秘密鍵ベクトルｖ中のｕ個の成分(ｎ＞ｕ)のみを用いて、ｕ次元の中間平文ベクトルへ復号するためのナップザック復号命令と、前記有限体上の正則な復号行列と中間平文ベクトルとの乗算によりｕ次元の平文ベクトルを復号するための行列乗算命令、とを備えたことを特徴とする。
【発明の効果】
【００１０】
この発明では、ｕ次元の平文ベクトルを線形符号の生成行列と乗算して有限体上で線形符号化し、あるいはｎ−ｕ次元などの線形符号の生成多項式で有限体上で線形符号化して、ｎ次元の拡大平文ベクトルへ拡大する。次に拡大平文ベクトルをｎ次元の公開鍵ベクトルと内積し、暗号文を得る。生成行列も生成多項式も共に線形符号化用のデータで、生成多項式が定まればそれに対応する生成行列が一意に定まる。また生成行列の要素はｕｎ個あるが、生成多項式の項数は例えばｎ−ｕ＋１項で、公開鍵のデータ長が短くなる。
【００１１】
復号時には、暗号文をモジュラ変換により中間平文に変換し、ｎ次元の秘密鍵ベクトルｖ中のｕ個の成分のみを用いて、ナップザック復号方式によりｕ次元の中間平文ベクトルへと復号する。暗号化用の公開鍵ベクトルはｎ次元であるが、復号に用いる秘密鍵ベクトルで用いるのはｕ個の成分であり、ｎ−ｕ個の成分は適当なノイズとすることができる。このため暗号の強度を高めることができる。次に中間平文ベクトルを正則な復号行列と乗算して、ｕ次元の平文ベクトルを復号する。
【００１２】
生成行列はｕ行ｎ列で、復号行列はｕ行ｕ列である。ここで生成行列のランクがｕで、一次独立なｕ個の列を集めて行列Ｇ'を作成すると、そのランクはｕとなる。従って行列Ｇ'にはＧ'−１が存在し、これを復号行列とする。ｎ次元の秘密鍵ベクトルｖ中のｕ個の成分以外に、ｎ−ｕ個のノイズの成分があるが、これらの成分は復号では用いないので記憶する必要がない。
【００１３】
この発明では、公開鍵は公開鍵ベクトルａと生成行列Ｇとを含み、好ましくはこれ以外に、ｎやｕの値を公開鍵とする。また秘密鍵は復号行列Ｇ'−１，秘密鍵ベクトルｖ中のｕ個の復号に用いる成分，モジュラ変換用の秘密のパラメータｗと秘密の法Ｐとがある。ここで公開鍵ベクトルａと秘密鍵ベクトルｖは、ｖ'≡ｗｖ modＰ；  ａ＝ｖ'σ  との関係により結ばれ、ここにσはｎ次置換群の元である。また非正方行列Ｇと正則行列Ｇ'とは、  Ｇ'＝ＫＧσ  の関係により結ばれ、行列Ｇに対して置換σにより列を置換し、置換後の行列から、変換Ｋにより列の順序を保ったまま所定個数の列、例えばｕ個の列を取り出すと正則行列Ｇ'となる。例えば秘密鍵ベクトルｖの成分ｖ1〜ｖuが復号に関係するとし、行列Ｇの各列をｇ1〜ｇnとすると、Ｇ'はｕ列の行列で、そのｉ番目の列はｇσ(i)で与えられる。
【００１４】
また多段のモジュラ変換を行うと、Shamirの攻撃に対する耐性が著しく向上する。さらに行列ＧやＧ'−１を定義する有限体は、ＧＦ(２)やＧＦ(２ｋ)などとする。
【００１５】
秘密鍵ベクトルｖはｕ個の成分を復号に用い、ｎ−ｕ個の成分は単なるノイズである。これらのｕ個の成分は、超増加性を備えたもの(非特許文献１)や下位ビットの偶奇性を用いたものなどとしても良いが、ｕ個の成分の一部が超増加性を備え、残部が下位ビットの偶奇性によるトラップドアを備えているようにすると、安全性をさらに高めることができる。
【発明を実施するための最良の形態】
【００１６】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１７】
図１〜図１３に公開鍵として非正方の暗号化行列（生成行列Ｇ）を用いた実施例とその変形とを示し、図１〜図９は有限体としてＧＦ(２)を用いた例を、図１１〜図１３は有限体としてＧＦ(２ｋ)を用いた例を示し、図１０〜図１３の各変形例では特に指摘した点以外は、図１〜図９の実施例と同様である。
【００１８】
図１〜図９において、２は暗号通信装置で、公開鍵と秘密鍵とを生成して記憶する鍵生成記憶部４と暗号化装置６並びに復号装置８を備えている。そして暗号通信装置２は通信インターフェース１０を介して、他の同様の暗号通信装置と公開鍵暗号通信を行う。なお鍵生成記憶部４は単に公開鍵を記憶するだけでも良い。次にメッセージｍをｕ次元の平文ベクトルとし、具体的にはｕビットのデータとする。メッセージｍに対してｍ'≡ｍＧ
mod２を拡大平文ベクトルｍ'とする。なおＧはｕ行ｎ列の暗号化行列（生成行列）である。ベクトルｍと行列Ｇの列とを積和演算する代わりに、ベクトルｍと行列Ｇの各行とを積和演算すると、行列Ｇは例えばｎ行ｕ列の行列となる。しかしながらこれはベクトルと行列との乗算の定義によるものであり、このような場合でも行列Ｇをｕ行ｎ列の行列と見なす。次に暗号文Ｃは公開鍵ベクトルａと拡大平文ベクトルｍ'との内積、あるいはこれらの各成分間の積和演算により与えられる。
【００１９】
復号装置８では、ｎ≡ｗ−１Ｃ modＰによりモジュラ変換を行って、中間平文Ｍを得る。次に秘密鍵ベクトルｖ中のｕ個の成分を用いて、中間平文Ｍからｕ個の成分を復号し、中間平文ベクトルｍ''とする。そして中間平文ベクトルｍ''を行列Ｇ'−１と乗算して、平文ｍを復号する。
【００２０】
図２に秘密鍵ベクトルｖの構造を示すと、ベクトルｖはｎ次元のベクトルで、このうちｕ個の成分を復号に用い、ｈ＝ｎ−ｕ個の成分は単なるノイズである。ベクトルｖのノイズ以外の成分は何らかのトラップドアを備えたものであり、実施例ではｖ1〜ｖsを下位ビットの偶奇性を利用したトラップドアを備えたものとし、ｖs+1〜ｖuを超増加性によるトラップドアを備えたものとする。そして秘密鍵ベクトルｖに対してｖ'≡ｗｖ modＰによりベクトルｖ'を得、これをｎ次置換群の元σにより置換して、ａ＝ｖ'σ  により得られる公開鍵ベクトルａとする。
【００２１】
ｕ次元データの平文ｍを暗号文Ｃに変換する際には図３に示すように、平文ベクトルｍを拡大平文ベクトルｍ'に変形し、積和演算により暗号文Ｃとする。
【００２２】
暗号文Ｃの復号では図４に示すように、ｍ≡ｗ−１Ｃ modＰにより中間平文Ｍを得る。次に秘密鍵ベクトルｖ中の成分ｖ1〜ｖsは下位ビットの偶奇性により復号可能なので、この部分を復号し、ｖs+1〜ｖuの部分は超増加性による復号が可能なので、この部分を復号する。このようにして中間平文Ｍをｕ次元の中間平文ベクトルｍ''に変換する。そして中間平文ベクトルｍ''を行列Ｇ'−１と乗算すると、平文ｍが得られる。
【００２３】
図５に、モジュラ変換装置２０の構造を示すと、２２は乗算器で、２４は剰余算器で、２６は置換装置でσによる置換を行う。
【００２４】
図６に暗号化行列Ｇから復号行列Ｇ'−１への変換を示す。行列Ｇはｕ行ｎ列の行列とし、そのうち少なくともｕ個の列が１次独立である。列分解装置３２で暗号化行列Ｇを列毎に分解し、置換装置３４によりσによる置換を行い、ｇσ(1)〜ｇσ(u)の列のみを取り出して、列連接装置３６で新たな行列Ｇ'とする。そして逆行列計算装置３８により逆行列Ｇ'−１を求める。なお行列Ｇ，Ｇ'−１はいずれも有限体ＧＦ(２)上の行列で、それらのランクが共にｕで、復号行列Ｇ'−１はｕ行ｕ列の正則行列である。
【００２５】
図７に暗号化装置６の構造を示すと、平文ベクトルｍに対して行列Ｇの各列との積和演算を行い、行列Ｇはｕ行ｎ列の行列なので、出力の拡大平文ベクトルｍ'はｎ次元のベクトルとなる。次に積和演算装置４２により積和演算を行い暗号文Ｃを求める
【００２６】
図８に復号装置８の構造を示すと、乗算器５０によりｗ−１を乗算し、剰余算器５２によりＰを法とする剰余を求め、ナップザック暗号復号装置５４により秘密鍵ベクトルｖ中の復号に用い得るｕ個の成分、例えばｖ1〜ｖuによる復号を行い、中間平文ベクトルｍ''を求める。そしてこれをｕ行ｕ列の正則行列Ｇ'−１と乗算すると、平文ベクトルｍが得られる。
【００２７】
図９に暗号通信プログラム６０を示すと、プログラム６０はパーソナルコンピュータなどの適宜の情報処理装置に実装され、公開鍵ベクトル生成命令６２は公開鍵ａ，ｇ，ｕ，ｎを生成し、復号行列生成命令６４は復号行列Ｇ'−１を生成する。暗号化命令６６は図７の手順により平文ベクトルｍを暗号文Ｃへ変換し、ナップザック復号命令６８は図８のＰを法とし、ｗ−１を用いた逆モジュラ変換と、ナップザック暗号復号装置５４での処理を行う。線形変換命令７０は復号行列Ｇ'−１との乗算を行う。
【００２８】
実施例では以下の効果が得られる。整数環Ｚ上の演算と有限体上の行列との演算との組合せにより暗号強度を高めることができる。また秘密鍵ベクトルｖのうち一部の成分は単なるノイズなので、暗号強度が向上する。
【００２９】
図１０に多段のモジュラ変換を用いた例を示す。ベクトルモジュラ変換装置７２を複数に例えばｅ段直列に配置し、各段での秘密のパラメータをｗ(i)、法をＰ(i)  (i=１〜ｅ)とする。そして置換装置２６によりσによる置換を施し、公開鍵ベクトルａを得る。これによってShamirの攻撃に対する耐性が向上する。
【００３０】
図１１〜図１３は有限体ＧＦ(２ｋ)上の暗号化と復号とを示し、暗号化行列Ｇは有限体ＧＦ(２ｋ)上の行列で、その行数はｎ'＝ｎ／ｋである。図１１に示すように、列分解装置８２は暗号化行列Ｇから複数の列を取り出し、置換装置８４で各列を置換し、列連接装置８６でｕ'＝ｕ／ｋ個の列を連接させ、逆行列計算装置８８で復号行列Ｇ'−１を得る。
【００３１】
暗号化では図１２に示すように、平文ベクトルｍをｋビットずつ変換器９０により、ＧＦ(２ｋ)上のデータに変換し、暗号化行列Ｇにより行列乗算器９２で乗算する。次いで変換器９４によりＧＦ(２)上の元に戻して、積和演算装置９６により積和演算し、暗号文Ｃとする。
【００３２】
復号では図１３に示すように、乗算器５０で秘密のパラメータｗ−１を乗算し、剰余算器５２で秘密の正整数、例えば秘密の素数Ｐを法とする剰余を求め、ナップザック暗号復号装置５４でｕ個の成分につき復号する。得られた中間平文ベクトルをｋビットずつ変換器９０で、ＧＦ(２ｋ)の元に変換し、行列乗算器９８で復号行列Ｇ'−１と乗算し、変換器９４で再度ＧＦ(２ｋ)上の元に戻して、平文ベクトルｍを得る。
【００３３】
次に暗号化に生成多項式ｇ(ｘ)を用いた実施例を示す。生成多項式ｇ(ｘ)はｎ−ｕ次元で、生体多項式から前記の暗号化行列Ｇが定まり、これによって復号行列も定まる。従って復号は前記の実施例と全く同様で、公開鍵では暗号化行列Ｇがよりデータ量の少ない生成多項式ｇ(ｘ)へ置き換えられる。平文ｍをｎ−１次の多項式ｍ(ｘ)と見なし、ｎ−１次の項からｎ−ｕ次の項までの係数は、ｍの成分（０または１，もしくはＧＦ（２ｋ）の元）である。ｍ(ｘ)のｎ−ｕ−１次から定数項までの係数は０である。ｎ−ｕ−１次の多項式ｒ(ｘ)を式(1)のように定義する。なお後半のmod２の成分を例えば０または1とするとの意味である。次に、各項の係数が拡大平文ベクトルｍ'の各項の成分となる拡大平文ｍ'の多項式表現ｍ'(ｘ)を式(2)のように定義する。
ｒ(ｘ)＝ ｍ(ｘ)  modｇ(ｘ)  mod２                            (1)
ｍ'(ｘ)＝ｍ(ｘ)＋r(ｘ)      mod２                            (2)
【００３４】
上記の手順は、ｕ個の元から成る平文ベクトルｍにｎ−ｕ個の元（ここではｎ−ｕビットのデータ）を付加して、線形符号の例である巡回符号に符号化することである。またこの実施例では、図１の暗号化部６や図９の暗号化命令９を、式(1),(2)により拡大平文ｍ'を生成するように置き換える。
【００３５】
実施例では、暗号化部６と復号部８を備えた暗号通信装置を説明したが、暗号化部６は設けなくても良い。また暗号化命令６６とナップザック復号命令６８及び線形変換命令７０を備えた暗号通信プログラムを説明したが、暗号化命令６６は設けなくても良い。
【図面の簡単な説明】
【００３６】
【図１】実施例の暗号通信装置のブロック図
【図２】実施例での秘密鍵ベクトルｖから公開鍵ベクトルａへの変換を示す図
【図３】実施例での平文ｍから拡大平文ｍ'を経て暗号文Ｃへの暗号化を示す図
【図４】実施例での暗号文Ｃから中間平文Ｍと行列Ｇ''−１を経ての、平文への復号を示す図
【図５】実施例での１段モジュラ変換による公開鍵ベクトルａの生成装置のブロック図
【図６】実施例でのＧＦ(２)上の復号行列Ｇ''−１の生成装置のブロック図
【図７】実施例でのＧＦ(２)上の暗号化装置のブロック図
【図８】実施例でのＧＦ(２)上の復号装置のブロック図
【図９】実施例の暗号通信プログラムのブロック図
【図１０】実施例での多段モジュラ変換による公開鍵ベクトルの生成装置のブロック図
【図１１】実施例でのＧＦ(２ｋ)上の復号行列Ｇ''−１の生成装置のブロック図
【図１２】実施例でのＧＦ(２ｋ)上の暗号化装置のブロック図
【図１３】実施例でのＧＦ(２ｋ)上の復号装置のブロック図
【符号の説明】
【００３７】
２          暗号通信装置
４          鍵生成記憶部
６          暗号化装置
８          復号装置
１０        通信インターフェース
２０        モジュラ変換装置
２２        乗算器
２４        剰余算器
２６        置換装置
３０        復号行列生成装置
３２，８２  列分解装置
３４，８４  置換装置
３６，８６  列連接装置
３８，８８  逆行列計算装置
４０        行列乗算器
４２        積和演算装置
５０        乗算器
５２        剰余算器
５４        ナップザック暗号復号装置
５６        行列乗算器
６０        暗号通信プログラム
６２        公開鍵ベクトル生成命令
６４        復号行列生成命令
６６        暗号化命令
６８        ナップザック復号命令
７０        線形変換命令
７２        ベクトルモジュラ変換装置
９０，９４  変換器
９２，９８  行列乗算器
９６        積和演算装置  
【図１】
2007140095.tif 000003
【図２】
2007140095.tif 000004
【図３】
2007140095.tif 000005
【図４】
2007140095.tif 000006
【図５】
2007140095.tif 000007
【図６】
2007140095.tif 000008
【図７】
2007140095.tif 000009
【図８】
2007140095.tif 000010
【図９】
2007140095.tif 000011
【図１０】
2007140095.tif 000012
【図１１】
2007140095.tif 000013
【図１２】
2007140095.tif 000014
【図１３】
2007140095.tif 000015