暗号システム、鍵生成装置、暗号化装置、復号化装置及び暗号処理方法
【課題】 標準計算機モデル上でＩＮＤ−ＣＣＡ安全であり、また、マルチユーザ環境においてもセキュリティ・リダクションを損なわない公開鍵暗号方法を提供すること。
【解決手段】 暗号の安全性を、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性と、特定の条件を満たす関数族の安全性に帰着するように、設計された公開鍵及び秘密鍵を鍵生成装置１１０で作成し、暗号化装置１３０では、鍵生成装置１１０で作成された公開鍵を用いてメッセージ文から暗号文を生成する。そして、復号化装置１５０では、暗号化装置１３０で生成された暗号文を、鍵生成装置１１０で作成された秘密鍵を用いて復号する。
【解決手段】 暗号の安全性を、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性と、特定の条件を満たす関数族の安全性に帰着するように、設計された公開鍵及び秘密鍵を鍵生成装置１１０で作成し、暗号化装置１３０では、鍵生成装置１１０で作成された公開鍵を用いてメッセージ文から暗号文を生成する。そして、復号化装置１５０では、暗号化装置１３０で生成された暗号文を、鍵生成装置１１０で作成された秘密鍵を用いて復号する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージ文を暗号化又は復号化する技術に関する。
【背景技術】
【０００２】
非特許文献１では、公開鍵暗号の安全性の概念が記載されており、ＩＮＤ−ＣＣＡ安全であることが最高レベルの安全性であると考えられている。実際には、公開鍵暗号がＩＮＤ−ＣＣＡ安全であることは、ランダムオラクルモデル、または、標準計算機モデル上で証明が与えられる。
【０００３】
ランダムオラクルモデルは、ランダム関数へのオラクルアクセスを前提としているため非現実のモデルである。よって、ランダムオラクルモデル上の安全性証明は現実システムでの安全性を完全に保証する訳ではなく、ひとつの指標と考えられている。しかし、実用性に優れた多様なバリエーションの公開鍵暗号方法を設計することが容易であり、実用化されている公開鍵暗号の多くはランダムオラクルモデル上でＩＮＤ−ＣＣＡ安全性が与えられている。
【０００４】
一方、標準計算機モデルは、現実の計算機システムに近いため、このモデル上での安全性証明は現実世界での安全性証明に等しいと考えられている。このように、安全性の観点からは、標準計算機モデル上でＩＮＤ−ＣＣＡ安全であることが望ましいが、実用的な方式設計が難しく、ランダムオラクルモデルに比べるとバリエーションが非常に少ない。非特許文献３に記載されている公開鍵暗号方式が、標準計算機モデル上でＩＮＤ−ＣＣＡ安全で、かつ、実用性を備えた方式として代表的なものである。
【０００５】
ところで、非特許文献１に記載されているＩＮＤ−ＣＣＡ安全の概念は、単一の送信者及び受信者に対して、ターゲットとなる暗号文がひとつ与えられた状況において定式化されている（以下、シングルユーザ環境と呼ぶ）。
【０００６】
しかし、現実世界では、同報メール通信など、同一のメッセージ文が複数の相手に対して送られている場合も少なくない。また、メールの返信などでは、同一メッセージ文の全体又は一部を含んだ新たなメッセージ文から暗号文が作成されることも多い。非特許文献２では、このようなマルチユーザ環境において、識別不能性の検証を行っている。
【０００７】
非特許文献２によると、シングルユーザ環境において識別不能性が示されれば、マルチユーザ環境においても識別不能性は示されるが、一般にはセキュリティ・リダクションは大きく劣化することが記載されている。ここで、セキュリティ・リダクションとは、暗号の安全性を計算量的困難性が予想される問題に帰着する際の帰着効率を意味する。セキュリティ・リダクションが悪い場合、暗号の安全性のためのパラメータ（鍵の長さなど）を大きく選ぶ必要性があり、暗号の効率性を大きく損なう場合が多い。
【０００８】
よって、実用上の観点から、計算量的困難性が十分に予想された問題に効率良く帰着するように公開鍵暗号をデザインすることが望ましい。非特許文献２によると、弱い安全性（ＩＮＤ−ＣＰＡ）をもつＥｌｇａｍａｌ暗号はマルチユーザ環境においてもセキュリティ・リダクションを全く損なわないことが示されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among notions of security for public-key encryption schemes: http://www.cse.ucsd.edu/~mihir/crypto-research-papers.html
【非特許文献２】M. Bellare, P. Boldyreva, and S.Micali. Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements: http://www.cse.ucsd.edu/~mihir/crypto-research-papers.html
【非特許文献３】R.Cramer and V.Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack: http://www.shoup.net/papers/
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以上に記載したように、非特許文献３では、標準計算機モデル上でＩＮＤ−ＣＣＡ安全な公開鍵暗号方法が記載されている。
【００１１】
しかしながら、非特許文献３に記載の標準計算機モデル上でＩＮＤ−ＣＣＡ安全な公開鍵暗号方法は部分的にはマルチユーザ環境においてもセキュリティ・リダクションを損なわないが完全ではないことが示されており、標準計算機モデル上で強い安全性（ＩＮＤ−ＣＣＡ）を持つ公開鍵暗号方法で、マルチユーザ環境においてもセキュリティ・リダクションを全く損なわない方法は知られていない。
【００１２】
そこで、本発明は、標準計算機モデル上でＩＮＤ−ＣＣＡ安全であり、また、マルチユーザ環境においてもセキュリティ・リダクションを損なわない公開鍵暗号方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
以上の課題を解決するため、本発明は、暗号の安全性を、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性と、特定の条件を満たす関数族の安全性に帰着するように、公開鍵暗号を設計する。
【００１４】
例えば、本発明は、第一の鍵情報を用いて、メッセージ文を暗号化した暗号文を生成し、第二の鍵情報を用いて、当該暗号文の復号化を行う少なくとも一つ以上のコンピュータを備える暗号システムであって、
前記コンピュータの制御部が、
セキュリティパラメータｋの入力を受け付ける処理と、
【００１５】
【数１】
【００１６】
および
【００１７】
【数２】
【００１８】
をランダムに作成する処理と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【００１９】
【数３】
【００２０】
を計算する処理と、
一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理と、
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【００２１】
【数４】
【００２２】
として生成する処理と、を行うこと、
但し、Ｆｋは、下記の（５）式で示され、ｆσは、Ｇ４上の関数である。
【００２３】
【数５】
【００２４】
を特徴とする。
【発明の効果】
【００２５】
以上のように、本発明によれば、標準計算機モデル上でＩＮＤ−ＣＣＡ安全であり、また、マルチユーザ環境においてもセキュリティ・リダクションを損なわない公開鍵暗号方法を提供することができる。
【図面の簡単な説明】
【００２６】
【図１】暗号システムの概略図。
【図２】鍵生成装置の概略図。
【図３】コンピュータの概略図。
【図４】暗号化装置の概略図。
【図５】復号化装置の概略図。
【図６】暗号システムでの動作手順を説明するためのシーケンス図。
【発明を実施するための形態】
【００２７】
図１は、本発明の一実施形態である暗号システム１００の概略図である。図示するように、暗号システム１００は、鍵生成装置１１０と、暗号化装置１３０と、復号化装置１５０と、を備え、これらは、通信回線１７０を介して、相互に情報の送受信を行うことができるようにされている。
【００２８】
そして、本実施形態では、公開鍵暗号Π＝（Ｋ，Ｅ，Ｄ）において、公開鍵暗号Πの鍵生成手段Ｋ、暗号化手段Ｅ、および、復号化手段Ｄは、それぞれ鍵生成装置１１０、暗号化装置１３０、および、復号化装置１５０により実現される。
【００２９】
図２は、鍵生成装置１１０の概略図である。図示するように、鍵生成装置１１０は、情報の入力を受け付ける入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵生成装置１１０の各部の制御を行う制御部１１２と、記憶部１１７と、通信回線１７０を介して暗号化装置１３０又は復号化装置１５０と通信を行う通信部１２１と、情報を出力する出力部１２２と、を備える。
【００３０】
ここで、制御部１１２は、乱数の生成を行う乱数生成部１１３と、公開鍵及び秘密鍵の生成を行う演算部１１４と、一方向性置換π及び落とし戸π−１を生成する落とし戸付き一方向性置換生成部１１５と、を備える。
【００３１】
また、記憶部１１７は、演算部１１４で生成した公開鍵及び秘密鍵を記憶する鍵情報記憶領域１１８と、制御部１１２での各種演算に必要な情報を記憶する一時情報記憶領域１１９と、を備える。
【００３２】
以上に記載した鍵生成装置１１０は、例えば、図３（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ（Compact Disk）やＤＶＤ（Digital Versatile Disk）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【００３３】
例えば、入力部１１１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、制御部１１２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１１７は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１２１は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１２２は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００３４】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００３５】
図４は、暗号化装置１３０の概略図である。図示するように、暗号化装置１３０は、情報の入力を受け付ける入力部１３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、暗号化装置１３０の各部の制御を行う制御部１３２と、記憶部１３８と、通信回線１７０を介して鍵生成装置１１０又は復号化装置１５０と通信を行う通信部１４２と、情報を出力する出力部１４３と、を備える。
【００３６】
ここで、制御部１３２は、乱数の生成を行う乱数生成部１３３と、メッセージ文の入力を受け付け、当該メッセージ文の暗号文を生成する処理を制御する演算部１３４と、（π、σ）を入力として、π（σ）を出力する（一方向性置換πの計算を行う）第一関数計算部１３５と、（σ、ｘ）を入力として、ｆσ（ｘ）を出力する第二関数計算部１３６と、を備える。
【００３７】
また、記憶部１３８は、鍵生成装置１１０で生成された公開鍵を記憶する鍵情報記憶領域１３９と、制御部１３２での各種演算に必要な情報を記憶する一時情報記憶領域１４０と、を備える。
【００３８】
以上に記載した暗号化装置１３０は、例えば、図３に示すような一般的なコンピュータ９００で実現できる。
【００３９】
例えば、入力部１３１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、制御部１３２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１３８は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１４２は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１４３は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００４０】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００４１】
図５は、復号化装置１５０の概略図である。図示するように、復号化装置１５０は、情報の入力を受け付ける入力部１５１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、復号化装置１５０の各部の制御を行う制御部１５２と、記憶部１５８と、通信回線１７０を介して鍵生成装置１１０又は暗号化装置１３０と通信を行う通信部１６２と、情報を出力する出力部１６３と、を備える。
【００４２】
ここで、制御部１５２は、暗号文の入力を受け付け、当該暗号文の復号処理を制御する演算部１５３と、関数計算器Ａ３０３は、（π−１、ｙ）を入力として、π（ｙ）を出力する（落とし戸π−１の計算を行う）第一関数計算部１５４と、（σ、ｘ）を入力として、ｆσ（ｘ）を出力する第二関数計算部１５５と、演算部１５３が算出した値の検証を行う検査部１５６と、を備える。
【００４３】
また、記憶部１５８は、鍵生成装置１１０で生成された秘密鍵を記憶する鍵情報記憶領域１５９と、制御部１５２での各種演算に必要な情報を記憶する一時情報記憶領域１６０と、を備える。
【００４４】
以上に記載した復号化装置１５０は、例えば、図３に示すような一般的なコンピュータ９００で実現できる。
【００４５】
例えば、入力部１５１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、制御部１５２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１５８は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１６２は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１６３は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００４６】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００４７】
図６は、暗号システム１００での動作手順を説明するためのシーケンス図である。
【００４８】
１．鍵生成装置１１０での処理。
【００４９】
まず、鍵生成装置１００の演算部１１４は、入力部１１１を介して、１ｋ（ｋはセキュリティパラメータで正の整数）の入力を受け付ける（Ｓ１０）。なお、入力された値は、一時情報記憶領域１１９に記憶される。
【００５０】
次に、鍵生成装置１００の乱数生成部１１３が、
【００５１】
【数６】
【００５２】
および
【００５３】
【数７】
【００５４】
をランダムに作成し、一時情報記憶領域１１９に記録する（Ｓ１１、Ｓ１２）。但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す。
【００５５】
次に、鍵生成装置１００の演算部１１４は、一時情報記憶領域１１９に記憶された（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【００５６】
【数８】
【００５７】
を計算し、一時情報記憶領域１１９に記録する（Ｓ１３）。
【００５８】
さらに、鍵生成装置１００の落とし戸付き一方向性置換生成部１１５が、一方向性置換πと落とし戸π−１の組（π，π−１）を作成し、一時情報記憶領域１１９に記録する（Ｓ１４）。
【００５９】
そして、鍵生成装置１００の演算部１１４が、一時情報記憶領域１１９に記憶された値から公開鍵ｐｋおよび秘密鍵ｓｋを、
【００６０】
【数９】
【００６１】
と設定し、出力部１２２を介して（ｐｋ，ｓｋ）を出力する（Ｓ１５）。但し、Ｆｋは、下記の（１０）式で示され、ｆσは、Ｇ４上の関数である。
【００６２】
【数１０】
【００６３】
なお、公開鍵ｐｋ又は秘密鍵ｓｋについては、通信部１２１を介して，暗号化装置１３０又は復号化装置１５０に送信することも可能である。
【００６４】
２．暗号化装置１３０での処理。
【００６５】
暗号化装置１３０の演算部１３４は、入力部１３１又は通信部１４２を介して取得した公開鍵ｐｋを鍵情報記憶領域１３９に記憶する（Ｓ１６）。
【００６６】
次に、暗号化装置１３０の演算部１３４は、入力部１３１又は通信部１４２を介して、メッセージ文ｍを取得し、一時情報記憶領域１４０に記憶する（Ｓ１７）。
【００６７】
そして、暗号化装置１３０の乱数生成部１３３は、
【００６８】
【数１１】
【００６９】
をランダムに選ぶ（Ｓ１８）。
【００７０】
次に、暗号化装置１３０の演算部１３４は、公開鍵ｐｋ（の一部）であるｇ１、ｇ２から、
【００７１】
【数１２】
【００７２】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ１９）。
【００７３】
次に、暗号化装置１３０の乱数生成部１３３が、
【００７４】
【数１３】
【００７５】
をランダムに選ぶ（Ｓ２０）。
【００７６】
そして、暗号化装置１３０の第一関数計算部１３５が、一方向性関数πを用いて、π(σ)を計算する（Ｓ２１）。
【００７７】
さらに、暗号化装置１３０の演算部１３４が、公開鍵（の一部）ｈ１から、
【００７８】
【数１４】
【００７９】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ２２）。
【００８０】
また、暗号化装置１３０の演算部１３４は、メッセージ文ｍ及び公開鍵（の一部）ｈ２から、
【００８１】
【数１５】
【００８２】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ２３）。
【００８３】
そして、暗号化装置１３０の第二関数計算部１３６が、
【００８４】
【数１６】
【００８５】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ２４）。
【００８６】
さらに、暗号化装置１３０の演算部１３４は、一時情報記憶領域１４０に記憶された各値からＣを、
【００８７】
【数１７】
【００８８】
と設定し、メッセージ文ｍに対する暗号文Ｃとして、出力部１４３から出力する（Ｓ２５）。
【００８９】
なお、暗号文Ｃについては、通信部１４２を介して復号化装置１５０に送信することも可能である。
【００９０】
３．復号化装置１５０での処理。
【００９１】
復号化装置１５０の演算部１５３は、入力部１５１又は通信部１６２を介して取得した秘密鍵ｓｋを鍵情報記憶領域１５９に記憶する（Ｓ２６）。
【００９２】
次に、復号化装置１５０の演算部１５３は、入力部１５１又は通信部１６２を介して、暗号文Ｃを取得し、一時情報記憶領域１６０に記憶する（Ｓ２７）。
【００９３】
次に、復号化装置１５０の演算部１５３及び第一関数計算部１５４は、
【００９４】
【数１８】
【００９５】
を計算し、一時情報記憶領域１６０に記憶する（Ｓ２８）。
【００９６】
さらに、復号化装置１５０の演算部１５３は、
【００９７】
【数１９】
【００９８】
を計算し、一時情報記憶領域１６０に記憶する（Ｓ２９）。
【００９９】
そして、復号化装置１５０の第二関数計算部１５５は、
【０１００】
【数２０】
【０１０１】
を計算する（Ｓ３０）。
【０１０２】
そして、復号化装置１５０の検査部１５６は、ステップＳ３０で計算した値の検査（検証）を行い（Ｓ３１）、もし検査（検証）に成功すれば、ステップＳ２９において、一時情報記憶領域１６０に記憶されたｍを暗号文Ｃに対するメッセージ文として出力部１６３から出力する。一方、検査（検証）に失敗した場合はエラーメッセージを出力部１６３から出力する。
【０１０３】
ここで、本実施形態における公開鍵暗号方法では、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の計算量的困難性及び関数族Ｆｋの条件（Ａ）、（Ｂ）の仮定のもとで、ＩＮＤ−ＣＣＡ安全であることが証明可能である（ＩＮＤ−ＣＣＡ安全の定義については、非特許文献１などに記載されている）。
【０１０４】
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題とは、ランダムに与えられたインスタンス（ｇ，Ｘ，Ｙ，Ｋ）（ここで、ｇ，Ｘ，Ｙ，Ｋ∈Ｇであり、Ｇは素位数をもつ乗法群）に対して、Ｘ＝ｇａ，Ｙ＝ｇｂとしたとき、Ｋ＝ｇａｂか否かを判定する問題である。なお、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性は、Ｅｌｇａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ公開鍵暗号など多くの暗号の安全性の根拠として利用されている。
【０１０５】
また、関数族Ｆｋの条件（Ａ）とは、「σの値をランダムに選んだとき、σの値を知ることなく、任意のｘに対して、ｆσ（ｘ）の値を予測することが困難である。」ことを意味する。
【０１０６】
さらに、関数族Ｆｋの条件（Ｂ）とは、「攻撃者が、π(σ)の値とｆσ’（ｘ）の値を手に入れたとき（πは一方向性置換）、σ’がσと一致するか否かを判定することが困難である。」ことを意味する。
【０１０７】
加えて、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題は、ランダム自己帰着性と呼ばれる性質を持つため、インスタンスが複数与えられた場合の計算量的困難性とひとつ与えられた場合の計算量的困難性は同一である。従って、条件（Ａ’）、（Ｂ’）の性質を持つように、関数族Ｆｋを選ぶとき、本実施形態で述べた公開鍵暗号方法は、マルチユーザ環境においてセキュリティ・リダクションを劣化させないことが証明される。
【０１０８】
そして、関数族Ｆｋの条件（Ａ’）とは、「σ１，・・・，σｎ（ｎは自然数）の値をランダムに選んだとき、これらの値を一切知ることなく、何れのｉ（ｉは、１≦ｉ≦ｎなる自然数）、および、任意のｘに対して、
【０１０９】
【数２１】
【０１１０】
の値を予測することが困難である。」ことを意味する。
【０１１１】
また、関数族Ｆｋの条件（Ｂ’）とは、「攻撃者が、π１(σ１)，・・・，πｎ(σｎ)（ｎは自然数）の値と、
【０１１２】
【数２２】
【０１１３】
の値を手に入れたとき（πｉは一方向性置換）、全てのｉ（ｉは、１≦ｉ≦ｎなる自然数）についても、σ’ｉがσｉと一致するか否かを判定することが困難である。」ことを意味する。
【０１１４】
以上に記載した実施形態では、公開鍵暗号の鍵生成、暗号化、復号化の各手段の実現方法について述べたが、具体的には、公開鍵暗号は、暗号通信をベースとした、電子ショッピングシステム、電子メールシステム、会員用情報配信システム、コンテンツ配信システム、の他、ファイル暗号システムなど様々なシステムに適用される。
【０１１５】
また、実施例における各計算は、ＣＰＵがメモリ内の各プログラムを実行することにより行われる他、いずれかがハードウエア化された演算装置であって、他の演算装置や、ＣＰＵと、データのやりとりを行うものであってもよい。
【０１１６】
さらに、以上に記載した実施形態においては、鍵生成装置１１０、暗号化装置１３０及び復号化装置１５０で暗号システム１００を構成しているが、このような態様に限定されず、鍵生成装置１１０での処理を暗号化装置１３０及び復号化装置１５０の何れか一方で行うことにより、鍵生成装置１１０を不要にすることも可能である。
【符号の説明】
【０１１７】
１００ 暗号システム
１１０ 鍵生成装置
１１１ 入力部
１１２ 制御部
１１７ 記憶部
１２１ 通信部
１２２ 出力部
１３０ 暗号化装置
１３１ 入力部
１３２ 制御部
１３８ 記憶部
１４２ 通信部
１４３ 出力部
１５０ 復号化装置
１５１ 入力部
１５２ 制御部
１５８ 記憶部
１６２ 通信部
１６３ 出力部
【技術分野】
【０００１】
本発明は、メッセージ文を暗号化又は復号化する技術に関する。
【背景技術】
【０００２】
非特許文献１では、公開鍵暗号の安全性の概念が記載されており、ＩＮＤ−ＣＣＡ安全であることが最高レベルの安全性であると考えられている。実際には、公開鍵暗号がＩＮＤ−ＣＣＡ安全であることは、ランダムオラクルモデル、または、標準計算機モデル上で証明が与えられる。
【０００３】
ランダムオラクルモデルは、ランダム関数へのオラクルアクセスを前提としているため非現実のモデルである。よって、ランダムオラクルモデル上の安全性証明は現実システムでの安全性を完全に保証する訳ではなく、ひとつの指標と考えられている。しかし、実用性に優れた多様なバリエーションの公開鍵暗号方法を設計することが容易であり、実用化されている公開鍵暗号の多くはランダムオラクルモデル上でＩＮＤ−ＣＣＡ安全性が与えられている。
【０００４】
一方、標準計算機モデルは、現実の計算機システムに近いため、このモデル上での安全性証明は現実世界での安全性証明に等しいと考えられている。このように、安全性の観点からは、標準計算機モデル上でＩＮＤ−ＣＣＡ安全であることが望ましいが、実用的な方式設計が難しく、ランダムオラクルモデルに比べるとバリエーションが非常に少ない。非特許文献３に記載されている公開鍵暗号方式が、標準計算機モデル上でＩＮＤ−ＣＣＡ安全で、かつ、実用性を備えた方式として代表的なものである。
【０００５】
ところで、非特許文献１に記載されているＩＮＤ−ＣＣＡ安全の概念は、単一の送信者及び受信者に対して、ターゲットとなる暗号文がひとつ与えられた状況において定式化されている（以下、シングルユーザ環境と呼ぶ）。
【０００６】
しかし、現実世界では、同報メール通信など、同一のメッセージ文が複数の相手に対して送られている場合も少なくない。また、メールの返信などでは、同一メッセージ文の全体又は一部を含んだ新たなメッセージ文から暗号文が作成されることも多い。非特許文献２では、このようなマルチユーザ環境において、識別不能性の検証を行っている。
【０００７】
非特許文献２によると、シングルユーザ環境において識別不能性が示されれば、マルチユーザ環境においても識別不能性は示されるが、一般にはセキュリティ・リダクションは大きく劣化することが記載されている。ここで、セキュリティ・リダクションとは、暗号の安全性を計算量的困難性が予想される問題に帰着する際の帰着効率を意味する。セキュリティ・リダクションが悪い場合、暗号の安全性のためのパラメータ（鍵の長さなど）を大きく選ぶ必要性があり、暗号の効率性を大きく損なう場合が多い。
【０００８】
よって、実用上の観点から、計算量的困難性が十分に予想された問題に効率良く帰着するように公開鍵暗号をデザインすることが望ましい。非特許文献２によると、弱い安全性（ＩＮＤ−ＣＰＡ）をもつＥｌｇａｍａｌ暗号はマルチユーザ環境においてもセキュリティ・リダクションを全く損なわないことが示されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among notions of security for public-key encryption schemes: http://www.cse.ucsd.edu/~mihir/crypto-research-papers.html
【非特許文献２】M. Bellare, P. Boldyreva, and S.Micali. Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements: http://www.cse.ucsd.edu/~mihir/crypto-research-papers.html
【非特許文献３】R.Cramer and V.Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack: http://www.shoup.net/papers/
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以上に記載したように、非特許文献３では、標準計算機モデル上でＩＮＤ−ＣＣＡ安全な公開鍵暗号方法が記載されている。
【００１１】
しかしながら、非特許文献３に記載の標準計算機モデル上でＩＮＤ−ＣＣＡ安全な公開鍵暗号方法は部分的にはマルチユーザ環境においてもセキュリティ・リダクションを損なわないが完全ではないことが示されており、標準計算機モデル上で強い安全性（ＩＮＤ−ＣＣＡ）を持つ公開鍵暗号方法で、マルチユーザ環境においてもセキュリティ・リダクションを全く損なわない方法は知られていない。
【００１２】
そこで、本発明は、標準計算機モデル上でＩＮＤ−ＣＣＡ安全であり、また、マルチユーザ環境においてもセキュリティ・リダクションを損なわない公開鍵暗号方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
以上の課題を解決するため、本発明は、暗号の安全性を、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性と、特定の条件を満たす関数族の安全性に帰着するように、公開鍵暗号を設計する。
【００１４】
例えば、本発明は、第一の鍵情報を用いて、メッセージ文を暗号化した暗号文を生成し、第二の鍵情報を用いて、当該暗号文の復号化を行う少なくとも一つ以上のコンピュータを備える暗号システムであって、
前記コンピュータの制御部が、
セキュリティパラメータｋの入力を受け付ける処理と、
【００１５】
【数１】
【００１６】
および
【００１７】
【数２】
【００１８】
をランダムに作成する処理と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【００１９】
【数３】
【００２０】
を計算する処理と、
一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理と、
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【００２１】
【数４】
【００２２】
として生成する処理と、を行うこと、
但し、Ｆｋは、下記の（５）式で示され、ｆσは、Ｇ４上の関数である。
【００２３】
【数５】
【００２４】
を特徴とする。
【発明の効果】
【００２５】
以上のように、本発明によれば、標準計算機モデル上でＩＮＤ−ＣＣＡ安全であり、また、マルチユーザ環境においてもセキュリティ・リダクションを損なわない公開鍵暗号方法を提供することができる。
【図面の簡単な説明】
【００２６】
【図１】暗号システムの概略図。
【図２】鍵生成装置の概略図。
【図３】コンピュータの概略図。
【図４】暗号化装置の概略図。
【図５】復号化装置の概略図。
【図６】暗号システムでの動作手順を説明するためのシーケンス図。
【発明を実施するための形態】
【００２７】
図１は、本発明の一実施形態である暗号システム１００の概略図である。図示するように、暗号システム１００は、鍵生成装置１１０と、暗号化装置１３０と、復号化装置１５０と、を備え、これらは、通信回線１７０を介して、相互に情報の送受信を行うことができるようにされている。
【００２８】
そして、本実施形態では、公開鍵暗号Π＝（Ｋ，Ｅ，Ｄ）において、公開鍵暗号Πの鍵生成手段Ｋ、暗号化手段Ｅ、および、復号化手段Ｄは、それぞれ鍵生成装置１１０、暗号化装置１３０、および、復号化装置１５０により実現される。
【００２９】
図２は、鍵生成装置１１０の概略図である。図示するように、鍵生成装置１１０は、情報の入力を受け付ける入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵生成装置１１０の各部の制御を行う制御部１１２と、記憶部１１７と、通信回線１７０を介して暗号化装置１３０又は復号化装置１５０と通信を行う通信部１２１と、情報を出力する出力部１２２と、を備える。
【００３０】
ここで、制御部１１２は、乱数の生成を行う乱数生成部１１３と、公開鍵及び秘密鍵の生成を行う演算部１１４と、一方向性置換π及び落とし戸π−１を生成する落とし戸付き一方向性置換生成部１１５と、を備える。
【００３１】
また、記憶部１１７は、演算部１１４で生成した公開鍵及び秘密鍵を記憶する鍵情報記憶領域１１８と、制御部１１２での各種演算に必要な情報を記憶する一時情報記憶領域１１９と、を備える。
【００３２】
以上に記載した鍵生成装置１１０は、例えば、図３（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ（Compact Disk）やＤＶＤ（Digital Versatile Disk）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【００３３】
例えば、入力部１１１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、制御部１１２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１１７は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１２１は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１２２は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００３４】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００３５】
図４は、暗号化装置１３０の概略図である。図示するように、暗号化装置１３０は、情報の入力を受け付ける入力部１３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、暗号化装置１３０の各部の制御を行う制御部１３２と、記憶部１３８と、通信回線１７０を介して鍵生成装置１１０又は復号化装置１５０と通信を行う通信部１４２と、情報を出力する出力部１４３と、を備える。
【００３６】
ここで、制御部１３２は、乱数の生成を行う乱数生成部１３３と、メッセージ文の入力を受け付け、当該メッセージ文の暗号文を生成する処理を制御する演算部１３４と、（π、σ）を入力として、π（σ）を出力する（一方向性置換πの計算を行う）第一関数計算部１３５と、（σ、ｘ）を入力として、ｆσ（ｘ）を出力する第二関数計算部１３６と、を備える。
【００３７】
また、記憶部１３８は、鍵生成装置１１０で生成された公開鍵を記憶する鍵情報記憶領域１３９と、制御部１３２での各種演算に必要な情報を記憶する一時情報記憶領域１４０と、を備える。
【００３８】
以上に記載した暗号化装置１３０は、例えば、図３に示すような一般的なコンピュータ９００で実現できる。
【００３９】
例えば、入力部１３１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、制御部１３２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１３８は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１４２は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１４３は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００４０】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００４１】
図５は、復号化装置１５０の概略図である。図示するように、復号化装置１５０は、情報の入力を受け付ける入力部１５１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、復号化装置１５０の各部の制御を行う制御部１５２と、記憶部１５８と、通信回線１７０を介して鍵生成装置１１０又は暗号化装置１３０と通信を行う通信部１６２と、情報を出力する出力部１６３と、を備える。
【００４２】
ここで、制御部１５２は、暗号文の入力を受け付け、当該暗号文の復号処理を制御する演算部１５３と、関数計算器Ａ３０３は、（π−１、ｙ）を入力として、π（ｙ）を出力する（落とし戸π−１の計算を行う）第一関数計算部１５４と、（σ、ｘ）を入力として、ｆσ（ｘ）を出力する第二関数計算部１５５と、演算部１５３が算出した値の検証を行う検査部１５６と、を備える。
【００４３】
また、記憶部１５８は、鍵生成装置１１０で生成された秘密鍵を記憶する鍵情報記憶領域１５９と、制御部１５２での各種演算に必要な情報を記憶する一時情報記憶領域１６０と、を備える。
【００４４】
以上に記載した復号化装置１５０は、例えば、図３に示すような一般的なコンピュータ９００で実現できる。
【００４５】
例えば、入力部１５１は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、制御部１５２は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、記憶部１５８は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、通信部１６２は、ＣＰＵ９０１が通信装置９０８を利用することで実現可能であり、出力部１６３は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【００４６】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【００４７】
図６は、暗号システム１００での動作手順を説明するためのシーケンス図である。
【００４８】
１．鍵生成装置１１０での処理。
【００４９】
まず、鍵生成装置１００の演算部１１４は、入力部１１１を介して、１ｋ（ｋはセキュリティパラメータで正の整数）の入力を受け付ける（Ｓ１０）。なお、入力された値は、一時情報記憶領域１１９に記憶される。
【００５０】
次に、鍵生成装置１００の乱数生成部１１３が、
【００５１】
【数６】
【００５２】
および
【００５３】
【数７】
【００５４】
をランダムに作成し、一時情報記憶領域１１９に記録する（Ｓ１１、Ｓ１２）。但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す。
【００５５】
次に、鍵生成装置１００の演算部１１４は、一時情報記憶領域１１９に記憶された（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【００５６】
【数８】
【００５７】
を計算し、一時情報記憶領域１１９に記録する（Ｓ１３）。
【００５８】
さらに、鍵生成装置１００の落とし戸付き一方向性置換生成部１１５が、一方向性置換πと落とし戸π−１の組（π，π−１）を作成し、一時情報記憶領域１１９に記録する（Ｓ１４）。
【００５９】
そして、鍵生成装置１００の演算部１１４が、一時情報記憶領域１１９に記憶された値から公開鍵ｐｋおよび秘密鍵ｓｋを、
【００６０】
【数９】
【００６１】
と設定し、出力部１２２を介して（ｐｋ，ｓｋ）を出力する（Ｓ１５）。但し、Ｆｋは、下記の（１０）式で示され、ｆσは、Ｇ４上の関数である。
【００６２】
【数１０】
【００６３】
なお、公開鍵ｐｋ又は秘密鍵ｓｋについては、通信部１２１を介して，暗号化装置１３０又は復号化装置１５０に送信することも可能である。
【００６４】
２．暗号化装置１３０での処理。
【００６５】
暗号化装置１３０の演算部１３４は、入力部１３１又は通信部１４２を介して取得した公開鍵ｐｋを鍵情報記憶領域１３９に記憶する（Ｓ１６）。
【００６６】
次に、暗号化装置１３０の演算部１３４は、入力部１３１又は通信部１４２を介して、メッセージ文ｍを取得し、一時情報記憶領域１４０に記憶する（Ｓ１７）。
【００６７】
そして、暗号化装置１３０の乱数生成部１３３は、
【００６８】
【数１１】
【００６９】
をランダムに選ぶ（Ｓ１８）。
【００７０】
次に、暗号化装置１３０の演算部１３４は、公開鍵ｐｋ（の一部）であるｇ１、ｇ２から、
【００７１】
【数１２】
【００７２】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ１９）。
【００７３】
次に、暗号化装置１３０の乱数生成部１３３が、
【００７４】
【数１３】
【００７５】
をランダムに選ぶ（Ｓ２０）。
【００７６】
そして、暗号化装置１３０の第一関数計算部１３５が、一方向性関数πを用いて、π(σ)を計算する（Ｓ２１）。
【００７７】
さらに、暗号化装置１３０の演算部１３４が、公開鍵（の一部）ｈ１から、
【００７８】
【数１４】
【００７９】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ２２）。
【００８０】
また、暗号化装置１３０の演算部１３４は、メッセージ文ｍ及び公開鍵（の一部）ｈ２から、
【００８１】
【数１５】
【００８２】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ２３）。
【００８３】
そして、暗号化装置１３０の第二関数計算部１３６が、
【００８４】
【数１６】
【００８５】
を計算し、一時情報記憶領域１４０に記憶する（Ｓ２４）。
【００８６】
さらに、暗号化装置１３０の演算部１３４は、一時情報記憶領域１４０に記憶された各値からＣを、
【００８７】
【数１７】
【００８８】
と設定し、メッセージ文ｍに対する暗号文Ｃとして、出力部１４３から出力する（Ｓ２５）。
【００８９】
なお、暗号文Ｃについては、通信部１４２を介して復号化装置１５０に送信することも可能である。
【００９０】
３．復号化装置１５０での処理。
【００９１】
復号化装置１５０の演算部１５３は、入力部１５１又は通信部１６２を介して取得した秘密鍵ｓｋを鍵情報記憶領域１５９に記憶する（Ｓ２６）。
【００９２】
次に、復号化装置１５０の演算部１５３は、入力部１５１又は通信部１６２を介して、暗号文Ｃを取得し、一時情報記憶領域１６０に記憶する（Ｓ２７）。
【００９３】
次に、復号化装置１５０の演算部１５３及び第一関数計算部１５４は、
【００９４】
【数１８】
【００９５】
を計算し、一時情報記憶領域１６０に記憶する（Ｓ２８）。
【００９６】
さらに、復号化装置１５０の演算部１５３は、
【００９７】
【数１９】
【００９８】
を計算し、一時情報記憶領域１６０に記憶する（Ｓ２９）。
【００９９】
そして、復号化装置１５０の第二関数計算部１５５は、
【０１００】
【数２０】
【０１０１】
を計算する（Ｓ３０）。
【０１０２】
そして、復号化装置１５０の検査部１５６は、ステップＳ３０で計算した値の検査（検証）を行い（Ｓ３１）、もし検査（検証）に成功すれば、ステップＳ２９において、一時情報記憶領域１６０に記憶されたｍを暗号文Ｃに対するメッセージ文として出力部１６３から出力する。一方、検査（検証）に失敗した場合はエラーメッセージを出力部１６３から出力する。
【０１０３】
ここで、本実施形態における公開鍵暗号方法では、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の計算量的困難性及び関数族Ｆｋの条件（Ａ）、（Ｂ）の仮定のもとで、ＩＮＤ−ＣＣＡ安全であることが証明可能である（ＩＮＤ−ＣＣＡ安全の定義については、非特許文献１などに記載されている）。
【０１０４】
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題とは、ランダムに与えられたインスタンス（ｇ，Ｘ，Ｙ，Ｋ）（ここで、ｇ，Ｘ，Ｙ，Ｋ∈Ｇであり、Ｇは素位数をもつ乗法群）に対して、Ｘ＝ｇａ，Ｙ＝ｇｂとしたとき、Ｋ＝ｇａｂか否かを判定する問題である。なお、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性は、Ｅｌｇａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ公開鍵暗号など多くの暗号の安全性の根拠として利用されている。
【０１０５】
また、関数族Ｆｋの条件（Ａ）とは、「σの値をランダムに選んだとき、σの値を知ることなく、任意のｘに対して、ｆσ（ｘ）の値を予測することが困難である。」ことを意味する。
【０１０６】
さらに、関数族Ｆｋの条件（Ｂ）とは、「攻撃者が、π(σ)の値とｆσ’（ｘ）の値を手に入れたとき（πは一方向性置換）、σ’がσと一致するか否かを判定することが困難である。」ことを意味する。
【０１０７】
加えて、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題は、ランダム自己帰着性と呼ばれる性質を持つため、インスタンスが複数与えられた場合の計算量的困難性とひとつ与えられた場合の計算量的困難性は同一である。従って、条件（Ａ’）、（Ｂ’）の性質を持つように、関数族Ｆｋを選ぶとき、本実施形態で述べた公開鍵暗号方法は、マルチユーザ環境においてセキュリティ・リダクションを劣化させないことが証明される。
【０１０８】
そして、関数族Ｆｋの条件（Ａ’）とは、「σ１，・・・，σｎ（ｎは自然数）の値をランダムに選んだとき、これらの値を一切知ることなく、何れのｉ（ｉは、１≦ｉ≦ｎなる自然数）、および、任意のｘに対して、
【０１０９】
【数２１】
【０１１０】
の値を予測することが困難である。」ことを意味する。
【０１１１】
また、関数族Ｆｋの条件（Ｂ’）とは、「攻撃者が、π１(σ１)，・・・，πｎ(σｎ)（ｎは自然数）の値と、
【０１１２】
【数２２】
【０１１３】
の値を手に入れたとき（πｉは一方向性置換）、全てのｉ（ｉは、１≦ｉ≦ｎなる自然数）についても、σ’ｉがσｉと一致するか否かを判定することが困難である。」ことを意味する。
【０１１４】
以上に記載した実施形態では、公開鍵暗号の鍵生成、暗号化、復号化の各手段の実現方法について述べたが、具体的には、公開鍵暗号は、暗号通信をベースとした、電子ショッピングシステム、電子メールシステム、会員用情報配信システム、コンテンツ配信システム、の他、ファイル暗号システムなど様々なシステムに適用される。
【０１１５】
また、実施例における各計算は、ＣＰＵがメモリ内の各プログラムを実行することにより行われる他、いずれかがハードウエア化された演算装置であって、他の演算装置や、ＣＰＵと、データのやりとりを行うものであってもよい。
【０１１６】
さらに、以上に記載した実施形態においては、鍵生成装置１１０、暗号化装置１３０及び復号化装置１５０で暗号システム１００を構成しているが、このような態様に限定されず、鍵生成装置１１０での処理を暗号化装置１３０及び復号化装置１５０の何れか一方で行うことにより、鍵生成装置１１０を不要にすることも可能である。
【符号の説明】
【０１１７】
１００ 暗号システム
１１０ 鍵生成装置
１１１ 入力部
１１２ 制御部
１１７ 記憶部
１２１ 通信部
１２２ 出力部
１３０ 暗号化装置
１３１ 入力部
１３２ 制御部
１３８ 記憶部
１４２ 通信部
１４３ 出力部
１５０ 復号化装置
１５１ 入力部
１５２ 制御部
１５８ 記憶部
１６２ 通信部
１６３ 出力部
【特許請求の範囲】
【請求項１】
第一の鍵情報を用いて、メッセージ文を暗号化した暗号文を生成し、第二の鍵情報を用いて、当該暗号文の復号化を行う少なくとも一つ以上のコンピュータを備える暗号システムであって、
前記コンピュータの制御部が、
セキュリティパラメータｋの入力を受け付ける処理と、
【数１】
および
【数２】
をランダムに作成する処理と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【数３】
を計算する処理と、
一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理と、
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【数４】
として生成する処理と、を行うこと、
但し、Ｆｋは、下記の（５）式で示され、ｆσは、Ｇ４上の関数である。
【数５】
を特徴とする暗号システム。
【請求項２】
請求項１に記載の暗号システムであって、
前記コンピュータの制御部が、
メッセージ文ｍの入力を受け付ける処理と、
【数６】
をランダムに選ぶ処理と、
第一の鍵情報ｐｋから、
【数７】
を計算する処理と、
【数８】
をランダムに選ぶ処理と、
一方向性関数πを用いて、π(σ)を計算する処理と、
第一の鍵情報ｐｋから、
【数９】
を計算する処理と、
メッセージ文ｍ及び第一の鍵情報ｐｋから、
【数１０】
を計算する処理と、
【数１１】
を計算する処理と、
暗号文Ｃを、
【数１２】
として生成する処理と、を行うこと、
を特徴とする暗号システム。
【請求項３】
請求項２に記載の暗号システムであって、
前記コンピュータの制御部が、
前記暗号文Ｃの入力を受け付ける処理と、
落とし戸π−１を用いて、
【数１３】
を計算する処理と、
【数１４】
を計算する処理と、
【数１５】
が成立するか否かを検査し、成立する場合には、算出したｍを暗号文Ｃに対するメッセージ文とする処理と、を行うこと、
を特徴とする暗号システム。
【請求項４】
請求項１〜３の何れか一項に記載の暗号システムであって、
前記関数Ｆｋは、
σの値をランダムに選んだとき、σの値を知ることなく、任意のｘに対して、ｆσ（ｘ）の値を予測することが困難であるという第一の条件と、
攻撃者が、π(σ)の値とｆσ’（ｘ）の値を手に入れたとき（πは一方向性置換）、σ’がσと一致するか否かを判定することが困難であるという第二の条件と、
を満たすものであること、
を特徴とする暗号システム。
【請求項５】
請求項１〜３の何れか一項に記載の暗号システムであって、
前記関数Ｆｋは、
σ１，・・・，σｎ（ｎは自然数）の値をランダムに選んだとき、これらの値を一切知ることなく、何れのｉ（ｉは、１≦ｉ≦ｎなる自然数）、および、任意のｘに対して、
【数１６】
の値を予測することが困難であるという第三の条件と、
攻撃者が、π１(σ１)，・・・，πｎ(σｎ)（ｎは自然数）の値と、
【数１７】
の値を手に入れたとき（πｉは一方向性置換）、全てのｉ（ｉは、１≦ｉ≦ｎなる自然数）についても、σ’ｉがσｉと一致するか否かを判定することが困難であるという第四の条件と、
を満たすものであること、
を特徴とする暗号システム。
【請求項６】
メッセージ文を暗号化する第一の鍵情報と、当該第一の鍵情報で暗号化された暗号文の復号化する第二の鍵情報と、を生成する鍵生成装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
【数１８】
および
【数１９】
をランダムに作成する処理と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【数２０】
を計算する処理と、
一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理と、
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【数２１】
として生成する処理と、を行う制御部を有すること、
但し、Ｆｋは、下記の（２２）式で示され、ｆσは、Ｇ４上の関数である。
【数２２】
を特徴とする鍵生成装置。
【請求項７】
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋが、
【数２３】
但し、
【数２４】
【数２５】
（Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）
【数２６】
πは一方向性置換、π−１はπの落とし戸
Ｆｋは、下記の（２７）式で示され、ｆσは、Ｇ４上の関数である。
【数２７】
として定義される第一の鍵情報ｐｋを用いて、メッセージ文を暗号化した暗号文を生成する暗号化装置であって、
メッセージ文ｍの入力を受け付ける処理と、
【数２８】
をランダムに選ぶ処理と、
第一の鍵情報ｐｋから、
【数２９】
を計算する処理と、
【数３０】
をランダムに選ぶ処理と、
一方向性関数πを用いて、π(σ)を計算する処理と、
第一の鍵情報ｐｋから、
【数３１】
を計算する処理と、
メッセージ文ｍ及び第一の鍵情報ｐｋから、
【数３２】
を計算する処理と、
【数３３】
を計算する処理と、
暗号文Ｃを、
【数３４】
として生成する処理と、を行う制御部を備えること、
を特徴とする暗号化装置。
【請求項８】
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋが、
【数３５】
但し、
【数３６】
【数３７】
（Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）
【数３８】
πは一方向性置換、π−１はπの落とし戸
Ｆｋは、下記の（３９）式で示され、ｆσは、Ｇ４上の関数である。
【数３９】
として定義される第一の鍵情報ｐｋを用いて、メッセージ文を暗号化した暗号文Ｃを復号する復号化装置であって、
前記暗号文Ｃの入力を受け付ける処理と、
落とし戸π−１を用いて、
【数４０】
を計算する処理と、
【数４１】
を計算する処理と、
【数４２】
が成立するか否かを検査し、成立する場合には、算出したｍを暗号文Ｃに対するメッセージ文とする処理と、を行う制御部を備えること、
を特徴とする復号化装置。
【請求項９】
第一の鍵情報を用いて、メッセージ文を暗号化した暗号文を生成し、第二の鍵情報を用いて、当該暗号文の復号化を行う少なくとも一つ以上のコンピュータを有する暗号システムが行う暗号処理方法であって、
前記コンピュータの制御部が、セキュリティパラメータｋの入力を受け付ける処理を行う過程と、
前記コンピュータの制御部が、
【数４３】
および
【数４４】
をランダムに作成する処理を行う過程と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
前記コンピュータの制御部が、（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【数４５】
を計算する処理を行う過程と、
前記コンピュータの制御部が、一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理を行う過程と、
前記コンピュータの制御部が、第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【数４６】
として生成する処理を行う過程と、を有すること、
但し、Ｆｋは、下記の（４７）式で示され、ｆσは、Ｇ４上の関数である。
【数４７】
を特徴とする暗号処理方法。
【請求項１０】
請求項９に記載の暗号処理方法であって、
前記コンピュータの制御部が、メッセージ文ｍの入力を受け付ける処理を行う過程と、
前記コンピュータの制御部が、
【数４８】
をランダムに選ぶ処理を行う過程と、
前記コンピュータの制御部が、第一の鍵情報ｐｋから、
【数４９】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５０】
をランダムに選ぶ処理を行う過程と、
前記コンピュータの制御部が、一方向性関数πを用いて、π(σ)を計算する処理を行う過程と、
前記コンピュータの制御部が、第一の鍵情報ｐｋから、
【数５１】
を計算する処理を行う過程と、
前記コンピュータの制御部が、メッセージ文ｍ及び第一の鍵情報ｐｋから、
【数５２】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５３】
を計算する処理を行う過程と、
前記コンピュータの制御部が、暗号文Ｃを、
【数５４】
として生成する処理を行う過程と、を有すること、
を特徴とする暗号処理方法。
【請求項１１】
請求項１０に記載の暗号処理方法であって、
前記コンピュータの制御部が、前記暗号文Ｃの入力を受け付ける処理を行う過程と、
前記コンピュータの制御部が、落とし戸π−１を用いて、
【数５５】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５６】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５７】
が成立するか否かを検査し、成立する場合には、算出したｍを暗号文Ｃに対するメッセージ文とする処理を行う過程と、を有すること、
を特徴とする暗号処理方法。
【請求項１２】
請求項９〜１１の何れか一項に記載の暗号処理方法であって、
前記関数Ｆｋは、
σの値をランダムに選んだとき、σの値を知ることなく、任意のｘに対して、ｆσ（ｘ）の値を予測することが困難であるという第一の条件と、
攻撃者が、π(σ)の値とｆσ’（ｘ）の値を手に入れたとき（πは一方向性置換）、σ’がσと一致するか否かを判定することが困難であるという第二の条件と、
を満たすものであること、
を特徴とする暗号処理方法。
【請求項１３】
請求項９〜１１の何れか一項に記載の暗号処理方法であって、
前記関数Ｆｋは、
σ１，・・・，σｎ（ｎは自然数）の値をランダムに選んだとき、これらの値を一切知ることなく、何れのｉ（ｉは、１≦ｉ≦ｎなる自然数）、および、任意のｘに対して、
【数５８】
の値を予測することが困難であるという第三の条件と、
攻撃者が、π１(σ１)，・・・，πｎ(σｎ)（ｎは自然数）の値と、
【数５９】
の値を手に入れたとき（πｉは一方向性置換）、全てのｉ（ｉは、１≦ｉ≦ｎなる自然数）についても、σ’ｉがσｉと一致するか否かを判定することが困難であるという第四の条件と、
を満たすものであること、
を特徴とする暗号処理方法。
【請求項１】
第一の鍵情報を用いて、メッセージ文を暗号化した暗号文を生成し、第二の鍵情報を用いて、当該暗号文の復号化を行う少なくとも一つ以上のコンピュータを備える暗号システムであって、
前記コンピュータの制御部が、
セキュリティパラメータｋの入力を受け付ける処理と、
【数１】
および
【数２】
をランダムに作成する処理と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【数３】
を計算する処理と、
一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理と、
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【数４】
として生成する処理と、を行うこと、
但し、Ｆｋは、下記の（５）式で示され、ｆσは、Ｇ４上の関数である。
【数５】
を特徴とする暗号システム。
【請求項２】
請求項１に記載の暗号システムであって、
前記コンピュータの制御部が、
メッセージ文ｍの入力を受け付ける処理と、
【数６】
をランダムに選ぶ処理と、
第一の鍵情報ｐｋから、
【数７】
を計算する処理と、
【数８】
をランダムに選ぶ処理と、
一方向性関数πを用いて、π(σ)を計算する処理と、
第一の鍵情報ｐｋから、
【数９】
を計算する処理と、
メッセージ文ｍ及び第一の鍵情報ｐｋから、
【数１０】
を計算する処理と、
【数１１】
を計算する処理と、
暗号文Ｃを、
【数１２】
として生成する処理と、を行うこと、
を特徴とする暗号システム。
【請求項３】
請求項２に記載の暗号システムであって、
前記コンピュータの制御部が、
前記暗号文Ｃの入力を受け付ける処理と、
落とし戸π−１を用いて、
【数１３】
を計算する処理と、
【数１４】
を計算する処理と、
【数１５】
が成立するか否かを検査し、成立する場合には、算出したｍを暗号文Ｃに対するメッセージ文とする処理と、を行うこと、
を特徴とする暗号システム。
【請求項４】
請求項１〜３の何れか一項に記載の暗号システムであって、
前記関数Ｆｋは、
σの値をランダムに選んだとき、σの値を知ることなく、任意のｘに対して、ｆσ（ｘ）の値を予測することが困難であるという第一の条件と、
攻撃者が、π(σ)の値とｆσ’（ｘ）の値を手に入れたとき（πは一方向性置換）、σ’がσと一致するか否かを判定することが困難であるという第二の条件と、
を満たすものであること、
を特徴とする暗号システム。
【請求項５】
請求項１〜３の何れか一項に記載の暗号システムであって、
前記関数Ｆｋは、
σ１，・・・，σｎ（ｎは自然数）の値をランダムに選んだとき、これらの値を一切知ることなく、何れのｉ（ｉは、１≦ｉ≦ｎなる自然数）、および、任意のｘに対して、
【数１６】
の値を予測することが困難であるという第三の条件と、
攻撃者が、π１(σ１)，・・・，πｎ(σｎ)（ｎは自然数）の値と、
【数１７】
の値を手に入れたとき（πｉは一方向性置換）、全てのｉ（ｉは、１≦ｉ≦ｎなる自然数）についても、σ’ｉがσｉと一致するか否かを判定することが困難であるという第四の条件と、
を満たすものであること、
を特徴とする暗号システム。
【請求項６】
メッセージ文を暗号化する第一の鍵情報と、当該第一の鍵情報で暗号化された暗号文の復号化する第二の鍵情報と、を生成する鍵生成装置であって、
セキュリティパラメータｋの入力を受け付ける処理と、
【数１８】
および
【数１９】
をランダムに作成する処理と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【数２０】
を計算する処理と、
一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理と、
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【数２１】
として生成する処理と、を行う制御部を有すること、
但し、Ｆｋは、下記の（２２）式で示され、ｆσは、Ｇ４上の関数である。
【数２２】
を特徴とする鍵生成装置。
【請求項７】
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋが、
【数２３】
但し、
【数２４】
【数２５】
（Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）
【数２６】
πは一方向性置換、π−１はπの落とし戸
Ｆｋは、下記の（２７）式で示され、ｆσは、Ｇ４上の関数である。
【数２７】
として定義される第一の鍵情報ｐｋを用いて、メッセージ文を暗号化した暗号文を生成する暗号化装置であって、
メッセージ文ｍの入力を受け付ける処理と、
【数２８】
をランダムに選ぶ処理と、
第一の鍵情報ｐｋから、
【数２９】
を計算する処理と、
【数３０】
をランダムに選ぶ処理と、
一方向性関数πを用いて、π(σ)を計算する処理と、
第一の鍵情報ｐｋから、
【数３１】
を計算する処理と、
メッセージ文ｍ及び第一の鍵情報ｐｋから、
【数３２】
を計算する処理と、
【数３３】
を計算する処理と、
暗号文Ｃを、
【数３４】
として生成する処理と、を行う制御部を備えること、
を特徴とする暗号化装置。
【請求項８】
第一の鍵情報ｐｋおよび第二の鍵情報ｓｋが、
【数３５】
但し、
【数３６】
【数３７】
（Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）
【数３８】
πは一方向性置換、π−１はπの落とし戸
Ｆｋは、下記の（３９）式で示され、ｆσは、Ｇ４上の関数である。
【数３９】
として定義される第一の鍵情報ｐｋを用いて、メッセージ文を暗号化した暗号文Ｃを復号する復号化装置であって、
前記暗号文Ｃの入力を受け付ける処理と、
落とし戸π−１を用いて、
【数４０】
を計算する処理と、
【数４１】
を計算する処理と、
【数４２】
が成立するか否かを検査し、成立する場合には、算出したｍを暗号文Ｃに対するメッセージ文とする処理と、を行う制御部を備えること、
を特徴とする復号化装置。
【請求項９】
第一の鍵情報を用いて、メッセージ文を暗号化した暗号文を生成し、第二の鍵情報を用いて、当該暗号文の復号化を行う少なくとも一つ以上のコンピュータを有する暗号システムが行う暗号処理方法であって、
前記コンピュータの制御部が、セキュリティパラメータｋの入力を受け付ける処理を行う過程と、
前記コンピュータの制御部が、
【数４３】
および
【数４４】
をランダムに作成する処理を行う過程と（但し、Ｇは素数ｑを位数とする乗法群であり、Ｚｑはｑを法とする剰余環を表す）、
前記コンピュータの制御部が、（ｘ１，ｘ２，ｙ１，ｙ２，ｇ１，ｇ２）を用いて、
【数４５】
を計算する処理を行う過程と、
前記コンピュータの制御部が、一方向性置換πと落とし戸π−１の組（π，π−１）を作成する処理を行う過程と、
前記コンピュータの制御部が、第一の鍵情報ｐｋおよび第二の鍵情報ｓｋを、
【数４６】
として生成する処理を行う過程と、を有すること、
但し、Ｆｋは、下記の（４７）式で示され、ｆσは、Ｇ４上の関数である。
【数４７】
を特徴とする暗号処理方法。
【請求項１０】
請求項９に記載の暗号処理方法であって、
前記コンピュータの制御部が、メッセージ文ｍの入力を受け付ける処理を行う過程と、
前記コンピュータの制御部が、
【数４８】
をランダムに選ぶ処理を行う過程と、
前記コンピュータの制御部が、第一の鍵情報ｐｋから、
【数４９】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５０】
をランダムに選ぶ処理を行う過程と、
前記コンピュータの制御部が、一方向性関数πを用いて、π(σ)を計算する処理を行う過程と、
前記コンピュータの制御部が、第一の鍵情報ｐｋから、
【数５１】
を計算する処理を行う過程と、
前記コンピュータの制御部が、メッセージ文ｍ及び第一の鍵情報ｐｋから、
【数５２】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５３】
を計算する処理を行う過程と、
前記コンピュータの制御部が、暗号文Ｃを、
【数５４】
として生成する処理を行う過程と、を有すること、
を特徴とする暗号処理方法。
【請求項１１】
請求項１０に記載の暗号処理方法であって、
前記コンピュータの制御部が、前記暗号文Ｃの入力を受け付ける処理を行う過程と、
前記コンピュータの制御部が、落とし戸π−１を用いて、
【数５５】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５６】
を計算する処理を行う過程と、
前記コンピュータの制御部が、
【数５７】
が成立するか否かを検査し、成立する場合には、算出したｍを暗号文Ｃに対するメッセージ文とする処理を行う過程と、を有すること、
を特徴とする暗号処理方法。
【請求項１２】
請求項９〜１１の何れか一項に記載の暗号処理方法であって、
前記関数Ｆｋは、
σの値をランダムに選んだとき、σの値を知ることなく、任意のｘに対して、ｆσ（ｘ）の値を予測することが困難であるという第一の条件と、
攻撃者が、π(σ)の値とｆσ’（ｘ）の値を手に入れたとき（πは一方向性置換）、σ’がσと一致するか否かを判定することが困難であるという第二の条件と、
を満たすものであること、
を特徴とする暗号処理方法。
【請求項１３】
請求項９〜１１の何れか一項に記載の暗号処理方法であって、
前記関数Ｆｋは、
σ１，・・・，σｎ（ｎは自然数）の値をランダムに選んだとき、これらの値を一切知ることなく、何れのｉ（ｉは、１≦ｉ≦ｎなる自然数）、および、任意のｘに対して、
【数５８】
の値を予測することが困難であるという第三の条件と、
攻撃者が、π１(σ１)，・・・，πｎ(σｎ)（ｎは自然数）の値と、
【数５９】
の値を手に入れたとき（πｉは一方向性置換）、全てのｉ（ｉは、１≦ｉ≦ｎなる自然数）についても、σ’ｉがσｉと一致するか否かを判定することが困難であるという第四の条件と、
を満たすものであること、
を特徴とする暗号処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−２４５６８３（Ｐ２０１０−２４５６８３Ａ）
【公開日】平成２２年１０月２８日（２０１０．１０．２８）
【国際特許分類】
【出願番号】特願２００９−９０１０２（Ｐ２００９−９０１０２）
【出願日】平成２１年４月２日（２００９．４．２）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２２年１０月２８日（２０１０．１０．２８）
【国際特許分類】
【出願日】平成２１年４月２日（２００９．４．２）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]