暗号鍵生成装置、およびその装置を利用可能な暗号化装置ならびに復号装置
【課題】ナップザック暗号は現在主流のＲＳＡ暗号と比べて暗号化および復号が短時間であり量子計算機によってさらに安全性が危うくなるということはないという利点があるが、解読法が存在する。
【解決手段】
緩増加秘密鍵生成部１０は、要素の値が単調増加に並んだベクトルであって当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成する緩増加ベクトル生成部３６と、任意の分割ベクトルにおける要素の総和よりも大きな整数を法Ｍとして生成する法Ｍ生成部３８と、法Ｍと互いに素である乗数を生成する乗数生成部４０とを含む。また、公開鍵生成部１２は、緩増加ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部４２と、分割数と公開鍵ベクトルとを公開鍵として出力する公開鍵出力部４４とを含む。
【解決手段】
緩増加秘密鍵生成部１０は、要素の値が単調増加に並んだベクトルであって当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成する緩増加ベクトル生成部３６と、任意の分割ベクトルにおける要素の総和よりも大きな整数を法Ｍとして生成する法Ｍ生成部３８と、法Ｍと互いに素である乗数を生成する乗数生成部４０とを含む。また、公開鍵生成部１２は、緩増加ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部４２と、分割数と公開鍵ベクトルとを公開鍵として出力する公開鍵出力部４４とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は暗号技術に関し、特に暗号鍵生成装置、およびその装置を利用可能な暗号化装置ならびに復号装置に関する。
【背景技術】
【０００２】
公開鍵暗号として代表的なものにＲＳＡ暗号がある。このＲＳＡ暗号の安全性は巨大数の因数分解が困難であることに依拠しているが、巨大数の因数分解は量子計算機の出現により実効的時間で可能となり、ＲＳＡ暗号の安全性は危うくなると言われている。また、ＲＳＡ暗号は暗号化や復号の計算に時間がかかるという欠点がある。
【０００３】
公開鍵暗号の一方式として、ナップザック暗号がある。ナップザック暗号は１９７８年頃にＭｅｒｋｌｅとＨｅｌｌｍａｎが提案した最初期の公開鍵暗号のひとつである（非特許文献１参照）。ナップザック暗号（以下「ＭＨ暗号」という。）の安全性は組み合わせ問題に依拠しており、量子計算機によってさらに安全性が危うくなるということはないが、解読法（非特許文献２、３参照）が存在するため、現在は実用されていない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】R.C.Merkle and M.E.Hellman, "Hiding information and signatures in trapdoor knapsacks", IEEE Transactions on Information Theory, vol. IT-24, no.5, pp.525-530, 1978.
【非特許文献２】J.C.Lagarias and A.M.Odlyzko, "Solving low density subset sum problems", Journal of ACM, vol.32, pp.229-246, 1985.
【非特許文献３】M.J.Coster, A.Joux, B.A.LaMacchia, A.M.Odlyzko, C.-P Schnorr, and J. Stern, "Improved low-density subset sum algorithms", Comput. Complexity, 2:111-128, 1992.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＭＨ暗号は暗号化が整数の足し算、復号が整数の比較と引き算からなるため、ＲＳＡ暗号に比して暗号化および復号の計算が高速であるという利点がある。また、量子計算機によってさらに安全性が危うくなるということはないという利点もある。しかしながら、ＭＨ暗号には低密度攻撃等の解読法が存在するという欠点がある。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、暗号解読に対して耐性の高い暗号鍵を生成する暗号鍵生成装置およびその装置を利用可能な暗号化装置ならびに復号装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のある態様は暗号鍵生成装置に関する。この装置は、緩増加秘密鍵生成部と公開鍵生成部とを含む。緩増加秘密鍵生成部は、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを緩増加ベクトルとして生成する緩増加ベクトル生成部と、各分割ベクトルにおける要素の総和の最大値よりも大きな整数を法Ｍとして生成する法Ｍ生成部と、法Ｍと互いに素である乗数を生成する乗数生成部とを含む。公開鍵生成部は、緩増加ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部と、分割数と公開鍵ベクトルとを公開鍵として出力する公開鍵出力部とを含む。
【０００８】
本発明の別の態様は暗号化装置に関する。この装置は、公開鍵として分割数と公開鍵ベクトルとを含む公開鍵の入力を受け付ける公開鍵受信部と、平文の入力を受け付ける平文入力部と、公開鍵ベクトルと平文とから少なくとも分割数個の暗号文を生成する暗号文生成部とを含み、公開鍵ベクトルは、緩増加ベクトルの要素をモジュラ乗算変換することで生成されたものであり、緩増加ベクトルは、前記平文のビット数と同数の要素を持つベクトルであって当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる。
【０００９】
本発明のさらに別の態様は復号装置に関する。この装置は、暗号文として複数個の暗号文を含む暗号文の入力を受け付ける暗号文受信部と、秘密鍵として緩増加ベクトルを含む秘密鍵に基づいて前記暗号文を復号する復号部とを含み、緩増加ベクトルは、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルであり、暗号文は、前記緩増加ベクトルの要素をモジュラ乗算変換することで生成された公開鍵ベクトルに基づいて暗号化されたものである。
【００１０】
本発明のさらに別の態様は暗号鍵生成方法に関する。この方法は、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成するステップと、任意の分割ベクトルにおける要素の総和よりも大きな整数を法Ｍとして生成するステップと、法Ｍと互いに素である乗数を生成するステップと、緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成するステップと、分割数と公開鍵ベクトルとを公開鍵として出力するステップとをプロセッサに実行させる。
【００１１】
本発明のさらに別の態様は、暗号鍵を生成するためのプログラムに関する。このプログラムは、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成する機能と、各分割ベクトルにおける要素の総和の最大値よりも大きな整数を法Ｍとして生成する機能と、法Ｍと互いに素である乗数を生成する機能と、緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成する機能と、分割数と公開鍵ベクトルとを公開鍵として出力する機能とをコンピュータに実現させる。
【００１２】
本発明の更に別の態様は秘密鍵生成装置に関する。この装置は、組み合わせ最適化問題の困難性により安全性を担保する暗号の鍵を生成する暗号鍵生成装置であって、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを暗号鍵として生成する。
【００１３】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１４】
本発明によれば、暗号解読に対して耐性の高い暗号のための暗号鍵を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態に係る暗号システムの全体構成図である。
【図２】図１の暗号システムによる鍵生成から暗号文の復号およびその結果の出力に至るまでの手順を説明するフローチャートである。
【図３】図１の暗号鍵生成装置の構成図である。
【図４】図３の緩増加秘密鍵生成部における緩増加秘密鍵の生成手順を説明するフローチャートである。
【図５】緩増加ベクトルを生成するための具体例を説明するフローチャートである。
【図６】暗号文生成の手順を説明するフローチャートである。
【図７】図７（ａ）は復号の手順を説明するフローチャートの前半部である。図７（ｂ）は復号の手順を説明するフローチャートの後半部である。
【発明を実施するための形態】
【００１６】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１７】
［前提技術］
［１］ 概要
実施の形態は、低密度攻撃に対するＭＨ暗号の安全性を高めることに関するものである。実施の形態の基礎技術は、ＭＨ暗号の秘密鍵を従来の超増加から緩増加に変更することにより、公開鍵ベクトルの密度を高めることである。
【００１８】
［２］ 本明細書で用いる記号の定義
平文のビット数： ｎ
秘密鍵ベクトル： ｂ
秘密鍵ベクトルの要素： ｂｉ （ｉ＝１，・・・，ｎ）
法： Ｍ
乗数： ｗ
乗数のＭを法とする逆元： ｗ−１
公開鍵ベクトル： ａ
公開鍵ベクトルの要素： ａｉ （ｉ＝１，・・・，ｎ）
平文： ｍ
平文の要素： ｍｉ （ｉ＝１，・・・，ｎ）
分割数： ｈ
補助変数： Ｓｉ （ｊ＝１，・・・，ｈ）
従来型の暗号文： Ｃ
実施の形態に係る暗号文： Ｃｉ （ｉ＝１，・・・，Ｈ，ただしＨ≧ｈ）
基底行列： ＡＬＯ
Ｃｏｓｔｅｒらの基底行列： ＡＣ
Ｆｉｅｚｅの基底行列： ＡＦ
格子： Ｌ
ａの密度： ｄ
整数全体の集合： Ｚ
【００１９】
［３］ 従来型ＭＨ暗号
［３．１］ 秘密鍵
正整数を要素とするベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）∈Ｚｎが次のような性質を有するとき、ｂは超増加（super increasing）であるという。
【数１】
法Ｍを次の式を満たすランダムな整数とする：
【数２】
Ｍをあまり大きくすると解読されやすくなるので、たとえば
【数３】
とする。
次を満たす乗数ｗをランダムに選び、更にＭを法とするｗの逆元ｗ−１を求める：
ｇｃｄ（ｗ，Ｍ）＝１、 １＜ｗ＜Ｍ （３）
ｗｗ−１≡１ （ｍｏｄ Ｍ） （４）
ここで、ｇｃｄ（ｗ，Ｍ）はｗとＭとの最大公約数を表す。
【００２０】
［３．２］ 公開鍵
秘密鍵ベクトルｂをｗとＭとを用いてモジュラ乗算変換し、公開鍵ベクトルａ＝（ａ１，ａ２，・・・，ａｎ）∈Ｚｎを作る：
ａｉ＝ｗｂｉｍｏｄ Ｍ，（ｉ＝１，２，・・・，ｎ） （５）
ここで、ｘｍｏｄ ＭはｘをＭで割った剰余ｒ、０≦ｒ＜Ｍを表す。
【００２１】
［３．３］ 暗号化
平文ｍはｎビットであるとする：
ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）∈｛０，１｝ｎ （６）
この平文に対する暗号文Ｃは次の式で与えられる。
【数４】
【００２２】
［３．４］ 復号
まず暗号文Ｃをｗの逆元ｗ−１と法Ｍとを用いるモジュラ乗算変換によりＣ’に変換する。この逆変換によって、Ｃとａとからｍを求めるという難しいナップザック問題は、Ｃ’とｂとからｍを求めるという易しいナップザック問題になる。こうして復号は次のようにして行われる。
Ｃ←ｗ−１Ｃｍｏｄ Ｍ，ｍ←０ｎ
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛ （８）
ｉｆ Ｃ≧ｂｉ ｔｈｅｎ
｛ｍｉ←１，Ｃ←Ｃ−ｂｉ｝
｝
【００２３】
［４］ 密度が高い鍵の生成法
本実施の形態に係る方式の特徴は秘密鍵生成法と、それにともなう暗号化の仕組みにある。秘密鍵が超増加ではなく、後述するように「緩増加」（slowly increasing）になる。このため、後述する密度が高くなる。そしてその結果として、ＭＨ暗号の解読の強力な方法であるＬａｇａｒｉａｓ−Ｏｄｌｙｚｋｏ法に耐性を有することになる。
【００２４】
［４．１］ 秘密鍵
ふたつの正整数ｎとｈとを定める。ｎはＭＨ暗号と同じく平文のビット数である。ｈは本実施の形態に係る方式特有のパラメータであり、ｎ以下である。ｈ＝１の場合には従来型のＭＨ暗号になる。便宜上、以下ｈを分割数という。
【００２５】
ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）∈Ｚｎは次の不等式を満たすものとする。
【数５】
ここで
【数６】
は（ｉ−１）/ｈを超えない最大の整数である。従来手法の場合の式（２）の右辺と比較すると式（９）の右辺は加算される要素の数が少ない（ｎが十分大きければ、加算される要素の数は従来手法の概ねｈ分の１になる）。したがって、従来手法に比べてｂｉは緩やかにしか増加しない数列である。そこで、式（９）を満たすことを「緩増加」と定義する。
【００２６】
式（９）においてｎ＝９、ｈ＝３の場合を以下に例示する。
ｂ２＞ｂ１
ｂ３＞ｂ２
ｂ４＞ｂ３
ｂ５＞ｂ４＋ｂ１
ｂ６＞ｂ５＋ｂ２
ｂ７＞ｂ６＋ｂ３
ｂ８＞ｂ７＋ｂ４＋ｂ１
ｂ９＞ｂ８＋ｂ５＋ｂ２
【００２７】
さらに法Ｍを、ｂｎから始めて降順にｈ個ごとに取ったｂの要素の総和より大きな整数とする：
【数７】
ここで
【数８】
は（ｎ−１）/ｈを超えない最大の整数である。これはすなわち式（１１）の右辺におけるｂｉのインデックスの最小値が１以上ｈ以下であることを意味する。また、不等式（１１）が成立すれば、ｂの任意のｈ個ごとの要素の和に対しＭは常に大きくなる。
【００２８】
Ｍと互いに素な整数ｗ，１＜ｗ＜Ｍおよびｗの法Ｍに関する逆元ｗ−１，１＜ｗ−１＜Ｍ、ｗ−１ｗ≡１（ｍｏｄ Ｍ）を定める。
以上のように定めたｂ，Ｍ，ｗ，ｗ−１を秘密鍵とする。
【００２９】
［４．２］ 公開鍵
秘密鍵ベクトルｂから公開鍵ベクトルａ＝（ａ１，ａ２，・・・，ａｎ）への変換は、従来型のＭＨ暗号の場合とまったく同じである。
ａｉ＝ｗｂｉｍｏｄ Ｍ （ｉ＝１，２，・・・，ｎ） （１３）
【００３０】
［４．３］ 暗号化
平文ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）∈｛０，１｝ｎを次のように、暗号文Ｃ１，Ｃ２，・・・，ＣＨに変換する。
Ｃ１＝Ｃ２＝・・・＝ＣＨ＝０
ｊ＝１
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛
ｉｆ ｍｉ＝１
ｔｈｅｎ｛Ｃｊ＝Ｃｊ＋ａｉ；ｊ＝ｊｍｏｄ H＋１；｝
｝
これはつまり、ａｉがＣｊに加算されるのは、ｍｉ＝１かつｍｎから始まってｍｉがｊ＋ｔｈ番目の１である時である（ｔはある整数）、ということである。
【００３１】
［４．４］ 復号
先ずＭとｗ−１とによりｈ個の暗号文Ｃｊをモジュラ乗算変換する。これは従来型のＭＨ暗号の復号と同じく公開鍵ａの要素の和を秘密鍵ｂの要素の和に変換するためである。
Ｃ’ｊ＝ｗ−１Ｃｊｍｏｄ Ｍ （ｊ＝１，２，・・・，H）
以下簡単のためＣ’ｊを改めてＣｊと書く。復号は以下のように進む。
ｍ１＝ｍ２＝・・・＝ｍｎ＝０
ｊ＝１
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛
ｉｆ Ｃｊ≧ｂｉ
ｔｈｅｎ｛ｍｉ＝１；Ｃｊ＝Ｃｊ−ｂｉ；ｊ＝ｊｍｏｄ H＋１｝
｝
これはつまり、ｍｉ＝１となるのは、Ｃｊがｂｉ以上のときである。ここでｊは１に始まるが、ｍｉ＝１としたときｊは１だけ増える（ただしHの次は１に戻る）、ということである。
【００３２】
［５］ Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏの攻撃法
Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏの攻撃法（以下「ＬＯ法」という。）は、ＭＨ暗号に対する強力な攻撃法で、低密度攻撃とも呼ばれる。後述する密度ｄがｄ＜０．６４６３のナップザック暗号は多項式時間で解読されることが証明されている。ただし整数格子の中の最短ベクトルを多項式時間で見出すアルゴリズムが存在することが仮定されている。実際にはこのようなアルゴリズムは存在しないが、実用的な近似アルゴリズムとしてＬＬＬアルゴリズムが存在する。臨界密度はその後０．６４６３から０．９４０８にまで改良されている。その結果密度が１以下であるＭＨ暗号はほとんど解読されることになった。
【００３３】
［５．１］ 従来型ＭＨ暗号のＬＯ法による攻撃
公開鍵ベクトルａと盗聴した暗号文Ｃとを用いて次のような基底行列を定義する。
【数９】
この行列のｎ＋１個の行をベクトルとみなし、これらのベクトルの整数係数の線形結合の全体Ｌを、ＡＬＯが生成する格子といい、Ｌ＝Ｌ（ＡＬＯ）と表す。
【数１０】
このとき基底行列ＡＬＯのｎ＋１個のベクトルは線形独立なので、Ｌの次元はｎ＋１である。ＬＯ法の原理は、平文に対応するベクトルがＬの比較的短いベクトルであり、したがってＬの短いベクトルを探索すれば平文が見出されるであろうというものである。実際ｉ＝１，・・・，ｎに対してｙｉ＝ｍｉで、ｙ＝１のときｙ０＝０であるから
ｖ＝（ｍ１，ｍ２，・・・，ｍｎ，０） （１６）
はＬのベクトルであり、例えば２乗ノルムは
【数１１】
となり短い。格子基底の各ベクトルをできるだけ短くすることを、格子基底縮小（または簡約）という。そしてこのための格子基底縮小アルゴリズムのひとつに前述のＬＬＬアルゴリズムがある。
【００３４】
式（１４）の他、ＬＯ法に用いられる行列は色々提案されている。よく知られたものにＣｏｓｔｅｒらが提案した
【数１２】
がある。またＦｒｉｅｚｅが提案した
【数１３】
がある。
【００３５】
［５．２］ ナップザックベクトルの密度と解読率との関係
ナップザックベクトルの密度は
ｄ＝ｎ／ｍａｘ（ｌｏｇ２ａｉ） （２０）
で定義される。
【００３６】
ＬＯ法による攻撃は極めて有効である。Ｌａｇａｒｉａｓ−ＯｄｌｙｚｋｏやＣｏｓｔｅｒらは、ｄがある値ｄｃ以下であれば、平文に対応するベクトルが格子の最短ベクトルである確率はｎが無限大になるとき漸近的に１になることを示した。さらにＬＬＬアルゴリズムを最短ベクトルを探索する近似法として用いて、上のことを実験的に検証した。従来型のＭＨ暗号では必然的にｄ＜１となり、したがってＬＯ法は従来型ＭＨ暗号の解読に有効な道具である。
【００３７】
［５．３］ 本実施の形態に係る手法の密度
以下、本実施の形態に係る手法に係る密度ｄの理論的上界について検討する。前述したとおり、本手法に係る秘密鍵ベクトルｂは緩増加となる。式（９）における不等号を等号で置き換えると、ｂｉの増加の仕方は最も緩やかになる：
【数１４】
さらに、ｂｉを公比ｒの等比数列とみなし、
ｂｉ＋１＝ｂ１ｒｉ （２２）
と置く。そして式（２１）に式（２２）を代入して両辺をｂ１で除して
【数１５】
を得る。ここで、ｉ０（０≦ｉ０＜ｈ）は式（１０）の整数ｊ１を用いてｉ０＝ｉ−１−ｊ１ｈと書くことができる。したがって
【数１６】
となる。ここで、両辺をｒ０で割って整理すると
【数１７】
となる。両辺をさらに
【数１８】
で割り、ｎが十分大きいとき、十分大きいｉについてはｊ１ｈも十分大きくなるので
【数１９】
の項を無視すれば
ｒｈ−ｒｈ−１−１＝０ （２８）
を得る。式（２８）の方程式の根が、ｂｉを等比数列と見なした場合の公比となる。
【００３８】
ベクトルｂの最大の要素はｂｎである。式（２２）より
ｂｎ＝ｂ１ｒｎ−１ （２９）
となる。
【００３９】
次にＭの大きさを式（１１）の右辺で見積もる。ここでは簡単のため、分割数ｈは平文のビット数ｎの約数であるとする。
【数２０】
ここで式（２８）よりrh-1＝rh-1を用いると
Ｍ＞ｂ１（ｒｎ−１） （３１）
を得る。
【００４０】
式（２０）より、ナップザックベクトルの密度は公開鍵ベクトルの要素の最大値を用いて定義される。式（１３）に示されるように、公開鍵ベクトルの要素は秘密鍵ベクトルの要素のＭを法とするモジュラ乗算変換で定義されるから、その可能な最大値はＭ−１である。そこで、公開鍵ベクトルの要素の最大値として式（３１）の右辺を採用し、式（２０）に代入すると以下のようになる。
【数２１】
となる。ここで、ｎが十分に大きい場合にはｎが分母となる項は無視できるので
ｄ＝１／ｌｏｇ２ｒ （３３）
となる。
【００４１】
ここで、分割数ｈ≧１のときのｈと公比ｒおよび密度ｄとの関係について考察する。式（２８）の左辺をｆ（ｘ）＝ｘｈ−ｘｈ−１−１と置き、ｆ（ｘ）におけるｈをｈ＋１に置き換えた式をｇ（ｘ）と置く。ｇ（ｘ）＝ｘｈ＋１−ｘｈ−１である。これよりｆ（０）＝ｇ（０）＝ｆ（１）＝ｇ（１）＝−１が成り立つ。ｆ（ｘ）をｘについて微分するとｆ’（ｘ）＝ｈｘｈ−１−（ｈ−１）ｘｈ−２＝ｘｈ−２（ｘ−（ｈ−１）／ｈ）を得る。ｘ＞０で考えると、ｆ’（ｘｍ）＝０となるｘｍはｘｍ＝（ｈ−１）／ｈとなる。したがって、ｆ（ｘ）は０＜ｘｍ＜１なるｘｍにおいて極小になる。
【００４２】
また、ｆ（２）＝２ｈ−２ｈ−１−１＝２ｈ−１−１≧０なので、前述のｆ（１）＝−１＜０であることおよびｆ（ｘ）が連続関数であることも考慮すると、中間値の定理より、１＜ｒ＜２でｆ（ｒ）＝０となるｒが存在する。
【００４３】
そこで、ｇ（ｘ）−ｆ（ｘ）を考える。ｇ（ｘ）−ｆ（ｘ）＝ｘｈ−１（ｘ−１）２≧０となるから、１＜ｘ≦２においてｇ（ｘ）＞ｆ（ｘ）が成り立つ。ｇ（ｒ）＞ｆ（ｒ）＝０であり、前述のｇ（１）＝−１＜０であることおよびｇ（ｘ）が連続関数であることも考慮すると、１＜ｒ１＜ｒでｇ（ｒ１）＝０となるｒ１が存在する（中間値の定理）。故に、ｈ≧１かつ１＜ｘ＜２において、ｆ（ｘ）の根ｒとｆ（ｘ）のｈをｈ＋１に置き換えた式ｇ（ｘ）の根ｒ１との関係は、１＜ｒ１＜ｒ＜２となる。換言すると、分割数ｈを大きくすれば公比ｒは小さくなる。式（３３）より、分割数ｈを大きくすれば密度ｄは大きくなる。
【００４４】
［具体例］
実施の形態
図１は、実施の形態に係る暗号システムの全体構成を表す図である。これらの構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされた暗号処理機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。後述する復号装置２００、暗号化装置３００、および暗号鍵生成装置４００の構成についても同様である。
【００４５】
暗号システム１００は、復号装置２００と暗号化装置３００とを含む。復号装置２００は、暗号鍵生成装置４００を用いて緩増加秘密鍵と公開鍵とを生成する。緩増加秘密鍵記憶部３０は、暗号鍵生成装置が生成した緩増加秘密鍵を格納する。公開鍵送信部１４は、暗号鍵生成装置４００が生成した公開鍵を、インターネット等の通信手段を通じて暗号化装置３００に送信する。
【００４６】
暗号化装置３００の公開鍵受信部１６は、暗号鍵生成装置４００が生成した公開鍵を、復号装置２００の公開鍵送信部１４から受信する。公開鍵記憶部１８は、公開鍵受信部１６が受信した公開鍵を格納する。暗号文生成部２０は、公開鍵記憶部１８から公開鍵を受け取り、平文入力部２２から入力された平文についての暗号文を生成する。暗号文送信部２４は、暗号文生成部２０から受け取った暗号文を、インターネット等の通信手段を通じて復号装置２００に送信する。
【００４７】
復号装置２００の暗号文受信部２６は、暗号化装置３００の暗号文生成部２０が生成した暗号文を暗号化装置３００の暗号文送信部２４から受信する。復号部２８は、暗号文受信部２６が受信した暗号文を、緩増加秘密鍵記憶部３０から受け取った緩増加秘密鍵を用いて復号する。平文出力部３２は、復号部２８が復号した平文を出力する。
【００４８】
図２は、以上の構成の暗号システム１００による鍵生成から暗号文の復号およびその結果の出力に至るまでの手順を説明するフローチャートである。
【００４９】
緩増加秘密鍵生成部１０は緩増加秘密鍵を生成する（Ｓ１０）。公開鍵生成部１２は、緩増加秘密鍵生成部１０から緩増加秘密鍵を受け取り、公開鍵を生成する（Ｓ１２）。公開鍵送信部１４は、公開鍵生成部１２が生成した公開鍵を、インターネット等の通信手段を通じて、暗号化装置３００に送信する（Ｓ１４）。
【００５０】
公開鍵受信部１６は、公開鍵送信部１４が送信した公開鍵を受信する（Ｓ１６）。暗号文生成部２０は、公開鍵受信部１６が受信した公開鍵を格納している公開鍵記憶部１８から公開鍵を受け取り、かつ平文入力部２２に入力された平文を受け取って、暗号文を生成する（Ｓ１８）。暗号文送信部２４は、暗号文生成部２０が生成した暗号文を、インターネット等の通信手段を通じて、復号装置２００に送信する（Ｓ２０）。
【００５１】
暗号文受信部２６は、暗号文送信部２４が送信した暗号文を受信する（Ｓ２２）。復号部２８は、緩増加秘密鍵生成部１０が生成した緩増加秘密鍵を格納している緩増加秘密鍵記憶部３０から緩増加秘密鍵を受け取り、かつ暗号文受信部２６が受信した暗号文を受け取って、暗号文を平文に復号する（Ｓ２４）。平文出力部３２は、復号部２８が復号した平文を図示しないモニタ等の出力デバイスに出力する（Ｓ２６）。
【００５２】
図３は、図１の暗号鍵生成装置４００の構成図である。暗号鍵生成装置４００は復号装置２００の内部にあり、緩増加秘密鍵生成部１０と公開鍵生成部１２とを含む。暗号鍵生成装置４００は、緩増加秘密鍵と公開鍵とを生成するものである。
【００５３】
緩増加秘密鍵生成部１０は、平文のビット数および分割数の入力部３４、緩増加ベクトル生成部３６、法Ｍ生成部３８、乗数生成部４０、逆元生成部４６および秘密鍵出力部４８を含む。また、公開鍵生成部１２は、公開鍵ベクトル生成部４２と公開鍵出力部４４とを含む。
【００５４】
平文のビット数および分割数の入力部３４は、平文のビット数ｎと分割数ｈとの入力を受け取る。緩増加ベクトル生成部３６は、平文ビット数および分割数の入力部３４から平文のビット数ｎと分割数ｈとを受け取り、緩増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を生成する。ここで緩増加ベクトル生成部３６は、緩増加ベクトルｂの要素ｂｉが、ｂｉ−１から始めて降順にｈ個ごとに取った要素の総和より大きな整数となるように緩増加ベクトルｂとして生成する。
【００５５】
上記の方法で生成された緩増加ベクトルｂは、平文のビット数と同数の要素が単調増加に並んだベクトルとなる。当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個のベクトル（以後、「分割ベクトル」という。）はそれぞれ超増加となる。
【００５６】
法Ｍ生成部３８は、緩増加ベクトル生成部３６から緩増加ベクトルｂを受け取り、ｂｎから始めて降順にｈ個ごとに取ったｂの要素の総和より大きな整数である法Ｍを生成する。乗数生成部４０は、法Ｍ生成部３８から法Ｍを受け取り、Ｍと互いに素な整数である乗数ｗを生成する。
【００５７】
上記の方法で生成された法Ｍは、任意の分割ベクトルにおける要素の総和よりも大きな整数となる。ｂｎから始めて降順にｈ個ごとに取ったｂの要素の総和は、各分割ベクトルにおける要素の総和の最大値となるからである。
【００５８】
公開鍵ベクトル生成部４２は、緩増加ベクトル生成部３６、法Ｍ生成部３８、乗数生成部４０からそれぞれ緩増加ベクトルｂ、法Ｍ、乗数ｗを受け取り、緩増加ベクトルｂの要素と乗数ｗとの積を法Ｍについてモジュラ乗算変換することで公開鍵ベクトルａを生成する。公開鍵出力部４４は、平文ビット数および分割数の入力部３４と公開鍵出力部４４とからそれぞれ分割数ｈ、公開鍵ベクトルａを受け取り、それらを合わせて公開鍵として、図１の公開鍵送信部１４に出力する。
【００５９】
逆元生成部４６は法Ｍ生成部３８と乗数生成部４０とからそれぞれ法Ｍ、乗数ｗを受け取り、Ｍを法とするｗの逆元ｗ−１を生成する。秘密鍵出力部４８は、平文ビット数および分割数の入力部３４、緩増加ベクトル生成部３６、法Ｍ生成部３８、逆元生成部４６からそれぞれ分割数ｈ、緩増加ベクトルｂ、法Ｍ、逆元ｗ−１を受け取り、それらを合わせて秘密鍵として、図１の緩増加秘密鍵記憶部３０に出力する。
【００６０】
緩増加ベクトルｂ、法Ｍ、乗数ｗ、逆元ｗ−１の生成は、前提技術[４．１]に記載のアルゴリズムに基づくものである。また、公開鍵ベクトルａの生成は、前提技術[４．２]に記載のアルゴリズムに基づくものである。
【００６１】
図４は、以上の構成の暗号鍵生成装置４００内の緩増加秘密鍵生成部１０における秘密鍵生成手順を説明するフローチャートであり、図２におけるＳ１０を詳細に説明するものである。
【００６２】
緩増加ベクトル生成部３６は、平文のビット数ｎと分割数ｈとを用いて、緩増加ベクトルｂを生成する（Ｓ２８）。法Ｍ生成部３８は、緩増加ベクトルｂを用いて、式（１０）を満たす正整数である法Ｍを生成する（Ｓ３０）。乗数生成部４０は、法Ｍを用いて、Ｍと互いに素な整数である乗数ｗを生成する（Ｓ３２）。逆元生成部４６は、法Ｍと乗数ｗとを用いて、ｗｗ−１≡１（ｍｏｄ Ｍ）を満たすｗの逆元ｗ−１を生成する（Ｓ３４）。これは例えば拡張されたユークリッドの互除法を用いれば計算することができる。
【００６３】
図５は、緩増加ベクトルｂを生成するための一例を説明するものであり、図４におけるＳ２８を、具体例を用いて詳細に説明するものである。
【００６４】
緩増加ベクトル生成部３６は平文のビット数ｎと分割数ｈとを受け取る（Ｓ３６、Ｓ３８）。ｈ個の補助変数Ｓｊ（ｊ＝１，・・・，ｈ）を０で初期化する（Ｓ４０）。補助変数Ｓｊは、緩増加ベクトルｂをｂ１から順に生成する際に、式（９）の右辺で表される和をｈ個に分割して格納するための変数である。ｂ１の初期値として、図示しない乱数生成器によって生成された乱数ｒｎｄをｂ１に格納する（Ｓ４２）。ここで乱数ｒｎｄは１〜Ｒの間の整数である。ｉをループ変数として、ｉに初期値１を入力する（Ｓ４４）。
【００６５】
Ｓ４６はループの終了を判定するステップである。Ｓ４６はループ変数ｉと平文のビット数ｎとを比較し、ｉがｎ以上となったときにループを終了する。Ｓ４８は補助変数Ｓｊのインデックスを更新するステップである。具体的には、現在のループ変数ｉを用いてｊに（（ｉ−１）ｍｏｄ ｈ）＋１を代入する。これにより、ｊは１から順に増加してｈに至ると、次は再び１に戻り、以後１〜ｈの値を繰り返すことになる。
【００６６】
Ｓ５０は補助変数Ｓｊの値を更新するステップである。Ｓ４８で計算したｊと現在のループ変数ｉとを用いて、ＳｊにＳｊ＋ｂｉを代入する。このことにより、式（９）の右辺で表される和をｈ個に分割して格納することができる。すなわち、Ｓｊは緩増加ベクトルｂの要素をｈ個ずつ間引きした要素の和となり、間引きの開始点の違いによりｈ種類生成されることになる。
【００６７】
Ｓ５２はｂｉ＋１の値を生成するステップである。Ｓ５２は、Ｓｊと図示しない乱数生成器によって生成された乱数ｒｎｄとの和を、ｂｉ＋１に格納する。乱数ｒｎｄは前述の場合と同様に１〜Ｒの間の整数である。Ｓ５４はループ変数ｉを更新するステップであり、ｉの値を１増加する。
【００６８】
以上のステップを踏むことによって生成されたベクトルｂは式（９）を満足し、緩増加となる。Ｓ５６はベクトルｂを緩増加ベクトルｂとして出力する。
【００６９】
以上述べたように、暗号鍵生成装置４００によれば、緩増加ベクトルｂを含む秘密鍵を生成することが可能となる。公開鍵ベクトルａは緩増加ベクトルｂを用いて従来手法と同様に計算することができる。
【００７０】
図１の３００は、本実施の形態に係る暗号化装置の構成図である。暗号化装置３００は、公開鍵受信部１６、公開鍵記憶部１８、暗号文生成部２０、平文入力部２２、暗号文送信部２４を含む。
【００７１】
図６は本発明の実施の形態に係る暗号文生成の手順を説明するフローチャートであり、図２におけるＳ１８を詳細に説明するものである。以下説明する暗号文生成手順は、前提技術[４．３]に記載のアルゴリズムに基づくものである。
【００７２】
Ｓ５８、Ｓ６０、Ｓ６２はそれぞれ、平文ｍ＝ｍｉ（ｉ＝１，・・・，ｎ）∈｛０，１｝ｎ、公開鍵ベクトルａ、分割数ｈの入力を受け取るステップである。Ｓ６４はｈ個の暗号文Ｃｊ（ｊ＝１，・・・，ｈ）の値を０で初期化するステップである。Ｓ６６はループ変数ｉと暗号文のインデックスｊとの初期化ステップであり、具体的にはｉの値をｎとし、ｊの値を１とするステップである。
【００７３】
Ｓ６８はループの終了を判定するステップであり、ループ変数ｉの値が０以下の場合にループを終了する。Ｓ７０は平文の要素ｍｉの値に応じて処理を分岐するステップである。平文の要素ｍｉは０または１のいずれかの値を持つから、その値に応じて処理を分岐するものである。具体的にはｍｉ＝０の場合には後述するＳ７２とＳ７４とのステップを飛ばしてＳ７６に進む。
【００７４】
Ｓ７２はＣｊの値を更新するステップである。具体的には、Ｃｊの値を、Ｃｊの値と公開鍵ベクトルのｉ番目の要素の値ａｉとを加算した値に更新する。Ｓ７４は暗号文のインデックスｊの値を更新するステップである。具体的にはｊの値を（ｊｍｏｄ ｈ）＋１に更新する。これにより、ｊは１から順に増加してｈに至ると、次は再び１に戻り、以後１〜ｈの値を繰り返すことになる。Ｓ７６はループ変数ｉを更新するステップであり、ｉの値を１減少する。Ｓ７８は、以上の手順で生成されたｈ個の暗号文Ｃｊを出力するステップである。
【００７５】
以上のステップによると、平文ｍｉの値を後ろから（ｉの大きい方から）順に調べていき、ｍｉ＝１を見つける毎に対応する公開鍵ａの要素をＣｊに加算するのであるが、加算の際に、加算先のＣｊを順に変更する、という処理が行われることになる。言い換えると、平文の要素ｍｉの値が後ろから数えてｋ番目に１となるときのインデックスの値をｍとすると、ｊ＝（ｋ−１）ｍｏｄ ｈ＋１をみたすＣｊに公開鍵ベクトルの要素ａｍの値が加算される、ということである。あるひとつの暗号文Ｃｊに加算される公開鍵ベクトルの要素ａｉのインデックスは、平文の要素ｍｉにおける１の出現パターンによって異なることになる。
【００７６】
以上述べたように、暗号化装置３００によれば、分割数ｈと、緩増加ベクトルｂを用いて生成された公開鍵ベクトルａとに基づいて平文を暗号化することができる。
【００７７】
図１の２００は、本発明の実施の形態に係る復号装置の構成図である。復号装置２００は、暗号鍵生成装置４００、公開鍵送信部１４、緩増加秘密鍵記憶部３０、暗号文受信部２６、復号部２８、平文出力部３２を含む。
【００７８】
図７は本発明の実施の形態に係る復号の手順を説明するフローチャートであり、図２におけるＳ２４を詳細に説明するものである。以下説明する復号の手順は、前提技術[４．４]に記載のアルゴリズムに基づくものである。
【００７９】
図７（ａ）におけるＳ８０、Ｓ８２、Ｓ８４、Ｓ８６、Ｓ８８はいずれも復号のための情報を受け取るステップであり、それぞれ緩増加ベクトルｂ、分割数ｈ、逆元ｗ−１、法Ｍ、暗号文Ｃｊの入力を受け取る。Ｓ９０は暗号文Ｃｊを緩増加ベクトルｂの要素の和に変換するステップである。Ｓ９２はｎ個の平文の要素ｍｉ（ｉ＝１，・・・，ｎ）の値を０で初期化するステップである。Ｓ９４はループ変数ｉと平文のインデックスｊとの初期化ステップであり、具体的にはｉの値をｎとし、ｊの値を１とするステップである。
【００８０】
図７（ｂ）は図７（ａ）の後半部分であり復号処理を行うステップである。
【００８１】
Ｓ９６はループの終了を判定するステップであり、ループ変数ｉの値が０以下の場合にループを終了する。Ｓ９８は暗号文Ｃｊと緩増加ベクトルの要素ｂｉとの大小関係による分岐のステップである。Ｃｊがｂｉより小さければ、後述するＳ１００、Ｓ１０２、Ｓ１０４を飛ばしてＳ１０６に進む。
【００８２】
Ｓ１００はＣｊがｂｉ以上であるときに、対応する平文の要素ｍｉの値を１とするステップである。ｂｉは緩増加でありかつＣｊはｂｉのいずれかの要素の和であるから、Ｃｊがｂｉ以上であればｂｉはＣｊに足された要素のひとつである。したがって、ｂｉに対応する平文の要素ｍｉの値は１である。Ｓ１０２はＣｊの値を更新するステップである。具体的にはＣｊの値をＣｊ−ｂｉに更新する。Ｓ１０４は暗号文のインデックスｊの値を更新するステップである。具体的にはｊの値を（ｊｍｏｄ ｈ）＋１に更新する。これにより、ｊは１から順に増加してｈに至ると、次は再び１に戻り、以後１〜ｈの値を繰り返すことになる。
【００８３】
Ｓ１０６はループ変数ｉを更新するステップであり、ｉの値を１減少する。Ｓ１０８は、以上の手順で生成された平文ｍを出力するステップである。
【００８４】
図６に示す暗号化のステップと図７に示す復号のステップとを比べると、インデックスの初期化ステップであるＳ６６とＳ９４およびインデックスの更新ステップであるＳ７４とＳ１０４、Ｓ７６とＳ１０６とが同一である。これは暗号化の際と復号の際との暗号文Ｃｊを変更する順序を同一にするためである。復号は後ろから（インデックスｉの値の大きい方から）順に行う必要があるという事実に合わせて暗号化も後ろから行えば、暗号化と復号の際の暗号文Ｃｊの変更順序を一致させることができ、１回で復号処理を終了できる点で有利である。
【００８５】
暗号化は前から（インデックスｉの値の小さい方から）順に行うこともできる。しかしながら、この場合には復号の際にどの暗号文Ｃｊから処理を始めればよいかは分からないため、暗号文のインデックスｊの初期値の候補として１〜ｈについて、最大でｈ回の試行錯誤を行う必要がある。
【００８６】
初期値探索の試行錯誤を省くためには、暗号化装置において、ｈ個の暗号文Ｃｊの順序を逆順にしてから復号装置に送信すればよい。より具体的には、図６のＳ７２において最後に更新処理の行われた暗号文のインデクスがｋであるとすると、ＣｋをＣ１に、Ｃｋ−１をＣ２に、Ｃｋ−２をＣ３に、・・・、Ｃｋ＋１をＣｈにする操作を行ってから送信すればよい。
【００８７】
以上説明したように緩増加ベクトルｂが既知であれば、Ｓ９６からＳ１０６のステップを踏むことで暗号文のインデックスｊを更新することができ、ｈ個の従来型ＭＨ暗号の復号と同様な処理に帰着することができる。
【００８８】
Ｃｊを緩増加ベクトルｂの要素ｂｉのいずれかの要素の和で分解する問題は組み合わせ最適化問題と呼ばれる問題に属し、一般的には要素の数が多い場合には最適解を得ることは困難とされている。しかし、もしｂが超増加であれば、前提技術[３．４]のアルゴリズムにより、Ｃｊとｂｉとの比較と引き算とで簡単に解くことができる。本実施例ではｂは超増加ではないが、ｂをｈ個の分割ベクトルに分割し、それぞれについて従来型のＭＨ暗号の復号処理と同様の処理を行うことで問題を解くことが可能となる。このために、緩増加ベクトルはそこから得られる分割ベクトルが超増加となるように設計されている。分割ベクトルが超増加となれば、緩増加ベクトルの要素を分割数以上の任意の間隔でサンプリングして得られるベクトルもまた、超増加となる。
【００８９】
したがって、本実施例の緩増加ベクトルｂは、組み合わせ最適化問題の困難性により安全性を担保する暗号であれば、その秘密鍵として利用することができる。
【００９０】
一方、緩増加ベクトルｂを知ることのできない攻撃者、すなわち暗号文Ｃｊ、公開鍵ベクトルａ、分割数ｈを盗聴した攻撃者は、盗聴した暗号文Ｃｊについてｈ個の従来型ＭＨ暗号の復号と同様な処理に分割することはできない。インデックスｊの更新は平文ｍにおける１の出現パターンに依存しているからである（図６におけるＳ７０）。
【００９１】
平文ｍを知ることのできない攻撃者がＬＯ法を用いて攻撃を試みるためには、式（１４）におけるＣの代わりにＣｊの各要素を用いるか、Ｃｊの総和を用いるか、Ｃｊの任意の部分和を用いる等の方法を取ることになる。いずれにしても式（２０）で計算される密度ｄは式（３３）に帰着し、高密度となる。すなわち、ＬＯ法に耐性を有することになる。
【００９２】
以上述べたように、復号装置２００によれば、公開鍵ベクトルａを用いて生成された暗号文Ｃｊを、緩増加ベクトルｂ、分割数ｈ、逆元ｗ−１、法Ｍを用いて復号することができる。また、緩増加ベクトルｂを知らない攻撃者に対しては、ＬＯ法に耐性を有することができる。
【００９３】
以下、本発明の実施の形態に係る暗号化および復号の手順について数値例を用いて具体的に説明する。
【００９４】
表１は平文のビット数ｎが１３で、分割数ｈの値が３の場合の暗号化および復号の数値例である。緩増加ベクトルｂは（４，６，９，・・・，２７３，４０１）の１３個の要素ｂｉ（ｉ＝１，・・・，１３）を持つベクトルであり、式（９）を満足する。法Ｍは５８７であり、ｂ１３＋ｂ１０＋ｂ７＋ｂ４＋ｂ１＝５８６よりも大きく、式（１１）を満足する。乗数ｗ＝１０１、逆元ｗ−１＝９３である。Ｍとｗは互いに素であり、これらはｗｗ−１≡１（ｍｏｄ Ｍ）である。なお表中ｗ_ｉｎｖはｗ−１を意味するものとする。
【００９５】
【表１】
【００９６】
公開鍵ベクトルａは式（５）に基づいて生成したものである。例えばａ２の値はｂ２とｗとの積（６×１０１＝６０６）を法Ｍの値である５８７で割った余りであるから１９となる。分割数ｈの値は３であるから、暗号文はＣ１、Ｃ２、Ｃ３の３つとする。
【００９７】
まず暗号化の手順について説明する。暗号化プロセスでは図６におけるＳ６６からＳ７６にしたがい、ｉ＝１３からｉ＝１に至るまで、平文ｍの要素が１であるかどうかを調べる。表１ではｉ＝１２のとき初めてｍ１２＝１となるから、Ｃ１にａ１２＝５７１の値が加算される。ｉ＝１０のとき再びｍ１０＝１となるから、今度はＣ２にａ１０＝５００の値を加算する。同様にｉ＝９のときはＣ３にａ９の値を加算する。
【００９８】
ｉ＝８のとき、ｍの要素が４度目の１となる。この場合、ａ８の値を加算すべき暗号文はＣ１に戻る。このように、ｍの要素が１となる毎にａｉの値を加算する暗号文をＣ１、Ｃ２、Ｃ３、Ｃ１、Ｃ２、Ｃ３・・・と循環しながら変更する。こうしてＣ１＝ａ１２＋ａ８＋ａ３＝１０８３、Ｃ２＝ａ１０＋ａ６＋ａ１＝１３８４、Ｃ３＝ａ９＋ａ４＝２２２となる。
【００９９】
次に復号の手順について説明する。暗号文Ｃ１、Ｃ２、Ｃ３をそれぞれＭとｗ−１とによりモジュラ乗算変換し、Ｃ’１、Ｃ’２、Ｃ’３を得る。例えば、ｗ−１×Ｃ１＝１００７１９となるが、これをＭ＝５８７で割った余りは３４２となるのでＣ’１の値は３４２となる。
【０１００】
以後は図７におけるＳ９４からＳ１０６にしたがい、ｉ＝１３からｉ＝１に至るまで順にｂｉの要素がＣ’ｊ以下であるかどうかを調べる。表２ではｉ＝１２で初めてＣ’１≧ｂ１２となる。そこでＣ’１の値をＣ’１−ｂ１２＝３４２−２７３＝６９に更新する。ｉ＝１０のときＣ’２≧ｂ１０となるから、今度はＣ’２の値をＣ’２−ｂ１０＝３２に更新する。同様にｉ＝９のとき、Ｃ’３の値をＣ’３−ｂ９＝１３とする。
【０１０１】
ｉ＝８のとき、ｂ８と大小を比較する値は、ｉ＝１２において更新されたＣ’１の値である。表１の場合、ｉ＝１２において更新されたＣ’１の値は６９であり、ｂ８の値は６０であるからＣ’１≧ｂ８となる。そこでＣ’１の値をあらためてＣ’１−ｂ８＝６９−６０＝９に更新する。以後、ｂｉの値と最新のＣ’ｊとの値の大小関係を比較してＣ’ｊ≧ｂｉとなる毎にＣ’ｊの値を更新する。最終的にＣ’１＝Ｃ’２＝Ｃ’３＝０となれば復号終了である。Ｃ’ｊ≧ｂｉとなるｉについてｍｉ＝１、それ以外をｍｉ＝０とすることで平文が得られる。
【０１０２】
表２は本発明実施の形態に係る分割数ｈと密度ｄとの関係を実験により求めた結果と理論的上界を示したものである。平文のビット数ｎを１５０とし、分割数ｈの値を１から５の間で変更したときの密度ｄを計算したものである。表の値は、秘密鍵として１００種類の鍵を用意し、それぞれの場合の密度ｄの平均値を記載したものである。表２から、分割数ｈを大きくするにしたがって密度ｄも大きくなっていることが分かる。
【０１０３】
【表２】
【０１０４】
なお、分割数の値をいくつにするかは実験により定めればよいが、一例としては平文のビット数ｎが１００または２００程度であれば分割数ｈの値は５程度とすればよい。
【０１０５】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下そのような変形例を説明する。
【０１０６】
上記の説明では、暗号文の数を分割数と同数として説明したが、一般にはＨ≧ｈとなるＨを用いてＨ個の暗号文を作成してもよい。この場合、復号プロセスにおいてＣｊのインデックスを１ずつ順に増やしてＨに至ったら次は再び１に戻し、以後１〜Ｈの値を繰り返せばよい。
【０１０７】
上記の説明では、秘密鍵として緩増加ベクトルを用いたが、緩増加ベクトルの並びを反転して降順に並べたベクトルを用いることもできる。この場合には暗号化および復号のプロセスにおけるループを逆に回せばよい。
【０１０８】
上記の説明では、実施の形態の暗号システム１００の利用例として暗号鍵生成を説明したが、これ以外に、本実施の形態における暗号鍵はデジタル署名の生成と検証に用いてもよい。
【符号の説明】
【０１０９】
１０ 緩増加秘密鍵生成部、 １２ 公開鍵生成部、 １４ 公開鍵送信部、 １６ 公開鍵受信部、 １８ 公開鍵記憶部、 ２０ 暗号文生成部、 ２２ 平文入力部、 ２４ 暗号文送信部、 ２６ 暗号文受信部、 ２８ 復号部、 ３０ 緩増加秘密鍵記憶部、 ３２ 平文出力部、 ３４ 平文ビット数および分割数の入力部、 ３６ 緩増加ベクトル生成部、 ３８ 法Ｍ生成部、 ４０ 乗数生成部、 ４２ 公開鍵ベクトル生成部、 ４４ 公開鍵出力部、 ４６ 逆元生成部、 ４８ 秘密鍵出力部、 １００ 暗号システム、 ２００ 復号装置、 ３００ 暗号化装置、 ４００ 暗号鍵生成装置。
【技術分野】
【０００１】
この発明は暗号技術に関し、特に暗号鍵生成装置、およびその装置を利用可能な暗号化装置ならびに復号装置に関する。
【背景技術】
【０００２】
公開鍵暗号として代表的なものにＲＳＡ暗号がある。このＲＳＡ暗号の安全性は巨大数の因数分解が困難であることに依拠しているが、巨大数の因数分解は量子計算機の出現により実効的時間で可能となり、ＲＳＡ暗号の安全性は危うくなると言われている。また、ＲＳＡ暗号は暗号化や復号の計算に時間がかかるという欠点がある。
【０００３】
公開鍵暗号の一方式として、ナップザック暗号がある。ナップザック暗号は１９７８年頃にＭｅｒｋｌｅとＨｅｌｌｍａｎが提案した最初期の公開鍵暗号のひとつである（非特許文献１参照）。ナップザック暗号（以下「ＭＨ暗号」という。）の安全性は組み合わせ問題に依拠しており、量子計算機によってさらに安全性が危うくなるということはないが、解読法（非特許文献２、３参照）が存在するため、現在は実用されていない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】R.C.Merkle and M.E.Hellman, "Hiding information and signatures in trapdoor knapsacks", IEEE Transactions on Information Theory, vol. IT-24, no.5, pp.525-530, 1978.
【非特許文献２】J.C.Lagarias and A.M.Odlyzko, "Solving low density subset sum problems", Journal of ACM, vol.32, pp.229-246, 1985.
【非特許文献３】M.J.Coster, A.Joux, B.A.LaMacchia, A.M.Odlyzko, C.-P Schnorr, and J. Stern, "Improved low-density subset sum algorithms", Comput. Complexity, 2:111-128, 1992.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＭＨ暗号は暗号化が整数の足し算、復号が整数の比較と引き算からなるため、ＲＳＡ暗号に比して暗号化および復号の計算が高速であるという利点がある。また、量子計算機によってさらに安全性が危うくなるということはないという利点もある。しかしながら、ＭＨ暗号には低密度攻撃等の解読法が存在するという欠点がある。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、暗号解読に対して耐性の高い暗号鍵を生成する暗号鍵生成装置およびその装置を利用可能な暗号化装置ならびに復号装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のある態様は暗号鍵生成装置に関する。この装置は、緩増加秘密鍵生成部と公開鍵生成部とを含む。緩増加秘密鍵生成部は、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを緩増加ベクトルとして生成する緩増加ベクトル生成部と、各分割ベクトルにおける要素の総和の最大値よりも大きな整数を法Ｍとして生成する法Ｍ生成部と、法Ｍと互いに素である乗数を生成する乗数生成部とを含む。公開鍵生成部は、緩増加ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部と、分割数と公開鍵ベクトルとを公開鍵として出力する公開鍵出力部とを含む。
【０００８】
本発明の別の態様は暗号化装置に関する。この装置は、公開鍵として分割数と公開鍵ベクトルとを含む公開鍵の入力を受け付ける公開鍵受信部と、平文の入力を受け付ける平文入力部と、公開鍵ベクトルと平文とから少なくとも分割数個の暗号文を生成する暗号文生成部とを含み、公開鍵ベクトルは、緩増加ベクトルの要素をモジュラ乗算変換することで生成されたものであり、緩増加ベクトルは、前記平文のビット数と同数の要素を持つベクトルであって当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる。
【０００９】
本発明のさらに別の態様は復号装置に関する。この装置は、暗号文として複数個の暗号文を含む暗号文の入力を受け付ける暗号文受信部と、秘密鍵として緩増加ベクトルを含む秘密鍵に基づいて前記暗号文を復号する復号部とを含み、緩増加ベクトルは、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルであり、暗号文は、前記緩増加ベクトルの要素をモジュラ乗算変換することで生成された公開鍵ベクトルに基づいて暗号化されたものである。
【００１０】
本発明のさらに別の態様は暗号鍵生成方法に関する。この方法は、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成するステップと、任意の分割ベクトルにおける要素の総和よりも大きな整数を法Ｍとして生成するステップと、法Ｍと互いに素である乗数を生成するステップと、緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成するステップと、分割数と公開鍵ベクトルとを公開鍵として出力するステップとをプロセッサに実行させる。
【００１１】
本発明のさらに別の態様は、暗号鍵を生成するためのプログラムに関する。このプログラムは、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成する機能と、各分割ベクトルにおける要素の総和の最大値よりも大きな整数を法Ｍとして生成する機能と、法Ｍと互いに素である乗数を生成する機能と、緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成する機能と、分割数と公開鍵ベクトルとを公開鍵として出力する機能とをコンピュータに実現させる。
【００１２】
本発明の更に別の態様は秘密鍵生成装置に関する。この装置は、組み合わせ最適化問題の困難性により安全性を担保する暗号の鍵を生成する暗号鍵生成装置であって、ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを暗号鍵として生成する。
【００１３】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１４】
本発明によれば、暗号解読に対して耐性の高い暗号のための暗号鍵を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態に係る暗号システムの全体構成図である。
【図２】図１の暗号システムによる鍵生成から暗号文の復号およびその結果の出力に至るまでの手順を説明するフローチャートである。
【図３】図１の暗号鍵生成装置の構成図である。
【図４】図３の緩増加秘密鍵生成部における緩増加秘密鍵の生成手順を説明するフローチャートである。
【図５】緩増加ベクトルを生成するための具体例を説明するフローチャートである。
【図６】暗号文生成の手順を説明するフローチャートである。
【図７】図７（ａ）は復号の手順を説明するフローチャートの前半部である。図７（ｂ）は復号の手順を説明するフローチャートの後半部である。
【発明を実施するための形態】
【００１６】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１７】
［前提技術］
［１］ 概要
実施の形態は、低密度攻撃に対するＭＨ暗号の安全性を高めることに関するものである。実施の形態の基礎技術は、ＭＨ暗号の秘密鍵を従来の超増加から緩増加に変更することにより、公開鍵ベクトルの密度を高めることである。
【００１８】
［２］ 本明細書で用いる記号の定義
平文のビット数： ｎ
秘密鍵ベクトル： ｂ
秘密鍵ベクトルの要素： ｂｉ （ｉ＝１，・・・，ｎ）
法： Ｍ
乗数： ｗ
乗数のＭを法とする逆元： ｗ−１
公開鍵ベクトル： ａ
公開鍵ベクトルの要素： ａｉ （ｉ＝１，・・・，ｎ）
平文： ｍ
平文の要素： ｍｉ （ｉ＝１，・・・，ｎ）
分割数： ｈ
補助変数： Ｓｉ （ｊ＝１，・・・，ｈ）
従来型の暗号文： Ｃ
実施の形態に係る暗号文： Ｃｉ （ｉ＝１，・・・，Ｈ，ただしＨ≧ｈ）
基底行列： ＡＬＯ
Ｃｏｓｔｅｒらの基底行列： ＡＣ
Ｆｉｅｚｅの基底行列： ＡＦ
格子： Ｌ
ａの密度： ｄ
整数全体の集合： Ｚ
【００１９】
［３］ 従来型ＭＨ暗号
［３．１］ 秘密鍵
正整数を要素とするベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）∈Ｚｎが次のような性質を有するとき、ｂは超増加（super increasing）であるという。
【数１】
法Ｍを次の式を満たすランダムな整数とする：
【数２】
Ｍをあまり大きくすると解読されやすくなるので、たとえば
【数３】
とする。
次を満たす乗数ｗをランダムに選び、更にＭを法とするｗの逆元ｗ−１を求める：
ｇｃｄ（ｗ，Ｍ）＝１、 １＜ｗ＜Ｍ （３）
ｗｗ−１≡１ （ｍｏｄ Ｍ） （４）
ここで、ｇｃｄ（ｗ，Ｍ）はｗとＭとの最大公約数を表す。
【００２０】
［３．２］ 公開鍵
秘密鍵ベクトルｂをｗとＭとを用いてモジュラ乗算変換し、公開鍵ベクトルａ＝（ａ１，ａ２，・・・，ａｎ）∈Ｚｎを作る：
ａｉ＝ｗｂｉｍｏｄ Ｍ，（ｉ＝１，２，・・・，ｎ） （５）
ここで、ｘｍｏｄ ＭはｘをＭで割った剰余ｒ、０≦ｒ＜Ｍを表す。
【００２１】
［３．３］ 暗号化
平文ｍはｎビットであるとする：
ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）∈｛０，１｝ｎ （６）
この平文に対する暗号文Ｃは次の式で与えられる。
【数４】
【００２２】
［３．４］ 復号
まず暗号文Ｃをｗの逆元ｗ−１と法Ｍとを用いるモジュラ乗算変換によりＣ’に変換する。この逆変換によって、Ｃとａとからｍを求めるという難しいナップザック問題は、Ｃ’とｂとからｍを求めるという易しいナップザック問題になる。こうして復号は次のようにして行われる。
Ｃ←ｗ−１Ｃｍｏｄ Ｍ，ｍ←０ｎ
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛ （８）
ｉｆ Ｃ≧ｂｉ ｔｈｅｎ
｛ｍｉ←１，Ｃ←Ｃ−ｂｉ｝
｝
【００２３】
［４］ 密度が高い鍵の生成法
本実施の形態に係る方式の特徴は秘密鍵生成法と、それにともなう暗号化の仕組みにある。秘密鍵が超増加ではなく、後述するように「緩増加」（slowly increasing）になる。このため、後述する密度が高くなる。そしてその結果として、ＭＨ暗号の解読の強力な方法であるＬａｇａｒｉａｓ−Ｏｄｌｙｚｋｏ法に耐性を有することになる。
【００２４】
［４．１］ 秘密鍵
ふたつの正整数ｎとｈとを定める。ｎはＭＨ暗号と同じく平文のビット数である。ｈは本実施の形態に係る方式特有のパラメータであり、ｎ以下である。ｈ＝１の場合には従来型のＭＨ暗号になる。便宜上、以下ｈを分割数という。
【００２５】
ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）∈Ｚｎは次の不等式を満たすものとする。
【数５】
ここで
【数６】
は（ｉ−１）/ｈを超えない最大の整数である。従来手法の場合の式（２）の右辺と比較すると式（９）の右辺は加算される要素の数が少ない（ｎが十分大きければ、加算される要素の数は従来手法の概ねｈ分の１になる）。したがって、従来手法に比べてｂｉは緩やかにしか増加しない数列である。そこで、式（９）を満たすことを「緩増加」と定義する。
【００２６】
式（９）においてｎ＝９、ｈ＝３の場合を以下に例示する。
ｂ２＞ｂ１
ｂ３＞ｂ２
ｂ４＞ｂ３
ｂ５＞ｂ４＋ｂ１
ｂ６＞ｂ５＋ｂ２
ｂ７＞ｂ６＋ｂ３
ｂ８＞ｂ７＋ｂ４＋ｂ１
ｂ９＞ｂ８＋ｂ５＋ｂ２
【００２７】
さらに法Ｍを、ｂｎから始めて降順にｈ個ごとに取ったｂの要素の総和より大きな整数とする：
【数７】
ここで
【数８】
は（ｎ−１）/ｈを超えない最大の整数である。これはすなわち式（１１）の右辺におけるｂｉのインデックスの最小値が１以上ｈ以下であることを意味する。また、不等式（１１）が成立すれば、ｂの任意のｈ個ごとの要素の和に対しＭは常に大きくなる。
【００２８】
Ｍと互いに素な整数ｗ，１＜ｗ＜Ｍおよびｗの法Ｍに関する逆元ｗ−１，１＜ｗ−１＜Ｍ、ｗ−１ｗ≡１（ｍｏｄ Ｍ）を定める。
以上のように定めたｂ，Ｍ，ｗ，ｗ−１を秘密鍵とする。
【００２９】
［４．２］ 公開鍵
秘密鍵ベクトルｂから公開鍵ベクトルａ＝（ａ１，ａ２，・・・，ａｎ）への変換は、従来型のＭＨ暗号の場合とまったく同じである。
ａｉ＝ｗｂｉｍｏｄ Ｍ （ｉ＝１，２，・・・，ｎ） （１３）
【００３０】
［４．３］ 暗号化
平文ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）∈｛０，１｝ｎを次のように、暗号文Ｃ１，Ｃ２，・・・，ＣＨに変換する。
Ｃ１＝Ｃ２＝・・・＝ＣＨ＝０
ｊ＝１
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛
ｉｆ ｍｉ＝１
ｔｈｅｎ｛Ｃｊ＝Ｃｊ＋ａｉ；ｊ＝ｊｍｏｄ H＋１；｝
｝
これはつまり、ａｉがＣｊに加算されるのは、ｍｉ＝１かつｍｎから始まってｍｉがｊ＋ｔｈ番目の１である時である（ｔはある整数）、ということである。
【００３１】
［４．４］ 復号
先ずＭとｗ−１とによりｈ個の暗号文Ｃｊをモジュラ乗算変換する。これは従来型のＭＨ暗号の復号と同じく公開鍵ａの要素の和を秘密鍵ｂの要素の和に変換するためである。
Ｃ’ｊ＝ｗ−１Ｃｊｍｏｄ Ｍ （ｊ＝１，２，・・・，H）
以下簡単のためＣ’ｊを改めてＣｊと書く。復号は以下のように進む。
ｍ１＝ｍ２＝・・・＝ｍｎ＝０
ｊ＝１
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛
ｉｆ Ｃｊ≧ｂｉ
ｔｈｅｎ｛ｍｉ＝１；Ｃｊ＝Ｃｊ−ｂｉ；ｊ＝ｊｍｏｄ H＋１｝
｝
これはつまり、ｍｉ＝１となるのは、Ｃｊがｂｉ以上のときである。ここでｊは１に始まるが、ｍｉ＝１としたときｊは１だけ増える（ただしHの次は１に戻る）、ということである。
【００３２】
［５］ Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏの攻撃法
Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏの攻撃法（以下「ＬＯ法」という。）は、ＭＨ暗号に対する強力な攻撃法で、低密度攻撃とも呼ばれる。後述する密度ｄがｄ＜０．６４６３のナップザック暗号は多項式時間で解読されることが証明されている。ただし整数格子の中の最短ベクトルを多項式時間で見出すアルゴリズムが存在することが仮定されている。実際にはこのようなアルゴリズムは存在しないが、実用的な近似アルゴリズムとしてＬＬＬアルゴリズムが存在する。臨界密度はその後０．６４６３から０．９４０８にまで改良されている。その結果密度が１以下であるＭＨ暗号はほとんど解読されることになった。
【００３３】
［５．１］ 従来型ＭＨ暗号のＬＯ法による攻撃
公開鍵ベクトルａと盗聴した暗号文Ｃとを用いて次のような基底行列を定義する。
【数９】
この行列のｎ＋１個の行をベクトルとみなし、これらのベクトルの整数係数の線形結合の全体Ｌを、ＡＬＯが生成する格子といい、Ｌ＝Ｌ（ＡＬＯ）と表す。
【数１０】
このとき基底行列ＡＬＯのｎ＋１個のベクトルは線形独立なので、Ｌの次元はｎ＋１である。ＬＯ法の原理は、平文に対応するベクトルがＬの比較的短いベクトルであり、したがってＬの短いベクトルを探索すれば平文が見出されるであろうというものである。実際ｉ＝１，・・・，ｎに対してｙｉ＝ｍｉで、ｙ＝１のときｙ０＝０であるから
ｖ＝（ｍ１，ｍ２，・・・，ｍｎ，０） （１６）
はＬのベクトルであり、例えば２乗ノルムは
【数１１】
となり短い。格子基底の各ベクトルをできるだけ短くすることを、格子基底縮小（または簡約）という。そしてこのための格子基底縮小アルゴリズムのひとつに前述のＬＬＬアルゴリズムがある。
【００３４】
式（１４）の他、ＬＯ法に用いられる行列は色々提案されている。よく知られたものにＣｏｓｔｅｒらが提案した
【数１２】
がある。またＦｒｉｅｚｅが提案した
【数１３】
がある。
【００３５】
［５．２］ ナップザックベクトルの密度と解読率との関係
ナップザックベクトルの密度は
ｄ＝ｎ／ｍａｘ（ｌｏｇ２ａｉ） （２０）
で定義される。
【００３６】
ＬＯ法による攻撃は極めて有効である。Ｌａｇａｒｉａｓ−ＯｄｌｙｚｋｏやＣｏｓｔｅｒらは、ｄがある値ｄｃ以下であれば、平文に対応するベクトルが格子の最短ベクトルである確率はｎが無限大になるとき漸近的に１になることを示した。さらにＬＬＬアルゴリズムを最短ベクトルを探索する近似法として用いて、上のことを実験的に検証した。従来型のＭＨ暗号では必然的にｄ＜１となり、したがってＬＯ法は従来型ＭＨ暗号の解読に有効な道具である。
【００３７】
［５．３］ 本実施の形態に係る手法の密度
以下、本実施の形態に係る手法に係る密度ｄの理論的上界について検討する。前述したとおり、本手法に係る秘密鍵ベクトルｂは緩増加となる。式（９）における不等号を等号で置き換えると、ｂｉの増加の仕方は最も緩やかになる：
【数１４】
さらに、ｂｉを公比ｒの等比数列とみなし、
ｂｉ＋１＝ｂ１ｒｉ （２２）
と置く。そして式（２１）に式（２２）を代入して両辺をｂ１で除して
【数１５】
を得る。ここで、ｉ０（０≦ｉ０＜ｈ）は式（１０）の整数ｊ１を用いてｉ０＝ｉ−１−ｊ１ｈと書くことができる。したがって
【数１６】
となる。ここで、両辺をｒ０で割って整理すると
【数１７】
となる。両辺をさらに
【数１８】
で割り、ｎが十分大きいとき、十分大きいｉについてはｊ１ｈも十分大きくなるので
【数１９】
の項を無視すれば
ｒｈ−ｒｈ−１−１＝０ （２８）
を得る。式（２８）の方程式の根が、ｂｉを等比数列と見なした場合の公比となる。
【００３８】
ベクトルｂの最大の要素はｂｎである。式（２２）より
ｂｎ＝ｂ１ｒｎ−１ （２９）
となる。
【００３９】
次にＭの大きさを式（１１）の右辺で見積もる。ここでは簡単のため、分割数ｈは平文のビット数ｎの約数であるとする。
【数２０】
ここで式（２８）よりrh-1＝rh-1を用いると
Ｍ＞ｂ１（ｒｎ−１） （３１）
を得る。
【００４０】
式（２０）より、ナップザックベクトルの密度は公開鍵ベクトルの要素の最大値を用いて定義される。式（１３）に示されるように、公開鍵ベクトルの要素は秘密鍵ベクトルの要素のＭを法とするモジュラ乗算変換で定義されるから、その可能な最大値はＭ−１である。そこで、公開鍵ベクトルの要素の最大値として式（３１）の右辺を採用し、式（２０）に代入すると以下のようになる。
【数２１】
となる。ここで、ｎが十分に大きい場合にはｎが分母となる項は無視できるので
ｄ＝１／ｌｏｇ２ｒ （３３）
となる。
【００４１】
ここで、分割数ｈ≧１のときのｈと公比ｒおよび密度ｄとの関係について考察する。式（２８）の左辺をｆ（ｘ）＝ｘｈ−ｘｈ−１−１と置き、ｆ（ｘ）におけるｈをｈ＋１に置き換えた式をｇ（ｘ）と置く。ｇ（ｘ）＝ｘｈ＋１−ｘｈ−１である。これよりｆ（０）＝ｇ（０）＝ｆ（１）＝ｇ（１）＝−１が成り立つ。ｆ（ｘ）をｘについて微分するとｆ’（ｘ）＝ｈｘｈ−１−（ｈ−１）ｘｈ−２＝ｘｈ−２（ｘ−（ｈ−１）／ｈ）を得る。ｘ＞０で考えると、ｆ’（ｘｍ）＝０となるｘｍはｘｍ＝（ｈ−１）／ｈとなる。したがって、ｆ（ｘ）は０＜ｘｍ＜１なるｘｍにおいて極小になる。
【００４２】
また、ｆ（２）＝２ｈ−２ｈ−１−１＝２ｈ−１−１≧０なので、前述のｆ（１）＝−１＜０であることおよびｆ（ｘ）が連続関数であることも考慮すると、中間値の定理より、１＜ｒ＜２でｆ（ｒ）＝０となるｒが存在する。
【００４３】
そこで、ｇ（ｘ）−ｆ（ｘ）を考える。ｇ（ｘ）−ｆ（ｘ）＝ｘｈ−１（ｘ−１）２≧０となるから、１＜ｘ≦２においてｇ（ｘ）＞ｆ（ｘ）が成り立つ。ｇ（ｒ）＞ｆ（ｒ）＝０であり、前述のｇ（１）＝−１＜０であることおよびｇ（ｘ）が連続関数であることも考慮すると、１＜ｒ１＜ｒでｇ（ｒ１）＝０となるｒ１が存在する（中間値の定理）。故に、ｈ≧１かつ１＜ｘ＜２において、ｆ（ｘ）の根ｒとｆ（ｘ）のｈをｈ＋１に置き換えた式ｇ（ｘ）の根ｒ１との関係は、１＜ｒ１＜ｒ＜２となる。換言すると、分割数ｈを大きくすれば公比ｒは小さくなる。式（３３）より、分割数ｈを大きくすれば密度ｄは大きくなる。
【００４４】
［具体例］
実施の形態
図１は、実施の形態に係る暗号システムの全体構成を表す図である。これらの構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされた暗号処理機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。後述する復号装置２００、暗号化装置３００、および暗号鍵生成装置４００の構成についても同様である。
【００４５】
暗号システム１００は、復号装置２００と暗号化装置３００とを含む。復号装置２００は、暗号鍵生成装置４００を用いて緩増加秘密鍵と公開鍵とを生成する。緩増加秘密鍵記憶部３０は、暗号鍵生成装置が生成した緩増加秘密鍵を格納する。公開鍵送信部１４は、暗号鍵生成装置４００が生成した公開鍵を、インターネット等の通信手段を通じて暗号化装置３００に送信する。
【００４６】
暗号化装置３００の公開鍵受信部１６は、暗号鍵生成装置４００が生成した公開鍵を、復号装置２００の公開鍵送信部１４から受信する。公開鍵記憶部１８は、公開鍵受信部１６が受信した公開鍵を格納する。暗号文生成部２０は、公開鍵記憶部１８から公開鍵を受け取り、平文入力部２２から入力された平文についての暗号文を生成する。暗号文送信部２４は、暗号文生成部２０から受け取った暗号文を、インターネット等の通信手段を通じて復号装置２００に送信する。
【００４７】
復号装置２００の暗号文受信部２６は、暗号化装置３００の暗号文生成部２０が生成した暗号文を暗号化装置３００の暗号文送信部２４から受信する。復号部２８は、暗号文受信部２６が受信した暗号文を、緩増加秘密鍵記憶部３０から受け取った緩増加秘密鍵を用いて復号する。平文出力部３２は、復号部２８が復号した平文を出力する。
【００４８】
図２は、以上の構成の暗号システム１００による鍵生成から暗号文の復号およびその結果の出力に至るまでの手順を説明するフローチャートである。
【００４９】
緩増加秘密鍵生成部１０は緩増加秘密鍵を生成する（Ｓ１０）。公開鍵生成部１２は、緩増加秘密鍵生成部１０から緩増加秘密鍵を受け取り、公開鍵を生成する（Ｓ１２）。公開鍵送信部１４は、公開鍵生成部１２が生成した公開鍵を、インターネット等の通信手段を通じて、暗号化装置３００に送信する（Ｓ１４）。
【００５０】
公開鍵受信部１６は、公開鍵送信部１４が送信した公開鍵を受信する（Ｓ１６）。暗号文生成部２０は、公開鍵受信部１６が受信した公開鍵を格納している公開鍵記憶部１８から公開鍵を受け取り、かつ平文入力部２２に入力された平文を受け取って、暗号文を生成する（Ｓ１８）。暗号文送信部２４は、暗号文生成部２０が生成した暗号文を、インターネット等の通信手段を通じて、復号装置２００に送信する（Ｓ２０）。
【００５１】
暗号文受信部２６は、暗号文送信部２４が送信した暗号文を受信する（Ｓ２２）。復号部２８は、緩増加秘密鍵生成部１０が生成した緩増加秘密鍵を格納している緩増加秘密鍵記憶部３０から緩増加秘密鍵を受け取り、かつ暗号文受信部２６が受信した暗号文を受け取って、暗号文を平文に復号する（Ｓ２４）。平文出力部３２は、復号部２８が復号した平文を図示しないモニタ等の出力デバイスに出力する（Ｓ２６）。
【００５２】
図３は、図１の暗号鍵生成装置４００の構成図である。暗号鍵生成装置４００は復号装置２００の内部にあり、緩増加秘密鍵生成部１０と公開鍵生成部１２とを含む。暗号鍵生成装置４００は、緩増加秘密鍵と公開鍵とを生成するものである。
【００５３】
緩増加秘密鍵生成部１０は、平文のビット数および分割数の入力部３４、緩増加ベクトル生成部３６、法Ｍ生成部３８、乗数生成部４０、逆元生成部４６および秘密鍵出力部４８を含む。また、公開鍵生成部１２は、公開鍵ベクトル生成部４２と公開鍵出力部４４とを含む。
【００５４】
平文のビット数および分割数の入力部３４は、平文のビット数ｎと分割数ｈとの入力を受け取る。緩増加ベクトル生成部３６は、平文ビット数および分割数の入力部３４から平文のビット数ｎと分割数ｈとを受け取り、緩増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を生成する。ここで緩増加ベクトル生成部３６は、緩増加ベクトルｂの要素ｂｉが、ｂｉ−１から始めて降順にｈ個ごとに取った要素の総和より大きな整数となるように緩増加ベクトルｂとして生成する。
【００５５】
上記の方法で生成された緩増加ベクトルｂは、平文のビット数と同数の要素が単調増加に並んだベクトルとなる。当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個のベクトル（以後、「分割ベクトル」という。）はそれぞれ超増加となる。
【００５６】
法Ｍ生成部３８は、緩増加ベクトル生成部３６から緩増加ベクトルｂを受け取り、ｂｎから始めて降順にｈ個ごとに取ったｂの要素の総和より大きな整数である法Ｍを生成する。乗数生成部４０は、法Ｍ生成部３８から法Ｍを受け取り、Ｍと互いに素な整数である乗数ｗを生成する。
【００５７】
上記の方法で生成された法Ｍは、任意の分割ベクトルにおける要素の総和よりも大きな整数となる。ｂｎから始めて降順にｈ個ごとに取ったｂの要素の総和は、各分割ベクトルにおける要素の総和の最大値となるからである。
【００５８】
公開鍵ベクトル生成部４２は、緩増加ベクトル生成部３６、法Ｍ生成部３８、乗数生成部４０からそれぞれ緩増加ベクトルｂ、法Ｍ、乗数ｗを受け取り、緩増加ベクトルｂの要素と乗数ｗとの積を法Ｍについてモジュラ乗算変換することで公開鍵ベクトルａを生成する。公開鍵出力部４４は、平文ビット数および分割数の入力部３４と公開鍵出力部４４とからそれぞれ分割数ｈ、公開鍵ベクトルａを受け取り、それらを合わせて公開鍵として、図１の公開鍵送信部１４に出力する。
【００５９】
逆元生成部４６は法Ｍ生成部３８と乗数生成部４０とからそれぞれ法Ｍ、乗数ｗを受け取り、Ｍを法とするｗの逆元ｗ−１を生成する。秘密鍵出力部４８は、平文ビット数および分割数の入力部３４、緩増加ベクトル生成部３６、法Ｍ生成部３８、逆元生成部４６からそれぞれ分割数ｈ、緩増加ベクトルｂ、法Ｍ、逆元ｗ−１を受け取り、それらを合わせて秘密鍵として、図１の緩増加秘密鍵記憶部３０に出力する。
【００６０】
緩増加ベクトルｂ、法Ｍ、乗数ｗ、逆元ｗ−１の生成は、前提技術[４．１]に記載のアルゴリズムに基づくものである。また、公開鍵ベクトルａの生成は、前提技術[４．２]に記載のアルゴリズムに基づくものである。
【００６１】
図４は、以上の構成の暗号鍵生成装置４００内の緩増加秘密鍵生成部１０における秘密鍵生成手順を説明するフローチャートであり、図２におけるＳ１０を詳細に説明するものである。
【００６２】
緩増加ベクトル生成部３６は、平文のビット数ｎと分割数ｈとを用いて、緩増加ベクトルｂを生成する（Ｓ２８）。法Ｍ生成部３８は、緩増加ベクトルｂを用いて、式（１０）を満たす正整数である法Ｍを生成する（Ｓ３０）。乗数生成部４０は、法Ｍを用いて、Ｍと互いに素な整数である乗数ｗを生成する（Ｓ３２）。逆元生成部４６は、法Ｍと乗数ｗとを用いて、ｗｗ−１≡１（ｍｏｄ Ｍ）を満たすｗの逆元ｗ−１を生成する（Ｓ３４）。これは例えば拡張されたユークリッドの互除法を用いれば計算することができる。
【００６３】
図５は、緩増加ベクトルｂを生成するための一例を説明するものであり、図４におけるＳ２８を、具体例を用いて詳細に説明するものである。
【００６４】
緩増加ベクトル生成部３６は平文のビット数ｎと分割数ｈとを受け取る（Ｓ３６、Ｓ３８）。ｈ個の補助変数Ｓｊ（ｊ＝１，・・・，ｈ）を０で初期化する（Ｓ４０）。補助変数Ｓｊは、緩増加ベクトルｂをｂ１から順に生成する際に、式（９）の右辺で表される和をｈ個に分割して格納するための変数である。ｂ１の初期値として、図示しない乱数生成器によって生成された乱数ｒｎｄをｂ１に格納する（Ｓ４２）。ここで乱数ｒｎｄは１〜Ｒの間の整数である。ｉをループ変数として、ｉに初期値１を入力する（Ｓ４４）。
【００６５】
Ｓ４６はループの終了を判定するステップである。Ｓ４６はループ変数ｉと平文のビット数ｎとを比較し、ｉがｎ以上となったときにループを終了する。Ｓ４８は補助変数Ｓｊのインデックスを更新するステップである。具体的には、現在のループ変数ｉを用いてｊに（（ｉ−１）ｍｏｄ ｈ）＋１を代入する。これにより、ｊは１から順に増加してｈに至ると、次は再び１に戻り、以後１〜ｈの値を繰り返すことになる。
【００６６】
Ｓ５０は補助変数Ｓｊの値を更新するステップである。Ｓ４８で計算したｊと現在のループ変数ｉとを用いて、ＳｊにＳｊ＋ｂｉを代入する。このことにより、式（９）の右辺で表される和をｈ個に分割して格納することができる。すなわち、Ｓｊは緩増加ベクトルｂの要素をｈ個ずつ間引きした要素の和となり、間引きの開始点の違いによりｈ種類生成されることになる。
【００６７】
Ｓ５２はｂｉ＋１の値を生成するステップである。Ｓ５２は、Ｓｊと図示しない乱数生成器によって生成された乱数ｒｎｄとの和を、ｂｉ＋１に格納する。乱数ｒｎｄは前述の場合と同様に１〜Ｒの間の整数である。Ｓ５４はループ変数ｉを更新するステップであり、ｉの値を１増加する。
【００６８】
以上のステップを踏むことによって生成されたベクトルｂは式（９）を満足し、緩増加となる。Ｓ５６はベクトルｂを緩増加ベクトルｂとして出力する。
【００６９】
以上述べたように、暗号鍵生成装置４００によれば、緩増加ベクトルｂを含む秘密鍵を生成することが可能となる。公開鍵ベクトルａは緩増加ベクトルｂを用いて従来手法と同様に計算することができる。
【００７０】
図１の３００は、本実施の形態に係る暗号化装置の構成図である。暗号化装置３００は、公開鍵受信部１６、公開鍵記憶部１８、暗号文生成部２０、平文入力部２２、暗号文送信部２４を含む。
【００７１】
図６は本発明の実施の形態に係る暗号文生成の手順を説明するフローチャートであり、図２におけるＳ１８を詳細に説明するものである。以下説明する暗号文生成手順は、前提技術[４．３]に記載のアルゴリズムに基づくものである。
【００７２】
Ｓ５８、Ｓ６０、Ｓ６２はそれぞれ、平文ｍ＝ｍｉ（ｉ＝１，・・・，ｎ）∈｛０，１｝ｎ、公開鍵ベクトルａ、分割数ｈの入力を受け取るステップである。Ｓ６４はｈ個の暗号文Ｃｊ（ｊ＝１，・・・，ｈ）の値を０で初期化するステップである。Ｓ６６はループ変数ｉと暗号文のインデックスｊとの初期化ステップであり、具体的にはｉの値をｎとし、ｊの値を１とするステップである。
【００７３】
Ｓ６８はループの終了を判定するステップであり、ループ変数ｉの値が０以下の場合にループを終了する。Ｓ７０は平文の要素ｍｉの値に応じて処理を分岐するステップである。平文の要素ｍｉは０または１のいずれかの値を持つから、その値に応じて処理を分岐するものである。具体的にはｍｉ＝０の場合には後述するＳ７２とＳ７４とのステップを飛ばしてＳ７６に進む。
【００７４】
Ｓ７２はＣｊの値を更新するステップである。具体的には、Ｃｊの値を、Ｃｊの値と公開鍵ベクトルのｉ番目の要素の値ａｉとを加算した値に更新する。Ｓ７４は暗号文のインデックスｊの値を更新するステップである。具体的にはｊの値を（ｊｍｏｄ ｈ）＋１に更新する。これにより、ｊは１から順に増加してｈに至ると、次は再び１に戻り、以後１〜ｈの値を繰り返すことになる。Ｓ７６はループ変数ｉを更新するステップであり、ｉの値を１減少する。Ｓ７８は、以上の手順で生成されたｈ個の暗号文Ｃｊを出力するステップである。
【００７５】
以上のステップによると、平文ｍｉの値を後ろから（ｉの大きい方から）順に調べていき、ｍｉ＝１を見つける毎に対応する公開鍵ａの要素をＣｊに加算するのであるが、加算の際に、加算先のＣｊを順に変更する、という処理が行われることになる。言い換えると、平文の要素ｍｉの値が後ろから数えてｋ番目に１となるときのインデックスの値をｍとすると、ｊ＝（ｋ−１）ｍｏｄ ｈ＋１をみたすＣｊに公開鍵ベクトルの要素ａｍの値が加算される、ということである。あるひとつの暗号文Ｃｊに加算される公開鍵ベクトルの要素ａｉのインデックスは、平文の要素ｍｉにおける１の出現パターンによって異なることになる。
【００７６】
以上述べたように、暗号化装置３００によれば、分割数ｈと、緩増加ベクトルｂを用いて生成された公開鍵ベクトルａとに基づいて平文を暗号化することができる。
【００７７】
図１の２００は、本発明の実施の形態に係る復号装置の構成図である。復号装置２００は、暗号鍵生成装置４００、公開鍵送信部１４、緩増加秘密鍵記憶部３０、暗号文受信部２６、復号部２８、平文出力部３２を含む。
【００７８】
図７は本発明の実施の形態に係る復号の手順を説明するフローチャートであり、図２におけるＳ２４を詳細に説明するものである。以下説明する復号の手順は、前提技術[４．４]に記載のアルゴリズムに基づくものである。
【００７９】
図７（ａ）におけるＳ８０、Ｓ８２、Ｓ８４、Ｓ８６、Ｓ８８はいずれも復号のための情報を受け取るステップであり、それぞれ緩増加ベクトルｂ、分割数ｈ、逆元ｗ−１、法Ｍ、暗号文Ｃｊの入力を受け取る。Ｓ９０は暗号文Ｃｊを緩増加ベクトルｂの要素の和に変換するステップである。Ｓ９２はｎ個の平文の要素ｍｉ（ｉ＝１，・・・，ｎ）の値を０で初期化するステップである。Ｓ９４はループ変数ｉと平文のインデックスｊとの初期化ステップであり、具体的にはｉの値をｎとし、ｊの値を１とするステップである。
【００８０】
図７（ｂ）は図７（ａ）の後半部分であり復号処理を行うステップである。
【００８１】
Ｓ９６はループの終了を判定するステップであり、ループ変数ｉの値が０以下の場合にループを終了する。Ｓ９８は暗号文Ｃｊと緩増加ベクトルの要素ｂｉとの大小関係による分岐のステップである。Ｃｊがｂｉより小さければ、後述するＳ１００、Ｓ１０２、Ｓ１０４を飛ばしてＳ１０６に進む。
【００８２】
Ｓ１００はＣｊがｂｉ以上であるときに、対応する平文の要素ｍｉの値を１とするステップである。ｂｉは緩増加でありかつＣｊはｂｉのいずれかの要素の和であるから、Ｃｊがｂｉ以上であればｂｉはＣｊに足された要素のひとつである。したがって、ｂｉに対応する平文の要素ｍｉの値は１である。Ｓ１０２はＣｊの値を更新するステップである。具体的にはＣｊの値をＣｊ−ｂｉに更新する。Ｓ１０４は暗号文のインデックスｊの値を更新するステップである。具体的にはｊの値を（ｊｍｏｄ ｈ）＋１に更新する。これにより、ｊは１から順に増加してｈに至ると、次は再び１に戻り、以後１〜ｈの値を繰り返すことになる。
【００８３】
Ｓ１０６はループ変数ｉを更新するステップであり、ｉの値を１減少する。Ｓ１０８は、以上の手順で生成された平文ｍを出力するステップである。
【００８４】
図６に示す暗号化のステップと図７に示す復号のステップとを比べると、インデックスの初期化ステップであるＳ６６とＳ９４およびインデックスの更新ステップであるＳ７４とＳ１０４、Ｓ７６とＳ１０６とが同一である。これは暗号化の際と復号の際との暗号文Ｃｊを変更する順序を同一にするためである。復号は後ろから（インデックスｉの値の大きい方から）順に行う必要があるという事実に合わせて暗号化も後ろから行えば、暗号化と復号の際の暗号文Ｃｊの変更順序を一致させることができ、１回で復号処理を終了できる点で有利である。
【００８５】
暗号化は前から（インデックスｉの値の小さい方から）順に行うこともできる。しかしながら、この場合には復号の際にどの暗号文Ｃｊから処理を始めればよいかは分からないため、暗号文のインデックスｊの初期値の候補として１〜ｈについて、最大でｈ回の試行錯誤を行う必要がある。
【００８６】
初期値探索の試行錯誤を省くためには、暗号化装置において、ｈ個の暗号文Ｃｊの順序を逆順にしてから復号装置に送信すればよい。より具体的には、図６のＳ７２において最後に更新処理の行われた暗号文のインデクスがｋであるとすると、ＣｋをＣ１に、Ｃｋ−１をＣ２に、Ｃｋ−２をＣ３に、・・・、Ｃｋ＋１をＣｈにする操作を行ってから送信すればよい。
【００８７】
以上説明したように緩増加ベクトルｂが既知であれば、Ｓ９６からＳ１０６のステップを踏むことで暗号文のインデックスｊを更新することができ、ｈ個の従来型ＭＨ暗号の復号と同様な処理に帰着することができる。
【００８８】
Ｃｊを緩増加ベクトルｂの要素ｂｉのいずれかの要素の和で分解する問題は組み合わせ最適化問題と呼ばれる問題に属し、一般的には要素の数が多い場合には最適解を得ることは困難とされている。しかし、もしｂが超増加であれば、前提技術[３．４]のアルゴリズムにより、Ｃｊとｂｉとの比較と引き算とで簡単に解くことができる。本実施例ではｂは超増加ではないが、ｂをｈ個の分割ベクトルに分割し、それぞれについて従来型のＭＨ暗号の復号処理と同様の処理を行うことで問題を解くことが可能となる。このために、緩増加ベクトルはそこから得られる分割ベクトルが超増加となるように設計されている。分割ベクトルが超増加となれば、緩増加ベクトルの要素を分割数以上の任意の間隔でサンプリングして得られるベクトルもまた、超増加となる。
【００８９】
したがって、本実施例の緩増加ベクトルｂは、組み合わせ最適化問題の困難性により安全性を担保する暗号であれば、その秘密鍵として利用することができる。
【００９０】
一方、緩増加ベクトルｂを知ることのできない攻撃者、すなわち暗号文Ｃｊ、公開鍵ベクトルａ、分割数ｈを盗聴した攻撃者は、盗聴した暗号文Ｃｊについてｈ個の従来型ＭＨ暗号の復号と同様な処理に分割することはできない。インデックスｊの更新は平文ｍにおける１の出現パターンに依存しているからである（図６におけるＳ７０）。
【００９１】
平文ｍを知ることのできない攻撃者がＬＯ法を用いて攻撃を試みるためには、式（１４）におけるＣの代わりにＣｊの各要素を用いるか、Ｃｊの総和を用いるか、Ｃｊの任意の部分和を用いる等の方法を取ることになる。いずれにしても式（２０）で計算される密度ｄは式（３３）に帰着し、高密度となる。すなわち、ＬＯ法に耐性を有することになる。
【００９２】
以上述べたように、復号装置２００によれば、公開鍵ベクトルａを用いて生成された暗号文Ｃｊを、緩増加ベクトルｂ、分割数ｈ、逆元ｗ−１、法Ｍを用いて復号することができる。また、緩増加ベクトルｂを知らない攻撃者に対しては、ＬＯ法に耐性を有することができる。
【００９３】
以下、本発明の実施の形態に係る暗号化および復号の手順について数値例を用いて具体的に説明する。
【００９４】
表１は平文のビット数ｎが１３で、分割数ｈの値が３の場合の暗号化および復号の数値例である。緩増加ベクトルｂは（４，６，９，・・・，２７３，４０１）の１３個の要素ｂｉ（ｉ＝１，・・・，１３）を持つベクトルであり、式（９）を満足する。法Ｍは５８７であり、ｂ１３＋ｂ１０＋ｂ７＋ｂ４＋ｂ１＝５８６よりも大きく、式（１１）を満足する。乗数ｗ＝１０１、逆元ｗ−１＝９３である。Ｍとｗは互いに素であり、これらはｗｗ−１≡１（ｍｏｄ Ｍ）である。なお表中ｗ_ｉｎｖはｗ−１を意味するものとする。
【００９５】
【表１】
【００９６】
公開鍵ベクトルａは式（５）に基づいて生成したものである。例えばａ２の値はｂ２とｗとの積（６×１０１＝６０６）を法Ｍの値である５８７で割った余りであるから１９となる。分割数ｈの値は３であるから、暗号文はＣ１、Ｃ２、Ｃ３の３つとする。
【００９７】
まず暗号化の手順について説明する。暗号化プロセスでは図６におけるＳ６６からＳ７６にしたがい、ｉ＝１３からｉ＝１に至るまで、平文ｍの要素が１であるかどうかを調べる。表１ではｉ＝１２のとき初めてｍ１２＝１となるから、Ｃ１にａ１２＝５７１の値が加算される。ｉ＝１０のとき再びｍ１０＝１となるから、今度はＣ２にａ１０＝５００の値を加算する。同様にｉ＝９のときはＣ３にａ９の値を加算する。
【００９８】
ｉ＝８のとき、ｍの要素が４度目の１となる。この場合、ａ８の値を加算すべき暗号文はＣ１に戻る。このように、ｍの要素が１となる毎にａｉの値を加算する暗号文をＣ１、Ｃ２、Ｃ３、Ｃ１、Ｃ２、Ｃ３・・・と循環しながら変更する。こうしてＣ１＝ａ１２＋ａ８＋ａ３＝１０８３、Ｃ２＝ａ１０＋ａ６＋ａ１＝１３８４、Ｃ３＝ａ９＋ａ４＝２２２となる。
【００９９】
次に復号の手順について説明する。暗号文Ｃ１、Ｃ２、Ｃ３をそれぞれＭとｗ−１とによりモジュラ乗算変換し、Ｃ’１、Ｃ’２、Ｃ’３を得る。例えば、ｗ−１×Ｃ１＝１００７１９となるが、これをＭ＝５８７で割った余りは３４２となるのでＣ’１の値は３４２となる。
【０１００】
以後は図７におけるＳ９４からＳ１０６にしたがい、ｉ＝１３からｉ＝１に至るまで順にｂｉの要素がＣ’ｊ以下であるかどうかを調べる。表２ではｉ＝１２で初めてＣ’１≧ｂ１２となる。そこでＣ’１の値をＣ’１−ｂ１２＝３４２−２７３＝６９に更新する。ｉ＝１０のときＣ’２≧ｂ１０となるから、今度はＣ’２の値をＣ’２−ｂ１０＝３２に更新する。同様にｉ＝９のとき、Ｃ’３の値をＣ’３−ｂ９＝１３とする。
【０１０１】
ｉ＝８のとき、ｂ８と大小を比較する値は、ｉ＝１２において更新されたＣ’１の値である。表１の場合、ｉ＝１２において更新されたＣ’１の値は６９であり、ｂ８の値は６０であるからＣ’１≧ｂ８となる。そこでＣ’１の値をあらためてＣ’１−ｂ８＝６９−６０＝９に更新する。以後、ｂｉの値と最新のＣ’ｊとの値の大小関係を比較してＣ’ｊ≧ｂｉとなる毎にＣ’ｊの値を更新する。最終的にＣ’１＝Ｃ’２＝Ｃ’３＝０となれば復号終了である。Ｃ’ｊ≧ｂｉとなるｉについてｍｉ＝１、それ以外をｍｉ＝０とすることで平文が得られる。
【０１０２】
表２は本発明実施の形態に係る分割数ｈと密度ｄとの関係を実験により求めた結果と理論的上界を示したものである。平文のビット数ｎを１５０とし、分割数ｈの値を１から５の間で変更したときの密度ｄを計算したものである。表の値は、秘密鍵として１００種類の鍵を用意し、それぞれの場合の密度ｄの平均値を記載したものである。表２から、分割数ｈを大きくするにしたがって密度ｄも大きくなっていることが分かる。
【０１０３】
【表２】
【０１０４】
なお、分割数の値をいくつにするかは実験により定めればよいが、一例としては平文のビット数ｎが１００または２００程度であれば分割数ｈの値は５程度とすればよい。
【０１０５】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下そのような変形例を説明する。
【０１０６】
上記の説明では、暗号文の数を分割数と同数として説明したが、一般にはＨ≧ｈとなるＨを用いてＨ個の暗号文を作成してもよい。この場合、復号プロセスにおいてＣｊのインデックスを１ずつ順に増やしてＨに至ったら次は再び１に戻し、以後１〜Ｈの値を繰り返せばよい。
【０１０７】
上記の説明では、秘密鍵として緩増加ベクトルを用いたが、緩増加ベクトルの並びを反転して降順に並べたベクトルを用いることもできる。この場合には暗号化および復号のプロセスにおけるループを逆に回せばよい。
【０１０８】
上記の説明では、実施の形態の暗号システム１００の利用例として暗号鍵生成を説明したが、これ以外に、本実施の形態における暗号鍵はデジタル署名の生成と検証に用いてもよい。
【符号の説明】
【０１０９】
１０ 緩増加秘密鍵生成部、 １２ 公開鍵生成部、 １４ 公開鍵送信部、 １６ 公開鍵受信部、 １８ 公開鍵記憶部、 ２０ 暗号文生成部、 ２２ 平文入力部、 ２４ 暗号文送信部、 ２６ 暗号文受信部、 ２８ 復号部、 ３０ 緩増加秘密鍵記憶部、 ３２ 平文出力部、 ３４ 平文ビット数および分割数の入力部、 ３６ 緩増加ベクトル生成部、 ３８ 法Ｍ生成部、 ４０ 乗数生成部、 ４２ 公開鍵ベクトル生成部、 ４４ 公開鍵出力部、 ４６ 逆元生成部、 ４８ 秘密鍵出力部、 １００ 暗号システム、 ２００ 復号装置、 ３００ 暗号化装置、 ４００ 暗号鍵生成装置。
【特許請求の範囲】
【請求項１】
秘密鍵生成部と公開鍵生成部とを含み、
前記秘密鍵生成部は、
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを緩増加ベクトルとして生成する緩増加ベクトル生成部と、
各分割ベクトルの要素の総和の最大値よりも大きな整数を法Ｍとして生成する法Ｍ生成部と、
法Ｍと互いに素である乗数を生成する乗数生成部とを含み、
前記公開鍵生成部は、
緩増加ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部と、
分割数と公開鍵ベクトルとを公開鍵として出力する公開鍵出力部とを含むことを特徴とする暗号鍵生成装置。
【請求項２】
前記緩増加ベクトル生成部は、平文のビット数をｎ、分割数をｈとし、緩増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）として、
【数１】
を満たすベクトルを緩増加ベクトルとして生成するものであり、
【数２】
は（ｉ−１）／ｈを超えない最大の整数であることを特徴とする請求項１に記載の暗号鍵生成装置。
【請求項３】
前記法Ｍ生成部は、緩増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）とし、平文のビット数をｎ、分割数をｈとして、
【数３】
を満たす整数Ｍを法Ｍとして生成するものであり、
【数４】
は（ｎ−１）／ｈを超えない最大の整数であることを特徴とする請求項１または２に記載の暗号鍵生成装置。
【請求項４】
公開鍵として分割数と公開鍵ベクトルとを含む公開鍵の入力を受け付ける公開鍵受信部と、
平文の入力を受け付ける平文入力部と、
公開鍵ベクトルと平文とから少なくとも分割数個の暗号文を生成する暗号文生成部とを含み、
前記公開鍵ベクトルは、緩増加ベクトルの要素をモジュラ乗算変換することで生成されたものであり、
前記緩増加ベクトルは、前記平文のビット数と同数の要素を持つベクトルであり、当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となることを特徴とする暗号化装置。
【請求項５】
前記暗号文生成部は、公開鍵ベクトルの要素の加算先を少なくとも分割数個用意し、平文のパターンに基づいて加算先を変更することにより少なくとも分割数個の暗号文を生成することを特徴とする請求項４に記載の暗号化装置。
【請求項６】
前記暗号文生成部は、公開鍵ベクトルの要素に対応する緩増加ベクトルの要素の値が大きい方から順に、公開鍵ベクトルの要素を加算することを特徴とする請求項４または５に記載の暗号化装置。
【請求項７】
暗号文として複数個の暗号文を含む暗号文の入力を受け付ける暗号文受信部と、
秘密鍵として緩増加ベクトルを含む秘密鍵に基づいて前記暗号文を復号する復号部とを含み、
前記緩増加ベクトルは、当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルであり、
前記暗号文は、前記緩増加ベクトルの要素をモジュラ乗算変換することで生成された公開鍵ベクトルに基づいて暗号化されたものであることを特徴とする復号装置。
【請求項８】
前記復号部は、前記複数個の暗号文のひとつと緩増加ベクトルの要素との大小比較を行い、前記複数個の暗号文のひとつが緩増加ベクトルの要素以上となるたびに比較対象とする暗号文を変更することを含むことを特徴とする請求項７に記載の復号装置。
【請求項９】
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成するステップと、
任意の分割ベクトルにおける要素の総和よりも大きな整数を法Ｍとして生成するステップと、
法Ｍと互いに素である乗数を生成するステップと、
緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成するステップと、
分割数と公開鍵ベクトルとを公開鍵として出力するステップとをプロセッサに実行させることを特徴とする暗号鍵生成方法。
【請求項１０】
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成する機能と、
各分割ベクトルにおける要素の総和の最大値よりも大きな整数を法Ｍとして生成する機能と、
法Ｍと互いに素である乗数を生成する機能と、
緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成する機能と、
分割数と公開鍵ベクトルとを公開鍵として出力する機能とをコンピュータに実現させることを特徴とするプログラム。
【請求項１１】
組み合わせ最適化問題の困難性により安全性を担保する暗号の鍵を生成する暗号鍵生成装置であって、
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを暗号鍵として生成することを特徴とする暗号鍵生成装置。
【請求項１】
秘密鍵生成部と公開鍵生成部とを含み、
前記秘密鍵生成部は、
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを緩増加ベクトルとして生成する緩増加ベクトル生成部と、
各分割ベクトルの要素の総和の最大値よりも大きな整数を法Ｍとして生成する法Ｍ生成部と、
法Ｍと互いに素である乗数を生成する乗数生成部とを含み、
前記公開鍵生成部は、
緩増加ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部と、
分割数と公開鍵ベクトルとを公開鍵として出力する公開鍵出力部とを含むことを特徴とする暗号鍵生成装置。
【請求項２】
前記緩増加ベクトル生成部は、平文のビット数をｎ、分割数をｈとし、緩増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）として、
【数１】
を満たすベクトルを緩増加ベクトルとして生成するものであり、
【数２】
は（ｉ−１）／ｈを超えない最大の整数であることを特徴とする請求項１に記載の暗号鍵生成装置。
【請求項３】
前記法Ｍ生成部は、緩増加ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）とし、平文のビット数をｎ、分割数をｈとして、
【数３】
を満たす整数Ｍを法Ｍとして生成するものであり、
【数４】
は（ｎ−１）／ｈを超えない最大の整数であることを特徴とする請求項１または２に記載の暗号鍵生成装置。
【請求項４】
公開鍵として分割数と公開鍵ベクトルとを含む公開鍵の入力を受け付ける公開鍵受信部と、
平文の入力を受け付ける平文入力部と、
公開鍵ベクトルと平文とから少なくとも分割数個の暗号文を生成する暗号文生成部とを含み、
前記公開鍵ベクトルは、緩増加ベクトルの要素をモジュラ乗算変換することで生成されたものであり、
前記緩増加ベクトルは、前記平文のビット数と同数の要素を持つベクトルであり、当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となることを特徴とする暗号化装置。
【請求項５】
前記暗号文生成部は、公開鍵ベクトルの要素の加算先を少なくとも分割数個用意し、平文のパターンに基づいて加算先を変更することにより少なくとも分割数個の暗号文を生成することを特徴とする請求項４に記載の暗号化装置。
【請求項６】
前記暗号文生成部は、公開鍵ベクトルの要素に対応する緩増加ベクトルの要素の値が大きい方から順に、公開鍵ベクトルの要素を加算することを特徴とする請求項４または５に記載の暗号化装置。
【請求項７】
暗号文として複数個の暗号文を含む暗号文の入力を受け付ける暗号文受信部と、
秘密鍵として緩増加ベクトルを含む秘密鍵に基づいて前記暗号文を復号する復号部とを含み、
前記緩増加ベクトルは、当該ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルであり、
前記暗号文は、前記緩増加ベクトルの要素をモジュラ乗算変換することで生成された公開鍵ベクトルに基づいて暗号化されたものであることを特徴とする復号装置。
【請求項８】
前記復号部は、前記複数個の暗号文のひとつと緩増加ベクトルの要素との大小比較を行い、前記複数個の暗号文のひとつが緩増加ベクトルの要素以上となるたびに比較対象とする暗号文を変更することを含むことを特徴とする請求項７に記載の復号装置。
【請求項９】
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成するステップと、
任意の分割ベクトルにおける要素の総和よりも大きな整数を法Ｍとして生成するステップと、
法Ｍと互いに素である乗数を生成するステップと、
緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成するステップと、
分割数と公開鍵ベクトルとを公開鍵として出力するステップとをプロセッサに実行させることを特徴とする暗号鍵生成方法。
【請求項１０】
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となる緩増加ベクトルを生成する機能と、
各分割ベクトルにおける要素の総和の最大値よりも大きな整数を法Ｍとして生成する機能と、
法Ｍと互いに素である乗数を生成する機能と、
緩増加ベクトルの要素と乗数との積について法Ｍを法とするモジュラ乗算変換することにより公開鍵ベクトルを生成する機能と、
分割数と公開鍵ベクトルとを公開鍵として出力する機能とをコンピュータに実現させることを特徴とするプログラム。
【請求項１１】
組み合わせ最適化問題の困難性により安全性を担保する暗号の鍵を生成する暗号鍵生成装置であって、
ベクトルの要素を分割数ごとに間引きすることにより得られる分割数個の分割ベクトルが超増加となるベクトルを暗号鍵として生成することを特徴とする暗号鍵生成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−２５６５４９（Ｐ２０１０−２５６５４９Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１０５２５４（Ｐ２００９−１０５２５４）
【出願日】平成２１年４月２３日（２００９．４．２３）
【出願人】（５９３１６５４８７）学校法人金沢工業大学 (202)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２３日（２００９．４．２３）
【出願人】（５９３１６５４８７）学校法人金沢工業大学 (202)
【Ｆターム（参考）】
[ Back to top ]