JP5871827B2 - 安全性強化システム、安全性強化装置、検証装置、およびプログラム - Google Patents
安全性強化システム、安全性強化装置、検証装置、およびプログラム Download PDFInfo
- Publication number
- JP5871827B2 JP5871827B2 JP2013003706A JP2013003706A JP5871827B2 JP 5871827 B2 JP5871827 B2 JP 5871827B2 JP 2013003706 A JP2013003706 A JP 2013003706A JP 2013003706 A JP2013003706 A JP 2013003706A JP 5871827 B2 JP5871827 B2 JP 5871827B2
- Authority
- JP
- Japan
- Prior art keywords
- information
- key
- unit
- secret
- verification
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Description
本発明は、情報セキュリティ技術の分野における安全性強化技術に関し、特に関連鍵攻撃に対する安全性を強化する技術に関する。
秘密情報を持つ一般の暗号学的な回路（以下、単に「回路」という）への関連鍵攻撃に対する（アルゴリズム的な）安全性強化手法がいくつか提案されている（例えば、非特許文献１から５等参照）。
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)と呼ばれる共通パラメータｃｒｓＮＩＺＫを出力する。なお、１κはκ個の１からなる列を表す。κは１以上の所定の整数である。
Ｐ（ｃｒｓＮＩＺＫ，ｘ，ｗ）は証明者アルゴリズムであり、共通パラメータｃｒｓＮＩＺＫと、文字列ｘ∈Ｌ⊆｛０，１｝*と、その証拠ｗを入力とし、ｘ∈Ｌの証明πを出力する。
Ｖ（ｃｒｓＮＩＺＫ，ｘ，π）は検証者アルゴリズムであり、共通パラメータｃｒｓＮＩＺＫと、文字列ｘと、証明πを入力とし、ｙｅｓ（合格）／ｎｏ（不合格）を出力する。
Ｂを二項関係とし、ＬをＢから定義される言語とする。すなわち、Ｌ＝｛ｘ∈｛０，１｝*：Ｂ（ｘ，ｗ）＝１ ｆｏｒ ｓｏｍｅ ｗ｝である。ｘ∈Ｌのときに対応するｗを証拠と呼ぶ。
非対話零知識証明とは三つ組みのアルゴリズムであり、ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ）と書く。
Ｇ（１κ）はセットアップアルゴリズムであり、セキュリティパラメータ１κを入力とし、ＣＲＳ(Common Reference String)と呼ばれる共通パラメータｃｒｓＮＩＺＫを出力する。なお、１κはκ個の１からなる列を表す。κは１以上の所定の整数である。
Ｐ（ｃｒｓＮＩＺＫ，ｘ，ｗ）は証明者アルゴリズムであり、共通パラメータｃｒｓＮＩＺＫと、文字列ｘ∈Ｌ⊆｛０，１｝*と、その証拠ｗを入力とし、ｘ∈Ｌの証明πを出力する。
Ｖ（ｃｒｓＮＩＺＫ，ｘ，π）は検証者アルゴリズムであり、共通パラメータｃｒｓＮＩＺＫと、文字列ｘと、証明πを入力とし、ｙｅｓ（合格）／ｎｏ（不合格）を出力する。
［双線形写像］
双線形写像ｅ：ＧＫ×ＧＫ→ＧＴは、双線形性、非退化性および効率的計算可能性を持つ写像である。ただし、ＧＫ，ＧＴは位数が素数ｑである可換群である。
双線形性により、任意のｈ１，ｈ２∈ＧＫおよび任意のα，β∈Ｚｑについてｅ（ｈ１ α，ｈ２ β）＝ｅ（ｈ１，ｈ２）αβとなる。非退化性により、ｅ（ｈ１，ｈ１）のＧＴでの位数がｑとなる。効率的計算可能性により、ｅを効率よく計算することができる。なお、Ｚｑはｑによる剰余群を表す。双線形写像の例はペアリングである。
双線形写像ｅ：ＧＫ×ＧＫ→ＧＴは、双線形性、非退化性および効率的計算可能性を持つ写像である。ただし、ＧＫ，ＧＴは位数が素数ｑである可換群である。
双線形性により、任意のｈ１，ｈ２∈ＧＫおよび任意のα，β∈Ｚｑについてｅ（ｈ１ α，ｈ２ β）＝ｅ（ｈ１，ｈ２）αβとなる。非退化性により、ｅ（ｈ１，ｈ１）のＧＴでの位数がｑとなる。効率的計算可能性により、ｅを効率よく計算することができる。なお、Ｚｑはｑによる剰余群を表す。双線形写像の例はペアリングである。
［衝突困難性（衝突耐性）を持つ写像］
写像Ｈが衝突困難性を持つとは、多項式時間で動作する敵が、写像の属からそれに属する写像Ｈを定める情報とセキュリティパラメータ１κとを受け取ったとき、γ≠δかつＨ（γ）＝Ｈ（δ）なる組（γ，δ）を無視できる確率でしか出力することができないことを表す。衝突困難性を持つ写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。通常、衝突困難性を持つ写像は一方向性も持つ。
写像Ｈが衝突困難性を持つとは、多項式時間で動作する敵が、写像の属からそれに属する写像Ｈを定める情報とセキュリティパラメータ１κとを受け取ったとき、γ≠δかつＨ（γ）＝Ｈ（δ）なる組（γ，δ）を無視できる確率でしか出力することができないことを表す。衝突困難性を持つ写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。通常、衝突困難性を持つ写像は一方向性も持つ。
＜原理＞
各実施形態に共通する原理を説明する。
安全性強化装置では、秘密の鍵情報に対応する秘密情報を格納し、秘密情報に対して特定の対応関係を持つ補助情報を得て出力する。ただし、当該秘密情報と異なる関連秘密情報に対して当該対応関係を持つ関連補助情報を当該補助情報から特定することは困難である。
各実施形態に共通する原理を説明する。
安全性強化装置では、秘密の鍵情報に対応する秘密情報を格納し、秘密情報に対して特定の対応関係を持つ補助情報を得て出力する。ただし、当該秘密情報と異なる関連秘密情報に対して当該対応関係を持つ関連補助情報を当該補助情報から特定することは困難である。
検証装置では、入力された補助情報が秘密情報に対して特定の対応関係を持つかを判定し、当該補助情報が秘密情報に対して当該対応関係を持つ場合に秘密情報に対応する秘密の鍵情報または当該鍵情報から得られる情報を得、当該補助情報が秘密情報に対して当該対応関係を持たない場合に拒絶を表す情報を出力する。
以上の構成では、秘密情報に対して特定の対応関係を持つ補助情報を用いる。上記の関連補助情報を補助情報から特定することは困難である。これにより自壊することなく、任意の回路の関連鍵攻撃に対する安全性を向上させることができる。本構成は任意の回路に汎用的に適用可能であるが、ここでは特定の従来構成に対する関連鍵攻撃を例示し、その関連鍵攻撃がこの原理を適用した方式に通じないことを示す。
[従来の公開鍵型暗号学的デバイスの一例]
以下に従来の公開鍵型暗号学的デバイスを例示する。
Ｓｅｔｕｐ（１κ）は、セキュリティパラメータ１κを入力とし、ＧＫとｑと生成元ｇ１，ｇ２∈ＧＫと衝突困難性を持つ写像Ｈ：ＧＫ ３→Ｚｑとを得、共通パラメータｐｐ＝（ＧＫ，ｑ，ｇ１，ｇ２，Ｈ）として出力する。
Ｇｅｎ（ｐｐ；ｒ）は、ｐｐを入力とし、秘密情報ｓである鍵情報ｄｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と公開情報である鍵情報ｅｋ＝（Ｘｅｋ，Ｙｅｋ，Ｚｅｋ）＝（ｇ１ ｘ１・ｇ２ ｘ２，ｇ１ ｙ１・ｇ２ ｙ２，ｇ１ ｚ１・ｇ２ ｚ２）とを得て出力する。
Ｅｎｃ（ｐｐ；ｅｋ，ｍ）は、ｐｐとｅｋとメッセージｍとを入力とし、乱数ｒ’∈Ｚｑを生成し、ｃ１＝ｇ１ ｒ’，ｃ２＝ｇ２ ｒ’，Ｅ＝ｍ・Ｚｅｋ ｒ’，ω＝Ｈ（ｃ１，ｃ２，Ｅ），ν＝（Ｘｅｋ ω・Ｙｅｋ）ｒ’を得て、暗号文ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）を出力する。
Ｄｅｃ（ｐｐ；ｄｋ，ｃｔ）は、ｐｐとｄｋとｃｔとを入力とし、ｃｔ∈ＧＫ ４であれば、ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）からω＝Ｈ（ｃ１，ｃ２，Ｅ）を得、さらにｃ１ｘ１*ω+ｙ１・ｃ２ｘ２*ω+ｙ２＝νであれば、ｍ＝Ｅ／（ｃ１ｚ１・ｃ２ｚ２）を出力する。
以下に従来の公開鍵型暗号学的デバイスを例示する。
Ｓｅｔｕｐ（１κ）は、セキュリティパラメータ１κを入力とし、ＧＫとｑと生成元ｇ１，ｇ２∈ＧＫと衝突困難性を持つ写像Ｈ：ＧＫ ３→Ｚｑとを得、共通パラメータｐｐ＝（ＧＫ，ｑ，ｇ１，ｇ２，Ｈ）として出力する。
Ｇｅｎ（ｐｐ；ｒ）は、ｐｐを入力とし、秘密情報ｓである鍵情報ｄｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と公開情報である鍵情報ｅｋ＝（Ｘｅｋ，Ｙｅｋ，Ｚｅｋ）＝（ｇ１ ｘ１・ｇ２ ｘ２，ｇ１ ｙ１・ｇ２ ｙ２，ｇ１ ｚ１・ｇ２ ｚ２）とを得て出力する。
Ｅｎｃ（ｐｐ；ｅｋ，ｍ）は、ｐｐとｅｋとメッセージｍとを入力とし、乱数ｒ’∈Ｚｑを生成し、ｃ１＝ｇ１ ｒ’，ｃ２＝ｇ２ ｒ’，Ｅ＝ｍ・Ｚｅｋ ｒ’，ω＝Ｈ（ｃ１，ｃ２，Ｅ），ν＝（Ｘｅｋ ω・Ｙｅｋ）ｒ’を得て、暗号文ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）を出力する。
Ｄｅｃ（ｐｐ；ｄｋ，ｃｔ）は、ｐｐとｄｋとｃｔとを入力とし、ｃｔ∈ＧＫ ４であれば、ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）からω＝Ｈ（ｃ１，ｃ２，Ｅ）を得、さらにｃ１ｘ１*ω+ｙ１・ｃ２ｘ２*ω+ｙ２＝νであれば、ｍ＝Ｅ／（ｃ１ｚ１・ｃ２ｚ２）を出力する。
[従来構成に対する関連鍵攻撃の一例]
上記の従来の公開鍵型暗号学的デバイスに対し、以下の一方向性を破る関連鍵攻撃が成功する。
１．敵はメッセージｍの暗号文ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）を受け取る。
２．敵は０以外のΔ∈Ｚｑを選択し、鍵情報ｄｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を関連鍵情報φ（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）＝（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）に移す写像φと、新しい暗号文ｃｔ’＝（ｃ１，ｃ２，Ｅ，ν・ｃ１Δ）をＤｅｃに問い合わせる。
３．Ｄｅｃは鍵情報ｄｋに写像φを適用し、関連鍵情報（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）を得、それを用いてｃｔ’を復号し、メッセージｍを敵に返す。
４．敵はｍをそのまま出力する。
上記の従来の公開鍵型暗号学的デバイスに対し、以下の一方向性を破る関連鍵攻撃が成功する。
１．敵はメッセージｍの暗号文ｃｔ＝（ｃ１，ｃ２，Ｅ，ν）を受け取る。
２．敵は０以外のΔ∈Ｚｑを選択し、鍵情報ｄｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を関連鍵情報φ（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）＝（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）に移す写像φと、新しい暗号文ｃｔ’＝（ｃ１，ｃ２，Ｅ，ν・ｃ１Δ）をＤｅｃに問い合わせる。
３．Ｄｅｃは鍵情報ｄｋに写像φを適用し、関連鍵情報（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）を得、それを用いてｃｔ’を復号し、メッセージｍを敵に返す。
４．敵はｍをそのまま出力する。
この例では秘密情報が鍵情報である。また、上述の原理を上述の公開鍵型暗号学的デバイスの一例に適用する場合には、例えば、Ｄｅｃに検証装置を組み込んで機能させる。鍵情報および関連鍵情報は秘密情報であり、敵はこれらの情報を知らない。また敵は、鍵情報（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）に対する補助情報を知ったとしても、関連鍵情報（ｘ１，ｘ２，ｙ１＋Δ，ｙ２，ｚ１，ｚ２）に対する補助情報（秘密情報と異なる関連秘密情報に対して特定の対応関係を持つ関連補助情報）を得ることができない。よって敵は、関連鍵情報に対する補助情報をＤｅｃに与えることができない。そのため検証装置は、Ｄｅｃからの問い合わせに対して拒絶を返し、Ｄｅｃは敵に対して拒絶を返す。その結果、敵は暗号文ｃｔ’＝（ｃ１，ｃ２，Ｅ，ν’）を復号することができず、メッセージｍも得ることができない。
＜第１実施形態＞
第１実施形態を説明する。本形態は、暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）に上述の原理を適用したものである。本形態の安全性強化装置は、非対話零知識証明（ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ））を用いて補助情報を生成する。この補助情報は、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文とに対する非対話零知識証明検証を行い、さらに秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定する。
第１実施形態を説明する。本形態は、暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）に上述の原理を適用したものである。本形態の安全性強化装置は、非対話零知識証明（ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ））を用いて補助情報を生成する。この補助情報は、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文とに対する非対話零知識証明検証を行い、さらに秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定する。
［構成］
図１に例示するように、本形態の安全性強化システム１は、設定装置１１０と安全性強化装置１２０と検証装置１３０とを有する。設定装置１１０と安全性強化装置１２０と検証装置１３０とは、それぞれ、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）等を含む汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置１１０と安全性強化装置１２０と検証装置１３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図１に例示するように、本形態の安全性強化システム１は、設定装置１１０と安全性強化装置１２０と検証装置１３０とを有する。設定装置１１０と安全性強化装置１２０と検証装置１３０とは、それぞれ、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）等を含む汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置１１０と安全性強化装置１２０と検証装置１３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
安全性強化装置１２０は、例えば、暗号化を行う際に用いる鍵を得る鍵生成装置である（暗号学的デバイスに上述の原理を適用する以降の実施形態の安全性強化装置についても同様）。安全性強化装置１２０は、入力部１２１と記憶部１２２と補助情報生成部１２３と出力部１２４とを有する。補助情報生成部１２３は、乱数生成部１２３ａと鍵・鍵暗号文生成部１２３ｂと暗号化部１２３ｃと証明生成部１２３ｄとを有する。安全性強化装置１２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
検証装置１３０は、例えば、暗号文を復号する際に用いる鍵を得る鍵生成装置である（暗号学的デバイスに上述の原理を適用する以降の実施形態の検証装置についても同様）。検証装置１３０は、入力部１３１と記憶部１３２と判定部１３３と鍵制御部１３６と出力部１３７とを有する。判定部１３３は、検証部１３３ａと鍵暗号文生成部１３３ｂと暗号文比較部１３３ｃとを有する。検証装置１３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
設定装置１１０は、セキュリティパラメータ（１κ）を入力としてセットアップアルゴリズムＳｅｔｕｐ（１κ）を実行し、共通パラメータｐｐを得る。この共通パラメータｐｐは、暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通することとする。また設定装置１１０は、セキュリティパラメータ（１κ）を入力として非対話零知識証明のセットアップアルゴリズムＧ（１κ）を実行し、共通パラメータｃｒｓＮＩＺＫを得る。さらに設定装置１１０は、鍵カプセル化方式の鍵生成アルゴリズムＧｅｎＫＥＭ（ｐｐ）を実行し、鍵ペア（ｐｋ，ｓｋ）を得る。また設定装置１１０は、公開鍵暗号方式の鍵生成アルゴリズムＧｅｎＰＫＥ（ｐｐ）を実行し、鍵ペア（ｅｋ，ｄｋ）を得る。設定装置１１０は、以上のように得られた共通パラメータｃｒｓ＝（ｐｐ，ｐｋ，ｅｋ，ｃｒｓＮＩＺＫ）を出力する。共通パラメータｃｒｓは、それぞれ、安全性強化装置１２０および検証装置１３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
設定装置１１０は、セキュリティパラメータ（１κ）を入力としてセットアップアルゴリズムＳｅｔｕｐ（１κ）を実行し、共通パラメータｐｐを得る。この共通パラメータｐｐは、暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通することとする。また設定装置１１０は、セキュリティパラメータ（１κ）を入力として非対話零知識証明のセットアップアルゴリズムＧ（１κ）を実行し、共通パラメータｃｒｓＮＩＺＫを得る。さらに設定装置１１０は、鍵カプセル化方式の鍵生成アルゴリズムＧｅｎＫＥＭ（ｐｐ）を実行し、鍵ペア（ｐｋ，ｓｋ）を得る。また設定装置１１０は、公開鍵暗号方式の鍵生成アルゴリズムＧｅｎＰＫＥ（ｐｐ）を実行し、鍵ペア（ｅｋ，ｄｋ）を得る。設定装置１１０は、以上のように得られた共通パラメータｃｒｓ＝（ｐｐ，ｐｋ，ｅｋ，ｃｒｓＮＩＺＫ）を出力する。共通パラメータｃｒｓは、それぞれ、安全性強化装置１２０および検証装置１３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
また、設定装置１１０はランダムな秘密情報ｓ∈Ｓを生成して出力する。秘密情報ｓは、安全性強化装置１２０および検証装置１３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理（図２Ａ）]
安全性強化装置１２０の乱数生成部１２３ａが、乱数ρ∈ＲＰＫＥを生成して出力する（ステップＳ１２１）。鍵・鍵暗号文生成部１２３ｂが、共通パラメータｐｐと公開鍵ｐｋと秘密情報ｓを用いて鍵暗号化アルゴリズムＥｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）を実行し、鍵（鍵情報）ｋとそれに対応する暗号文ｃ（第１暗号文）とを出力する（ステップＳ１２２）。暗号化部１２３ｃが、共通パラメータｐｐと暗号化鍵ｅｋと秘密情報ｓと乱数ρとを用いて暗号化アルゴリズムＥｎｃ（ｐｐ，ｅｋ，ｍ；ρ）を実行し、秘密情報ｓの暗号文τ（第２暗号文）を得て出力する（ステップＳ１２３）。証明生成部１２３ｄが、共通パラメータｃｒｓＮＩＺＫと、暗号文ｃ，τに対応する文字列ｘ＝（ｃ，τ）と、その証拠ｗである証拠情報（ｓ，ρ）とを入力とし、証明者アルゴリズムＰ（ｃｒｓＮＩＺＫ，（ｃ，τ），（ｓ，ρ））を実行し、その証明である証明情報πを得て出力する。なお、文字列ｘの例は、ｃ，τのビット列表現値のビット結合値である。証拠情報（ｓ，ρ）の例は、ｓ，ρのビット列表現値のビット結合値である。また、非対話零知識証明の二項関係Ｂを以下のように定義する。
Ｂ（ｘ，ｗ）＝｛（（ｃ，τ），（ｓ，ρ））：（（ｃ，*）＝Ｅｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）∧（τ＝Ｅｎｃ（ｐｐ，ｅｋ，ｓ；ρ）））｝
ここで「*」はワイルドカードを表す（ステップＳ１２４）。出力部１２４は、暗号文ｃ，τと証明情報πとを含む補助情報ａｕｘ＝（ｃ，τ，π）を出力する（ステップＳ１２５）。得られた鍵ｋは、例えば共通鍵暗号方式に則って暗号化するための共通鍵として用いられる（暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
安全性強化装置１２０の乱数生成部１２３ａが、乱数ρ∈ＲＰＫＥを生成して出力する（ステップＳ１２１）。鍵・鍵暗号文生成部１２３ｂが、共通パラメータｐｐと公開鍵ｐｋと秘密情報ｓを用いて鍵暗号化アルゴリズムＥｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）を実行し、鍵（鍵情報）ｋとそれに対応する暗号文ｃ（第１暗号文）とを出力する（ステップＳ１２２）。暗号化部１２３ｃが、共通パラメータｐｐと暗号化鍵ｅｋと秘密情報ｓと乱数ρとを用いて暗号化アルゴリズムＥｎｃ（ｐｐ，ｅｋ，ｍ；ρ）を実行し、秘密情報ｓの暗号文τ（第２暗号文）を得て出力する（ステップＳ１２３）。証明生成部１２３ｄが、共通パラメータｃｒｓＮＩＺＫと、暗号文ｃ，τに対応する文字列ｘ＝（ｃ，τ）と、その証拠ｗである証拠情報（ｓ，ρ）とを入力とし、証明者アルゴリズムＰ（ｃｒｓＮＩＺＫ，（ｃ，τ），（ｓ，ρ））を実行し、その証明である証明情報πを得て出力する。なお、文字列ｘの例は、ｃ，τのビット列表現値のビット結合値である。証拠情報（ｓ，ρ）の例は、ｓ，ρのビット列表現値のビット結合値である。また、非対話零知識証明の二項関係Ｂを以下のように定義する。
Ｂ（ｘ，ｗ）＝｛（（ｃ，τ），（ｓ，ρ））：（（ｃ，*）＝Ｅｎｃａｐｓ（ｐｐ，ｐｋ；ｓ）∧（τ＝Ｅｎｃ（ｐｐ，ｅｋ，ｓ；ρ）））｝
ここで「*」はワイルドカードを表す（ステップＳ１２４）。出力部１２４は、暗号文ｃ，τと証明情報πとを含む補助情報ａｕｘ＝（ｃ，τ，π）を出力する（ステップＳ１２５）。得られた鍵ｋは、例えば共通鍵暗号方式に則って暗号化するための共通鍵として用いられる（暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
[検証処置（図２Ｂ）]
補助情報ａｕｘ＝（ｃ，τ，π）は、検証装置１３０の入力部１３１に入力されて記憶部１３２に格納される。検証部１３３ａが、共通パラメータｃｒｓＮＩＺＫと暗号文ｃ，τと証明情報πとを入力とし、検証者アルゴリズムＶ（ｃｒｓＮＩＺＫ，（ｃ，τ），π）を実行し、証明情報πを用いた暗号文ｃ，τに対する非対話零知識証明検証を行い、その検証結果がｙｅｓであるかを判定する（ステップＳ１３１）。検証結果がｎｏであれば、出力部１３７が⊥を出力し（ステップＳ１３５）、処理を終える。検証結果がｙｅｓであれば、鍵暗号文生成部１３３ｂが、共通パラメータｐｐと公開鍵ｐｋと秘密情報ｓを用い、アルゴリズムＥｎｃａｐｓ１（ｐｐ，ｐｋ；ｓ）を実行し、秘密情報ｓに対応する検証用暗号文ｃ’を得て出力する（ステップＳ１３２）。暗号文比較部１３３ｃが、暗号文ｃと検証用暗号文ｃ’とが一致するかを判定する（ステップＳ１３３）。これらが一致しないと判定された場合（ｃ≠ｃ’）、出力部１３７が⊥を出力し（ステップＳ１３５）、処理を終える。暗号文ｃと検証用暗号文ｃ’とが一致すると判定された場合（ｃ＝ｃ’）、鍵制御部１３６が、共通パラメータｐｐと秘密情報ｓとを用い、アルゴリズムＥｎｃａｐｓ２（ｐｐ；ｓ）を実行し、秘密情報ｓに対応する鍵ｋ’を得て出力する（ステップＳ１３４）。出力部１３７は、鍵（鍵情報）ｋ’を出力し（ステップＳ１３６）、処理を終える。出力された鍵ｋ’は、例えば共通鍵暗号方式に則って復号するための共通鍵として用いられる（暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
補助情報ａｕｘ＝（ｃ，τ，π）は、検証装置１３０の入力部１３１に入力されて記憶部１３２に格納される。検証部１３３ａが、共通パラメータｃｒｓＮＩＺＫと暗号文ｃ，τと証明情報πとを入力とし、検証者アルゴリズムＶ（ｃｒｓＮＩＺＫ，（ｃ，τ），π）を実行し、証明情報πを用いた暗号文ｃ，τに対する非対話零知識証明検証を行い、その検証結果がｙｅｓであるかを判定する（ステップＳ１３１）。検証結果がｎｏであれば、出力部１３７が⊥を出力し（ステップＳ１３５）、処理を終える。検証結果がｙｅｓであれば、鍵暗号文生成部１３３ｂが、共通パラメータｐｐと公開鍵ｐｋと秘密情報ｓを用い、アルゴリズムＥｎｃａｐｓ１（ｐｐ，ｐｋ；ｓ）を実行し、秘密情報ｓに対応する検証用暗号文ｃ’を得て出力する（ステップＳ１３２）。暗号文比較部１３３ｃが、暗号文ｃと検証用暗号文ｃ’とが一致するかを判定する（ステップＳ１３３）。これらが一致しないと判定された場合（ｃ≠ｃ’）、出力部１３７が⊥を出力し（ステップＳ１３５）、処理を終える。暗号文ｃと検証用暗号文ｃ’とが一致すると判定された場合（ｃ＝ｃ’）、鍵制御部１３６が、共通パラメータｐｐと秘密情報ｓとを用い、アルゴリズムＥｎｃａｐｓ２（ｐｐ；ｓ）を実行し、秘密情報ｓに対応する鍵ｋ’を得て出力する（ステップＳ１３４）。出力部１３７は、鍵（鍵情報）ｋ’を出力し（ステップＳ１３６）、処理を終える。出力された鍵ｋ’は、例えば共通鍵暗号方式に則って復号するための共通鍵として用いられる（暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
＜第２実施形態＞
第２実施形態を説明する。本形態は、公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用したものである。本形態の安全性強化装置は、非対話零知識証明（ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ））を用いて補助情報を生成する。この補助情報は、秘密情報に対応する公開鍵と、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文とに対する非対話零知識証明検証を行い、秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定し、さらに秘密情報に対応する検証用公開鍵と公開鍵とが一致するかを判定する。以降、これまで説明したものと共通する事項については、同じ参照番号を用いて説明を省略する。
第２実施形態を説明する。本形態は、公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用したものである。本形態の安全性強化装置は、非対話零知識証明（ＮＩＺＫ＝（Ｇ，Ｐ，Ｖ））を用いて補助情報を生成する。この補助情報は、秘密情報に対応する公開鍵と、秘密情報に対応する第１暗号文と、秘密情報と乱数とに対応する第２暗号文と、秘密情報と乱数とを証拠情報として第１暗号文と第２暗号文とに対する非対話零知識証明を行うための証明情報とを含む。本形態の検証装置は、補助情報が含む証明情報を用いて第１暗号文と第２暗号文とに対する非対話零知識証明検証を行い、秘密情報に対応する検証用暗号文と第１暗号文とが一致するかを判定し、さらに秘密情報に対応する検証用公開鍵と公開鍵とが一致するかを判定する。以降、これまで説明したものと共通する事項については、同じ参照番号を用いて説明を省略する。
［構成］
図１に例示するように、本形態の安全性強化システム２は、設定装置２１０と安全性強化装置２２０と検証装置２３０とを有する。設定装置２１０と安全性強化装置２２０と検証装置２３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置２１０と安全性強化装置２２０と検証装置２３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図１に例示するように、本形態の安全性強化システム２は、設定装置２１０と安全性強化装置２２０と検証装置２３０とを有する。設定装置２１０と安全性強化装置２２０と検証装置２３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置２１０と安全性強化装置２２０と検証装置２３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
安全性強化装置２２０は、例えば、暗号化や署名を行う際に用いる鍵を得る鍵生成装置またはその一部である（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態の安全性強化装置についても同様）。安全性強化装置２２０は、入力部１２１と記憶部１２２と補助情報生成部２２３と出力部２２４とを有する。補助情報生成部２２３は、乱数生成部１２３ａと鍵・鍵暗号文生成部２２３ｂと暗号化部１２３ｃと証明生成部１２３ｄと鍵ペア生成部２２３ｅとを有する。安全性強化装置２２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
検証装置２３０は、例えば、暗号文の復号や署名検証を行う際に用いる鍵を得る生成装置である（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態の検証装置についても同様）。検証装置２３０は、入力部１３１と記憶部１３２と判定部２３３と鍵制御部２３６と出力部２３７とを有する。判定部２３３は、検証部１３３ａと鍵暗号文生成部１３３ｂと暗号文比較部１３３ｃと公開鍵比較部２３３ｄを有する。検証装置２３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
本形態の設定装置２１０のセットアップ処理で生成される共通パラメータｐｐは、公開鍵型暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通するものである。その他のセットアップ処理の内容は第１実施形態の設定装置１１０と同じである。設定装置２１０は、生成した共通パラメータｃｒｓ＝（ｐｐ，ｐｋ，ｅｋ，ｃｒｓＮＩＺＫ）および秘密情報ｓ∈Ｓを出力する。これらはそれぞれ、安全性強化装置２２０および検証装置２３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
本形態の設定装置２１０のセットアップ処理で生成される共通パラメータｐｐは、公開鍵型暗号学的デバイス、鍵カプセル化方式、および公開鍵暗号方式に共通するものである。その他のセットアップ処理の内容は第１実施形態の設定装置１１０と同じである。設定装置２１０は、生成した共通パラメータｃｒｓ＝（ｐｐ，ｐｋ，ｅｋ，ｃｒｓＮＩＺＫ）および秘密情報ｓ∈Ｓを出力する。これらはそれぞれ、安全性強化装置２２０および検証装置２３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理（図３Ａ）]
安全性強化装置２２０の乱数生成部１２３ａが第１実施形態で説明したステップＳ１２１の処理を実行した後、鍵・暗号文生成装置２２３ｂが第１実施形態で説明したステップＳ１２２の処理を「ｋ」を「ｒ」に置換して実行し（ステップＳ２２２）、その後、暗号化部１２３ｃおよび証明生成部１２３ｄが第１実施形態で説明したステップＳ１２３およびＳ１２４の処理を実行する。次に安全性強化装置２２０の鍵ペア生成部２２３ｅが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、公開鍵ｐと秘密鍵ｋ（鍵情報）との鍵ペア（ｐ，ｋ）を得て出力する。ただし、ｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）は、共通パラメータｐｐと秘密情報ｓを入力とし、鍵カプセル化方式のアルゴリズムＥｎｃａｐｓ２（ｐｐ；ｓ）を実行して鍵ｒを得、公開鍵型暗号学的デバイスの鍵生成アルゴリズムＧｅｎ（ｐｐ；ｒ）を実行して、秘密鍵ｋ∈Ｋと公開鍵ｐを得て出力するアルゴリズムである。ただし、鍵ｒを新たに得るのではなく、ステップＳ２２２で得られた鍵ｒがｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）で流用されてもよい（ステップＳ２２４）。出力部２２４は、公開鍵ｐと暗号文ｃ，τと証明情報πとを含む補助情報ａｕｘ＝（ｐ，ｃ，τ，π）を出力する（ステップＳ２２５）。得られた秘密鍵ｋは、例えば公開鍵暗号方式に則って暗号化するために用いられる（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
安全性強化装置２２０の乱数生成部１２３ａが第１実施形態で説明したステップＳ１２１の処理を実行した後、鍵・暗号文生成装置２２３ｂが第１実施形態で説明したステップＳ１２２の処理を「ｋ」を「ｒ」に置換して実行し（ステップＳ２２２）、その後、暗号化部１２３ｃおよび証明生成部１２３ｄが第１実施形態で説明したステップＳ１２３およびＳ１２４の処理を実行する。次に安全性強化装置２２０の鍵ペア生成部２２３ｅが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、公開鍵ｐと秘密鍵ｋ（鍵情報）との鍵ペア（ｐ，ｋ）を得て出力する。ただし、ｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）は、共通パラメータｐｐと秘密情報ｓを入力とし、鍵カプセル化方式のアルゴリズムＥｎｃａｐｓ２（ｐｐ；ｓ）を実行して鍵ｒを得、公開鍵型暗号学的デバイスの鍵生成アルゴリズムＧｅｎ（ｐｐ；ｒ）を実行して、秘密鍵ｋ∈Ｋと公開鍵ｐを得て出力するアルゴリズムである。ただし、鍵ｒを新たに得るのではなく、ステップＳ２２２で得られた鍵ｒがｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）で流用されてもよい（ステップＳ２２４）。出力部２２４は、公開鍵ｐと暗号文ｃ，τと証明情報πとを含む補助情報ａｕｘ＝（ｐ，ｃ，τ，π）を出力する（ステップＳ２２５）。得られた秘密鍵ｋは、例えば公開鍵暗号方式に則って暗号化するために用いられる（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
[検証処置（図３Ｂ）]
補助情報ａｕｘ＝（ｐ，ｃ，τ，π）は、検証装置２３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ１３１〜Ｓ１３３，Ｓ１３５の処理が第１実施形態で説明した通りに実行される。ステップＳ１３３で暗号文ｃと検証用暗号文ｃ’とが一致すると判定された場合（ｃ＝ｃ’）、公開鍵比較部２３３ｄが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報に対応する検証用公開鍵ｐ’と秘密鍵ｋ’との鍵ペア（ｐ’，ｋ’）を得る（ステップＳ２３３）。さらに公開鍵比較部２３３ｄは、検証用公開鍵ｐ’と公開鍵ｐとが一致するかを判定する（ステップＳ２３４）。これらが一致しないと判定された場合（ｐ≠ｐ’）、出力部２３７が⊥を出力し（ステップＳ１３５）、処理を終える。一方、検証用公開鍵ｐ’と公開鍵ｐとが一致すると判定された場合（ｐ＝ｐ’）、鍵制御部２３６が、秘密鍵ｋ’を出力部２３７に送り、出力部２３７は秘密鍵ｋ’（鍵情報）を出力し（ステップＳ２３６）、処理を終える。出力された秘密鍵ｋ’は、例えば公開鍵暗号方式に則って復号するためや署名生成に用いられる（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
補助情報ａｕｘ＝（ｐ，ｃ，τ，π）は、検証装置２３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ１３１〜Ｓ１３３，Ｓ１３５の処理が第１実施形態で説明した通りに実行される。ステップＳ１３３で暗号文ｃと検証用暗号文ｃ’とが一致すると判定された場合（ｃ＝ｃ’）、公開鍵比較部２３３ｄが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報に対応する検証用公開鍵ｐ’と秘密鍵ｋ’との鍵ペア（ｐ’，ｋ’）を得る（ステップＳ２３３）。さらに公開鍵比較部２３３ｄは、検証用公開鍵ｐ’と公開鍵ｐとが一致するかを判定する（ステップＳ２３４）。これらが一致しないと判定された場合（ｐ≠ｐ’）、出力部２３７が⊥を出力し（ステップＳ１３５）、処理を終える。一方、検証用公開鍵ｐ’と公開鍵ｐとが一致すると判定された場合（ｐ＝ｐ’）、鍵制御部２３６が、秘密鍵ｋ’を出力部２３７に送り、出力部２３７は秘密鍵ｋ’（鍵情報）を出力し（ステップＳ２３６）、処理を終える。出力された秘密鍵ｋ’は、例えば公開鍵暗号方式に則って復号するためや署名生成に用いられる（公開鍵型暗号学的デバイスに上述の原理を適用する以降の実施形態についても同様）。
＜第３実施形態＞
第３実施形態を説明する。本形態は、暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）として、Ｋ＝ＧＴとし、双線形写像を用いたものに上述の原理を適用したものである。本形態では、ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅ：ＧＫ ２→ＧＴが双線形写像であり、秘密情報が乱数σに対するｓ＝ｈσ∈ＧＫであり、鍵情報がｅ（ｚ，ｓ）∈ＧＴを含み、補助情報がＸ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫとを含む。本形態の検証装置は、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定し、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定する。
第３実施形態を説明する。本形態は、暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ）として、Ｋ＝ＧＴとし、双線形写像を用いたものに上述の原理を適用したものである。本形態では、ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅ：ＧＫ ２→ＧＴが双線形写像であり、秘密情報が乱数σに対するｓ＝ｈσ∈ＧＫであり、鍵情報がｅ（ｚ，ｓ）∈ＧＴを含み、補助情報がＸ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫとを含む。本形態の検証装置は、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定し、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定する。
［構成］
図３に例示するように、本形態の安全性強化システム３は、設定装置３１０と安全性強化装置３２０と検証装置３３０とを有する。設定装置３１０と安全性強化装置３２０と検証装置３３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置３１０と安全性強化装置３２０と検証装置３３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図３に例示するように、本形態の安全性強化システム３は、設定装置３１０と安全性強化装置３２０と検証装置３３０とを有する。設定装置３１０と安全性強化装置３２０と検証装置３３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置３１０と安全性強化装置３２０と検証装置３３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
安全性強化装置３２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と鍵生成部３２５と補助情報生成部３２６と出力部３２７とを有する。補助情報生成部３２６は、群演算部３２６ａ，３２６ｂを有する。安全性強化装置３２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
検証装置３３０は、入力部１３１と記憶部１３２と判定部３３３と鍵制御部３３６と出力部３３７とを有する。判定部３３３は、比較部３３３ａ，３３３ｂを有する。検証装置３３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
設定装置３１０は、セキュリティパラメータ（１κ）を入力としてセットアップアルゴリズムＳｅｔｕｐ（１κ）を実行し、共通パラメータｐｐとして、ＧＫ，ＧＴ，ｑ，ｅ，ｇと衝突困難性を持つ写像Ｈ：ＧＫ→Ｚｑとを得、ｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）とする。写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。また設定装置３１０は、群ＧＫの元ｈ，ｚ，Ｖ，Ｗ∈ＧＫをランダムに選び、ｃｒｓ＝（ｐｐ，ｈ，ｚ，Ｖ，Ｗ）を出力する。共通パラメータｃｒｓは、それぞれ、安全性強化装置３２０および検証装置３３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
設定装置３１０は、セキュリティパラメータ（１κ）を入力としてセットアップアルゴリズムＳｅｔｕｐ（１κ）を実行し、共通パラメータｐｐとして、ＧＫ，ＧＴ，ｑ，ｅ，ｇと衝突困難性を持つ写像Ｈ：ＧＫ→Ｚｑとを得、ｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）とする。写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。また設定装置３１０は、群ＧＫの元ｈ，ｚ，Ｖ，Ｗ∈ＧＫをランダムに選び、ｃｒｓ＝（ｐｐ，ｈ，ｚ，Ｖ，Ｗ）を出力する。共通パラメータｃｒｓは、それぞれ、安全性強化装置３２０および検証装置３３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理（図５Ａ）]
安全性強化装置３２０の乱数生成部３２３は、ｐｐを入力として乱数σ∈Ｚｑを選択して出力する（ステップＳ３２１）。秘密情報生成部３２４は、ｐｐ，σを入力とし、乱数σに対する秘密情報ｓ＝ｈσ∈ＧＫを得て出力する（ステップＳ３２２）。鍵生成部３２５は、ｐｐ，ｚ，ｓを入力とし、秘密の鍵（鍵情報）ｋ＝ｅ（ｚ，ｓ）∈ＧＴを生成して出力する（ステップＳ３２３）。群演算部３２６ａは、ｐｐ，σを入力としてＸ＝ｇσ∈ＧＫを得て出力する（ステップＳ３２４）。群演算部３２６ｂは、ｐｐ，Ｘ，σを入力としてＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫを得て出力する（ステップＳ３２５）。出力部３２７は、ＸとＴＧとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓを出力する（ステップＳ３２６）。
安全性強化装置３２０の乱数生成部３２３は、ｐｐを入力として乱数σ∈Ｚｑを選択して出力する（ステップＳ３２１）。秘密情報生成部３２４は、ｐｐ，σを入力とし、乱数σに対する秘密情報ｓ＝ｈσ∈ＧＫを得て出力する（ステップＳ３２２）。鍵生成部３２５は、ｐｐ，ｚ，ｓを入力とし、秘密の鍵（鍵情報）ｋ＝ｅ（ｚ，ｓ）∈ＧＴを生成して出力する（ステップＳ３２３）。群演算部３２６ａは、ｐｐ，σを入力としてＸ＝ｇσ∈ＧＫを得て出力する（ステップＳ３２４）。群演算部３２６ｂは、ｐｐ，Ｘ，σを入力としてＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫを得て出力する（ステップＳ３２５）。出力部３２７は、ＸとＴＧとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓを出力する（ステップＳ３２６）。
[検証処置（図５Ｂ）]
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓは、検証装置３３０の入力部１３１に入力されて記憶部１３２に格納される。比較部３３３ａは、ｐｐ，ａｕｘを入力とし、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定する（ステップＳ３３１）。これらが一致しないと判定された場合（ｅ（ｇ，ＴＧ）≠ｅ（Ｘ，Ｖ・ＷＨ（Ｘ）））、出力部３３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致すると判定された場合（ｅ（ｇ，ＴＧ）＝ｅ（Ｘ，Ｖ・ＷＨ（Ｘ）））、比較部３３３ａは、ｐｐ，ｓを入力とし、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定する（ステップＳ３３２）。これらが一致しないと判定された場合（ｅ（ｇ，ｓ）≠ｅ（Ｘ，ｈ））、出力部３３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部３３６がｐｐ，ｚ，ｓを入力とし、秘密の鍵（鍵情報）ｋ’＝ｅ（ｚ，ｓ）∈ＧＴを生成し（ステップＳ３３４）、出力部３３７が鍵ｋを出力する（ステップＳ３３６）。
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓは、検証装置３３０の入力部１３１に入力されて記憶部１３２に格納される。比較部３３３ａは、ｐｐ，ａｕｘを入力とし、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定する（ステップＳ３３１）。これらが一致しないと判定された場合（ｅ（ｇ，ＴＧ）≠ｅ（Ｘ，Ｖ・ＷＨ（Ｘ）））、出力部３３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致すると判定された場合（ｅ（ｇ，ＴＧ）＝ｅ（Ｘ，Ｖ・ＷＨ（Ｘ）））、比較部３３３ａは、ｐｐ，ｓを入力とし、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定する（ステップＳ３３２）。これらが一致しないと判定された場合（ｅ（ｇ，ｓ）≠ｅ（Ｘ，ｈ））、出力部３３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部３３６がｐｐ，ｚ，ｓを入力とし、秘密の鍵（鍵情報）ｋ’＝ｅ（ｚ，ｓ）∈ＧＴを生成し（ステップＳ３３４）、出力部３３７が鍵ｋを出力する（ステップＳ３３６）。
＜第４実施形態＞
第４実施形態を説明する。本形態は、公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）として、Ｋ＝ＧＴとし、双線形写像を用いたものに上述の原理を適用したものである。本形態では、ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅ：ＧＫ ２→ＧＴが双線形写像であり、秘密情報が乱数σに対するｓ＝ｈσ∈ＧＫであり、鍵情報がｅ（ｚ，ｓ）∈ＧＴを含み、補助情報が秘密情報ｓに対応する公開鍵とＸ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫとを含む。本形態の検証装置は、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定し、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定し、さらに秘密情報に対応する検証用公開鍵と公開鍵とが一致するかを判定する。
第４実施形態を説明する。本形態は、公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）として、Ｋ＝ＧＴとし、双線形写像を用いたものに上述の原理を適用したものである。本形態では、ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅ：ＧＫ ２→ＧＴが双線形写像であり、秘密情報が乱数σに対するｓ＝ｈσ∈ＧＫであり、鍵情報がｅ（ｚ，ｓ）∈ＧＴを含み、補助情報が秘密情報ｓに対応する公開鍵とＸ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫとを含む。本形態の検証装置は、ｅ（ｇ，ＴＧ）∈ＧＴとｅ（Ｘ，Ｖ・ＷＨ（Ｘ））∈ＧＴとが一致するかを判定し、ｅ（ｇ，ｓ）∈ＧＴとｅ（Ｘ，ｈ）∈ＧＴとが一致するかを判定し、さらに秘密情報に対応する検証用公開鍵と公開鍵とが一致するかを判定する。
［構成］
図４に例示するように、本形態の安全性強化システム４は、設定装置４１０と安全性強化装置４２０と検証装置４３０とを有する。設定装置４１０と安全性強化装置４２０と検証装置４３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置４１０と安全性強化装置４２０と検証装置４３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図４に例示するように、本形態の安全性強化システム４は、設定装置４１０と安全性強化装置４２０と検証装置４３０とを有する。設定装置４１０と安全性強化装置４２０と検証装置４３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置４１０と安全性強化装置４２０と検証装置４３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
安全性強化装置４２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と補助情報生成部４２６と出力部４２７とを有する。補助情報生成部４２６は、鍵生成部４２６ｃと群演算部３２６ａ，３２６ｂとを有する。安全性強化装置４２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
検証装置４３０は、入力部１３１と記憶部１３２と判定部４３３と鍵制御部４３６と出力部４３７とを有する。判定部４３３は、比較部３３３ａ，３３３ｂと公開鍵比較部４３３ｃとを有する。検証装置４３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
本形態の設定装置４１０は、第３実施形態の共通パラメータｐｐに加え、さらに公開鍵型暗号学的デバイスの共通パラメータを生成し、それらを共通パラメータｐｐとして、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を得る。その他のセットアップ処理の内容は第３実施形態の設定装置３１０と同じである。設定装置４１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を出力し、共通パラメータｃｒｓは、それぞれ、安全性強化装置４２０および検証装置４３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
本形態の設定装置４１０は、第３実施形態の共通パラメータｐｐに加え、さらに公開鍵型暗号学的デバイスの共通パラメータを生成し、それらを共通パラメータｐｐとして、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を得る。その他のセットアップ処理の内容は第３実施形態の設定装置３１０と同じである。設定装置４１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を出力し、共通パラメータｃｒｓは、それぞれ、安全性強化装置４２０および検証装置４３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理（図６Ａ）]
安全性強化装置４２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行する。鍵生成部４２６ｃが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報ｓに対応する公開鍵ｐと秘密鍵ｋ（鍵情報）との鍵ペア（ｐ，ｋ）を得て出力する（ステップＳ４２３）。その後、第３実施形態で説明したステップＳ３２４およびＳ３２５と同じ処理が実行され、出力部４２７は、ｐとＸとＴＧとを含む補助情報ａｕｘ＝（ｐ，Ｘ，ＴＧ）と秘密情報ｓを出力する（ステップＳ４２６）。
安全性強化装置４２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行する。鍵生成部４２６ｃが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報ｓに対応する公開鍵ｐと秘密鍵ｋ（鍵情報）との鍵ペア（ｐ，ｋ）を得て出力する（ステップＳ４２３）。その後、第３実施形態で説明したステップＳ３２４およびＳ３２５と同じ処理が実行され、出力部４２７は、ｐとＸとＴＧとを含む補助情報ａｕｘ＝（ｐ，Ｘ，ＴＧ）と秘密情報ｓを出力する（ステップＳ４２６）。
[検証処置（図６Ｂ）]
補助情報ａｕｘ＝（ｐ，Ｘ，ＴＧ）と秘密情報ｓは、検証装置４３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、公開鍵比較部４３３ｃが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報ｓに対応する検証用公開鍵ｐ’と秘密鍵ｋ’（鍵情報）との鍵ペア（ｐ’，ｋ’）を得る。公開鍵比較部４３３ｃは、検証用公開鍵ｐ’と公開鍵ｐとが一致するかを判定する（ステップＳ４３４）。検証用公開鍵ｐ’と公開鍵ｐとが一致しないと判定された場合（ｐ≠ｐ’）、出力部４３７が⊥を出力し（ステップＳ１３５）、処理を終える。検証用公開鍵ｐ’と公開鍵ｐとが一致すると判定された場合（ｐ＝ｐ’）、鍵制御部４３６が、秘密鍵ｋ’を出力部４３７に送り、出力部４３７が秘密鍵ｋ’（鍵情報）を出力し（ステップＳ４３６）、処理を終える。
補助情報ａｕｘ＝（ｐ，Ｘ，ＴＧ）と秘密情報ｓは、検証装置４３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、公開鍵比較部４３３ｃが、共通パラメータｐｐと秘密情報ｓを入力とし、鍵生成アルゴリズムｋｅｙ−ｅｘｔｒａｃｔ（ｐｐ，ｓ）を実行し、秘密情報ｓに対応する検証用公開鍵ｐ’と秘密鍵ｋ’（鍵情報）との鍵ペア（ｐ’，ｋ’）を得る。公開鍵比較部４３３ｃは、検証用公開鍵ｐ’と公開鍵ｐとが一致するかを判定する（ステップＳ４３４）。検証用公開鍵ｐ’と公開鍵ｐとが一致しないと判定された場合（ｐ≠ｐ’）、出力部４３７が⊥を出力し（ステップＳ１３５）、処理を終える。検証用公開鍵ｐ’と公開鍵ｐとが一致すると判定された場合（ｐ＝ｐ’）、鍵制御部４３６が、秘密鍵ｋ’を出力部４３７に送り、出力部４３７が秘密鍵ｋ’（鍵情報）を出力し（ステップＳ４３６）、処理を終える。
＜第５実施形態＞
第５実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、補助情報ａｕｘの一部であるＸ＝ｇσ∈ＧＫを公開鍵ｐとして流用する。すなわち、本形態の公開鍵ｐは補助情報ａｕｘの一部であるＸ＝ｇσを含み、これに対応する秘密鍵ｋ（鍵情報）は秘密情報ｓ＝ｈσ∈ＧＫを含む。これにより、補助情報ａｕｘのサイズを第４実施形態よりも小さくできる。
第５実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、補助情報ａｕｘの一部であるＸ＝ｇσ∈ＧＫを公開鍵ｐとして流用する。すなわち、本形態の公開鍵ｐは補助情報ａｕｘの一部であるＸ＝ｇσを含み、これに対応する秘密鍵ｋ（鍵情報）は秘密情報ｓ＝ｈσ∈ＧＫを含む。これにより、補助情報ａｕｘのサイズを第４実施形態よりも小さくできる。
［構成］
図７に例示するように、本形態の安全性強化システム５は、設定装置５１０と安全性強化装置５２０と検証装置５３０とを有する。設定装置５１０と安全性強化装置５２０と検証装置５３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置５１０と安全性強化装置５２０と検証装置５３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図７に例示するように、本形態の安全性強化システム５は、設定装置５１０と安全性強化装置５２０と検証装置５３０とを有する。設定装置５１０と安全性強化装置５２０と検証装置５３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置５１０と安全性強化装置５２０と検証装置５３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
安全性強化装置５２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と補助情報生成部５２６と出力部５２７とを有する。補助情報生成部５２６は、群演算部３２６ａ，３２６ｂを有する。安全性強化装置５２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
検証装置５３０は、入力部１３１と記憶部１３２と判定部３３３と鍵制御部５３６と出力部５３７とを有する。検証装置５３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
本形態の設定装置５１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を得る。設定装置５１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を出力する。ｃｒｓは、それぞれ、安全性強化装置５２０および検証装置５３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
本形態の設定装置５１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を得る。設定装置５１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ）を出力する。ｃｒｓは、それぞれ、安全性強化装置５２０および検証装置５３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理（図８Ａ）]
安全性強化装置５２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行する。ただし、ステップＳ３２２で得られた秘密情報ｓは秘密鍵（鍵情報）として機能する。その後、補助情報生成部５２６の群演算部３２６ａおよび３２６ｂが、第３実施形態で説明したステップＳ３２４およびＳ３２５の処理を実行し、Ｘ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫを得て出力する。ただし、出力部５２４は、ＸとＴＧとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓを出力する。ただし、Ｘは補助情報として用いられるだけではなく、さらに暗号化処理等に公開鍵として用いられる（ステップＳ３２６）。
安全性強化装置５２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行する。ただし、ステップＳ３２２で得られた秘密情報ｓは秘密鍵（鍵情報）として機能する。その後、補助情報生成部５２６の群演算部３２６ａおよび３２６ｂが、第３実施形態で説明したステップＳ３２４およびＳ３２５の処理を実行し、Ｘ＝ｇσ∈ＧＫとＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫを得て出力する。ただし、出力部５２４は、ＸとＴＧとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓを出力する。ただし、Ｘは補助情報として用いられるだけではなく、さらに暗号化処理等に公開鍵として用いられる（ステップＳ３２６）。
[検証処置（図８Ｂ）]
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓと暗号化対象のメッセージｘが、検証装置５３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部５３６が、秘密情報ｓを秘密鍵ｋ’とし、メッセージｘに対する暗号文ＣＰＰ（ｓ，ｘ）（鍵情報から得られる情報）を得（ステップＳ５３４）、出力部５３７が当該暗号文ＣＰＰ（ｓ，ｘ）を出力し（ステップＳ５３６）、処理を終える。なお、ステップＳ５３４で暗号文ＣＰＰ（ｓ，ｘ）を得、ステップＳ５３６で当該暗号文ＣＰＰ（ｓ，ｘ）を出力する代わりに、ステップＳ５３４で秘密情報ｓを秘密鍵ｋ’とし、ステップＳ５３６で秘密鍵ｋ’（鍵情報）を出力してもよい。
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓと暗号化対象のメッセージｘが、検証装置５３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部５３６が、秘密情報ｓを秘密鍵ｋ’とし、メッセージｘに対する暗号文ＣＰＰ（ｓ，ｘ）（鍵情報から得られる情報）を得（ステップＳ５３４）、出力部５３７が当該暗号文ＣＰＰ（ｓ，ｘ）を出力し（ステップＳ５３６）、処理を終える。なお、ステップＳ５３４で暗号文ＣＰＰ（ｓ，ｘ）を得、ステップＳ５３６で当該暗号文ＣＰＰ（ｓ，ｘ）を出力する代わりに、ステップＳ５３４で秘密情報ｓを秘密鍵ｋ’とし、ステップＳ５３６で秘密鍵ｋ’（鍵情報）を出力してもよい。
＜第６実施形態＞
第６実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、公開鍵型暗号学的デバイスとしてＷａｔｅｒｓ ＩＤベース暗号を用い、さらに補助情報ａｕｘであるＸ＝ｇσ∈ＧＫおよびＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫをマスター公開鍵ｍｐｋとして流用し、秘密情報ｓ＝ｈσ∈ＧＫをマスター秘密鍵（鍵情報）ｍｓｋとして用いる。これにより、補助情報ａｕｘのサイズを第４実施形態よりも小さくできる。
第６実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、公開鍵型暗号学的デバイスとしてＷａｔｅｒｓ ＩＤベース暗号を用い、さらに補助情報ａｕｘであるＸ＝ｇσ∈ＧＫおよびＴＧ＝（Ｖ・ＷＨ（Ｘ））σ∈ＧＫをマスター公開鍵ｍｐｋとして流用し、秘密情報ｓ＝ｈσ∈ＧＫをマスター秘密鍵（鍵情報）ｍｓｋとして用いる。これにより、補助情報ａｕｘのサイズを第４実施形態よりも小さくできる。
［構成］
図７に例示するように、本形態の安全性強化システム６は、設定装置６１０と安全性強化装置５２０と検証装置６３０とを有する。検証装置６３０は、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置６１０と安全性強化装置５２０と検証装置６３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図７に例示するように、本形態の安全性強化システム６は、設定装置６１０と安全性強化装置５２０と検証装置６３０とを有する。検証装置６３０は、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置６１０と安全性強化装置５２０と検証装置６３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
検証装置６３０は、入力部１３１と記憶部１３２と判定部３３３と鍵制御部６３６と出力部６３７とを有する。検証装置６３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
本形態の設定装置６１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、さらに群ＧＫからランダムにＹ０，Ｙ１，...，Ｙｎ∈ＧＫを選択し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ，Ｙ０，Ｙ１，...，Ｙｎ）を得る。ただし、ｎは正整数である。設定装置６１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ，Ｙ１，...，Ｙｎ）を出力し、ｃｒｓは、それぞれ、安全性強化装置６２０および検証装置６３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
本形態の設定装置６１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、さらに群ＧＫからランダムにＹ０，Ｙ１，...，Ｙｎ∈ＧＫを選択し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ，Ｙ０，Ｙ１，...，Ｙｎ）を得る。ただし、ｎは正整数である。設定装置６１０はｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ，Ｙ１，...，Ｙｎ）を出力し、ｃｒｓは、それぞれ、安全性強化装置６２０および検証装置６３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理]
本形態の安全性強化処理は第５実施形態と同じである。ただし、Ｘ＝ｇσおよびＴＧ＝（Ｖ・ＷＨ（Ｘ））σがマスター公開鍵ｍｐｋとして機能し、秘密情報ｓ＝ｈσをマスター秘密鍵（鍵情報）ｍｓｋとして機能する。マスター公開鍵ｍｐｋはＩＤ＝（ＩＤ１，...，ＩＤｎ）∈｛０，１｝ｎに対応する公開鍵の生成に用いられ、マスター秘密鍵ｍｓｋはＩＤに対応する秘密鍵の生成に用いられる。
本形態の安全性強化処理は第５実施形態と同じである。ただし、Ｘ＝ｇσおよびＴＧ＝（Ｖ・ＷＨ（Ｘ））σがマスター公開鍵ｍｐｋとして機能し、秘密情報ｓ＝ｈσをマスター秘密鍵（鍵情報）ｍｓｋとして機能する。マスター公開鍵ｍｐｋはＩＤ＝（ＩＤ１，...，ＩＤｎ）∈｛０，１｝ｎに対応する公開鍵の生成に用いられ、マスター秘密鍵ｍｓｋはＩＤに対応する秘密鍵の生成に用いられる。
[検証処置（図９）]
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓとＩＤとが、検証装置５３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部６３６が、共通パラメータｐｐとマスター秘密鍵（鍵情報）ｍｓｋ＝ｓとＩＤとを入力とし、乱数ｄ∈Ｚｑを生成し、ＩＤ＝（ＩＤ１，...，ＩＤｎ）∈｛０，１｝ｎに対応する秘密鍵ｋ’＝ｄｋＩＤ（鍵情報から得られる情報）を以下のように生成する。
ｋ’＝ｄｋＩＤ＝（ｇｄ，ｓ・（ＷａｔＨ（ＩＤ））ｄ）∈ＧＫ ２
ただし、ＷａｔＨ（ＩＤ）を
とする（ステップＳ６３４）。出力部６３７は秘密鍵ｋ’を出力し（ステップＳ６３６）、処理を終える。
補助情報ａｕｘ＝（Ｘ，ＴＧ）と秘密情報ｓとＩＤとが、検証装置５３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、鍵制御部６３６が、共通パラメータｐｐとマスター秘密鍵（鍵情報）ｍｓｋ＝ｓとＩＤとを入力とし、乱数ｄ∈Ｚｑを生成し、ＩＤ＝（ＩＤ１，...，ＩＤｎ）∈｛０，１｝ｎに対応する秘密鍵ｋ’＝ｄｋＩＤ（鍵情報から得られる情報）を以下のように生成する。
ｋ’＝ｄｋＩＤ＝（ｇｄ，ｓ・（ＷａｔＨ（ＩＤ））ｄ）∈ＧＫ ２
ただし、ＷａｔＨ（ＩＤ）を
とする（ステップＳ６３４）。出力部６３７は秘密鍵ｋ’を出力し（ステップＳ６３６）、処理を終える。
＜第７実施形態＞
第７実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、公開鍵型暗号学的デバイスとしてＢｏｙｅｎ−Ｍｅｉ−Ｗａｔｅｒｓ鍵カプセル化方式の変種を用いる。本形態の補助情報はＸ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σに加えてＲ＝ｈρとＴ＝（ｖ・ｗＨ（Ｒ））ρとを含む。ただし、ｖ、ｗが群ＧＫの元であり、ρが乱数である。形態の検証装置は、ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致するかを判定し、ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致するかを判定し、さらにｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致するかを判定する。
第７実施形態を説明する。本形態でも、双線形写像を用いた公開鍵型暗号学的デバイス（Ｓｅｔｕｐ，Ｇｅｎ，Ｃ，Ｘ，Ｙ，Ｋ，Ω）に上述の原理を適用する。ただし本形態では、公開鍵型暗号学的デバイスとしてＢｏｙｅｎ−Ｍｅｉ−Ｗａｔｅｒｓ鍵カプセル化方式の変種を用いる。本形態の補助情報はＸ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σに加えてＲ＝ｈρとＴ＝（ｖ・ｗＨ（Ｒ））ρとを含む。ただし、ｖ、ｗが群ＧＫの元であり、ρが乱数である。形態の検証装置は、ｅ（ｇ，ＴＧ）とｅ（Ｘ，Ｖ・ＷＨ（Ｘ））とが一致するかを判定し、ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致するかを判定し、さらにｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致するかを判定する。
［構成］
図７に例示するように、本形態の安全性強化システム７は、設定装置７１０と安全性強化装置７２０と検証装置７３０とを有する。設定装置７１０と安全性強化装置７２０と検証装置７３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置７１０と安全性強化装置７２０と検証装置７３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
図７に例示するように、本形態の安全性強化システム７は、設定装置７１０と安全性強化装置７２０と検証装置７３０とを有する。設定装置７１０と安全性強化装置７２０と検証装置７３０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置７１０と安全性強化装置７２０と検証装置７３０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
安全性強化装置７２０は、入力部１２１と記憶部１２２と乱数生成部３２３と秘密情報生成部３２４と補助情報生成部７２６と鍵生成部７２５と出力部７２７とを有する。補助情報生成部７２６は、群演算部３２６ａ，３２６ｂ，７２６ｄ，７２６ｅと乱数生成部７２６ｃを有する。安全性強化装置７２０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１２２に格納され、必要に応じて各部に読み込まれる。
検証装置５３０は、入力部１３１と記憶部１３２と判定部７３３と鍵制御部７３６と出力部７３７とを有する。判定部７３３は、比較部３３３ａ，３３３ｂ，７３３ｃを有する。検証装置７３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み込まれる。
[セットアップ処理]
本形態の設定装置７１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、第３実施形態と同じｐｐ，ｈ，Ｖ，Ｗに加え、さらにランダムに元ｖ，ｗ∈ＧＫを選択し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ, v, w）を得る。共通パラメータｃｒｓは、それぞれ、安全性強化装置７２０および検証装置７３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
本形態の設定装置７１０は、第３実施形態と同じ共通パラメータｐｐ＝（ＧＫ，ＧＴ，ｑ，ｅ，ｇ，Ｈ）を生成し、第３実施形態と同じｐｐ，ｈ，Ｖ，Ｗに加え、さらにランダムに元ｖ，ｗ∈ＧＫを選択し、共通パラメータｃｒｓ＝（ｐｐ，ｈ，Ｖ，Ｗ, v, w）を得る。共通パラメータｃｒｓは、それぞれ、安全性強化装置７２０および検証装置７３０の入力部１２１および１３１に入力され、記憶部１２２および１３２に格納される。
[安全性強化処理（図１０Ａ）]
安全性強化装置７２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行し、群演算部３２６ａ，３２６ｂが、第３実施形態で説明したステップＳ３２４およびＳ３２５の処理を実行する。次に、乱数生成部７２６ｃが、ｐｐを入力として第２乱数ρ∈Ｚｑを選択して出力する（ステップＳ７２１）。群演算部７２６ｄは、ｐｐ，ρを入力とし、乱数ρに対するＲ＝ｇρ∈ＧＫを得て出力する（ステップＳ７２２）。群演算部７２６ｅは、ｐｐ，ｖ，ｗ，Ｒ，ρを入力とし、Ｔ＝（ｖ・ｗＨ（Ｒ））ρ∈ＧＫを得て出力する（ステップＳ７２３）。鍵生成部７２５は、ｐｐ，Ｘ，ｈ，ρを入力とし、鍵（鍵情報）ｋ＝ｅ（Ｘ，ｈ）ρ∈ＧＫを得て出力する。出力部７２７は、ＸとＴＧとＲとＴとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ，Ｒ，Ｔ）を暗号文とし、当該補助情報ａｕｘと鍵ｋと秘密情報ｓとを出力する（ステップＳ７２６）。
安全性強化装置７２０の乱数生成部３２３および秘密情報生成部３２４が、第３実施形態で説明したステップＳ３２１およびＳ３２２の処理を実行し、群演算部３２６ａ，３２６ｂが、第３実施形態で説明したステップＳ３２４およびＳ３２５の処理を実行する。次に、乱数生成部７２６ｃが、ｐｐを入力として第２乱数ρ∈Ｚｑを選択して出力する（ステップＳ７２１）。群演算部７２６ｄは、ｐｐ，ρを入力とし、乱数ρに対するＲ＝ｇρ∈ＧＫを得て出力する（ステップＳ７２２）。群演算部７２６ｅは、ｐｐ，ｖ，ｗ，Ｒ，ρを入力とし、Ｔ＝（ｖ・ｗＨ（Ｒ））ρ∈ＧＫを得て出力する（ステップＳ７２３）。鍵生成部７２５は、ｐｐ，Ｘ，ｈ，ρを入力とし、鍵（鍵情報）ｋ＝ｅ（Ｘ，ｈ）ρ∈ＧＫを得て出力する。出力部７２７は、ＸとＴＧとＲとＴとを含む補助情報ａｕｘ＝（Ｘ，ＴＧ，Ｒ，Ｔ）を暗号文とし、当該補助情報ａｕｘと鍵ｋと秘密情報ｓとを出力する（ステップＳ７２６）。
[検証処置（図１０Ｂ）]
補助情報ａｕｘ＝（Ｘ，ＴＧ，Ｒ，Ｔ）と鍵ｋと秘密情報ｓは、検証装置７３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、比較部７３３ｃが、ｅ（ｇ，Ｔ）∈ＧＴとｅ（Ｒ，ｖ・ｗＨ（Ｒ））∈ＧＴとが一致するかを判定する（ステップＳ７３３）。これらが一致しないと判定された場合（ｅ（ｇ，Ｔ）≠ｅ（Ｒ，ｖ・ｗＨ（Ｒ）））、出力部７３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致すると判定された場合（ｅ（ｇ，Ｔ）＝ｅ（Ｒ，ｖ・ｗＨ（Ｒ）））、鍵制御部７３６が、ｐｐ，Ｒ，ｓを入力とし、鍵（鍵情報）ｋ’＝ｅ（Ｒ，ｓ）∈ＧＴを得て出力し、出力部７３７が鍵ｋ’を出力する。
補助情報ａｕｘ＝（Ｘ，ＴＧ，Ｒ，Ｔ）と鍵ｋと秘密情報ｓは、検証装置７３０の入力部１３１に入力されて記憶部１３２に格納される。その後、ステップＳ３３１，３３２，Ｓ１３５の処理が、第３実施形態で説明した通りに実行される。ステップＳ３３２でｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致すると判定された場合（ｅ（ｇ，ｓ）＝ｅ（Ｘ，ｈ））、比較部７３３ｃが、ｅ（ｇ，Ｔ）∈ＧＴとｅ（Ｒ，ｖ・ｗＨ（Ｒ））∈ＧＴとが一致するかを判定する（ステップＳ７３３）。これらが一致しないと判定された場合（ｅ（ｇ，Ｔ）≠ｅ（Ｒ，ｖ・ｗＨ（Ｒ）））、出力部７３７が⊥を出力し（ステップＳ１３５）、処理を終える。ｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗＨ（Ｒ））とが一致すると判定された場合（ｅ（ｇ，Ｔ）＝ｅ（Ｒ，ｖ・ｗＨ（Ｒ）））、鍵制御部７３６が、ｐｐ，Ｒ，ｓを入力とし、鍵（鍵情報）ｋ’＝ｅ（Ｒ，ｓ）∈ＧＴを得て出力し、出力部７３７が鍵ｋ’を出力する。
＜その他の変形例等＞
なお、本発明は上述の実施形態に限定されるものではない。例えば、安全性強化装置や検証装置が複数個存在してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
なお、本発明は上述の実施形態に限定されるものではない。例えば、安全性強化装置や検証装置が複数個存在してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
１〜７ 安全性強化システム
１１０〜７１０ 設定装置
１２０〜７２０ 安全性強化装置
１３０〜７３０ 検証装置
１１０〜７１０ 設定装置
１２０〜７２０ 安全性強化装置
１３０〜７３０ 検証装置
Claims (10)
- 秘密の鍵情報に対応する秘密情報を格納する記憶部と、前記秘密情報に対して特定の対応関係を持つ補助情報を得て出力する補助情報生成部と、を含む安全性強化装置と、
入力された前記補助情報が前記秘密情報に対して前記特定の対応関係を持つかを判定する判定部と、前記補助情報が前記秘密情報に対して前記対応関係を持つ場合に前記秘密情報に対応する秘密の鍵情報または前記鍵情報から得られる情報を得、前記補助情報が前記秘密情報に対して前記対応関係を持たない場合に拒絶を表す情報を出力する鍵制御部と、を含む検証装置と、を有し、
前記秘密情報と異なる関連秘密情報に対して前記対応関係を持つ関連補助情報を前記補助情報から特定することが困難である、
ことを特徴とする安全性強化システム。 - 請求項１の安全性強化システムであって、
前記補助情報が、前記秘密情報に対応する第１暗号文と、前記秘密情報と乱数とに対応する第２暗号文と、前記秘密情報と前記乱数とを証拠情報として前記第１暗号文と前記第２暗号文とに対する非対話零知識証明を行うための証明情報と、を含み、
前記判定部が、
前記証明情報を用いて前記第１暗号文と前記第２暗号文とに対する非対話零知識証明検証を行う検証部と、
前記秘密情報に対応する検証用暗号文と前記第１暗号文とが一致するかを判定する暗号文比較部と、を含む、
ことを特徴とする安全性強化システム。 - 請求項１の安全性強化システムであって、
ｈ、ｚ、ＶおよびＷが群ＧＫの元、ｇが前記群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅが双線形写像であり、
前記秘密情報が、乱数σに対するｓ＝ｈσであり、
前記鍵情報が、ｅ（ｚ，ｓ）を含み、
前記補助情報が、Ｘ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σとを含み、
前記判定部が、
ｅ（ｇ，Ｔ Ｇ ）とｅ（Ｘ，Ｖ・Ｗ Ｈ（Ｘ） ）とが一致するかを判定する第１比較部と、
ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致するかを判定する第２比較部と、を含む、ことを特徴とする安全性強化システム。 - 請求項２または３の安全性強化システムであって、
前記補助情報が、さらに、前記秘密情報に対応する公開鍵を含み、
前記判定部が、さらに、前記秘密情報に対応する検証用公開鍵と前記公開鍵とが一致するかを判定する公開鍵比較部を含む、
ことを特徴とする安全性強化システム。 - 請求項１の安全性強化システムであって、
ｈ、ＶおよびＷが群ＧＫの元、ｇが前記群ＧＫの生成元、Ｈが衝突困難性を持つ写像、ｅが双線形写像であり、
前記秘密情報が、乱数σに対するｓ＝ｈσであり、
前記鍵情報が、ｓを含み、
前記補助情報が、Ｘ＝ｇσとＴＧ＝（Ｖ・ＷＨ（Ｘ））σとを含み、
前記判定部が、
ｅ（ｇ，Ｔ Ｇ ）とｅ（Ｘ，Ｖ・Ｗ Ｈ（Ｘ） ）とが一致するかを判定する第１比較部と、
ｅ（ｇ，ｓ）とｅ（Ｘ，ｈ）とが一致するかを判定する第２比較部と、を含む、ことを特徴とする安全性強化システム。 - 請求項５の安全性強化システムであって、
ｖ、ｗ、ＲおよびＴが前記群ＧＫの元であり、
前記補助情報が、さらに、第２乱数ρに対するＲ＝ｈρとＴ＝（ｖ・ｗＨ（Ｒ））ρとを含み、
前記判定部が、ｅ（ｇ，Ｔ）とｅ（Ｒ，ｖ・ｗ Ｈ（Ｒ） ）とが一致するかを判定する第３比較部を含む、
ことを特徴とする安全性強化システム。 - 請求項１から６の何れかの安全性強化システムにおける安全性強化装置。
- 請求項１から６の何れかの安全性強化システムにおける検証装置。
- 請求項７の安全性強化装置としてコンピュータを機能させるためのプログラム。
- 請求項８の検証装置としてコンピュータを機能させるためのプログラム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2013003706A JP5871827B2 (ja) | 2013-01-11 | 2013-01-11 | 安全性強化システム、安全性強化装置、検証装置、およびプログラム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2013003706A JP5871827B2 (ja) | 2013-01-11 | 2013-01-11 | 安全性強化システム、安全性強化装置、検証装置、およびプログラム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2014135687A JP2014135687A (ja) | 2014-07-24 |
| JP5871827B2 true JP5871827B2 (ja) | 2016-03-01 |
Family
ID=51413659
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2013003706A Active JP5871827B2 (ja) | 2013-01-11 | 2013-01-11 | 安全性強化システム、安全性強化装置、検証装置、およびプログラム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP5871827B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP6267657B2 (ja) * | 2015-01-07 | 2018-01-24 | 日本電信電話株式会社 | 安全性強化方法、安全性強化システム、安全性強化装置、検証装置、およびプログラム |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4961909B2 (ja) * | 2006-09-01 | 2012-06-27 | ソニー株式会社 | 暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラム |
| JP5682527B2 (ja) * | 2011-03-28 | 2015-03-11 | ソニー株式会社 | 暗号処理装置、および暗号処理方法、並びにプログラム |
-
2013
- 2013-01-11 JP JP2013003706A patent/JP5871827B2/ja active Active
Also Published As
| Publication number | Publication date |
|---|---|
| JP2014135687A (ja) | 2014-07-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Coron et al. | Fully homomorphic encryption over the integers with shorter public keys | |
| Abusukhon et al. | A hybrid network security algorithm based on Diffie Hellman and Text-to-Image Encryption algorithm | |
| JP4786531B2 (ja) | 暗号システム、暗号装置、復号装置、プログラムおよび集積回路 | |
| US20140233731A1 (en) | Device and Method for Generating Keys with Enhanced Security for Fully Homomorphic Encryption Algorithm | |
| CN105933101B (zh) | 一种基于参数高次偏移的全同态加密公钥压缩方法 | |
| TWI511517B (zh) | Information processing apparatus, information processing method, program and recording medium | |
| JP4620669B2 (ja) | 署名生成装置、署名検証装置、それらの方法、および集積回路 | |
| JP5730805B2 (ja) | 格子問題に基づく階層型内積暗号システム，格子問題に基づく階層型内積暗号方法，装置 | |
| JP5871827B2 (ja) | 安全性強化システム、安全性強化装置、検証装置、およびプログラム | |
| JPWO2006114948A1 (ja) | 署名生成装置および署名検証装置 | |
| JP5300373B2 (ja) | 代数的トーラスを用いたデータ圧縮処理を行う装置およびプログラム | |
| JP5314449B2 (ja) | 電子署名検証システム、電子署名装置、検証装置、電子署名検証方法、電子署名方法、検証方法、電子署名プログラム、検証プログラム | |
| JP2017038336A (ja) | 復号方法 | |
| CN112733176B (zh) | 基于全域哈希的标识密码加密方法 | |
| Easttom | More approaches to quantum-resistant cryptography | |
| JP6267657B2 (ja) | 安全性強化方法、安全性強化システム、安全性強化装置、検証装置、およびプログラム | |
| Harjito et al. | Comparative Analysis between Elgamal and NTRU Algorithms and their implementation of Digital Signature for Electronic Certificate | |
| Biryukov et al. | PURED: A unified framework for resource-hard functions | |
| WO2017203743A1 (ja) | 暗号化装置、復号装置及び暗号システム | |
| CN118764170B (zh) | 数据处理方法、系统、设备、存储介质和程序产品 | |
| JP5931797B2 (ja) | 署名システム及び方法、署名生成装置並びに署名検証装置 | |
| Orsini et al. | Bootstrapping BGV ciphertexts with a wider choice of p and q | |
| JP5871826B2 (ja) | 認証子生成装置、検証装置、およびプログラム | |
| JP2015213233A (ja) | 鍵生成装置、再暗号化装置、およびプログラム | |
| JP6087849B2 (ja) | 代理署名装置、署名検証装置、鍵生成装置、代理署名システム、およびプログラム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20150204 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20150925 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20151104 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20151209 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20160105 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20160112 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 5871827 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |