(57)【要約】【課題】暗号文及び秘密鍵の最大の長さが限定されない、内積関数型暗号方式を構築可能にする。【解決手段】暗号化装置２０は、一定のサイズの公開情報を入力として生成された暗号化設定情報であって、ベクトルｘのサイズに応じたサイズの暗号化設定情報を用いて、ベクトルｘが暗号化された暗号文ｃｔｘを生成する。鍵生成装置３０は、公開情報を入力として生成された鍵設定情報であって、ベクトルｙのサイズに応じたサイズの鍵設定情報を用いて、ベクトルｙが設定された秘密鍵ｓｋｙを生成する。復号装置４０は、暗号文ｃｔｘを秘密鍵ｓｋｙで復号して、ベクトルｘとベクトルｙとの内積値を計算する。【選択図】図１
2019215391.tif 000002
【特許請求の範囲】
【請求項１】
一定のサイズの公開情報を入力として定義された暗号化設定情報であって、ベクトルｘのサイズに応じたサイズの暗号化設定情報を用いて、前記ベクトルｘが暗号化された暗号文ｃｔｘを取得する暗号文取得部と、
前記公開情報を入力として定義された鍵設定情報であって、ベクトルｙのサイズに応じたサイズの鍵設定情報を用いて、前記ベクトルｙが設定された秘密鍵ｓｋｙを取得する秘密鍵取得部と、
前記暗号文取得部によって取得された前記暗号文ｃｔｘを、前記秘密鍵取得部によって取得された前記秘密鍵ｓｋｙで復号して、前記ベクトルｘと前記ベクトルｙとの内積値を計算する復号部と
を備える復号装置。
【請求項２】
前記暗号化設定情報及び前記鍵設定情報は、前記公開情報を入力として、疑似ランダム関数により定義された
請求項１に記載の復号装置。
【請求項３】
前記暗号化設定情報は、行列Ｂであり、
前記暗号文ｃｔｘは、前記ベクトルｘの各要素ｘｉを対象として、対象の要素ｘｉと前記行列Ｂとの積が群要素に設定された要素［ｃｉ］１を含み、
前記鍵設定情報は、前記行列Ｂの随伴行列Ｂ＊であり、
前記秘密鍵ｓｋｙは、前記ベクトルｙの各要素ｙｉを対象として、対象の要素ｙｉと前記随伴行列Ｂ＊との積が群要素に設定された要素［ｋｉ］２を含み、
前記復号部は、前記暗号文ｃｔｘと前記秘密鍵ｓｋｙとについてのペアリング演算を計算することにより、前記内積値を計算する
請求項２に記載の復号装置。
【請求項４】
前記暗号文ｃｔｘは、１以上の整数ｍと、ｉ＝１，．．．，ｍの各整数ｉについての行列Ｂである行列Ｂｉとについて、数１に示す要素ｃｉが群要素に設定された要素［ｃｉ］１を含み、
前記秘密鍵ｓｋｙは、整数の集合Ｓと、前記集合Ｓに含まれる各整数ｉについての随伴行列Ｂ＊である行列Ｂ＊ｉとについて、数２に示す要素ｋｉが群要素に設定された要素［ｋｉ］２を含む
請求項３に記載の復号装置。
【数１】
2019215391.tif 000058
【数２】
2019215391.tif 000059
【請求項５】
前記暗号化設定情報は、前記ベクトルｘの要素毎に生成されたインデックス情報Ｉが前記公開情報に設定されて定義され、
前記鍵設定情報は、前記ベクトルｙの要素毎に生成されたインデックス情報Ｉ’であって、前記ベクトルｘの対応する要素に対して生成されたインデックス情報Ｉとの内積値が０になるように生成されたインデックス情報Ｉ’が前記公開情報に設定されて定義された
請求項１に記載の復号装置。
【請求項６】
前記暗号文ｃｔｘは、前記ベクトルｘの各要素ｘｉを対象として、前記インデックス情報Ｉと対象の要素ｘｉとを設定したベクトルと、前記公開情報である行列Ｂとの積が群要素に設定された要素［ｃｉ］１を含み、
前記秘密鍵ｓｋｙは、前記ベクトルｙの各要素ｙｉを対象として、前記インデックス情報Ｉ’と対象の要素ｙｉとを設定したベクトルと、前記行列Ｂの随伴行列Ｂ＊との積が群要素に設定された要素［ｋｉ］２を含み、
前記復号部は、前記暗号文ｃｔｘと前記秘密鍵ｓｋｙとについてのペアリング演算を計算することにより、前記内積値を計算する
請求項５に記載の復号装置。
【請求項７】
前記暗号文ｃｔｘは、１以上の整数ｍと、ｉ＝１，．．．，ｍの各整数ｉについてのインデックス情報Ｉであるπｉ（１，ｉ）とについて、数３に示す要素ｃｉが群要素に設定された要素［ｃｉ］１を含み、
前記秘密鍵ｓｋｙは、整数の集合Ｓと、前記集合Ｓに含まれる各整数ｉについてのインデックス情報Ｉ’であるρｉ（−ｉ，１）とについて、数４に示す要素ｋｉが群要素に設定された要素［ｋｉ］２を含む
請求項６に記載の復号装置。
【数３】
2019215391.tif 000060
【数４】
2019215391.tif 000061
【請求項８】
ベクトルｘが暗号化された暗号文ｃｔｘを、ベクトルｙが設定された秘密鍵ｓｋｙで復号することにより、前記ベクトルｘと前記ベクトルｙとの内積値を計算する暗号システムにおける暗号化装置であり、
一定のサイズの公開情報を入力として、暗号化する対象のベクトルｘのサイズに応じたサイズの暗号化設定情報を定義する設定情報定義部と、
前記設定情報定義部によって定義された前記暗号化設定情報を用いて、前記ベクトルｘを暗号化して暗号文ｃｔｘを生成する暗号化部と
を備える暗号化装置。
【請求項９】
前記設定情報定義部は、前記公開情報を入力として、疑似ランダム関数により前記暗号化設定情報を定義する
請求項８に記載の暗号化装置。
【請求項１０】
前記設定情報定義部は、行列Ｂを前記暗号化設定情報として定義し、
前記暗号化部は、前記ベクトルｘの各要素ｘｉを対象として、対象の要素と前記行列Ｂとの積が群要素に設定された要素［ｃｉ］１を含む前記暗号文ｃｔｘを生成する
請求項９に記載の暗号化装置。
【請求項１１】
前記暗号化部は、１以上の整数ｍと、ｉ＝１，．．．，ｍの各整数ｉについての行列Ｂである行列Ｂｉとについて、数５に示す要素ｃｉが群要素に設定された要素［ｃｉ］１を含む前記暗号文ｃｔｘを生成する
請求項１０に記載の暗号化装置。
【数５】
2019215391.tif 000062
【請求項１２】
前記設定情報定義部は、前記ベクトルｘの要素毎に生成されたインデックス情報Ｉを前記公開情報に設定した情報を、前記暗号化設定情報と定義する
請求項８に記載の暗号化装置。
【請求項１３】
前記暗号文ｃｔｘは、前記ベクトルｘの各要素ｘｉを対象として、前記インデックス情報Ｉと対象の要素とを設定したベクトルと、前記公開情報である行列Ｂとの積が群要素に設定された要素［ｃｉ］１を含む前記暗号文ｃｔｘを生成する
請求項１２に記載の暗号化装置。
【請求項１４】
前記暗号化部は、１以上の整数ｍと、ｉ＝１，．．．，ｍの各整数ｉについてのインデックス情報Ｉであるπｉ（１，ｉ）とについて、数６に示す要素ｃｉが群要素に設定された要素［ｃｉ］１を含む前記暗号文ｃｔｘを生成する
請求項１３に記載の暗号化装置。
【数６】
2019215391.tif 000063
【請求項１５】
一定のサイズの公開情報を入力として生成された暗号化設定情報であって、ベクトルｘのサイズに応じたサイズの暗号化設定情報を用いて、前記ベクトルｘが暗号化された暗号文ｃｔｘを生成する暗号化装置と、
前記公開情報を入力として生成された鍵設定情報であって、ベクトルｙのサイズに応じたサイズの鍵設定情報を用いて、前記ベクトルｙが設定された秘密鍵ｓｋｙを生成する鍵生成装置と、
前記暗号化装置によって生成された前記暗号文ｃｔｘを、前記鍵生成装置によって生成された前記秘密鍵ｓｋｙで復号して、前記ベクトルｘと前記ベクトルｙとの内積値を計算する復号装置と
を備える暗号システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、内積関数型暗号（以下、ＩＰＦＥ）に関する。
【背景技術】
【０００２】
非特許文献１には、ＩＰＦＥ方式が記載されている。ＩＰＦＥは、実用的な統計処理及び情報処理を、プライバシーを保護したまま行うのに、大変有用である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ａｂｄａｌｌａ，  Ｍ．，  Ｂｏｕｒｓｅ，  Ｆ．，  Ｄｅ  Ｃａｒｏ，  Ａ．，  Ｐｏｉｎｔｃｈｅｖａｌ，  Ｄ．：  Ｓｉｍｐｌｅ  ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔｓ．  Ｉｎ：  Ｋａｔｚ，  Ｊ．  （ｅｄ．）  ＰＫＣ  ２０１５．  ＬＮＣＳ，  ｖｏｌ．  ９０２０，  ｐｐ．  ７３３−７５１．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （Ｍａｒ  ／  Ａｐｒ  ２０１５）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に記載されたＩＰＦＥ方式では、セットアップフェーズにおいて生成されるマスター鍵によって、方式で用いられるベクトルの最大の長さが固定される。つまり、方式で用いられる暗号文及び秘密鍵の最大の長さが固定される。最大の長さが固定された後に、その長さを超えた暗号文及び秘密鍵を扱うことはできない。
セットアップフェーズにおいて、どのようなデータが暗号化されるか、また、暗号文を用いてどのような情報処理が行われるかは決まっていない場合がある。この場合には、暗号文及び秘密鍵の最大の長さを決定することは困難である。なお、最大の長さを非常に長くしておくことが考えられる。しかし、これは、不要な効率の悪化を招くことになる。
この発明は、暗号文及び秘密鍵の最大の長さが限定されない、ＩＰＦＥ方式を構築可能にすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る復号装置は、
一定のサイズの公開情報を入力として生成された暗号化設定情報であって、ベクトルｘのサイズに応じたサイズの暗号化設定情報を用いて、前記ベクトルｘが暗号化された暗号文ｃｔｘを取得する暗号文取得部と、
前記公開情報を入力として生成された鍵設定情報であって、ベクトルｙのサイズに応じたサイズの鍵設定情報を用いて、前記ベクトルｙが設定された秘密鍵ｓｋｙを取得する秘密鍵取得部と、
前記暗号文取得部によって取得された前記暗号文ｃｔｘを、前記秘密鍵取得部によって取得された前記秘密鍵ｓｋｙで復号して、前記ベクトルｘと前記ベクトルｙとの内積値を計算する復号部と
を備える。
【発明の効果】
【０００６】
この発明では、暗号文ｃｔｘは、一定のサイズの公開情報を入力として生成された暗号化設定情報であって、ベクトルｘのサイズに応じたサイズの暗号化設定情報を用いて、ベクトルｘが暗号化されて生成される。また、秘密鍵ｓｋｙは、一定のサイズの公開情報を入力として生成された鍵設定情報であって、ベクトルｙのサイズに応じたサイズの鍵設定情報を用いて、ベクトルｙが設定されて生成される。そして、暗号文ｃｔｘが秘密鍵ｓｋｙで復号されて、ベクトルｘとベクトルｙとの内積値が計算される。そのため、暗号文及び秘密鍵の最大の長さが限定されない、ＩＰＦＥ方式を構築可能にすることができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１に係る暗号システム１の構成図。
【図２】実施の形態１に係るセットアップ装置１０の構成図。
【図３】実施の形態１に係る暗号化装置２０の構成図。
【図４】実施の形態１に係る鍵生成装置３０の構成図。
【図５】実施の形態１に係る復号装置４０の構成図。
【図６】実施の形態１に係るセットアップ装置１０の動作を示すフローチャート。
【図７】実施の形態１に係る暗号化装置２０の動作を示すフローチャート。
【図８】実施の形態１に係る鍵生成装置３０の動作を示すフローチャート。
【図９】実施の形態１に係る復号装置４０の動作を示すフローチャート。
【図１０】変形例１に係るセットアップ装置１０の構成図。
【図１１】変形例１に係る暗号化装置２０の構成図。
【図１２】変形例１に係る鍵生成装置３０の構成図。
【図１３】変形例１に係る復号装置４０の構成図。
【図１４】実施の形態２に係る暗号システム１の構成図。
【発明を実施するための形態】
【０００８】
実施の形態１．
＊＊＊表記＊＊＊
以下の説明で用いられる表記を説明する。
素数ｐに対して、数１０１は、数１０２に示す体を示す。
【数１０１】
2019215391.tif 000003
【数１０２】
2019215391.tif 000004
【０００９】
自然数ｎ，ｍに対して、［ｎ］は、集合｛１，．．．，ｎ｝を示し、［ｍ，ｎ］は、集合｛ｍ，．．．，ｎ｝を示す。
【００１０】
集合Ｓに対して、数１０３は、ｓがＳから一様に選択されることを示す。
【数１０３】
2019215391.tif 000005
【００１１】
ベクトルは、行ベクトルとして扱う。ベクトルｘに対して、数１０４は、無限大ノルムを示す。
【数１０４】
2019215391.tif 000006
【００１２】
体Ｋに対して、Ｍｎ（Ｋ）は、Ｋにおける要素を有する全てのｎ×ｎ行列の集合を示し、ＧＬｎ（Ｋ）は、Ｋにおける要素を有する全てのｎ×ｎの正則行列の集合を示す。
【００１３】
正則行列Ａに対して、Ａ＊は、（Ａ−１）Ｔ、つまり随伴行列を示す。
【００１４】
巡回群Ｇιの生成元ｇιと、行列Ａ及びベクトルａとに対して、［Ａ］ι及び［ａ］ιは、それぞれ、生成元ｇιの指数部の行列及びベクトルを示す。つまり、［Ａ］ιは、ｇιＡを示し、［ａ］ιは、ｇιａを示す。
【００１５】
数１０５に示すベクトルｘ及びベクトルｙに対して、数１０６は、数１０７によって指数部の内積を計算する関数を示す。
【数１０５】
2019215391.tif 000007
【数１０６】
2019215391.tif 000008
【数１０７】
2019215391.tif 000009
【００１６】
＊＊＊定義＊＊＊
以下の説明で用いられる用語の定義を説明する。
＜ＩＰＦＥ＞
ＩＰＦＥは、マスター秘密鍵ｍｓｋの所有者がベクトルｙに対して秘密鍵ｓｋｙを発行可能であり、ベクトルｘの暗号文ｃｔｘを秘密鍵ｓｋｙで復号するとベクトルｘとベクトルｙとの内積値だけが明らかになる方式である。
内積値の計算は、数値データに対する重み付けと、統計的な計算に対する利用といった様々な応用が可能である。
【００１７】
＜双線形群＞
双線形群Ｇ：＝（ｐ，Ｇ１，Ｇ２，ＧＴ，ｇ１，ｇ２，ｅ）は、素数ｐと、位数ｐの巡回群Ｇ１，Ｇ２，ＧＴと、巡回群Ｇ１の生成元ｇ１と、巡回群Ｇ２の生成元ｇ２と、数１０８に示す双線形写像ｅとを備え、以下の双線形性と非退化性との２つの性質を有する。
【数１０８】
2019215391.tif 000010
【００１８】
（双線形性）
数１０９が成立する。
【数１０９】
2019215391.tif 000011
（非退化性）
生成元ｇ１，ｇ２に対して、ｅ（ｇ１，ｇ２）がＧＴの生成元である。
【００１９】
＜双対ペアリングベクトル空間（以下、ＤＰＶＳ）＞
自然数ｎに対して、数１１０に示すように、ランダムに双対正規直交基底（Ｂ，Ｂ＊）を選択することが可能である。
【数１１０】
2019215391.tif 000012
そして、［Ｂ］１及び［Ｂ＊］２は、それぞれ、ベクトル空間Ｖ：＝Ｇ１ｎ及びＶ＊：＝Ｇ２ｎの双対正規直交基底である。
【００２０】
以下の２つの性質が成立する。
（性質１）
数１１１に示すどんなベクトルｘ，ｙに対しても、数１１２が成立する。
【数１１１】
2019215391.tif 000013
【数１１２】
2019215391.tif 000014
【００２１】
（性質２）
数１１３に示すどんなベクトルｘ１，．．．，ｘｋ及びベクトルｙ１，．．．，ｙＬと、行列Ｍとに対しても、数１１４は一様に分散する。
【数１１３】
2019215391.tif 000015
【数１１４】
2019215391.tif 000016
さらに、数１１５に示すどんな集合Ｓに対しても、数１１６は一様に分散する。
【数１１５】
2019215391.tif 000017
【数１１６】
2019215391.tif 000018
これは、数１１７がランダムな双対正規直交基底であり、数１１８であるためである。
【数１１７】
2019215391.tif 000019
【数１１８】
2019215391.tif 000020
【００２２】
＜暗号方式の条件＞
暗号化と鍵生成と復号との条件を説明する。
【００２３】
暗号化及び鍵生成については、連続（ｃｏｎ）と、分離（ｓｅｐ）との２つの条件がある。
連続設定では、ベクトルが暗号化又は鍵生成のアルゴリズムに入力されると、ベクトルの各要素に対して、その位置によって自動的にインデックスが設定される。つまり、ベクトル（ａ，ｂ，ｃ）に対して、ａのインデックスは１が設定され、ｂのインデックスは２が設定され、ｃのインデックスは３が設定される。
分離設定では、インデックスの集合がベクトルに付加されており、暗号化及び鍵生成は、インデックスの集合に対応して実行される。言い換えると、ベクトル（ａ，ｂ，ｃ）は、ある集合、例えば｛１，５，６｝によってインデックスが設定される。つまり、ａのインデックスは１が設定され、ｂのインデックスは５が設定され、ｃのインデックスは６が設定される。
【００２４】
復号については、ｃｔ−ｄｏｍｉｎａｎｔ方式と、ｓｋ−ｄｏｍｉｎａｎｔ方式と、ｅｑｕａｌ方式との３つの条件がある。
Ｓｃｔを暗号文ｃｔのインデックスの集合とし、Ｓｓｋを秘密鍵ｓｋのインデックスの集合とする。このとき、ｃｔ−ｄｏｍｉｎａｎｔ方式では、Ｓｃｔ⊇Ｓｓｋの場合に限り、暗号文ｃｔが秘密鍵ｓｋで復号される。ｓｋ−ｄｏｍｉｎａｎｔ方式では、Ｓｃｔ⊆Ｓｓｋの場合に限り、暗号文ｃｔが秘密鍵ｓｋで復号される。ｅｑｕａｌ方式では、Ｓｃｔ＝Ｓｓｋの場合に限り、暗号文ｃｔが秘密鍵ｓｋで復号される。
【００２５】
以下の説明では、方式の条件を（Ｅ：ｘｘ，Ｋ：ｙｙ，Ｄ：ｚｚ）と記述する。ｘｘ，ｙｙは、連続設定を表すｃｏｎと、分離設定を表すｓｅｐとのいずれかが設定される。ｚｚは、ｃｔ−ｄｏｍｉｎａｎｔ方式を表すｃｔ−ｄｏｍと、ｓｋ−ｄｏｍｉｎａｎｔ方式を表すｓｋ−ｄｏｍと、ｅｑｕａｌ方式を表すｅｑとのいずれかが設定される。
実施の形態１では、（Ｅ：ｃｏｎ，Ｋ：ｓｅｐ，Ｄ：ｃｔ−ｄｏｍ）セッティングについて説明する。つまり、実施の形態１では、長さｍのベクトルの暗号文と、集合Ｓが付加された秘密鍵とに対して、Ｓ⊆［ｍ］の場合に限り、暗号文を秘密鍵で復号でき、集合Ｓに関する内積値が得られる方式を説明する。しかし、後の実施の形態で説明するように、他の設定についても実現可能である。
【００２６】
＜ノルム上限＞
実施の形態１で説明するＵｎｂｏｕｎｄｅｄ  ＩＰＦＥ（以下、ＵＩＰＦＥ）方式では、復号時に離散対数問題を解く処理が含まれる。そのため、扱うベクトルのノルムに上限が置かれる。ここでは、ＩＰＦＥ方式で使用される関数を以下のように定義することにより、扱うベクトルのノルムに上限が置かれる。
【００２７】
関数族Ｆは、数１１９に示す関数ｆＳ，ｙＸ，Ｙによって構成される。
【数１１９】
2019215391.tif 000021
数１２０に示す全てのベクトルｘに対して、数１２１の関数が定義される。
【数１２０】
2019215391.tif 000022
【数１２１】
2019215391.tif 000023
【００２８】
＊＊＊構成の説明＊＊＊
＜Ｐｒｉｖａｔｅ−ｋｅｙ  ＵＩＰＦＥの構成＞
実施の形態１では、Ｐｒｉｖａｔｅ−ｋｅｙ  ＵＩＰＦＥを説明する。Ｐｒｉｖａｔｅ−ｋｅｙ  ＵＩＰＦＥは、秘密鍵セッティングのＵＩＰＦＥである。秘密鍵セッティングは、暗号文の作成に秘密鍵が必要な方式である。
秘密鍵セッティングの暗号化方式には、端末のバックアップデータをクラウドに置いておき、必要に応じてバックアップデータをクラウドから取得するというような、暗号化と復号とを同じユーザが行うケースといった実際的な応用が存在する。
【００２９】
Ｐｒｉｖａｔｅ−ｋｅｙ  ＵＩＰＦＥは、Ｓｅｔｕｐアルゴリズムと、Ｅｎｃアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｄｅｃアルゴリズムとを含む。Χ：＝｛Ｘλ｝λ∈Ｎ，Υ：＝｛Ｙλ｝λ∈Ｎをノルム上限の集合体とする。ここで、Ｎは、自然数の集合である。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｐと、マスター秘密鍵ｍｓｋとを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｐと、マスター秘密鍵ｍｓｋと、ベクトルｘ：＝（ｘ１，．．．，ｘｍ）とを入力として、暗号文ｃｔｘを出力する。ここで、ｍ：＝ｍ（λ）は、多項式である。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｐと、マスター秘密鍵ｍｓｋと、空でない集合Ｓ：＝［ｓ］と、インデックス付けされたベクトルｙ：＝（ｙｉ）ｉ∈Ｓとを入力として、秘密鍵ｓｋｙを出力する。ここで、ｓ：＝ｓ（λ）は、多項式である。
Ｄｅｃアルゴリズムは、公開パラメータｐｐと、暗号文ｃｔｘと、秘密鍵ｓｋｙとを入力として、復号された値ｄ∈Ｚ、又は、識別子⊥を出力する。ここで、Ｚは、実数の集合である。識別子⊥は、復号できないことを示す。
【００３０】
＜暗号システム１の構成＞
図１を参照して、実施の形態１に係る暗号システム１の構成を説明する。
暗号システム１は、セットアップ装置１０と、暗号化装置２０と、鍵生成装置３０と、復号装置４０とを備える。セットアップ装置１０と暗号化装置２０と鍵生成装置３０と復号装置４０とは、ネットワークを介して接続される。
【００３１】
図２を参照して、実施の形態１に係るセットアップ装置１０の構成を説明する。
セットアップ装置１０は、Ｓｅｔｕｐアルゴリズムを実行するコンピュータである。
セットアップ装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００３２】
セットアップ装置１０は、機能構成要素として、受付部１１１と、マスター鍵生成部１１２と、送信部１１３とを備える。セットアップ装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、セットアップ装置１０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、セットアップ装置１０の各機能構成要素の機能が実現される。
【００３３】
図３を参照して、実施の形態１に係る暗号化装置２０の構成を説明する。
暗号化装置２０は、Ｅｎｃアルゴリズムを実行するコンピュータである。
暗号化装置２０は、プロセッサ２１と、メモリ２２と、ストレージ２３と、通信インタフェース２４とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００３４】
暗号化装置２０は、機能構成要素として、マスター鍵取得部２１１と、ベクトル取得部２１２と、設定情報定義部２１３と、暗号化部２１４と、送信部２１５とを備える。暗号化装置２０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ２３には、暗号化装置２０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ２１によりメモリ２２に読み込まれ、プロセッサ２１によって実行される。これにより、暗号化装置２０の各機能構成要素の機能が実現される。
【００３５】
図４を参照して、実施の形態１に係る鍵生成装置３０の構成を説明する。
鍵生成装置３０は、ＫｅｙＧｅｎアルゴリズムを実行するコンピュータである。
鍵生成装置３０は、プロセッサ３１と、メモリ３２と、ストレージ３３と、通信インタフェース３４とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００３６】
鍵生成装置３０は、機能構成要素として、マスター鍵取得部３１１と、ベクトル取得部３１２と、設定情報定義部３１３と、鍵生成部３１４と、送信部３１５とを備える。鍵生成装置３０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ３３には、鍵生成装置３０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ３１によりメモリ３２に読み込まれ、プロセッサ３１によって実行される。これにより、鍵生成装置３０の各機能構成要素の機能が実現される。
【００３７】
図５を参照して、実施の形態１に係る復号装置４０の構成を説明する。
復号装置４０は、Ｄｅｃアルゴリズムを実行するコンピュータである。
復号装置４０は、プロセッサ４１と、メモリ４２と、ストレージ４３と、通信インタフェース４４とのハードウェアを備える。プロセッサ４１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００３８】
復号装置４０は、機能構成要素として、公開鍵取得部４１１と、暗号文取得部４１２と、復秘密鍵取得部４１３と、復号部４１４とを備える。復号装置４０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ４３には、復号装置４０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ４１によりメモリ４２に読み込まれ、プロセッサ４１によって実行される。これにより、復号装置４０の各機能構成要素の機能が実現される。
【００３９】
プロセッサ１１，２１，３１，４１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１，２１，３１，４１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００４０】
メモリ１２，２２，３２，４２は、データを一時的に記憶する記憶装置である。メモリ１２，２２，３２，４２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００４１】
ストレージ１３，２３，３３，４３は、データを保管する記憶装置である。ストレージ１３，２３，３３，４３は、具体例としては、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ１３，２３，３３，４３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ，登録商標）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）といった可搬記録媒体であってもよい。
【００４２】
通信インタフェース１４，２４，３４，４４は、外部の装置と通信するためのインタフェースである。通信インタフェース１４，２４，３４，４４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）のポートである。
【００４３】
図２では、プロセッサ１１は、１つだけ示されていた。しかし、プロセッサ１１は、複数であってもよく、複数のプロセッサ１１が、各機能を実現するプログラムを連携して実行してもよい。同様に、プロセッサ２１，３１，４１は、複数であってもよく、複数のプロセッサ２１，３１，４１が、各機能を実現するプログラムを連携して実行してもよい。
【００４４】
＊＊＊動作の説明＊＊＊
以下の説明では、ノルム上限Ｘλ，Ｙλは、ある多項式である。数１２２に示す関数族Ｆは、数１２３に示す関数ＦＫからなる鍵空間Ｋλについての疑似ランダム関数（以下、ＰＲＦ）族である。
【数１２２】
2019215391.tif 000024
【数１２３】
2019215391.tif 000025
【００４５】
図６を参照して、実施の形態１に係るセットアップ装置１０の動作を説明する。
実施の形態１に係るセットアップ装置１０の動作は、実施の形態１に係るセットアップ方法に相当する。また、実施の形態１に係るセットアップ装置１０の動作は、実施の形態１に係るセットアッププログラムの処理に相当する。
【００４６】
（ステップＳ１１：受付処理）
受付部１１１は、セキュリティパラメータ１λの入力を受け付ける。
具体的には、受付部１１１は、通信インタフェース１４を介して、セットアップ装置１０のユーザによって入力されたセキュリティパラメータ１λを受け付ける。受付部１１１は、セキュリティパラメータ１λをメモリ１２に書き込む。
【００４７】
（ステップＳ１２：マスター鍵生成処理）
マスター鍵生成部１１２は、ステップＳ１１で受け付けられたセキュリティパラメータ１λを入力として、双線形群Ｇを選択する。また、マスター鍵生成部１１２は、鍵空間ＫλからランダムにＰＲＦ鍵Ｋを選択する。
具体的には、マスター鍵生成部１１２は、メモリ１２からセキュリティパラメータ１λを読み出す。マスター鍵生成部１１２は、セキュリティパラメータ１λを入力として、双線形群の生成アルゴリズムＧＢＧを実行して、双線形群Ｇを選択する。また、マスター鍵生成部１１２は、セキュリティパラメータ１λによって定まる鍵空間ＫλからランダムにＰＲＦ鍵Ｋを選択する。マスター鍵生成部１１２は、双線形群Ｇ及びＰＲＦ鍵Ｋをメモリ１２に書き込む。
【００４８】
（ステップＳ１３：送信処理）
送信部１１３は、ステップＳ１２で選択された双線形群Ｇを公開パラメータｐｐとして、公開する。具体的には、送信部１１３は、メモリ１２から双線形群Ｇを読み出す。送信部１１３は、双線形群Ｇを公開パラメータｐｐとして公開用のサーバに送信するといった方法により、公開する。これにより、暗号化装置２０と鍵生成装置３０と復号装置４０とは、双線形群Ｇを取得可能になる。
また、送信部１１３は、ステップＳ１２で選択されたＰＲＦ鍵Ｋをマスター秘密鍵ｍｓｋとして、暗号化装置２０及び鍵生成装置３０に秘密裡に送信する。具体的には、送信部１１３は、メモリ１２からＰＲＦ鍵Ｋを読み出す。送信部１１３は、ＰＲＦ鍵Ｋをマスター秘密鍵ｍｓｋとして、既存の暗号化方式で暗号化した上で暗号化装置２０及び鍵生成装置３０に送信する。
【００４９】
つまり、セットアップ装置１０は、数１２４に示すＳｅｔｕｐアルゴリズムを実行する。
【数１２４】
2019215391.tif 000026
【００５０】
図７を参照して、実施の形態１に係る暗号化装置２０の動作を説明する。
実施の形態１に係る暗号化装置２０の動作は、実施の形態１に係る暗号化方法に相当する。また、実施の形態１に係る暗号化装置２０の動作は、実施の形態１に係る暗号化プログラムの処理に相当する。
【００５１】
（ステップＳ２１：マスター鍵取得処理）
マスター鍵取得部２１１は、セットアップ装置１０によって生成された公開パラメータｐｐである双線形群Ｇと、マスター秘密鍵ｍｓｋであるＰＲＦ鍵Ｋとを取得する。
具体的には、マスター鍵取得部２１１は、通信インタフェース２４を介して、公開された公開パラメータｐｐを取得するとともに、セットアップ装置１０によって送信されたマスター秘密鍵ｍｓｋを取得する。マスター鍵取得部２１１は、公開パラメータｐｐ及びマスター秘密鍵ｍｓｋをメモリ２２に書き込む。
【００５２】
（ステップＳ２２：ベクトル取得処理）
ベクトル取得部２１２は、数１２５に示すベクトルｘを取得する。ベクトルｘは、暗号化の対象である。ここで、ｍ：＝ｍ（λ）は、多項式である。
【数１２５】
2019215391.tif 000027
具体的には、ベクトル取得部２１２は、通信インタフェース２４を介して、暗号化装置２０のユーザによって入力されたベクトルｘを取得する。ベクトル取得部２１２は、ベクトルｘをメモリ２２に書き込む。
【００５３】
（ステップＳ２３：設定情報生成処理）
設定情報定義部２１３は、ステップＳ２１で取得された一定サイズの公開情報であるマスター秘密鍵ｍｓｋを入力として、ステップＳ２２で取得された暗号化する対象のベクトルｘのサイズに応じたサイズの暗号化設定情報を定義する。ここでは、設定情報定義部２１３は、一定サイズの公開情報に基づき、ベクトルｘのサイズに応じたデータサイズ拡張用の情報を暗号化して、データサイズ拡張用の情報が設定された暗号化設定情報を生成する。ここでのデータサイズ拡張用の情報は、インデックスｉである。したがって、設定情報定義部２１３は、インデックスｉを暗号化して、インデックスｉが設定された暗号化設定情報を生成する。
具体的には、設定情報定義部２１３は、メモリ２２からマスター秘密鍵ｍｓｋ及びベクトルｘを読み出す。設定情報定義部２１３は、ｉ＝１，．．．，ｍの各整数ｉについて、ＰＲＦである関数Ｆに、マスター秘密鍵ｍｓｋであるＰＲＦ鍵Ｋと、インデックスｉとを入力として、行列Ｂｉを暗号化設定情報として生成する。ｍは、ベクトルｘの要素数である。つまり、設定情報定義部２１３は、ｉ＝１，．．．，ｍの各整数ｉについて、Ｂｉ：＝ＦＫ（ｉ）を計算して、行列Ｂｉを暗号化設定情報として扱う。
なお、設定情報定義部２１３は、生成された行列Ｂｉが非正則行列である場合には、識別子⊥を出力して、処理を終了する。
【００５４】
（ステップＳ２４：暗号化処理）
暗号化部２１４は、ステップＳ２３で定義された暗号化設定情報を用いて、ベクトルｘを暗号化して暗号文ｃｔｘを生成する。
具体的には、暗号化部２１４は、ｉ＝１，．．．，ｍの各整数ｉについて、数１２６に示すように、要素ｃｉを計算する。つまり、暗号化部２１４は、インデックスｉが暗号化された暗号化設定情報を用いて、ベクトルｘを暗号化して要素ｃｉを計算する。
【数１２６】
2019215391.tif 000028
暗号化部２１４は、メモリ１２から公開パラメータｐｐである双線形群Ｇに含まれる群Ｇ１の群要素ｇ１を読み出す。暗号化部２１４は、ｉ＝１，．．．，ｍの各整数ｉについての各要素ｃｉを群要素ｇ１の指数部に設定した要素［ｃｉ］１を生成する。暗号化部２１４は、数１２７に示すように、ｉ＝１，．．．，ｍの各整数ｉについての要素［ｃｉ］１を暗号文ｃｔｘとしてメモリ２２に書き込む。
【数１２７】
2019215391.tif 000029
【００５５】
（ステップＳ２５：送信処理）
送信部２１５は、ステップＳ２４で生成された暗号文ｃｔｘを復号装置４０に送信する。具体的には、送信部２１５は、メモリ２２から暗号文ｃｔｘを読み出す。送信部２１５は、通信インタフェース２４を介して、暗号文ｃｔｘを復号装置４０に送信する。
【００５６】
つまり、暗号化装置２０は、数１２８に示すＥｎｃアルゴリズムを実行する。
【数１２８】
2019215391.tif 000030
【００５７】
図８を参照して、実施の形態１に係る鍵生成装置３０の動作を説明する。
実施の形態１に係る鍵生成装置３０の動作は、実施の形態１に係る鍵生成方法に相当する。また、実施の形態１に係る鍵生成装置３０の動作は、実施の形態１に係る鍵生成プログラムの処理に相当する。
【００５８】
（ステップＳ３１：マスター鍵取得処理）
マスター鍵取得部３１１は、セットアップ装置１０によって生成された公開パラメータｐｐである双線形群Ｇと、マスター秘密鍵ｍｓｋであるＰＲＦ鍵Ｋとを取得する。
具体的には、マスター鍵取得部３１１は、通信インタフェース３４を介して、公開された公開パラメータｐｐを取得するとともに、セットアップ装置１０によって送信されたマスター秘密鍵ｍｓｋを取得する。マスター鍵取得部３１１は、公開パラメータｐｐ及びマスター秘密鍵ｍｓｋをメモリ３２に書き込む。
【００５９】
（ステップＳ３２：ベクトル取得処理）
ベクトル取得部３１２は、集合Ｓ⊆［ｓ］と、インデックスが設定された数１２９に示すベクトルｙとを取得する。ここで、ｓ：＝ｓ（λ）は、多項式である。
【数１２９】
2019215391.tif 000031
具体的には、ベクトル取得部３１２は、通信インタフェース２４を介して、鍵生成装置３０のユーザによって入力された集合Ｓ及びベクトルｙを取得する。ベクトル取得部３１２は、集合Ｓ及びベクトルｙをメモリ３２に書き込む。
【００６０】
（ステップＳ３３：設定情報生成処理）
設定情報定義部３１３は、ステップＳ３１で取得された一定サイズの公開情報であるマスター秘密鍵ｍｓｋを入力として、ステップＳ３２で取得されたベクトルｙのサイズに応じたサイズの鍵設定情報を定義する。ここでは、設定情報定義部３１３は、一定サイズの公開情報に基づき、ベクトルｙのサイズに応じたデータサイズ拡張用の情報を暗号化して、データサイズ拡張用の情報が設定された鍵設定情報を生成する。ここでの、データサイズ拡張用の情報は、インデックスｉである。したがって、設定情報定義部３１３は、インデックスｉを暗号化して、インデックスｉが設定された鍵設定情報を生成する。
具体的には、設定情報定義部３１３は、メモリ３２からマスター秘密鍵ｍｓｋと、集合Ｓとを読み出す。設定情報定義部３１３は、ｉ∈Ｓの各整数ｉについて、ＰＲＦである関数Ｆに、マスター秘密鍵ｍｓｋであるＰＲＦ鍵Ｋと、インデックスｉとを入力として、行列Ｂｉを生成する。設定情報定義部３１３は、行列Ｂｉの随伴行列Ｂ＊ｉ：＝（Ｂｉ−１）Ｔを鍵設定情報として生成する。つまり、設定情報定義部３１３は、ｉ∈Ｓの各整数ｉについて、Ｂｉ：＝ＦＫ（ｉ）を計算して、行列Ｂｉの随伴行列Ｂ＊ｉを鍵設定情報として扱う。
なお、設定情報定義部３１３は、生成された行列Ｂｉが非正則行列である場合には、識別子⊥を出力して、処理を終了する。
【００６１】
（ステップＳ３４：鍵生成処理）
鍵生成部３１４は、ステップＳ３３で生成された鍵設定情報を用いて、ベクトルｙを設定した秘密鍵ｓｋｙを生成する。
具体的には、鍵生成部３１４は、ｉ∈Ｓの各整数ｉについて、数１３０に示すように、乱数ｒｉを生成する。
【数１３０】
2019215391.tif 000032
鍵生成部３１４は、ｉ∈Ｓの各整数ｉについて、乱数ｒｉを用いて、数１３１に示すように、要素ｋｉを生成する。つまり、鍵生成部３１４は、インデックスｉが暗号化された鍵設定情報を用いて、ベクトルｙを暗号化して要素ｋｉを計算する。
【数１３１】
2019215391.tif 000033
鍵生成部３１４は、メモリ１２から公開パラメータｐｐである双線形群Ｇに含まれる群Ｇ２の群要素ｇ２を読み出す。鍵生成部３１４は、ｉ∈Ｓの各整数ｉについて、各要素ｋｉを群要素ｇ２の指数部に設定した要素［ｋｉ］２を生成する。鍵生成部３１４は、数１３２に示すように、集合Ｓと、ｉ∈Ｓの各整数ｉについての要素［ｋｉ］２とを秘密鍵ｓｋｙとしてメモリ３２に書き込む。
【数１３２】
2019215391.tif 000034
【００６２】
（ステップＳ３５：送信処理）
送信部３１５は、ステップＳ３４で生成された秘密鍵ｓｋｙを復号装置４０に送信する。具体的には、送信部３１５は、メモリ３２から秘密鍵ｓｋｙを読み出す。送信部３１５は、通信インタフェース３４を介して、秘密鍵ｓｋｙを復号装置４０に送信する。
【００６３】
つまり、鍵生成装置３０は、数１３３に示すＫｅｙＧｅｎアルゴリズムを実行する。
【数１３３】
2019215391.tif 000035
【００６４】
図９を参照して、実施の形態１に係る復号装置４０の動作を説明する。
実施の形態１に係る復号装置４０の動作は、実施の形態１に係る復号方法に相当する。また、実施の形態１に係る復号装置４０の動作は、実施の形態１に係る復号プログラムの処理に相当する。
【００６５】
（ステップＳ４１：公開鍵取得処理）
公開鍵取得部４１１は、セットアップ装置１０によって生成された公開パラメータｐｐである双線形群Ｇを取得する。
具体的には、公開鍵取得部４１１は、通信インタフェース４４を介して、公開された公開パラメータｐｐを取得する。公開鍵取得部４１１は、公開パラメータｐｐをメモリ４２に書き込む。
【００６６】
（ステップＳ４２：暗号文取得処理）
暗号文取得部４１２は、暗号化装置２０によって生成された暗号文ｃｔｘを取得する。
具体的には、暗号文取得部４１２は、通信インタフェース４４を介して、暗号化装置２０によって送信された暗号文ｃｔｘを取得する。暗号文取得部４１２は、暗号文ｃｔｘをメモリ４２に書き込む。
【００６７】
（ステップＳ４３：秘密鍵取得処理）
秘密鍵取得部４１３は、鍵生成装置３０によって生成された秘密鍵ｓｋｙを取得する。
具体的には、秘密鍵取得部４１３は、通信インタフェース４４を介して、鍵生成装置３０によって送信された秘密鍵ｓｋｙを取得する。秘密鍵取得部４１３は、秘密鍵ｓｋｙをメモリ４２に書き込む。
【００６８】
（ステップＳ４４：判定処理）
復号部４１４は、Ｓ⊆［ｍ］であるか否かを判定することにより、復号可能か否かを判定する。
復号部４１４は、Ｓ⊆［ｍ］である場合には、処理をステップＳ４５に進める。一方、復号部４１４は、Ｓ⊆［ｍ］でない場合には、復号できないとして識別子⊥を出力して、処理を終了する。
【００６９】
（ステップＳ４５：復号処理）
復号部４１４は、ステップＳ４２で取得された暗号文ｃｔｘを、ステップＳ４３で取得された秘密鍵ｓｋｙで復号して、ベクトルｘとベクトルｙとの内積値を計算する。
具体的には、復号部４１４は、公開パラメータｐｐと暗号文ｃｔｘと秘密鍵ｓｋｙとをメモリ４２から読み出す。復号部４１４は、数１３４に示すように、暗号文ｃｔｘと秘密鍵ｓｋｙとについてのペアリング演算を計算することにより、値ｈを計算する。
【数１３４】
2019215391.tif 000036
復号部４１４は、−｜Ｓ｜ＸλＹλから｜Ｓ｜ＸλＹλまでの範囲からｅ（ｇ１，ｇ２）ｄ＝ｈであるような値ｄを探索する。ここで、｜Ｓ｜は、集合Ｓの要素数である。復号部４１４は、値ｄが見つかった場合には、値ｄを出力する。一方、復号部４１４は、値ｄが見つからない場合には、識別子⊥を出力する。
【００７０】
数１３５に示すように、値ｈは計算される。
【数１３５】
2019215391.tif 000037
したがって、ｅ（ｇ１，ｇ２）ｄ＝ｈであるような値ｄは、ベクトルｘとベクトルｙとの内積値になる。
【００７１】
つまり、復号装置４０は、数１３６に示すＤｅｃアルゴリズムを実行する。
【数１３６】
2019215391.tif 000038
【００７２】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る暗号システム１では、暗号文ｃｔｘは、一定のサイズの公開情報を入力として生成された暗号化設定情報であって、ベクトルｘのサイズに応じたサイズの暗号化設定情報を用いて、ベクトルｘが暗号化されて生成される。また、秘密鍵ｓｋｙは、一定のサイズの公開情報を入力として生成された鍵設定情報であって、ベクトルｙのサイズに応じたサイズの鍵設定情報を用いて、ベクトルｙが設定されて生成される。そして、暗号文ｃｔｘが秘密鍵ｓｋｙで復号されて、ベクトルｘとベクトルｙとの内積値が計算される。そのため、暗号文及び秘密鍵の最大の長さが限定されない、ＩＰＦＥ方式を構築可能にすることができる。
【００７３】
暗号化設定情報及び鍵設定情報は、公開情報を入力として、ＰＲＦにより生成される。これにより、一定のサイズの公開情報からランダムな暗号化設定情報及び鍵設定情報を生成することができる。
【００７４】
また、暗号文ｃｔｘの各要素［ｃｉ］１を構成する要素ｃｉに乱数ｚが含まれる。これにより、暗号文ｃｔｘの一部の要素を、別途生成された他の暗号文の要素と入れ替えるといったことができないようになっている。つまり、乱数ｚにより、暗号文ｃｔｘがバインドされている。
同様に、秘密鍵ｓｋｙの各要素［ｋｉ］２を構成する要素ｋｉに乱数ｒｉが含まれる。これにより、秘密鍵ｓｋｙの一部の要素を、別途生成された他の秘密鍵の要素と入れ替える、一部の要素を削除するといったことができないようになっている。つまり、乱数ｒｉにより、秘密鍵ｓｋｙがバインドされている。
【００７５】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、各機能構成要素がソフトウェアで実現された。しかし、変形例１として、各機能構成要素はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００７６】
図１０を参照して、変形例１に係るセットアップ装置１０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、セットアップ装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、電子回路１５を備える。電子回路１５は、各機能構成要素と、メモリ１２と、ストレージ１３との機能とを実現する専用の回路である。
【００７７】
図１１を参照して、変形例１に係る暗号化装置２０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、暗号化装置２０は、プロセッサ２１とメモリ２２とストレージ２３とに代えて、電子回路２５を備える。電子回路２５は、各機能構成要素と、メモリ２２と、ストレージ２３との機能とを実現する専用の回路である。
【００７８】
図１２を参照して、変形例１に係る鍵生成装置３０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、鍵生成装置３０は、プロセッサ３１とメモリ３２とストレージ３３とに代えて、電子回路３５を備える。電子回路３５は、各機能構成要素と、メモリ３２と、ストレージ３３との機能とを実現する専用の回路である。
【００７９】
図１３を参照して、変形例１に係る復号装置４０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、復号装置４０は、プロセッサ４１とメモリ４２とストレージ４３とに代えて、電子回路４５を備える。電子回路４５は、各機能構成要素と、メモリ４２と、ストレージ４３との機能とを実現する専用の回路である。
【００８０】
電子回路１５，２５，３５，４５としては、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
各機能構成要素を１つの電子回路１５，２５，３５，４５で実現してもよいし、各機能構成要素を複数の電子回路１５，２５，３５，４５に分散させて実現してもよい。
【００８１】
＜変形例２＞
変形例２として、一部の各機能構成要素がハードウェアで実現され、他の各機能構成要素がソフトウェアで実現されてもよい。
【００８２】
プロセッサ１１，２１，３１，４１とメモリ１２，２２，３２，４２とストレージ１３，２３，３３，４３と電子回路１５，２５，３５，４５とを処理回路という。つまり、各機能構成要素の機能は、処理回路により実現される。
【００８３】
実施の形態２．
実施の形態２では、Ｐｕｂｌｉｃ−ｋｅｙ  ＵＩＰＦＥについて説明する。実施の形態２では、実施の形態１と異なる点を説明し、同一の点については説明を省略する。
【００８４】
＊＊＊構成の説明＊＊＊
＜Ｐｕｂｌｉｃ−ｋｅｙ  ＵＩＰＦＥの構成＞
Ｐｕｂｌｉｃ−ｋｅｙ  ＵＩＰＦＥは、公開鍵セッティングのＵＩＰＦＥである。公開鍵セッティングは、暗号文の作成に公開鍵だけが必要であり、秘密鍵は必要ない方式である。
【００８５】
Ｐｕｂｌｉｃ−ｋｅｙ  ＵＩＰＦＥは、Ｓｅｔｕｐアルゴリズムと、Ｅｎｃアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｄｅｃアルゴリズムとを含む。Χ：＝｛Ｘλ｝λ∈Ｎ，Υ：＝｛Ｙλ｝λ∈Ｎをノルム上限の集合体とする。ここで、Ｎは、自然数の集合である。
【００８６】
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開鍵ｐｋと、マスター秘密鍵ｍｓｋとを出力する。
Ｅｎｃアルゴリズムは、公開鍵ｐｋと、ベクトルｘ：＝（ｘ１，．．．，ｘｍ）とを入力として、暗号文ｃｔｘを出力する。ここで、ｍ：＝ｍ（λ）は、多項式である。
ＫｅｙＧｅｎアルゴリズムは、公開鍵ｐｋと、マスター秘密鍵ｍｓｋと、空でない集合Ｓ：＝［ｓ］と、インデックス付けされたベクトルｙ：＝（ｙｉ）ｉ∈Ｓとを入力として、秘密鍵ｓｋｙを出力する。ここで、ｓ：＝ｓ（λ）は、多項式である。
Ｄｅｃアルゴリズムは、公開鍵ｐｋと、暗号文ｃｔｘと、秘密鍵ｓｋｙとを入力として、復号された値ｄ∈Ｚ、又は、識別子⊥を出力する。ここで、Ｚは、実数の集合である。識別子⊥は、復号できないことを示す。
【００８７】
＜暗号システム１の構成＞
図１４を参照して、実施の形態２に係る暗号システム１の構成を説明する。
暗号システム１は、セットアップ装置１０と、暗号化装置２０と、鍵生成装置３０と、復号装置４０とを備える。セットアップ装置１０と暗号化装置２０と鍵生成装置３０と復号装置４０とは、ネットワークを介して接続される。
暗号システム１は、セットアップ装置１０から暗号化装置２０にマスター秘密鍵ｍｓｋが送信されていない点が図１に示す暗号システム１と異なる。
【００８８】
＊＊＊動作の説明＊＊＊
以下の説明では、ノルム上限Ｘλ，Ｙλは、ある多項式である。
【００８９】
図６を参照して、実施の形態２に係るセットアップ装置１０の動作を説明する。
実施の形態２に係るセットアップ装置１０の動作は、実施の形態２に係るセットアップ方法に相当する。また、実施の形態２に係るセットアップ装置１０の動作は、実施の形態２に係るセットアッププログラムの処理に相当する。
【００９０】
ステップＳ１１の処理は、実施の形態１と同じである。
【００９１】
（ステップＳ１２：マスター鍵生成処理）
マスター鍵生成部１１２は、ステップＳ１１で受け付けられたセキュリティパラメータ１λを入力として、双線形群Ｇを選択する。また、マスター鍵生成部１１２は、７×７の正則行列Ｂを生成する。
具体的には、マスター鍵生成部１１２は、メモリ１２からセキュリティパラメータ１λを読み出す。マスター鍵生成部１１２は、セキュリティパラメータ１λを入力として、双線形群の生成アルゴリズムＧＢＧを実行して、双線形群Ｇを選択する。マスター鍵生成部１１２は、数１３７に示すように、ランダムに７×７の正則行列Ｂを生成する。マスター鍵生成部１１２は、正則行列Ｂの随伴行列Ｂ＊：＝（Ｂ−１）Ｔを生成する。マスター鍵生成部１１２は、双線形群Ｇと正則行列Ｂ及び随伴行列Ｂ＊とをメモリ１２に書き込む。
【数１３７】
2019215391.tif 000039
【００９２】
（ステップＳ１３：送信処理）
送信部１１３は、ステップＳ１２で選択された双線形群Ｇと、ｉ＝１，．．．，４の各整数ｉについての正則行列Ｂのｉ行目の要素を群要素ｇ１の指数部に設定した要素［ｂｉ］１とを公開鍵ｐｋとして、公開する。具体的には、送信部１１３は、メモリ１２から双線形群Ｇを読み出す。送信部１１３は、双線形群Ｇに含まれる要素ｇ１を用いて、ｉ＝１，．．．，４の各整数ｉについての正則行列Ｂのｉ行目の要素を群要素ｇ１の指数部に設定して、要素［ｂｉ］１を生成する。送信部１１３は、双線形群Ｇ及び要素［ｂ１］１，．．．，［ｂ４］１を公開鍵ｐｋとして公開用のサーバに送信するといった方法により、公開する。これにより、暗号化装置２０と鍵生成装置３０と復号装置４０とは、双線形群Ｇ及び要素［ｂ１］１，．．．，［ｂ４］１を取得可能になる。
また、送信部１１３は、ｉ＝１，．．．，４の各整数ｉについての随伴行列Ｂ＊のｉ行目の要素ｂ＊ｉをマスター秘密鍵ｍｓｋとして、鍵生成装置３０に秘密裡に送信する。具体的には、送信部１１３は、メモリ１２から随伴行列Ｂ＊を読み出す。送信部１１３は、ｉ＝１，．．．，４の各整数ｉについての随伴行列Ｂ＊のｉ行目の要素ｂ＊ｉをマスター秘密鍵ｍｓｋとして、既存の暗号化方式で暗号化した上で鍵生成装置３０に送信する。
【００９３】
つまり、セットアップ装置１０は、数１３８に示すＳｅｔｕｐアルゴリズムを実行する。
【数１３８】
2019215391.tif 000040
【００９４】
図７を参照して、実施の形態２に係る暗号化装置２０の動作を説明する。
実施の形態２に係る暗号化装置２０の動作は、実施の形態２に係る暗号化方法に相当する。また、実施の形態２に係る暗号化装置２０の動作は、実施の形態２に係る暗号化プログラムの処理に相当する。
【００９５】
ステップＳ２２及びステップＳ２５の処理は、実施の形態１と同じである。
【００９６】
（ステップＳ２１：マスター鍵取得処理）
マスター鍵取得部２１１は、セットアップ装置１０によって生成された公開鍵ｐｋである双線形群Ｇ及び要素［ｂ１］１，．．．，［ｂ４］１を取得する。
具体的には、マスター鍵取得部２１１は、通信インタフェース２４を介して、公開された公開鍵ｐｋを取得する。マスター鍵取得部２１１は、公開鍵ｐｋをメモリ２２に書き込む。
【００９７】
（ステップＳ２３：設定情報生成処理）
設定情報定義部２１３は、ステップＳ２１で取得された一定サイズの公開情報にベクトルｘの要素毎に生成されたインデックス情報Ｉを設定した情報を、ステップＳ２２で取得された暗号化する対象のベクトルｘのサイズに応じたサイズの暗号化設定情報として定義する。
具体的には、設定情報定義部２１３は、ｉ＝１，．．．，ｍの各整数ｉについて、数１３９に示すように、乱数πｉを生成する。
【数１３９】
2019215391.tif 000041
そして、設定情報定義部２１３は、ｉ＝１，．．．，ｍの各整数ｉについて、数１４０に示すように、インデックス情報Ｉである乱数πｉと乱数πｉに値ｉを乗じた値との組を設定した情報を、暗号化設定情報Ｂｉと定義する。
【数１４０】
2019215391.tif 000042
つまり、実施の形態１とは方法は異なるが、実施の形態１と同様に、設定情報定義部２１３は、インデックスｉを暗号化して、インデックスｉが設定された暗号化設定情報を定義する。
【００９８】
（ステップＳ２４：暗号化処理）
暗号化部２１４は、ステップＳ２３で定義された暗号化設定情報を用いて、ベクトルｘを暗号化して暗号文ｃｔｘを生成する。
具体的には、暗号化部２１４は、ｉ＝１，．．．，ｍの各整数ｉについて、数１４１に示すように、要素ｘｉ及び乱数ｚを設定した情報を、要素ｃｉと定義する。
【数１４１】
2019215391.tif 000043
つまり、要素ｃｉは、数１４２に示すように定義される。
【数１４２】
2019215391.tif 000044
暗号化部２１４は、メモリ１２から公開パラメータｐｐである双線形群Ｇに含まれる群Ｇ１の群要素ｇ１を読み出す。暗号化部２１４は、ｉ＝１，．．．，ｍの各整数ｉについての各要素ｃｉを群要素ｇ１の指数部に設定した要素［ｃｉ］１を生成する。暗号化部２１４は、数１４３に示すように、ｉ＝１，．．．，ｍの各整数ｉについての要素［ｃｉ］１を暗号文ｃｔｘとしてメモリ２２に書き込む。
【数１４３】
2019215391.tif 000045
【００９９】
つまり、暗号化装置２０は、数１４４に示すＥｎｃアルゴリズムを実行する。
【数１４４】
2019215391.tif 000046
【０１００】
図８を参照して、実施の形態２に係る鍵生成装置３０の動作を説明する。
実施の形態２に係る鍵生成装置３０の動作は、実施の形態２に係る鍵生成方法に相当する。また、実施の形態２に係る鍵生成装置３０の動作は、実施の形態２に係る鍵生成プログラムの処理に相当する。
【０１０１】
ステップＳ３２及びステップＳ３５の処理は、実施の形態１と同じである。
【０１０２】
（ステップＳ３１：マスター鍵取得処理）
マスター鍵取得部３１１は、セットアップ装置１０によって生成された公開鍵ｐｋである双線形群Ｇ及び要素［ｂ１］１，．．．，［ｂ４］１と、マスター秘密鍵ｍｓｋである要素ｂ＊１，．．．，ｂ＊４とを取得する。
具体的には、マスター鍵取得部３１１は、通信インタフェース３４を介して、公開された公開鍵ｐｋを取得するとともに、セットアップ装置１０によって送信されたマスター秘密鍵ｍｓｋを取得する。マスター鍵取得部３１１は、公開鍵ｐｋ及びマスター秘密鍵ｍｓｋをメモリ３２に書き込む。
【０１０３】
（ステップＳ３３：設定情報生成処理）
設定情報定義部３１３は、ステップＳ３１で取得された一定サイズの秘密情報であるマスター秘密鍵ｍｓｋである要素ｂ＊１，．．．，ｂ＊４を入力として、ステップＳ３２で取得されたベクトルｙのサイズに応じたサイズの鍵設定情報を定義する。
具体的には、設定情報定義部３１３は、設定情報定義部３１３は、メモリ３２からマスター秘密鍵ｍｓｋと、集合Ｓとを読み出す。設定情報定義部３１３は、ｉ∈Ｓの各整数ｉについて、数１４５に示すように、乱数ρｉを生成する。
【数１４５】
2019215391.tif 000047
そして、設定情報定義部３１３は、ｉ∈Ｓの各整数ｉについて、数１４６に示すように、インデックス情報Ｉ’である乱数ρｉに値−ｉを乗じた値と乱数ρｉとの組を設定した情報を、鍵設定情報Ｂ＊ｉと生成する。
【数１４６】
2019215391.tif 000048
つまり、実施の形態１とは方法は異なるが、実施の形態１と同様に、設定情報定義部３１３は、インデックスｉを暗号化して、インデックスｉが設定された鍵設定情報を生成する。
【０１０４】
（ステップＳ３４：鍵生成処理）
鍵生成部３１４は、ステップＳ３３で定義された鍵設定情報を用いて、ベクトルｙを設定した秘密鍵ｓｋｙを生成する。
具体的には、鍵生成部３１４は、ｉ∈Ｓの各整数ｉについて、数１４７に示すように、乱数ｒｉを生成する。
【数１４７】
2019215391.tif 000049
鍵生成部３１４は、ｉ∈Ｓの各整数ｉについて、乱数ｒｉを用いて、数１４８に示すように、要素ｋｉを生成する。
【数１４８】
2019215391.tif 000050
つまり、要素ｋｉは、数１４９に示すようになる。
【数１４９】
2019215391.tif 000051
鍵生成部３１４は、メモリ１２から公開パラメータｐｐである双線形群Ｇに含まれる群Ｇ２の群要素ｇ２を読み出す。鍵生成部３１４は、ｉ∈Ｓの各整数ｉについて、各要素ｋｉを群要素ｇ２の指数部に設定した要素［ｋｉ］２を生成する。鍵生成部３１４は、数１５０に示すように、集合Ｓと、ｉ∈Ｓの各整数ｉについての要素［ｋｉ］２とを秘密鍵ｓｋｙとしてメモリ３２に書き込む。
【数１５０】
2019215391.tif 000052
【０１０５】
つまり、鍵生成装置３０は、数１５１に示すＫｅｙＧｅｎアルゴリズムを実行する。
【数１５１】
2019215391.tif 000053
【０１０６】
実施の形態２に係る復号装置４０の動作は、実施の形態１に係る復号装置４０の動作と同じである。
【０１０７】
＊＊＊実施の形態２の効果＊＊＊
以上のように、実施の形態２に係る暗号システム１では、実施の形態１と同様に、暗号文及び秘密鍵の最大の長さが限定されない、ＩＰＦＥ方式を構築可能にすることができる。
【０１０８】
暗号化設定情報及び鍵設定情報は、公開情報を入力として、インデックス情報Ｉ，Ｉ’を用いて生成される。これにより、一定のサイズの公開情報からランダムな暗号化設定情報及び鍵設定情報を生成することができる。
【０１０９】
＊＊＊他の構成＊＊＊
＜変形例３＞
実施の形態２では、インデックス情報Ｉは、乱数πｉと乱数πｉに値ｉを乗じた値との組であり、インデックス情報Ｉ’は、乱数ρｉに値−ｉを乗じた値と乱数ρｉとの組であった。インデックス情報Ｉ及びインデックス情報Ｉ’は、内積値が０になる値であれば、これに限定されない。
【０１１０】
実施の形態３．
実施の形態１，２では、（Ｅ：ｃｏｎ，Ｋ：ｓｅｐ，Ｄ：ｃｔ−ｄｏｍ）セッティングについて説明した。実施の形態３では、他のセッティングについて説明する。実施の形態３では、実施の形態１，２と異なる点を説明し、同一の点については説明を省略する。
【０１１１】
他のセッティングとしては、以下のセッティング１からセッティング７の７個が考えられる。
【０１１２】
セッティング１：（Ｅ：ｃｏｎ，Ｋ：ｃｏｎ，Ｄ：ｃｔ−ｄｏｍ）セッティング
長さｍのベクトルの暗号文と、長さｎのベクトルの秘密鍵とに対して、ｎ≦ｍの場合に限り、暗号文を秘密鍵で復号でき、［ｎ］に関する内積値が得られる方式である。
【０１１３】
セッティング２：（Ｅ：ｓｅｐ，Ｋ：ｓｅｐ，Ｄ：ｃｔ−ｄｏｍ）セッティング
集合Ｕが付加された暗号文と、集合Ｓが付加された秘密鍵とに対して、Ｓ⊆Ｕの場合に限り、暗号文を秘密鍵で復号でき、集合Ｓに関する内積値が得られる方式である。
【０１１４】
セッティング３：（Ｅ：ｃｏｎ，Ｋ：ｃｏｎ，Ｄ：ｓｋ−ｄｏｍ）セッティング
長さｍのベクトルの暗号文と、長さｎのベクトルの秘密鍵とに対して、ｍ≦ｎの場合に限り、暗号文を秘密鍵で復号でき、［ｍ］に関する内積値が得られる方式である。
【０１１５】
セッティング４：（Ｅ：ｓｅｐ，Ｋ：ｃｏｎ，Ｄ：ｓｋ−ｄｏｍ）セッティング
集合Ｕが付加された暗号文と、長さｎのベクトルの秘密鍵とに対して、Ｕ⊆［ｎ］の場合に限り、暗号文を秘密鍵で復号でき、集合Ｕに関する内積値が得られる方式である。
【０１１６】
セッティング５：（Ｅ：ｓｅｐ，Ｋ：ｓｅｐ，Ｄ：ｓｋ−ｄｏｍ）セッティング
集合Ｕが付加された暗号文と、集合Ｓが付加された秘密鍵とに対して、Ｕ⊆Ｓの場合に限り、暗号文を秘密鍵で復号でき、集合Ｕに関する内積値が得られる方式である。
【０１１７】
セッティング６：（Ｅ：ｃｏｎ，Ｋ：ｃｏｎ，Ｄ：ｅｑ）セッティング
長さｍのベクトルの暗号文と、長さｍのベクトルの秘密鍵とに対して、［ｍ］に関する内積値が得られる方式である。
【０１１８】
セッティング７：（Ｅ：ｓｅｐ，Ｋ：ｓｅｐ，Ｄ：ｅｑ）セッティング
集合Ｓが付加された暗号文と、集合Ｓが付加された秘密鍵とに対して、集合Ｓに関する内積値が得られる方式である。
【０１１９】
各セッティングにおける動作の違いを説明する。
Ｅ：ｘｘ，Ｋ：ｙｙ，Ｄ：ｚｚの違いは、暗号文を秘密鍵で復号できる条件に影響する。具体的には、図９のステップＳ４４での判定内容に影響する。
実施の形態１，２では、Ｅ：ｃｏｎ，Ｋ：ｓｅｐ，Ｄ：ｃｔ−ｄｏｍであったため、Ｓ⊆［ｍ］の場合に限り、暗号文を秘密鍵で復号できた。そのため、図９のステップＳ４４でＳ⊆［ｍ］であるか否かが判定された。他のセッティングの場合には、図９のステップＳ４４でそのセッティングに応じた判定がされる。判定内容は、各セッティングで説明した通りである。
なお、Ｄ：ｅｑの場合には、暗号文及び秘密鍵のベクトルの長さが同じである、あるいは、暗号文及び秘密鍵に付加された集合が同じであることが前提である。そのため、図９のステップＳ４４は不要である。又は、図９のステップＳ４４で、暗号文及び秘密鍵のベクトルの長さが同じであること、あるいは、暗号文及び秘密鍵に付加された集合が同じであることの判定が行われてもよい。
【０１２０】
また、Ｄ：ｚｚの違いは、暗号文ｃｔｘの要素ｃｉと、秘密鍵ｓｋｙの要素ｋｉとの乱数の設定方法に影響する。具体的には、図７のステップＳ２４で設定された乱数ｚと、図８のステップＳ３４で設定された乱数ｒｉとの設定方法に影響する。
実施の形態１，２では、Ｄ：ｃｔ−ｄｏｍであったため、秘密鍵ｓｋｙの要素ｋｉに乱数ｒｉが設定された。一方、要素ｋｉにおける乱数ｒｉが設定された要素に対応する、要素ｃｉにおける要素には乱数ｚが設定された。これにより、秘密鍵ｓｋｙがバインドされるとともに、暗号文ｃｔｘがバインドされた。ここで、乱数ｒｉは、秘密鍵ｓｋｙの集合Ｓに含まれる各整数ｉについて、乱数ｒｉの和が０になるように生成された。つまり、全ての要素ｋｉについての乱数ｒｉの和が０になるように乱数ｒｉは生成された。
他のセッティングの場合には、Ｄ：ｚｚに応じて、乱数ｒｉと乱数ｚとが、要素ｃｉと要素ｋｉとのどちらに設定されるかが変更される。具体的には、Ｄ：ｃｔ−ｄｏｍの場合には、上述した通り、要素ｋｉに乱数ｒｉ設定され、要素ｃｉに乱数ｚが設定される。この場合には、全ての要素ｋｉについての乱数ｒｉの和が０になるように乱数ｒｉは生成される。Ｄ：ｓｋ−ｄｏｍの場合には、要素ｃｉに乱数ｒｉが設定され、要素ｋｉに乱数ｚが設定される。この場合には、全ての要素ｃｉについての乱数ｒｉの和が０になるように乱数ｒｉは生成される。Ｄ：ｅｑの場合には、要素ｋｉに乱数ｒｉが設定され、要素ｃｉに乱数ｚが設定されるとともに、要素ｃｉに乱数ｒ’ｉが設定され、要素ｋｉに乱数ｚ’が設定される。この場合には、全ての要素ｋｉについての乱数ｒｉの和が０になるように乱数ｒｉは生成され、全ての要素ｃｉについての乱数ｒ’ｉの和が０になるように乱数ｒ’ｉは生成される。なお、乱数ｒ’ｉは、乱数ｒｉとは異なる乱数であるが、乱数ｒｉと同様の役割を果たす乱数である。乱数ｚ’は、乱数ｚとは異なる乱数であるが、乱数ｚと同様の役割を果たす乱数である。
【０１２１】
以上のように、実施の形態３に係る暗号システム１では、実施の形態１，２で説明したセッティングとは異なるセッティングについても、暗号文及び秘密鍵の最大の長さが限定されない、ＩＰＦＥ方式を構築可能にすることができる。
【０１２２】
実施の形態４．
実施の形態４では、実施の形態１で説明したＰｒｉｖａｔｅ−ｋｅｙ  ＵＩＰＦＥの処理を効率的に実現可能な方式を説明する。実施の形態４では、実施の形態１と異なる点を説明し、同一の点については説明を省略する。
【０１２３】
実施の形態４では、（Ｅ：ｃｏｎ，Ｋ：ｃｏｎ，Ｄ：ｅｑ）セッティングについて説明する。つまり、実施の形態４では、実施の形態３で説明したセッティング６について説明する。
【０１２４】
以下の説明では、数１５２に示すｂｉｎａｒｙλは、入力をバイナリー形式に変換し、変換されたデータに０を付加してλビットにする関数である。
【数１５２】
2019215391.tif 000054
【０１２５】
セットアップ装置１０の動作は、実施の形態１と同じである。
【０１２６】
暗号化装置２０は、数１５３に示すＥｎｃアルゴリズムを実行する。
【数１５３】
2019215391.tif 000055
【０１２７】
鍵生成装置３０は、数１５４に示すＫｅｙＧｅｎアルゴリズムを実行する。
【数１５４】
2019215391.tif 000056
【０１２８】
復号装置４０は、数１５５に示すＤｅｃアルゴリズムを実行する。
【数１５５】
2019215391.tif 000057
【０１２９】
ここでは、（Ｅ：ｃｏｎ，Ｋ：ｃｏｎ，Ｄ：ｅｑ）セッティングについて説明した。しかし、他のセッティングについても同様の考えに基づき実現可能である。Ｅ：ｓｅｐ及びＫ：ｓｅｐの場合には、ＥｎｃアルゴリズムにおけるＢｍに代えて、集合Ｓ毎にＢＵを生成し、ＫｅｙＧｅｎアルゴリズムにおけるＢｎに代えて、集合Ｕ毎にＢＳを生成すればよい。
【符号の説明】
【０１３０】
１  暗号システム、１０  セットアップ装置、１１  プロセッサ、１２  メモリ、１３  ストレージ、１４  通信インタフェース、１５  電子回路、１１１  受付部、１１２  マスター鍵生成部、１１３  送信部、２０  暗号化装置、２１  プロセッサ、２２  メモリ、２３  ストレージ、２４  通信インタフェース、２５  電子回路、２１１  マスター鍵取得部、２１２  ベクトル取得部、２１３  設定情報定義部、２１４  暗号化部、２１５  送信部、３０  鍵生成装置、３１  プロセッサ、３２  メモリ、３３  ストレージ、３４  通信インタフェース、３５  電子回路、３１１  マスター鍵取得部、３１２  ベクトル取得部、３１３  設定情報定義部、３１４  鍵生成部、３１５  送信部、４０  復号装置、４１  プロセッサ、４２  メモリ、４３  ストレージ、４４  通信インタフェース、４５  電子回路、４１１  公開鍵取得部、４１２  暗号文取得部、４１３  秘密鍵取得部、４１４  復号部。
【図１】
2019215391.tif 000064
【図２】
2019215391.tif 000065
【図３】
2019215391.tif 000066
【図４】
2019215391.tif 000067
【図５】
2019215391.tif 000068
【図６】
2019215391.tif 000069
【図７】
2019215391.tif 000070
【図８】
2019215391.tif 000071
【図９】
2019215391.tif 000072
【図１０】
2019215391.tif 000073
【図１１】
2019215391.tif 000074
【図１２】
2019215391.tif 000075
【図１３】
2019215391.tif 000076
【図１４】
2019215391.tif 000077
【手続補正書】
【提出日】平成31年1月30日(2019.1.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
Ｐｒｉｖａｔｅ−ｋｅｙ  ＵＩＰＦＥは、Ｓｅｔｕｐアルゴリズムと、Ｅｎｃアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｄｅｃアルゴリズムとを含む。Χ：＝｛Ｘλ｝λ∈Ｎ，Υ：＝｛Ｙλ｝λ∈Ｎをノルム上限の集合体とする。ここで、Ｎは、自然数の集合である。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｐと、マスター秘密鍵ｍｓｋとを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｐと、マスター秘密鍵ｍｓｋと、ベクトルｘ：＝（ｘ１，．．．，ｘｍ）とを入力として、暗号文ｃｔｘを出力する。ここで、ｍ：＝ｍ（λ）は、多項式である。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｐと、マスター秘密鍵ｍｓｋと、空でない集合Ｓ：＝［ｓ］と、インデックス付けされたベクトルｙ：＝（ｙｉ）ｉ∈Ｓとを入力として、秘密鍵ｓｋｙを出力する。ここで、ｓ：＝ｓ（λ）は、多項式である。
Ｄｅｃアルゴリズムは、公開パラメータｐｐと、暗号文ｃｔｘと、秘密鍵ｓｋｙとを入力として、復号された値ｄ∈Ｚ、又は、識別子⊥を出力する。ここで、Ｚは、整数の集合である。識別子⊥は、復号できないことを示す。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開鍵ｐｋと、マスター秘密鍵ｍｓｋとを出力する。
Ｅｎｃアルゴリズムは、公開鍵ｐｋと、ベクトルｘ：＝（ｘ１，．．．，ｘｍ）とを入力として、暗号文ｃｔｘを出力する。ここで、ｍ：＝ｍ（λ）は、多項式である。
ＫｅｙＧｅｎアルゴリズムは、公開鍵ｐｋと、マスター秘密鍵ｍｓｋと、空でない集合Ｓ：＝［ｓ］と、インデックス付けされたベクトルｙ：＝（ｙｉ）ｉ∈Ｓとを入力として、秘密鍵ｓｋｙを出力する。ここで、ｓ：＝ｓ（λ）は、多項式である。
Ｄｅｃアルゴリズムは、公開鍵ｐｋと、暗号文ｃｔｘと、秘密鍵ｓｋｙとを入力として、復号された値ｄ∈Ｚ、又は、識別子⊥を出力する。ここで、Ｚは、整数の集合である。識別子⊥は、復号できないことを示す。