(57)【要約】【課題】RKA-KDM-CCA安全な公開鍵暗号方式を実現する暗号通信システムを提供する。【解決手段】パラメータ装置と鍵生成装置と暗号化装置と復号装置を含む暗号通信システムであって、パラメータ装置は条件パラメータと共通パラメータとを出力する。鍵生成装置は、共通パラメータを入力とし、秘密鍵と公開鍵とを出力する。暗号化装置は、共通パラメータと公開鍵とメッセージを入力とし、暗号文を出力する。復号装置は、共通パラメータと改竄秘密鍵と暗号文とを入力とし、リジェクトシンボルまたはメッセージを出力する。【選択図】図５
2015126332.tif 000002
【特許請求の範囲】
【請求項１】
パラメータ装置と、鍵生成装置と、暗号化装置と、復号装置を含む暗号通信システムであって、
前記パラメータ装置は、
合成数の長さ、メッセージの数、フィルタ用素数の長さを示す条件パラメータを設定する条件パラメータ設定部と、
セキュリティパラメータを入力とし、第１、第２のブラム素数とＲＳＡモジュラスの合成数を生成するＲＳＡモジュラス生成部と、
前記合成数の３乗未満であって、前記合成数の３乗と互いに素な数のみの集合のうち、所定の位数の部分群である乱数用部分群において、第１、第２ランダム生成元を設定するランダム生成元設定部と、
前記セキュリティパラメータを入力とし、フィルタ鍵とトラップドアを生成するパラメータ生成部とを含み、
前記鍵生成装置は、
平文空間から、第１、第２、第３、第４秘密鍵パラメータをランダムに選択する秘密鍵パラメータ選択部と、
前記第１、第２ランダム生成元と、前記第１、第２、第３、第４秘密鍵パラメータに基づいて第１、第２公開鍵パラメータを計算する公開鍵パラメータ計算部と、
前記第１、第２公開鍵パラメータから公開鍵を生成する公開鍵生成部と、
前記第１、第２、第３、第４秘密鍵パラメータから秘密鍵を生成する秘密鍵生成部とを含み、
前記暗号化装置は、
前記合成数の４分の１未満の数の集合から第１、第２乱数をランダムに選択する乱数選択部と、
前記セキュリティパラメータを入力とし、使い捨て署名用の鍵ペアである検証鍵と署名鍵を生成する署名鍵生成部と、
共通鍵暗号用のランダムな鍵である共通鍵をランダムに選択する共通鍵選択部と、
タグがコアタグと補助タグからなるものとし、前記検証鍵を前記補助タグとし、前記コアタグをタグ空間からランダムに選択するタグ設定部と、
前記第１乱数と前記第１、第２ランダム生成元に基づいて第１中間暗号文のペアを計算する第１中間暗号文計算部と、
前記第２乱数と前記第１、第２ランダム生成元に基づいて第２中間暗号文のペアを計算する第２中間暗号文計算部と、
前記第１、第２公開鍵パラメータと前記検証鍵と前記第１乱数と前記合成数に基づいてチェック用暗号文を計算するチェック用暗号文計算部と、
前記第１、第２公開鍵パラメータと前記検証鍵と前記第１、第２乱数と前記合成数と前記共通鍵とメッセージに基づいてマスク済暗号文を計算するマスク済暗号文計算部と、
フィルタ入力用に変換した前記メッセージの損失的代数フィルタのフィルタ値を前記共通鍵で暗号化して共通鍵暗号文を生成する共通鍵暗号化部と、
前記署名鍵を用いて、前記公開鍵と前記第１、第２中間暗号文のペアと前記チェック用暗号文と前記マスク済暗号文と前記共通鍵暗号文と前記コアタグの使い捨て署名を生成する署名部と、
前記第１、第２中間暗号文のペアと前記チェック用暗号文と前記マスク済暗号文と前記共通鍵暗号文と前記コアタグと前記検証鍵と前記使い捨て署名を含む暗号文を生成する暗号文生成部とを含み、
前記復号装置は、
前記第１、第２ランダム生成元と、改竄された可能性があるパラメータである第１、第２、第３、第４改竄秘密鍵パラメータに基づいて第１、第２改竄公開鍵パラメータを計算し、改竄公開鍵を計算する改竄公開鍵計算部と、
前記改竄公開鍵と前記第１、第２中間暗号文のペアと前記チェック用暗号文と前記マスク済暗号文と前記共通鍵暗号文と前記コアタグとからなるメッセージを前記検証鍵、前記使い捨て署名を用いて検証し検証結果を出力する検証部と、
前記検証結果を確認して、前記検証結果が検証成功である場合に検証結果を出力し、検証失敗である場合にリジェクトシンボルを出力し処理を停止する検証結果確認部と、
前記チェック用暗号文が、前記第１中間暗号文のペアと前記第１、第２、第３、第４改竄秘密鍵パラメータと前記検証鍵と前記合成数を用いて計算される真値であることを確認し、前記真値であればチェック用暗号文を出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止するチェック用暗号文確認部と、
前記第１、第２中間暗号文のペアと前記第１、第２、第３、第４改竄秘密鍵パラメータと前記検証鍵からマスク鍵を計算するマスク鍵計算部と、
前記マスク鍵を用いて前記マスク済暗号文を復号してマスク復号結果を取得し、前記合成数の３乗未満であって、前記合成数の３乗と互いに素な数のみの集合のうち、前記合成数の２乗を位数とする部分群である平文用部分群に前記マスク復号結果が属するか否かを確認し、属する場合には前記マスク復号結果を出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止するマスク復号結果確認部と、
前記マスク復号結果に対数計算を実行して変換済平文を計算し、前記メッセージを取得する変換済平文計算部と、
前記メッセージが前記平文空間に属するか否かを確認し、属する場合には前記メッセージを出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止するメッセージ確認部と、
前記検証鍵を前記補助タグとして、前記補助タグと前記コアタグから前記タグを生成するタグ生成部と、
前記共通鍵を用いて前記共通鍵暗号文を復号し復号結果を出力する共通鍵復号部と、
前記復号結果が前記フィルタ値と等しいか否かを確認し、等しければ前記メッセージを出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止する復号結果確認部と、
前記復号装置の各部の動作時に前記リジェクトシンボルが出力されなかった場合、前記メッセージを出力するメッセージ出力部を含む。
【請求項２】
請求項１に記載の暗号通信システムであって、
前記鍵生成装置と、前記復号装置とが単一の装置内に含まれる
暗号通信システム。
【請求項３】
パラメータ装置と、鍵生成装置と、暗号化装置と、復号装置が実行する暗号通信方法であって、
前記パラメータ装置は、
合成数の長さ、メッセージの数、フィルタ用素数の長さを示す条件パラメータを設定する条件パラメータ設定ステップと、
セキュリティパラメータを入力とし、第１、第２のブラム素数とＲＳＡモジュラスの合成数を生成するＲＳＡモジュラス生成ステップと、
前記合成数の３乗未満であって、前記合成数の３乗と互いに素な数のみの集合のうち、所定の位数の部分群である乱数用部分群において、第１、第２ランダム生成元を設定するランダム生成元設定ステップと、
前記セキュリティパラメータを入力とし、フィルタ鍵とトラップドアを生成するパラメータ生成ステップとを実行し、
前記鍵生成装置は、
平文空間から、第１、第２、第３、第４秘密鍵パラメータをランダムに選択する秘密鍵パラメータ選択ステップと、
前記第１、第２ランダム生成元と、前記第１、第２、第３、第４秘密鍵パラメータに基づいて第１、第２公開鍵パラメータを計算する公開鍵パラメータ計算ステップと、
前記第１、第２公開鍵パラメータから公開鍵を生成する公開鍵生成ステップと、
前記第１、第２、第３、第４秘密鍵パラメータから秘密鍵を生成する秘密鍵生成ステップとを実行し、
前記暗号化装置は、
前記合成数の４分の１未満の数の集合から第１、第２乱数をランダムに選択する乱数選択ステップと、
前記セキュリティパラメータを入力とし、使い捨て署名用の鍵ペアである検証鍵と署名鍵を生成する署名鍵生成ステップと、
共通鍵暗号用のランダムな鍵である共通鍵をランダムに選択する共通鍵選択ステップと、
タグがコアタグと補助タグからなるものとし、前記検証鍵を前記補助タグとし、前記コアタグをタグ空間からランダムに選択するタグ設定ステップと、
前記第１乱数と前記第１、第２ランダム生成元に基づいて第１中間暗号文のペアを計算する第１中間暗号文計算ステップと、
前記第２乱数と前記第１、第２ランダム生成元に基づいて第２中間暗号文のペアを計算する第２中間暗号文計算ステップと、
前記第１、第２公開鍵パラメータと前記検証鍵と前記第１乱数と前記合成数に基づいてチェック用暗号文を計算するチェック用暗号文計算ステップと、
前記第１、第２公開鍵パラメータと前記検証鍵と前記第１、第２乱数と前記合成数と前記共通鍵とメッセージに基づいてマスク済暗号文を計算するマスク済暗号文計算ステップと、
フィルタ入力用に変換した前記メッセージの損失的代数フィルタのフィルタ値を前記共通鍵で暗号化して共通鍵暗号文を生成する共通鍵暗号化ステップと、
前記署名鍵を用いて、前記公開鍵と前記第１、第２中間暗号文のペアと前記チェック用暗号文と前記マスク済暗号文と前記共通鍵暗号文と前記コアタグの使い捨て署名を生成する署名ステップと、
前記第１、第２中間暗号文のペアと前記チェック用暗号文と前記マスク済暗号文と前記共通鍵暗号文と前記コアタグと前記検証鍵と前記使い捨て署名を含む暗号文を生成する暗号文生成ステップとを実行し、
前記復号装置は、
前記第１、第２ランダム生成元と、改竄された可能性があるパラメータである第１、第２、第３、第４改竄秘密鍵パラメータに基づいて第１、第２改竄公開鍵パラメータを計算し、改竄公開鍵を計算する改竄公開鍵計算ステップと、
前記改竄公開鍵と前記第１、第２中間暗号文のペアと前記チェック用暗号文と前記マスク済暗号文と前記共通鍵暗号文と前記コアタグとからなるメッセージを前記検証鍵、前記使い捨て署名を用いて検証し検証結果を出力する検証ステップと、
前記検証結果を確認して、前記検証結果が検証成功である場合に検証結果を出力し、検証失敗である場合にリジェクトシンボルを出力し処理を停止する検証結果確認ステップと、
前記チェック用暗号文が、前記第１中間暗号文のペアと前記第１、第２、第３、第４改竄秘密鍵パラメータと前記検証鍵と前記合成数を用いて計算される真値であることを確認し、前記真値であればチェック用暗号文を出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止するチェック用暗号文確認ステップと、
前記第１、第２中間暗号文のペアと前記第１、第２、第３、第４改竄秘密鍵パラメータと前記検証鍵からマスク鍵を計算するマスク鍵計算ステップと、
前記マスク鍵を用いて前記マスク済暗号文を復号してマスク復号結果を取得し、前記合成数の３乗未満であって、前記合成数の３乗と互いに素な数のみの集合のうち、前記合成数の２乗を位数とする部分群である平文用部分群に前記マスク復号結果が属するか否かを確認し、属する場合には前記マスク復号結果を出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止するマスク復号結果確認ステップと、
前記マスク復号結果に対数計算を実行して変換済平文を計算し、前記メッセージを取得する変換済平文計算ステップと、
前記メッセージが前記平文空間に属するか否かを確認し、属する場合には前記メッセージを出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止するメッセージ確認ステップと、
前記検証鍵を前記補助タグとして、前記補助タグと前記コアタグから前記タグを生成するタグ生成ステップと、
前記共通鍵を用いて前記共通鍵暗号文を復号し復号結果を出力する共通鍵復号ステップと、
前記復号結果が前記フィルタ値と等しいか否かを確認し、等しければ前記メッセージを出力し、そうでなければ前記リジェクトシンボルを出力し処理を停止する復号結果確認ステップと、
前記復号装置の各ステップ実行時に前記リジェクトシンボルが出力されなかった場合、前記メッセージを出力するメッセージ出力ステップとを実行する。
【請求項４】
請求項３に記載の暗号通信方法であって、
前記鍵生成装置と、前記復号装置とが単一の装置内に含まれ、前記鍵生成装置と、前記復号装置とが実行するステップの全てを前記単一の装置が実行する
暗号通信方法。
【請求項５】
コンピュータを、請求項１または２に記載の暗号通信システムに含まれる暗号化装置として機能させるためのプログラム。
【請求項６】
コンピュータを、請求項１または２に記載の暗号通信システムに含まれる復号装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号方式に関し、特にRKA-KDM-CCA安全性を実現する暗号通信システム、暗号通信方法、プログラムに関する。
【背景技術】
【０００２】
本明細書では、鍵依存平文の暗号文の安全性をKDM安全性、関連鍵攻撃に対する安全性をRKA安全性と呼ぶ。なお関連鍵攻撃環境下での鍵依存平文の暗号文の安全性をRKA-KDM安全性と呼ぶ。またKDM安全かつRKA安全だからといって、RKA-KDM安全だとは限らない。
【０００３】
秘密鍵に依存した平文を暗号化する方式には理論的な応用と実際的な応用がある。理論的な応用として、暗号を用いたプロトコルの自動検証が挙げられる。自動検証を通るプロトコルは、KDM安全な暗号方式を用いているのであれば、暗号学的な意味でも安全性が保障される。また実際的な応用として、ディスク暗号化が挙げられる。たとえばディスク暗号化ソフトであるBitLockerでは、秘密鍵自身を暗号化することがあった。この安全性を保障するには、KDM安全性が必要である。KDM安全な暗号方式の既往研究として、非特許文献１がある。復号オラクルが存在する環境下での鍵依存平文の安全性をKDM-CCA安全性と呼ぶ。KDM-CCA安全な公開鍵暗号方式として、Camenisch, Chandran, Shoupの方式（非特許文献２）やHofheinzの方式（非特許文献３）が知られている。また、RKA-KDM-CPA安全な共通鍵暗号方式として、Applebaumの方式（非特許文献４）やBohl, Davies, Hofheinzの方式（非特許文献５）が知られている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Isamu Teranishi. Survey of key dependent message ( KDM ) security. IEICE Fundamentals Review,6(1):26-36,2012.
【非特許文献２】Jan Camenisch、Nishanth Chandran, and Victor Shoup. A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In Antoine Joux, editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 351-368. Springer, Heidelberg, 2009.
【非特許文献３】Dennis Hofheinz. Circular chosen-ciphertext security with compact ciphertexts. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 520-536. Springer, Heidelberg,2013.
【非特許文献４】Benny Applebaum. Garbling XOR gates “for free” in the standard model. In Amit Sahai, editor, TCC2013, volume 7785 of LNCS, pages 162-181. Springer, Heidelberg, 2013. See also http://eprint.iacr.org/2012/516.
【非特許文献５】Florian Bohl, Gareth T. Davies, and Dennis Hofheinz. RKA-KDM secure encryption from public-key encryption. Cryptology ePrint Archive, Report 2013/653, 2013. Available at http://eprint.iacr.org/2013/653.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
RKA-KDM-CPA安全な共通鍵暗号方式として非特許文献５などが知られている一方、RKA-KDM-CCA安全な公開鍵暗号方式についての研究はこれまでなされておらず、存在するかどうかも不明であった。そこで本発明では、RKA-KDM-CCA安全な公開鍵暗号方式を実現する暗号通信システム、暗号通信方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の暗号通信システムは、パラメータ装置と、鍵生成装置と、暗号化装置と、復号装置を含む。
【０００７】
パラメータ装置は、条件パラメータ設定部と、ＲＳＡモジュラス生成部と、ランダム生成元設定部と、パラメータ生成部とを含む。条件パラメータ設定部は、合成数の長さ、メッセージの数、フィルタ用素数の長さを示す条件パラメータを設定する。ＲＳＡモジュラス生成部は、セキュリティパラメータを入力とし、第１、第２のブラム素数とＲＳＡモジュラスの合成数を生成する。ランダム生成元設定部は、合成数の３乗未満であって、合成数の３乗と互いに素な数のみの集合のうち、所定の位数の部分群である乱数用部分群において、第１、第２ランダム生成元を設定する。パラメータ生成部は、セキュリティパラメータを入力とし、フィルタ鍵とトラップドアを生成する。
【０００８】
鍵生成装置は、秘密鍵パラメータ選択部と、公開鍵パラメータ計算部と、公開鍵生成部と、秘密鍵生成部とを含む。秘密鍵パラメータ選択部は、平文空間から、第１、第２、第３、第４秘密鍵パラメータをランダムに選択する。公開鍵パラメータ計算部は、第１、第２ランダム生成元と、第１、第２、第３、第４秘密鍵パラメータに基づいて第１、第２公開鍵パラメータを計算する。公開鍵生成部は、第１、第２公開鍵パラメータから公開鍵を生成する。秘密鍵生成部は、第１、第２、第３、第４秘密鍵パラメータから秘密鍵を生成する。
【０００９】
暗号化装置は、乱数選択部と、署名鍵生成部と、共通鍵選択部と、タグ設定部と、第１中間暗号文計算部と、第２中間暗号文計算部と、チェック用暗号文計算部と、マスク済暗号文計算部と、共通鍵暗号化部と、署名部と、暗号文生成部とを含む。乱数選択部は、合成数の４分の１未満の数の集合から第１、第２乱数をランダムに選択する。署名鍵生成部は、セキュリティパラメータを入力とし、使い捨て署名用の鍵ペアである検証鍵と署名鍵を生成する。共通鍵選択部は、共通鍵暗号用のランダムな鍵である共通鍵をランダムに選択する。タグ設定部は、タグがコアタグと補助タグからなるものとし、検証鍵を補助タグとし、コアタグをタグ空間からランダムに選択する。第１中間暗号文計算部は、第１乱数と第１、第２ランダム生成元に基づいて第１中間暗号文のペアを計算する。第２中間暗号文計算部は、第２乱数と第１、第２ランダム生成元に基づいて第２中間暗号文のペアを計算する。チェック用暗号文計算部は、第１、第２公開鍵パラメータと検証鍵と第１乱数と合成数に基づいてチェック用暗号文を計算する。マスク済暗号文計算部は、第１、第２公開鍵パラメータと検証鍵と第１、第２乱数と合成数と共通鍵とメッセージに基づいてマスク済暗号文を計算する。共通鍵暗号化部は、フィルタ入力用に変換したメッセージの損失的代数フィルタのフィルタ値を共通鍵で暗号化して共通鍵暗号文を生成する。署名部は、署名鍵を用いて、公開鍵と第１、第２中間暗号文のペアとチェック用暗号文とマスク済暗号文と共通鍵暗号文とコアタグの使い捨て署名を生成する。暗号文生成部は、第１、第２中間暗号文のペアとチェック用暗号文とマスク済暗号文と共通鍵暗号文とコアタグと検証鍵と使い捨て署名を含む暗号文を生成する。
【００１０】
復号装置は、改竄公開鍵計算部と、検証部と、検証結果確認部と、チェック用暗号文確認部と、マスク鍵計算部と、マスク復号結果確認部と、変換済平文計算部と、メッセージ確認部と、タグ生成部と、共通鍵復号部と、復号結果確認部と、メッセージ出力部を含む。改竄公開鍵計算部は、第１、第２ランダム生成元と、改竄された可能性があるパラメータである第１、第２、第３、第４改竄秘密鍵パラメータに基づいて第１、第２改竄公開鍵パラメータを計算し、改竄公開鍵を計算する。検証部は、改竄公開鍵と第１、第２中間暗号文のペアとチェック用暗号文とマスク済暗号文と共通鍵暗号文とコアタグとからなるメッセージを検証鍵、使い捨て署名を用いて検証し検証結果を出力する。検証結果確認部は、検証結果を確認して、検証結果が検証成功である場合に検証結果を出力し、検証失敗である場合にリジェクトシンボルを出力し処理を停止する。チェック用暗号文確認部は、チェック用暗号文が、第１中間暗号文のペアと第１、第２、第３、第４改竄秘密鍵パラメータと検証鍵と合成数を用いて計算される真値であることを確認し、真値であればチェック用暗号文を出力し、そうでなければリジェクトシンボルを出力し処理を停止する。マスク鍵計算部は、第１、第２中間暗号文のペアと第１、第２、第３、第４改竄秘密鍵パラメータと検証鍵からマスク鍵を計算する。マスク復号結果確認部は、マスク鍵を用いてマスク済暗号文を復号してマスク復号結果を取得し、合成数の３乗未満であって、合成数の３乗と互いに素な数のみの集合のうち、合成数の２乗を位数とする部分群である平文用部分群にマスク復号結果が属するか否かを確認し、属する場合にはマスク復号結果を出力し、そうでなければリジェクトシンボルを出力し処理を停止する。変換済平文計算部は、マスク復号結果に対数計算を実行して変換済平文を計算し、メッセージを取得する。メッセージ確認部は、メッセージが平文空間に属するか否かを確認し、属する場合にはメッセージを出力し、そうでなければリジェクトシンボルを出力し処理を停止する。タグ生成部は、検証鍵を補助タグとして、補助タグとコアタグからタグを生成する。共通鍵復号部は、共通鍵を用いて共通鍵暗号文を復号し復号結果を出力する。復号結果確認部は、復号結果がフィルタ値と等しいか否かを確認し、等しければメッセージを出力し、そうでなければリジェクトシンボルを出力し処理を停止する。メッセージ出力部は、復号装置の各部の動作時にリジェクトシンボルが出力されなかった場合、メッセージを出力する。
【発明の効果】
【００１１】
本発明の暗号通信システムによれば、RKA-KDM-CCA安全な公開鍵暗号方式を実現することができる。
【図面の簡単な説明】
【００１２】
【図１】従来技術の損失的代数フィルタアルゴリズムを装置の構成要素に分解して示すブロック図。
【図２】従来技術のＲＳＡモジュラス生成アルゴリズムを装置の構成要素として示すブロック図。
【図３】従来技術の共通鍵暗号アルゴリズムを装置の構成要素に分解して示すブロック図。
【図４】従来技術の使い捨て署名アルゴリズムを装置の構成要素に分解して示すブロック図。
【図５】本発明の実施例１の暗号通信システムの概略を示す図。
【図６】本発明の実施例１の変形例の暗号通信システムの概略を示す図。
【図７】本発明の実施例１のパラメータ装置の構成を示すブロック図。
【図８】本発明の実施例１のパラメータ装置の動作を示すフローチャート。
【図９】本発明の実施例１の鍵生成装置の構成を示すブロック図。
【図１０】本発明の実施例１の鍵生成装置の動作を示すフローチャート。
【図１１】本発明の実施例１の暗号化装置の構成を示すブロック図。
【図１２】本発明の実施例１の暗号化装置の動作を示すフローチャート。
【図１３】本発明の実施例１の復号装置の構成を示すブロック図。
【図１４】本発明の実施例１の復号装置の動作を示すフローチャート。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１４】
≪準備≫
実施例１について述べる前に、本節では以降で利用する用語について説明する。以下では、κ∈Nをセキュリティパラメータとする。
【００１５】
＜損失的代数フィルタ, Lossy Algebraic Filter, LAF＞
(lLAF,n)-LAFとは、フィルタ鍵fpkとタグtによって決まる関数の族である。lLAFはフィルタ用素数pの長さパラメータ、nはメッセージの数を表す。従って、フィルタ用素数pをlLAFビットの素数とし、ZnpはZp要素のｎ次元ベクトル空間を表すものとし、ｎ個のメッセージX=(X1,…,Xn)∈Znpを入力とし、損失的代数フィルタのフィルタ値LAFfpk,t(X)を出力とする。タグにはinjectiveなものとlossyなものが存在する。またタグtは、t=(ta,tc)と分けることができ、特にtcをコアタグ、taを補助タグと呼ぶ。
【００１６】
損失的代数フィルタアルゴリズムは、４つのアルゴリズムの組からなる。詳細には、LAF=(FGen,FEval,TagSample,FTag)と表現される。以下、図１を参照して損失的代数フィルタアルゴリズムの各アルゴリズムについて説明する。図１は、従来技術の損失的代数フィルタアルゴリズムを装置の構成要素に分解して示すブロック図である。図１に示すように、損失的代数フィルタアルゴリズムは、パラメータ生成部(FGen)５１、関数評価部(FEval)５２、タグサンプリング部(TagSample)５３、ロッシータグサンプリング部(FTag)５４のそれぞれが実行するアルゴリズムの総称を意味する。本明細書では、FGenなどのアルゴリズムの名称は、対応する各構成要件の名称の後ろにカッコ書きで併記する。
【００１７】
＜パラメータ生成部(FGen)５１＞
パパラメータ生成部(FGen)５１はセキュリティパラメータ1κを入力とし、（フィルタ鍵，トラップドア）＝(fpk,ftd)を出力する。フィルタ鍵fpkは、lLAF(κ)ビットの素数pとタグ空間T={0,1}*×Tcの記述とを含む。Tcは、コアタグ全体の集合である。トラップドアftdを用いるとlossyなタグをサンプルすることが出来る。
【００１８】
＜関数評価部(FEval)５２＞
関数評価部(FEval)５２は、フィルタ鍵fpk、タグt∈T、X∈Znpを入力とし、損失的代数フィルタのフィルタ値LAFfpk,t(X)を出力する。
【００１９】
＜タグサンプリング部(TagSample)５３＞
タグサンプリング部(TagSample)５３は、フィルタ鍵fpkを入力とし、コアタグtc∈Tcをサンプルする。このとき、コアタグtcとして圧倒的な確率でinjectiveなタグがサンプルされる。
【００２０】
＜ロッシータグサンプリング部(FTag)５４＞
ロッシータグサンプリング部(FTag)５４は、トラップドアftdと補助タグta∈{0,1}*を入力とし、タグt=(ta,tc)がlossyになるようなコアタグtc∈Tcをサンプルする。本アルゴリズムの具体的な構成法は非特許文献３を参照のこと。
【００２１】
＜RSAモジュラス生成アルゴリズム＞
以下、図２を参照してRSAモジュラス生成アルゴリズムについて説明する。図２は、従来技術のＲＳＡモジュラス生成アルゴリズムを装置の構成要素として示すブロック図である。図２に示すように、RSAモジュラス生成アルゴリズムは、RSAモジュラス生成部(GenN)６が実行するアルゴリズムを意味する。RSAモジュラス生成部(GenN)６は、セキュリティパラメータ1κを入力とし、lNビットの第１、第２のブラム素数P,Qを生成し、合成数N=PQを出力する。lNは、合成数Nの長さパラメータである。
【００２２】
＜RSAモジュラスの性質＞
RSAモジュラス生成部(GenN)６が出力した合成数Nについて、0以上N3-1以下(N3未満)の範囲で、合成数Nの3乗(N3)と互いに素な数のみの集合である
【００２３】
【数１】
2015126332.tif 000003
【００２４】
を考える。この群の位数はφ(N3)=N2・φ(N)である。PおよびQは奇素数なのでφ(N)/4=(P-1)(Q-1)=4は正整数である。N2および、φ(N)/4はφ(N3)を割り切り、それぞれの位数を持つ
【００２５】
【数２】
2015126332.tif 000004
【００２６】
の部分群が存在する。Grndは、
【００２７】
【数３】
2015126332.tif 000005
【００２８】
の位数φ(N)/4の部分群を表す。Grndを、乱数用部分群ともいう。Gmsgは、
【００２９】
【数４】
2015126332.tif 000006
【００３０】
の位数N2の部分群を表す。Gmsgを、平文用部分群ともいう。Gmsgの生成元hを、h = 1 + N mod N3と定義する。このとき、Gmsgの生成元hで生成される巡回群<h>は平文用部分群Gmsgに等しい。この群では離散対数が簡単に解ける。N,h,X=hx∈Gmsgが与えられたとき、
【００３１】
【数５】
2015126332.tif 000007
【００３２】
を求める効率の良いアルゴリズムが存在する（参考非特許文献１）。
（参考非特許文献１：Ivan Damgard and Mads Jurik. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In Kwangjo Kim, editor, PKC2001, volume 1992 of LNCS, pages 119-136. Springer, Heidelberg, 2001.）
【００３３】
＜共通鍵暗号アルゴリズム＞
共通鍵暗号アルゴリズムとして、IND-CPA安全かつkey-uniqueな共通鍵暗号を用いる。共通鍵暗号アルゴリズムは2つのアルゴリズム(E,D)からなる。以下、図３を参照して従来技術の共通鍵暗号アルゴリズムの各アルゴリズムについて説明する。図３は、従来技術の共通鍵暗号アルゴリズムを装置の構成要素に分解して示すブロック図である。図３に示すように、共通鍵暗号アルゴリズムは、共通鍵暗号化部(E)７１、共通鍵復号部(D)７２のそれぞれが実行するアルゴリズムの総称を意味する。共通鍵暗号化部(E)７１は共通鍵K∈{0,1}κと平文Mを入力とし、暗号文Cを出力する。共通鍵復号部(D)７２は共通鍵K∈{0,1}κと暗号文Cを入力とし、平文Mまたはリジェクトシンボル（⊥）を出力する。共通鍵暗号アルゴリズム(E,D)がkey-uniqueとは、任意の暗号文CについてD(K,C)≠⊥となるのは高々1つの共通鍵Kであることを意味する。
【００３４】
＜使い捨て署名アルゴリズム＞
従来技術の使い捨て署名アルゴリズムは3つのアルゴリズム(OGen,OSign,OVrfy)からなる。以下、図４を参照して従来技術の使い捨て署名アルゴリズムの各アルゴリズムについて説明する。図４は、従来技術の使い捨て署名アルゴリズムを装置の構成要素に分解して示すブロック図である。図４に示すように、従来技術の使い捨て署名アルゴリズムは、署名鍵生成部(OGen)８１、署名部(OSign)８２、検証部(OVrfy)８３のそれぞれが実行するアルゴリズムの総称を意味する。署名鍵生成部(OGen)８１はセキュリティパラメータ1κを入力とし、使い捨て署名用の鍵ペア（検証鍵，署名鍵）＝(ovk,osk)を出力する。署名部(OSign)８２は署名鍵oskとメッセージMを入力とし、使い捨て署名σを出力する。検証部(OVrfy)８３は検証鍵ovkとメッセージMと使い捨て署名σを入力とし、検証結果(0 or 1)を出力する。本明細書では0を検証失敗、1を検証成功を示す値とする。
【実施例１】
【００３５】
以下、図５を参照して実施例１の暗号通信システムの概略について説明する。図５は、本実施例の暗号通信システム１０００の概略を示す図である。図５に示すように、本実施例の暗号通信システム１０００は、パラメータ装置１と、鍵生成装置(Gen)２と、暗号化装置(Enc)３と、復号装置(Dec)４を含む。パラメータ装置１、鍵生成装置(Gen)２、暗号化装置(Enc)３、復号装置(Dec)４はネットワーク９により無線または有線で通信可能に接続されている。各装置の詳細、および動作については後述する。なお、鍵生成装置(Gen)２と、復号装置(Dec)４とは一つの装置で構成されていてもよい。従って、図６に示すような変形例が実施可能である。図６は、本実施例の変形例の暗号通信システム１０００’の概略を示す図である。図６に示すように、前述の復号装置４は鍵生成部２、復号部４を含む復号装置４’と変形可能である。この時、鍵生成部２、復号部４は前述の鍵生成装置２、復号装置４と全く同じ動作をする。以下では、暗号通信システム１０００の構成に従って各装置の説明を行うが、暗号通信システム１０００’としてシステムを構成する場合には、後述する鍵生成装置２、復号装置４をそれぞれ鍵生成部２、復号部４と読み替えればよい。
【００３６】
＜パラメータ装置１＞
次に、図７、図８を参照して本実施例の暗号通信システム１０００を構成するパラメータ装置１について説明する。図７は、本実施例のパラメータ装置１の構成を示すブロック図である。図８は、本実施例のパラメータ装置１の動作を示すフローチャートである。図７に示すように、パラメータ装置１は、条件パラメータ設定部１１と、共通パラメータ生成部(Pars)１２を含む。共通パラメータ生成部(Pars)１２は、ＲＳＡモジュラス生成部(GenN)６と、ランダム生成元設定部１２１と、パラメータ生成部(FGen)５１とを含む。
【００３７】
条件パラメータ設定部１１は、合成数の長さ、メッセージの数、フィルタ用素数の長さを示す条件パラメータを設定する（Ｓ１１）。詳細には、条件パラメータ設定部１１は、合成数の長さパラメータをlN≧25κ+8と設定し、メッセージ数nをn=6と設定し、フィルタ用素数pの長さパラメータをlLAF=(lN+κ+1)/(n-6)と設定する。ＲＳＡモジュラス生成部(GenN)６は、セキュリティパラメータを入力とし、第１、第２のブラム素数とＲＳＡモジュラスの合成数を生成する（Ｓ６）。詳細には、ＲＳＡモジュラス生成部(GenN)６は、セキュリティパラメータ１κを入力とし、アルゴリズムGenN(1κ)を用いて、第１、第２のブラム素数P、Qと、合成数Nを得る。ランダム生成元設定部１２１は、合成数の３乗未満であって、合成数の３乗と互いに素な数のみの集合のうち、所定の位数の部分群である乱数用部分群において、第１、第２ランダム生成元を設定する（Ｓ１２１）。詳細には、ランダム生成元設定部１２１は、第１、第２のランダム生成元g1,g2を乱数用部分群Grndのランダムな生成元として設定する。パラメータ生成部(FGen)５１は、セキュリティパラメータを入力とし、フィルタ鍵とトラップドアを生成する（Ｓ５１）。詳細には、パラメータ生成部(FGen)５１は、セキュリティパラメータ1κを入力とし、（フィルタ鍵，トラップドア）＝(fpk,ftd)←FGen(1κ)を生成する。共通パラメータ生成部(Pars)１２は、共通パラメータpp=(N,g1,g2,fpk)を出力する。記号[p1,pm)は、p1からpm-1までの数の集合(p1,...,pm-1)を表すものとし、以下では、平文空間を
【００３８】
【数６】
2015126332.tif 000008
【００３９】
とする。従って平文空間は、
【００４０】
【数７】
2015126332.tif 000009
【００４１】
である。任意の
【００４２】
【数８】
2015126332.tif 000010
【００４３】
について、M=a+b・p2k+c・p24kとなる一意な
【００４４】
【数９】
2015126332.tif 000011
【００４５】
が存在する。この３つ組(a,b,c)を求める関数をαとする。また平文をLAFの入力に変換する関数
【００４６】
【数１０】
2015126332.tif 000012
【００４７】
を定義する。これは、ζ(M)=(a, b mod p, c0, …, cn-3)∈Znpとする。なお、c0, … , cn-3は係数cを、
【００４８】
【数１１】
2015126332.tif 000013
【００４９】
と分解したものである。
【００５０】
＜鍵生成装置(Gen)２＞
以下、図９、図１０を参照して本実施例の暗号通信システム１０００を構成する鍵生成装置(Gen)２について説明する。図９は、本実施例の鍵生成装置(Gen)２の構成を示すブロック図である。図１０は、本実施例の鍵生成装置(Gen)２の動作を示すフローチャートである。図９に示すように、鍵生成装置(Gen)２は、秘密鍵パラメータ選択部２１と、公開鍵パラメータ計算部２２と、公開鍵生成部２３と、秘密鍵生成部２４とを含む。鍵生成装置(Gen)２は、共通パラメータpp=(N,g1,g2,fpk)を入力とする。秘密鍵パラメータ選択部２１は、平文空間から、第１、第２、第３、第４秘密鍵パラメータをランダムに選択する（Ｓ２１）。詳細には、秘密鍵パラメータ選択部２１は、s1,s2,s3,s4をそれぞれ第１、第２、第３、第４秘密鍵パラメータとし、j=1,2,3,4について、
【００５１】
【数１２】
2015126332.tif 000014
【００５２】
をランダムに選ぶ。公開鍵パラメータ計算部２２は、第１、第２ランダム生成元と、第１、第２、第３、第４秘密鍵パラメータに基づいて第１、第２公開鍵パラメータを計算する（Ｓ２２）。詳細には、公開鍵パラメータ計算部２２は、第１、第２公開鍵パラメータu,vを、
【００５３】
【数１３】
2015126332.tif 000015
【００５４】
と計算する。公開鍵生成部２３は、第１、第２公開鍵パラメータから公開鍵を生成する（Ｓ２３）。詳細には、公開鍵生成部２３は、公開鍵をpk=(u,v)∈G2rndとして生成する。秘密鍵生成部２４は、第１、第２、第３、第４秘密鍵パラメータから秘密鍵を生成する（Ｓ２４）。詳細には、秘密鍵生成部２４は、秘密鍵を
【００５５】
【数１４】
2015126332.tif 000016
【００５６】
として出力する。
【００５７】
＜暗号化装置(Enc)３＞
以下、図１１、図１２を参照して本実施例の暗号通信システム１０００を構成する暗号化装置(Enc)３について説明する。図１１は、本実施例の暗号化装置(Enc)３の構成を示すブロック図である。図１２は、本実施例の暗号化装置(Enc)３の動作を示すフローチャートである。図１１に示すように、暗号化装置(Enc)３は、乱数選択部３１と、署名鍵生成部(OGen)８１と、共通鍵選択部３２と、タグ設定部３３と、第１中間暗号文計算部３４と、第２中間暗号文計算部３５と、チェック用暗号文計算部３６と、マスク済暗号文計算部３７と、共通鍵暗号化部(E)７１と、署名部(OSign)８２と、暗号文生成部３８とを含む。暗号化装置(Enc)３は、共通パラメータpp、公開鍵pk、メッセージ（平文）Ｍを入力とする。なお、
【００５８】
【数１５】
2015126332.tif 000017
【００５９】
である。乱数選択部３１は、合成数の４分の１未満の数の集合から第１、第２乱数をランダムに選択する（Ｓ３１）。詳細には、乱数選択部３１は、第１、第２乱数r,ρ(r,ρ∈ZN/4)をランダムに選ぶ。署名鍵生成部(OGen)８１は、セキュリティパラメータを入力とし、使い捨て署名用の鍵ペアである検証鍵と署名鍵を生成する（Ｓ８１）。詳細には、署名鍵生成部(OGen)８１は、使い捨て署名用の鍵ペア（検証鍵，署名鍵）を(ovk,osk)←OGenと生成する。共通鍵選択部３２は、共通鍵暗号用のランダムな鍵である共通鍵をランダムに選択する（Ｓ３２）。詳細には、共通鍵空間を{0,1}kと表し、共通鍵選択部３２は、共通鍵暗号用のランダムな鍵である共通鍵KをK∈{0,1}kとランダムに選ぶ。タグ設定部３３は、タグがコアタグと補助タグからなるものとし、検証鍵を補助タグとし、コアタグをタグ空間からランダムに選択する（Ｓ３３）。詳細には、タグ設定部３３は、補助タグta=ovkとし、コアタグtc←Tcをランダムに選び、タグをt=(ta,tc)として設定する。第１中間暗号文計算部３４は、第１乱数と第１、第２ランダム生成元に基づいて第１中間暗号文のペアを計算する（Ｓ３４）。詳細には、第１中間暗号文計算部３４は、第１中間暗号文のペアをG1,G2として、(G1,G2)=(g1r,g2r)を計算する。第２中間暗号文計算部３５は、第２乱数と第１、第２ランダム生成元に基づいて第２中間暗号文のペアを計算する（Ｓ３５）。詳細には、第２中間暗号文計算部３４は、第２中間暗号文のペアをF1,F2として、(F1,F2)=(g1ρ,g2ρ)を計算する。チェック用暗号文計算部３６は、第１、第２公開鍵パラメータと検証鍵と第１乱数と合成数に基づいてチェック用暗号文を計算する（Ｓ３６）。詳細には、チェック用暗号文計算部３６は、チェック用暗号文Zを、
【００６０】
【数１６】
2015126332.tif 000018
【００６１】
と計算する。マスク済暗号文計算部３７は、第１、第２公開鍵パラメータと検証鍵と第１、第２乱数と合成数と共通鍵とメッセージに基づいてマスク済暗号文を計算する（Ｓ３７）。詳細には、マスク済暗号文計算部３７は、マスク済暗号文Yを、
【００６２】
【数１７】
2015126332.tif 000019
【００６３】
と計算する。共通鍵暗号化部７１は、フィルタ入力用に変換したメッセージの損失的代数フィルタのフィルタ値を共通鍵で暗号化して共通鍵暗号文を生成する（Ｓ７１）。詳細には、共通鍵暗号化部７１は、共通鍵暗号文CEを、CE=E(K,LAFfpk,t(ζ(M)))と生成する。署名部(OSign)８２は、署名鍵を用いて、公開鍵と第１、第２中間暗号文のペアとチェック用暗号文とマスク済暗号文と共通鍵暗号文とコアタグの使い捨て署名を生成する（Ｓ８２）。詳細には、署名部８２は、σ=OSign(osk,(pk,G1,G2,F1,F2,Z,Y,CE,tc))として、使い捨て署名σを生成する。最後に、暗号文生成部３８は、第１、第２中間暗号文のペアとチェック用暗号文とマスク済暗号文と共通鍵暗号文とコアタグと検証鍵と使い捨て署名を含む暗号文を生成する（Ｓ３８）。詳細には、暗号文生成部３８は、暗号文Cを、C=(G1,G2,F1,F2,Z,Y,CE,tc,ovk,σ)として生成する。暗号化装置(Enc)３は、暗号文として、Cを出力する。
【００６４】
＜復号装置(Dec)４＞
以下、図１３、図１４を参照して本実施例の暗号通信システム１０００を構成する復号装置(Dec)４について説明する。図１３は、本実施例の復号装置(Dec)４の構成を示すブロック図である。図１４は、本実施例の復号装置(Dec)４の動作を示すフローチャートである。図１３に示すように、復号装置(Dec)４は、改竄公開鍵計算部４０と、検証部(OVrfy)８３と、検証結果確認部４１と、チェック用暗号文確認部４２と、マスク鍵計算部４３と、マスク復号結果確認部４４と、変換済平文計算部４５と、メッセージ確認部４６と、タグ生成部４７と、共通鍵復号部(D)７２と、復号結果確認部４８と、メッセージ出力部４９を含む。復号装置(Dec)４は、共通パラメータppと、改竄秘密鍵
【００６５】
【数１８】
2015126332.tif 000020
【００６６】
と、暗号文C=(G1,G2,F1,F2,Z,Y,CE,tc,ovk,σ)を入力とする。ξ1,ξ2,ξ3,ξ4をそれぞれ、第１、第２、第３、第４改竄秘密鍵パラメータと呼ぶ。改竄秘密鍵とは、攻撃者により改竄された可能性がある秘密鍵のことである。改竄がなされていない場合には、ξj=sjである(j=1,2,3,4)。改竄公開鍵計算部４０は、第１、第２ランダム生成元と、改竄された可能性があるパラメータである第１、第２、第３、第４改竄秘密鍵パラメータに基づいて第１、第２改竄公開鍵パラメータを計算し、改竄公開鍵を計算する（Ｓ４０）。詳細には、改竄公開鍵計算部４０は、改竄公開鍵を、
【００６７】
【数１９】
2015126332.tif 000021
【００６８】
と計算する。検証部(OVrfy)８３は、改竄公開鍵と第１、第２中間暗号文のペアとチェック用暗号文とマスク済暗号文と共通鍵暗号文とコアタグとからなるメッセージを検証鍵、使い捨て署名を用いて検証し検証結果を出力する（Ｓ８３）。詳細には、検証部(OVrfy)８３は、検証結果
【００６９】
【数２０】
2015126332.tif 000022
【００７０】
を生成し、出力する。検証結果確認部４１は、検証結果を確認して、検証結果が検証成功である場合に検証結果を出力し、検証失敗である場合にリジェクトシンボル（⊥）を出力し処理を停止する（Ｓ４１）。詳細には、検証結果確認部４１は、
【００７１】
【数２１】
2015126332.tif 000023
【００７２】
であることを確かめる。検証結果確認部４１は、検証結果が１でない場合には、リジェクトシンボル（⊥）を出力し、処理を停止する。チェック用暗号文確認部４２は、チェック用暗号文が、第１中間暗号文のペアと第１、第２、第３、第４改竄秘密鍵パラメータと検証鍵と合成数を用いて計算される真値であることを確認し、真値であればチェック用暗号文を出力し、そうでなければリジェクトシンボル（⊥）を出力し処理を停止する（Ｓ４２）。詳細には、チェック用暗号文確認部４２は、チェック用暗号文Zが、
【００７３】
【数２２】
2015126332.tif 000024
【００７４】
であることを確かめる。チェック用暗号文確認部４２は、チェック用暗号文Zが、真値
【００７５】
【数２３】
2015126332.tif 000025
【００７６】
と等しくならない場合には、リジェクトシンボル（⊥）を出力し処理を停止する。マスク鍵計算部４３は、第１、第２中間暗号文のペアと第１、第２、第３、第４改竄秘密鍵パラメータと検証鍵からマスク鍵を計算する（Ｓ４３）。詳細には、マスク鍵計算部４３は、マスク鍵Z'を、
【００７７】
【数２４】
2015126332.tif 000026
【００７８】
と計算する。マスク復号結果確認部４４は、マスク鍵を用いてマスク済暗号文を復号してマスク復号結果を取得し、合成数の３乗未満であって、合成数の３乗と互いに素な数のみの集合のうち、合成数の２乗を位数とする部分群である平文用部分群Gmsgにマスク復号結果が属するか否かを確認し、属する場合にはマスク復号結果を出力し、そうでなければリジェクトシンボル（⊥）を出力し処理を停止する（Ｓ４４）。詳細には、マスク復号結果確認部４４は、マスク復号結果YZ'-1が、
【００７９】
【数２５】
2015126332.tif 000027
【００８０】
であることを確かめる。マスク復号結果確認部４４は、マスク復号結果YZ'-1が平文用部分群Gmsgに属さない場合にはリジェクトシンボル（⊥）を出力し処理を停止する。変換済平文計算部４５は、マスク復号結果に対数計算を実行して変換済平文を計算し、メッセージを取得する（Ｓ４５）。詳細には、変換済平文計算部４５は、変換済み平文dを、d=dlogh(YZ'-1)と計算し、d=K+2k・Mとパースする。メッセージ確認部４６は、メッセージが平文空間に属するか否かを確認し、属する場合にはメッセージを出力し、そうでなければリジェクトシンボルを出力し処理を停止する（Ｓ４６）。詳細には、メッセージ確認部４６は、
【００８１】
【数２６】
2015126332.tif 000028
【００８２】
であることを確かめる。メッセージ確認部４６は、メッセージＭが平文空間に属さない場合には、リジェクトシンボル（⊥）を出力し処理を停止する。タグ生成部４７は、検証鍵を補助タグとして、補助タグとコアタグからタグを生成する（Ｓ４７）。詳細には、タグ生成部４７は、タグt=(ovk,tc)とする。共通鍵復号部(D)７２は、共通鍵を用いて共通鍵暗号文を復号し復号結果D(K,CE)を出力する（Ｓ７２）。復号結果確認部４８は、復号結果がフィルタ値と等しいか否かを確認し、等しければメッセージを出力し、そうでなければリジェクトシンボルを出力し処理を停止する（Ｓ４８）。詳細には、復号結果確認部４８は、復号結果であるD(K,CE)が、D(K,CE)=LAFfpk,t(ζ(M))であることを確かめる。復号結果確認部４８は、D(K,CE)=LAFfpk,t(ζ(M))でない場合には、リジェクトシンボル（⊥）を出力し処理を停止する。メッセージ出力部４９は、復号装置(Dec)４の各部の動作時にリジェクトシンボル（⊥）が出力されなかった場合、メッセージを出力する（Ｓ４９）。
【００８３】
このように、本実施例の暗号通信システム１０００、その変形例の暗号通信システム１０００’によれば、RKA-KDM-CCA安全な公開鍵暗号方式を実現することができ、関連鍵攻撃に対しても鍵依存平文暗号文を守ることができる。
【００８４】
≪発明の要点≫
本発明は、KDM-CCA安全性を持つHofheinzの方式（非特許文献３）を元にしている。Hofheinz方式と本発明との差分を説明する。
【００８５】
＜暗号化＞
本発明とHofheinz方式とでは、署名生成手順が異なる。実施例１における署名部(OSign)８２における手順（ステップＳ８２）である。Hofheinzの方式では、
σH=OSign(osk,(G1,G2,F1,F2,Z,Y,CE,tc))として使い捨て署名を生成している。本発明ではσ←OSign(osk,(pk,G1,G2,F1,F2,Z,Y,CE,tc))と公開鍵pkを追加した上で、使い捨て署名を生成する。
【００８６】
＜復号＞
本発明では、Hofheinz方式の復号アルゴリズムに、公開鍵の再生成手順を追加した。実施例１における改竄公開鍵計算部４０における手順（ステップＳ４０）である。本発明では、再生成された公開鍵を用いて、使い捨て署名の検証を行う。実施例１における検証部(OVrfy)８３における手順（ステップＳ８３）である。Hofheinz方式の場合は、公開鍵の再生成手順（Ｓ４０）はなく、ステップＳ８３は、OVrfy(ovk,(G1,G2,F1,F2,Z,Y,CE,tc),σ)=1であることを確かめる。そうでなければリジェクト（⊥）を出力し、停止する。
【００８７】
本発明では、公開鍵pkを秘密鍵skの指紋として用い、その指紋ごと使い捨て署名を付けることで、暗号文と暗号化に用いた公開鍵を関連付ける。これにより関連鍵攻撃に耐性を持たせることが出来る。ここで、改竄秘密鍵について、
【００８８】
【数２７】
2015126332.tif 000029
【００８９】
であることを確かめないのが好適である。確かめた場合、関連鍵攻撃に弱くなる。
【００９０】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００９１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００９２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015126332.tif 000030
【図２】
2015126332.tif 000031
【図３】
2015126332.tif 000032
【図４】
2015126332.tif 000033
【図５】
2015126332.tif 000034
【図６】
2015126332.tif 000035
【図７】
2015126332.tif 000036
【図８】
2015126332.tif 000037
【図９】
2015126332.tif 000038
【図１０】
2015126332.tif 000039
【図１１】
2015126332.tif 000040
【図１２】
2015126332.tif 000041
【図１３】
2015126332.tif 000042
【図１４】
2015126332.tif 000043