(57)【特許請求の範囲】
【請求項１】
安全性強化装置と検証装置とを含む安全性強化システムが実行する安全性強化方法であって、
上記安全性強化装置は、秘密情報生成部と一時鍵生成部と鍵暗号化部と補助情報生成部とを含むものであり、
上記検証装置は、検証部と一時鍵制御部と鍵制御部とを含むものであり、
上記安全性強化装置の秘密情報生成部が、秘密情報を生成する秘密情報生成ステップと、
上記安全性強化装置の一時鍵生成部が、上記秘密情報を用いて一時鍵を生成する一時鍵生成ステップと、
上記安全性強化装置の鍵暗号化部が、入力された秘密の鍵情報を上記一時鍵により暗号化した鍵暗号文を生成する鍵暗号化ステップと、
上記安全性強化装置の補助情報生成部が、上記秘密情報に対して特定の対応関係を持つ暗号文を得、上記暗号文と上記鍵暗号文を含む補助情報を生成する補助情報生成ステップと、
上記検証装置の検証部が、上記補助情報が上記秘密情報に対して上記対応関係を持つか否かを判定する検証ステップと、
上記検証装置の一時鍵制御部が、上記補助情報が上記秘密情報に対して上記対応関係を持つ場合に上記秘密情報を用いて上記一時鍵を生成する一時鍵制御ステップと、
上記検証装置の鍵制御部が、上記一時鍵を用いて上記鍵暗号文を復号して上記鍵情報を得る鍵制御ステップと、
を含み、
上記秘密情報と異なる関連秘密情報に対して上記対応関係を持つ関連補助情報を上記補助情報から特定することが困難である
安全性強化方法。
【請求項２】
請求項１に記載の安全性強化方法であって、
上記補助情報生成ステップは、上記鍵暗号文と、上記秘密情報に対応する第１暗号文と、上記秘密情報と乱数とに対応する第２暗号文と、上記秘密情報と上記乱数と上記鍵情報を証拠情報として上記第１暗号文と上記第２暗号文と上記鍵暗号文とに対する非対話零知識証明を行うための証明情報とを含む上記補助情報を生成するものであり、
上記検証ステップは、上記証明情報を用いて上記第１暗号文と上記第２暗号文と上記鍵暗号文とに対する非対話零知識証明検証を行い、上記秘密情報に対応する検証用暗号文と上記第１暗号文とが一致するか否かを判定するものである
安全性強化方法。
【請求項３】
請求項１に記載の安全性強化方法であって、
gを群GKの生成元とし、h, z, V, Wを群GKの元とし、Hを衝突困難性を持つ写像とし、eを双線形写像とし、
上記秘密情報生成ステップは、乱数σを選択してs=hσを上記秘密情報として生成するものであり、
上記鍵暗号化ステップは、ξ=e(z, s)を共通鍵として上記鍵情報を暗号化して上記鍵暗号文μを生成するものであり、
上記補助情報生成ステップは、X=gσとTG=(V・WH(X, μ))σとを上記暗号文として得るものであり、
上記検証ステップは、e(g, TG)とe(X, V・WH(X, μ))とが一致し、かつ、e(g, s)とe(X, h)とが一致するか否かを判定するものである
安全性強化方法。
【請求項４】
安全性強化装置と検証装置を含む安全性強化システムであって、
上記安全性強化装置は、
秘密情報を生成する秘密情報生成部と、
上記秘密情報を用いて一時鍵を生成する一時鍵生成部と、
入力された秘密の鍵情報を上記一時鍵により暗号化した鍵暗号文を生成する鍵暗号化部と、
上記秘密情報に対して特定の対応関係を持つ暗号文を得、上記暗号文と上記鍵暗号文を含む補助情報を生成する補助情報生成部と、
を含み、
上記検証装置は、
上記補助情報が上記秘密情報に対して上記対応関係を持つか否かを判定する検証部と、
上記補助情報が上記秘密情報に対して上記対応関係を持つ場合に上記秘密情報を用いて上記一時鍵を生成する一時鍵制御部と、
上記一時鍵を用いて上記鍵暗号文を復号して上記鍵情報を得る鍵制御部と、
を含み、
上記秘密情報と異なる関連秘密情報に対して上記対応関係を持つ関連補助情報を上記補助情報から特定することが困難である
安全性強化システム。
【請求項５】
秘密情報を生成する秘密情報生成部と、
上記秘密情報を用いて一時鍵を生成する一時鍵生成部と、
入力された秘密の鍵情報を上記一時鍵により暗号化した鍵暗号文を生成する鍵暗号化部と、
上記秘密情報に対して特定の対応関係を持つ暗号文を得、上記暗号文と上記鍵暗号文を含む補助情報を生成する補助情報生成部と、
を含み、
上記秘密情報と異なる関連秘密情報に対して上記対応関係を持つ関連補助情報を上記補助情報から特定することが困難である
安全性強化装置。
【請求項６】
秘密情報を用いて生成した一時鍵により秘密の鍵情報を暗号化した鍵暗号文と、上記秘密情報に対して特定の対応関係を持つ暗号文とを含む補助情報を入力として、上記補助情報が上記秘密情報に対して上記対応関係を持つか否かを判定する検証部と、
上記補助情報が上記秘密情報に対して上記対応関係を持つ場合に上記秘密情報を用いて上記一時鍵を生成する一時鍵制御部と、
上記一時鍵を用いて上記鍵暗号文を復号して上記鍵情報を得る鍵制御部と、
を含み、
上記秘密情報と異なる関連秘密情報に対して上記対応関係を持つ関連補助情報を上記補助情報から特定することが困難である
検証装置。
【請求項７】
請求項５に記載の安全性強化装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項６に記載の検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ分野における安全性強化技術に関し、特に関連鍵攻撃に対する安全性を強化する技術に関する。
【背景技術】
【０００２】
秘密情報を持つ一般の暗号学的な回路（以下、単に「回路」という）への関連鍵攻撃に対するアルゴリズム的な安全性強化手法がいくつか提案されている（例えば、非特許文献１から５、特許文献１等参照）。
【０００３】
非特許文献１では、任意の関連鍵攻撃に対する安全性強化手法が提案されている。しかしながら、非特許文献１の安全性強化手法は信頼できる第三者を必要とする。この第三者は公開鍵を公開し、暗号デバイスを作成するたびに、この第三者が関わる必要がある。また、この強化手法では、ひとたび関連鍵攻撃を検知すると回路は自壊してしまう。
【０００４】
非特許文献２では、一部の関連鍵攻撃に対する安全性強化手法が提案されている。非特許文献２の強化手法は信頼できる第三者を必要としない。しかしながら、この強化手法でも、ひとたび関連鍵攻撃を検知すると回路は自壊してしまう。
【０００５】
非特許文献３から５の強化手法は自壊を必要としない。しかしながら、回路および秘密への変更箇所に制限を加えており、任意の関数を捉えていない。
【０００６】
以上より、非特許文献１から５では、回路を自壊させることなく、任意の回路の関連鍵攻撃に対する安全性を向上させる手法は提案されていない。
【０００７】
特許文献１では、安全性強化時に、鍵情報に対応する秘密情報に対して特定の対応関係を持つ補助情報を得て出力する。この秘密情報と異なる関連秘密情報に対して当該対応関係を持つ関連補助情報を当該補助情報から特定することは困難である。このように構成することにより、特許文献１に記載の安全性強化技術は、自壊を必要とせず、任意の回路の関連鍵攻撃に対する安全性を向上させることができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１４−１３５６８７号公報
【非特許文献】
【０００９】
【非特許文献１】R. Gennaro, A. Lysyanskaya, T. Malkin, S. Micali, and T. Rabin, “Algorithmic Tamper-Proof (ATP) Security: Theoretical Foundations for Security against Hardware Tampering”, TCC 2004, vol. 2951 of Lecture Notes in Computer Science, pp. 258-277, 2004.
【非特許文献２】S. Dziembowski, K. Pietrzak, and D. Wichs, “Non-Malleable Codes”, ICS 2010, pp. 434-452, 2010.
【非特許文献３】Y. Ishai, M. Prabhakaran, A. Sahai, and D. Wagner, “Private Circuits II: Keeping Secrets in Tamperable Circuits”, EUROCRYPT 2006, vol. 4004 of Lecture Notes in Computer Science, pp. 308-327, 2006.
【非特許文献４】S. Faust, K. Pietrzak, and D. Venturi, “Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience”, ICALP 2011, vol. 6755 of Lecture Notes in Computer Science, pp. 391-402, 2011.
【非特許文献５】Dana Dachman-Soled, Yael Tauman Kalai, “Securing Circuits against Constant-Rate Tampering”, CRYPTO 2012, vol. 7417 of Lecture Notes in Computer Science, pp. 533-551, 2012.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１に記載の安全性強化技術では、秘密の鍵を安全性強化時に生成することが必要である。そのため、秘密の鍵が既に用いられている場合、安全性を強化することができなかった。
【００１１】
本発明の目的は、このような点に鑑みて、既に用いられている秘密の鍵の安全性を強化することができる安全性強化技術を提供することである。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、この発明の安全性強化方法は、安全性強化装置が、秘密情報を生成する秘密情報生成ステップと、安全性強化装置が、秘密情報を用いて一時鍵を生成する一時鍵生成ステップと、安全性強化装置が、入力された秘密の鍵情報を一時鍵により暗号化した鍵暗号文を生成する鍵暗号化ステップと、安全性強化装置が、秘密情報に対して特定の対応関係を持つ暗号文を得、暗号文と鍵暗号文を含む補助情報を生成する補助情報生成ステップと、検証装置が、補助情報が秘密情報に対して対応関係を持つか否かを判定する検証ステップと、検証装置が、補助情報が秘密情報に対して対応関係を持つ場合に秘密情報を用いて一時鍵を生成する一時鍵制御ステップと、検証装置が、一時鍵を用いて鍵暗号文を復号して鍵情報を得る鍵制御ステップと、を含み、秘密情報と異なる関連秘密情報に対して対応関係を持つ関連補助情報を補助情報から特定することが困難である。
【発明の効果】
【００１３】
この発明によれば、秘密の鍵が安全性強化の前に存在する場合であっても安全性を強化することができる。また、回路が暗号学的デバイスであっても公開鍵型暗号学的デバイスであっても同様に安全性強化が可能である。また、暗号学的デバイスの安全性強化手法の適用領域が、特許文献１の発明よりも広く、汎用的な構成となっている。
【図面の簡単な説明】
【００１４】
【図１】図１は、第一実施形態および第二実施形態の安全性強化システムの機能構成を例示する図である。
【図２】図２Ａは、第一実施形態の設定装置の機能構成を例示する図である。図２Ｂは、第一実施形態の安全性強化装置の機能構成を例示する図である。図２Ｃは、第一実施形態の検証装置の機能構成を例示する図である。
【図３】図３Ａは、第一実施形態のセットアップ方法の処理フローを例示する図である。図３Ｂは、第一実施形態の安全性強化方法の処理フローを例示する図である。図３Ｃは、第一実施形態の検証方法の処理フローを例示する図である。
【図４】図４Ａは、第二実施形態の設定装置の機能構成を例示する図である。図４Ｂは、第二実施形態の安全性強化装置の機能構成を例示する図である。図４Ｃは、第二実施形態の検証装置の機能構成を例示する図である。
【図５】図５Ａは、第二実施形態のセットアップ方法の処理フローを例示する図である。図５Ｂは、第二実施形態の安全性強化方法の処理フローを例示する図である。図５Ｃは、第二実施形態の検証方法の処理フローを例示する図である。
【図６】図６は、第三実施形態の安全性強化システムの機能構成を例示する図である。
【図７】図７Ａは、第三実施形態の設定装置の機能構成を例示する図である。図７Ｂは、第三実施形態の鍵生成装置の機能構成を例示する図である。
【図８】図８Ａは、第三実施形態の送信装置の機能構成を例示する図である。図８Ｂは、第三実施形態の受信装置の機能構成を例示する図である。
【図９】図９Ａは、第三実施形態のセットアップ方法の処理フローを例示する図である。図９Ｂは、第三実施形態のマスター鍵生成方法の処理フローを例示する図である。図９Ｃは、第三実施形態のユーザ鍵生成方法の処理フローを例示する図である。
【図１０】図１０Ａは、第三実施形態の暗号化方法の処理フローを例示する図である。図１０Ｂは、第三実施形態の復号方法の処理フローを例示する図である。
【図１１】図１１は、第四実施形態の安全性強化システムの機能構成を例示する図である。
【図１２】図１２Ａは、第四実施形態の設定装置の機能構成を例示する図である。図１２Ｂは、第四実施形態の送信装置の機能構成を例示する図である。図１２Ｃは、第四実施形態の受信装置の機能構成を例示する図である。
【図１３】図１３Ａは、第四実施形態のセットアップ方法の処理フローを例示する図である。図１３Ｂは、第四実施形態の鍵生成方法の処理フローを例示する図である。
【図１４】図１４Ａは、第四実施形態の暗号化方法の処理フローを例示する図である。図１４Ｂは、第四実施形態の復号方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１５】
実施形態の説明に先立って、本明細書で用いる記法および用語を定義する。
【００１６】
［暗号学的デバイス］
暗号学的デバイス（Setup, Gen, C, X, Y, K）は、以下のSetup, Gen, C, X, Y, Kから構成される。
・Setup(1к)はセットアップアルゴリズムであり、セキュリティパラメータ1кを入力とし、共通パラメータppを出力する。ppは集合X, Y, Kの情報を含む。なお、1кはк個の1からなる列を表す。кは1以上の所定の整数である。
・Gen(pp)は鍵生成アルゴリズムであり、共通パラメータppを入力とし、秘密の鍵情報k∈Kをランダムに選んで出力する。
・C(pp, (k, x))は回路であり、共通パラメータppおよび(k, x)∈K×Xを入力とし、y∈Yを出力する。例えば、C(pp, (k, x))は共通鍵暗号の復号回路であり、kは秘密鍵、xは暗号文、yは平文に対応する。
【００１７】
［公開鍵型暗号学的デバイス］
公開鍵型暗号学的デバイス（Setup, Gen, C, X, Y, K, Ω）は、以下のSetup, Gen, C, X, Y, K, Ωから構成される。
・Setup(1к)はセットアップアルゴリズムであり、セキュリティパラメータ1кを入力とし、共通パラメータppを出力する。ppは集合X, Y, K, Ωの情報を含む。
・Gen(pp; r)は鍵生成アルゴリズムであり、共通パラメータppを入力とし、乱数r∈Ωに基づいて、秘密の鍵情報k∈Kと公開の鍵情報pをランダムに選んで出力する。
・C(pp, (k, x))は回路であり、共通パラメータppおよび(k, x)∈K×Xを入力とし、y∈Yを出力する。例えば、C(pp, (k, x))は公開鍵暗号の復号回路であり、kは復号鍵、xは暗号文、yは平文に対応する。他にもC(pp, (k, x))を電子署名の署名回路とすれば、kは署名鍵、xはメッセージ、yは署名となる。
【００１８】
［鍵カプセル化方式（KEM: Key Encapsulation Mechanism）］
鍵カプセル化方式とは、以下の４つ組からなる。
・Setup(1к)はセットアップアルゴリズムであり、セキュリティパラメータ1кを入力とし、共通パラメータppを出力する。
・GenKEM(pp)は鍵生成アルゴリズムであり、共通パラメータppを入力とし、公開鍵pkと秘密鍵skとの鍵ペア(pk, sk)を生成する。
・Encaps(pp, pk; s)は鍵暗号化アルゴリズムであり、共通パラメータppと公開鍵pkとを入力とし、秘密情報s∈Sに基づいた鍵kとその暗号文cとを出力する。ここで、Sは秘密情報が属する集合を表す。なお、特許文献１ではEncapsをEncaps1とEncaps2とに分離していたが、本発明ではその必要はない。
・Decaps(pp, sk, c)は鍵復号アルゴリズムであり、共通パラメータppと秘密鍵skと暗号文cとを入力とし、鍵kまたは⊥を出力する。なお、⊥は拒絶を表す情報である。
【００１９】
［公開鍵暗号方式（PKE: Public-Key Encryption）］
公開鍵暗号方式は、以下の４つ組からなる。
・Setup(1к)はセットアップアルゴリズムであり、セキュリティパラメータ1кを入力とし、共通パラメータppを出力する。
・GenPKE(pp)は鍵生成アルゴリズムであり、共通パラメータppを入力とし、暗号化鍵ekと復号鍵dkとの鍵ペア(ek, dk)を生成する。
・EncPKE(pp, ek, m; ρ)は暗号化アルゴリズムであり、共通パラメータppと暗号化鍵ekとメッセージmとを入力とし、乱数ρ∈RPKEに基づいて、メッセージmの暗号文Xを出力する。ここで、RPKEは乱数空間を表す。
・DecPKE(pp, dk, X)は復号アルゴリズムであり、共通パラメータppと復号鍵dkと暗号文Xとを入力とし、メッセージmまたは⊥を出力する。
【００２０】
［共通鍵暗号方式（SKE: Symmetric-Key Encryption）］
共通鍵暗号方式は、以下の３つ組からなる。
・Setup(1к)はセットアップアルゴリズムであり、セキュリティパラメータ1кを入力とし、共通パラメータppを出力する。
・EncSKE(pp, ξ, m; λ)は暗号化アルゴリズムであり、共通パラメータppと一時鍵ξとメッセージmとを入力とし、乱数λ∈RSKEに基づいて、メッセージmの暗号文μを出力する。ここで、RSKEは乱数空間を表す。
・DecSKE(pp, ξ, μ)は復号アルゴリズムであり、共通パラメータppと一時鍵ξと暗号文μとを入力とし、メッセージmまたは⊥を出力する。
【００２１】
［非対話零知識証明（NIZK: Non-Interactive Zero-Knowledge）］
Bを二項関係とし、LをBから定義される言語とする。すなわち、L={x∈{0,1}*: B(x,w)=1 for some w}である。x∈Lのとき対応するwを証拠と呼ぶ。
【００２２】
非対話零知識証明とは３つ組みのアルゴリズムであり、NIZK=(G, P, V)と書く。
・G(1к)はセットアップアルゴリズムであり、セキュリティパラメータ1кを入力とし、CRS（Common Reference String）と呼ばれる共通パラメータcrsNIZKを出力する。
・P(crsNIZK, x, w)は証明者アルゴリズムであり、共通パラメータcrsNIZKと、文字列x∈L⊆{0,1}*と、その証拠wとを入力とし、x∈Lの証明πを出力する。
・V(crsNIZK, x, π)は検証者アルゴリズムであり、共通パラメータcrsNIZKと文字列xと証明πとを入力とし、yes（合格）またはno（不合格）のいずれか一方を出力する。
【００２３】
［双線形写像］
双線形写像e:GK×GK→GTは、双線型性、非退化性、および効率的計算可能性を持つ写像である。ただし、GK, GTは位数が素数qである可換群である。
【００２４】
双線型性により、任意のh1, h2∈GKおよび任意のα, β∈Zqについて、e(h1α, h2β)=e(h1, h2)αβとなる。非退化性により、h1≠1G∈GKであれば、e(h1, h1)のGTでの位数がqとなる。効率的計算可能性により、eを効率よく計算することができる。なお、Zqはqによる剰余群を表す。双線形写像の例はペアリングである。
【００２５】
［衝突困難性（衝突耐性）を持つ写像］
写像Hが衝突困難性を持つとは、多項式時間で動作する敵が、写像の属からそれに属する写像Hを定める情報とセキュリティパラメータ1кとを受け取ったときγ≠δかつH(γ)=H(δ)なる組(γ, δ)を無視できる確率でしか出力することができないことを表す。衝突困難性を持つ写像Hの例は、SHA-1等の暗号学的なハッシュ関数などである。通常、衝突困難性を持つ写像は一方向性も持つ。
【００２６】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２７】
［第一実施形態］
第一実施形態の安全性強化システムおよび方法は、暗号学的デバイス（Setup, Gen, C, X, Y, K）の安全性を強化するものである。本形態の安全性強化装置は、非対話零知識証明NIZK=(G, P, V)を用いて補助情報を生成する。この補助情報は、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密の鍵に対応する第３暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文と第３暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文と第３暗号文とに対する非対話零知識証明検証を行い、さらに秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定する。本形態と特許文献１の従来技術との主たる相違点は、入力される秘密の鍵に対応する第３暗号文を補助情報に含む点である。
【００２８】
＜構成＞
本形態の安全性強化システムは、例えば、図１に示すように、設定装置１１、安全性強化装置１２、および検証装置１３を含む。設定装置１１、安全性強化装置１２、および検証装置１３は通信網１０を介して相互に通信可能に接続される。通信網１０は、例えば、インターネットやWAN（Wide Area Network）、LAN（Local Area Network）、専用線、公衆交換電話網、携帯電話通信網などで構成することができる。設定装置１１、安全性強化装置１２、および検証装置１３は必ずしも通信網１０を介してオンラインで通信可能である必要はなく、例えば、磁気テープやUSBメモリのような可搬型記録媒体を通じて、オフラインで情報の入出力が可能なように構成してもよい。
【００２９】
設定装置１１は、例えば、図２Ａに示すように、共通パラメータ生成部１１１、NIZK設定部１１２、KEM設定部１１３、PKE設定部１１４、および出力部１１５を含む。
【００３０】
安全性強化装置１２は、例えば、図２Ｂに示すように、入力部１２１、乱数生成部１２２、秘密情報生成部１２３、一時鍵生成部１２４、第一暗号化部１２５、第二暗号化部１２６、証明生成部１２７、および出力部１２８を含む。
【００３１】
検証装置１３は、例えば、図２Ｃに示すように、入力部１３１、検証部１３２、一時鍵制御部１３３、暗号文比較部１３４、鍵制御部１３５、および出力部１３６を含む。
【００３２】
設定装置１１、安全性強化装置１２、および検証装置１３は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。設定装置１１、安全性強化装置１２、および検証装置１３は、例えば、中央演算処理装置の制御のもとで各処理を実行する。設定装置１１、安全性強化装置１２、および検証装置１３に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。また、設定装置１１、安全性強化装置１２、および検証装置１３の各処理部の少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００３３】
＜セットアップ処理＞
図３Ａを参照して、本形態のセットアップ処理の手続きを説明する。
【００３４】
ステップＳ１１１において、設定装置１１の共通パラメータ生成部１１１は、セキュリティパラメータ1кを入力として、セットアップアルゴリズムSetup(1к)を実行し、共通パラメータppを得る。共通パラメータppは、（公開鍵型）暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通するものとする。
【００３５】
ステップＳ１１２において、設定装置１１のNIZK設定部１１２は、セキュリティパラメータ1кを入力として、非対話零知識証明のセットアップアルゴリズムG(1к)を実行し、共通パラメータcrsNIZKを得る。
【００３６】
ステップＳ１１３において、設定装置１１のKEM設定部１１３は、鍵カプセル化方式の鍵生成アルゴリズムGenKEM(pp)を実行し、公開鍵pkと秘密鍵skの鍵ペア(pk, sk)を得る。
【００３７】
ステップＳ１１４において、設定装置１１のPKE設定部１１４は、公開鍵暗号方式の鍵生成アルゴリズムGenPKE(pp)を実行し、暗号化鍵ekと復号鍵dkの鍵ペア(ek, dk)を得る。
【００３８】
ステップＳ１１５において、設定装置１１の出力部１１５は、共通パラメータppと公開鍵pkと暗号化鍵ekと共通パラメータcrsNIZKとを含む共通パラメータcrs=(pp, pk, ek, crsNIZK)を出力する。共通パラメータcrsは、安全性強化装置１２および検証装置１３へ送信され、それぞれの記憶部に格納される。これは、複数の安全性強化装置１２および検証装置１３が存在する構成において、共通パラメータcrsが共有されることを想定しているためである。
【００３９】
＜安全性強化処理＞
図３Ｂを参照して、本形態の安全性強化処理の手続きを説明する。
【００４０】
ステップＳ１２１において、安全性強化装置１２の入力部１２１へ、共通パラメータcrs=(pp, pk, ek, crsNIZK)と秘密の鍵k∈Kとが入力される。ここで、Kは鍵空間である。共通パラメータcrsは記憶部へ格納される。
【００４１】
ステップＳ１２２において、安全性強化装置１２の乱数生成部１２２は、乱数ρ∈RPKE、乱数λ∈RSKEを生成する。ここで、RPKEは公開鍵暗号方式の乱数空間であり、RSKEは共通鍵暗号方式の乱数空間である。
【００４２】
ステップＳ１２３において、安全性強化装置１２の秘密情報生成部１２３は、秘密情報s∈Sを生成する。ここで、Sは秘密情報の属する空間である。
【００４３】
ステップＳ１２４において、安全性強化装置１２の一時鍵生成部１２４は、共通パラメータppと公開鍵pkと秘密情報sとを用いて、鍵カプセル化方式の鍵暗号化アルゴリズムEncaps(pp, pk, s)を実行し、秘密情報sに対応する一時鍵ξとその暗号文c（以下、第１暗号文と呼ぶ。）とを得る。
【００４４】
ステップＳ１２５において、安全性強化装置１２の第一暗号化部１２５は、共通パラメータppと暗号化鍵ekと秘密情報sと乱数ρとを用いて、公開鍵暗号方式の暗号化アルゴリズムEncPKE(pp, ek, s; ρ)を実行し、秘密情報sの暗号文X（以下、第２暗号文と呼ぶ。）を得る。
【００４５】
ステップＳ１２６において、安全性強化装置１２の第二暗号化部１２６は、共通パラメータppと一時鍵ξと秘密の鍵kと乱数λとを用いて、共通鍵暗号方式の暗号化アルゴリズムEncSKE(pp, ξ, k; λ)を実行し、秘密の鍵kの暗号文μ（以下、第３暗号文と呼ぶ。）を得る。
【００４６】
ステップＳ１２７において、安全性強化装置１２の証明生成部１２７は、共通パラメータpp, crsNIZKと、暗号文c, X, μに対応する文字列x=(c, X, μ)と、その証拠wである証拠情報(s, ρ, λ, k)とを入力とし、非対話零知識証明の証明者アルゴリズムP(pp, crsNIZK, (c, X, μ), (s, ρ, λ, k))を実行し、その証明である証明情報πを得る。なお、文字列xの例は、c, X, μのビット列表現値のビット結合値である。証拠情報(s, ρ, λ, k)の例は、s, ρ, λ, kのビット列表現値のビット結合値である。また、非対話零知識証明の二項関係Bppを次式のように定義する。
Bpp={((c, X, μ),(s, ρ, λ, k))|∃ξ: ((c, ξ)=Encaps(pp, pk; s)∧(X=EncPKE(pp, ek, s; p))∧(μ=EncSKE(pp, ξ, k; λ)))}
【００４７】
ステップＳ１２８において、安全性強化装置１２の出力部１２８は、暗号文c, X, μと証明情報πとを含む補助情報aux=(c, X, μ, π)および秘密情報sを出力する。
【００４８】
＜検証処理＞
図３Ｃを参照して、本形態の検証処理の手続きを説明する。
【００４９】
ステップＳ１３１において、検証装置１３の入力部１３１へ、共通パラメータcrs=(pp, pk, ek, crsNIZK)と補助情報aux=(c, X, μ, π)と秘密鍵sとが入力される。共通パラメータcrsと補助情報auxと秘密鍵sとは記憶部へ格納される。
【００５０】
ステップＳ１３２において、検証装置１３の検証部１３２は、共通パラメータppと共通パラメータcrsNIZKと暗号文(c, X, μ)と証明情報πとを入力とし、非対話零知識証明の検証者アルゴリズムV(pp, crsNIZK, (c, X, μ), π)を実行し、証明情報πを用いた暗号文(c, X, μ)に対する非対話零知識証明検証を行う。検証に合格した場合（すなわち、検証結果が「yes」）には、ステップＳ１３３へ処理を進める。検証に不合格であった場合（すなわち、検証結果が「no」）には、ステップＳ１３６ｂへ処理を進める。
【００５１】
ステップＳ１３３において、検証装置１３の一時鍵制御部１３３は、共通パラメータppと公開鍵pkと秘密情報sとを用いて、鍵カプセル化方式の鍵暗号化アルゴリズムEncaps(pp, pk; s)を実行し、秘密情報sに対応する一時鍵ξ’とその検証用暗号文c’とを得る。
【００５２】
ステップＳ１３４において、検証装置１３の暗号文比較部１３４は、第１暗号文cと検証用暗号文c’とが一致するか否かを判定する。一致する場合（すなわち、c=c’）には、ステップＳ１３５へ処理を進める。一致しない場合（すなわち、c≠c’）には、ステップＳ１３６ｂへ処理を進める。
【００５３】
ステップＳ１３５において、検証装置１３の鍵制御部１３５は、共通パラメータppと一時鍵ξ’と第３暗号文μとを用いて、共通鍵暗号方式の復号アルゴリズムDecSKE(pp, ξ’, μ)を実行し、秘密の鍵k’を得る。
【００５４】
ステップＳ１３６ａにおいて、検証装置１３の出力部１３６は、秘密の鍵k’を出力して処理を終了する。ステップＳ１３６ｂにおいて、検証装置１３の出力部１３６は、検証が失敗した旨を示す情報（例えば、「⊥」）を出力して処理を終了する。
【００５５】
特許文献１に記載された従来の安全性強化技術では、安全性強化処理の中で秘密の鍵kを生成していた。本形態では、外部から入力された秘密の鍵kを共通鍵暗号方式の平文として扱い、補助情報に含める。これにより、秘密の鍵kは既存のものが利用でき選択の自由度が高くなっている。
【００５６】
［第二実施形態］
第二実施形態の安全性強化システムおよび方法は、暗号学的デバイス（Setup, Gen, C, X, Y, K）として、K=GTとし、双線形写像を用いたものの安全性を強化するものである。本形態の安全性強化装置では、h, z, V, Wが群GKの元、gが群GKの生成元、Hが衝突困難性を持つ写像、e: GK2→GTが双線形写像であり、秘密情報が乱数σに対するs=hσ∈GKであり、一時鍵がξ=e(z, s)∈GTであり、補助情報がX=gσ∈GKと、TG=(V・WH(X, μ))σ∈GKと、一時鍵ξを共通鍵として乱数λを用いて秘密の鍵kを暗号化した暗号文μとを含む。本形態の検証装置は、e(g, TG)∈GTとe(X, V・WH(X, μ))∈GTとが一致し、かつ、e(g, s)∈GTとe(X, h)∈GTとが一致するか否かを判定する。
【００５７】
＜構成＞
本形態の安全性強化システムは、例えば、図１に示すように、設定装置２１、安全性強化装置２２、および検証装置２３を含む。設定装置２１、安全性強化装置２２、および検証装置２３は通信網１０もしくは可搬型記録媒体を介して相互に情報の入出力が可能なように構成される。
【００５８】
設定装置２１は、例えば、図４Ａに示すように、共通パラメータ生成部２１１、乱数生成部２１２、および出力部２１３を含む。
【００５９】
安全性強化装置２２は、例えば、図４Ｂに示すように、入力部２２１、乱数生成部２２２、秘密情報生成部２２３、一時鍵生成部２２４、第一暗号化部２２５、第二暗号化部２２６、群演算部２２７、および出力部２２８を含む。
【００６０】
検証装置２３は、例えば、図４Ｃに示すように、入力部２３１、第一検証部２３２、第二検証部２３３、一時鍵制御部２３４、鍵制御部２３５、および出力部２３６を含む。
【００６１】
＜セットアップ処理＞
図５Ａを参照して、本形態のセットアップ処理の手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【００６２】
ステップＳ２１１において、設定装置２１の共通パラメータ生成部２１１は、セキュリティパラメータ1кを入力として、セットアップアルゴリズムSetup(1к)を実行し、共通パラメータpp=(GK, GT, q, e, g, H)を得る。ここで、Hは衝突困難性を持つ写像H: {0, 1}*→Zqである。写像Hの例は、SHA-1等の暗号学的なハッシュ関数などである。
【００６３】
ステップＳ２１２において、設定装置２１の乱数生成部２１２は、群GKの元h, z, V, W∈GKをランダムに選択する。
【００６４】
ステップＳ２１３において、設定装置２１の出力部２１３は、共通パラメータppと群要素h, z, V, Wとを含む共通パラメータcrs=(pp, h, z, V, W)を出力する。共通パラメータcrsは、第一実施形態と同様に、安全性強化装置２２および検証装置２３へ送信され、それぞれの記憶部に格納される。
【００６５】
＜安全性強化処理＞
図５Ｂを参照して、本形態の安全性強化処理の手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【００６６】
ステップＳ２２１において、安全性強化装置２２の入力部２２１へ、共通パラメータcrs=(pp, h, z, V, W)と秘密の鍵k∈Kとが入力される。共通パラメータcrsは記憶部へ格納される。
【００６７】
ステップＳ２２２において、安全性強化装置２２の乱数生成部２２２は、乱数σ∈Zq、乱数λ∈RSKEを生成する。
【００６８】
ステップＳ２２３において、安全性強化装置２２の秘密情報生成部２２３は、群要素hと乱数σとを用いて、乱数σに対する秘密情報s=hσ∈GKを計算する。
【００６９】
ステップＳ２２４において、安全性強化装置２２の一時鍵生成部２２４は、共通パラメータppと群要素zと秘密情報sとを用いて、一時鍵ξ=e(z, s)∈GTを計算する。また、一時鍵ξは共通鍵暗号の一時鍵生成アルゴリズムに合わせてξ^=KDF(ξ)∈{0, 1}кと適切な関数を用いて変形してもよい。ここで、KDFはKey Derivation Functionであり、入力された秘密の値から鍵を導出する関数である。
【００７０】
ステップＳ２２５において、安全性強化装置２２の第一暗号化部２２５は、共通パラメータppと一時鍵ξと秘密の鍵kと乱数λとを用いて、共通鍵暗号方式の暗号化アルゴリズムEncSKE(pp, ξ, k; λ)を実行し、秘密の鍵kの暗号文μを得る。
【００７１】
ステップＳ２２６において、安全性強化装置２２の第二暗号化部２２６は、共通パラメータppと乱数σとを用いて、暗号文X=gσ∈GKを計算する。
【００７２】
ステップＳ２２７において、安全性強化装置２２の群演算部２２７は、共通パラメータppと乱数σと暗号文Xと暗号文μとを用いて、暗号文TG=(V・WH(X, μ))σ∈GKを計算する。
【００７３】
ステップＳ２２８において、安全性強化装置２２の出力部２２８は、暗号文X, TG, μを含む補助情報aux=(X, μ, TG)および秘密情報sを出力する。
【００７４】
＜検証処理＞
図５Ｃを参照して、本形態の検証処理の手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【００７５】
ステップＳ２３１において、検証装置２３の入力部２３１へ、共通パラメータcrs=(pp, h, z, V, W)と補助情報aux=(X, μ, TG)と秘密鍵sとが入力される。共通パラメータcrsと補助情報auxと秘密鍵sとは記憶部へ格納される。
【００７６】
ステップＳ２３２において、検証装置２３の第一検証部２３２は、e(g, TG)∈GTとe(X, V・WH(X, μ))∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, TG)=e(X, V・WH(X, μ))）には、ステップＳ２３３へ処理を進める。一致しない場合（すなわち、e(g, TG)≠e(X, V・WH(X, μ))）には、ステップＳ２３６ｂへ処理を進める。
【００７７】
ステップＳ２３３において、検証装置２３の第二検証部２３３は、e(g, s)∈GTとe(X, h)∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, s)=e(X, h)）には、ステップＳ２３４へ処理を進める。一致しない場合（すなわち、e(g, s)≠e(X, h)）には、ステップＳ２３６ｂへ処理を進める。
【００７８】
ステップＳ２３４において、検証装置２３の一時鍵制御部２３４は、共通パラメータppと群要素zと秘密情報sとを用いて、一時鍵ξ’=e(z, s)∈GTを計算する。
【００７９】
ステップＳ２３５において、検証装置２３の鍵制御部２３５は、共通パラメータppと一時鍵ξ’と暗号文μとを用いて、共通鍵暗号方式の復号アルゴリズムDecSKE(pp, ξ’, μ)を実行し、秘密の鍵k’を得る。
【００８０】
ステップＳ２３６ａにおいて、検証装置２３の出力部２３６は、秘密の鍵k’を出力して処理を終了する。ステップＳ２３６ｂにおいて、検証装置２３の出力部２３６は、検証が失敗した旨を示す情報（例えば、「⊥」）を出力して処理を終了する。
【００８１】
［第三実施形態］
第三実施形態の安全性強化システムおよび方法は、公開鍵型暗号学的デバイス（Setup, Gen, C, X, Y, K, Ω）として、Waters IDベース暗号を用いたものの安全性を強化する。本形態では、補助情報auxに含まれるX=gσ∈GKおよびTG=(V・WH(X))σ∈GKをマスター公開鍵mpkとして流用し、秘密情報s=hσ∈GKをマスター秘密鍵（鍵情報）mskとして用いる。これにより、補助情報auxのサイズを小さくできる。
【００８２】
＜構成＞
本形態の安全性強化システムは、例えば、図６に示すように、設定装置３１、鍵生成装置３２、送信装置３３、および受信装置３４を含む。設定装置３１、鍵生成装置３２、送信装置３３、および受信装置３４は通信網１０もしくは可搬型記録媒体を介して相互に情報の入出力が可能なように構成される。
【００８３】
設定装置３１は、例えば、図７Ａに示すように、共通パラメータ生成部３１１、乱数生成部３１２、および出力部３１３を含む。
【００８４】
鍵生成装置３２は、例えば、図７Ｂに示すように、入力部３２１、乱数生成部３２２、秘密情報生成部３２３、公開鍵生成部３２４、補助情報生成部３２５、第一検証部３２６、第二検証部３２７、鍵制御部３２８、および出力部３２９を含む。
【００８５】
送信装置３３は、例えば、図８Ａに示すように、入力部３３１、検証部３３２、暗号化部３３３、および出力部３３４を含む。
【００８６】
受信装置３４は、例えば、図８Ｂに示すように、入力部３４１、復号部３４２、および出力部３４３を含む。
【００８７】
本形態の安全性強化システムにおいては、鍵生成装置３２が安全性強化装置および検証装置の役割を兼ねている。また、送信装置３３と受信装置３４は鍵生成装置３２により強化された鍵を用いて暗号化された通信を行う。
【００８８】
＜セットアップ処理＞
図９Ａを参照して、本形態のセットアップ処理の手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【００８９】
ステップＳ３１１において、設定装置３１の共通パラメータ設定部３１１は、セキュリティパラメータ1кを入力として、セットアップアルゴリズムSetup(1к)を実行し、共通パラメータpp=(GK, GT, q, e, g, H)を得る。
【００９０】
ステップＳ３１２において、設定装置３１の乱数生成部３１２は、群GKの元h, V, W, Y0, Y1, …, Yn∈GKをランダムに選択する。
【００９１】
ステップＳ３１３において、設定装置３１の出力部３１３は、共通パラメータppと群要素h, V, W, Y0, Y1, …, Ynと写像H’を含む共通パラメータcrs=(pp, h, V, W, Y0, Y1, …, Yn, H’)を出力する。H’は衝突困難性を持つ写像H’: {0, 1}*→{0, 1}nである。共通パラメータcrsは、鍵生成装置３２へ送信され、記憶部に格納される。
【００９２】
＜マスター鍵生成処理＞
図９Ｂを参照して、本形態のマスター鍵生成処理の手続きを説明する。
【００９３】
ステップＳ３２１ａにおいて、鍵生成装置３２の入力部３２１へ、共通パラメータcrs=(pp, h, V, W, Y0, Y1, …, Yn, H’)が入力される。共通パラメータcrsは記憶部へ格納される。
【００９４】
ステップＳ３２２において、鍵生成装置３２の乱数生成部３２２は、乱数σ∈Zqを選択する。
【００９５】
ステップＳ３２３において、鍵生成装置３２の秘密情報生成部３２３は、乱数σを用いて、マスター秘密鍵s=gσ∈GKを計算する。
【００９６】
ステップＳ３２４において、鍵生成装置３２の公開鍵生成部３２４は、乱数σを用いて、公開鍵X=gσ∈GKを計算する。
【００９７】
ステップＳ３２５において、鍵生成装置３２の補助情報生成部３２５は、群要素V, Wと乱数σと暗号文Xとを用いて、補助情報TG=(V・WH(X))σ∈GKを計算する。
【００９８】
ステップＳ３２９ａにおいて、鍵生成装置３２の出力部３２９は、公開鍵Xと補助情報TGとを含むマスター公開鍵mpk=(X, TG)およびマスター秘密鍵msk=sを出力する。
【００９９】
＜ユーザ鍵生成処理＞
図９Ｃを参照して、本形態のユーザ鍵生成処理の手続きを説明する。
【０１００】
ステップＳ３２１ｂにおいて、鍵生成装置３２の入力部３２１へ、マスター秘密鍵msk=sとユーザのID∈{0, 1}*が入力される。
【０１０１】
ステップＳ３２６において、鍵生成装置３２の第一検証部３２６は、IDを(X, TG, id)に分解し、e(g, TG)∈GTとe(X, V・WH(X))∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, TG)=e(X, V・WH(X))）には、ステップＳ３２７へ処理を進める。一致しない場合（すなわち、e(g, TG)≠e(X, V・WH(X))）には、ステップＳ３２９ｃへ処理を進める。
【０１０２】
ステップＳ３２７において、鍵生成装置３２の第二検証部３２７は、e(g, s)∈GTとe(h, X)∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, s)=e(h, X)）には、ステップＳ３２８へ処理を進める。一致しない場合（すなわち、e(g, s)≠e(h, X)）には、ステップＳ３２９ｃへ処理を進める。
【０１０３】
ステップＳ３２８において、鍵生成装置３２の鍵制御部３２８は、乱数d∈Zqを選択し、値Z=(Z1,…,Zn)=H’(ID)∈{0, 1}nを計算し、IDに対応するユーザ秘密鍵dkID=(D1, D2)を次式により計算する。
【０１０４】
【数１】
0006267657.tif 000002
【０１０５】
ステップＳ３２９ｂにおいて、鍵生成装置３２の出力部３２９は、ユーザ秘密鍵dkID=(D1, D2)を出力して処理を終了する。ステップＳ３２９ｃにおいて、鍵生成装置３２の出力部３２９は、鍵生成に失敗した旨を示す情報（例えば、「⊥」）を出力して処理を終了する。
【０１０６】
＜暗号化処理＞
図１０Ａを参照して、本形態の暗号化処理の手続きを説明する。
【０１０７】
ステップＳ３３１において、送信装置３３の入力部３３１へ、共通パラメータcrs=(pp, h, V, W, Y0, Y1, …, Yn, H’)とマスター公開鍵mpk=(X, TG)とユーザのID∈{0, 1}*とメッセージm∈GTとが入力される。
【０１０８】
ステップＳ３３２において、送信装置３３の検証部３３２は、IDを(X’, TG’, id)に分解し、(X, TG)と(X’, TG’)とが一致するか否かを判定する。一致する場合（すなわち、(X, TG)=(X’, TG’)）には、ステップＳ３３３へ処理を進める。一致しない場合（すなわち、(X, TG)≠(X’, TG’)）には、ステップＳ３３４ｂへ処理を進める。
【０１０９】
ステップＳ３３３において、送信装置３３の暗号化部３３３は、乱数d∈Zqを選択し、値Z=(Z1,…,Zn)=H’(ID)∈{0, 1}nを計算し、メッセージmの暗号文c=(c1, c2, c3)を次式により計算する。
【０１１０】
【数２】
0006267657.tif 000003
【０１１１】
ステップＳ３３４ａにおいて、送信装置３３の出力部３３４は、暗号文c=(c1, c2, c3)を出力して処理を終了する。ステップＳ３３４ｂにおいて、送信装置３３の出力部３３４は、暗号化に失敗した旨を示す情報（例えば、「⊥」）を出力して処理を終了する。
【０１１２】
＜復号処理＞
図１０Ｂを参照して、本形態の復号処理の手続きを説明する。
【０１１３】
ステップＳ３４１において、受信装置３４の入力部３４１へ、共通パラメータcrs=(pp, h, V, W, Y0, Y1, …, Yn, H’)とマスター公開鍵mpk=(X, TG)とユーザ秘密鍵dkID=(D1, D2)∈GK2と暗号文c=(c1, c2, c3)∈GK2×GTが入力される。
【０１１４】
ステップＳ３４２において、受信装置３４の復号部３４２は、メッセージmを次式により計算する。
【０１１５】
【数３】
0006267657.tif 000004
【０１１６】
ステップＳ３４３において、受信装置３４の出力部３４３は、メッセージmを出力して処理を終了する。
【０１１７】
［第四実施形態］
第四実施形態の安全性強化システムおよび方法は、公開鍵型暗号学的デバイス（Setup, Gen, C, X, Y, K, Ω）として、Boyen-Mei-Waters鍵カプセル化方式を用いたものの安全性を強化する。本形態の補助情報はX=gσ∈GKとTG=(V・WH(X))σ∈GKに加えて、R=hρ∈GKとT=(Y・WH’(X, TG, R))ρ∈GKとを含む。ただし、V, Wは群GKの元であり、σ, ρは乱数である。本形態の検証装置は、e(g, TG)とe(X, V・WH(X))とが一致するかを判定し、e(g, s)とe(h, X)とが一致するかを判定し、さらにe(g, T)とe(R, V・WH’(X, TG, R))とが一致するかを判定する。
【０１１８】
＜構成＞
本形態の安全性強化システムは、例えば、図１１に示すように、設定装置４１、送信装置４２、および受信装置４３を含む。設定装置４１、送信装置４２、および受信装置４３は通信網１０もしくは可搬型記録媒体を介して相互に情報の入出力が可能なように構成される。
【０１１９】
設定装置４１は、例えば、図１２Ａに示すように、共通パラメータ生成部４１１、乱数生成部４１２、および出力部４１３を含む。
【０１２０】
送信装置４２は、例えば、図１２Ｂに示すように、入力部４２１、乱数生成部４２２、一時鍵生成部４２３、第一暗号化部４２４、第二暗号化部４２５、および出力部４２６を含む。
【０１２１】
受信装置４３は、例えば、図１２Ｃに示すように、入力部４３１、乱数生成部４３２、秘密情報生成部４３３、公開鍵生成部４３４、補助情報生成部４３５、第一検証部４３６、第二検証部４３７、第三検証部４３８、鍵制御部４３９、および出力部４４０を含む。
【０１２２】
本形態の安全性強化システムにおいては、受信装置４３が安全性強化装置および検証装置の役割を兼ねている。また、送信装置４２と受信装置４３は受信装置４３により強化された鍵を用いて暗号化された通信を行う。
【０１２３】
＜セットアップ処理＞
図１３Ａを参照して、本形態のセットアップ処理の手続きを説明する。
【０１２４】
ステップＳ４１１において、設定装置４１の共通パラメータ設定部４１１は、セキュリティパラメータ1кを入力として、セットアップアルゴリズムSetup(1к)を実行し、共通パラメータpp=(GK, GT, q, e, g, H)を得る。
【０１２５】
ステップＳ４１２において、設定装置４１の乱数生成部４１２は、群GKの元h, V, W, Y∈GKをランダムに選択する。
【０１２６】
ステップＳ４１３において、設定装置４１の出力部４１３は、共通パラメータppと群要素h, V, W, Yと写像H’を含む共通パラメータcrs=(pp, h, V, W, Y, H’)を出力する。本形態のH’は衝突困難性を持つ写像H’: GK3→Zqである。共通パラメータcrsは、受信装置４３へ送信され、記憶部に格納される。
【０１２７】
＜鍵生成処理＞
図１３Ｂを参照して、本形態の鍵生成処理の手続きを説明する。
【０１２８】
ステップＳ４３１ａにおいて、受信装置４３の入力部４３１へ、共通パラメータcrs=(pp, h, V, W, Y, H’)が入力される。共通パラメータcrsは記憶部へ格納される。
【０１２９】
ステップＳ４３２において、受信装置４３の乱数生成部４３２は、乱数σ∈Zqを選択する。
【０１３０】
ステップＳ４３３において、受信装置４３の秘密情報生成部４３３は、乱数σを用いて、秘密鍵s=gσ∈GKを計算する。
【０１３１】
ステップＳ４３４において、受信装置４３の公開鍵生成部４３４は、乱数σを用いて、公開鍵X=gσ∈GKを計算する。
【０１３２】
ステップＳ４３５において、受信装置４３の補助情報生成部４３５は、共通パラメータppと乱数σと暗号文Xとを用いて、補助情報TG=(V・WH(X))σ∈GKを計算する。
【０１３３】
ステップＳ４４０ａにおいて、受信装置４３の出力部４４０は、公開鍵Xと補助情報TGとを含む公開鍵pk=(X, TG)および秘密鍵sk=sを出力する。
【０１３４】
＜暗号化処理＞
図１４Ａを参照して、本形態の暗号化処理の手続きを説明する。
【０１３５】
ステップＳ４２１ｂにおいて、送信装置４２の入力部４２１へ、公開鍵pk=(X, TG)∈GK2が入力される。
【０１３６】
ステップＳ４２２において、送信装置４２の乱数生成部４２２は、乱数ρ∈Zqを選択する。
【０１３７】
ステップＳ４２３において、送信装置４２の一時鍵生成部４２３は、乱数ρを用いて、一時鍵ξ=e(X, h)ρを計算する。
【０１３８】
ステップＳ４２４において、送信装置４２の第一暗号化部４２４は、乱数ρを用いて、暗号文R=gρを計算する。
【０１３９】
ステップＳ４２５において、送信装置４２の第二暗号化部４２５は、共通パラメータppと乱数ρと暗号文X, TG, Rを用いて、暗号文T=(V・WH’(X, TG, R))ρ∈GKを計算する。
【０１４０】
ステップＳ４２６において、送信装置４２の出力部４２６は、一時鍵ξとその暗号文c=(X, TG, R, T)∈GK4とを出力する。
【０１４１】
＜復号処理＞
図１４Ｂを参照して、本形態の復号処理の手続きを説明する。
【０１４２】
ステップＳ４３１において、送信装置４２の入力部４３１へ、秘密鍵sk=s∈GKと暗号文c=(X, TG, R, T)とが入力される。
【０１４３】
ステップＳ４３６において、送信装置４２の第一検証部４３６は、e(g, TG)∈GTとe(X, V・WH(X))∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, TG)=e(X, V・WH(X))）には、ステップＳ４３７へ処理を進める。一致しない場合（すなわち、e(g, TG)≠e(X, V・WH(X))）には、ステップＳ４４０ｃへ処理を進める。
【０１４４】
ステップＳ４３７において、送信装置４２の第二検証部４３７は、e(g, s)∈GTとe(h, X)∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, s)=e(h, X)）には、ステップＳ４３８へ処理を進める。一致しない場合（すなわち、e(g, s)≠e(h, X)）には、ステップＳ４４０ｃへ処理を進める。
【０１４５】
ステップＳ４３８において、送信装置４２の第三検証部４３８は、e(g, T)∈GTとe(R, V・WH’(X, TG, R))∈GTとが一致するか否かを判定する。一致する場合（すなわち、e(g, T)= e(R, V・WH’(X, TG, R))）には、ステップＳ４３９へ処理を進める。一致しない場合（すなわち、e(g, T)≠e(R, V・WH’(X, TG, R))）には、ステップＳ４４０ｃへ処理を進める。
【０１４６】
ステップＳ４３９において、送信装置４２の鍵制御部４３９は、一時鍵k’=e(R, s)∈GTを計算する。
【０１４７】
ステップＳ４４０ｂにおいて、送信装置４２の出力部４４０は、一時鍵k’を出力して処理を終了する。ステップＳ４４０ｃにおいて、送信装置４２の出力部４４０は、復号に失敗した旨を示す情報（例えば、「⊥」）を出力して処理を終了する。
【０１４８】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１４９】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１５０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１５１】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１５２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１５３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１５４】
１１、２１、３１、４１  設定装置
１２、２２  安全性強化装置
１３、２３  検証装置
３２  鍵生成装置
３３、４２  送信装置
３４、４３  受信装置
【図１】
0006267657.tif 000005
【図２】
0006267657.tif 000006
【図３】
0006267657.tif 000007
【図４】
0006267657.tif 000008
【図５】
0006267657.tif 000009
【図６】
0006267657.tif 000010
【図７】
0006267657.tif 000011
【図８】
0006267657.tif 000012
【図９】
0006267657.tif 000013
【図１０】
0006267657.tif 000014
【図１１】
0006267657.tif 000015
【図１２】
0006267657.tif 000016
【図１３】
0006267657.tif 000017
【図１４】
0006267657.tif 000018