(57)【要約】      （修正有）【課題】関数秘匿内積関数型暗号を用いて関数秘匿多入力内積関数型暗号を提供する。【解決手段】関数秘匿性を有する多入力内積関数型暗号により暗号化及び復号を行う暗号システム１は、ベクトル長と内積関数の引数の数μとを入力し、単入力内積関数型暗号と共通鍵暗号のアルゴリズムを用いて、マスター秘密鍵と公開パラメータとを生成するセットアップ装置と、マスター秘密鍵と、公開パラメータと、引数のインデックスと、ベクトルとを入力し、単入力内積関数型暗号と共通鍵暗号のアルゴリズムを用いて、暗号文を生成する暗号化装置と、マスター秘密鍵と、公開パラメータと、μ個のベクトルとを入力し、単入力内積関数型暗号と共通鍵暗号のアルゴリズムを用いて、秘密鍵を生成する鍵生成装置と、公開パラメータと、暗号文と、秘密鍵とを入力し、単入力内積関数型暗号と共通鍵暗号のアルゴリズムを用いて、暗号文を復号する復号装置と、を有する。【選択図】図１
2020086292.tif 000002
【特許請求の範囲】
【請求項１】
関数秘匿性を有する多入力内積関数型暗号により暗号化及び復号を行う暗号システムであって、
ベクトル長mと前記内積関数の引数の数μとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号のセットアップアルゴリズムと、所定の条件を満たす共通鍵暗号の鍵生成アルゴリズムとを用いて、マスター秘密鍵mskと公開パラメータppとを生成するセットアップ手段と、
前記マスター秘密鍵mskと、前記公開パラメータppと、前記引数のインデックスiと、ベクトルｘとを入力として、前記単入力内積関数型暗号の暗号化アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記インデックスiに対応する暗号文ctiを生成する暗号化手段と、
前記マスター秘密鍵mskと、前記公開パラメータppと、μ個のベクトルy1,・・・,yμとを入力として、前記単入力内積関数型暗号の鍵生成アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記暗号文ctiを復号するための秘密鍵skを生成する秘密鍵生成手段と、
前記公開パラメータppと、前記暗号文ct1,・・・,ctμと、前記秘密鍵skとを入力として、前記単入力内積関数型暗号の復号アルゴリズムと、前記共通鍵暗号の復号アルゴリズムとを用いて、前記暗号文ct1,・・・,ctμの復号値dを生成する復号手段と、
を有することを特徴とする暗号システム。
【請求項２】
前記所定の性質は、剰余環Zn上での内積計算が可能であることであり、
前記所定の条件は、選択的平文攻撃のもとでの識別不可能性を満たすことである、ことを特徴とする請求項１に記載の暗号システム。
【請求項３】
関数秘匿性を有する多入力内積関数型暗号により暗号化を行う暗号化装置であって、
ベクトル長mと前記内積関数の引数の数μとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号のセットアップアルゴリズムと、所定の条件を満たす共通鍵暗号の鍵生成アルゴリズムとを用いて、マスター秘密鍵mskと公開パラメータppとを生成するセットアップ手段と、
前記マスター秘密鍵mskと、前記公開パラメータppと、前記引数のインデックスiと、ベクトルｘとを入力として、前記単入力内積関数型暗号の暗号化アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記インデックスiに対応する暗号文ctiを生成する暗号化手段と、
を有することを特徴とする暗号化装置。
【請求項４】
関数秘匿性を有する多入力内積関数型暗号により暗号化された暗号文ct1,・・・,ctμの復号を行う復号装置であって、
公開パラメータppと、前記暗号文ct1,・・・,ctμと、所定の秘密鍵skとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号の復号アルゴリズムと、所定の条件を満たす共通鍵暗号の復号アルゴリズムとを用いて、前記暗号文ct1,・・・,ctμの復号値dを生成する復号手段を有することを特徴とする復号装置。
【請求項５】
関数秘匿性を有する多入力内積関数型暗号により暗号化及び復号を行う暗号システムが、
ベクトル長mと前記内積関数の引数の数μとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号のセットアップアルゴリズムと、所定の条件を満たす共通鍵暗号の鍵生成アルゴリズムとを用いて、マスター秘密鍵mskと公開パラメータppとを生成するセットアップ手順と、
前記マスター秘密鍵mskと、前記公開パラメータppと、前記引数のインデックスiと、ベクトルｘとを入力として、前記単入力内積関数型暗号の暗号化アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記インデックスiに対応する暗号文ctiを生成する暗号化手順と、
前記マスター秘密鍵mskと、前記公開パラメータppと、μ個のベクトルy1,・・・,yμとを入力として、前記単入力内積関数型暗号の鍵生成アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記暗号文ctiを復号するための秘密鍵skを生成する秘密鍵生成手順と、
前記公開パラメータppと、前記暗号文ct1,・・・,ctμと、前記秘密鍵skとを入力として、前記単入力内積関数型暗号の復号アルゴリズムと、前記共通鍵暗号の復号アルゴリズムとを用いて、前記暗号文ct1,・・・,ctμの復号値dを生成する復号手順と、
を実行することを特徴とする暗号方法。
【請求項６】
関数秘匿性を有する多入力内積関数型暗号により暗号化を行う暗号化装置が、
ベクトル長mと前記内積関数の引数の数μとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号のセットアップアルゴリズムと、所定の条件を満たす共通鍵暗号の鍵生成アルゴリズムとを用いて、マスター秘密鍵mskと公開パラメータppとを生成するセットアップ手順と、
前記マスター秘密鍵mskと、前記公開パラメータppと、前記引数のインデックスiと、ベクトルｘとを入力として、前記単入力内積関数型暗号の暗号化アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記インデックスiに対応する暗号文ctiを生成する暗号化手順と、
を実行することを特徴とする暗号化方法。
【請求項７】
関数秘匿性を有する多入力内積関数型暗号により暗号化された暗号文ct1,・・・,ctμの復号を行う復号装置が、
公開パラメータppと、前記暗号文ct1,・・・,ctμと、所定の秘密鍵skとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号の復号アルゴリズムと、所定の条件を満たす共通鍵暗号の復号アルゴリズムとを用いて、前記暗号文ct1,・・・,ctμの復号値dを生成する復号手順を実行することを特徴とする復号方法。
【請求項８】
コンピュータを、請求項３に記載の暗号化装置における各手段又は請求項４に記載の復号装置における各手段のいずれかとして機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号システム、暗号化装置、復号装置、暗号方法、暗号化方法、復号方法及びプログラムに関する。
【背景技術】
【０００２】
単入力関数型暗号（以降、単に「関数型暗号」とも表す。）では、暗号文を復号するための鍵（つまり、復号鍵）に関数fを埋め込むことができる。関数fを埋め込んだ復号鍵を用いてxの暗号文を復号すると、関数値f(x)が復号される。
【０００３】
多入力関数型暗号は、単入力関数型暗号を拡張したものであり、1つの引数をもつ関数だけでなく、2以上の引数をもつ関数をも復号鍵に埋め込むことができる方式である。つまり、引数1,・・・,nにそれぞれ対応する値x1,・・・,xnの暗号文ct1,・・・,ctnがあるとき、引数1,・・・,nをとる関数fを埋め込んだ秘密鍵skfを用いて暗号文ct1,・・・,ctnを復号すると、関数値f(x1,・・・,xn)が復号される。ただし、関数fがとる引数のうち、どれか1つでもその引数に対応する暗号文が存在しない場合は復号することができない。
【０００４】
内積関数型暗号は、扱える関数fを内積に限定した関数型暗号であり、多入力内積関数型暗号では、復号鍵にn個のベクトルy1,・・・,ynが埋め込まれていて、n個のベクトルx1,・・・,xnをそれぞれ暗号化したn個の暗号文ct1,・・・,ctnを復号鍵で復号すると、関数値
【０００５】
【数１】
2020086292.tif 000003
が復号されるというものである。ここで、<・,・>は内積を表す。
【０００６】
また、関数型暗号に対して関数秘匿性という性質がある。関数秘匿性とは、関数を埋め込んだ復号鍵が、その関数を秘匿しているという性質である（ただし、内積関数型暗号の場合はベクトルが関数に相当する。）。すなわち、或る関数を埋め込んだ復号鍵の所持者であっても、その埋め込まれた関数がどのような関数であるかを知ることができないという性質である。
【０００７】
従来、関数秘匿性を有する多入力内積関数型暗号（以降、「関数秘匿多入力内積関数型暗号」とも表す。）を具体的に構成する方法が知られている（非特許文献１及び２）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M. Abdalla, D. Catalano, D. Fiore, R. Gay, and B. Ursu. Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings. Cryptology ePrint Archive, Report 2017/972, 2017. http://eprint.iacr.org/2017/972.
【非特許文献２】P. Datta, T. Okamoto, and J. Tomida. Full-hiding (unbounded) multi-input inner product functional encryption from the k-linear assumption. In M. Abdalla and R. Da-hab, editors, PKC 2018, Part II, volume 10770 of LNCS, pages 245-277. Springer, Heidelberg, Mar. 2018.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、一般的に、多入力関数型暗号を構成することは、単入力関数型暗号を構成することに比べて難しい場合が多い。したがって、例えば、より効率的な関数秘匿多入力内積関数型暗号を構成しようとする場合、その設計や安全性分析に多大な労力が必要なると考えられる。
【００１０】
本発明は、上記の点に鑑みてなされたもので、関数秘匿内積関数型暗号を用いて関数秘匿多入力内積関数型暗号を実現することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の実施の形態における暗号システムは、関数秘匿性を有する多入力内積関数型暗号により暗号化及び復号を行う暗号システムであって、ベクトル長mと前記内積関数の引数の数μとを入力として、所定の性質を有し、かつ、関数秘匿性を有する単入力内積関数型暗号のセットアップアルゴリズムと、所定の条件を満たす共通鍵暗号の鍵生成アルゴリズムとを用いて、マスター秘密鍵mskと公開パラメータppとを生成するセットアップ手段と、前記マスター秘密鍵mskと、前記公開パラメータppと、前記引数のインデックスiと、ベクトルｘとを入力として、前記単入力内積関数型暗号の暗号化アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記インデックスiに対応する暗号文ctiを生成する暗号化手段と、前記マスター秘密鍵mskと、前記公開パラメータppと、μ個のベクトルy1,・・・,yμとを入力として、前記単入力内積関数型暗号の鍵生成アルゴリズムと、前記共通鍵暗号の暗号化アルゴリズムとを用いて、前記暗号文ctiを復号するための秘密鍵skを生成する秘密鍵生成手段と、前記公開パラメータppと、前記暗号文ct1,・・・,ctμと、前記秘密鍵skとを入力として、前記単入力内積関数型暗号の復号アルゴリズムと、前記共通鍵暗号の復号アルゴリズムとを用いて、前記暗号文ct1,・・・,ctμの復号値dを生成する復号手段と、を有することを特徴とする。
【発明の効果】
【００１２】
関数秘匿内積関数型暗号を用いて関数秘匿多入力内積関数型暗号を実現することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態における暗号システムの全体構成の一例を示す図である。
【図２】本発明の実施の形態におけるセットアップ装置が実行する処理の一例を示すフローチャートである。
【図３】本発明の実施の形態における暗号化装置が実行する処理の一例を示すフローチャートである。
【図４】本発明の実施の形態における鍵生成装置が実行する処理の一例を示すフローチャートである。
【図５】本発明の実施の形態における復号装置が実行する処理の一例を示すフローチャートである。
【図６】コンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、関数秘匿内積関数型暗号（すなわち、関数秘匿性を有する単入力内積関数型暗号）を用いて関数秘匿多入力内積関数型暗号を実現する暗号システム１について説明する。言い換えれば、本発明の実施の形態における暗号システム１は、関数秘匿内積関数型暗号から関数秘匿多入力内積関数型暗号へ汎用的に変換する。これにより、本発明の実施の形態では、関数秘匿多入力内積関数型暗号を設計するためには、（所定の性質を有する）関数秘匿内積関数型暗号さえ設計できればよくなり、関数秘匿多入力内積関数型暗号の設計に要する労力を大幅に削減することができるようになる。
【００１５】
＜記法＞
まず、本明細書で用いる記法について説明する。
【００１６】
・変数aをbと定義するという操作をa:=bと表記する。
【００１７】
・ベクトルは列ベクトルとして扱う。
【００１８】
・集合Sから要素sをランダムに選ぶことを
【００１９】
【数２】
2020086292.tif 000004
と表記する。
【００２０】
・ビット列bに対して、bのビット長を|b|と表記する。
【００２１】
・自然数nに対して剰余環Z/nZをZnと表記する。
【００２２】
・自然数nに対してn以下の自然数の集合を[n]と表記する。
【００２３】
・自然数nに対してnビットの全てのビット列で構成される集合を{0,1}nと表記する。
【００２４】
・双線型写像e:G1×G2→GTをもつ素数位数pの双線型群G1,G2,GTとその生成元g1,g2,gTとを考える。このとき、i∈{1,2,T}及びZp上のJ×L行列
【００２５】
【数３】
2020086292.tif 000005
に対して、[M]iを
【００２６】
【数４】
2020086292.tif 000006
で定義される群要素を各要素とするJ×L行列とする。
【００２７】
＜関数秘匿多入力内積関数型暗号への変換に用いる従来技術＞
本発明の実施の形態で用いる従来技術として、関数秘匿内積関数型暗号及び共通鍵暗号について説明する。
【００２８】
・関数秘匿内積関数型暗号（つまり、関数秘匿性を有する単入力内積関数型暗号）
変換元となる関数秘匿内積関数型暗号としては、従来技術により構成された関数秘匿内積関数型暗号を用いることができる。ここで、本発明の実施の形態で用いる関数秘匿内積関数型暗号は、剰余環Zn上で内積が計算できるものとする。ただし、復号値として必ずしも剰余環Zn上の内積値が出力される必要はなく、値同士で加法の準同型演算が可能であれば、何等かのエンコードされた値が出力されてもよい。
【００２９】
このような関数秘匿内積関数型暗号の構成方法は、いくつか知られているが、例えば、以下の参考文献１や参考文献２を参照されたい。
【００３０】
［参考文献１］
A. Bishop, A. Jain, and L. Kowalczyk. Function-hiding inner product encryption. In T. Iwata and J. H. Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS, pages 470-491. Springer, Heidelberg, Nov. / Dec. 2015.
［参考文献２］
H. Lin. Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In J. Katz and H. Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 599-629. Springer, Heidelberg, Aug. 2017.
これらの関数秘匿内積関数型暗号は、双線型群と呼ばれる数学的な構造を用いて構成されている。
【００３１】
以降では、関数秘匿内積関数型暗号のセットアップアルゴリズム、暗号化アルゴリズム、鍵生成アルゴリズム及び復号アルゴリズムをそれぞれ「Setup´」、「Enc´」、「KeyGen´」及び「Dec´」と表す。また、関数秘匿内積関数型暗号が内積を計算する剰余環の位数をnとする（つまり、変換元の関数秘匿内積関数型暗号は、剰余環Zn上で内積を計算するものとする。）。
【００３２】
・共通鍵暗号
共通鍵暗号は任意の一方向性関数から構成できることが知られている。ここで、本発明の実施の形態で用いる共通鍵暗号は、或る種の識別不可能性（具体的には、選択的平文攻撃のもとでの識別不可能性（Indistinguishability under Chosen-Plaintext Attack））を満たすものとする。選択的平文攻撃のもとでの識別不可能性については、例えば、以下の参考文献３を参照されたい。
【００３３】
［参考文献３］
COSC 530: Lecture Notes on Symmetric-Key Encryption, [online], インターネット<URL: http://people.cs.georgetown.edu/~adam/fa15530/cs530-lec4.pdf>
なお、実用上は、共通鍵暗号として、例えば、AES（Advanced Encryption Standard）やCamellia等を用いることができる。
【００３４】
以降では、共通鍵暗号の鍵生成アルゴリズム、暗号化アルゴリズム及び復号アルゴリズムをそれぞれ「SKE.Gen」、「SKE.Enc」及び「SKE.Dec」と表す。
【００３５】
＜全体構成＞
本発明の実施の形態における暗号システム１は、上記の関数秘匿内積関数型暗号のSetup´、Enc´、KeyGen´及びDec´と、上記の共通鍵暗号のSKE.Gen、SKE.Enc及びSKE.Decとを用いて、関数秘匿多入力内積関数型暗号のセットアップアルゴリズムSetup、暗号化アルゴリズムEnc、鍵生成アルゴリズムKeyGen及び復号アルゴリズムDecを構成する。そこで、本発明の実施の形態における暗号システム１の全体構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における暗号システム１の全体構成の一例を示す図である。
【００３６】
図１に示すように、本発明の実施の形態における暗号システム１には、セットアップ装置１０と、暗号化装置２０と、鍵生成装置３０と、復号装置４０とが含まれる。また、これらの各装置は、通信ネットワークＮを介して相互に通信可能に接続されている。
【００３７】
セットアップ装置１０は、セットアップアルゴリズムSetupを実行するコンピュータ又はコンピュータシステムである。
【００３８】
セットアップ装置１０には、セットアップ処理部１０１と、記憶部１０２とが含まれる。セットアップ処理部１０１は、ベクトル長m（ただし、mは自然数）と引数の数μ（ただし、μは自然数）とを入力として、セットアップアルゴリズムSetupを実行する。セットアップアルゴリズムSetupでは、マスター秘密鍵mskと公開パラメータppとが生成及び出力される。また、記憶部１０２には、セットアップアルゴリズムSetupに用いられる各種情報（例えば、ベクトル長mや引数の数μ）やセットアップアルゴリズムSetupの出力結果（例えば、マスター秘密鍵mskや公開パラメータpp）等が記憶される。なお、セットアップアルゴリズムSetupには、セキュリティパラメータ1λが入力されてもよい。
【００３９】
なお、セットアップ処理部１０１は、例えば、セットアップ装置１０にインストールされた１以上のプログラムが、プロセッサ等の演算装置に実行させる処理により実現される。また、記憶部１０２は、各種メモリ（例えば、主記憶装置や補助記憶装置等）を用いて実現可能である。
【００４０】
暗号化装置２０は、暗号化アルゴリズムEncを実行するコンピュータ又はコンピュータシステムである。
【００４１】
暗号化装置２０には、暗号化処理部２０１と、記憶部２０２とが含まれる。暗号化処理部２０１は、マスター秘密鍵mskと、公開パラメータppと、引数のインデックスi∈[μ]と、ベクトルx∈Zmとを入力として、暗号化アルゴリズムEncを実行する。暗号化アルゴリズムEncでは、インデックスiに対応する暗号文ctiが生成及び出力される。また、記憶部２０２には、暗号化アルゴリズムEncに用いられる各種情報（例えば、マスター秘密鍵mskや公開パラメータpp、インデックスi、ベクトルx等）や暗号化アルゴリズムEncの出力結果（例えば、暗号文cti）等が記憶される。
【００４２】
なお、暗号化処理部２０１は、例えば、暗号化装置２０にインストールされた１以上のプログラムが、プロセッサ等の演算装置に実行させる処理により実現される。また、記憶部２０２は、各種メモリ（例えば、主記憶装置や補助記憶装置等）を用いて実現可能である。
【００４３】
鍵生成装置３０は、鍵生成アルゴリズムKeyGenを実行するコンピュータ又はコンピュータシステムである。
【００４４】
鍵生成装置３０には、鍵生成処理部３０１と、記憶部３０２とが含まれる。鍵生成処理部３０１は、マスター秘密鍵mskと、公開パラメータppと、μ個のベクトル{yi}i∈[μ]（ただし、yi∈Zm）とを入力として、鍵生成アルゴリズムKeyGenを実行する。鍵生成アルゴリズムKeyGenでは、秘密鍵skが生成及び出力される。また、記憶部３０２には、鍵生成アルゴリズムKeyGenに用いられる各種情報（例えば、マスター秘密鍵mskや公開パラメータpp、ベクトル{yi}i∈[μ]）や鍵生成アルゴリズムKeyGenの出力結果（例えば、秘密鍵sk）等が記憶される。
【００４５】
なお、鍵生成処理部３０１は、例えば、鍵生成装置３０にインストールされた１以上のプログラムが、プロセッサ等の演算装置に実行させる処理により実現される。また、記憶部３０２は、各種メモリ（例えば、主記憶装置や補助記憶装置等）を用いて実現可能である。
【００４６】
復号装置４０は、復号アルゴリズムDecを実行するコンピュータ又はコンピュータシステムである。
【００４７】
復号装置４０には、復号処理部４０１と、記憶部４０２とが含まれる。復号処理部４０１は、公開パラメータppと、暗号文{cti}i∈[μ]と、秘密鍵skとを入力として、復号アルゴリズムDecを実行する。復号アルゴリズムDecでは、復号値dが生成及び出力される。また、記憶部４０２には、復号アルゴリズムDecに用いられる各種情報（例えば、公開パラメータppや暗号文{cti}i∈[μ]、秘密鍵sk）や復号アルゴリズムDecの出力結果（例えば、復号値d）等が記憶される。
【００４８】
なお、復号処理部４０１は、例えば、復号装置４０にインストールされた１以上のプログラムが、プロセッサ等の演算装置に実行させる処理により実現される。また、記憶部４０２は、各種メモリ（例えば、主記憶装置や補助記憶装置等）を用いて実現可能である。
【００４９】
図１に示す暗号システム１の構成は一例であって、他の構成であってもよい。例えば、セットアップ装置１０、暗号化装置２０及び鍵生成装置３０のうちの任意の２以上の装置が１つの装置として構成されていてもよい。また、暗号システム１には、複数台の復号装置４０が含まれていてもよい。同様に、セットアップ装置１０、暗号化装置２０及び鍵生成装置３０のうちの任意の１以上の装置が複数台含まれていてもよい。
【００５０】
＜セットアップ＞
次に、セットアップ装置１０が実行する処理（セットアップアルゴリズムSetupにより実現される処理）について、図２を参照しながら説明する。図２は、本発明の実施の形態におけるセットアップ装置１０が実行する処理の一例を示すフローチャートである。
【００５１】
まず、セットアップ処理部１０１は、ベクトル長mと引数の数μとを入力する（ステップＳ１０１）。なお、ベクトル長mと引数の数μとの入力元は任意であり、例えば、記憶部１０２から入力されてもよいし、キーボード等の入力装置から入力されてもよいし、通信ネットワークＮを介して接続された他の装置から入力されてもよい。
【００５２】
次に、セットアップ処理部１０１は、セットアップアルゴリズムSetup(m,μ)により、マスター秘密鍵mskと公開パラメータppとを生成する（ステップＳ１０２）。
【００５３】
ここで、セットアップ処理部１０１は、
【００５４】
【数５】
2020086292.tif 000007
として、
【００５５】
【数６】
2020086292.tif 000008
により公開パラメータppを生成する。
【００５６】
また、セットアップ処理部１０１は、K←SKE.Gen（つまり、共通鍵暗号の鍵生成アルゴリズムSKE.Genの出力結果をK）として、
【００５７】
【数７】
2020086292.tif 000009
とした上で、
【００５８】
【数８】
2020086292.tif 000010
とする。なお、
【００５９】
【数９】
2020086292.tif 000011
は排他的論理和を表す。
【００６０】
更に、セットアップ処理部１０１は、
【００６１】
【数１０】
2020086292.tif 000012
として、
【００６２】
【数１１】
2020086292.tif 000013
によりマスター秘密鍵mskを生成する。
【００６３】
以上によりマスター秘密鍵mskと公開パラメータppとが生成される。マスター秘密鍵mskと公開パラメータppとは、例えば、記憶部１０２に記憶される。また、マスター秘密鍵msk及び公開パラメータppは、例えば、通信ネットワークＮを介して暗号化装置２０や鍵生成装置３０に送信される。
【００６４】
＜暗号化＞
次に、暗号化装置２０が実行する処理（暗号化アルゴリズムEncにより実現される処理）について、図３を参照しながら説明する。図３は、本発明の実施の形態における暗号化装置２０が実行する処理の一例を示すフローチャートである。
【００６５】
まず、暗号化処理部２０１は、マスター秘密鍵mskと、公開パラメータppと、インデックスi∈[μ]と、ベクトルx∈Zmとを入力する（ステップＳ２０１）。なお、マスター秘密鍵mskと、公開パラメータppと、インデックスi∈[μ]と、ベクトルx∈Zmとの入力元は任意であり、例えば、記憶部２０２から入力されてもよいし、キーボード等の入力装置から入力されてもよいし、通信ネットワークＮを介して接続された他の装置から入力されてもよい。
【００６６】
次に、暗号化処理部２０１は、暗号化アルゴリズムEnc(msk,pp,i,x)により、インデックスiに対応する暗号文ctiを生成する（ステップＳ２０２）。
【００６７】
ここで、暗号化処理部２０１は、
【００６８】
【数１２】
2020086292.tif 000014
として、
【００６９】
【数１３】
2020086292.tif 000015
とする。なお、0mはZmのゼロベクトルを表す。
【００７０】
そして、暗号化処理部２０１は、
【００７１】
【数１４】
2020086292.tif 000016
として、cti:=(Ki,Ci)により、インデックスiに対応する暗号文ctiを生成する。
【００７２】
以上により、インデックスiに対応する暗号文ctiが生成される。暗号文ctiは、例えば、記憶部２０２に記憶されてもよいし、通信ネットワークＮを介して他の装置（例えば、復号装置４０等）に送信されてもよい。
【００７３】
＜鍵生成＞
次に、鍵生成装置３０が実行する処理（鍵生成アルゴリズムKeyGenにより実現される処理）について、図４を参照しながら説明する。図４は、本発明の実施の形態における鍵生成装置３０が実行する処理の一例を示すフローチャートである。
【００７４】
まず、鍵生成処理部３０１は、マスター秘密鍵mskと、公開パラメータppと、ベクトル{yi}i∈[μ]とを入力する（ステップＳ３０１）。なお、マスター秘密鍵mskと、公開パラメータppと、ベクトル{yi}i∈[μ]との入力元は任意であり、例えば、記憶部３０２から入力されてもよいし、キーボード等の入力装置から入力されてもよいし、通信ネットワークＮを介して接続された他の装置から入力されてもよい。
【００７５】
次に、鍵生成処理部３０１は、鍵生成アルゴリズムKeyGen(msk,pp,{yi}i∈[μ])により、秘密鍵skを生成する（ステップＳ３０２）。
【００７６】
ここで、鍵生成処理部３０１は、
【００７７】
【数１５】
2020086292.tif 000017
として、
【００７８】
【数１６】
2020086292.tif 000018
とした上で、
【００７９】
【数１７】
2020086292.tif 000019
とする。そして、鍵生成処理部３０１は、
【００８０】
【数１８】
2020086292.tif 000020
として、
【００８１】
【数１９】
2020086292.tif 000021
により秘密鍵skを生成する。
【００８２】
以上により秘密鍵skが生成される。秘密鍵skは、例えば、通信ネットワークＮを介して復号装置４０に送信される。また、このとき、秘密鍵skと共に公開パラメータppが復号装置４０に送信されてもよい。
【００８３】
＜復号＞
次に、復号装置４０が実行する処理（復号アルゴリズムDecにより実現される処理）について、図５を参照しながら説明する。図５は、本発明の実施の形態における復号装置４０が実行する処理の一例を示すフローチャートである。
【００８４】
まず、復号処理部４０１は、公開パラメータppと、暗号文{cti}i∈[μ]と、秘密鍵skとを入力する（ステップＳ４０１）。なお、公開パラメータppと、暗号文{cti}i∈[μ]と、秘密鍵skとの入力元は任意であり、例えば、記憶部４０２から入力されてもよいし、キーボード等の入力装置から入力されてもよいし、通信ネットワークＮを介して接続された他の装置から入力されてもよい。
【００８５】
次に、復号処理部４０１は、復号アルゴリズムDec(pp, {cti}i∈[μ],sk)により、復号値dを生成する（ステップＳ４０２）。
【００８６】
ここで、復号処理部４０１は、
【００８７】
【数２０】
2020086292.tif 000022
として、
【００８８】
【数２１】
2020086292.tif 000023
とすると共に、
【００８９】
【数２２】
2020086292.tif 000024
とする。次に、復号処理部４０１は、
【００９０】
【数２３】
2020086292.tif 000025
として、
【００９１】
【数２４】
2020086292.tif 000026
とする。なお、○はエンコードされたZn上の元同士の準同型演算である。
【００９２】
そして、復号処理部４０１は、d´をデコードすることで、復号値dを生成する。
【００９３】
以上により復号値dが生成される。復号値dは、例えば、記憶部４０２に記憶されてもよいし、通信ネットワークＮを介して他の装置に送信されてもよい。
【００９４】
＜実施例＞
上記の図２乃至図５に示す各処理では、共通鍵暗号と関数秘匿内積関数型暗号とを用いて、当該関数秘匿内積関数型暗号を関数秘匿多入力内積関数型暗号に汎用的に変換する場合について説明した。以降の実施例では、具体的な関数秘匿内積関数型暗号を用いた場合について説明する。
【００９５】
以降の実施例では、以下の参考文献４に記載されている内積関数型暗号（より具体的にはA one-SEL-SIM scheme for single-input inner product）に対して、以下の参考文献５に記載されている手法を適用することで、当該内積関数型暗号が関数秘匿性を有するように構成した関数秘匿内積関数型暗号を用いるものとする。これにより、例えば、非特許文献１や非特許文献２に記載されている関数秘匿多入力内積関数型暗号よりも効率的な関数秘匿多入力内積関数型暗号を実現することができる。
【００９６】
［参考文献４］
Michel Abdalla, Romain Gay, Mariana Raykova, and Hoeteck Wee. Multi-input inner-product functional encryption from pairings. In Jean-Sebastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part I, volume 10210 of LNCS, pages 601-626. Springer, Heidelberg, April / May 2017.
［参考文献５］
H. Lin. Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In J. Katz and H. Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 599-629. Springer, Heidelberg, Aug. 2017.
なお、以降の実施例では、kは任意の自然数としてよい。また、pは素数である。
【００９７】
（実施例におけるセットアップ）
図２のステップＳ１０１において、セットアップ処理部１０１は、ベクトル長mと引数の数μとを入力する。そして、図２のステップＳ１０２において、セットアップ処理部１０１は、セットアップアルゴリズムSetup(m,μ)により、マスター秘密鍵mskと公開パラメータppとを生成する。このとき、本実施例では、以下によりマスター秘密鍵mskと公開パラメータppとを生成する。
【００９８】
まず、セットアップ処理部１０１は、
【００９９】
【数２５】
2020086292.tif 000027
として、K←SKE.Genとする。次に、セットアップ処理部１０１は、
【０１００】
【数２６】
2020086292.tif 000028
とすると共に、
【０１０１】
【数２７】
2020086292.tif 000029
とする。そして、セットアップ処理部１０１は、
【０１０２】
【数２８】
2020086292.tif 000030
によりマスター秘密鍵mskを生成する。
【０１０３】
また、セットアップ処理部１０１は、適当なk-線型仮定が成り立つ双線型群G1,G2,GTを指定する情報を公開パラメータppとする。なお、k-線型仮定の定義については、例えば、以下の参考文献６を参照されたい。
【０１０４】
［参考文献６］
Allison B. Lewko and Brent Waters, "Efficient pseudorandom functions from the decisional linear assumption and weaker variants", Proceedin gs of the 2009 ACM Conference on Computer and Communications Security, CCS 2009, Chicago, Illinois, USA, pp. 112-120, Nov. 2009.
上記の参考文献６にはk-線型仮定が成り立つ双線型群を楕円曲線から構成する例が記載されているが、このような楕円曲線のより一般的な構成方法が以下の参考文献７に記載されている。
【０１０５】
［参考文献７］
David Freeman, Michael Scott and Edlyn Teske, "A taxonomy of pairing-friendly elliptic curves, IACR Cryptology ePrint Archive, vol. 2006, pp. 372, http://eprint.iacr.org/2006/372, 2006.
なお、上記の双線型群G1,G2,GTは必ずしも楕円曲線から構成されている必要はない。これらの双線型群G1,G2,GTは楕円曲線以外の方法により構成されたものであってもよい。
【０１０６】
（実施例における暗号化）
図３のステップＳ２０１において、暗号化処理部２０１は、マスター秘密鍵mskと、公開パラメータppと、インデックスi∈[μ]と、ベクトルx∈Zmとを入力する。そして、図３のステップＳ２０２において、暗号化処理部２０１は、暗号化アルゴリズムEnc(msk,pp,i,x)により、インデックスiに対応する暗号文ctiを生成する。このとき、本実施例では、以下により暗号文ctiを生成する。
【０１０７】
まず、暗号化処理部２０１は、
【０１０８】
【数２９】
2020086292.tif 000031
とすると共に、
【０１０９】
【数３０】
2020086292.tif 000032
とした上で、
【０１１０】
【数３１】
2020086292.tif 000033
とする。また、暗号化処理部２０１は、
【０１１１】
【数３２】
2020086292.tif 000034
とする。そして、暗号化処理部２０１は、cti=(Ci,Ki)により、インデックスiに対応する暗号文ctiを生成する。
【０１１２】
（実施例における鍵生成）
図４のステップＳ３０１において、鍵生成処理部３０１は、マスター秘密鍵mskと、公開パラメータppと、ベクトル{yi}i∈[μ]とを入力する。そして、図４のステップＳ３０２において、鍵生成処理部３０１は、鍵生成アルゴリズムKeyGen(msk,pp,{yi}i∈[μ])により、秘密鍵skを生成する。このとき、本実施例では、以下により秘密鍵skを生成する。
【０１１３】
まず、鍵生成処理部３０１は、
【０１１４】
【数３３】
2020086292.tif 000035
とすると共に、
【０１１５】
【数３４】
2020086292.tif 000036
とした上で、
【０１１６】
【数３５】
2020086292.tif 000037
とする。また、鍵生成処理部３０１は、
【０１１７】
【数３６】
2020086292.tif 000038
とする。そして、鍵生成処理部３０１は、
【０１１８】
【数３７】
2020086292.tif 000039
として、
【０１１９】
【数３８】
2020086292.tif 000040
により秘密鍵skを生成する。
【０１２０】
（実施例における復号）
図５のステップＳ４０１において、復号処理部４０１は、公開パラメータppと、暗号文{cti}i∈[μ]と、秘密鍵skとを入力する。そして、図５のステップＳ４０２において、復号処理部４０１は、復号アルゴリズムDec(pp, {cti}i∈[μ],sk)により、復号値dを生成する。このとき、本実施例では、以下により復号値dを生成する。
【０１２１】
まず、復号処理部４０１は、
【０１２２】
【数３９】
2020086292.tif 000041
として、
【０１２３】
【数４０】
2020086292.tif 000042
とすると共に、
【０１２４】
【数４１】
2020086292.tif 000043
とする。次に、復号処理部４０１は、
【０１２５】
【数４２】
2020086292.tif 000044
とする。そして、復号処理部４０１は、e(g1,g2)を底とするd´の離散対数問題を解いた結果を復号値dとして生成する。
【０１２６】
＜ハードウェア構成＞
最後に、本発明の実施の形態における暗号システム１に含まれるセットアップ装置１０、暗号化装置２０、鍵生成装置３０及び復号装置４０のハードウェア構成について説明する。これらの装置のハードウェアとしては、例えば、図６に示すコンピュータ５００を用いて実現可能である。図６は、コンピュータ５００のハードウェア構成の一例を示す図である。
【０１２７】
図６に示すコンピュータ５００は、入力装置５０１と、表示装置５０２と、ＲＡＭ（Random Access Memory）５０３と、ＲＯＭ（Read Only Memory）５０４と、プロセッサ５０５と、外部Ｉ／Ｆ５０６と、通信Ｉ／Ｆ５０７と、補助記憶装置５０８とを有する。これら各ハードウェアは、それぞれがバス５０９を介して通信可能に接続されている。
【０１２８】
入力装置５０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置５０２は、例えばディスプレイ等であり、コンピュータ５００の処理結果を表示する。なお、コンピュータ５００は、入力装置５０１及び表示装置５０２の少なくとも一方を有していなくてもよい。
【０１２９】
ＲＡＭ５０３は、プログラムやデータを一時保持する揮発性の半導体メモリ（主記憶装置）である。ＲＯＭ５０４は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ５０４には、例えば、ＯＳ（Operating System）に関する設定情報や通信ネットワークＮに接続するための設定情報等が格納されている。
【０１３０】
プロセッサ５０５は、例えばＣＰＵ（Central Processing Unit）等であり、ＲＯＭ５０４や補助記憶装置５０８等からプログラムやデータをＲＡＭ５０３上に読み出して処理を実行する演算装置である。
【０１３１】
外部Ｉ／Ｆ５０６は、外部装置とのインタフェースである。外部装置には、記録媒体５０６ａ等がある。コンピュータ５００は、外部Ｉ／Ｆ５０６を介して、記録媒体５０６ａの読み取りや書き込み等を行うことができる。
【０１３２】
記録媒体５０６ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【０１３３】
通信Ｉ／Ｆ５０７は、コンピュータ５００を通信ネットワークＮに接続するためのインタフェースである。
【０１３４】
補助記憶装置５０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置５０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上で各種機能を実現するアプリケーションプログラム、本発明の実施の形態における各種処理を実現するプログラム等がある。
【０１３５】
本発明の実施の形態におけるセットアップ装置１０、暗号化装置２０、鍵生成装置３０及び復号装置４０は、図６に示すコンピュータ５００のハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図６に示す例に限られず、コンピュータ５００は、例えば、複数の演算装置（プロセッサ５０６）と、複数のメモリ（ＲＡＭ５０３やＲＯＭ５０４、補助記憶装置５０）とを有していてもよい。
【０１３６】
＜まとめ＞
以上のように、本発明の実施の形態における暗号システム１では、所定の性質（つまり、剰余環Zn上で内積が計算可能）を有する関数秘匿内積関数型暗号を関数秘匿多入力内積関数型暗号へ汎用的に変換することができる。したがって、本発明の実施の形態における暗号システム１によれば、所定の性質を有する関数秘匿内積関数型暗号さえ安全に設計できればよくなり、関数秘匿多入力内積関数型暗号の設計に要する労力を大幅に削減することができる。ただし、上述したように、関数秘匿多入力内積関数型暗号を実現する際に用いる共通鍵暗号は、選択的平文攻撃のもとでの識別不可能性を満たしている必要がある。
【０１３７】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１３８】
１        暗号システム
１０      セットアップ装置
２０      暗号化装置
３０      鍵生成装置
４０      復号装置
１０１    セットアップ処理部
１０２    記憶部
２０１    暗号化処理部
２０２    記憶部
３０１    鍵生成処理部
３０２    記憶部
４０１    復号処理部
４０２    記憶部
【図１】
2020086292.tif 000045
【図２】
2020086292.tif 000046
【図３】
2020086292.tif 000047
【図４】
2020086292.tif 000048
【図５】
2020086292.tif 000049
【図６】
2020086292.tif 000050