(57)【要約】【課題】秘密鍵関数型暗号において、1-key方式からunbounded-key方式を構成する。【解決手段】（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を入力とした回路秘匿化によって（Ｃ〜，｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得、Ｒ［ｉ］を要素Ｚｉ，αとする行列を得、Ｋｉ，αにＰＲＧを適用して擬似乱数Ｋｉ，α〜を得、暗号文ｃｉ，α←Ｅ（Ｋｉ，α〜，Ｚｉ，α）を得、秘密鍵ｓｋｆ１←（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得る。ｍ１とＲとの排他的論理和値ｘのｉ∈［ｎ］ビット目の値をｘ［ｉ］として暗号文ＣＴ１←｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］を得、ＫｉにＰＲＧを適用してＫｉ〜を得、Ｋｉ〜を共通鍵としてｃｉ，０を復号できるのであればＬｉ←Ｄ（Ｋｉ〜，ｃｉ，０）を得、そうでなければＬｉ←Ｄ（Ｋｉ〜，ｃｉ，１）を得、Ｃ〜と｛Ｌｉ｝ｉ∈［ｎ］について秘匿回路を実行する。【選択図】図１
2018112613.tif 000002
【特許請求の範囲】
【請求項１】
ｎ，ｔ，λが正整数であり、ｎ≦λであり、ｗ＝λ１／ｔが正整数であり、Ｃｆ１がｎ個の論理ゲートｉ∈［ｎ］からなる論理回路であり、前記論理回路Ｃｆ１は関数ｆ１によって表される演算を行い、ＧａｒｂｌｅがＧａｒｂｌｉｎｇ方式で前記論理回路Ｃｆ１を秘匿化して前記ｎ個の論理ゲートｉ∈［ｎ］の鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝とを得る秘匿化アルゴリズムであり、Ｅｖａｌが前記鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］を用い、前記Ｇａｒｂｌｉｎｇ方式に則り、前記関数ｆ１によって表される演算を行う実行アルゴリズムであり、Ｅが共通鍵暗号方式に則った暗号化を行う暗号化アルゴリズムであり、Ｄが前記共通鍵暗号方式に則った復号を行う復号アルゴリズムであり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，α←｛０，１｝ｗを選択し、Ｒ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ１←（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を得るセットアップアルゴリズムＳｅｔｕｐ１を実行するセットアップ装置と、
前記関数ｆ１および前記マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を入力とし、前記秘匿化アルゴリズムＧａｒｂｌｅを実行して（Ｃ〜，｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得、前記Ｒのｉ∈［ｎ］ビット目の値Ｒ［ｉ］を要素Ｚｉ，αとする行列
【数４】
2018112613.tif 000006
を得、各ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，αに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ，α〜を得、前記暗号化アルゴリズムＥを用い、前記擬似乱数Ｋｉ，α〜を共通鍵として前記要素Ｚｉ，αを暗号化した暗号文ｃｉ，α←Ｅ（Ｋｉ，α〜，Ｚｉ，α）を得、前記関数ｆ１に対する秘密鍵ｓｋｆ１←（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得る鍵生成アルゴリズムＫＧ１を実行する鍵生成装置と、
前記マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）およびメッセージｍ１∈｛０，１｝λを入力とし、ｍ１とＲとの排他的論理和値ｘ∈｛０，１｝λを得、前記排他的論理和値ｘのｉ∈［ｎ］ビット目の値をｘ［ｉ］として暗号文ＣＴ１←｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］を得る暗号化アルゴリズムＥｎｃ１を実行する暗号化装置と、
前記秘密鍵ｓｋｆ１＝（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）および前記暗号文ＣＴ１＝｛Ｋｉ｝ｉ∈［ｎ］を入力とし、各ｉ∈［ｎ］についてＫｉに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ〜を得、前記復号アルゴリズムＤを用い、前記擬似乱数Ｋｉ〜を共通鍵として前記暗号文ｃｉ，０を復号できるのであれば、前記擬似乱数Ｋｉ〜を共通鍵として前記暗号文ｃｉ，０を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，０）を得、そうでなければ、前記擬似乱数Ｋｉ〜を共通鍵として前記暗号文ｃｉ，１を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，１）を得、前記鍵情報Ｃ〜と前記秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］について前記実行アルゴリズムＥｖａｌを実行する復号アルゴリズムＤｅｃ１を実行する復号装置と、
を有する暗号システム。
【請求項２】
第１関数暗号がunbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ１が、マスター秘密鍵ＭＳＫ１を得る前記第１関数暗号のセットアップアルゴリズムであり、ＫＧ１が、関数ｆ１およびマスター秘密鍵ＭＳＫ１を入力として前記関数ｆ１に対する秘密鍵ｓｋｆ１を得る前記第１関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ１が、前記マスター秘密鍵ＭＳＫ１およびメッセージｍ１を入力とし、前記マスター秘密鍵ＭＳＫ１で前記メッセージｍ１を暗号化して暗号文ＣＴ１を得る前記第１関数暗号の暗号化アルゴリズムであり、Ｄｅｃ１が、前記秘密鍵ｓｋｆ１および前記暗号文ＣＴ１を入力とし、前記秘密鍵ｓｋｆ１で前記暗号文ＣＴ１を復号する前記第１関数暗号の復号アルゴリズムであり、
第２関数暗号がλ-key unbounded-ciphertext 秘密鍵関数型暗号であり、Ｓｅｔｕｐ２が、マスター秘密鍵ＭＳＫ２を得る前記第２関数暗号のセットアップアルゴリズムであり、ＫＧ２が、関数ｆ２、マスター秘密鍵ＭＳＫ２、インデックスｊを入力として前記関数ｆ２に対する秘密鍵ｓｋｆ２を得る前記第２関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ２が、前記マスター秘密鍵ＭＳＫ２およびメッセージｍ２を入力とし、前記マスター秘密鍵ＭＳＫ２で前記メッセージｍ２を暗号化して暗号文ＣＴ２を得る前記第２関数暗号の暗号化アルゴリズムであり、Ｄｅｃ２が、前記秘密鍵ｓｋｆ２および前記暗号文ＣＴ２を入力とし、前記秘密鍵ｓｋｆ２で前記暗号文ＣＴ２を復号する前記第２関数暗号の復号アルゴリズムであり、
⊥が無意味な情報を表し、λが正整数であり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
前記Ｓｅｔｕｐ２を実行して前記マスター秘密鍵ＭＳＫ２←Ｓｅｔｕｐ２（１λ）を得るセットアップアルゴリズムＳｅｔｕｐ３を実行するセットアップ装置と、
前記マスター秘密鍵ＭＳＫ２、前記関数ｆ３、および前記インデックスｊを入力とし、θ∈｛０，１｝λを選択し、θに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数ｒθ←ＰＲＧ（θ）を得、パラメータ（ｍ０，ｍ１，γ）（ただし、γ∈｛０，１｝）を入力として関数ｆ３の関数値ｆ３（ｍγ）を出力する関数をＣ［ｆ３］とし、設定されたパラメータ（ｆ０，ｆ１，ｖ，ｊ，θ）について前記マスター秘密鍵ＭＳＫ１およびα∈｛０，１｝を入力としてＭＳＫ１＝⊥ならばｖを出力し、そうでなければ前記ＫＧ１を実行して関数Ｃ［ｆα］に対する、前記擬似乱数ｒθでランダム化された秘密鍵ｓｋＣ←ＫＧ１（ＭＳＫ１，Ｃ［ｆα］；ｒθ）を得て秘密鍵ｓｋＣおよび前記インデックスｊを出力する関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］を設定し、前記ＫＧ２を実行して、関数Ｇ［ｆ３，⊥，⊥，ｊ，θ］に対する秘密鍵ｓｋＧ←ＫＧ２（ＭＳＫ２，Ｇ［ｆ３，⊥，⊥，ｊ，θ］，ｊ）を得る鍵生成アルゴリズムＫＧ３を実行する鍵生成装置と、
前記マスター秘密鍵ＭＳＫ２およびメッセージｍ３を入力とし、前記Ｓｅｔｕｐ１を実行してマスター秘密鍵ＭＳＫ１←Ｓｅｔｕｐ１（１λ）を得、前記Ｅｎｃ１を実行し、前記マスター秘密鍵ＭＳＫ１でメッセージ（ｍ３，⊥，０）を暗号化して暗号文ＣＴ１←Ｅｎｃ１（ＭＳＫ１，（ｍ３，⊥，０））を得、前記Ｅｎｃ２を実行し、前記マスター秘密鍵ＭＳＫ２でメッセージ（ＭＳＫ１，０）を暗号化して暗号文ＣＴ２←Ｅｎｃ２（ＭＳＫ２，（ＭＳＫ１，０））を得、暗号文ＣＴ３←（ＣＴ１，ＣＴ２）を得る暗号化アルゴリズムＥｎｃ３を実行する暗号化装置と、
前記秘密鍵ｓｋＧおよび前記暗号文ＣＴ３＝（ＣＴ１，ＣＴ２）を入力とし、前記Ｄｅｃ２を実行して前記秘密鍵ｓｋＧで前記暗号文ＣＴ２を復号することで前記秘密鍵ｓｋＣ←Ｄｅｃ２（ｓｋＧ，ＣＴ２）を得、前記Ｄｅｃ１を実行して前記秘密鍵ｓｋＣで前記暗号文ＣＴ１を復号することで復号値ｙ←Ｄｅｃ１（ｓｋＣ，ＣＴ１）を得る復号アルゴリズムＤｅｃ３を実行する復号装置と、
を有する暗号システム。
【請求項３】
請求項２の暗号システムであって、
前記Ｓｅｔｕｐ１は、請求項１の前記Ｓｅｔｕｐ１であり、
前記ＫＧ１は、請求項１の前記ＫＧ１であり、
前記Ｅｎｃ１は、請求項１の前記Ｅｎｃ１であり、
前記Ｄｅｃ１は、請求項１の前記Ｄｅｃ１である、暗号システム。
【請求項４】
ｑ４が正整数であり、第４関数型暗号がq4-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ４が、マスター秘密鍵ＭＳＫ４を得る前記第４関数暗号のセットアップアルゴリズムであり、ＫＧ４が、関数ｆ４、マスター秘密鍵ＭＳＫ４、およびインデックスιを入力として前記関数ｆ４に対する秘密鍵ｓｋｆ４を得る前記第４関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ４が、前記マスター秘密鍵ＭＳＫ４およびメッセージｍ４を入力とし、前記マスター秘密鍵ＭＳＫ４で前記メッセージｍ４を暗号化して暗号文ＣＴ４を得る前記第４関数暗号の暗号化アルゴリズムであり、Ｄｅｃ４が、前記秘密鍵ｓｋｆ４および前記暗号文ＣＴ４を入力とし、前記秘密鍵ｓｋｆ４で前記暗号文ＣＴ４を復号する前記第４関数暗号の復号アルゴリズムであり、
ｑ５が正整数であり、第５関数型暗号がq5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ５が、マスター秘密鍵ＭＳＫ５を得る前記第５関数暗号のセットアップアルゴリズムであり、ＫＧ５が、関数ｆ５、マスター秘密鍵ＭＳＫ５、およびインデックスκを入力として前記関数ｆ５に対する秘密鍵ｓｋｆ５を得る前記第５関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ５が、前記マスター秘密鍵ＭＳＫ５およびメッセージｍ５を入力とし、前記マスター秘密鍵ＭＳＫ５で前記メッセージｍ５を暗号化して暗号文ＣＴ５を得る前記第５関数暗号の暗号化アルゴリズムであり、Ｄｅｃ５が、前記秘密鍵ｓｋｆ５および前記暗号文ＣＴ５を入力とし、前記秘密鍵ｓｋｆ５で前記暗号文ＣＴ５を復号する前記第５関数暗号の復号アルゴリズムであり、
λが正整数であり、
前記Ｓｅｔｕｐ４を実行して前記マスター秘密鍵ＭＳＫ４←Ｓｅｔｕｐ４（１λ）を得、擬似ランダム関数ＰＲＦの鍵Ｓ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ６←（ＭＳＫ４，Ｓ）を得るセットアップアルゴリズムＳｅｔｕｐ６を実行するセットアップ装置と、
前記マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）、関数ｆ６、および前記インデックスι，κを入力とし、前記鍵Ｓおよび前記インデックスιに前記擬似ランダム関数ＰＲＦを適用して擬似乱数ｒ５，ι←ＰＲＦ（Ｓ，ι）を得、前記Ｓｅｔｕｐ５を実行して擬似乱数ｒ５，ιでランダム化されたマスター秘密鍵ＭＳＫ５ι←Ｓｅｔｕｐ５（１λ；ｒ５，ι）を得、擬似ランダム関数の鍵Ｓι←｛０，１｝λを選択し、前記鍵Ｓιおよび前記マスター秘密鍵ＭＳＫ５ιが設定された関数ｅι［Ｓι，ＭＳＫ５ι］であって、任意の（ｍ，ｍ〜，ｒ，ＣＴ〜）を入力として擬似乱数ｒι←ＰＲＦ（Ｓι，ｒ）を得る処理と、前記Ｅｎｃ５を実行して前記マスター秘密鍵ＭＳＫ５ιでｍを暗号化して前記擬似乱数ｒιでランダム化された暗号文ＣＴ５ι←Ｅｎｃ５（ＭＳＫ５ι，ｍ；ｒι）を出力する処理と、を行うものを設定し、前記マスター秘密鍵ＭＳＫ４、前記関数ｅι［Ｓι，ＭＳＫ５ι］、および前記インデックスιを入力として前記ＫＧ４を実行して秘密鍵ｓｋｅι←ＫＧ４（ＭＳＫ４，ｅι［Ｓι，ＭＳＫ５ι］，ι）を得、前記マスター秘密鍵ＭＳＫ５ι、前記関数ｆ６を、および前記インデックスκを入力として前記ＫＧ５を実行して前記関数ｆ６に対応する秘密鍵ｓｋｆ６，ι←ＫＧ５（ＭＳＫ５ι，ｆ６，κ）を得、秘密鍵ｓｋｆ６←（ｓｋｅι，ｓｋｆ６，ι）を得る鍵生成アルゴリズムＫＧ６を実行する鍵生成装置と、
前記マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）およびメッセージｍ６を入力とし、ｒ←｛０，１｝λを選択し、前記Ｅｎｃ４を実行して前記マスター秘密鍵ＭＳＫ４で（ｍ６，⊥，ｒ，⊥）を暗号化して暗号文ＣＴ４←Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を得る暗号化アルゴリズムＥｎｃ６を実行する暗号化装置と、
前記秘密鍵ｓｋｆ６＝（ｓｋｅι，ｓｋｆ６，ι）および前記暗号文ＣＴ４＝Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を入力とし、前記Ｄｅｃ４を実行して前記秘密鍵ｓｋｅιで前記暗号文ＣＴ４を復号して前記暗号文ＣＴ５ι←Ｄｅｃ４（ｓｋｅι，ＣＴ４）を得、前記Ｄｅｃ５を実行して前記秘密鍵ｓｋｆ６，ιで前記暗号文ＣＴ５ιを復号して復号値ｙ←Ｄｅｃ５（ｓｋｆ６，ι，ＣＴ５ι）を得る復号アルゴリズムＤｅｃ６を実行する復号装置と、
を有する暗号システム。
【請求項５】
請求項４の暗号システムであって、
ｑ４・ｑ５＝λｔである、暗号システム。
【請求項６】
請求項５の暗号システムであって、
前記Ｓｅｔｕｐ４および前記Ｓｅｔｕｐ５は、請求項３の前記Ｓｅｔｕｐ３であり、
前記ＫＧ４および前記ＫＧ５は、請求項３の前記ＫＧ３であり、
前記Ｅｎｃ４および前記Ｅｎｃ５は、請求項３の前記Ｅｎｃ３であり、
前記Ｄｅｃ４および前記Ｄｅｃ５は、請求項３の前記Ｄｅｃ３であり、
請求項１の前記ＫＧ１および前記Ｄｅｃ１で用いられる前記似乱数生成アルゴリズムＰＲＧは、quasi exponentailly-secure 一方向性関数を利用して構成されており、
ｔ＝ｌｏｇｌｏｇλである、暗号システム。
【請求項７】
λが正整数であり、η＝ｌｏｇｌｏｇλであり、ｋ∈［η］であり、第６関数型暗号ＳＫＦＥ６ｋがλk-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ６ｋが、マスター秘密鍵ＭＳＫ６ｋを得る前記第６関数暗号ＳＫＦＥ６ｋのセットアップアルゴリズムであり、ＫＧ６ｋが、関数ｆ６ｋ、マスター秘密鍵ＭＳＫ６ｋ、およびインデックスβｋを入力として前記関数ｆ６ｋに対する秘密鍵ｓｋｆ６，ｋを得る前記第６関数暗号ＳＫＦＥ６ｋの鍵生成アルゴリズムであり、Ｅｎｃ６ｋが、前記マスター秘密鍵ＭＳＫ６ｋおよびメッセージｍ６を入力とし、前記マスター秘密鍵ＭＳＫ６ｋで前記メッセージｍ６を暗号化して暗号文ＣＴ６ｋを得る前記第６関数暗号ＳＫＦＥ６ｋの暗号化アルゴリズムであり、Ｄｅｃ６ｋが、前記秘密鍵ｓｋｆ６，ｋおよび前記暗号文ＣＴ６ｋを入力とし、前記秘密鍵ｓｋｆ６，ｋで前記暗号文ＣＴ６をｋ復号する前記第６関数暗号ＳＫＦＥ６ｋの復号アルゴリズムであり、
各ｋ∈［η］について前記Ｓｅｔｕｐ６ｋを実行してマスター秘密鍵ＭＳＫ６ｋ←Ｓｅｔｕｐ６ｋ（１λ）を得、マスター秘密鍵ＭＳＫ７←（ＭＳＫ６１，…，ＭＳＫ６η）を得るセットアップアルゴリズムＳｅｔｕｐ７を実行するセットアップ装置と、
前記マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）、関数ｆ７、およびインデックス（ｋ，ρ）を入力とし、前記ＫＧ６ｋを実行して秘密鍵ｓｋｆ６，ｋ←ＫＧ６ｋ（ＭＳＫ６ｋ，ｆ７，ρ）を得、前記関数ｆ７に対する秘密鍵ｓｋｆ７←（ｋ，ｓｋｆ６，ｋ）を得る鍵生成アルゴリズムＫＧ７を実行する鍵生成装置と、
前記マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）およびメッセージｍ７を入力とし、各ｋ∈［η］について前記Ｅｎｃ６ｋを実行して前記マスター秘密鍵ＭＳＫ６ｋで前記メッセージｍ７を暗号化した暗号文ＣＴ６ｋ←Ｅｎｃ６ｋ（ＭＳＫ６ｋ，ｍ７）を得、暗号文ＣＴ７←（ＣＴ６１，…，ＣＴ６η）を得る暗号化アルゴリズムＥｎｃ７を実行する暗号化装置と、
前記秘密鍵ｓｋｆ７＝（ｋ，ｓｋｆ６，ｋ）および前記暗号文ＣＴ７＝（ＣＴ６１，…，ＣＴ６η）を入力とし、前記Ｄｅｃ６ｋを実行して前記秘密鍵ｓｋｆ６，ｋで前記暗号文ＭＳＫ６ｋを復号して復号値ｙ←Ｄｅｃ６ｋ（ｓｋｆ６，ｋ，ＣＴ６ｋ）を得る復号アルゴリズムＤｅｃ７を実行する復号装置と、
を有する暗号システム。
【請求項８】
請求項７の暗号システムであって、
前記Ｓｅｔｕｐ６ｋは、ｔ←ｋとした請求項５の前記Ｓｅｔｕｐ６であり、
前記ＫＧ６ｋは、ｔ←ｋとした請求項５の前記ＫＧ６であり、
前記Ｅｎｃ６ｋは、ｔ←ｋとした請求項５の前記Ｅｎｃ６であり、
前記Ｄｅｃ６ｋは、ｔ←ｋとした請求項５の前記Ｄｅｃ６である、暗号システム。
【請求項９】
ｎ，ｔ，λが正整数であり、ｎ≦λであり、ｗ＝λ１／ｔが正整数であり、Ｃｆ１がｎ個の論理ゲートｉ∈［ｎ］からなる論理回路であり、前記論理回路Ｃｆ１は関数ｆ１によって表される演算を行い、ＧａｒｂｌｅがＧａｒｂｌｉｎｇ方式で前記論理回路Ｃｆ１を秘匿化して前記ｎ個の論理ゲートｉ∈［ｎ］の鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝とを得る秘匿化アルゴリズムであり、Ｅｖａｌが前記鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］を用い、前記Ｇａｒｂｌｉｎｇ方式に則り、前記関数ｆ１によって表される演算を行う実行アルゴリズムであり、Ｅが共通鍵暗号方式に則った暗号化を行う暗号化アルゴリズムであり、Ｄが前記共通鍵暗号方式に則った復号を行う復号アルゴリズムであり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，α←｛０，１｝ｗを選択し、Ｒ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ１←（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を得るセットアップアルゴリズムＳｅｔｕｐ１が実行されており、
前記関数ｆ１および前記マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）が入力され、
前記秘匿化アルゴリズムＧａｒｂｌｅを実行して（Ｃ〜，｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得る秘匿化部と、
前記Ｒのｉ∈［ｎ］ビット目の値Ｒ［ｉ］を要素Ｚｉ，αとする行列
【数５】
2018112613.tif 000007
を得る行列生成部と、
各ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，αに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ，α〜を得る擬似乱数生成部と、
前記暗号化アルゴリズムＥを用い、前記擬似乱数Ｋｉ，α〜を共通鍵として前記要素Ｚｉ，αを暗号化した暗号文ｃｉ，α←Ｅ（Ｋｉ，α〜，Ｚｉ，α）を得る暗号化部と、
前記関数ｆ１に対する秘密鍵ｓｋｆ１←（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得る秘密鍵生成部と、
を有する鍵生成装置。
【請求項１０】
ｎ，ｔ，λが正整数であり、ｎ≦λであり、ｗ＝λ１／ｔが正整数であり、Ｃｆ１がｎ個の論理ゲートｉ∈［ｎ］からなる論理回路であり、前記論理回路Ｃｆ１は関数ｆ１によって表される演算を行い、ＧａｒｂｌｅがＧａｒｂｌｉｎｇ方式で前記論理回路Ｃｆ１を秘匿化して前記ｎ個の論理ゲートｉ∈［ｎ］の鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝とを得る秘匿化アルゴリズムであり、Ｅｖａｌが前記鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］を用い、前記Ｇａｒｂｌｉｎｇ方式に則り、前記関数ｆ１によって表される演算を行う実行アルゴリズムであり、Ｅが共通鍵暗号方式に則った暗号化を行う暗号化アルゴリズムであり、Ｄが前記共通鍵暗号方式に則った復号を行う復号アルゴリズムであり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，α←｛０，１｝ｗを選択し、Ｒ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ１←（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を得るセットアップアルゴリズムＳｅｔｕｐ１が実行されており、
前記マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）およびメッセージｍ∈｛０，１｝λが入力され、
ｍ１とＲとの排他的論理和値ｘ∈｛０，１｝λを得る排他的論理和部と、
前記排他的論理和値ｘのｉ∈［ｎ］ビット目の値をｘ［ｉ］として暗号文ＣＴ１←｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］を得る暗号化部と、
を有する暗号化装置。
【請求項１１】
ｎ，ｔ，λが正整数であり、ｎ≦λであり、ｗ＝λ１／ｔが正整数であり、Ｃｆ１がｎ個の論理ゲートｉ∈［ｎ］からなる論理回路であり、前記論理回路Ｃｆ１は関数ｆ１によって表される演算を行い、ＧａｒｂｌｅがＧａｒｂｌｉｎｇ方式で前記論理回路Ｃｆ１を秘匿化して前記ｎ個の論理ゲートｉ∈［ｎ］の鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝とを得る秘匿化アルゴリズムであり、Ｅｖａｌが前記鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］を用い、前記Ｇａｒｂｌｉｎｇ方式に則り、前記関数ｆ１によって表される演算を行う実行アルゴリズムであり、Ｅが共通鍵暗号方式に則った暗号化を行う暗号化アルゴリズムであり、Ｄが前記共通鍵暗号方式に則った復号を行う復号アルゴリズムであり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，α←｛０，１｝ｗを選択し、Ｒ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ１←（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を得るセットアップアルゴリズムＳｅｔｕｐ１と、
前記関数ｆ１および前記マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を入力とし、前記秘匿化アルゴリズムＧａｒｂｌｅを実行して（Ｃ〜，｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得、前記Ｒのｉ∈［ｎ］ビット目の値Ｒ［ｉ］を要素Ｚｉ，αとする行列
【数６】
2018112613.tif 000008
を得、各ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，αに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ，α〜を得、前記暗号化アルゴリズムＥを用い、前記擬似乱数Ｋｉ，α〜を共通鍵として前記要素Ｚｉ，αを暗号化した暗号文ｃｉ，α←Ｅ（Ｋｉ，α〜，Ｚｉ，α）を得、前記関数ｆ１に対する秘密鍵ｓｋｆ１←（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得る鍵生成アルゴリズムＫＧ１と、
前記マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）およびメッセージｍ∈｛０，１｝λを入力とし、ｍ１とＲとの排他的論理和値ｘ∈｛０，１｝λを得、前記排他的論理和値ｘのｉ∈［ｎ］ビット目の値をｘ［ｉ］として暗号文ＣＴ１←｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］を得る暗号化アルゴリズムＥｎｃ１と、が実行されており、
前記秘密鍵ｓｋｆ１＝（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）および前記暗号文ＣＴ１＝｛Ｋｉ｝ｉ∈［ｎ］が入力され、
各ｉ∈［ｎ］についてＫｉに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ〜を得る擬似乱数生成部と、
前記復号アルゴリズムＤを用い、前記擬似乱数Ｋｉ〜を共通鍵として前記暗号文ｃｉ，０を復号できるのであれば、前記擬似乱数Ｋｉ〜を共通鍵として前記暗号文ｃｉ，０を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，０）を得、そうでなければ、前記擬似乱数Ｋｉ〜を共通鍵として前記暗号文ｃｉ，１を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，１）を得る復号部と、
前記鍵情報Ｃ〜と前記秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］について前記実行アルゴリズムＥｖａｌを実行する実行部と、
を有する復号装置。
【請求項１２】
第１関数暗号がunbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ１が、マスター秘密鍵ＭＳＫ１を得る前記第１関数暗号のセットアップアルゴリズムであり、ＫＧ１が、関数ｆ１およびマスター秘密鍵ＭＳＫ１を入力として前記関数ｆ１に対する秘密鍵ｓｋｆ１を得る前記第１関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ１が、前記マスター秘密鍵ＭＳＫ１およびメッセージｍ１を入力とし、前記マスター秘密鍵ＭＳＫ１で前記メッセージｍ１を暗号化して暗号文ＣＴ１を得る前記第１関数暗号の暗号化アルゴリズムであり、Ｄｅｃ１が、前記秘密鍵ｓｋｆ１および前記暗号文ＣＴ１を入力とし、前記秘密鍵ｓｋｆ１で前記暗号文ＣＴ１を復号する前記第１関数暗号の復号アルゴリズムであり、
第２関数暗号がλ-key unbounded-ciphertext 秘密鍵関数型暗号であり、Ｓｅｔｕｐ２が、マスター秘密鍵ＭＳＫ２を得る前記第２関数暗号のセットアップアルゴリズムであり、ＫＧ２が、関数ｆ２、マスター秘密鍵ＭＳＫ２、インデックスｊを入力として前記関数ｆ２に対する秘密鍵ｓｋｆ２を得る前記第２関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ２が、前記マスター秘密鍵ＭＳＫ２およびメッセージｍ２を入力とし、前記マスター秘密鍵ＭＳＫ２で前記メッセージｍ２を暗号化して暗号文ＣＴ２を得る前記第２関数暗号の暗号化アルゴリズムであり、Ｄｅｃ２が、前記秘密鍵ｓｋｆ２および前記暗号文ＣＴ２を入力とし、前記秘密鍵ｓｋｆ２で前記暗号文ＣＴ２を復号する前記第２関数暗号の復号アルゴリズムであり、
⊥が無意味な情報を表し、λが正整数であり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
前記Ｓｅｔｕｐ２を実行して前記マスター秘密鍵ＭＳＫ２←Ｓｅｔｕｐ２（１λ）を得るセットアップアルゴリズムＳｅｔｕｐ３が実行されており、
前記マスター秘密鍵ＭＳＫ２、前記関数ｆ３、および前記インデックスｊが入力され、
θ∈｛０，１｝λを選択する選択部と、
θに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数ｒθ←ＰＲＧ（θ）を得る擬似乱数生成部と、
パラメータ（ｍ０，ｍ１，γ）（ただし、γ∈｛０，１｝）を入力として関数ｆ３の関数値ｆ３（ｍγ）を出力する関数をＣ［ｆ３］とし、設定されたパラメータ（ｆ０，ｆ１，ｖ，ｊ，θ）について前記マスター秘密鍵ＭＳＫ１およびα∈｛０，１｝を入力としてＭＳＫ１＝⊥ならばｖを出力し、そうでなければ前記ＫＧ１を実行して関数Ｃ［ｆα］に対する、前記擬似乱数ｒθでランダム化された秘密鍵ｓｋＣ←ＫＧ１（ＭＳＫ１，Ｃ［ｆα］；ｒθ）を得て秘密鍵ｓｋＣおよび前記インデックスｊを出力する関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］を設定する関数設定部と、
前記ＫＧ２を実行して、関数Ｇ［ｆ３，⊥，⊥，ｊ，θ］に対する秘密鍵ｓｋＧ←ＫＧ２（ＭＳＫ２，Ｇ［ｆ３，⊥，⊥，ｊ，θ］，ｊ）を得る秘密鍵生成部と、
を有する鍵生成装置。
【請求項１３】
第１関数暗号がunbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ１が、マスター秘密鍵ＭＳＫ１を得る前記第１関数暗号のセットアップアルゴリズムであり、ＫＧ１が、関数ｆ１およびマスター秘密鍵ＭＳＫ１を入力として前記関数ｆ１に対する秘密鍵ｓｋｆ１を得る前記第１関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ１が、前記マスター秘密鍵ＭＳＫ１およびメッセージｍ１を入力とし、前記マスター秘密鍵ＭＳＫ１で前記メッセージｍ１を暗号化して暗号文ＣＴ１を得る前記第１関数暗号の暗号化アルゴリズムであり、Ｄｅｃ１が、前記秘密鍵ｓｋｆ１および前記暗号文ＣＴ１を入力とし、前記秘密鍵ｓｋｆ１で前記暗号文ＣＴ１を復号する前記第１関数暗号の復号アルゴリズムであり、
第２関数暗号がλ-key unbounded-ciphertext 秘密鍵関数型暗号であり、Ｓｅｔｕｐ２が、マスター秘密鍵ＭＳＫ２を得る前記第２関数暗号のセットアップアルゴリズムであり、ＫＧ２が、関数ｆ２、マスター秘密鍵ＭＳＫ２、インデックスｊを入力として前記関数ｆ２に対する秘密鍵ｓｋｆ２を得る前記第２関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ２が、前記マスター秘密鍵ＭＳＫ２およびメッセージｍ２を入力とし、前記マスター秘密鍵ＭＳＫ２で前記メッセージｍ２を暗号化して暗号文ＣＴ２を得る前記第２関数暗号の暗号化アルゴリズムであり、Ｄｅｃ２が、前記秘密鍵ｓｋｆ２および前記暗号文ＣＴ２を入力とし、前記秘密鍵ｓｋｆ２で前記暗号文ＣＴ２を復号する前記第２関数暗号の復号アルゴリズムであり、
⊥が無意味な情報を表し、λが正整数であり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
前記Ｓｅｔｕｐ２を実行して前記マスター秘密鍵ＭＳＫ２←Ｓｅｔｕｐ２（１λ）を得るセットアップアルゴリズムＳｅｔｕｐ３が実行されており、
前記マスター秘密鍵ＭＳＫ２およびメッセージｍ３が入力され、
前記Ｓｅｔｕｐ１を実行してマスター秘密鍵ＭＳＫ１←Ｓｅｔｕｐ１（１λ）を得るセットアップ部と、
前記Ｅｎｃ１を実行し、前記マスター秘密鍵ＭＳＫ１でメッセージ（ｍ３，⊥，０）を暗号化して暗号文ＣＴ１←Ｅｎｃ１（ＭＳＫ１，（ｍ３，⊥，０））を得、前記Ｅｎｃ２を実行し、前記マスター秘密鍵ＭＳＫ２でメッセージ（ＭＳＫ１，０）を暗号化して暗号文ＣＴ２←Ｅｎｃ２（ＭＳＫ２，（ＭＳＫ１，０））を得、暗号文ＣＴ３←（ＣＴ１，ＣＴ２）を得る暗号化部と、
を有する暗号化装置。
【請求項１４】
第１関数暗号がunbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ１が、マスター秘密鍵ＭＳＫ１を得る前記第１関数暗号のセットアップアルゴリズムであり、ＫＧ１が、関数ｆ１およびマスター秘密鍵ＭＳＫ１を入力として前記関数ｆ１に対する秘密鍵ｓｋｆ１を得る前記第１関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ１が、前記マスター秘密鍵ＭＳＫ１およびメッセージｍ１を入力とし、前記マスター秘密鍵ＭＳＫ１で前記メッセージｍ１を暗号化して暗号文ＣＴ１を得る前記第１関数暗号の暗号化アルゴリズムであり、Ｄｅｃ１が、前記秘密鍵ｓｋｆ１および前記暗号文ＣＴ１を入力とし、前記秘密鍵ｓｋｆ１で前記暗号文ＣＴ１を復号する前記第１関数暗号の復号アルゴリズムであり、
第２関数暗号がλ-key unbounded-ciphertext 秘密鍵関数型暗号であり、Ｓｅｔｕｐ２が、マスター秘密鍵ＭＳＫ２を得る前記第２関数暗号のセットアップアルゴリズムであり、ＫＧ２が、関数ｆ２、マスター秘密鍵ＭＳＫ２、インデックスｊを入力として前記関数ｆ２に対する秘密鍵ｓｋｆ２を得る前記第２関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ２が、前記マスター秘密鍵ＭＳＫ２およびメッセージｍ２を入力とし、前記マスター秘密鍵ＭＳＫ２で前記メッセージｍ２を暗号化して暗号文ＣＴ２を得る前記第２関数暗号の暗号化アルゴリズムであり、Ｄｅｃ２が、前記秘密鍵ｓｋｆ２および前記暗号文ＣＴ２を入力とし、前記秘密鍵ｓｋｆ２で前記暗号文ＣＴ２を復号する前記第２関数暗号の復号アルゴリズムであり、
⊥が無意味な情報を表し、λが正整数であり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムであり、
前記Ｓｅｔｕｐ２を実行して前記マスター秘密鍵ＭＳＫ２←Ｓｅｔｕｐ２（１λ）を得るセットアップアルゴリズムＳｅｔｕｐ３と、
前記マスター秘密鍵ＭＳＫ２、前記関数ｆ３、および前記インデックスｊを入力とし、θ∈｛０，１｝λを選択し、θに前記擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数ｒθ←ＰＲＧ（θ）を得、パラメータ（ｍ０，ｍ１，γ）（ただし、γ∈｛０，１｝）を入力として関数ｆ３の関数値ｆ３（ｍγ）を出力する関数をＣ［ｆ３］とし、設定されたパラメータ（ｆ０，ｆ１，ｖ，ｊ，θ）について前記マスター秘密鍵ＭＳＫ１およびα∈｛０，１｝を入力としてＭＳＫ１＝⊥ならばｖを出力し、そうでなければ前記ＫＧ１を実行して関数Ｃ［ｆα］に対する、前記擬似乱数ｒθでランダム化された秘密鍵ｓｋＣ←ＫＧ１（ＭＳＫ１，Ｃ［ｆα］；ｒθ）を得て秘密鍵ｓｋＣおよび前記インデックスｊを出力する関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］を設定し、前記ＫＧ２を実行して、関数Ｇ［ｆ３，⊥，⊥，ｊ，θ］に対する秘密鍵ｓｋＧ←ＫＧ２（ＭＳＫ２，Ｇ［ｆ３，⊥，⊥，ｊ，θ］，ｊ）を得る鍵生成アルゴリズムＫＧ３と、
前記マスター秘密鍵ＭＳＫ２およびメッセージｍ３を入力とし、前記Ｓｅｔｕｐ１を実行してマスター秘密鍵ＭＳＫ１←Ｓｅｔｕｐ１（１λ）を得、前記Ｅｎｃ１を実行し、前記マスター秘密鍵ＭＳＫ１でメッセージ（ｍ３，⊥，０）を暗号化して暗号文ＣＴ１←Ｅｎｃ１（ＭＳＫ１，（ｍ３，⊥，０））を得、前記Ｅｎｃ２を実行し、前記マスター秘密鍵ＭＳＫ２でメッセージ（ＭＳＫ１，０）を暗号化して暗号文ＣＴ２←Ｅｎｃ２（ＭＳＫ２，（ＭＳＫ１，０））を得、暗号文ＣＴ３←（ＣＴ１，ＣＴ２）を得る暗号化アルゴリズムＥｎｃ３と、が実行されており、
前記秘密鍵ｓｋＧおよび前記暗号文ＣＴ３＝（ＣＴ１，ＣＴ２）が入力され、
前記Ｄｅｃ２を実行して前記秘密鍵ｓｋＧで前記暗号文ＣＴ２を復号することで前記秘密鍵ｓｋＣ←Ｄｅｃ２（ｓｋＧ，ＣＴ２）を得る秘密鍵復号部と、
前記Ｄｅｃ１を実行して前記秘密鍵ｓｋＣで前記暗号文ＣＴ１を復号することで復号値ｙ←Ｄｅｃ１（ｓｋＣ，ＣＴ１）を得る復号部と、
を有する復号装置。
【請求項１５】
ｑ４が正整数であり、第４関数型暗号がq4-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ４が、マスター秘密鍵ＭＳＫ４を得る前記第４関数暗号のセットアップアルゴリズムであり、ＫＧ４が、関数ｆ４、マスター秘密鍵ＭＳＫ４、およびインデックスιを入力として前記関数ｆ４に対する秘密鍵ｓｋｆ４を得る前記第４関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ４が、前記マスター秘密鍵ＭＳＫ４およびメッセージｍ４を入力とし、前記マスター秘密鍵ＭＳＫ４で前記メッセージｍ４を暗号化して暗号文ＣＴ４を得る前記第４関数暗号の暗号化アルゴリズムであり、Ｄｅｃ４が、前記秘密鍵ｓｋｆ４および前記暗号文ＣＴ４を入力とし、前記秘密鍵ｓｋｆ４で前記暗号文ＣＴ４を復号する前記第４関数暗号の復号アルゴリズムであり、
ｑ５が正整数であり、第５関数型暗号がq5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ５が、マスター秘密鍵ＭＳＫ５を得る前記第５関数暗号のセットアップアルゴリズムであり、ＫＧ５が、関数ｆ５、マスター秘密鍵ＭＳＫ５、およびインデックスκを入力として前記関数ｆ５に対する秘密鍵ｓｋｆ５を得る前記第５関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ５が、前記マスター秘密鍵ＭＳＫ５およびメッセージｍ５を入力とし、前記マスター秘密鍵ＭＳＫ５で前記メッセージｍ５を暗号化して暗号文ＣＴ５を得る前記第５関数暗号の暗号化アルゴリズムであり、Ｄｅｃ５が、前記秘密鍵ｓｋｆ５および前記暗号文ＣＴ５を入力とし、前記秘密鍵ｓｋｆ５で前記暗号文ＣＴ５を復号する前記第５関数暗号の復号アルゴリズムであり、
λが正整数であり、
前記Ｓｅｔｕｐ４を実行して前記マスター秘密鍵ＭＳＫ４←Ｓｅｔｕｐ４（１λ）を得、擬似ランダム関数ＰＲＦの鍵Ｓ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ６←（ＭＳＫ４，Ｓ）を得るセットアップアルゴリズムＳｅｔｕｐ６が実行されており、
前記マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）、関数ｆ６、および前記インデックスι，κが入力され、
前記鍵Ｓおよび前記インデックスιに前記擬似ランダム関数ＰＲＦを適用して擬似乱数ｒ５，ι←ＰＲＦ（Ｓ，ι）を得る擬似乱数生成部と、
前記Ｓｅｔｕｐ５を実行して擬似乱数ｒ５，ιでランダム化されたマスター秘密鍵ＭＳＫ５ι←Ｓｅｔｕｐ５（１λ；ｒ５，ι）を得るセットアップ部と、
擬似ランダム関数の鍵Ｓι←｛０，１｝λを選択する鍵選択部と、
前記鍵Ｓιおよび前記マスター秘密鍵ＭＳＫ５ιが設定された関数ｅι［Ｓι，ＭＳＫ５ι］であって、任意の（ｍ，ｍ〜，ｒ，ＣＴ〜）を入力として擬似乱数ｒι←ＰＲＦ（Ｓι，ｒ）を得る処理と、前記Ｅｎｃ５を実行して前記マスター秘密鍵ＭＳＫ５ιでｍを暗号化して前記擬似乱数ｒιでランダム化された暗号文ＣＴ５ι←Ｅｎｃ５（ＭＳＫ５ι，ｍ；ｒι）を出力する処理と、を行うものを設定する関数設定部と、
前記マスター秘密鍵ＭＳＫ４、前記関数ｅι［Ｓι，ＭＳＫ５ι］、および前記インデックスιを入力として前記ＫＧ４を実行して秘密鍵ｓｋｅι←ＫＧ４（ＭＳＫ４，ｅι［Ｓι，ＭＳＫ５ι］，ι）を得、前記マスター秘密鍵ＭＳＫ５ι、前記関数ｆ６を、および前記インデックスκを入力として前記ＫＧ５を実行して前記関数ｆ６に対応する秘密鍵ｓｋｆ６，ι←ＫＧ５（ＭＳＫ５ι，ｆ６，κ）を得、秘密鍵ｓｋｆ６←（ｓｋｅι，ｓｋｆ６，ι）を得る秘密鍵生成部と、
を有する鍵生成装置。
【請求項１６】
ｑ４が正整数であり、第４関数型暗号がq4-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ４が、マスター秘密鍵ＭＳＫ４を得る前記第４関数暗号のセットアップアルゴリズムであり、ＫＧ４が、関数ｆ４、マスター秘密鍵ＭＳＫ４、およびインデックスιを入力として前記関数ｆ４に対する秘密鍵ｓｋｆ４を得る前記第４関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ４が、前記マスター秘密鍵ＭＳＫ４およびメッセージｍ４を入力とし、前記マスター秘密鍵ＭＳＫ４で前記メッセージｍ４を暗号化して暗号文ＣＴ４を得る前記第４関数暗号の暗号化アルゴリズムであり、Ｄｅｃ４が、前記秘密鍵ｓｋｆ４および前記暗号文ＣＴ４を入力とし、前記秘密鍵ｓｋｆ４で前記暗号文ＣＴ４を復号する前記第４関数暗号の復号アルゴリズムであり、
ｑ５が正整数であり、第５関数型暗号がq5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であり、Ｓｅｔｕｐ５が、マスター秘密鍵ＭＳＫ５を得る前記第５関数暗号のセットアップアルゴリズムであり、ＫＧ５が、関数ｆ５、マスター秘密鍵ＭＳＫ５、およびインデックスκを入力として前記関数ｆ５に対する秘密鍵ｓｋｆ５を得る前記第５関数暗号の鍵生成アルゴリズムであり、Ｅｎｃ５が、前記マスター秘密鍵ＭＳＫ５およびメッセージｍ５を入力とし、前記マスター秘密鍵ＭＳＫ５で前記メッセージｍ５を暗号化して暗号文ＣＴ５を得る前記第５関数暗号の暗号化アルゴリズムであり、Ｄｅｃ５が、前記秘密鍵ｓｋｆ５および前記暗号文ＣＴ５を入力とし、前記秘密鍵ｓｋｆ５で前記暗号文ＣＴ５を復号する前記第５関数暗号の復号アルゴリズムであり、
λが正整数であり、
前記Ｓｅｔｕｐ４を実行して前記マスター秘密鍵ＭＳＫ４←Ｓｅｔｕｐ４（１λ）を得、擬似ランダム関数ＰＲＦの鍵Ｓ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ６←（ＭＳＫ４，Ｓ）を得るセットアップアルゴリズムＳｅｔｕｐ６と、
前記マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）、関数ｆ６、および前記インデックスι，κを入力とし、前記鍵Ｓおよび前記インデックスιに前記擬似ランダム関数ＰＲＦを適用して擬似乱数ｒ５，ι←ＰＲＦ（Ｓ，ι）を得、前記Ｓｅｔｕｐ５を実行して擬似乱数ｒ５，ιでランダム化されたマスター秘密鍵ＭＳＫ５ι←Ｓｅｔｕｐ５（１λ；ｒ５，ι）を得、擬似ランダム関数の鍵Ｓι←｛０，１｝λを選択し、前記鍵Ｓιおよび前記マスター秘密鍵ＭＳＫ５ιが設定された関数ｅι［Ｓι，ＭＳＫ５ι］であって、任意の（ｍ，ｍ〜，ｒ，ＣＴ〜）を入力として擬似乱数ｒι←ＰＲＦ（Ｓι，ｒ）を得る処理と、前記Ｅｎｃ５を実行して前記マスター秘密鍵ＭＳＫ５ιでｍを暗号化して前記擬似乱数ｒιでランダム化された暗号文ＣＴ５ι←Ｅｎｃ５（ＭＳＫ５ι，ｍ；ｒι）を出力する処理と、を行うものを設定し、前記マスター秘密鍵ＭＳＫ４、前記関数ｅι［Ｓι，ＭＳＫ５ι］、および前記インデックスιを入力として前記ＫＧ４を実行して秘密鍵ｓｋｅι←ＫＧ４（ＭＳＫ４，ｅι［Ｓι，ＭＳＫ５ι］，ι）を得、前記マスター秘密鍵ＭＳＫ５ι、前記関数ｆ６を、および前記インデックスκを入力として前記ＫＧ５を実行して前記関数ｆ６に対応する秘密鍵ｓｋｆ６，ι←ＫＧ５（ＭＳＫ５ι，ｆ６，κ）を得、秘密鍵ｓｋｆ６←（ｓｋｅι，ｓｋｆ６，ι）を得る鍵生成アルゴリズムＫＧ６と、
前記マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）およびメッセージｍ６を入力とし、ｒ←｛０，１｝λを選択し、前記マスター秘密鍵ＭＳＫ４および（ｍ６，⊥，ｒ，⊥）を入力として前記Ｅｎｃ４を実行して暗号文ＣＴ４←Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を得る暗号化アルゴリズムＥｎｃ６と、が実行されており、
前記秘密鍵ｓｋｆ６＝（ｓｋｅι，ｓｋｆ６，ι）および前記暗号文ＣＴ４＝Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））が入力され、
前記Ｄｅｃ４を実行して前記秘密鍵ｓｋｅιで前記暗号文ＣＴ４を復号して前記暗号文ＣＴ５ι←Ｄｅｃ４（ｓｋｅι，ＣＴ４）を得る第１復号部と、
前記Ｄｅｃ５を実行して前記秘密鍵ｓｋｆ６，ιで前記暗号文ＣＴ５ιを復号して復号値ｙ←Ｄｅｃ５（ｓｋｆ６，ι，ＣＴ５ι）を得る第２復号部と、
を有する復号装置。
【請求項１７】
請求項６または７の前記暗号システムが有する前記暗号化装置を用い、入力されたプログラムを識別不可能性難読化して難読化プログラムを生成する難読化装置。
【請求項１８】
請求項６または７の前記暗号システムが有する前記復号装置を用い、請求項１７の前記難読化装置で生成された前記難読化プログラムを実行する実行装置。
【請求項１９】
請求項９，１２，１５の鍵生成装置、請求項１０，１３の暗号化装置、請求項１１，１４，１６の復号装置、請求項１７の難読化装置、もしくは請求項１８の実行装置の機能をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関数型暗号技術に関する。
【背景技術】
【０００２】
関数型暗号において、鍵生成アルゴリズムによる鍵の発行回数が１回の場合には安全性が保たれるが、鍵の発行回数が２回以上の場合には安全性が保たれるとは限らない暗号方式（1-key方式）から、鍵生成アルゴリズムによる鍵の発行回数が事前に定められた回数（複数回数）以下の場合には安全性が保たれるが、鍵の発行回数が事前に定められた回数を超えた場合には安全性が保たれるとは限らない暗号方式（bounded-key方式）を構成する方法が知られている（例えば、非特許文献１参照）。また、非特許文献２，３には、公開鍵関数型暗号において、1-key方式から、鍵生成アルゴリズムによる鍵の発行回数にかかわらず、安全性が保たれる暗号方式（unbounded-key方式）を構成する方法が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee, “Functional encryption with bounded collusions via multi-party computation,” In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 162-179. Springer, Heidelberg, August 2012.
【非特許文献２】Baiyu Li and Daniele Micciancio, “Compactness vs collusion resistance in functional encryption,” IACR Cryptology ePrint Archive, 2016:561, 2016.
【非特許文献３】Sanjam Garg and Akshayaram Srinivasan, “Single-key to multi-key functional encryption with polynomial loss,” IACR Cryptology ePrint Archive, 2016:524, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献２の方法を秘密鍵関数型暗号に適用するとbounded-key方式しか得ることができず、非特許文献３は秘密鍵関数型暗号には適用できない。このように、秘密鍵関数型暗号において、1-key方式から、鍵生成アルゴリズムによる鍵の発行回数にかかわらず、安全性が保たれる暗号方式（unbounded-key方式）を構成する方法は知られていない。
【０００５】
本発明はこのような点に鑑みてなされたものであり、秘密鍵関数型暗号において、1-key方式からunbounded-key方式を構成するための暗号方式を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、特許請求の範囲に記載された少なくともいずれかの発明が提供される。
【発明の効果】
【０００７】
本発明では、1-key方式からunbounded-key方式を構成するための各暗号方式を構成できるため、それらの各方式を用いて1-key方式からunbounded-key方式を構成できる。
【図面の簡単な説明】
【０００８】
【図１】図１は第１実施形態の暗号システムを例示したブロック図である。
【図２】図２は第２実施形態の暗号システムを例示したブロック図である。
【図３】図３は第３実施形態の暗号システムを例示したブロック図である。
【図４】図４は第４実施形態の暗号システムを例示したブロック図である。
【図５】図５は第５実施形態の暗号システムを例示したブロック図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［前提］
まず実施形態の前提事項を説明する。
「難読化(obfuscation)」とは、入力されたプログラムを変換し、異なるプログラムに変換することをいう（例えば、Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters, “Candidate indistinguishability obfuscation and functional encryption for all circuits,” In 54th FOCS, pages 40-49. IEEE Computer Society Press, October 2013（参考文献１）等参照）。変換後のプログラムの機能は変換前のプログラムの機能と完全に同一である。変換後のプログラムは変換前のプログラムに関する情報を漏らさない。特に「識別不可能性難読化(Indistinguishability Obfuscation)」とは、同一の機能をもつ２つの異なるプログラムを変換したとき、変換後のプログラムがどちらのプログラムを変換して得られたものかを判別できない「難読化」を意味する。「難読化器(Obfuscator)」とは難読化を行う装置を意味し、「識別不可能性難読化器(Indistinguishability Obfuscator(iO))」とは識別不可能性難読化を行う装置を意味する。確率的多項式時間機械ｉＯがプログラムによって記述される回路が属する回路族｛Ｃλ｝λ∈Ｎに対する「識別不可能性難読化器（Indistinguishability Obfuscator）」であるとは、「機能性」および「識別不可能性」を満たすことである。
「機能性」とは、任意のセキュリティパラメータλ∈Ｎ、任意のプログラムＣ∈｛Ｃλ｝λ∈Ｎ、任意の入力ｘに対して以下を満たすことを意味する。ただし、Ｎは自然数を表し、Ｐｒ［α］は事象αの確率を表し、ｉＯ（Ｃ）はｉＯによってＣを難読化することを表し、α←βはβの結果をαとすることを表す。
Ｐr[C’(x)=C(x):C’←iO(C)]=1
すなわち、ｉＯが機能性を満たすとは、確率的多項式時間機械ｉＯで任意のプログラムＣをプログラムＣ’に変換したとき、入力ｘに対するプログラムＣ’の出力Ｃ’（ｘ）とプログラムＣの出力Ｃ（ｘ）とが等しくなることを意味する。
「識別不可能性」とは、任意の多項式サイズ識別器Ｄ’に対して、無視できる関数μ（・）が存在して、任意のセキュリティパラメータλ∈Ｎ，サイズが等しい任意のプログラム対（回路対）Ｃ０，Ｃ１∈Ｃλで任意の入力ｘについてＣ０（ｘ）＝Ｃ１（ｘ）が成立するものに対し、以下を満たすことを意味する。
Pr[D’(iO(C0))=1]-Pr[D’(iO(C1))=1]≦μ(λ)
すなわち、ｉＯが識別不可能性を満たすとは、ｉＯ（Ｃ０）の判別結果Ｄ’（ｉＯ（Ｃ０））（ｉＯ（Ｃ０）がＣ０を難読化して得られたものなのかＣ１を難読化して得られたものなのかの判別結果）が１となる（例えば、ｉＯ（Ｃ０）がＣ１を難読化して得られたものであると判別される）確率と、ｉＯ（Ｃ１）の判別結果Ｄ’（ｉＯ（Ｃ１））が１となる（例えば、ｉＯ（Ｃ１）がＣ１を難読化して得られたものであると判別される）確率との違いが無視できることを意味する。
【００１０】
「秘密鍵関数型暗号（SKFE：Secret-Key Functional Encryption）」とは、マスター秘密鍵を用いて暗号化を行う関数型暗号（Functional Encryption）を意味する。以下に秘密鍵関数型暗号のアルゴリズム(Setup, KG, Enc, Dec)を示す（例えば、Nir Bitansky, Ryo Nishimaki, Alain Passel`egue, and Daniel Wichs, “From cryptomania to obfustopia through secret-key functional encryption,” IACR Cryptology ePrint Archive, 2016:558, 2016（参考文献２）等参照）。
セットアップアルゴリズム（Ｓｅｔｕｐ）：鍵の長さ（ビット長）を表す任意のセキュリティパラメータλ∈Ｎを入力とし、マスター秘密鍵ＭＳＫを生成する。
MSK ←Setup(1λ)
鍵生成アルゴリズム（ＫＧ）：マスター秘密鍵ＭＳＫおよび関数ｆを入力とし、関数ｆに対する秘密鍵ｓｋｆを生成する。関数ｆは任意の関数でよく、例えば、ｆ（ｍ）＝ｍまたはｆ（ｍ）＝⊥を満たす関数である。ただし、⊥はエラーを表す。
skf ←KG(MSK,f)
暗号化アルゴリズム（Ｅｎｃ）：マスター秘密鍵ＭＳＫとメッセージｍを入力とし、暗号文ｃを生成する。
c ←Enc(MSK, m)
復号アルゴリズム（Ｄｅｃ）：関数ｆに対する秘密鍵ｓｋｆと暗号文ｃを入力とし、メッセージｍの関数値ｆ（ｍ）を生成する。
f(m) ←Dec(skf,c)
【００１１】
「1-key(single-key)方式」とは、鍵生成アルゴリズムによる鍵の発行回数（すなわち、攻撃者による鍵の入手回数）が１回の場合には安全性が保たれるが、鍵の発行回数が２回以上の場合には安全性が保たれるとは限らない暗号方式をいう。
「bounded-key方式」とは、鍵生成アルゴリズムによる鍵の発行回数が事前（セットアップアルゴリズムの実行時）に定められた回数（複数回数）以下の場合には安全性が保たれるが、鍵の発行回数が事前に定められた回数を超えた場合には安全性が保たれるとは限らない暗号方式をいう。特に、鍵生成アルゴリズムによる鍵の発行回数が事前に定められたｑ（ただし、ｑ≧２）以下の場合安全性が保たれるが、鍵の発行回数がｑを超えた場合には安全性が保たれるとは限らない暗号方式を「q-Key方式」という。
「unbounded-key方式」とは、鍵生成アルゴリズムによる鍵の発行回数にかかわらず、安全性が保たれる暗号方式をいう。
【００１２】
「1-ciphertext方式」とは、暗号化アルゴリズムによる暗号文の生成回数（すなわち、攻撃者による暗号文の入手回数）が１回の場合には安全性が保たれるが、暗号文の生成回数が２回以上の場合には安全性が保たれるとは限らない暗号方式をいう。
「unbounded-ciphertext方式」とは、暗号化アルゴリズムによる暗号文の生成回数にかかわらず、安全性が保たれる暗号方式をいう。
【００１３】
「non-succinct方式」とは、暗号化アルゴリズムによって記述される暗号化回路のサイズ｜Ｅ｜が以下の関係を満たす暗号方式をいう。ただし、ｐｏｌｙ（α）はαの多項式を表し、ｎはメッセージｍの長さ（ビット長）を表し、｜ｆ｜は上述の関数ｆのサイズを表す。
|E|=poly(λ,n,|f|)
「weakly-succinct方式」とは、暗号化アルゴリズムによって記述される暗号化回路のサイズ｜Ｅ｜が以下の関係を満たす暗号方式をいう。ただし、εは０＜ε＜１を満たす。
|E|=poly(λ,n)・|f|1-ε
「succinct（完全簡素性）方式」とは、暗号化アルゴリズムによって記述される暗号化回路のサイズ｜Ｅ｜が以下の関係を満たす暗号方式をいう。
|E|=poly(λ,n)
「q-key collusion-succinctness（ｑ−ｋｅｙ結託簡素性）方式」とは、暗号化アルゴリズムによって記述される暗号化回路のサイズ｜Ｅ｜が以下の関係を満たす暗号方式をいう。ただし、ｑは鍵生成アルゴリズムによる鍵の発行回数を表し、εは０＜ε＜１を満たす。
|E|=poly(λ,n,|f|)・q1-ε
【００１４】
上記で定義した「α方式」の関数型暗号を「α関数型暗号」と呼び、「α方式」の秘密鍵関数型暗号を「α秘密鍵関数型暗号」と呼ぶことにする。また、上記で定義した複数の方式の用語を組み合わせることで、それらの方式の性質を兼ね備える暗号方式を表現することにする。例えば、unbounded-key方式および1-ciphertext方式の両方の性質を備える秘密鍵関数型暗号を「unbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号」と呼び、1-key方式およびunbounded-ciphertext方式の両方の性質を備える秘密鍵関数型暗号を「1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号」と呼び、λ-key方式及びunbounded-ciphertext方式の両方の性質を備える秘密鍵関数型暗号を「λ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号」と呼び、λt-key方式およびunbounded-ciphertext方式の両方の性質を備える秘密鍵関数型暗号を「λt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号」と呼び、unbounded-key方式およびunbounded-ciphertext方式の両方の性質を備える秘密鍵関数型暗号を「unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号」と呼ぶ。
【００１５】
［原理］
次に原理を説明する。
＜unbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ１＞
unbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号であって暗号文サイズが高々λ１／ｔ・φである方式ＳＫＦＥ１＝（Ｓｅｔｕｐ１，ＫＧ１，Ｅｎｃ１，Ｄｅｃ１）の構成を説明する。
ただし、φ，ｎ，ｔ，λ∈Ｎが正整数であり、ｎ≦λであり、ｗ＝λ１／ｔが正整数である。λは鍵長に対応するセキュリティパラメータであり、Ｃｆ１はｎ個の論理ゲートｉ∈［ｎ］からなる論理回路であり、関数ｆ１によって表される演算を行う。ＧＣ＝（Ｇａｒｂｌｅ，Ｅｖａｌ）はＧａｒｂｌｉｎｇ方式を表す（例えば、Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway, “Foundations of garbled circuits,” In Ting Yu, George Danezis, and Virgil D. Gligor, editors, ACM CCS 12, pages 784-796. ACM Press, October 2012（参考文献３）等参照）。ｉ∈［ｎ］はｉ∈｛１，・・・，ｎ｝と同義である。ＧａｒｂｌｅはＧａｒｂｌｉｎｇ方式ＧＣで論理回路Ｃｆ１を秘匿化してｎ個の論理ゲートｉ∈［ｎ］の鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝とを得る秘匿化アルゴリズムである。Ｅｖａｌは鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］を用い、Ｇａｒｂｌｉｎｇ方式ＧＣに則り、関数ｆ１によって表される演算を行う実行アルゴリズムである。ＳＫＥ＝（Ｇｅｎ，Ｅ，Ｄ）は鍵空間が｛０，１｝λである共通鍵暗号方式を表す（Jonathan Katz and Yehuda Lindell, “Introduction to Modern Cryptography,” Chapman & Hall/CRC Press, 2007（参考文献４）等参照）。Ｇｅｎは共通鍵暗号方式ＳＫＥに則った鍵生成アルゴリズムであり、Ｅは共通鍵暗号方式ＳＫＥに則った暗号化を行う暗号化アルゴリズムであり、Ｄは共通鍵暗号方式ＳＫＥに則った復号を行う復号アルゴリズムである。ＰＲＧは入力長Ｌの入力情報に対してその２倍の長さ２Ｌの擬似乱数を出力する擬似乱数生成器（擬似乱数生成アルゴリズム）｛ＰＲＧ：｛０，１｝Ｌ→｛０，１｝２Ｌ｝Ｌ∈Ｎを表す（参考文献４）。
【００１６】
セットアップアルゴリズムＳｅｔｕｐ１（１λ）：
Ｓｅｔｕｐ１（１λ）は、セキュリティパラメータλを入力とし、ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，α←｛０，１｝ｗを選択し、Ｒ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ１←（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を得て出力する。ただし、「α１←α２」は、α２をα１として設定することを意味する。
【００１７】
鍵生成アルゴリズムＫＧ１（ＭＳＫ１，ｆ１）：
ＫＧ１（ＭＳＫ１，ｆ１）は、関数ｆ１およびマスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を入力とし、以下の処理を行う。
まず、ＫＧ１（ＭＳＫ１，ｆ１）は、関数ｆ１に対応する論理回路Ｃｆ１に対して秘匿化アルゴリズムＧａｒｂｌｅを実行して（Ｃ〜，｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）←Ｇａｒｂｌｅ（１λ，Ｃｆ１）を得る。ＫＧ１（ＭＳＫ１，ｆ１）は、Ｒのｉ∈［ｎ］ビット目の値Ｒ［ｉ］をｉ行α列の要素Ｚｉ，αとする２×ｎ行列
【数１】
2018112613.tif 000003
を得る。
次にＫＧ１（ＭＳＫ１，ｆ１）は、各ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，αに擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ，α〜を得る。例えばＫＧ１（ＭＳＫ１，ｆ１）は、νｉ，αの初期値をＫｉ，αとした後、νｉ，αのビット長がλビットに達するまでνｉ，α←ＰＲＧ（νｉ，α）の処理を繰り返し、λビットに達したνｉ，αを擬似乱数Ｋｉ，α〜とする。
ＫＧ１（ＭＳＫ１，ｆ１）は、暗号化アルゴリズムＥを用い、各ｉ∈［ｎ］およびα∈｛０，１｝について、擬似乱数Ｋｉ，α〜を共通鍵として要素Ｚｉ，αを暗号化した暗号文ｃｉ，α←Ｅ（Ｋｉ，α〜，Ｚｉ，α）を得、関数ｆ１に対する秘密鍵（個別秘密鍵）ｓｋｆ１←（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得て出力する。
【００１８】
暗号化アルゴリズムＥｎｃ１（ＭＳＫ１，ｍ１）：
Ｅｎｃ１（ＭＳＫ１，ｍ１）は、マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）およびメッセージｍ１∈｛０，１｝λを入力とし、以下の処理を行う。
まず、Ｅｎｃ１（ＭＳＫ１，ｍ１）は、ＭＳＫ１から｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝およびＲを取り出し、ｍ１とＲとの排他的論理和値ｘ∈｛０，１｝λを得る。
【数２】
2018112613.tif 000004
次にＥｎｃ１（ＭＳＫ１，ｍ１）は、排他的論理和値ｘのｉ∈［ｎ］ビット目の値をｘ［ｉ］として暗号文ＣＴ１←｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］を得て出力する。
【００１９】
復号アルゴリズムＤｅｃ１（ｓｋｆ１，ＣＴ１）：
Ｄｅｃ１（ｓｋｆ１，ＣＴ１）は、秘密鍵ｓｋｆ１＝（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）および暗号文ＣＴ１＝｛Ｋｉ｝ｉ∈［ｎ］を入力とし、以下の処理を行う。
Ｄｅｃ１（ｓｋｆ１，ＣＴ１）は、各ｉ∈［ｎ］についてＫｉに擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ〜を得る。ただし、擬似乱数生成アルゴリズムＰＲＧの適用の仕方は前述したＫＧ１（ＭＳＫ１，ｆ１）のものと同じである。例えば、例えばＤｅｃ１（ｓｋｆ１，ＣＴ１）は、νｉの初期値をＫｉとした後、νｉのビット長がλビットに達するまでνｉ←ＰＲＧ（νｉ）の処理を繰り返し、λビットに達したνｉを擬似乱数Ｋｉ〜とする。
Ｄｅｃ１（ｓｋｆ１，ＣＴ１）は、復号アルゴリズムＤを用い、擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，０を復号できるのであれば（Ｄ（Ｋｉ〜，ｃｉ，０）≠⊥）、擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，０を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，０）を得る。そうでなければ、擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，１を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，１）を得る。Ｄｅｃ１（ｓｋｆ１，ＣＴ１）は、この処理を各ｉ∈［ｎ］について行う。
Ｄｅｃ１（ｓｋｆ１，ＣＴ１）は、鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］について実行アルゴリズムＥｖａｌを実行し、復号値ｙ←Ｅｖａｌ（Ｃ〜，｛Ｌｉ｝ｉ∈［ｎ］）を得て出力する。
【００２０】
＜λ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ３＞
上述したＳＫＦＥ１（第１関数暗号）と1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を用い、λ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であって暗号文サイズが高々λ１／ｔ・φ＋ｐｏｌｙ（λ）である方式ＳＫＦＥ３＝（Ｓｅｔｕｐ３，ＫＧ３，Ｅｎｃ３，Ｄｅｃ３）を構成する方法を説明する。
まず、1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号から、λ-key unbounded-ciphertext完全簡素性秘密鍵関数型暗号ＳＫＦＥ２（第２関数暗号）で暗号文サイズが高々poly(λ,n)であるものを構成できることが知られている（例えば、非特許文献２等参照）。以下では、ＳＫＦＥ１とＳＫＦＥ２とを用い、以下のＳＫＦＥ３＝（Ｓｅｔｕｐ３，ＫＧ３，Ｅｎｃ３，Ｄｅｃ３）を構成する。
【００２１】
ただし、ＳＫＦＥ１＝（Ｓｅｔｕｐ１，ＫＧ１，Ｅｎｃ１，Ｄｅｃ１）はunbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号である。Ｓｅｔｕｐ１は、マスター秘密鍵ＭＳＫ１を得るＳＫＦＥ１のセットアップアルゴリズムであり、ＫＧ１は、関数ｆ１およびマスター秘密鍵ＭＳＫ１を入力として関数ｆ１に対する秘密鍵ｓｋｆ１を得るＳＫＦＥ１の鍵生成アルゴリズムであり、Ｅｎｃ１は、マスター秘密鍵ＭＳＫ１およびメッセージｍ１を入力とし、マスター秘密鍵ＭＳＫ１でメッセージｍ１を暗号化して暗号文ＣＴ１を得るＳＫＦＥ１の暗号化アルゴリズムであり、Ｄｅｃ１は、秘密鍵ｓｋｆ１および暗号文ＣＴ１を入力とし、秘密鍵ｓｋｆ１で暗号文ＣＴ１を復号するＳＫＦＥ１の復号アルゴリズムである。
第２関数暗号ＳＫＦＥ２＝（Ｓｅｔｕｐ２，ＫＧ２，Ｅｎｃ２，Ｄｅｃ２）は1-key unbounded-ciphertext 秘密鍵関数型暗号である。Ｓｅｔｕｐ２は、マスター秘密鍵ＭＳＫ２を得るＳＫＦＥ２のセットアップアルゴリズムであり、ＫＧ２は、関数ｆ２、マスター秘密鍵ＭＳＫ２、インデックスｊを入力として関数ｆ２に対する秘密鍵ｓｋｆ２を得るＳＫＦＥ２の鍵生成アルゴリズムであり、Ｅｎｃ２は、マスター秘密鍵ＭＳＫ２およびメッセージｍ２を入力とし、マスター秘密鍵ＭＳＫ２でメッセージｍ２を暗号化して暗号文ＣＴ２を得るＳＫＦＥ２の暗号化アルゴリズムであり、Ｄｅｃ２は、秘密鍵ｓｋｆ２および暗号文ＣＴ２を入力とし、秘密鍵ｓｋｆ２で暗号文ＣＴ２を復号するＳＫＦＥ２の復号アルゴリズムである。
⊥は無意味な情報（例えば、ランダムな情報や予め定められた情報）を表し、λが正整数であるセキュリティパラメータであり、ＰＲＧが入力情報に対応する擬似乱数を出力する擬似乱数生成アルゴリズムを表す。
【００２２】
セットアップアルゴリズムＳｅｔｕｐ３（１λ）：
Ｓｅｔｕｐ３は、セキュリティパラメータλを入力とし、Ｓｅｔｕｐ２を実行してマスター秘密鍵ＭＳＫ２←Ｓｅｔｕｐ２（１λ）を得て出力する。
【００２３】
鍵生成アルゴリズムＫＧ３（ＭＳＫ２，ｆ３，ｊ）：
ＫＧ３（ＭＳＫ２，ｆ３，ｊ）は、マスター秘密鍵ＭＳＫ２、関数ｆ３、およびインデックスｊを入力とし、以下の処理を行う。
ＫＧ３（ＭＳＫ２，ｆ３，ｊ）は、θ∈｛０，１｝λを選択し、θに擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数ｒθ←ＰＲＧ（θ）を得る。
ＫＧ３（ＭＳＫ２，ｆ３，ｊ）は、パラメータ（ｆ０，ｆ１，ｖ，ｊ，θ）が書き込まれている（設定されている）関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］を設定する。関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］は、マスター秘密鍵ＭＳＫ１およびα∈｛０，１｝を入力としてＭＳＫ１＝⊥ならばｖを出力し、そうでなければＫＧ１を実行して関数Ｃ［ｆα］に対する、擬似乱数ｒθでランダム化された秘密鍵ｓｋＣ←ＫＧ１（ＭＳＫ１，Ｃ［ｆα］；ｒθ）を得て秘密鍵ｓｋＣおよびインデックスｊを出力する。ただし、Ｃ［ｆ３］は関数ｆ３が書き込まれた（設定された）関数であり、パラメータ（ｍ０，ｍ１，γ）（ただし、γ∈｛０，１｝）を入力として関数ｆ３の関数値ｆ３（ｍγ）を出力する。
ＫＧ３（ＭＳＫ２，ｆ３，ｊ）は、ＫＧ２を実行して、関数Ｇ［ｆ３，⊥，⊥，ｊ，θ］に対する秘密鍵（個別秘密鍵）ｓｋＧ←ＫＧ２（ＭＳＫ２，Ｇ［ｆ３，⊥，⊥，ｊ，θ］，ｊ）を得て出力する。秘密鍵ｓｋＧは関数ｆ３に対応する秘密鍵ｓｋｆ３である。
【００２４】
暗号化アルゴリズムＥｎｃ３（ＭＳＫ２，ｍ３）：
Ｅｎｃ３（ＭＳＫ２，ｍ３）は、マスター秘密鍵ＭＳＫ２およびメッセージｍ３を入力とし、以下の処理を実行する。
Ｅｎｃ３（ＭＳＫ２，ｍ３）は、セキュリティパラメータλを入力とし、Ｓｅｔｕｐ１を実行してマスター秘密鍵ＭＳＫ１←Ｓｅｔｕｐ１（１λ）を得る。
Ｅｎｃ３（ＭＳＫ２，ｍ３）は、Ｅｎｃ１を実行し、マスター秘密鍵ＭＳＫ１でメッセージ（ｍ３，⊥，０）を暗号化して暗号文ＣＴ１←Ｅｎｃ１（ＭＳＫ１，（ｍ３，⊥，０））を得る。またＥｎｃ３（ＭＳＫ２，ｍ３）は、Ｅｎｃ２を実行し、マスター秘密鍵ＭＳＫ２でメッセージ（ＭＳＫ１，０）を暗号化して暗号文ＣＴ２←Ｅｎｃ２（ＭＳＫ２，（ＭＳＫ１，０））を得、暗号文ＣＴ３←（ＣＴ１，ＣＴ２）を得て出力する。
【００２５】
復号アルゴリズムＤｅｃ３（ｓｋＧ，ＣＴ３）：
Ｄｅｃ３（ｓｋＧ，ＣＴ３）は、秘密鍵ｓｋｆ３＝ｓｋＧおよび暗号文ＣＴ３＝（ＣＴ１，ＣＴ２）を入力とし、以下の処理を実行する。
Ｄｅｃ３（ｓｋＧ，ＣＴ３）は、Ｄｅｃ２を実行して秘密鍵ｓｋＧで暗号文ＣＴ２を復号することで秘密鍵ｓｋＣ←Ｄｅｃ２（ｓｋＧ，ＣＴ２）を得、Ｄｅｃ１を実行して秘密鍵ｓｋＣで暗号文ＣＴ１を復号することで復号値ｙ←Ｄｅｃ１（ｓｋＣ，ＣＴ１）を得て出力する。
【００２６】
＜q4q5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ６＞
q4-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であって暗号文サイズが高々λ１／ｔ・φ＋ｐｏｌｙ（λ）である第４関数型暗号ＳＫＦＥ４＝（Ｓｅｔｕｐ４，ＫＧ４，Ｅｎｃ４，Ｄｅｃ４）およびq5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号であって暗号文サイズが高々λ１／ｔ・φ＋ｐｏｌｙ（λ）である第５関数型暗号ＳＫＦＥ５＝（Ｓｅｔｕｐ５，ＫＧ５，Ｅｎｃ５，Ｄｅｃ５）を用い、q4q5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ６＝（Ｓｅｔｕｐ６，ＫＧ６，Ｅｎｃ６，Ｄｅｃ６）を構成（積構成）する方法を説明する。
【００２７】
ただし、λが正整数のセキュリティパラメータであり、ＳＫＦＥ４のメッセージ空間、関数空間、インデックス空間をそれぞれＭ４，Ｆ４，およびＩ４とし、ＳＫＦＥ５のメッセージ空間、関数空間、インデックス空間をそれぞれＭ５，Ｆ５，およびＩ５とする。つまり、｜Ｉ４｜＝ｑ４、｜Ｉ５｜＝ｑ５である。ＰＲＦを鍵空間が｛０，１｝λである擬似ランダム関数とする（参考文献４）。
ｑ４は正整数であり、ＳＫＦＥ４＝（Ｓｅｔｕｐ４，ＫＧ４，Ｅｎｃ４，Ｄｅｃ４）のＳｅｔｕｐ４は、マスター秘密鍵ＭＳＫ４を得る第４関数型暗号ＳＫＦＥ４のセットアップアルゴリズムである。ＫＧ４は、関数ｆ４、マスター秘密鍵ＭＳＫ４、およびインデックスιを入力として関数ｆ４に対する秘密鍵ｓｋｆ４を得るＳＫＦＥ４の鍵生成アルゴリズムである。Ｅｎｃ４は、マスター秘密鍵ＭＳＫ４およびメッセージｍ４を入力とし、マスター秘密鍵ＭＳＫ４でメッセージｍ４を暗号化して暗号文ＣＴ４を得るＳＫＦＥ４の暗号化アルゴリズムである。Ｄｅｃ４は、秘密鍵ｓｋｆ４および暗号文ＣＴ４を入力とし、秘密鍵ｓｋｆ４で暗号文ＣＴ４を復号するＳＫＦＥ４の復号アルゴリズムである。
ｑ５は正整数であり、ＳＫＦＥ５＝（Ｓｅｔｕｐ５，ＫＧ５，Ｅｎｃ５，Ｄｅｃ５）のＳｅｔｕｐ５は、マスター秘密鍵ＭＳＫ５を得る第５関数暗号ＳＫＦＥ５のセットアップアルゴリズムである。ＫＧ５は、関数ｆ５、マスター秘密鍵ＭＳＫ５、およびインデックスκを入力として関数ｆ５に対する秘密鍵ｓｋｆ５を得るＳＫＦＥ５の鍵生成アルゴリズムである。Ｅｎｃ５は、マスター秘密鍵ＭＳＫ５およびメッセージｍ５を入力とし、マスター秘密鍵ＭＳＫ５でメッセージｍ５を暗号化して暗号文ＣＴ５を得るＳＫＦＥ５の暗号化アルゴリズムである。Ｄｅｃ５は、秘密鍵ｓｋｆ５および暗号文ＣＴ５を入力とし、秘密鍵ｓｋｆ５で暗号文ＣＴ５を復号するＳＫＦＥ５の復号アルゴリズムである。
ＳＫＦＥ４およびＳＫＦＥ５には前述のＳＫＦＥ３を用いることができる。すなわち、Ｓｅｔｕｐ４およびＳｅｔｕｐ５としてＳｅｔｕｐ３を用い、ＫＧ４およびＫＧ５としてＫＧ３を用い、Ｅｎｃ４およびＥｎｃ５としてＥｎｃ３を用い、Ｄｅｃ４およびＤｅｃ５としてＤｅｃ３を用いることができる。
【００２８】
セットアップアルゴリズムＳｅｔｕｐ６（１λ）：
Ｓｅｔｕｐ６（１λ）は、セキュリティパラメータλを入力とし、Ｓｅｔｕｐ４を実行してマスター秘密鍵ＭＳＫ４←Ｓｅｔｕｐ４（１λ）を得、擬似ランダム関数ＰＲＦの鍵Ｓ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ６←（ＭＳＫ４，Ｓ）を得て出力する。
【００２９】
鍵生成アルゴリズムＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））：
ＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））は、マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）、関数ｆ６、およびインデックスι，κを入力とし、以下の処理を実行する。
ＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））は、鍵Ｓおよびインデックスιに擬似ランダム関数ＰＲＦを適用して擬似乱数ｒ５，ι←ＰＲＦ（Ｓ，ι）を得、Ｓｅｔｕｐ５を実行して擬似乱数ｒ５，ιでランダム化されたマスター秘密鍵ＭＳＫ５ι←Ｓｅｔｕｐ５（１λ；ｒ５，ι）を得る。
ＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））は、擬似ランダム関数の鍵Ｓι←｛０，１｝λを選択し、鍵Ｓιおよびマスター秘密鍵ＭＳＫ５ιが書き込まれた（設定された）関数ｅι［Ｓι，ＭＳＫ５ι］を設定する。ただし、関数ｅι［Ｓι，ＭＳＫ５ι］は、任意の（ｍ，ｍ〜，ｒ，ＣＴ〜）を入力として擬似乱数ｒι←ＰＲＦ（Ｓι，ｒ）を得る処理と、Ｅｎｃ５を実行してマスター秘密鍵ＭＳＫ５ιでｍを暗号化して擬似乱数ｒιでランダム化された暗号文ＣＴ５ι←Ｅｎｃ５（ＭＳＫ５ι，ｍ；ｒι）を出力する処理と、を行う関数である。
ＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））は、マスター秘密鍵ＭＳＫ４、関数ｅι［Ｓι，ＭＳＫ５ι］、およびインデックスιを入力としてＫＧ４を実行して秘密鍵ｓｋｅι←ＫＧ４（ＭＳＫ４，ｅι［Ｓι，ＭＳＫ５ι］，ι）を得る。また、ＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））は、マスター秘密鍵ＭＳＫ５ι、関数ｆ６を、およびインデックスκを入力としてＫＧ５を実行して、関数ｆ６に対応する秘密鍵ｓｋｆ６，ι←ＫＧ５（ＭＳＫ５ι，ｆ６，κ）を得る。ＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））は、秘密鍵ｓｋｆ６←（ｓｋｅι，ｓｋｆ６，ι）を得て出力する。
【００３０】
暗号化アルゴリズムＥｎｃ６（ＭＳＫ６，ｍ６）：
Ｅｎｃ６（ＭＳＫ６，ｍ６）は、マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）およびメッセージｍ６を入力とし、ｒ←｛０，１｝λをランダムに選択し、Ｅｎｃ４を実行してマスター秘密鍵ＭＳＫ４で（ｍ６，⊥，ｒ，⊥）を暗号化して暗号文ＣＴ４←Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を得て出力する。
【００３１】
復号アルゴリズムＤｅｃ６（ｓｋｆ６，ＣＴ４）：
Ｄｅｃ６（ｓｋｆ６，ＣＴ４）は、秘密鍵ｓｋｆ６＝（ｓｋｅι，ｓｋｆ６，ι）および暗号文ＣＴ４＝Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を入力とし、Ｄｅｃ４を実行して秘密鍵ｓｋｅιで暗号文ＣＴ４を復号して暗号文ＣＴ５ι←Ｄｅｃ４（ｓｋｅι，ＣＴ４）を得、Ｄｅｃ５を実行して秘密鍵ｓｋｆ６，ιで暗号文ＣＴ５ιを復号して復号値ｙ←Ｄｅｃ５（ｓｋｆ６，ι，ＣＴ５ι）を得て出力する。
【００３２】
＜λt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号＞
上記においてｑ４＝ｑ５＝λとすると、ＳＫＦＥ６はλ2-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号となる。得られたｑ４＝λ２のＳＫＦＥ６をＳＫＦＥ４として用い、ｑ５＝λのＳＫＦＥ５を用いて同様に構成すると新たなＳＫＦＥ６はλ3-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号となる。同様な積構成を繰り返し、ｑ４＝λｔ−１のＳＫＦＥ６をＳＫＦＥ４として用い、ｑ５＝λのＳＫＦＥ５を用いることで、自然数ｔについてλt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を構成できる。すなわち、ｑ４・ｑ５＝λｔを満たすｑ４およびｑ５について上記の積構成を適用すると、λt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を構成できる。
【００３３】
＜unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号＞
また、Ｓｅｔｕｐ４およびＳｅｔｕｐ５がＳｅｔｕｐ３であり、ＫＧ４およびＫＧ５がＫＧ３であり、Ｅｎｃ４およびＥｎｃ５がＥｎｃ３であり、Ｄｅｃ４およびＤｅｃ５がＤｅｃ３であり、ＳＫＦＥ３の構成に用いられたＳＫＦＥ１のＫＧ１およびＤｅｃ１で用いられる擬似乱数生成アルゴリズムＰＲＧが、quasi exponentailly-secure 一方向性関数を利用して構成されている場合、ｔ＝ｌｏｇｌｏｇλとすることができる。この場合、λtは任意の多項式より大きくなり、上述のように構成されるλt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号は、unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号となる。なお、quasi exponentailly-secure 一方向性関数は、楕円曲線上の離散対数問題を利用した一方向性関数である（例えば、森山大輔，西巻陵，岡本龍明,「公開鍵暗号の数理 (シリーズ応用数理２)」，２０１１年３月２５日，共立出版，Ｐ１２，Ｐ４０〜Ｐ４２（参考文献５）等参照）。
【００３４】
＜unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ７＞
また、quasi exponentailly-secure 一方向性関数を利用したＰＲＧを用いない場合であっても、以下のようにすればunbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ７＝（Ｓｅｔｕｐ７，ＫＧ７，Ｅｎｃ７，Ｄｅｃ７）を構成できる。
ただし、λが正整数のセキュリティパラメータであり、η＝ｌｏｇｌｏｇλであり（例えば、ηは正整数）、ｋ∈［η］である。なお、「ｌｏｇ」の底は２である。第６関数型暗号ＳＫＦＥ６ｋ＝（Ｓｅｔｕｐ６ｋ，ＫＧ６ｋ，Ｅｎｃ６ｋ，Ｄｅｃ６ｋ）はλk-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号である。これはｑ４ｑ５＝λｋの場合のＳＫＦＥ６＝（Ｓｅｔｕｐ６，ＫＧ６，Ｅｎｃ６，Ｄｅｃ６）である。ＳＫＦＥ６ｋのメッセージ空間、関数空間、インデックス空間をそれぞれＭ、Ｆ、および［λｋ］とする。Ｓｅｔｕｐ６ｋは、マスター秘密鍵ＭＳＫ６ｋを得るＳＫＦＥ６ｋのセットアップアルゴリズムである。ＫＧ６ｋは、関数ｆ６ｋ、マスター秘密鍵ＭＳＫ６ｋ、およびインデックスβｋを入力として関数ｆ６ｋに対する秘密鍵ｓｋｆ６，ｋを得る第６関数暗号ＳＫＦＥ６ｋの鍵生成アルゴリズムである。Ｅｎｃ６ｋは、マスター秘密鍵ＭＳＫ６ｋおよびメッセージｍ６を入力とし、マスター秘密鍵ＭＳＫ６ｋでメッセージｍ６を暗号化して暗号文ＣＴ６ｋを得るＳＫＦＥ６ｋの暗号化アルゴリズムである。Ｄｅｃ６ｋは、秘密鍵ｓｋｆ６，ｋおよび暗号文ＣＴ６ｋを入力とし、秘密鍵ｓｋｆ６，ｋで暗号文ＣＴ６をｋ復号するＳＫＦＥ６ｋの復号アルゴリズムである。
これを用いて構成されるＳＫＦＥ７＝（Ｓｅｔｕｐ７，ＫＧ７，Ｅｎｃ７，Ｄｅｃ７）のメッセージ空間、関数空間、インデックス空間は、それぞれＭ、Ｆ、および∪ｋ∈［η］｛（ｋ，ρ）｜ρ∈［λｋ］｝である。
【００３５】
セットアップアルゴリズムＳｅｔｕｐ７（１λ）：
Ｓｅｔｕｐ７（１λ）は、各ｋ∈［η］についてＳｅｔｕｐ６ｋを実行してマスター秘密鍵ＭＳＫ６ｋ←Ｓｅｔｕｐ６ｋ（１λ）を得、これらを用いてマスター秘密鍵ＭＳＫ７←（ＭＳＫ６１，…，ＭＳＫ６η）を得て出力する。
【００３６】
鍵生成アルゴリズムＫＧ７（ＭＳＫ７，ｆ７，（ｋ，ρ））：
ＫＧ７（ＭＳＫ７，ｆ７，（ｋ，ρ））は、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）、関数ｆ７、およびインデックス（ｋ，ρ）を入力とし、ＫＧ６ｋを実行して秘密鍵ｓｋｆ６，ｋ←ＫＧ６ｋ（ＭＳＫ６ｋ，ｆ７，ρ）を得、関数ｆ７に対する秘密鍵ｓｋｆ７←（ｋ，ｓｋｆ６，ｋ）を得て出力する。
【００３７】
暗号化アルゴリズムＥｎｃ７（ＭＳＫ７，ｍ７）：
Ｅｎｃ７（ＭＳＫ７，ｍ７）は、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）およびメッセージｍ７を入力とし、各ｋ∈［η］についてＥｎｃ６ｋを実行して、マスター秘密鍵ＭＳＫ６ｋでメッセージｍ７を暗号化した暗号文ＣＴ６ｋ←Ｅｎｃ６ｋ（ＭＳＫ６ｋ，ｍ７）を得る。Ｅｎｃ７（ＭＳＫ７，ｍ７）は、これらを用いて暗号文ＣＴ７←（ＣＴ６１，…，ＣＴ６η）を得て出力する。
【００３８】
復号アルゴリズムＤｅｃ７（ｓｋｆ７，ＣＴ７）：
Ｄｅｃ７（ｓｋｆ７，ＣＴ７）は、秘密鍵ｓｋｆ７＝（ｋ，ｓｋｆ６，ｋ）および暗号文ＣＴ７＝（ＭＳＫ６１，…，ＭＳＫ６η）を入力とし、Ｄｅｃ６ｋを実行して秘密鍵ｓｋｆ６，ｋで暗号文ＭＳＫ６ｋを復号して復号値ｙ←Ｄｅｃ６ｋ（ｓｋｆ６，ｋ，ＭＳＫ６ｋ）を得て出力する。
【００３９】
以上のように、unbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ１を構成でき、これと1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を用いることでλ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ３を構成できる。すなわち、1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号からλ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ３を構成できる。
またλ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ３からq4q5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ６を構成でき、これを用いることでλt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を構成できる。
また、λt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を用いることで、unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を構成できる。
つまり、1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号（1-key方式）から、unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号（unbounded-key方式）を構成できる。
【００４０】
＜識別不可能性難読化器＞
参考文献６（Nir Bitansky, Ryo Nishimaki, Alain Passel`egue, and Daniel Wichs, “From cryptomania to obfustopia through secret-key functional encryption,” IACR Cryptology ePrint Archive, 2016:558, 2016.）には、unbounded-key unbounded-ciphertext 秘密鍵関数型暗号と（標準的な）公開鍵暗号とを用いて、識別不可能性難読化器を構成できることが記載されている。上述のように、本形態では1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号から、unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号を構成できるため、1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号と（標準的な）公開鍵暗号とを用いて、識別不可能性難読化器も構成できる。
【００４１】
＜第１実施形態＞
次に、図面を用いて本発明の第１実施形態を説明する。
本形態は、前述した＜unbounded-key 1-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ１＞の具体例である（ＳＫＦＥ１＝（Ｓｅｔｕｐ１，ＫＧ１，Ｅｎｃ１，Ｄｅｃ１））。
【００４２】
＜構成＞
図１に例示するように、本形態の暗号システム１は、セットアップ装置１１、鍵生成装置１２、暗号化装置１３、および復号装置１４を有する。セットアップ装置１１は、例えば、メモリ１１１、通信部１１２、およびマスター鍵生成部１１３を有する。鍵生成装置１２は、例えば、メモリ１２１、通信部１２２、秘匿化部１２３、行列生成部１２４、擬似乱数生成部１２５、暗号化部１２６、および秘密鍵生成部１２７を有する。暗号化装置１３は、例えば、メモリ１３１、通信部１３２、排他的論理和部１３３、および暗号化部１３４を有する。復号装置１４は、例えば、メモリ１４１、通信部１４２、擬似乱数生成部１４３、復号部１４４、および実行部１４５を有する。
【００４３】
セットアップ装置１１、鍵生成装置１２、暗号化装置１３、および復号装置１４は、入力情報、演算過程で保存する必要がある情報、演算結果の情報をメモリ１１１，１２１，１３１，１４１にそれぞれ格納し、必要に応じて読み出して利用する。また、セットアップ装置１１、鍵生成装置１２、暗号化装置１３、および復号装置１４は、それぞれ通信部１１２，１２２，１３２，１４２によって情報の送受信を行う。各装置から送信された情報は、例えばネットワークを通じて他の装置に送信される。
【００４４】
セットアップ装置１１、鍵生成装置１２、暗号化装置１３、および復号装置１４のそれぞれは、例えば、通信装置、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）、およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００４５】
なお、図１では、セットアップ装置１１、鍵生成装置１２、暗号化装置１３、および復号装置１４を１個ずつ例示するが、これらの少なくとも一部の装置が複数個存在していてもよい。
【００４６】
＜処理＞
次に本形態の処理を説明する。
≪セットアップアルゴリズムＳｅｔｕｐ１（１λ）の実行処理≫
セットアップ装置１１のマスター鍵生成部１１３は、セキュリティパラメータλを入力とし、各ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，α←｛０，１｝ｗを選択し、Ｒ←｛０，１｝λを選択し、マスター秘密鍵ＭＳＫ１←（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を得て出力する。Ｋｉ，αおよびＲの選択は、例えば、ランダムに行われる。マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）はメモリ１１１に格納される。通信部１１２は、マスター秘密鍵ＭＳＫ１を鍵生成装置１２および暗号化装置１３に送信する。
【００４７】
≪鍵生成アルゴリズムＫＧ１（ＭＳＫ１，ｆ１）の実行処理≫
鍵生成装置１２の通信部１２２には、復号装置１４から送られた関数ｆ１およびセットアップ装置１１から送られたマスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）が入力される。関数ｆ１およびマスター秘密鍵ＭＳＫ１はメモリ１２１に格納される。
【００４８】
秘匿化部１２３は、関数ｆ１に対応する論理回路Ｃｆ１に対して秘匿化アルゴリズムＧａｒｂｌｅを実行して（Ｃ〜，｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）←Ｇａｒｂｌｅ（１λ，Ｃｆ１）を得てメモリ１２１に格納する。
【００４９】
行列生成部１２４は、Ｒおよび｛Ｌｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝を入力として、Ｒのｉ∈［ｎ］ビット目の値Ｒ［ｉ］をｉ行α列の要素Ｚｉ，αとする２×ｎ行列
【数３】
2018112613.tif 000005
を得てメモリ１２１に格納する。
【００５０】
擬似乱数生成部１２５は、各ｉ∈［ｎ］およびα∈｛０，１｝についてＫｉ，αに擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ，α〜を得る。例えば擬似乱数生成部１２５は、νｉ，αの初期値をＫｉ，αとした後、νｉ，αのビット長がλビットに達するまでνｉ，α←ＰＲＧ（νｉ，α）の処理を繰り返し、λビットに達したνｉ，αを擬似乱数Ｋｉ，α〜とする。擬似乱数Ｋｉ，α〜はメモリ１２１に格納される。
【００５１】
暗号化部１２６は、擬似乱数Ｋｉ，α〜、および２×ｎ行列（Ｚｉ，α）を入力とし、暗号化アルゴリズムＥを用い、各ｉ∈［ｎ］およびα∈｛０，１｝について、擬似乱数Ｋｉ，α〜を共通鍵として要素Ｚｉ，αを暗号化した暗号文ｃｉ，α←Ｅ（Ｋｉ，α〜，Ｚｉ，α）を得てメモリ１２１に格納する。
【００５２】
秘密鍵生成部１２７は、Ｃ〜および暗号文ｃｉ，αを入力とし、関数ｆ１に対する秘密鍵ｓｋｆ１←（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を得てメモリ１２１に格納する。通信部１２２は、秘密鍵ｓｋｆ１＝（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）を復号装置１４に送信する。
【００５３】
≪暗号化アルゴリズムＥｎｃ１（ＭＳＫ１，ｍ１）の実行処理≫
暗号化装置１３の通信部１３２は、マスター秘密鍵ＭＳＫ１＝（｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝，Ｒ）を受信してメモリ１３１に格納する。排他的論理和部１３３は、メッセージｍ１およびマスター秘密鍵ＭＳＫ１を入力とし、ＭＳＫ１から｛Ｋｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝およびＲを取り出し、ｍ１とＲとの排他的論理和値ｘ∈｛０，１｝λを得てメモリ１３１に格納する。
【００５４】
暗号化部１３４は、排他的論理和値ｘのｉ∈［ｎ］ビット目の値をｘ［ｉ］として暗号文ＣＴ１←｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］を得てメモリ１３１に格納する。通信部１３２は暗号文ＣＴ１を復号装置１４に送信する。
【００５５】
≪復号アルゴリズムＤｅｃ１（ｓｋｆ１，ＣＴ１）の実行処理≫
復号装置１４の通信部１４２には、秘密鍵ｓｋｆ１＝（Ｃ〜，｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝）および暗号文ＣＴ１＝｛Ｋｉ｝ｉ∈［ｎ］＝｛Ｋｉ，ｘ［ｉ］｝ｉ∈［ｎ］が入力される。秘密鍵ｓｋｆ１および暗号文ＣＴ１はメモリ１４１に格納される。
【００５６】
擬似乱数生成部１４３は、｛Ｋｉ｝ｉ∈［ｎ］を入力とし、各ｉ∈［ｎ］についてＫｉに擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数Ｋｉ〜を得てメモリ１４１に格納する。ただし、擬似乱数生成アルゴリズムＰＲＧの適用の仕方は前述した擬似乱数生成部１２５での擬似乱数生成アルゴリズムＰＲＧの適用の仕方と同じである。例えば、例えばＤｅｃ１（ｓｋｆ１，ＣＴ１）は、νｉの初期値をＫｉとした後、νｉのビット長がλビットに達するまでνｉ←ＰＲＧ（νｉ）の処理を繰り返し、λビットに達したνｉを擬似乱数Ｋｉ〜とする。
【００５７】
復号部１４４は、｛Ｋｉ〜｝ｉ∈［ｎ］および｛ｃｉ，α｝ｉ∈［ｎ］，α∈｛０，１｝を入力とし、各ｉ∈［ｎ］について、復号アルゴリズムＤを用い、擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，０を復号できるかを判定する。擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，０を復号できるのであれば（Ｄ（Ｋｉ〜，ｃｉ，０）≠⊥）、復号部１４４は、擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，０を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，０）を得、Ｌｉ＝Ｄ（Ｋｉ〜，ｃｉ，０）をメモリ１４１に格納する。そうでなければ（Ｄ（Ｋｉ〜，ｃｉ，０）＝⊥）、復号部１４４は、擬似乱数Ｋｉ〜を共通鍵として暗号文ｃｉ，１を復号してＬｉ←Ｄ（Ｋｉ〜，ｃｉ，１）を得、Ｌｉ＝Ｄ（Ｋｉ〜，ｃｉ，１）をメモリ１４１に格納する。
【００５８】
実行部１４５は、鍵情報Ｃ〜および秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］を入力とし、鍵情報Ｃ〜と秘匿化ラベル情報｛Ｌｉ｝ｉ∈［ｎ］について実行アルゴリズムＥｖａｌを実行し、復号値ｙ←Ｅｖａｌ（Ｃ〜，｛Ｌｉ｝ｉ∈［ｎ］）を得て出力する。
【００５９】
＜第２実施形態＞
次に、図面を用いて本発明の第２実施形態を説明する。
本形態は、前述した＜λ-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ３＞の具体例である。第１実施形態のＳＫＦＥ１＝（Ｓｅｔｕｐ１，ＫＧ１，Ｅｎｃ１，Ｄｅｃ１）と、1-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号から構成されるλ-key unbounded-ciphertext完全簡素性秘密鍵関数型暗号ＳＫＦＥ２（例えば、非特許文献２等参照）とを用い、ＳＫＦＥ３＝（Ｓｅｔｕｐ３，ＫＧ３，Ｅｎｃ３，Ｄｅｃ３）を構成する。以降、既に説明した事項については同じ参照番号を用いて説明を省略する。
【００６０】
＜構成＞
図２に例示するように、本形態の暗号システム２は、セットアップ装置２１、鍵生成装置２２、暗号化装置２３、および復号装置２４を有する。セットアップ装置２１は、例えば、メモリ１１１、通信部１１２、およびマスター鍵生成部２１３を有する。鍵生成装置２２は、例えば、メモリ１２１、通信部１２２、選択部２２３、擬似乱数生成部２２４、関数設定部２２５、および秘密鍵生成部２２６を有する。暗号化装置２３は、例えば、メモリ１３１、通信部１３２、セットアップ部２３３、および暗号化部２３４を有する。復号装置２４は、例えば、メモリ１４１、通信部１４２、秘密鍵復号部２４３、および復号部２４４を有する。
【００６１】
セットアップ装置２１、鍵生成装置２２、暗号化装置２３、および復号装置２４は、入力情報、演算過程で保存する必要がある情報、演算結果の情報をメモリ１１１，１２１，１３１，１４１にそれぞれ格納し、必要に応じて読み出して利用する。また、セットアップ装置２１、鍵生成装置２２、暗号化装置２３、および復号装置２４は、それぞれ通信部１１２，１２２，１３２，１４２によって情報の送受信を行う。セットアップ装置２１、鍵生成装置２２、暗号化装置２３、および復号装置２４のそれぞれは、例えば、前述のコンピュータが所定のプログラムを実行することで構成される装置である。なお、図２では、セットアップ装置２１、鍵生成装置２２、暗号化装置２３、および復号装置２４を１個ずつ例示するが、これらの少なくとも一部の装置が複数個存在していてもよい。
【００６２】
＜処理＞
次に本形態の処理を説明する。
≪セットアップアルゴリズムＳｅｔｕｐ３（１λ）の実行処理≫
セットアップ装置２１のマスター鍵生成部２１３は、セキュリティパラメータλを入力とし、Ｓｅｔｕｐ２を実行してマスター秘密鍵ＭＳＫ２←Ｓｅｔｕｐ２（１λ）を得てメモリ１１１に格納する。通信部１１２は、ＭＳＫ２を鍵生成装置２２および暗号化装置２３に送信する。
【００６３】
≪鍵生成アルゴリズムＫＧ３（ＭＳＫ２，ｆ３，ｊ）の実行処理≫
鍵生成装置２２の通信部１２２には、復号装置２４から送られた関数ｆ３およびインデックスｊ、ならびにセットアップ装置２１から送られたマスター秘密鍵ＭＳＫ２が入力される。関数ｆ３、インデックスｊ、およびマスター秘密鍵ＭＳＫ２は、メモリ１２１に格納される。
【００６４】
選択部２２３は、θ∈｛０，１｝λを選択して出力し、擬似乱数生成部２２４は、このθに擬似乱数生成アルゴリズムＰＲＧを適用して擬似乱数ｒθ←ＰＲＧ（θ）を得てメモリ１２１に格納する。θの選択は、例えばランダムに行われる。
【００６５】
関数設定部２２５は、ｊ，θ、関数ｆ３、任意の関数ｆ０，ｆ１、および任意値ｖを入力とし、パラメータ（ｆ０，ｆ１，ｖ，ｊ，θ）が書き込まれている（設定されている）前述した関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］を設定し、関数Ｇ［ｆ０，ｆ１，ｖ，ｊ，θ］をメモリ１２１に格納する。
【００６６】
秘密鍵生成部２２６は、マスター秘密鍵ＭＳＫ２、関数Ｇ［ｆ３，⊥，⊥，ｊ，θ］、およびインデックスｊを入力とし、ＫＧ２を実行して、関数Ｇ［ｆ３，⊥，⊥，ｊ，θ］に対する秘密鍵ｓｋＧ←ＫＧ２（ＭＳＫ２，Ｇ［ｆ３，⊥，⊥，ｊ，θ］，ｊ）を得てメモリ１２１に格納する。通信部１２２は、秘密鍵ｓｋｆ３＝ｓｋＧ＝ＫＧ２（ＭＳＫ２，Ｇ［ｆ３，⊥，⊥，ｊ，θ］，ｊ）を復号装置２４に送信する。
【００６７】
≪暗号化アルゴリズムＥｎｃ３（ＭＳＫ２，ｍ３）の実行処理≫
暗号化装置２３の通信部１３２にはマスター秘密鍵ＭＳＫ２が入力される。セットアップ部２３３は、セキュリティパラメータλを入力とし、Ｓｅｔｕｐ１を実行してマスター秘密鍵ＭＳＫ１←Ｓｅｔｕｐ１（１λ）を得てメモリ１３１に格納する。
【００６８】
暗号化部２３４は、メッセージｍ３およびマスター秘密鍵ＭＳＫ１を入力とし、Ｅｎｃ１を実行し、マスター秘密鍵ＭＳＫ１でメッセージ（ｍ３，⊥，０）を暗号化して暗号文ＣＴ１←Ｅｎｃ１（ＭＳＫ１，（ｍ３，⊥，０））を得てメモリ１３１に格納する。さらに暗号化部２３４は、マスター秘密鍵ＭＳＫ１およびＭＳＫ２を入力とし、Ｅｎｃ２を実行し、マスター秘密鍵ＭＳＫ２でメッセージ（ＭＳＫ１，０）を暗号化して暗号文ＣＴ２←Ｅｎｃ２（ＭＳＫ２，（ＭＳＫ１，０））を得てメモリ１３１に格納する。その後、暗号化部２３４は、暗号文ＣＴ３←（ＣＴ１，ＣＴ２）を得てメモリ１３１に格納する。通信部１３２は、暗号文ＣＴ３＝（ＣＴ１，ＣＴ２）を復号装置２４に送信する。
【００６９】
≪復号アルゴリズムＤｅｃ３（ｓｋＧ，ＣＴ３）の実行処理≫
復号装置２４の通信部１４２には、秘密鍵ｓｋｆ３＝ｓｋＧおよび暗号文ＣＴ３＝（ＣＴ１，ＣＴ２）が入力される。
【００７０】
秘密鍵復号部２４３は、秘密鍵ｓｋｆ３＝ｓｋＧおよびＣＴ３＝（ＣＴ１，ＣＴ２）を入力とし、暗号文ＣＴ３から暗号文ＣＴ２を取り出し、Ｄｅｃ２を実行して秘密鍵ｓｋＧで暗号文ＣＴ２を復号することで秘密鍵ｓｋＣ←Ｄｅｃ２（ｓｋＧ，ＣＴ２）を得てメモリ１４１に格納する。
【００７１】
復号部２４４は、秘密鍵ｓｋＣおよびＣＴ３＝（ＣＴ１，ＣＴ２）を入力とし、暗号文ＣＴ３から暗号文ＣＴ１を取り出し、Ｄｅｃ１を実行して秘密鍵ｓｋＣで暗号文ＣＴ１を復号することで復号値ｙ←Ｄｅｃ１（ｓｋＣ，ＣＴ１）を得て出力する。
【００７２】
＜第３実施形態＞
次に、図面を用いて本発明の第３実施形態を説明する。
本形態は、前述した＜q4q5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ６＞の具体例である。前述の第４関数型暗号ＳＫＦＥ４＝（Ｓｅｔｕｐ４，ＫＧ４，Ｅｎｃ４，Ｄｅｃ４）および第５関数型暗号ＳＫＦＥ５＝（Ｓｅｔｕｐ５，ＫＧ５，Ｅｎｃ５，Ｄｅｃ５）を用い、q4q5-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ６＝（Ｓｅｔｕｐ６，ＫＧ６，Ｅｎｃ６，Ｄｅｃ６）を構成する。なお、第４関数型暗号ＳＫＦＥ４および第５関数型暗号ＳＫＦＥ５には、第２実施形態のＫＦＥ３＝（Ｓｅｔｕ３，ＫＧ３，Ｅｎｃ３，Ｄｅｃ３）を利用できる。
【００７３】
＜構成＞
図３に例示するように、本形態の暗号システム３は、セットアップ装置３１、鍵生成装置３２、暗号化装置３３、および復号装置３４を有する。セットアップ装置３１は、例えば、メモリ１１１、通信部１１２、マスター鍵生成部３１３、擬似乱数生成部３１４、およびマスター鍵生成部３１５を有する。鍵生成装置３２は、例えば、メモリ１２１、通信部１２２、擬似乱数生成部３２３、鍵選択部３２４、関数設定部３２５、秘密鍵生成部３２６、およびセットアップ部３２７を有する。暗号化装置３３は、例えば、メモリ１３１、通信部１３２、選択部３３３、および暗号化部３３４を有する。復号装置３４は、例えば、メモリ１４１、通信部１４２、復号部３４３，３４４を有する。
【００７４】
セットアップ装置３１、鍵生成装置３２、暗号化装置３３、および復号装置３４は、入力情報、演算過程で保存する必要がある情報、演算結果の情報をメモリ１１１，１２１，１３１，１４１にそれぞれ格納し、必要に応じて読み出して利用する。また、セットアップ装置３１、鍵生成装置３２、暗号化装置３３、および復号装置３４は、それぞれ通信部１１２，１２２，１３２，１４２によって情報の送受信を行う。セットアップ装置３１、鍵生成装置３２、暗号化装置３３、および復号装置３４のそれぞれは、例えば、前述のコンピュータが所定のプログラムを実行することで構成される装置である。なお、図３では、セットアップ装置３１、鍵生成装置３２、暗号化装置３３、および復号装置３４を１個ずつ例示するが、これらの少なくとも一部の装置が複数個存在していてもよい。
【００７５】
＜処理＞
次に本形態の処理を説明する。
≪セットアップアルゴリズムＳｅｔｕｐ６（１λ）の実行処理≫
セットアップ装置３１のマスター鍵生成部３１３は、セキュリティパラメータλを入力とし、Ｓｅｔｕｐ４を実行してマスター秘密鍵ＭＳＫ４←Ｓｅｔｕｐ４（１λ）を得てメモリ１１１に格納する。
【００７６】
擬似乱数生成部３１４は、擬似ランダム関数ＰＲＦの鍵Ｓ←｛０，１｝λを選択し、マスター鍵生成部３１５は、マスター秘密鍵ＭＳＫ６←（ＭＳＫ４，Ｓ）を得てメモリ１１１に格納する。鍵Ｓの選択は例えばランダムに行われる。通信部１１２は、マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）を鍵生成装置３２および暗号化装置３３に送信する。
【００７７】
≪鍵生成アルゴリズムＫＧ６（ＭＳＫ６，ｆ６，（ι，κ））の実行処理≫
鍵生成装置３２の通信部１２２には、セットアップ装置３１から送信されたマスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）、ならびに復号装置３４から送信された関数ｆ６およびインデックス（ι，κ）が入力される。
【００７８】
擬似乱数生成部３２３は、鍵Ｓおよびインデックスιを入力とし、鍵Ｓおよびインデックスιに擬似ランダム関数ＰＲＦを適用して擬似乱数ｒ５，ι←ＰＲＦ（Ｓ，ι）を得てメモリ１２１に格納する。
【００７９】
セットアップ部３２７は、擬似乱数ｒ５，ιを入力とし、Ｓｅｔｕｐ５を実行して擬似乱数ｒ５，ιでランダム化されたマスター秘密鍵ＭＳＫ５ι←Ｓｅｔｕｐ５（１λ；ｒ５，ι）を得て、メモリ１２１に格納する。
【００８０】
鍵選択部３２４は、擬似ランダム関数の鍵Ｓι←｛０，１｝λを選択してメモリ１２１に格納する。鍵Ｓιは例えばランダムに選択される。関数設定部３２５は、ＳιおよびＭＳＫ５ιを入力とし、鍵Ｓιおよびマスター秘密鍵ＭＳＫ５ιが書き込まれた（設定された）前述の関数ｅι［Ｓι，ＭＳＫ５ι］を設定する。関数ｅι［Ｓι，ＭＳＫ５ι］はメモリ１２１に格納される。
【００８１】
秘密鍵生成部３２６は、マスター秘密鍵ＭＳＫ４、関数ｅι［Ｓι，ＭＳＫ５ι］、およびインデックスιを入力としてＫＧ４を実行して秘密鍵ｓｋｅι←ＫＧ４（ＭＳＫ４，ｅι［Ｓι，ＭＳＫ５ι］，ι）を得る。また秘密鍵生成部３２６は、マスター秘密鍵ＭＳＫ５ι、関数ｆ６を、およびインデックスκを入力としてＫＧ５を実行して、関数ｆ６に対応する秘密鍵ｓｋｆ６，ι←ＫＧ５（ＭＳＫ５ι，ｆ６，κ）を得る。秘密鍵生成部３２６は、関数ｆ６に対応する秘密鍵ｓｋｆ６←（ｓｋｅι，ｓｋｆ６，ι）を得てメモリ１２１に格納する。通信部１２２は、秘密鍵ｓｋｆ６を復号装置３４に送信する。
【００８２】
≪暗号化アルゴリズムＥｎｃ６（ＭＳＫ６，ｍ６）の実行処理≫
暗号化装置３３の通信部１３２には、マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）が入力される。選択部３３３は、ｒ←｛０，１｝λをランダムに選択してメモリ１３１に格納する。暗号化部３３４は、マスター秘密鍵ＭＳＫ６＝（ＭＳＫ４，Ｓ）、メッセージｍ６、およびｒを入力とし、Ｅｎｃ４を実行してマスター秘密鍵ＭＳＫ４で（ｍ６，⊥，ｒ，⊥）を暗号化して暗号文ＣＴ４←Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を得てメモリ１３１に格納する。通信部１３２は、暗号文ＣＴ４＝Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を復号装置３４に送信する。
【００８３】
≪復号アルゴリズムＤｅｃ６（ｓｋｆ６，ＣＴ４）の実行処理≫
復号装置３４の通信部１４２には、秘密鍵ｓｋｆ６および暗号文ＣＴ４が入力される。復号部３４３は、秘密鍵ｓｋｆ６＝（ｓｋｅι，ｓｋｆ６，ι）および暗号文ＣＴ４＝Ｅｎｃ４（ＭＳＫ４，（ｍ６，⊥，ｒ，⊥））を入力とし、秘密鍵ｓｋｆ６から秘密鍵ｓｋｅιを取り出し、Ｄｅｃ４を実行して秘密鍵ｓｋｅιで暗号文ＣＴ４を復号して暗号文ＣＴ５ι←Ｄｅｃ４（ｓｋｅι，ＣＴ４）を得てメモリ１２１に格納する。
【００８４】
復号部３４４は、秘密鍵ｓｋｆ６＝（ｓｋｅι，ｓｋｆ６，ι）および暗号文ＣＴ５ιを入力とし、秘密鍵ｓｋｆ６から秘密鍵ｓｋｆ６，ιを取り出し、Ｄｅｃ５を実行して秘密鍵ｓｋｆ６，ιで暗号文ＣＴ５ιを復号して復号値ｙ←Ｄｅｃ５（ｓｋｆ６，ι，ＣＴ５ι）を得て出力する。
【００８５】
［第３実施形態の変形例］
前述のように、第３実施形態の積構成を繰り返し、最終的にｑ４＝λｔ−１のＳＫＦＥ６をＳＫＦＥ４として用い、ｑ５＝λのＳＫＦＥ５を用いることで、自然数ｔについてλt-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ６’＝（Ｓｅｔｕｐ６’，ＫＧ６’，Ｅｎｃ６’，Ｄｅｃ６’）を構成できる。また、第１実施形態で用いられている擬似乱数生成アルゴリズムＰＲＧが、quasi exponentailly-secure 一方向性関数を利用して構成されている場合、ｔ＝ｌｏｇｌｏｇλとすることができ、この場合には、unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号となる。
【００８６】
＜第４実施形態＞
次に、図面を用いて本発明の第４実施形態を説明する。
本形態は、前述した＜unbounded-key unbounded-ciphertext 完全簡素性秘密鍵関数型暗号ＳＫＦＥ７＞の具体例である。以下、本形態のＳＫＦＥ７＝（Ｓｅｔｕｐ７，ＫＧ７，Ｅｎｃ７，Ｄｅｃ７）について説明する。
【００８７】
＜構成＞
図４に例示するように、本形態の暗号システム４は、セットアップ装置４１、鍵生成装置４２、暗号化装置４３、および復号装置４４を有する。セットアップ装置４１は、例えば、メモリ１１１、通信部１１２、およびマスター鍵生成部４１３，４１４、を有する。鍵生成装置４２は、例えば、メモリ１２１、通信部１２２、および秘密鍵生成部４２４，４２４を有する。暗号化装置４３は、例えば、メモリ１３１、通信部１３２、および暗号化部４３３、４３４を有する。復号装置４４は、例えば、メモリ１４１、通信部１４２、復号部４４４を有する。
【００８８】
セットアップ装置４１、鍵生成装置４２、暗号化装置４３、および復号装置４４は、入力情報、演算過程で保存する必要がある情報、演算結果の情報をメモリ１１１，１２１，１３１，１４１にそれぞれ格納し、必要に応じて読み出して利用する。また、セットアップ装置４１、鍵生成装置４２、暗号化装置４３、および復号装置４４は、それぞれ通信部１１２，１２２，１３２，１４２によって情報の送受信を行う。セットアップ装置４１、鍵生成装置４２、暗号化装置４３、および復号装置４４のそれぞれは、例えば、前述のコンピュータが所定のプログラムを実行することで構成される装置である。なお、図４では、セットアップ装置４１、鍵生成装置４２、暗号化装置４３、および復号装置４４を１個ずつ例示するが、これらの少なくとも一部の装置が複数個存在していてもよい。
【００８９】
＜処理＞
次に本形態の処理を説明する。
≪セットアップアルゴリズムＳｅｔｕｐ７（１λ）の実行処理≫
セットアップ装置４１のマスター鍵生成部４１３は、セキュリティパラメータλを入力とし、各ｋ∈［η］についてＳｅｔｕｐ６ｋを実行してマスター秘密鍵ＭＳＫ６ｋ←Ｓｅｔｕｐ６ｋ（１λ）を得てメモリ１１１に格納する。マスター鍵生成部４１４は、これらＭＳＫ６ｋを用いてマスター秘密鍵ＭＳＫ７←（ＭＳＫ６１，…，ＭＳＫ６η）を得てメモリ１１１に格納する。通信部１１２は、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）を、鍵生成装置４２および暗号化装置４３に送信する。
【００９０】
≪鍵生成アルゴリズムＫＧ７（ＭＳＫ７，ｆ７，（ｋ，ρ））の実行処理≫
鍵生成装置４２の通信部１２２には、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）、ならびに復号装置４４から送信された関数ｆ７およびインデックス（ｋ，ρ）が入力される。
【００９１】
秘密鍵生成部４２３は、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）、関数ｆ７、およびインデックス（ｋ，ρ）を入力とし、ＫＧ６ｋを実行して秘密鍵ｓｋｆ６，ｋ←ＫＧ６ｋ（ＭＳＫ６ｋ，ｆ７，ρ）を得てメモリ１２１に格納する。秘密鍵生成部４２４は、ｋおよびｓｋｆ６，ｋを入力とし、関数ｆ７に対する秘密鍵ｓｋｆ７←（ｋ，ｓｋｆ６，ｋ）を得てメモリ１２１に格納する。通信部１２２は、秘密鍵ｓｋｆ７を復号装置４４に送信する。
【００９２】
≪暗号化アルゴリズムＥｎｃ７（ＭＳＫ７，ｍ７）の実行処理≫
暗号化装置４３の通信部１３２には、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）が入力される。暗号化部４３３は、マスター秘密鍵ＭＳＫ７＝（ＭＳＫ６１，…，ＭＳＫ６η）およびメッセージｍ７を入力とし、各ｋ∈［η］についてＥｎｃ６ｋを実行して、マスター秘密鍵ＭＳＫ６ｋでメッセージｍ７を暗号化した暗号文ＣＴ６ｋ←Ｅｎｃ６ｋ（ＭＳＫ６ｋ，ｍ７）を得てメモリ１３１に格納する。暗号化部４３４は、これらの暗号文ＣＴ６ｋ＝Ｅｎｃ６ｋ（ＭＳＫ６ｋ，ｍ７）を用いて暗号文ＣＴ７←（ＣＴ６１，…，ＣＴ６η）を得てメモリ１３１に格納する。通信部１３２は、暗号文ＣＴ７＝（ＣＴ６１，…，ＣＴ６η）を復号装置４４に送信する。
【００９３】
≪復号アルゴリズムＤｅｃ７（ｓｋｆ７，ＣＴ７）の実行処理≫
復号装置４４の通信部１４２には、秘密鍵ｓｋｆ７＝（ｋ，ｓｋｆ６，ｋ）および暗号文ＣＴ７＝（ＣＴ６１，…，ＣＴ６η）が入力される。復号部４４３は、秘密鍵ｓｋｆ７＝（ｋ，ｓｋｆ６，ｋ）および暗号文ＣＴ７＝（ＣＴ６１，…，ＣＴ６η）を入力とし、Ｄｅｃ６ｋを実行し、秘密鍵ｓｋｆ７から取り出した秘密鍵ｓｋｆ６，ｋで、秘密鍵ｓｋｆ７から取り出したｋに対応するＭＳＫ６ｋを復号して復号値ｙ←Ｄｅｃ６ｋ（ｓｋｆ６，ｋ，ＣＴ６ｋ）を得て出力する。
【００９４】
＜第５実施形態＞
次に、図面を用いて本発明の第５実施形態を説明する。
本形態は、unbounded-key unbounded-ciphertext 秘密鍵関数型暗号と（標準的な）公開鍵暗号とを用い、前述した＜識別不可能性難読化器＞を構成する例を示す。unbounded-key unbounded-ciphertext 秘密鍵関数型暗号としては、第３実施形態の変形例で示したＳＫＦＥ６’を用いてもよいし、第４実施形態で示したＳＫＦＥ７＝（Ｓｅｔｕｐ７，ＫＧ７，Ｅｎｃ７，Ｄｅｃ７）を用いてもよい。以下では、unbounded-key unbounded-ciphertext 秘密鍵関数型暗号としてＳＫＦＥ７を用いる例を説明する。
【００９５】
＜構成＞
図５に例示するように、本形態の暗号システム５は、セットアップ装置４１、鍵生成装置４２、難読化装置５３、および実行装置５４を有する。難読化装置５３は、メモリ４３１、暗号化装置４３、難読化部５３２、および通信部５３３を有する。実行装置５４は、メモリ５４１、復号装置４４、実行部５４２、および通信部５４３を有する。
【００９６】
難読化装置５３および実行装置５４は、入力情報、演算過程で保存する必要がある情報、演算結果の情報をメモリ５３１および５４１にそれぞれ格納し、必要に応じて読み出して利用する。また、難読化装置５３および実行装置５４は、それぞれ通信部５３３および５４３によって情報の送受信を行う。各装置から送信された情報は、例えばネットワークを通じて他の装置に送信される。難読化装置５３および実行装置５４は、それぞれ前述のコンピュータが所定のプログラムを実行することで構成される装置である。図５では、１個の難読化装置５３および実行装置５４を例示するが、これらの少なくとも一方が複数個存在してもよい。
【００９７】
＜処理＞
次に本形態の処理を説明する。
≪セットアップアルゴリズムＳｅｔｕｐ７（１λ）の実行処理≫
本形態のＳｅｔｕｐ７（１λ）の実行処理は、第４実施形態のものと同じである。
【００９８】
≪鍵生成アルゴリズムＫＧ７（ＭＳＫ７，ｆ７，（ｋ，ρ））の実行処理≫
本形態のＫＧ７（ＭＳＫ７，ｆ７，（ｋ，ρ））は、第４実施形態のものと同じである。
【００９９】
≪プログラムの難読化の実行処理≫
難読化装置５３の難読化部５３２は、難読化対象のプログラムｐｒｏを入力とし、暗号化アルゴリズムＥｎｃ７（ＭＳＫ７，ｍ７）を実行する暗号化装置４３を用い、参考文献６、参考文献７（Prabhanjan Ananth and Abhishek Jain, “Indistinguishability obfuscation from compact functional encryption,” In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 308-326. Springer, Heidelberg, August 2015.）、参考文献８（Nir Bitansky and Vinod Vaikuntanathan, “Indistinguishability obfuscation from functional encryption,” In Guruswami [Gur15], pages 171-190.）などに記載された識別不可能性難読化によってプログラムｐｒｏを難読化し、難読化プログラムｉＯ（ｐｒｏ）を得てメモリ５３１に格納する。通信部５３３は、難読化プログラムｉＯ（ｐｒｏ）を実行装置５４に送信する。
【０１００】
≪難読化プログラムの実行処理≫
実行装置５４の通信部５４３には難読化プログラムｉＯ（ｐｒｏ）が入力され、これはメモリ５４１に格納される。実行部５４２は、難読化プログラムｉＯ（ｐｒｏ）を入力とし、復号アルゴリズムＤｅｃ７（ｓｋｆ７，ＣＴ７）を実行する復号装置４４を用い、参考文献６，７，８などに記載された難読化プログラムｉＯ（ｐｒｏ）の実行処理を行い、実行結果を得て出力する。
【０１０１】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。これらの装置の一部からなる組み合わせが、同一の装置であってもよい。例えば、難読化装置５３が、セットアップアルゴリズムＳｅｔｕｐ７（１λ）および鍵生成アルゴリズムＫＧ７（ＭＳＫ７，ｆ７，（ｋ，ρ））を実行してもよい。この場合には、難読化装置５３から実行装置５４に送られる難読化プログラムｉＯ（ｐｒｏ）に秘密鍵ｓｋｆ７が含まれる。また、実行部５４２が難読化プログラムｉＯ（ｐｒｏ）と入力値ｘとを入力として、入力値ｘに対する難読化プログラムｉＯ（ｐｒｏ）の実行処理を行ってもよい。
【０１０２】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０３】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１０４】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１０６】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１０７】
１〜５  暗号システム
【図１】
2018112613.tif 000009
【図２】
2018112613.tif 000010
【図３】
2018112613.tif 000011
【図４】
2018112613.tif 000012
【図５】
2018112613.tif 000013