(57)【要約】【課題】回路を自壊させることなく、任意の回路の関連鍵攻撃に対する安全性を向上させる。【解決手段】安全性強化時に、鍵情報に対応する秘密情報に対して特定の対応関係を持つ補助情報を得て出力する。ただし、この秘密情報と異なる関連秘密情報に対して当該対応関係を持つ関連補助情報を当該補助情報から特定することは困難である。検証時に、入力された補助情報が秘密情報に対して特定の対応関係を持つかを判定し、当該補助情報が秘密情報に対して当該対応関係を持つ場合に秘密情報に対応する鍵情報または当該鍵情報から得られる情報を得、当該補助情報が秘密情報に対して当該対応関係を持たない場合に拒絶を表す情報を出力する。【選択図】図１
2014135687.tif 000002
【特許請求の範囲】
【請求項１】
秘密の鍵情報に対応する秘密情報を格納する記憶部と、
前記秘密情報に対して特定の対応関係を持つ補助情報を得て出力する補助情報生成部と、を有し、
前記秘密情報と異なる関連秘密情報に対して前記対応関係を持つ関連補助情報を前記補助情報から特定することが困難である、
ことを特徴とする安全性強化装置。
【請求項２】
請求項１の安全性強化装置であって、
前記補助情報が、前記秘密情報に対応する第１暗号文と、前記秘密情報と乱数とに対応する第２暗号文と、前記秘密情報と前記乱数とを証拠情報として前記第１暗号文と前記第２暗号文とに対する非対話零知識証明を行うための証明情報と、を含む、
ことを特徴とする安全性強化装置。
【請求項３】
請求項１の安全性強化装置であって、
ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが前記群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅが双線形写像であり、
前記秘密情報が、乱数σに対するｓ＝ｈσであり、
前記鍵情報が、ｅ（ｚ，ｓ）を含み、
前記補助情報が、Ｘ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σとを含む、
ことを特徴とする安全性強化装置。
【請求項４】
請求項２または３の安全性強化装置であって、
前記補助情報が、さらに、前記秘密情報に対応する公開鍵を含む、
ことを特徴とする安全性強化装置。
【請求項５】
請求項１の安全性強化装置であって、
ｈ、ＶおよびＷが群ＧＫの元、ｇが前記群ＧＫの生成元、Ｈが衝突困難性を持つ写像であり、
前記秘密情報が、乱数σに対するｓ＝ｈσであり、
前記鍵情報が、ｓを含み、
前記補助情報が、Ｘ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σとを含む、
ことを特徴とする安全性強化装置。
【請求項６】
請求項５の安全性強化装置であって、
ｖ、ｗが前記群ＧＫの元であり、
前記補助情報が、さらに、第２乱数ρに対するＲ＝ｈρとＴ＝（ｖ・ｗＨ（Ｒ））ρとを含む、
ことを特徴とする安全性強化装置。
【請求項７】
入力された補助情報が秘密情報に対して特定の対応関係を持つかを判定する判定部と、
前記補助情報が前記秘密情報に対して前記対応関係を持つ場合に前記秘密情報に対応する秘密の鍵情報または前記鍵情報から得られる情報を得、前記補助情報が前記秘密情報に対して前記対応関係を持たない場合に拒絶を表す情報を出力する鍵制御部と、を有し、
前記秘密情報と異なる関連秘密情報に対して前記対応関係を持つ関連補助情報を前記補助情報から特定することが困難である、
ことを特徴とする検証装置。
【請求項８】
請求項７の検証装置であって、
前記補助情報が、第１暗号文と、第２暗号文と、前記第１暗号文と前記第２暗号文とに対する非対話零知識証明を行うための証明情報と、を含み、
前記判定部が、前記証明情報を用いて前記第１暗号文と前記第２暗号文とに対する非対話零知識証明検証を行う検証部と、
前記秘密情報に対応する検証用暗号文と前記第１暗号文とが一致するかを判定する暗号文比較部と、を含む、
ことを特徴とする検証装置。
【請求項９】
請求項７の検証装置であって、
ｈ、Ｖ、Ｗ、ＸおよびＴＧが群ＧＫの元、ｇが前記群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅが双線形写像、ｓが前記秘密情報であり、
前記補助情報が、ＸとＴＧとを含み、
前記判定部が、
ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致するかを判定する第１比較部と、
ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致するかを判定する第２比較部と、を含む、
ことを特徴とする検証装置。
【請求項１０】
請求項８または９の検証装置であって、
前記補助情報が、さらに公開鍵を含み、
前記判定部が、さらに、前記秘密情報に対応する検証用公開鍵と前記公開鍵とが一致するかを判定する公開鍵比較部を含む、
ことを特徴とする検証装置。
【請求項１１】
請求項９の検証装置であって、
前記鍵情報が前記秘密情報ｓを含む、
ことを特徴とする検証装置。
【請求項１２】
請求項１１の検証装置であって、
ｖ、ｗ、ＲおよびＴが前記群ＧＫの元であり、
前記補助情報が、さらにＲとＴとを含み、
ｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致するかを判定する第３比較部と、を含む、
ことを特徴とする検証装置。
【請求項１３】
請求項１から６の何れかの安全性強化装置としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項７から１２の何れかの検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の分野における安全性強化技術に関し、特に関連鍵攻撃に対する安全性を強化する技術に関する。
【背景技術】
【０００２】
秘密情報を持つ一般の暗号学的な回路（以下、単に「回路」という）への関連鍵攻撃に対する（アルゴリズム的な）安全性強化手法がいくつか提案されている（例えば、非特許文献１から５等参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Rosario Gennaro, Anna Lysyanskaya, Tal Malkin, Silvio Micali, and Tal Rabin, “Algorithmic tamper-proof (ATP) security: Theoretical foundations for security against hardware tampering,” in Moni Naor, editor, TCC 2004, volume 2951 of Lecture Notes in Computer Science, pages 258-277, Springer, Heidelberg, 2004.
【非特許文献２】Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs, “Non-malleable codes,” in Andrew Chi-Chih Yao, editor, ICS 2010, pages 434-452, Tsinghua University Press, 2010.
【非特許文献３】Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and DavidWagner, “Private circuits ii: Keeping secrets in tamperable circuits,” in Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 308-327, Springer, Heidelberg, 2006.
【非特許文献４】Sebastian Faust, Krzysztof Pietrzak, and Daniele Venturi, “Tamper-proof circuits: How to trade leakage for tamper-resilience,” In Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP 2011, Part I, volume 6755 of Lecture Notes in Computer Science, pages 391-402, Springer-Verlag, 2011.
【非特許文献５】Dana Dachman-Soled and Yael Tauman Kalai. Securing circuits against constant-rate tampering. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 533-551, Springer, Heidelberg, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１では、任意の関連鍵攻撃に対する安全性強化手法が提案されている。しかしながら、非特許文献１の強化手法は信頼できる第三者を必要とする。この第三者は公開鍵を公開し、暗号デバイスを作成するたびにこの第三者が関わる必要がある。また、この強化手法では、ひとたび関連鍵攻撃を検知すると回路は自壊してしまう。
【０００５】
非特許文献２では、一部の関連鍵攻撃に対する安全性強化手法が提案されている。非特許文献２の強化手法は信頼できる第三者を必要としない。しかしながら、この強化手法でも、ひとたび関連鍵攻を検知すると回路は自壊してしまう。
【０００６】
非特許文献３から５の強化手法は自壊を必要としない。しかしながら、回路および秘密への変更箇所に制限を加えており、任意の関数をとらえていない。
【０００７】
このように、回路を自壊させることなく、任意の回路の関連鍵攻撃に対する安全性を向上させる手法は提案されていない。
【課題を解決するための手段】
【０００８】
安全性強化時に、鍵情報に対応する秘密情報に対して特定の対応関係を持つ補助情報を得て出力する。ただし、この秘密情報と異なる関連秘密情報に対して当該対応関係を持つ関連補助情報を当該補助情報から特定することは困難である。
【０００９】
検証時に、入力された補助情報が秘密情報に対して特定の対応関係を持つかを判定し、当該補助情報が秘密情報に対して当該対応関係を持つ場合に秘密情報に対応する鍵情報または当該鍵情報から得られる情報を得、当該補助情報が秘密情報に対して当該対応関係を持たない場合に拒絶を表す情報を出力する。
【発明の効果】
【００１０】
本発明では、秘密情報に対して特定の対応関係を持つ補助情報を用いる。上記の関連補助情報を補助情報から特定することは困難である。これにより、任意の回路の関連鍵攻撃に対する安全性を向上させることができる。また本発明では、回路を自壊させる必要はない。
【図面の簡単な説明】
【００１１】
【図１】図１は、第１，２実施形態の安全性強化システムの構成を説明するためのブロック図である。
【図２】図２Ａは、第１実施形態の安全性強化処理を説明するためのフロー図であり、図２Ｂは、第１実施形態の検証処理を説明するためのフロー図である。
【図３】図３Ａは、第２実施形態の安全性強化処理を説明するためのフロー図であり、図３Ｂは、第２実施形態の検証処理を説明するためのフロー図である。
【図４】図４は、第３，４実施形態の安全性強化システムの構成を説明するためのブロック図である。
【図５】図５Ａは、第３実施形態の安全性強化処理を説明するためのフロー図であり、図５Ｂは、第３実施形態の検証処理を説明するためのフロー図である。
【図６】図６Ａは、第４実施形態の安全性強化処理を説明するためのフロー図であり、図６Ｂは、第４実施形態の検証処理を説明するためのフロー図である。
【図７】図７は、第５，６，７実施形態の安全性強化システムの構成を説明するためのブロック図である。
【図８】図８Ａは、第５実施形態の安全性強化処理を説明するためのフロー図であり、図８Ｂは、第５実施形態の検証処理を説明するためのフロー図である。
【図９】図９は、第６実施形態の検証処理を説明するためのフロー図である。
【図１０】図１０Ａは、第７実施形態の安全性強化処理を説明するためのフロー図であり、図１０Ｂは、第７実施形態の検証処理を説明するためのフロー図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態を説明する。
＜定義＞
各実施形態で用いる記号や用語を定義する。
[暗号学的デバイス]
暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）は、以下のＳｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋから構成される。
Ｓｅｔｕｐ（１κ）はセットアップアルゴリズムであり、セキュリティパラメータ１κを入力とし、共通パラメータｐｐを出力する。ｐｐは集合Ｘ，Ｙ，Ｋの情報を含む。
Ｇｅｎ（ｐｐ）は鍵生成アルゴリズムであり、ｐｐを入力とし、秘密の鍵情報ｋ∈Ｋをランダムに選んで出力する。
Ｃ（ｐｐ，（ｋ，ｘ））は回路であり、ｐｐおよび（ｋ，ｘ）∈Ｋ×Ｘを入力とし、ｙ∈Ｙを出力する。
例えばＣ（ｐｐ，（ｋ，ｘ））は共通鍵暗号の復号回路であり、ｋは秘密鍵、ｘは暗号文、ｙは平文に対応する。
【００１３】
[公開鍵型暗号学的デバイス]
公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）は、以下のＳｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ωから構成される。
Ｓｅｔｕｐ（１κ）はセットアップアルゴリズムであり、セキュリティパラメータ１κを入力とし、共通パラメータｐｐを出力する。ｐｐは集合Ｘ，Ｙ，Ｋ，Ωの情報を含む。
Ｇｅｎ（ｐｐ；ｒ）は鍵生成アルゴリズムであり、ｐｐを入力とし、乱数ｒ∈Ωに基づいて、秘密の鍵情報ｋ∈Ｋと公開の鍵情報ｐを出力する。
Ｃ（ｐｐ，（ｋ，ｘ））は回路であり、ｐｐおよび（ｋ，ｘ）∈Ｋ×Ｘを入力とし、ｙ∈Ｙを出力する。
例えばＣ（ｐｐ，（ｋ，ｘ））は公開鍵暗号の復号回路であり、ｋは復号鍵、ｐは暗号鍵、ｘは暗号文、ｙは平文に対応する。他にもＣ（ｐｐ，（ｋ，ｘ））を電子署名の署名回路とすれば、ｋは署名鍵、ｐは検証鍵、ｘはメッセージ、ｙは署名となる。
【００１４】
[鍵カプセル化方式（Key Encapsulation Mechanism (KEM)）]
鍵カプセル化方式は、以下の４つ組からなる。
Ｓｅｔｕｐ（１κ）はセットアップアルゴリズムであり、セキュリティパラメータ１κを入力とし、共通パラメータｐｐを出力する。
ＧｅｎＫＥＭ（ｐｐ）は鍵生成アルゴリズムであり、ｐｐを入力とし、公開鍵ｐｋと秘密鍵ｓｋとの鍵ペア（ｐｋ，ｓｋ）を生成する。
Ｅｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）は、鍵暗号化アルゴリズムであり、ｐｐとｐｋを入力とし、秘密情報ｓ∈Ｓに基づいた鍵ｋとその暗号文ｃとを出力する。Ｓは秘密情報が属する集合を表す。以下では簡単のため、Ｅｎｃａｐｓ（ｐｐ，ｐｋ）をＥｎｃａｐｓ１（ｐｐ，ｐｋ；ｓ）とＥｎｃａｐｓ２（ｐｐ；ｓ）とに分離して表記する。Ｅｎｃａｐｓ１（ｐｐ，ｐｋ；ｓ）は暗号文ｃを出力するアルゴリズムであり、Ｅｎｃａｐｓ２（ｐｐ；ｓ）は鍵ｋを出力するアルゴリズムである。
Ｄｅｃａｐｓ（ｐｐ，ｓｋ，ｃ）は、鍵復号アルゴリズムであり、ｐｐとｓｋとｃを入力とし、鍵ｋまたは⊥を出力する。なお、⊥は拒絶を表す情報である。
【００１５】
[公開鍵暗号方式（Public-Key Encryption (PKE)）]
公開鍵暗号方式は、以下の４つ組からなる。
Ｓｅｔｕｐ（１κ）はセットアップアルゴリズムであり、セキュリティパラメータ（１κ）を入力とし、共通パラメータｐｐを出力する。
ＧｅｎＰＫＥ（ｐｐ）は鍵生成アルゴリズムであり、ｐｐを入力とし、暗号化鍵ｅｋと復号鍵ｄｋとの鍵ペア（ｅｋ，ｄｋ）を生成する。
Ｅｎｃ（ｐｐ，ｅｋ，ｍ；ρ）は暗号化アルゴリズムであり、ｐｐとｅｋとメッセージｍを入力にとり、乱数ρ∈ＲＰＫＥに基づいてメッセージｍの暗号文ｃｍを得て出力する。ＲＰＫＥは乱数空間を表す。
Ｄｅｃａｐｓ（ｐｐ，ｄｋ，ｃｍ）は復号アルゴリズムであり、ｐｐとｄｋとｃｍを入力にとり、メッセージｍまたは⊥を出力する。
【００１６】
[非対話零知識証明（Non-Interactive Zero-Knowledge (NIZK)）]
Ｂを二項関係とし、ＬをＢから定義される言語とする。すなわち、Ｌ＝｛ｘ∈｛０，１｝*：Ｂ（ｘ，ｗ）＝１  ｆｏｒ  ｓｏｍｅ  ｗ｝である。ｘ∈Ｌのときに対応するｗを証拠と呼ぶ。
非対話零知識証明とは三つ組みのアルゴリズムであり、ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ）と書く。
Ｇ（１κ）はセットアップアルゴリズムであり、セキュリティパラメータ１κを入力とし、ＣＲＳ(Common Reference String)と呼ばれる共通パラメータｃｒｓＮＩＺＫを出力する。なお、１κはκ個の１からなる列を表す。κは１以上の所定の整数である。
Ｐ（ｃｒｓＮＩＺＫ，ｘ，ｗ）は証明者アルゴリズムであり、共通パラメータｃｒｓＮＩＺＫと、文字列ｘ∈Ｌ⊆｛０，１｝*と、その証拠ｗを入力とし、ｘ∈Ｌの証明πを出力する。
Ｖ（ｃｒｓＮＩＺＫ，ｘ，π）は検証者アルゴリズムであり、共通パラメータｃｒｓＮＩＺＫと、文字列ｘと、証明πを入力とし、ｙｅｓ（合格）／ｎｏ（不合格）を出力する。
【００１７】
［双線形写像］
双線形写像ｅ：ＧＫ×ＧＫ→ＧＴは、双線形性、非退化性および効率的計算可能性を持つ写像である。ただし、ＧＫ，ＧＴは位数が素数ｑである可換群である。
双線形性により、任意のｈ１，ｈ２∈ＧＫおよび任意のα，β∈Ｚｑについてｅ（ｈ１α，ｈ２β）＝ｅ（ｈ１，ｈ２）αβとなる。非退化性により、ｅ（ｈ１，ｈ１）のＧＴでの位数がｑとなる。効率的計算可能性により、ｅを効率よく計算することができる。なお、Ｚｑはｑによる剰余群を表す。双線形写像の例はペアリングである。
【００１８】
［衝突困難性（衝突耐性）を持つ写像］
写像Ｈが衝突困難性を持つとは、多項式時間で動作する敵が、写像の属からそれに属する写像Ｈを定める情報とセキュリティパラメータ１κとを受け取ったとき、γ≠δかつＨ（γ）＝Ｈ（δ）なる組（γ，δ）を無視できる確率でしか出力することができないことを表す。衝突困難性を持つ写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。通常、衝突困難性を持つ写像は一方向性も持つ。
【００１９】
＜原理＞
各実施形態に共通する原理を説明する。
安全性強化装置では、秘密の鍵情報に対応する秘密情報を格納し、秘密情報に対して特定の対応関係を持つ補助情報を得て出力する。ただし、当該秘密情報と異なる関連秘密情報に対して当該対応関係を持つ関連補助情報を当該補助情報から特定することは困難である。
【００２０】
検証装置では、入力された補助情報が秘密情報に対して特定の対応関係を持つかを判定し、当該補助情報が秘密情報に対して当該対応関係を持つ場合に秘密情報に対応する秘密の鍵情報または当該鍵情報から得られる情報を得、当該補助情報が秘密情報に対して当該対応関係を持たない場合に拒絶を表す情報を出力する。
【００２１】
以上の構成では、秘密情報に対して特定の対応関係を持つ補助情報を用いる。上記の関連補助情報を補助情報から特定することは困難である。これにより自壊することなく、任意の回路の関連鍵攻撃に対する安全性を向上させることができる。本構成は任意の回路に汎用的に適用可能であるが、ここでは特定の従来構成に対する関連鍵攻撃を例示し、その関連鍵攻撃がこの原理を適用した方式に通じないことを示す。
【００２２】
[従来の公開鍵型暗号学的デバイスの一例]
以下に従来の公開鍵型暗号学的デバイスを例示する。
Ｓｅｔｕｐ（１κ）は、セキュリティパラメータ１κを入力とし、ＧＫとｑと生成元ｇ１，ｇ２∈ＧＫと衝突困難性を持つ写像Ｈ：ＧＫ３→Ｚｑとを得、共通パラメータｐｐ＝（ＧＫ，ｑ，ｇ１，ｇ２，Ｈ）として出力する。
Ｇｅｎ（ｐｐ；ｒ）は、ｐｐを入力とし、秘密情報ｓである鍵情報ｄｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と公開情報である鍵情報ｅｋ＝（Ｘｅｋ，Ｙｅｋ，Ｚｅｋ）＝（ｇ１ｘ１・ｇ２ｘ２，ｇ１ｙ１・ｇ２ｙ２，ｇ１ｚ１・ｇ２ｚ２）とを得て出力する。
Ｅｎｃ（ｐｐ；ｅｋ，ｍ）は、ｐｐとｅｋとメッセージｍとを入力とし、乱数ｒ’∈Ｚｑを生成し、ｃ１＝ｇ１ｒ’，ｃ２＝ｇ２ｒ’，Ｅ＝ｍ・Ｚｅｋｒ’，ω＝Ｈ（ｃ１，ｃ２，Ｅ），ν＝（Ｘｅｋω・Ｙｅｋ）ｒ’を得て、暗号文ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）を出力する。
Ｄｅｃ（ｐｐ；ｄｋ，ｃｔ）は、ｐｐとｄｋとｃｔとを入力とし、ｃｔ∈ＧＫ４であれば、ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）からω＝Ｈ（ｃ１，ｃ２，Ｅ）を得、さらにｃ１ｘ１*ω+ｙ１・ｃ２ｘ２*ω+ｙ２＝νであれば、ｍ＝Ｅ／（ｃ１ｚ１・ｃ２ｚ２）を出力する。
【００２３】
[従来構成に対する関連鍵攻撃の一例]
上記の従来の公開鍵型暗号学的デバイスに対し、以下の一方向性を破る関連鍵攻撃が成功する。
１．敵はメッセージｍの暗号文ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）を受け取る。
２．敵は０以外のΔ∈Ｚｑを選択し、鍵情報ｄｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を関連鍵情報φ（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）＝（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）に移す写像φと、新しい暗号文ｃｔ’＝（ｃ１，ｃ２，Ｅ，ν・ｃ１Δ）をＤｅｃに問い合わせる。
３．Ｄｅｃは鍵情報ｄｋに写像φを適用し、関連鍵情報（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）を得、それを用いてｃｔ’を復号し、メッセージｍを敵に返す。
４．敵はｍをそのまま出力する。
【００２４】
この例では秘密情報が鍵情報である。また、上述の原理を上述の公開鍵型暗号学的デバイスの一例に適用する場合には、例えば、Ｄｅｃに検証装置を組み込んで機能させる。鍵情報および関連鍵情報は秘密情報であり、敵はこれらの情報を知らない。また敵は、鍵情報（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）に対する補助情報を知ったとしても、関連鍵情報（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）に対する補助情報（秘密情報と異なる関連秘密情報に対して特定の対応関係を持つ関連補助情報）を得ることができない。よって敵は、関連鍵情報に対する補助情報をＤｅｃに与えることができない。そのため検証装置は、Ｄｅｃからの問い合わせに対して拒絶を返し、Ｄｅｃは敵に対して拒絶を返す。その結果、敵は暗号文ｃｔ’＝（ｃ１，ｃ２，Ｅ，ν’）を復号することができず、メッセージｍも得ることができない。
【００２５】
＜第１実施形態＞
第１実施形態を説明する。本形態は、暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）に上述の原理を適用したものである。本形態の安全性強化装置は、非対話零知識証明（ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ））を用いて補助情報を生成する。この補助情報は、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文とに対する非対話零知識証明検証を行い、さらに秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定する。
【００２６】
［構成］
図１に例示するように、本形態の安全性強化システム１は、設定装置１１０と安全性強化装置１２０と検証装置１３０とを有する。設定装置１１０と安全性強化装置１２０と検証装置１３０とは、それぞれ、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）等を含む汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置１１０と安全性強化装置１２０と検証装置１３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００２７】
安全性強化装置１２０は、例えば、暗号化を行う際に用いる鍵を得る鍵生成装置である（暗号学的デバイスに上述の原理を適用する以降の実施形態の安全性強化装置についても同様）。安全性強化装置１２０は、入力部１２１と記憶部１２２と補助情報生成部１２３と出力部１２４とを有する。補助情報生成部１２３は、乱数生成部１２３ａと鍵・鍵暗号文生成部１２３ｂと暗号化部１２３ｃと証明生成部１２３ｄとを有する。安全性強化装置１２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
【００２８】
検証装置１３０は、例えば、暗号文を復号する際に用いる鍵を得る鍵生成装置である（暗号学的デバイスに上述の原理を適用する以降の実施形態の検証装置についても同様）。検証装置１３０は、入力部１３１と記憶部１３２と判定部１３３と鍵制御部１３６と出力部１３７とを有する。判定部１３３は、検証部１３３ａと鍵暗号文生成部１３３ｂと暗号文比較部１３３ｃとを有する。検証装置１３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００２９】
[セットアップ処理]
設定装置１１０は、セキュリティパラメータ（１κ）を入力としてセットアップアルゴリズムＳｅｔｕｐ（１κ）を実行し、共通パラメータｐｐを得る。この共通パラメータｐｐは、暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通することとする。また設定装置１１０は、セキュリティパラメータ（１κ）を入力として非対話零知識証明のセットアップアルゴリズムＧ（１κ）を実行し、共通パラメータｃｒｓＮＩＺＫを得る。さらに設定装置１１０は、鍵カプセル化方式の鍵生成アルゴリズムＧｅｎＫＥＭ（ｐｐ）を実行し、鍵ペア（ｐｋ，ｓｋ）を得る。また設定装置１１０は、公開鍵暗号方式の鍵生成アルゴリズムＧｅｎＰＫＥ（ｐｐ）を実行し、鍵ペア（ｅｋ，ｄｋ）を得る。設定装置１１０は、以上のように得られた共通パラメータｃｒｓ＝（ｐｐ，ｐｋ，ｅｋ，ｃｒｓＮＩＺＫ）を出力する。共通パラメータｃｒｓは、それぞれ、安全性強化装置１２０および検証装置１３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００３０】
また、設定装置１１０はランダムな秘密情報ｓ∈Ｓを生成して出力する。秘密情報ｓは、安全性強化装置１２０および検証装置１３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００３１】
[安全性強化処理（図２Ａ）]
安全性強化装置１２０の乱数生成部１２３ａが、乱数ρ∈ＲＰＫＥを生成して出力する（ステップＳ１２１）。鍵・鍵暗号文生成部１２３ｂが、共通パラメータｐｐと公開鍵ｐｋと秘密情報ｓを用いて鍵暗号化アルゴリズムＥｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）を実行し、鍵（鍵情報）ｋとそれに対応する暗号文ｃ（第１暗号文）とを出力する（ステップＳ１２２）。暗号化部１２３ｃが、共通パラメータｐｐと暗号化鍵ｅｋと秘密情報ｓと乱数ρとを用いて暗号化アルゴリズムＥｎｃ（ｐｐ，ｅｋ，ｍ；ρ）を実行し、秘密情報ｓの暗号文τ（第２暗号文）を得て出力する（ステップＳ１２３）。証明生成部１２３ｄが、共通パラメータｃｒｓＮＩＺＫと、暗号文ｃ，τに対応する文字列ｘ＝（ｃ，τ）と、その証拠ｗである証拠情報（ｓ，ρ）とを入力とし、証明者アルゴリズムＰ（ｃｒｓＮＩＺＫ，（ｃ，τ），（ｓ，ρ））を実行し、その証明である証明情報πを得て出力する。なお、文字列ｘの例は、ｃ，τのビット列表現値のビット結合値である。証拠情報（ｓ，ρ）の例は、ｓ，ρのビット列表現値のビット結合値である。また、非対話零知識証明の二項関係Ｂを以下のように定義する。
Ｂ（ｘ，ｗ）＝｛（（ｃ，τ），（ｓ，ρ））：（（ｃ，*）＝Ｅｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）∧（τ＝Ｅｎｃ（ｐｐ，ｅｋ，ｓ；ρ）））｝
ここで「*」はワイルドカードを表す（ステップＳ１２４）。出力部１２４は、暗号文ｃ，τと証明情報πとを含む補助情報ａｕｘ＝（ｃ，τ，π）を出力する（ステップＳ１２５）。得られた鍵ｋは、例えば共通鍵暗号方式に則って暗号化するための共通鍵として用いられる（暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
【００３２】
[検証処置（図２Ｂ）]
補助情報ａｕｘ＝（ｃ，τ，π）は、検証装置１３０の入力部１３１に入力されて記憶部１３２に格納される。検証部１３３ａが、共通パラメータｃｒｓＮＩＺＫと暗号文ｃ，τと証明情報πとを入力とし、検証者アルゴリズムＶ（ｃｒｓＮＩＺＫ，（ｃ，τ），π）を実行し、証明情報πを用いた暗号文ｃ，τに対する非対話零知識証明検証を行い、その検証結果がｙｅｓであるかを判定する（ステップＳ１３１）。検証結果がｎｏであれば、出力部１３７が⊥を出力し（ステップＳ１３５）、処理を終える。検証結果がｙｅｓであれば、鍵暗号文生成部１３３ｂが、共通パラメータｐｐと公開鍵ｐｋと秘密情報ｓを用い、アルゴリズムＥｎｃａｐｓ１（ｐｐ，ｐｋ；ｓ）を実行し、秘密情報ｓに対応する検証用暗号文ｃ’を得て出力する（ステップＳ１３２）。暗号文比較部１３３ｃが、暗号文ｃと検証用暗号文ｃ’とが一致するかを判定する（ステップＳ１３３）。これらが一致しないと判定された場合（ｃ≠ｃ’）、出力部１３７が⊥を出力し（ステップＳ１３５）、処理を終える。暗号文ｃと検証用暗号文ｃ’とが一致すると判定された場合（ｃ＝ｃ’）、鍵制御部１３６が、共通パラメータｐｐと秘密情報ｓとを用い、アルゴリズムＥｎｃａｐｓ２（ｐｐ；ｓ）を実行し、秘密情報ｓに対応する鍵ｋ’を得て出力する（ステップＳ１３４）。出力部１３７は、鍵（鍵情報）ｋ’を出力し（ステップＳ１３６）、処理を終える。出力された鍵ｋ’は、例えば共通鍵暗号方式に則って復号するための共通鍵として用いられる（暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
【００３３】
＜第２実施形態＞
第２実施形態を説明する。本形態は、公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用したものである。本形態の安全性強化装置は、非対話零知識証明（ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ））を用いて補助情報を生成する。この補助情報は、秘密情報に対応する公開鍵と、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文とに対する非対話零知識証明検証を行い、秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定し、さらに秘密情報に対応する検証用公開鍵と公開鍵とが一致するかを判定する。以降、これまで説明したものと共通する事項については、同じ参照番号を用いて説明を省略する。
【００３４】
［構成］
図１に例示するように、本形態の安全性強化システム２は、設定装置２１０と安全性強化装置２２０と検証装置２３０とを有する。設定装置２１０と安全性強化装置２２０と検証装置２３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置２１０と安全性強化装置２２０と検証装置２３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００３５】
安全性強化装置２２０は、例えば、暗号化や署名を行う際に用いる鍵を得る鍵生成装置またはその一部である（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態の安全性強化装置についても同様）。安全性強化装置２２０は、入力部１２１と記憶部１２２と補助情報生成部２２３と出力部２２４とを有する。補助情報生成部２２３は、乱数生成部１２３ａと鍵・鍵暗号文生成部２２３ｂと暗号化部１２３ｃと証明生成部１２３ｄと鍵ペア生成部２２３ｅとを有する。安全性強化装置２２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
【００３６】
検証装置２３０は、例えば、暗号文の復号や署名検証を行う際に用いる鍵を得る生成装置である（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態の検証装置についても同様）。検証装置２３０は、入力部１３１と記憶部１３２と判定部２３３と鍵制御部２３６と出力部２３７とを有する。判定部２３３は、検証部１３３ａと鍵暗号文生成部１３３ｂと暗号文比較部１３３ｃと公開鍵比較部２３３ｄを有する。検証装置２３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００３７】
[セットアップ処理]
本形態の設定装置２１０のセットアップ処理で生成される共通パラメータｐｐは、公開鍵型暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通するものである。その他のセットアップ処理の内容は第１実施形態の設定装置１１０と同じである。設定装置２１０は、生成した共通パラメータｃｒｓ＝（ｐｐ，ｐｋ，ｅｋ，ｃｒｓＮＩＺＫ）および秘密情報ｓ∈Ｓを出力する。これらはそれぞれ、安全性強化装置２２０および検証装置２３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００３８】
[安全性強化処理（図３Ａ）]
安全性強化装置２２０の乱数生成部１２３ａが第１実施形態で説明したステップＳ１２１の処理を実行した後、鍵・暗号文生成装置２２３ｂが第１実施形態で説明したステップＳ１２２の処理を「ｋ」を「ｒ」に置換して実行し（ステップＳ２２２）、その後、暗号化部１２３ｃおよび証明生成部１２３ｄが第１実施形態で説明したステップＳ１２３およびＳ１２４の処理を実行する。次に安全性強化装置２２０の鍵ペア生成部２２３ｅが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、公開鍵ｐと秘密鍵ｋ（鍵情報）との鍵ペア（ｐ，ｋ）を得て出力する。ただし、ｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）は、共通パラメータｐｐと秘密情報ｓを入力とし、鍵カプセル化方式のアルゴリズムＥｎｃａｐｓ２（ｐｐ；ｓ）を実行して鍵ｒを得、公開鍵型暗号学的デバイスの鍵生成アルゴリズムＧｅｎ（ｐｐ；ｒ）を実行して、秘密鍵ｋ∈Ｋと公開鍵ｐを得て出力するアルゴリズムである。ただし、鍵ｒを新たに得るのではなく、ステップＳ２２２で得られた鍵ｒがｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）で流用されてもよい（ステップＳ２２４）。出力部２２４は、公開鍵ｐと暗号文ｃ，τと証明情報πとを含む補助情報ａｕｘ＝（ｐ，ｃ，τ，π）を出力する（ステップＳ２２５）。得られた秘密鍵ｋは、例えば公開鍵暗号方式に則って暗号化するために用いられる（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
【００３９】
[検証処置（図３Ｂ）]
補助情報ａｕｘ＝（ｐ，ｃ，τ，π）は、検証装置２３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ１３１〜Ｓ１３３，Ｓ１３５の処理が第１実施形態で説明した通りに実行される。ステップＳ１３３で暗号文ｃと検証用暗号文ｃ’とが一致すると判定された場合（ｃ＝ｃ’）、公開鍵比較部２３３ｄが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報に対応する検証用公開鍵ｐ’と秘密鍵ｋ’との鍵ペア（ｐ’，ｋ’）を得る（ステップＳ２３３）。さらに公開鍵比較部２３３ｄは、検証用公開鍵ｐ’と公開鍵ｐとが一致するかを判定する（ステップＳ２３４）。これらが一致しないと判定された場合（ｐ≠ｐ’）、出力部２３７が⊥を出力し（ステップＳ１３５）、処理を終える。一方、検証用公開鍵ｐ’と公開鍵ｐとが一致すると判定された場合（ｐ＝ｐ’）、鍵制御部２３６が、秘密鍵ｋ’を出力部２３７に送り、出力部２３７は秘密鍵ｋ’（鍵情報）を出力し（ステップＳ２３６）、処理を終える。出力された秘密鍵ｋ’は、例えば公開鍵暗号方式に則って復号するためや署名生成に用いられる（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
【００４０】
＜第３実施形態＞
第３実施形態を説明する。本形態は、暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）として、Ｋ＝ＧＴとし、双線形写像を用いたものに上述の原理を適用したものである。本形態では、ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅ：ＧＫ２→ＧＴが双線形写像であり、秘密情報が乱数σに対するｓ＝ｈσ∈ＧＫであり、鍵情報がｅ（ｚ，ｓ）∈ＧＴを含み、補助情報がＸ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫとを含む。本形態の検証装置は、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定し、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定する。
【００４１】
［構成］
図３に例示するように、本形態の安全性強化システム３は、設定装置３１０と安全性強化装置３２０と検証装置３３０とを有する。設定装置３１０と安全性強化装置３２０と検証装置３３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置３１０と安全性強化装置３２０と検証装置３３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００４２】
安全性強化装置３２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と鍵生成部３２５と補助情報生成部３２６と出力部３２７とを有する。補助情報生成部３２６は、群演算部３２６ａ，３２６ｂを有する。安全性強化装置３２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
【００４３】
検証装置３３０は、入力部１３１と記憶部１３２と判定部３３３と鍵制御部３３６と出力部３３７とを有する。判定部３３３は、比較部３３３ａ，３３３ｂを有する。検証装置３３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００４４】
[セットアップ処理]
設定装置３１０は、セキュリティパラメータ（１κ）を入力としてセットアップアルゴリズムＳｅｔｕｐ（１κ）を実行し、共通パラメータｐｐとして、ＧＫ，ＧＴ，ｑ，ｅ，ｇと衝突困難性を持つ写像Ｈ：ＧＫ→Ｚｑとを得、ｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）とする。写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。また設定装置３１０は、群ＧＫの元ｈ，ｚ，Ｖ，Ｗ∈ＧＫをランダムに選び、ｃｒｓ＝（ｐｐ，ｈ，ｚ，Ｖ，Ｗ）を出力する。共通パラメータｃｒｓは、それぞれ、安全性強化装置３２０および検証装置３３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００４５】
[安全性強化処理（図５Ａ）]
安全性強化装置３２０の乱数生成部３２３は、ｐｐを入力として乱数σ∈Ｚｑを選択して出力する（ステップＳ３２１）。秘密情報生成部３２４は、ｐｐ，σを入力とし、乱数σに対する秘密情報ｓ＝ｈσ∈ＧＫを得て出力する（ステップＳ３２２）。鍵生成部３２５は、ｐｐ，ｚ，ｓを入力とし、秘密の鍵（鍵情報）ｋ＝ｅ（ｚ，ｓ）∈ＧＴを生成して出力する（ステップＳ３２３）。群演算部３２６ａは、ｐｐ，σを入力としてＸ＝ｇσ∈ＧＫを得て出力する（ステップＳ３２４）。群演算部３２６ｂは、ｐｐ，Ｘ，σを入力としてＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫを得て出力する（ステップＳ３２５）。出力部３２７は、ＸとＴＧとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓを出力する（ステップＳ３２６）。
【００４６】
[検証処置（図５Ｂ）]
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓは、検証装置３３０の入力部１３１に入力されて記憶部１３２に格納される。比較部３３３ａは、ｐｐ，ａｕｘを入力とし、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定する（ステップＳ３３１）。これらが一致しないと判定された場合（ｅ（ｇ，ＴＧ）≠ｅ（Ｘ，Ｖ・ＷＨ（Ｘ）））、出力部３３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致すると判定された場合（ｅ（ｇ，ＴＧ）＝ｅ（Ｘ，Ｖ・ＷＨ（Ｘ）））、比較部３３３ａは、ｐｐ，ｓを入力とし、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定する（ステップＳ３３２）。これらが一致しないと判定された場合（ｅ（ｇ，ｓ）≠ｅ（Ｘ，ｈ））、出力部３３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部３３６がｐｐ，ｚ，ｓを入力とし、秘密の鍵（鍵情報）ｋ’＝ｅ（ｚ，ｓ）∈ＧＴを生成し（ステップＳ３３４）、出力部３３７が鍵ｋを出力する（ステップＳ３３６）。
【００４７】
＜第４実施形態＞
第４実施形態を説明する。本形態は、公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）として、Ｋ＝ＧＴとし、双線形写像を用いたものに上述の原理を適用したものである。本形態では、ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅ：ＧＫ２→ＧＴが双線形写像であり、秘密情報が乱数σに対するｓ＝ｈσ∈ＧＫであり、鍵情報がｅ（ｚ，ｓ）∈ＧＴを含み、補助情報が秘密情報ｓに対応する公開鍵とＸ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫとを含む。本形態の検証装置は、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定し、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定し、さらに秘密情報に対応する検証用公開鍵と公開鍵とが一致するかを判定する。
【００４８】
［構成］
図４に例示するように、本形態の安全性強化システム４は、設定装置４１０と安全性強化装置４２０と検証装置４３０とを有する。設定装置４１０と安全性強化装置４２０と検証装置４３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置４１０と安全性強化装置４２０と検証装置４３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００４９】
安全性強化装置４２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と補助情報生成部４２６と出力部４２７とを有する。補助情報生成部４２６は、鍵生成部４２６ｃと群演算部３２６ａ，３２６ｂとを有する。安全性強化装置４２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
【００５０】
検証装置４３０は、入力部１３１と記憶部１３２と判定部４３３と鍵制御部４３６と出力部４３７とを有する。判定部４３３は、比較部３３３ａ，３３３ｂと公開鍵比較部４３３ｃとを有する。検証装置４３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００５１】
[セットアップ処理]
本形態の設定装置４１０は、第３実施形態の共通パラメータｐｐに加え、さらに公開鍵型暗号学的デバイスの共通パラメータを生成し、それらを共通パラメータｐｐとして、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を得る。その他のセットアップ処理の内容は第３実施形態の設定装置３１０と同じである。設定装置４１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を出力し、共通パラメータｃｒｓは、それぞれ、安全性強化装置４２０および検証装置４３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００５２】
[安全性強化処理（図６Ａ）]
安全性強化装置４２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行する。鍵生成部４２６ｃが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報ｓに対応する公開鍵ｐと秘密鍵ｋ（鍵情報）との鍵ペア（ｐ，ｋ）を得て出力する（ステップＳ４２３）。その後、第３実施形態で説明したステップＳ３２４およびＳ３２５と同じ処理が実行され、出力部４２７は、ｐとＸとＴＧとを含む補助情報ａｕｘ＝（ｐ，Ｘ，ＴＧ）と秘密情報ｓを出力する（ステップＳ４２６）。
【００５３】
[検証処置（図６Ｂ）]
補助情報ａｕｘ＝（ｐ，Ｘ，ＴＧ）と秘密情報ｓは、検証装置４３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、公開鍵比較部４３３ｃが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報ｓに対応する検証用公開鍵ｐ’と秘密鍵ｋ’（鍵情報）との鍵ペア（ｐ’，ｋ’）を得る。公開鍵比較部４３３ｃは、検証用公開鍵ｐ’と公開鍵ｐとが一致するかを判定する（ステップＳ４３４）。検証用公開鍵ｐ’と公開鍵ｐとが一致しないと判定された場合（ｐ≠ｐ’）、出力部４３７が⊥を出力し（ステップＳ１３５）、処理を終える。検証用公開鍵ｐ’と公開鍵ｐとが一致すると判定された場合（ｐ＝ｐ’）、鍵制御部４３６が、秘密鍵ｋ’を出力部４３７に送り、出力部４３７が秘密鍵ｋ’（鍵情報）を出力し（ステップＳ４３６）、処理を終える。
【００５４】
＜第５実施形態＞
第５実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、補助情報ａｕｘの一部であるＸ＝ｇσ∈ＧＫを公開鍵ｐとして流用する。すなわち、本形態の公開鍵ｐは補助情報ａｕｘの一部であるＸ＝ｇσを含み、これに対応する秘密鍵ｋ（鍵情報）は秘密情報ｓ＝ｈσ∈ＧＫを含む。これにより、補助情報ａｕｘのサイズを第４実施形態よりも小さくできる。
【００５５】
［構成］
図７に例示するように、本形態の安全性強化システム５は、設定装置５１０と安全性強化装置５２０と検証装置５３０とを有する。設定装置５１０と安全性強化装置５２０と検証装置５３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置５１０と安全性強化装置５２０と検証装置５３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００５６】
安全性強化装置５２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と補助情報生成部５２６と出力部５２７とを有する。補助情報生成部５２６は、群演算部３２６ａ，３２６ｂを有する。安全性強化装置５２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
【００５７】
検証装置５３０は、入力部１３１と記憶部１３２と判定部３３３と鍵制御部５３６と出力部５３７とを有する。検証装置５３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００５８】
[セットアップ処理]
本形態の設定装置５１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を得る。設定装置５１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を出力する。ｃｒｓは、それぞれ、安全性強化装置５２０および検証装置５３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００５９】
[安全性強化処理（図８Ａ）]
安全性強化装置５２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行する。ただし、ステップＳ３２２で得られた秘密情報ｓは秘密鍵（鍵情報）として機能する。その後、補助情報生成部５２６の群演算部３２６ａおよび３２６ｂが、第３実施形態で説明したステップＳ３２４およびＳ３２５の処理を実行し、Ｘ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫを得て出力する。ただし、出力部５２４は、ＸとＴＧとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓを出力する。ただし、Ｘは補助情報として用いられるだけではなく、さらに暗号化処理等に公開鍵として用いられる（ステップＳ３２６）。
【００６０】
[検証処置（図８Ｂ）]
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓと暗号化対象のメッセージｘが、検証装置５３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部５３６が、秘密情報ｓを秘密鍵ｋ’とし、メッセージｘに対する暗号文ＣＰＰ（ｓ，ｘ）（鍵情報から得られる情報）を得（ステップＳ５３４）、出力部５３７が当該暗号文ＣＰＰ（ｓ，ｘ）を出力し（ステップＳ５３６）、処理を終える。なお、ステップＳ５３４で暗号文ＣＰＰ（ｓ，ｘ）を得、ステップＳ５３６で当該暗号文ＣＰＰ（ｓ，ｘ）を出力する代わりに、ステップＳ５３４で秘密情報ｓを秘密鍵ｋ’とし、ステップＳ５３６で秘密鍵ｋ’（鍵情報）を出力してもよい。
【００６１】
＜第６実施形態＞
第６実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、公開鍵型暗号学的デバイスとしてＷａｔｅｒｓ ＩＤベース暗号を用い、さらに補助情報ａｕｘであるＸ＝ｇσ∈ＧＫおよびＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫをマスター公開鍵ｍｐｋとして流用し、秘密情報ｓ＝ｈσ∈ＧＫをマスター秘密鍵（鍵情報）ｍｓｋとして用いる。これにより、補助情報ａｕｘのサイズを第４実施形態よりも小さくできる。
【００６２】
［構成］
図７に例示するように、本形態の安全性強化システム６は、設定装置６１０と安全性強化装置５２０と検証装置６３０とを有する。検証装置６３０は、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置６１０と安全性強化装置５２０と検証装置６３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００６３】
検証装置６３０は、入力部１３１と記憶部１３２と判定部３３３と鍵制御部６３６と出力部６３７とを有する。検証装置６３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００６４】
[セットアップ処理]
本形態の設定装置６１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、さらに群ＧＫからランダムにＹ０，Ｙ１，...，Ｙｎ∈ＧＫを選択し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ，Ｙ０，Ｙ１，...，Ｙｎ）を得る。ただし、ｎは正整数である。設定装置６１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ，Ｙ１，...，Ｙｎ）を出力し、ｃｒｓは、それぞれ、安全性強化装置６２０および検証装置６３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００６５】
[安全性強化処理]
本形態の安全性強化処理は第５実施形態と同じである。ただし、Ｘ＝ｇσおよびＴＧ＝（Ｖ・ＷＨ（Ｘ））σがマスター公開鍵ｍｐｋとして機能し、秘密情報ｓ＝ｈσをマスター秘密鍵（鍵情報）ｍｓｋとして機能する。マスター公開鍵ｍｐｋはＩＤ＝（ＩＤ１，...，ＩＤｎ）∈｛０，１｝ｎに対応する公開鍵の生成に用いられ、マスター秘密鍵ｍｓｋはＩＤに対応する秘密鍵の生成に用いられる。
【００６６】
[検証処置（図９）]
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓとＩＤとが、検証装置５３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部６３６が、共通パラメータｐｐとマスター秘密鍵（鍵情報）ｍｓｋ＝ｓとＩＤとを入力とし、乱数ｄ∈Ｚｑを生成し、ＩＤ＝（ＩＤ１，...，ＩＤｎ）∈｛０，１｝ｎに対応する秘密鍵ｋ’＝ｄｋＩＤ（鍵情報から得られる情報）を以下のように生成する。
ｋ’＝ｄｋＩＤ＝（ｇｄ，ｓ・（ＷａｔＨ（ＩＤ））ｄ）∈ＧＫ２
ただし、ＷａｔＨ（ＩＤ）を
【数１】
2014135687.tif 000003
とする（ステップＳ６３４）。出力部６３７は秘密鍵ｋ’を出力し（ステップＳ６３６）、処理を終える。
【００６７】
＜第７実施形態＞
第７実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、公開鍵型暗号学的デバイスとしてＢｏｙｅｎ−Ｍｅｉ−Ｗａｔｅｒｓ鍵カプセル化方式の変種を用いる。本形態の補助情報はＸ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σに加えてＲ＝ｈρとＴ＝（ｖ・ｗＨ（Ｒ））ρとを含む。ただし、ｖ、ｗが群ＧＫの元であり、ρが乱数である。形態の検証装置は、ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致するかを判定し、ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致するかを判定し、さらにｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致するかを判定する。
【００６８】
［構成］
図７に例示するように、本形態の安全性強化システム７は、設定装置７１０と安全性強化装置７２０と検証装置７３０とを有する。設定装置７１０と安全性強化装置７２０と検証装置７３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置７１０と安全性強化装置７２０と検証装置７３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００６９】
安全性強化装置７２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と補助情報生成部７２６と鍵生成部７２５と出力部７２７とを有する。補助情報生成部７２６は、群演算部３２６ａ，３２６ｂ，７２６ｄ，７２６ｅと乱数生成部７２６ｃを有する。安全性強化装置７２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
【００７０】
検証装置５３０は、入力部１３１と記憶部１３２と判定部７３３と鍵制御部７３６と出力部７３７とを有する。判定部７３３は、比較部３３３ａ，３３３ｂ，７３３ｃを有する。検証装置７３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
【００７１】
[セットアップ処理]
本形態の設定装置７１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、第３実施形態と同じｐｐ，ｈ，Ｖ，Ｗに加え、さらにランダムに元ｖ，ｗ∈ＧＫを選択し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ, v, w）を得る。共通パラメータｃｒｓは、それぞれ、安全性強化装置７２０および検証装置７３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
【００７２】
[安全性強化処理（図１０Ａ）]
安全性強化装置７２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行し、群演算部３２６ａ，３２６ｂが、第３実施形態で説明したステップＳ３２４およびＳ３２５の処理を実行する。次に、乱数生成部７２６ｃが、ｐｐを入力として第２乱数ρ∈Ｚｑを選択して出力する（ステップＳ７２１）。群演算部７２６ｄは、ｐｐ，ρを入力とし、乱数ρに対するＲ＝ｇρ∈ＧＫを得て出力する（ステップＳ７２２）。群演算部７２６ｅは、ｐｐ，ｖ，ｗ，Ｒ，ρを入力とし、Ｔ＝（ｖ・ｗＨ（Ｒ））ρ∈ＧＫを得て出力する（ステップＳ７２３）。鍵生成部７２５は、ｐｐ，Ｘ，ｈ，ρを入力とし、鍵（鍵情報）ｋ＝ｅ（Ｘ，ｈ）ρ∈ＧＫを得て出力する。出力部７２７は、ＸとＴＧとＲとＴとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ，Ｒ，Ｔ）を暗号文とし、当該補助情報ａｕｘと鍵ｋと秘密情報ｓとを出力する（ステップＳ７２６）。
【００７３】
[検証処置（図１０Ｂ）]
補助情報ａｕｘ＝（Ｘ，ＴＧ，Ｒ，Ｔ）と鍵ｋと秘密情報ｓは、検証装置７３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、比較部７３３ｃが、ｅ（ｇ，Ｔ）∈ＧＴとｅ（Ｒ，ｖ・ｗＨ（Ｒ））∈ＧＴとが一致するかを判定する（ステップＳ７３３）。これらが一致しないと判定された場合（ｅ（ｇ，Ｔ）≠ｅ（Ｒ，ｖ・ｗＨ（Ｒ）））、出力部７３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致すると判定された場合（ｅ（ｇ，Ｔ）＝ｅ（Ｒ，ｖ・ｗＨ（Ｒ）））、鍵制御部７３６が、ｐｐ，Ｒ，ｓを入力とし、鍵（鍵情報）ｋ’＝ｅ（Ｒ，ｓ）∈ＧＴを得て出力し、出力部７３７が鍵ｋ’を出力する。
【００７４】
＜その他の変形例等＞
なお、本発明は上述の実施形態に限定されるものではない。例えば、安全性強化装置や検証装置が複数個存在してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７５】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００７６】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００７８】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００７９】
１〜７  安全性強化システム
１１０〜７１０  設定装置
１２０〜７２０  安全性強化装置
１３０〜７３０  検証装置
【図１】
2014135687.tif 000004
【図２】
2014135687.tif 000005
【図３】
2014135687.tif 000006
【図４】
2014135687.tif 000007
【図５】
2014135687.tif 000008
【図６】
2014135687.tif 000009
【図７】
2014135687.tif 000010
【図８】
2014135687.tif 000011
【図９】
2014135687.tif 000012
【図１０】
2014135687.tif 000013