(57)【要約】【課題】ナップザック暗号は暗号化および復号が短時間であり量子計算機によってさらに安全性が危うくなることはない利点があるが、解読法が存在する。【解決手段】  秘密鍵生成部１０は、要素が単調増加に並び、任意の要素の値がその値よりも小さな要素それぞれに所定の自然数を乗じて和を取った値よりも大きな値となるベクトルを生成する低密度秘密鍵ベクトル生成部３８と、ベクトルの全ての要素に所定の自然数を乗じて和を取った値よりも大きな自然数を生成する法Ｍ生成部４０と、法Ｍと互いに素である自然数を生成する乗数生成部４２とを含む。公開鍵生成部１２は、低密度秘密鍵ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換して公開鍵ベクトルを生成する公開鍵ベクトル生成部４４と、低密度秘密鍵ベクトルの要素と同数の自然数を要素とするベクトルを生成する暗号化乗数生成部４６とを含む。【選択図】図３
2011033809.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵生成部と公開鍵生成部とを含み、
前記秘密鍵生成部は、
平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数１】
2011033809.tif 000051
を満たす自然数からなるベクトルを低密度秘密鍵ベクトルとして生成する低密度秘密鍵ベクトル生成部と、
Ｍを自然数として、
【数２】
2011033809.tif 000052
を満たす自然数Ｍを法Ｍとして生成する法Ｍ生成部と、
法Ｍと互いに素である自然数を乗数として生成する乗数生成部とを含み、
前記公開鍵生成部は、
低密度秘密鍵ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部と、
ｎ個の自然数を要素とするベクトルを暗号化乗数ｅ＝（ｅ１，ｅ２，・・・，ｅｎ）として、
【数３】
2011033809.tif 000053
を満たす自然数からなるベクトルを暗号化乗数として生成する暗号化乗数生成部とを含むことを特徴とする鍵生成装置。
【請求項２】
公開鍵として暗号化乗数と公開鍵ベクトルとを含む公開鍵の入力を受け付ける公開鍵受信部と、
平文の入力を受け付ける平文入力部と、
暗号化乗数、公開鍵ベクトルおよび平文とから暗号文を生成する暗号文生成部とを含み、
前記公開鍵ベクトルは、低密度秘密鍵ベクトルの要素をモジュラ乗算変換することで生成されたものであり、
前記低密度秘密鍵ベクトルは、平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数４】
2011033809.tif 000054
を満たすベクトルであることを特徴とする暗号化装置。
【請求項３】
前記暗号文生成部は、暗号化乗数の要素と公開鍵ベクトルの要素との積の和を暗号文として生成するものであり、平文のパターンに基づいて公開鍵ベクトルの要素に乗ずる暗号化乗数の要素を変更することを特徴とする請求項２に記載の暗号化装置。
【請求項４】
前記暗号文生成部は、公開鍵ベクトルの要素に対応する低密度秘密鍵ベクトルの要素の値が大きい方から順に、公開鍵ベクトルの要素と暗号化乗数の要素との積を加算することを特徴とする請求項２または３に記載の暗号化装置。
【請求項５】
暗号文の入力を受け付ける暗号文受信部と、
低密度秘密鍵ベクトルおよび暗号化乗数を含む復号パラメータに基づいて前記暗号文を復号する復号部とを含み、
前記低密度秘密鍵ベクトルは、平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数５】
2011033809.tif 000055
を満たすベクトルであり、
前記暗号文は、前記低密度秘密鍵ベクトルの要素をモジュラ乗算変換することで生成された公開鍵ベクトルおよび暗号化乗数に基づいて暗号化されたものであることを特徴とする復号装置。
【請求項６】
前記復号部は、低密度秘密鍵ベクトルの要素と暗号化乗数の要素との積の値と暗号文との大小比較を行い、暗号文が前記積の値以上となるたびに低密度秘密鍵ベクトルの要素に乗ずる暗号化乗数の要素を変更することを含むことを特徴とする請求項５に記載の復号装置。
【請求項７】
平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数６】
2011033809.tif 000056
を満たす自然数からなるベクトルを低密度秘密鍵ベクトルとして生成するステップと、
Ｍを自然数として、
【数７】
2011033809.tif 000057
を満たす自然数Ｍを法Ｍとして生成するステップと、
法Ｍと互いに素である自然数を乗数として生成するステップと、
低密度秘密鍵ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成するステップと、
ｎ個の自然数を要素とするベクトルを暗号化乗数ｅ＝（ｅ１，ｅ２，・・・，ｅｎ）として、
【数８】
2011033809.tif 000058
を満たす自然数からなるベクトルを暗号化乗数として生成するステップとをプロセッサに実行させることを特徴とする鍵生成方法。
【請求項８】
平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数９】
2011033809.tif 000059
を満たす自然数からなるベクトルを低密度秘密鍵ベクトルとして生成する機能と、
Ｍを自然数として、
【数１０】
2011033809.tif 000060
を満たす自然数Ｍを法Ｍとして生成する機能と、
法Ｍと互いに素である自然数を乗数として生成する機能と、
低密度秘密鍵ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する機能と、
ｎ個の自然数を要素とするベクトルを暗号化乗数ｅ＝（ｅ１，ｅ２，・・・，ｅｎ）として、
【数１１】
2011033809.tif 000061
を満たす自然数からなるベクトルを暗号化乗数として生成する機能とをコンピュータに実現させることを特徴とするプログラム。
【請求項９】
組み合わせ最適化問題の困難性により安全性を担保する暗号の鍵を生成する暗号鍵生成装置であって、
平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数１２】
2011033809.tif 000062
を満たす自然数からなるベクトルを暗号鍵として生成することを特徴とする鍵生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は暗号技術に関し、特に鍵生成装置、およびその装置を利用可能な暗号化装置ならびに復号装置に関する。
【背景技術】
【０００２】
公開鍵暗号として代表的なものにＲＳＡ暗号［１］がある。このＲＳＡ暗号の安全性は巨大数の因数分解が困難であることに依拠しているが、巨大数の因数分解は量子計算機の出現により実効的時間で可能となり、ＲＳＡ暗号の安全性は危うくなると言われている。また、ＲＳＡ暗号は暗号化や復号の計算に時間がかかるという欠点がある。
【０００３】
公開鍵暗号の一方式として、ナップザック暗号がある。ナップザック暗号は１９７８年頃にＭｅｒｋｌｅとＨｅｌｌｍａｎ［２］が提案した最初期の公開鍵暗号［３］のひとつである（非特許文献１参照）。ナップザック暗号（以下「ＭＨ暗号」という。）の安全性は組み合わせ問題に依拠しており、量子計算機によってさらに安全性が危うくなるということはないが、解読法（非特許文献２、３参照）が存在するため、現在は実用されていない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＭＨ暗号は暗号化が整数の足し算、復号が整数の比較と引き算からなるため、ＲＳＡ暗号に比して暗号化および復号の計算が高速であるという利点がある。また、量子計算機によってさらに安全性が危うくなるということはないという利点もある。しかしながら、ＭＨ暗号には低密度攻撃等の解読法が存在するという欠点がある。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、暗号解読に対して耐性の高い暗号鍵を生成する鍵生成装置およびその装置を利用可能な暗号化装置ならびに復号装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のある態様は鍵生成装置に関する。この装置は秘密鍵生成部と公開鍵生成部とを含む。秘密鍵生成部は、平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数１】
2011033809.tif 000003
を満たす自然数からなるベクトルを低密度秘密鍵ベクトルとして生成する低密度秘密鍵ベクトル生成部と、Ｍを自然数として、
【数２】
2011033809.tif 000004
を満たす自然数Ｍを法Ｍとして生成する法Ｍ生成部と、法Ｍと互いに素である自然数を乗数として生成する乗数生成部とを含み、公開鍵生成部は、低密度秘密鍵ベクトルの要素と乗数との積について法Ｍを法としてモジュラ乗算変換することにより公開鍵ベクトルを生成する公開鍵ベクトル生成部と、ｎ個の自然数を要素とするベクトルを暗号化乗数ｅ＝（ｅ１，ｅ２，・・・，ｅｎ）として、
【数３】
2011033809.tif 000005
を満たす自然数からなるベクトルを暗号化乗数として生成する暗号化乗数生成部とを含む。
【０００８】
本発明の別の態様は暗号化装置に関する。この装置は、公開鍵として暗号化乗数と公開鍵ベクトルとを含む公開鍵の入力を受け付ける公開鍵受信部と、平文の入力を受け付ける平文入力部と、暗号化乗数、公開鍵ベクトルおよび平文とから暗号文を生成する暗号文生成部とを含み、公開鍵ベクトルは、低密度秘密鍵ベクトルの要素をモジュラ乗算変換することで生成されたものであり、低密度秘密鍵ベクトルは、平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数４】
2011033809.tif 000006
を満たすベクトルである。
【０００９】
本発明のさらに別の態様は復号装置に関する。この装置は、暗号文の入力を受け付ける暗号文受信部と、低密度秘密鍵ベクトルおよび暗号化乗数を含む復号パラメータに基づいて前記暗号文を復号する復号部とを含み、低密度秘密鍵ベクトルは、平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数５】
2011033809.tif 000007
を満たすベクトルであり、暗号文は、前記低密度秘密鍵ベクトルの要素をモジュラ乗算変換することで生成された公開鍵ベクトルおよび暗号化乗数に基づいて暗号化されたものである。
【００１０】
本発明の更に別の態様は秘密鍵生成装置に関する。この装置は、組み合わせ最適化問題の困難性により安全性を担保する暗号の鍵を生成する暗号鍵生成装置であって、平文のビット数をｎ、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）、任意に設定するｎ個の自然数を要素とするベクトルを秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）として、
【数６】
2011033809.tif 000008
を満たす自然数からなるベクトルを暗号鍵として生成する。
【００１１】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、暗号解読に対して耐性の高い暗号のための暗号鍵を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態に係る暗号システムの全体構成図である。
【図２】図１の暗号システムによる鍵生成から暗号文の復号およびその結果の出力に至るまでの手順を説明するフローチャートである。
【図３】図１の鍵生成装置の構成図である。
【図４】図３の低密度秘密鍵生成部における秘密鍵の生成手順を説明するフローチャートである。
【図５】低密度秘密鍵ベクトルを生成するための具体例を説明するフローチャートである。
【図６】暗号化乗数の生成手順を説明するフローチャートである。
【図７】暗号文生成の手順を説明するフローチャートである。
【図８】図８（ａ）は復号の手順を説明するフローチャートの前半部である。図８（ｂ）は復号の手順を説明するフローチャートの後半部である。
【発明を実施するための形態】
【００１４】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１５】
［前提技術］
［１］  本明細書で用いる記号の定義
平文のビット数：              ｎ
秘密鍵ベクトル：              ｂ
秘密鍵ベクトルの要素：        ｂｉ  （ｉ＝１，・・・，ｎ）∈Ｎ
法：                          Ｍ
乗数：                        ｗ
乗数のＭを法とする逆元：      ｗ−１
公開鍵ベクトル：              ａ
公開鍵ベクトルの要素：        ａｉ  （ｉ＝１，・・・，ｎ）∈Ｎ
平文：                        ｍ
平文の要素：                  ｍｉ  （ｉ＝１，・・・，ｎ）∈｛０，１｝
秘密鍵乗数：                  ｓｉ  （ｉ＝１，・・・，ｎ）∈Ｎ
暗号化乗数：                  ｅｉ  （ｉ＝１，・・・，ｎ）∈Ｎ
暗号文：                      Ｃ
基底行列：                    ＡＬＯ
Ｃｏｓｔｅｒらの基底行列：    ＡＣ
Ｆｉｅｚｅの基底行列：        ＡＦ
格子：                        Ｌ
ａの密度：                    ｄ
【００１６】
［２］  従来型ＭＨ暗号
ＭＨ暗号はＭｅｒｋｌｅ−Ｈｅｌｌｍａｎ［１］が考案した最初期の公開鍵暗号［２］のひとつである。この暗号の特徴は次の通りである。
１．高速である。暗号化が整数の足し算、復号が比較と引き算だけからなるからである。
２．既に解読法が存在し安全ではなく、現在実用されていない。
３．しかし細々と研究が続けられている。高速性の利点があるからである。
４．特に近年別の観点からも再び注目されている。量子計算機が出現するとＲＳＡ暗号［３］が危うくなるからである。ＭＨ暗号は組み合わせ問題を利用しており、量子計算によってさらに危うくなることはない。
［２．１］  秘密鍵
自然数を要素とするベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）∈Ｎｎが次のような性質を有するとき、ｂは超増加（super increasing）であるという。
【数７】
2011033809.tif 000009
法Ｍを次の式を満たすランダムな整数とする：
【数８】
2011033809.tif 000010
Ｍをあまり大きくすると解読されやすくなるので、たとえば
【数９】
2011033809.tif 000011
とする。
次を満たす乗数ｗをランダムに選び、更にＭを法とするｗの逆元ｗ−１を求める：
ｇｃｄ（ｗ，Ｍ）＝１、  １＜ｗ＜Ｍ    （３）
ｗｗ−１≡１  （ｍｏｄ Ｍ）    （４）
ここで、ｇｃｄ（ｗ，Ｍ）はｗとＭとの最大公約数を表す。
【００１７】
［２．２］  公開鍵
秘密鍵ベクトルｂをｗとＭとを用いてモジュラ乗算変換し、公開鍵ベクトルａ＝（ａ１，ａ２，・・・，ａｎ）∈Ｎｎを作る：
ａｉ＝ｗｂｉｍｏｄ Ｍ，（ｉ＝１，２，・・・，ｎ）    （５）
ここで、ｘｍｏｄ ＭはｘをＭで割った剰余ｒ、０≦ｒ＜Ｍを表す。
【００１８】
［２．３］  暗号化
平文ｍはｎビットであるとする：
ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）∈｛０，１｝ｎ    （６）
この平文に対する暗号文Ｃは次の式で与えられる。
【数１０】
2011033809.tif 000012
【００１９】
［２．４］  復号
まず暗号文Ｃをｗの逆元ｗ−１と法Ｍとを用いるモジュラ乗算変換によりＣ’に変換する。この逆変換によって、Ｃとａとからｍを求めるという難しいナップザック問題は、Ｃ’とｂとからｍを求めるという易しいナップザック問題になる。こうして復号は次のようにして行われる。
Ｃ←ｗ−１Ｃｍｏｄ Ｍ，ｍ←０ｎ
ｆｏｒ  ｉ＝ｎ ｄｏｗｎｔｏ １
｛
ｉｆ  Ｃ≧ｂｉ ｔｈｅｎ
｛ｍｉ←１，Ｃ←Ｃ−ｂｉ｝
｝
【００２０】
［３］  本実施の形態に係る方式
実施の形態は、ＭＨ暗号の安全性を高めることに関するものである。実施の形態の基礎技術は、秘密鍵生成方法と、それに伴う暗号化および復号の仕組みにある。秘密鍵は通常のＭＨ暗号よりもさらに増加が急であり、後述する密度は低くなるが、暗号化の方法とあいまって、ＭＨ暗号の解読の強力な手法であるラガリアス−オドリズコ法［４］に耐性を有することが期待できる。なお、Ｓｈａｍｉｒ攻撃［５］に対しては、後述する理由により現時点では耐性を有すると考えられる。
【００２１】
［３．１］  秘密鍵
自然数ｎを定める。ｎはＭＨ暗号と同じく平文のビット数である。自然数を要素とするベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）∈Ｎｎおよび法Ｍを、ｂ１を適当な大きさのランダムな整数として、次の不等式を満たすように定める：
【数１１】
2011033809.tif 000013
【数１２】
2011033809.tif 000014
ここでｓ＝（ｓ１，・・・，ｓｎ）∈Ｎｎは任意に設定するｎ個の自然数の列であり、秘密鍵乗数と呼ぶことにする。またＭと互いに素な整数ｗ、１＜ｗ＜ＭおよびＭを法とするｗの逆元ｗ−１、１＜ｗ−１＜Ｍ、ｗ−１ｗ≡１（ｍｏｄ Ｍ）を定める。以上のように定めたｂ、ｓ、Ｍ、ｗ、ｗ−１を秘密鍵とする。
【００２２】
式（８）においてｎ＝５までを以下に例示する。
ｂ２＞ｓ１ｂ１
ｂ３＞ｓ１ｂ２＋ｓ２ｂ１
ｂ４＞ｓ１ｂ３＋ｓ２ｂ２＋ｓ３ｂ１
ｂ５＞ｓ１ｂ４＋ｓ２ｂ３＋ｓ３ｂ２＋ｓ４ｂ１
【００２３】
［３．２］  公開鍵
秘密鍵ｂをＭとｗによってモジュラ乗算変換し、これをａ＝（ａ１，・・・，ａｎ）とする。
ａｉ＝ｗｂｉｍｏｄ Ｍ  （ｉ＝１，２，・・・，ｎ）    （１０）
さらに暗号化乗数と呼ぶ自然数の列ｅ＝（ｅ１，・・・，ｅｎ）∈Ｎｎを定める。ただし、ｅは次の式を満たす：
【数１３】
2011033809.tif 000015
以上のように定めたａとｅとを公開鍵とする。
【００２４】
［３．３］  暗号化
平文ｍ＝（ｍ１，ｍ２，・・・，ｍｎ）∈｛０，１｝ｎを次のように暗号化する。
Ｃ＝０
ｊ＝１
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １
｛
ｉｆ ｍｉ＝１｛Ｃ＝Ｃ＋ｅｊａｉ，ｊ＝ｊ＋１｝
｝
通常のＭＨ暗号における暗号化との違いは、ｍｉ＝１のときａｉをＣに単に加算するのではなく、ｍｎから始めて、平文ビットが１になるたびに、ｅｊ倍したａｉを加え、かつｊを１ずつ増すことである。ここでｊは平文に依存するので、ａｉが何倍されてＣに加算されるかは固定されないことに注意する。
【００２５】
［３．４］  復号
先ずＭとｗ−１とにより暗号文Ｃをモジュラ乗算変換する。これは従来型のＭＨ暗号の復号と同じく公開鍵ａの要素の和を秘密鍵ｂの要素の和に変換するためである。
Ｃ＝ｗ−１Ｃｍｏｄ Ｍ
ｍ１＝ｍ２＝・・・＝ｍｎ＝０
ｊ＝１
ｆｏｒ ｉ＝ｎ ｄｏｗｎｔｏ １｛
ｉｆ Ｃ≧ｅｊｂｉ｛ｍｉ＝１，Ｃ＝Ｃ−ｅｊｂｉ，ｊ＝ｊ＋１｝
｝
これはつまり、ｍｉ＝１となるのは、Ｃがｅｊｂｉ以上のときである。
【００２６】
［３．５］  数値例
ｎ＝５の場合の小さな例を表１に示す。具体的には、ｓ＝（１，１，２，３，４）、ｅ＝（１，１，２，３，４）の場合である。
【表１】
2011033809.tif 000016
この例について、鍵設定、暗号化、復号を説明する。
【００２７】
１．３＞２、ｂ２＞ｂ１、８＞３＋２＝５、ｂ３＞ｂ２＋ｂ１、２１＞８＋３＋２×２＝１５、ｂ４＞ｂ３＋ｂ２＋２ｂ１、５５＞２１＋８＋２×３＋３×２＝４１、ｂ５＞ｂ４＋ｂ３＋２ｂ２＋３ｂ１であり、式（８）を満たす。
２．ｂ５＋ｂ４＋２ｂ３＋３ｂ２＋４ｂ１＝１０９である。ここでＭ＝１１０＞１０９とし、ｗ＝７１とすればｗ−１＝３１となる。
３．ａｉたちは式（１０）によって得られる。
４．平文をｍ＝（０，１，０，１，１）とする。暗号化はｉ＝５から始め、Ｃ＝ａ５＋ａ４＋２ａ２＝５５＋６１＋２×１０３＝３２２となる。
５．まずＣ’＝ｗ−１ＣｍｏｄＭ＝３１×３２２ｍｏｄ１１０＝８２を求める。
６．８２−５５＝２７なのでｍ５＝１。２７−２１＝６なのでｍ４＝１。６−２×８＝−１０＜０なのでｍ３＝０。６−２×３＝０なのでｍ２＝１。Ｃ’＝０なのでｍ５＝０として比較を終え、ｍ’＝（０，１，０，１，１）＝ｍと正しく復号される。
【００２８】
［３．６］  復号の正しさ
（１）秘密鍵領域への変換
Ｃ’＝ｗ−１ＣｍｏｄＭとおけば、
【数１４】
2011033809.tif 000017
ここで式（１２）の右辺がＭより小さく、したがって合同式が等式になることを示す。
【００２９】
式（１２）の右辺の総和において、ｍｉ＝１の項がｔ個あるとし、ｍｉ＝０の項を除きｍｉ＝１の項だけで次のように書ける：
【数１５】
2011033809.tif 000018
式（１３）における添字ｉｋはｋの減少列である。ゆえに、
【数１６】
2011033809.tif 000019
である。よって式（１３）における添字ｉ１，ｉ２，・・・，ｉｔをｎ，ｎ−１，・・・，ｎ＋１−ｔに置き換えれば、
【数１７】
2011033809.tif 000020
となる。
【００３０】
もし1≦ｉ≦ｋなるすべてのｉについてｅｉ≦ｓｉなら、上の式でｅｋをｓｋで置き換えても不等式はそのまま成立する。もしあるｋにつきｅｋ＞ｓｋなら、ｅ’ｋ＝ｓｋとし、ｅｋ−ｓｋの値をｅ’１≦ｓ１，・・・,ｅ’ｋ−１≦ｓｋ−１を満たしつつ、添字がｋよりも小さなｅの要素ｅ１，・・・，ｅｋ−１に適当に分散しｅ’１・・・,ｅ’ｋに変更する。この変更によりすべてのｋについてｅ’ｋ≦ｓｋとなる。したがって式（９）によって、式（１４）の総和はＭより小さくなり、合同式（１２）は等式（１５）になることを示すことができた。ただしＣ’を改めてＣと書く。
【数１８】
2011033809.tif 000021
【００３１】
（２）平文ビットｍｉの順次決定
（２ａ）ｍｎの決定
ｍｎ＝１のとき、
【数１９】
2011033809.tif 000022
であるから、Ｃ≧ｅ１ｂｎは明らか。ｍｎ＝０なら、式（１２）の右辺がＭより小さいことを導いたときと同じ議論により
【数２０】
2011033809.tif 000023
となる。ｍｎ∈｛０，１｝であるから、Ｃ≧ｅ１ｂｎならｍｎ＝１、Ｃ＜ｅ１ｂｎならｍｎ＝０である。
【００３２】
（２ｂ）ｍｉ，ｉ＜ｎの決定
ｍｎ，ｍｎ−１，・・・，ｍｋ＋１が復号できたとする。ここでＣを改めて
【数２１】
2011033809.tif 000024
とおく。ここで、
【数２２】
2011033809.tif 000025
なら、ｍｋ＝１、
【数２３】
2011033809.tif 000026
ならｍｋ＝０となることを示す。
【００３３】
ｍｋ＝１なら、
【数２４】
2011033809.tif 000027
は明らか。ｍｋ＝０なら、
【数２５】
2011033809.tif 000028
となるが、前と同じ議論により、
【数２６】
2011033809.tif 000029
が成り立つ。よって、
【数２７】
2011033809.tif 000030
となる。以上で復号の正しさが示された。
【００３４】
［３．７］  鍵の密度について
ｂの増加の仕方を調べるために式（８）の不等式を全て等式に置き換えて考える。ただしここではｓ＝（１，１，・・・，ｎ−１）とする。ｂの要素を公比ｒの等比数列と見なすとき、ｒは次の方程式の解である。この式の導出については後述する。
ｒ２−３ｒ＋１＝０    （１６）
この方程式の１より大きい方の解は
【数２８】
2011033809.tif 000031
であり、後述するＬａｇａｒｉａｓ−Ｏｄｌｙｚｋｏ法に対する耐性を測る尺度となる密度ｄはこのｒを用いて
【数２９】
2011033809.tif 000032
となる。この評価は、ｂの増加を小さく見積もった場合であるから、実際にはｂの増加はさらに大きく、ｄは小さくなる。
【００３５】
［４］  Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏ（ラガリアス−オドリズコ）の攻撃法
Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏの攻撃法［４］（以下「ＬＯ法」という。）は、ＭＨ暗号に対する強力な攻撃法で、低密度攻撃とも呼ばれる。ＬＯ法によれば、式（５）で定義されるナップザックベクトルａの密度ｄがｄ＜０．６４６３のＭＨ暗号は多項式時間で解読されることが証明されている［４］。ただし整数格子の中の最短ベクトルを多項式時間で見出すアルゴリズムが存在することが仮定されている。実際にはこのようなアルゴリズムは存在しないが、実用的な近似アルゴリズムとしてＬＬＬ［８］アルゴリズムが存在する。
【００３６】
ここでナップザックベクトルの密度は、
【数３０】
2011033809.tif 000033
で定義される。なおｄは情報伝送効率を表すとみなせる。というのは、暗号文のビット数はほぼａｉのビット数（よりｎのビット数だけ多い）程度であるからである。臨界密度はその後０．６４６３から０．９４０８［７］にまで改良さている。その結果、密度が１以下である従来型ＭＨ暗号はほとんど解読されることになった。
【００３７】
［４．１］  従来型ＭＨ暗号のＬＯ法による攻撃
公開鍵ベクトルａと盗聴した暗号文Ｃとを用いて次のような基底行列を定義する。
【数３１】
2011033809.tif 000034
行列ＡＬＯの各行ベクトルの整数係数線形結合の全体Ｌを、ＡＬＯが生成する格子といい、Ｌ＝Ｌ（ＡＬＯ）と表す。
【数３２】
2011033809.tif 000035
基底行列ＡＬＯのｎ＋１個のベクトルは線形独立なので、Ｌの階数はｎ＋１である。ＬＯ法の原理は、平文に対応するベクトルがＬの比較的短いベクトルであり、したがってＬの短いベクトルを探索すれば平文が見出される確率が高いというものである。実際ｉ＝１，・・・，ｎに対してｙｉ＝ｍｉで、ｙ＝１のときｙ０＝０であるから
ｖ＝（ｍ１，ｍ２，・・・，ｍｎ，０）    （２０）
はＬのベクトルであり、例えば２乗ノルムは
【数３３】
2011033809.tif 000036
となり短い。対してａｉたちは大きいので、ＡＬＯの各行ベクトルは長い。格子基底の各ベクトルをできるだけ短くすることを、格子基底縮小（または簡約）という。そしてこのための格子基底縮小アルゴリズムのひとつに前述のＬＬＬアルゴリズム［８］がある。
【００３８】
［４．２］  ナップザックベクトルの密度と解読率との関係
Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏ［４］やＣｏｓｔｅｒら［７］は、ｄがある値ｄｃ以下であれば、平文に対応するベクトルが格子の最短ベクトルである確率はｎが無限大になるとき漸近的に１になることを示した。さらにＬＬＬアルゴリズムを最短ベクトルを探索する近似法として用いて、上のことを実験的に検証した［４］。従来型のＭＨ暗号では必然的にｄ＜１となり、したがってＬＯ法は従来型ＭＨ暗号の解読に有効な道具となる。
【００３９】
［４．３］  本実施の形態へのＬＯ法の適用
さて、本実施の形態の場合はどうか。いま平文のハミング重み（ビット１の個数）をｔ（ｔ＞１と仮定する）とし、暗号化乗数ｅ＝（１，１，２，３，・・・ｔ−１）の場合について考える。格子Ｌ（ＡＬＯ）における解ベクトルｖ＝（ｍ’１，ｍ’２，・・・，ｍ’ｎ，０）、ただしｍ’ｉ＝ｍｉ×ｅｉのノルムの２乗は
【数３４】
2011033809.tif 000037
となる。よって‖ｖ‖はｔ３／２程度になる。これはＭＨ方式の場合の解ベクトルのそれｔ１／２と比べ長い。さらに多くの平文ではｔ＝ｎ／２であるから、‖ｖ‖はｎ３／２程度である。したがって解読を格子の最短非零ベクトル探索問題に帰着するＬＯ攻撃は有効でないと考えられる。
【００４０】
［５］  解読実験
［５．１］  小さな例
全数探索攻撃を無効にするためにはｎ＝１００程度が必要である。ここでは説明の簡単のためｎ＝１０の場合につき、ＬＯ法による解読実験の例を示す。
【００４１】
格子基底ＡをＬＬＬアルゴリズムに与え、縮小基底Ｂを得る。Ａの最左列要素は暗号文−Ｃと公開鍵ａ１，・・・，ａ１０をそれぞれｎ２＝１００倍して順に並べたものである。なお、Ａの並び方は前述の並び方とは異なるが、本質的な違いはないことに注意する。また、Ｂの最右列の（）内の数は各行ベクトルの長さの２乗である。
【００４２】
まず、解読に成功した場合の例を示す。解ベクトルはＢの２番目の行ベクトルと一致する。ここで平文ｍ＝（０，０，１，０，０，１，０，０，１，０）とする。この時の暗号文はＣ＝２５６５６＋３９７４０２＋２×５７７２７８＝１５７７６１４となる。
【数３５】
2011033809.tif 000038
【数３６】
2011033809.tif 000039
Ｂの第２行が解ベクトル０００２００１００１０と一致する。なお解ベクトルの長さは√６である。この例の場合、平文のハミング重みが小さいため解ベクトルが比較的短い。そのお陰で縮小基底の中に解ベクトルが現れたと考えられる。
【００４３】
次に解読に失敗した例を示す。この例では解ベクトルはＢのどの行ベクトルとも一致しない。ここで平文をｍ＝（０，１，１，０，０，０，１，１，１，０）とする。このとき暗号文はＣ＝２５６５６＋５８０３４３＋２×５２４４０９＋３×５７７２７８＋４×１２５８４５＝３８９００３１となる。
【数３７】
2011033809.tif 000040
【数３８】
2011033809.tif 000041
解ベクトル００４３０００２１１０はＢのどの行とも一致しない。この例の場合、解ベクトルの長さは３１１/２で、解ベクトルより短いベクトルが多数あるために、Ｂの中に現れなかったと考えられる。
【００４４】
［５．２］  解読結果
次元ｎを４０まで変化させ解読成功率を調べた結果を表２に示す。ｎ＝２０でも０．２％、ｎ＝３０で５０万回中３回、ｎ＝４０では１３０万回で解読は全て失敗であった。
【表２】
2011033809.tif 000042
【００４５】
［６］  検討と結び
本実施の形態におけるＭＨ暗号の特徴を一言でいえば、秘密鍵が通常の超増加性よりもさらに急激に増加するという鍵設定法にある。これは公開鍵の密度を低くし、そのために一見安全性が損なわれると考えられるが実はそうでないことを計算機実験によって示した。
【００４６】
ＭＨ暗号に対する一般的で最強の攻撃法としてラガリオス−オドリズコの方法が知られている。これによる解読実験の結果は十分に満足できるものである。４０次元においてさえ１３０万本の標本に対して解読成功は０であった。
【００４７】
鍵設定の特徴に伴い、当然暗号化の仕組みにも工夫がある。それは暗号化の際に公開鍵に乗数を乗ずることであるが、この乗数が平文に依存している。この平文依存性のお陰で解読を困難にしていると考えられる。
【００４８】
［７］  参考文献
[1] R. C. Merkle and M. E. Hellman, “Hiding information and signatures
in trapdoor knapsacks”, IEEE Trans. Inform. Theory, vol.IT-24, no.5,
pp.525-530, 1978.
[2] W. Diffie and M. E. Hellman : “New Directions in Cryptography”, IEEE
Trans. Inform. Theory, vol. IT?22, No. 6, pp.644?654, 1976.
[3] R. Rivest, A. Shamir and L. Adleman: “A method for obtaining digital
signatures and public-key cryptosystems”,   Comm. ACM, vol.21, No. 2,
pp.120-126, 1978.
[4] J. C. Lagarias and A. M. Odlyzko, “Solving low density sum problems”,
J. ACM, vol.32, pp.229-246, 1985.
[5] A.Shamir, “A polynomial time algorithm for breaking the basic Merkle-
Hellman cryptosystems”, IEEE Trans. Inform. Theory, vol. IT-30, no. 5,
pp.699-704, 1984.
[6] A. M. Frieze, “On the Lagarias?Odlyzko algorithm for the subset sum
problem”, SIAM J. Comput., vol. 15, pp.536?539, 1986.
[7] 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.
[8] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lov´asz, “Factoring Polynomials
with Rational Coefficients”, Mathematische Annalen, 261, 515-534, 1982.
【００４９】
［補足Ａ］  式（１２）の導出
式（８）における不等号を等号で置き換える。ただし、ｓ＝（１，１，２，３，・・・，ｎ−１）とする：
【数３９】
2011033809.tif 000043
さらにｂを公比ｒの等比数列とみなし、
ｂｉ＋１＝ｂ０ｒｉ      （２７）
と置く。そして式（２６）に式（２７）を代入しｂ０で除して
【数４０】
2011033809.tif 000044
を得る。
【００５０】
ここで公式
【数４１】
2011033809.tif 000045
を適用する。
【数４２】
2011033809.tif 000046
【００５１】
さてナップザックの次元ｎはかなり大きいので、ｉが十分大きいところを考える。１／ｒ＜１を考慮し、（１／ｒ）ｉ以上の高次項を無視し、両辺に（１−１／ｒ）２を乗じて整理すると、
（１−１／ｒ）２＝１／ｒ
となる。これから式（１６）が得られる。
【００５２】
［補足Ｂ］  ＬＯ法に用いる種々の格子基底
Ｌａｇａｒｉａｓ−Ｏｄｌｙｚｋｏのオリジナル［４］のほかにも色々提案されているが、よく知られたものにＦｒｉｅｚｅのもの［６］とＣｏｓｔｅｒらのもの［７］がある。なおＣｏｓｔｅｒらの基底ＡＣでは臨界密度が上がる（解読がより強力になる）。一方、Ｆｒｉｅｚｅ基底ＡＦでは臨界密度がＬＯ基底と変わらず、証明が簡単化されるだけ、というのが理論的結果である。しかし、計算機実験ではＦｒｉｅｚｅ基底は改良になっている。ここにも理論と実際の違いがある。
【数４３】
2011033809.tif 000047
【数４４】
2011033809.tif 000048
【００５３】
［補足Ｃ］  本実施の形態にかかる暗号の解読に適用可能な別の格子基底
次のような基底行列Ａ’が考えられる。たとえば、ａ１は最大ｎ−１倍されて加算されるから、最終要素がａ１である行ベクトルをｎ−１個用意する。以下同様にａ２は最大ｎ−２倍されて加算されるから、最終要素がａ２である行ベクトルをｎ−２個用意する。Ａ’の左上はＮ次の単位行列ＩＮである。ただし、Ｎ＝１＋１＋２＋・・・＋ｎ−１＝ｎ（ｎ−１）／２＋１である。
【数４５】
2011033809.tif 000049
【００５４】
このような基底を用いれば解ベクトルはＮ＋１次元格子の長さ（ｔ（ｔ−１）/２＋１）１/２≒Ｎ１/２程度のベクトルになる。ゆえに解ベクトルの長さと次元との比はＮ−１/２となりこれは通常のＭＨ暗号に対するＬＯ法の場合と同じである。しかしこれは解読できるとは考えにくい。なぜならｎ＝１００としてもＮ＝５０００次元程度の格子を対象にすることになるからである。さらにＡＬＯ法の場合と異なり、第Ｎ＋１要素が等しいベクトルが多数あるので長さ√２の短いベクトルが多数存在する。よって、解ベクトルが見出されるとは考えられない。
【００５５】
［具体例］
実施の形態
図１は、実施の形態に係る暗号システム１００の全体構成を表す図である。これらの構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされた暗号処理機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。後述する復号装置２００、暗号化装置３００、および鍵生成装置４００の構成についても同様である。
【００５６】
暗号システム１００は、復号装置２００と暗号化装置３００とを含む。復号装置２００は、鍵生成装置４００を用いて低密度秘密鍵と公開鍵とを生成する。復号パラメータ記憶部３０は、鍵生成装置が生成した低密度秘密鍵と暗号化乗数とを格納する。公開鍵送信部１４は、鍵生成装置４００が生成した公開鍵を、インターネット等の通信手段を通じて暗号化装置３００に送信する。
【００５７】
暗号化装置３００の公開鍵受信部１６は、鍵生成装置４００が生成した公開鍵を、復号装置２００の公開鍵送信部１４から受信する。公開鍵記憶部１８は、公開鍵受信部１６が受信した公開鍵を格納する。暗号文生成部２０は、公開鍵記憶部１８から公開鍵を受け取り、平文入力部２２から入力された平文についての暗号文を生成する。暗号文送信部２４は、暗号文生成部２０から受け取った暗号文を、インターネット等の通信手段を通じて復号装置２００に送信する。
【００５８】
復号装置２００の暗号文受信部２６は、暗号化装置３００の暗号文生成部２０が生成した暗号文を暗号化装置３００の暗号文送信部２４から受信する。復号部２８は、暗号文受信部２６が受信した暗号文を、復号パラメータ記憶部３０から受け取った低密度秘密鍵と暗号化乗数とを用いて復号する。平文出力部３２は、復号部２８が復号した平文を、例えば図示しないモニタ等の出力装置に出力する。
【００５９】
図２は、以上の構成の暗号システム１００による鍵生成から暗号文の復号およびその結果の出力に至るまでの手順を説明するフローチャートである。
【００６０】
低密度秘密鍵生成部１０は低密度秘密鍵と秘密鍵乗数とを生成する（Ｓ１０）。公開鍵生成部１２は、低密度秘密鍵生成部１０から低密度秘密鍵と秘密鍵乗数とを受け取り、公開鍵ベクトルおよび暗号化乗数を生成する（Ｓ１２）。公開鍵送信部１４は、公開鍵生成部１２が生成した公開鍵ベクトルと暗号化乗数とを合わせて公開鍵として、インターネット等の通信手段を通じて、暗号化装置３００に送信する（Ｓ１４）。
【００６１】
公開鍵受信部１６は、公開鍵送信部１４が送信した公開鍵を受信する（Ｓ１６）。暗号文生成部２０は、公開鍵受信部１６が受信した公開鍵を格納している公開鍵記憶部１８から公開鍵を受け取り、かつ平文入力部２２に入力された平文を受け取って、暗号文を生成する（Ｓ１８）。暗号文送信部２４は、暗号文生成部２０が生成した暗号文を、インターネット等の通信手段を通じて、復号装置２００に送信する（Ｓ２０）。
【００６２】
暗号文受信部２６は、暗号文送信部２４が送信した暗号文を受信する（Ｓ２２）。復号部２８は、低密度秘密鍵生成部１０が生成した低密度秘密鍵および公開鍵生成部１２が生成した暗号化乗数とを格納している復号パラメータ記憶部３０から低密度秘密鍵および暗号化乗数を受け取り、かつ暗号文受信部２６が受信した暗号文を受け取って、暗号文を平文に復号する（Ｓ２４）。平文出力部３２は、復号部２８が復号した平文を図示しないモニタ等の出力デバイスに出力する（Ｓ２６）。
【００６３】
図３は、図１の鍵生成装置４００の構成図である。鍵生成装置４００は復号装置２００の内部にあり、低密度秘密鍵生成部１０と公開鍵生成部１２とを含む。鍵生成装置４００は、低密度秘密鍵と公開鍵とを生成するものである。
【００６４】
低密度秘密鍵生成部１０は、平文のビット数入力部３４、秘密鍵乗数生成部３６、低密度秘密鍵ベクトル生成部３８、法Ｍ生成部４０、乗数生成部４２、逆元生成部４８および復号パラメータ出力部５０を含む。また、公開鍵生成部１２は、公開鍵ベクトル生成部４４と暗号化乗数生成部４６とを含む。
【００６５】
平文のビット数入力部３４は、平文のビット数ｎの入力を受け取る。秘密鍵乗数生成部３６は、平文のビット数入力部３４から平文のビット数ｎを受け取り、秘密鍵乗数ｓ＝（ｓ１，ｓ２，・・・，ｓｎ）を生成する。ここで秘密鍵乗数生成部３６は、前提技術［３．１］の記載に基づき、任意に設定するｎ個の自然数の列を秘密鍵乗数ｓとして生成する。
【００６６】
低密度秘密鍵ベクトル生成部３８は、秘密鍵乗数生成部３６から秘密鍵乗数ｓを受け取り、低密度秘密鍵ベクトルｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を生成する。ここで低密度秘密鍵ベクトル生成部３８は、前提技術［３．１］に記載の式（８）に基づいて低密度秘密鍵ベクトルｂを生成する。
【００６７】
上記の方法で生成された低密度秘密鍵ベクトルｂは、通常のＭＨ暗号における秘密鍵と比べて、要素の増加の仕方よりもさらに急となる。この結果、前提技術［４］に記載の公開鍵ベクトルの密度は低くなる。このように、低密度秘密鍵ベクトルとは、対応する公開鍵ベクトルの密度が通常のＭＨ暗号の公開鍵と比べて低くなるベクトルをいう。
【００６８】
法Ｍ生成部４０は、秘密鍵乗数生成部３６から秘密鍵乗数ｓを、低密度秘密鍵ベクトル生成部３８から低密度秘密鍵ベクトルｂを受け取り、前提技術［３．１］に記載の式（９）に基づいて法Ｍを生成する。乗数生成部４２は、法Ｍ生成部４０から法Ｍを受け取り、Ｍと互いに素な整数である乗数ｗを生成する。
【００６９】
暗号化乗数生成部４６は、秘密鍵乗数生成部３６から秘密鍵乗数ｓを受け取り、暗号化乗数ｅ＝（ｅ１，ｅ２，・・・，ｅｎ）を生成する。ここで暗号化乗数生成部４６は、前提技術［３．２］に記載の式（１１）に基づいて暗号化乗数ｅを生成する。暗号化乗数ｅは図１の公開鍵送信部１４に送られ、復号パラメータの一部として復号パラメータ記憶部３０にも出力される。
【００７０】
公開鍵ベクトル生成部４４は、低密度秘密鍵ベクトル生成部３８、法Ｍ生成部４０、乗数生成部４２からそれぞれ低密度秘密鍵ベクトルｂ、法Ｍ、乗数ｗを受け取り、低密度秘密鍵ベクトルｂの要素と乗数ｗとの積を法Ｍについてモジュラ乗算変換することで公開鍵ベクトルａを生成する。これは前提技術［３．２］に記載の式（１０）に基づくものである。
【００７１】
逆元生成部４８は法Ｍ生成部４０と乗数生成部４２とからそれぞれ法Ｍ、乗数ｗを受け取り、Ｍを法とするｗの逆元ｗ−１を生成する。復号パラメータ出力部５０は、低密度秘密鍵ベクトル生成部３８、法Ｍ生成部４０、逆元生成部４８からそれぞれ低密度ベクトルｂ、法Ｍ、逆元ｗ−１を受け取り、それらを合わせて復号パラメータの一部として、図１の復号パラメータ記憶部３０に出力する。
【００７２】
図４は、以上の構成の鍵生成装置４００内の低密度秘密鍵生成部１０における秘密鍵生成手順を説明するフローチャートであり、図２におけるＳ１０を詳細に説明するものである。
【００７３】
秘密鍵乗数生成部３６は、平文のビット数ｎを用いて、ｎ個の自然数の列を秘密鍵乗数ｓとして生成する（Ｓ２８）。低密度秘密鍵ベクトル生成部３８は、秘密鍵乗数ｓを用いて低密度秘密鍵ベクトルｂを生成する（Ｓ３０）。法Ｍ生成部４０は、低密度秘密鍵ベクトルｂを用いて、式（９）を満たす自然数である法Ｍを生成する（Ｓ３２）。乗数生成部４２は、法Ｍを用いて、Ｍと互いに素な整数である乗数ｗを生成する（Ｓ３４）。逆元生成部４８は、法Ｍと乗数ｗとを用いて、ｗｗ−１≡１（ｍｏｄ Ｍ）を満たすｗの逆元ｗ−１を生成する（Ｓ３６）。これは例えば拡張されたユークリッドの互除法を用いれば計算することができる。
【００７４】
図５は、低密度秘密鍵ベクトルｂを生成するための一例を説明するものであり、図４におけるＳ３０を、具体例を用いて詳細に説明するものである。
【００７５】
低密度秘密鍵ベクトル生成部３８はｂ１の初期値として、図示しない乱数生成器によって生成された乱数ｒｎをｂ１に格納する（Ｓ３８）。ここで乱数ｒｎは１〜Ｒの間の整数である。ｉを第１のループ変数とし、ｉに初期値２を入力する（Ｓ４０）。
【００７６】
ステップＳ４２は第１のループの終了を判定するステップである。第１のループ変数ｉと平文のビット数ｎとを比較し、ｉがｎ以下の間第１のループを回す（Ｓ４２Ｙ）。ｉがｎより大きくなったときにループを終了する（Ｓ４２Ｎ）。ｊを第２のループ変数とし、ｊに１を代入する（Ｓ４４）。次いで、ｂｉを０で初期化する（Ｓ４６）。
【００７７】
ステップＳ４８は第２のループの終了を判定するステップである。第２のループ変数ｊと第１のループ変数ｉとを比較し、ｊがｉよりも小さい間第２のループを回す（Ｓ４８Ｙ）。ｊがｉ以上になたときにループを終了する（Ｓ４８Ｎ）。ステップＳ５０はｂｉの値を更新するステップである。第１のループ変数ｉと第２のループ変数ｊとを用いて、ｂｉにｂｉ＋ｓｊｂｉ−ｊの値を代入する（Ｓ５０）。ｂｉを更新したら第２のループ変数ｊを１増加することで、第２のループ変数ｊを更新する（Ｓ５２）。
【００７８】
第２のループが終了した後、得られたｂｉに図示しない乱数生成器によって生成された乱数ｒｎを加算する（Ｓ５４）。これは前提技術［３．１］に記載の式（８）の不等号を成立させるためである。ステップＳ５４によってｂｉの生成は終了である。第１のループ変数ｉを１増加して更新し（Ｓ５６）、第１のループの終了を判定するステップＳ４２に戻る。
【００７９】
第１のループが終了すれば低密度秘密鍵ｂの生成は完了する。以上のステップを踏むことによって生成されたベクトルｂは式（８）を満足する。ベクトルｂを低密度秘密鍵ベクトルｂとして出力する（Ｓ５８）。
【００８０】
以上述べたように、鍵生成装置４００によれば、低密度秘密鍵ベクトルｂを含む秘密鍵を生成することが可能となる。公開鍵ベクトルａは低密度秘密鍵ベクトルｂを用いて従来手法と同様に計算することができる。
【００８１】
次に、平文の暗号化および暗号文の復号の際に用いられる暗号化乗数ｅの生成手順の一例について図６を用いて説明する。図６は暗号化乗数生成部４６における暗号化乗数ｅの生成手順を説明するフローチャートである。前述したように、暗号化乗数ｅは前提技術［３．２］に記載の式（１１）に基づくものである。
【００８２】
式（１１）の右辺を評価するために、秘密鍵乗数ｓの要素の和を格納するための補助変数Ｓを導入し、初期値としてＳに０を代入する（Ｓ６０）。また、式（１１）の左辺を評価するために、暗号化乗数ｅの要素の和を格納するための補助変数Ｅを導入し、初期値として０を代入する（Ｓ６２）。ループ変数ｊに初期値として１を代入する（Ｓ６４）。
【００８３】
ステップＳ６６はループの終了を判断するステップである。ループ変数ｊと平文のビット数ｎとを比較し、ｊがｎ以下の間ループを回す（Ｓ６６Ｙ）。ｊがｎより大きくなったときにループを終了する（Ｓ６６Ｎ）。ステップＳ６８は補助変数Ｓを更新するステップである。具体的にはＳにＳ＋ｓｊを代入する（Ｓ６８）。これにより、補助変数Ｓは暗号化乗数ｓの要素が順に加算されることになる。続いて、ｅｊの値は補助変数ＳとＥとを用いて生成する。具体的には、ｅｊは１からＳ−Ｅ以下の自然数をランダムに与える（Ｓ７０）。ここでＲｎ（ｘ）を１〜ｘの間の自然数をランダムに生成する関数とすれば、ｅｊ＝Ｒｎ（Ｅ−Ｓ）となる。
【００８４】
補助変数ＥにＥ＋ｅｊを代入する（Ｓ７２）。これにより、補助変数Ｅは暗号化乗数ｅの要素が順に加算されることになる。ループ変数ｊを１増加することでループ変数ｊを更新し（Ｓ７４）、終了判定に戻る。ループ変数ｊがｎより大きくなればループが終了し、暗号化乗数ｅが生成される。生成された暗号化乗数ｅを出力し（Ｓ７６）、終了でする。
【００８５】
ステップＳ７０により、ｅｊは１以上Ｓ−Ｅ以下のランダムな自然数となる。これにより、秘密鍵乗数ｓの要素と暗号化乗数ｅの要素との関係を規定する式（１１）を満たすことが保証される。
【００８６】
図１の３００は、本実施の形態に係る暗号化装置の構成図である。暗号化装置３００は、公開鍵受信部１６、公開鍵記憶部１８、暗号文生成部２０、平文入力部２２、暗号文送信部２４を含む。
【００８７】
図７は本発明の実施の形態に係る暗号文生成の手順を説明するフローチャートであり、図２におけるＳ１８を詳細に説明するものである。以下説明する暗号文生成手順は、前提技術[３．３]に記載のアルゴリズムに基づくものである。
【００８８】
まず、平文ｍ＝ｍｉ（ｉ＝１，・・・，ｎ）∈｛０，１｝、公開鍵ベクトルａ、暗号化乗数ｅの入力を受け付ける（Ｓ７８、Ｓ８０、Ｓ８２）。続いて暗号Ｃを０で初期化し（Ｓ８４）、ループ変数ｉをｎに初期化する（Ｓ８６）。暗号化乗数ｅの要素を特定する変数ｊを１に初期化する（Ｓ８８）。
【００８９】
Ｓ９０はループの終了を判定するステップであり、ループ変数ｉの値が０より大きい間ループを回す（Ｓ９０Ｙ）。ｉの値が０以下になったらループを抜ける（Ｓ９０Ｎ）。ステップＳ９２平文の要素ｍｉの値に応じて処理を分岐するステップである。平文の要素ｍｉは０または１のいずれかの値を持つから、その値に応じて処理を分岐するものである。具体的にはｍｉ＝１の場合には暗号分Ｃを更新し（Ｓ９２Ｙ）、ｍｉ＝０の場合には暗号文Ｃの更新をスキップする（Ｓ９２Ｎ）。
【００９０】
ステップＳ９４は暗号文Ｃの値を更新するステップである。具体的には、Ｃの値に公開鍵ベクトルのｉ番目の要素の値ａｉと暗号化乗数の要素ｅｊとの積を加算する（Ｓ９４）。次いでインデックスｊの値更新するためｊの値を１増加する（Ｓ９６）。ステップＳ９８はループ変数ｉを更新するステップであり、ｉの値を１減少する。ステップＳ１００は、以上の手順で生成された暗号文Ｃを出力する（Ｓ１００）。
【００９１】
以上のステップによると、平文ｍｉの値を後ろから（ｉの大きい方から）順に調べていき、ｍｉ＝１を見つける毎に対応する公開鍵ａの要素と暗号化乗数ｅの要素との積をＣに加算するのであるが、加算の際に、公開鍵ａの要素に乗ずる暗号化乗数ｅの要素を順に変更する、という処理が行われることになる。これにより、暗号文Ｃに加算される公開鍵ベクトルの要素ａｉに乗ずる暗号化乗数ｅの要素は、平文の要素ｍｉにおける１の出現パターンによって異なることになる。
【００９２】
以上述べたように、暗号化装置３００によれば、暗号化乗数ｅと低密度ベクトルｂを用いて生成された公開鍵ベクトルａとに基づいて平文を暗号化することができる。
【００９３】
図１の２００は、本発明の実施の形態に係る復号装置の構成図である。復号装置２００は、鍵生成装置４００、公開鍵送信部１４、復号パラメータ記憶部３０、暗号文受信部２６、復号部２８、平文出力部３２を含む。
【００９４】
図８は本発明の実施の形態に係る復号の手順を説明するフローチャートであり、図２におけるＳ２４を詳細に説明するものである。以下説明する復号の手順は、前提技術[３．４]に記載のアルゴリズムに基づくものである。
【００９５】
図８（ａ）におけるステップＳ１０２、Ｓ１０４、Ｓ１０６、Ｓ１０８、Ｓ１１０はいずれも復号のための情報を受け取るステップであり、それぞれ低密度秘密鍵ベクトルｂ（Ｓ１０２）、暗号化乗数ｅ（Ｓ１０４）、逆元ｗ−１（Ｓ１０６）、法Ｍ（Ｓ１０８）、暗号文Ｃ（Ｓ１１０）の入力を受け取る。法Ｍ、逆元ｗ−１、暗号文Ｃを用いて、暗号文Ｃを低密度秘密鍵ベクトルｂの要素の和に変換する（Ｓ１１２）。続いて、ｎ個の平文の要素ｍｉ（ｉ＝１，・・・，ｎ）の値を０で初期化する（Ｓ１１４）。ループ変数ｉをｎに初期化し（Ｓ１１６）、ｊの値を１に初期化する（Ｓ１１８）。
【００９６】
図８（ｂ）は図８（ａ）の後半部分であり復号処理を行うステップである。ステップＳ１２０はループの終了を判定するステップであり、ループ変数ｉの値が０より大きい間ループを回す（Ｓ１２０Ｙ）。ループ変数委が０以下となったらループを終了する（Ｓ１２０Ｎ）。ステップＳ１２２は暗号文Ｃと、低密度秘密鍵ベクトルの要素ｂｉと暗号化乗数の要素ｅｊとの積ｅｊｂｉとの大小関係による分岐のステップである。Ｃがｅｊｂｉより小さければ、後述するステップＳ１２４、Ｓ１２６、Ｓ１２８を飛ばしてＳ１３０に進み（Ｓ１２２Ｎ）、Ｃがｅｊｂｉ以上の場合には後述するステップＳ１２４、Ｓ１２６、Ｓ１２８に進んで暗号文の更新等の操作を行う（Ｓ１２２Ｙ）。
【００９７】
Ｃがｅｊｂｉ以上であるときに、対応する平文の要素ｍｉの値を１とする（Ｓ１２４）。前提技術［３．６］で説明したように、Ｃがｅｊｂｉ以上であればｅｊｂｉ以上はＣに足された要素のひとつである。したがって、ｂｉに対応する平文の要素ｍｉの値は１である。ステップＳ１２６は暗号文Ｃの値を更新するステップである。具体的にはＣの値をＣ−ｅｊｂｉに更新する（Ｓ１２６）。続いて暗号文のインデックスｊの値を更新する。具体的にはｊの値をｊ＋１に更新する（Ｓ１２８）。これにより、暗号化乗数ｅの要素の添字であるｊは１から順に増加すことになる。
【００９８】
ステップＳ１３０はループ変数ｉを更新するステップである。具体的にはｉの値を１減少する（Ｓ１３０）。以上の手順で生成された平文ｍを出力して終了する（Ｓ１３２）。
【００９９】
図７に示す暗号化のステップと図８に示す復号のステップとを比べると、インデックスの初期化ステップであるステップＳ８６とＳ１１６およびインデックスの更新ステップであるステップＳ９６とＳ１２８、Ｓ９８とＳ１３０とが同一である。これは暗号化の際と復号の際との低密度秘密鍵ｂの要素ｂｉに乗ずる暗号化乗数ｅの要素ｅｊを変更する順序を同一にするためである。復号は後ろから（インデックスｉの値の大きい方から）順に行う必要があるという事実に合わせて暗号化も後ろから行えば、暗号化と復号の際のｅｊの変更順序を一致させることができ、１回で復号処理を終了できる点で有利である。
【０１００】
以上説明したように低密度秘密鍵ベクトルｂが既知であれば、ステップＳ１２０からＳ１３０のステップを踏むことで暗号化乗数ｅの要素のインデックスｊを更新することができ暗号文を復号することができる。
【０１０１】
Ｃを低密度秘密鍵ベクトルｂの要素ｂｉと暗号化乗数の要素ｅｊとの積ｅｊｂｉのいずれかの要素の和で分解する問題は組み合わせ最適化問題と呼ばれる問題に属し、一般的には要素の数が多い場合には最適解を得ることは困難とされている。しかし、もしｅｊｂｉが適切な組み合わせ、すなわち、暗号化の際に用いられた組み合わせを既知とすれば、前提技術[３．４]のアルゴリズムにより、Ｃとｅｊｂｉとの比較と引き算とで簡単に解くことができる。
【０１０２】
したがって、本実施例の緩増加ベクトルｂは、組み合わせ最適化問題の困難性により安全性を担保する暗号であれば、その秘密鍵として利用することができる。
【０１０３】
一方、低密度秘密鍵ベクトルｂを知ることのできない攻撃者、すなわち暗号文Ｃ、公開鍵ベクトルａ、暗号化乗数ｅを盗聴した攻撃者は、ｅｊｂｉ（ｅｊａｉ）の適切な組み合わせを知ることはできない。低密度秘密鍵ベクトルｂが分からないし、暗号化乗数ｅの要素のインデックスｊの出現の仕方は平文ｍにおける１の出現パターンに依存しているからである（図７におけるＳ９２）。
【０１０４】
以上述べたように、復号装置２００によれば、公開鍵ベクトルａおよび暗号化乗数ｅを用いて生成された暗号文Ｃを、低密度秘密鍵ベクトルｂ、暗号化乗数ｅ、逆元ｗ−１、法Ｍを用いて復号することができる。また、低密度秘密鍵ベクトルｂを知らない攻撃者に対しては、ＬＯ法に耐性を有することができる。
【０１０５】
以下、本発明の実施の形態に係る暗号化および復号の手順について数値例を用いて具体的に説明する。
【０１０６】
表３は平文のビット数ｎが５、秘密鍵乗数ｓ＝（２，３，５，７，９）、暗号化乗数ｅ＝（１，４，５，６，７）の場合の暗号化および復号の数値例である。低密度秘密鍵ベクトルｂは（２，５，１７，６０，２１３）の５個の要素ｂｉ（ｉ＝１，・・・，５）を持つベクトルであり、式（８）を満足する。法Ｍは７４７であり、ｓ１ｂ５＋ｓ２ｂ４＋ｓ３ｂ３＋ｓ４ｂ２＋ｓ５ｂ１＝７４４よりも大きく、式（９）を満足する。乗数ｗ＝６０７、逆元ｗ−１＝１６である。Ｍとｗは互いに素であり、これらはｗｗ−１≡１（ｍｏｄ Ｍ）である。なお表中ｗｉはｗ−１を意味するものとする。
【０１０７】
【表３】
2011033809.tif 000050
【０１０８】
秘密鍵ｂｉは式（８）に基づいて生成したものである。例えばｂ３の値１７は、ｓ２ｂ１＋ｓ１ｂ２＝１６よりも大きい。公開鍵ベクトルａは式（１０）に基づいて生成したものである。例えばａ２の値はｂ２とｗとの積（５×６０７＝３０３５）を法Ｍの値である７４７で割った余りであるから４７となる。
【０１０９】
まず暗号化の手順について説明する。暗号化プロセスでは図７におけるステップＳ９０からＳ９８にしたがい、ｉ＝５からｉ＝１に至るまで、平文ｍの要素が１であるかどうかを調べる。表３ではｉ＝５のとき初めてｍ５＝１となるから、Ｃにｅ１×ａ５＝６０の値が加算される。ｉ＝４のときもｍ４＝１となるから、Ｃにｅ２×ａ４＝２２５６の値を加算し、２３１６を得る。これをｉ＝１まで繰り返すことで、最終的に暗号文ＣはＣ＝２５５１となる。
【０１１０】
次に復号の手順について説明する。暗号文ＣをＭとｗ−１とによりモジュラ乗算変換し、Ｃ’を得る。具体的にはｗ−１×Ｃ＝４０８１６となるが、これをＭ＝７４７で割った余りは４７８となるのでＣ’の値は４７８となる。
【０１１１】
以後は図８におけるステップＳ１２０からＳ１３０にしたがい、ｉ＝５からｉ＝１に至るまで順にｅｊｂｉの要素がＣ’以下であるかどうかを調べる。表３ではｉ＝５でＣ’≧ｅ１ｂ５となる。そこでＣ’の値をＣ’−ｅ１ｂ５＝４７８−１×２１３＝２６５に更新する。ｉ＝４のときＣ’≧ｅ２ｂ４となるから、今度はＣ’の値をＣ’２−ｅ２ｂ４＝２６５−４×６０＝２５に更新する。これをｉ＝１まで繰り返し、Ｃ’＝０となれば復号終了である。
【０１１２】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下そのような変形例を説明する。
【０１１３】
上記の説明では、暗号化乗数ｅを公開鍵として送信する構成としたが、暗号化する者と復号する者との間で暗号化乗数ｅについての共通認識がある場合には、暗号化乗数ｅを公開鍵として送信する必要はない。例えばｅとして、ｅ＝（１，１，２，３，４，５，・・・）の様に単純に１ずつ増加するものを採用するという取り決めがある場合などである。この場合、送信される公開鍵および暗号文Ｃは、見かけ上従来型ＭＨ暗号のそれと区別は付かない。
【０１１４】
上記の説明では、実施の形態の暗号システム１００の利用例として暗号鍵生成を説明したが、これ以外に、本実施の形態における暗号鍵はデジタル署名の生成と検証に用いてもよい。
【符号の説明】
【０１１５】
１０  低密度秘密鍵生成部、  １２  公開鍵生成部、  １４  公開鍵送信部、  １６  公開鍵受信部、  １８  公開鍵記憶部、  ２０  暗号文生成部、  ２２  平文入力部、  ２４  暗号文送信部、  ２６  暗号文受信部、  ２８  復号部、  ３０  復号パラメータ記憶部、  ３２  平文出力部、  ３４  平文のビット数入力部、  ３６  秘密鍵乗数生成部、  ３８  低密度秘密鍵ベクトル生成部、  ４０  法Ｍ生成部、  ４２  乗数生成部、  ４４  公開鍵ベクトル生成部、  ４６  暗号化乗数生成部、  ４８  逆元生成部、  ５０  復号パラメータ出力部、  １００  暗号システム、  ２００  復号装置、  ３００  暗号化装置、  ４００  鍵生成装置。
【図１】
2011033809.tif 000063
【図２】
2011033809.tif 000064
【図３】
2011033809.tif 000065
【図４】
2011033809.tif 000066
【図５】
2011033809.tif 000067
【図６】
2011033809.tif 000068
【図７】
2011033809.tif 000069
【図８】
2011033809.tif 000070