(57)【特許請求の範囲】
【請求項１】
鍵発行装置と，暗号化装置と，復号装置とを含み，格子問題に基づく階層型内積暗号システムであって，
κをセキュリティパラメータ，dを階層の最大の深さ，μを属性ベクトルの長さ，Lを平文のビット長，n，q，mをそれぞれ格子用のパラメータ，σ1，…，σdを鍵発行用のパラメータ，DΧをZq上の分布，b，k=┌logb q┐，m’=nkをそれぞれサイズ用のパラメータ，g=(1，b，…，bk-1)∈Zqk，gg=gg(x)∈Zq[x]をGF(qn)=Zq[x]/<gg>を定義するモニック既約多項式とし，自然数nについて{1，…，n}を[n]で表し，行列A∈Zqn×mについて格子を
Λq⊥(A)={z∈Zm:z≡ATs (mod q)となるs∈Zqnが存在する}
とし，
セットアップアルゴリズムSetup(1κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)：
1. (A，T┬)←GenTrap(1κ，q，n，m)，
2. δ∈[d]およびi∈[μ]について，Aδ，i←Zqn×m’をランダムに選び，
3. U←Zqn×Lをランダムに選ぶ
ことによって，予め共通パラメータpp=((κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)，A，{Aδ，i}，U)とマスター秘密鍵msk=(T┬，pp)が与えられているとして，
鍵発行装置は，
鍵生成アルゴリズムGen(pp，msk，(v^1，…，v^j))：(v^1，…，v^j)を鍵属性ベクトル，1≦j≦dとし，δ∈[j]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μ，Cv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’，F(v^1，…，v^j)=[A|Cv^1|…|Cv^j]∈Zqn×(m+jm’)として，T(v^1，…，v^j)←DelgBasis(T┬，F(v^1，…，v^j)，σj)，を実行し，秘密鍵dk(v^1，…，v^j)=T(v^1，…，v^j)を出力する鍵生成部
を含み，
暗号化装置は，
暗号化アルゴリズムEnc(pp，(w^1，…，w^h)，m∈{0，1}L)：(w^1，…，w^h)を暗号属性ベクトル，Inをｎ行ｎ列の単位行列，(×)をクロネッカー積とし，δ∈[h]について，w^δ=(wwδ，1，…，wwδ，μ)∈GF(qn)μ，G←In(×)(1，b，…，bk-1)として，
s←Zqnをランダムに選び，e←DΧmとf←DΧLをランダムに選ぶ選択部と，
c0←ATs+eを計算する第１暗号要素計算部と，
δ∈[h]とi∈[μ]について，Rδ，i←{-1，+1}m×m’をランダムに選び，cδ，i←(Aδ，i+H(wwδ，i)・G)Ts+Rδ，iTe∈Zqm’を計算する第２暗号要素計算部と，
c’←UTs+f+└q/2┘mを計算する第３暗号要素計算部と，
を含み，ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)を暗号文として出力する暗号文生成部と，
を含み，
復号装置は，
復号アルゴリズムDec(pp，dk(v^1，…，v^j)，ct)：
秘密鍵dk(v^1，…，v^j)=T(v^1，…，v^j)と暗号文ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)から，
δ∈[j]についてcv^δ←Σi=1μHg(vvδ，i)・cδ，iを計算する第１計算部と，
c←[c0|cv^1|…|cv^j]として，s←Invert(F(v^1，…，v^j)，T(v^1，…，v^j)，c)を計算する第２計算部と，
d←c’-UTsを計算する第３計算部と，
を含み，(2/q)dの各要素を一番近い整数に丸め，各々偶奇を0/1と対応させた結果，得られたベクトルを復号された平文m∈{0，1}Lとして出力する復号部と
を含む階層型内積暗号システム。
ただし，
GenTrap(1κ，q，n，m)：
行列A∈Zqn×m，Λq⊥(A)の基底Tの組(A，T)∈Zqn×m×Zm×mを出力するアルゴリズムであり，
Invert(A，T，c)：
TがΛq⊥(A)の基底であるときc=ATs+eとなるs∈Zqnを出力するアルゴリズムであり，
Hgを，Hg:GF(qn)→Zqnk×nk，Hg(aa)=Dg(H(aa))∈Bnk×nk⊆Zqnk×nkと定義し，
正整数b≧2について，B={0，1，…，b-1}⊆Zq，g=(1，b，…，bk-1)∈Zqk，q≦bkが成立しているとして，a∈Zqについて，dg(a)=(a1，…，ak)T∈Bkを，a=Σi=1kai・bi-1となるような関数として定義し，
Dgを，Dg:Zq→Bk×k，a → [dg(a)dg(ba)…dg(bk-1a)]∈Bk×kと定義し，
行列A={ai,j}∈Zqn×mについてDgの定義域を拡張したものを
【数３】
0005730805.tif 000004
と定義し，
ηを，η：GF(qn)→Zqn，aa=a0+a1X+…+an-1Xn-1 → (a0，…，an-1)Tと定義し，
Hを，H:GF(qn)→Zqn×n，aa=a0+a1X+…+an-1Xn-1 → [η(aa)η(aX)…η(aXn-1)]と定義している。
【請求項２】
請求項１に記載の階層型内積暗号システムにおいて，
復号装置は，
鍵生成アルゴリズムDelg(pp，dk(v^1，…，v^j)，(v^j+1，…，v^s))：
dk(v^1，…，v^j)=T(v^1，…，v^j)，δ∈[s]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μとして，
δ∈[s]についてCv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’とし，F(v^1，…，v^j，v^j+1，…，v^s)=[A|Cv^1|…|Cv^s]∈Zqn×(m+sm’)として，T(v^1，…，v^j，v^j+1，…，v^s)←DelgBasis(T(v^1，…，v^j)，F(v^1，…，v^j)，σs)を実行し，dk(v^1，…，v^s)=T(v^1，…，v^s)を出力する鍵生成部
をさらに含むことを特徴とする階層型内積暗号システム。
ただし，
ExtBasis(T，A^=[A|C])：
TがΛq⊥(A)の基底であるとき，Λq⊥(A^)の基底T’を出力するアルゴリズムであり，
RandBasis(S，s)：
Sが格子Λq⊥(A)の基底であるとき，格子Λq⊥(A)のランダムな基底S’を出力するアルゴリズムであり，
DelgBasis(T，A^=[A|C]，s)：
TがΛq⊥(A)の基底であるとき，A^に対応する行列T’を出力するアルゴリズムであり，S←ExtBasis(T，A^)，T’←RandBasis(S，s)で与えられる。
【請求項３】
鍵発行装置と，暗号化装置と，復号装置とを含み，格子問題に基づく階層型内積暗号システムにおける階層型内積暗号方法であって，
κをセキュリティパラメータ，dを階層の最大の深さ，μを属性ベクトルの長さ，Lを平文のビット長，n，q，mをそれぞれ格子用のパラメータ，σ1，…，σdを鍵発行用のパラメータ，DΧをZq上の分布，b，k=┌logb q┐，m’=nkをそれぞれサイズ用のパラメータ，g=(1，b，…，bk-1)∈Zqk，gg=gg(x)∈Zq[x]をGF(qn)=Zq[x]/<gg>を定義するモニック既約多項式とし，自然数nについて{1，…，n}を[n]で表し，行列A∈Zqn×mについて格子を
Λq⊥(A)={z∈Zm:z≡ATs (mod q)となるs∈Zqnが存在する}
とし，
セットアップアルゴリズムSetup(1κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)：
1. (A，T┬)←GenTrap(1κ，q，n，m)，
2. δ∈[d]およびi∈[μ]について，Aδ，i←Zqn×m’をランダムに選び，
3. U←Zqn×Lをランダムに選ぶ
ことによって，予め共通パラメータpp=((κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)，A，{Aδ，i}，U)とマスター秘密鍵msk=(T┬，pp)が与えられているとして，
鍵発行装置の鍵生成部が，
鍵生成アルゴリズムGen(pp，msk，(v^1，…，v^j))：(v^1，…，v^j)を鍵属性ベクトル，1≦j≦dとし，δ∈[j]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μ，Cv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’，F(v^1，…，v^j)=[A|Cv^1|…|Cv^j]∈Zqn×(m+jm’)として，T(v^1，…，v^j)←DelgBasis(T┬，F(v^1，…，v^j)，σj)，を実行し，秘密鍵dk(v^1，…，v^j)=T(v^1，…，v^j)を出力する鍵生成ステップと，
暗号化装置において，
暗号化アルゴリズムEnc(pp，(w^1，…，w^h)，m∈{0，1}L)：(w^1，…，w^h)を暗号属性ベクトル，Inをｎ行ｎ列の単位行列，(×)をクロネッカー積とし，δ∈[h]について，w^δ=(wwδ，1，…，wwδ，μ)∈GF(qn)μ，G←In(×)(1，b，…，bk-1)として，
選択部が，s←Zqnをランダムに選び，e←DΧmとf←DΧLをランダムに選ぶ選択ステップと，
第１暗号要素計算部が，c0←ATs+eを計算する第１暗号要素計算ステップと，
第２暗号要素計算部が，δ∈[h]とi∈[μ]について，Rδ，i←{-1，+1}m×m’をランダムに選び，cδ，i←(Aδ，i+H(wwδ，i)・G)Ts+Rδ，iTe∈Zqm’を計算する第２暗号要素計算ステップと，
第３暗号要素計算部が，c’←UTs+f+└q/2┘mを計算する第３暗号要素計算ステップと，
を有し，暗号文生成部が，ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)を暗号文として出力する暗号文生成ステップと，
復号装置において，
復号アルゴリズムDec(pp，dk(v^1，…，v^j)，ct)：
秘密鍵dk(v^1，…，v^j)=T(v^1，…，v^j)と暗号文ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)から，
第１計算部が，δ∈[j]についてcv^δ←Σi=1μHg(vvδ，i)・cδ，iを計算する第１計算ステップと，
第２計算部が，c←[c0|cv^1|…|cv^j]として，s←Invert(F(v^1，…，v^j)，T(v^1，…，v^j)，c)を計算する第２計算ステップと，
第３計算部が，d←c’-UTsを計算する第３計算ステップと，
を有し，復号部が，(2/q)dの各要素を一番近い整数に丸め，各々偶奇を0/1と対応させた結果，得られたベクトルを復号された平文m∈{0，1}Lとして出力する復号ステップと
を有する階層型内積暗号方法。
ただし，
GenTrap(1κ，q，n，m)：
行列A∈Zqn×m，Λq⊥(A)の基底Tの組(A，T)∈Zqn×m×Zm×mを出力するアルゴリズムであり，
Invert(A，T，c)：
TがΛq⊥(A)の基底であるときc=ATs+eとなるs∈Zqnを出力するアルゴリズムであり，
Hgを，Hg:GF(qn)→Zqnk×nk，Hg(aa)=Dg(H(aa))∈Bnk×nk⊆Zqnk×nkと定義し，
正整数b≧2について，B={0，1，…，b-1}⊆Zq，g=(1，b，…，bk-1)∈Zqk，q≦bkが成立しているとして，a∈Zqについて，dg(a)=(a1，…，ak)T∈Bkを，a=Σi=1kai・bi-1となるような関数として定義し，
Dgを，Dg:Zq→Bk×k，a → [dg(a)dg(ba)…dg(bk-1a)]∈Bk×kと定義し，
行列A={ai,j}∈Zqn×mについてDgの定義域を拡張したものを
【数４】
0005730805.tif 000005
と定義し，
ηを，η：GF(qn)→Zqn，aa=a0+a1X+…+an-1Xn-1 → (a0，…，an-1)Tと定義し，
Hを，H:GF(qn)→Zqn×n，aa=a0+a1X+…+an-1Xn-1 → [η(aa)η(aX)…η(aXn-1)]と定義している。
【請求項４】
請求項３に記載の階層型内積暗号方法において，
復号装置において，
鍵生成アルゴリズムDelg(pp，dk(v^1，…，v^j)，(v^j+1，…，v^s))：
dk(v^1，…，v^j)=T(v^1，…，v^j)，δ∈[s]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μとして，
鍵生成部が，δ∈[s]についてCv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’とし，F(v^1，…，v^j，v^j+1，…，v^s)=[A|Cv^1|…|Cv^s]∈Zqn×(m+sm’)として，T(v^1，…，v^j，v^j+1，…，v^s)←DelgBasis(T(v^1，…，v^j)，F(v^1，…，v^j)，σs)を実行し，dk(v^1，…，v^s)=T(v^1，…，v^s)を出力する鍵生成ステップ
をさらに有することを特徴とする階層型内積暗号方法。
ただし，
ExtBasis(T，A^=[A|C])：
TがΛq⊥(A)の基底であるとき，Λq⊥(A^)の基底T’を出力するアルゴリズムであり，
RandBasis(S，s)：
Sが格子Λq⊥(A)の基底であるとき，格子Λq⊥(A)のランダムな基底S’を出力するアルゴリズムであり，
DelgBasis(T，A^=[A|C]，s)：
TがΛq⊥(A)の基底であるとき，A^に対応する行列T’を出力するアルゴリズムであり，S←ExtBasis(T，A^)，T’←RandBasis(S，s)で与えられる。
【請求項５】
請求項１または請求項２に記載の階層型内積暗号システムに含まれる暗号化装置。
【請求項６】
請求項１または請求項２に記載の階層型内積暗号システムに含まれる復号装置。
【請求項７】
請求項１または請求項２に記載の階層型内積暗号システムに含まれる鍵発行装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，格子問題に基づく階層型内積暗号技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式では，或る公開鍵で暗号化された暗号文を復号できるのは，対応する秘密鍵を有する者にのみ限られる。例えば，ユーザ装置hからユーザ装置iに平文mを送信する場合，ユーザ装置hはユーザ装置iの暗号化鍵ekiを用いて，暗号文ciを生成し，ユーザ装置iに暗号文ciを送信する。暗号化鍵ekiに対応する復号鍵dkiを持つユーザ装置のみがこの暗号文ciを復号できる。
【０００３】
IDベース暗号では鍵生成局とユーザ装置が分離される。セットアップ時に鍵生成局は(mpk，msk)を生成する。ユーザ装置は各々が一意のidを持っており，鍵生成局が各ユーザに対して秘密鍵dkidを発行する。IDベース暗号では，或るidで暗号化された暗号文を復号できるのは，秘密鍵dkidを持つユーザ装置だけである（ただし，鍵生成局も秘密鍵dkidを持てる点に注意のこと）。
【０００４】
ユーザ（装置）と暗号の組み合わせをより多様にするため，内積暗号が提案された。セットアップ時に鍵生成局は(mpk，msk)を生成する。ユーザ装置は各々が鍵属性ベクトルv^∈Rμを持っている。鍵生成局は各ユーザ装置に対してdkv^を発行する。暗号化の際には，暗号属性ベクトルw^∈Rμを用いて暗号化を行う。内積暗号では，或るw^で暗号化された暗号文を復号できるのは，内積w^Tv^=0となるdkv^を持つユーザ装置だけである。
【０００５】
内積暗号は非特許文献１で初めて提案された。それ以降，楕円離散対数問題に基づいて様々な内積暗号やその変種が提案されている。格子問題に基づく内積暗号として，非特許文献２がある。
【０００６】
また，内積暗号を階層化したものとして，階層型内積暗号がある。これは非特許文献３で初めて提案された。階層の深さを最大でdとする(d=1のとき内積暗号に一致する)。セットアップ時に鍵生成局は(mpk，msk=dk┬)を生成する。ユーザ装置は各々が鍵属性ベクトル(v^1，…，v^j)∈(Rμ)≦d=Rμ∪(Rμ)2∪(Rμ)3∪…∪(Rμ)d(1≦j≦d)を持っている。鍵生成局は各ユーザ装置に対してdk(v^1，…，v^j)を発行する。階層型内積暗号では，鍵生成機能の委譲が行える。すなわち鍵dk(v^1，…，v^j)を持つユーザ装置は，任意のv^j+1，…，v^sについて鍵dk(v^1，…，v^j，v^j+1，…，v^s)を生成できる。暗号化の際には，暗号属性ベクトル(w^1，…，w^h)∈(Rμ)≦dを用いて暗号化を行う。階層型内積暗号では，鍵属性ベクトルを(v^1，…，v^j)，暗号属性ベクトル(w^1，…，w^h)としたとき，この暗号属性ベクトルで暗号化された暗号文を復号可能なのは，j≦hかつ1≦i≦jについてw^iTv^i=0となるdk(v^1，…，v^j)を持つユーザ装置だけである。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開2011-141472号公報
【特許文献２】特開2011-128609号公報
【特許文献３】特開2010-273317号公報
【非特許文献】
【０００８】
【非特許文献１】Jonathan Katz, Amit Sahai, and Brent Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of Lecture Notes in Computer Science, pages 146-162. Springer-Verlag, 2008. The full version is available at http://eprint.iacr.org/2007/404.
【非特許文献２】Shweta Agrawal, David Mandell Freeman, and Vinod Vaikuntanathan. Functional encryption for inner product predicates from learning with errors. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 21-40. Springer-Verlag, 2011. The full version is available at http://eprint.iacr.org/2011/410.
【非特許文献３】Tatsuaki Okamoto and Katsuyuki Takashima. Hierarchical predicate encryption for inner-products. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 214-231. Springer-Verlag, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
nをセキュリティパラメータとする。非特許文献１の格子問題に基づく内積暗号のベクトルの台はR=Zqである。このとき，鍵サイズはΩ(μn2 lg3q)，暗号文サイズはΩ(μn lg3 q)となる。μは属性ベクトルの長さ，lgは２を底とする対数を表す。一部の応用では，1/|R|が無視できることが必要なため，q=2O(n)と取ることがある。この場合，鍵サイズはΩ(μn5)，暗号文サイズはΩ(μn4)となり，非常に大きい。また，既存方式で格子問題に基づき階層型内積暗号を提案したものは存在しない。
【００１０】
本発明は，鍵サイズや暗号文サイズの小さい，格子問題に基づく階層型内積暗号技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の階層型内積暗号技術は，内積暗号のパラメータRをGF(qn)とすることで，鍵サイズや暗号文サイズを抑える。具体的には，
κをセキュリティパラメータ，dを階層の最大の深さ，μを属性ベクトルの長さ，Lを平文のビット長，n，q，mをそれぞれ格子用のパラメータ，σ1，…，σdを鍵発行用のパラメータ，DΧをZq上の分布，b，k=┌logb q┐，m’=nkをそれぞれサイズ用のパラメータ，g=(1，b，…，bk-1)∈Zqk，gg=gg(x)∈Zq[x]をGF(qn)=Zq[x]/<gg>を定義するモニック既約多項式とし，自然数nについて{1，…，n}を[n]で表し，行列A∈Zqn×mについて格子を
Λq⊥(A)={z∈Zm:z≡ATs (mod q)となるs∈Zqnが存在する}
とし，
セットアップアルゴリズムSetup(1κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)：
1. (A，T┬)←GenTrap(1κ，q，n，m)，
2. δ∈[d]およびi∈[μ]について，Aδ，i←Zqn×m’をランダムに選び，
3. U←Zqn×Lをランダムに選ぶ
ことによって，予め共通パラメータpp=((κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)，A，{Aδ，i}，U)とマスター秘密鍵msk=(T┬，pp)が与えられているとして，
鍵発行装置は，
鍵生成アルゴリズムGen(pp，msk，(v^1，…，v^j))：(v^1，…，v^j)を鍵属性ベクトル，1≦j≦dとし，δ∈[j]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μ，Cv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’，F(v^1，…，v^j)=[A|Cv^1|…|Cv^j]∈Zqn×(m+jm’)として，T(v^1，…，v^j)←DelgBasis(T┬，F(v^1，…，v^j)，σj)，を実行し，秘密鍵dk(v^1，…，v^j)=T(v^1，…，v^j)を出力する鍵生成部
を含み，
暗号化装置は，
暗号化アルゴリズムEnc(pp，(w^1，…，w^h)，m∈{0，1}L)：(w^1，…，w^h)を暗号属性ベクトル，Inをｎ行ｎ列の単位行列，(×)をクロネッカー積とし，δ∈[h]について，w^δ=(wwδ，1，…，wwδ，μ)∈GF(qn)μ，G←In(×)(1，b，…，bk-1)として，
s←Zqnをランダムに選び，e←DΧmとf←DΧLをランダムに選ぶ選択部と，
c0←ATs+eを計算する第１暗号要素計算部と，
δ∈[h]とi∈[μ]について，Rδ，i←{-1，+1}m×m’をランダムに選び，cδ，i←(Aδ，i+H(wwδ，i)・G)Ts+Rδ，iTe∈Zqm’を計算する第２暗号要素計算部と，
c’←UTs+f+└q/2┘mを計算する第３暗号要素計算部と，
を含み，ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)を暗号文として出力する暗号文生成部と，
を含み，
復号装置は，
復号アルゴリズムDec(pp，dk(v^1，…，v^j)，ct)：
秘密鍵dk(v^1，…，v^j)=T(v^1，…，v^j)と暗号文ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)から，
δ∈[j]についてcv^δ←Σi=1μHg(vvδ，i)・cδ，iを計算する第１計算部と，
c←[c0|cv^1|…|cv^j]として，s←Invert(F(v^1，…，v^j)，T(v^1，…，v^j)，c)を計算する第２計算部と，
d←c’-UTsを計算する第３計算部と，
を含み，(2/q)dの各要素を一番近い整数に丸め，各々偶奇を0/1と対応させた結果，得られたベクトルを復号された平文m∈{0，1}Lとして出力する復号部と
を含む階層型内積暗号システムを構成する。
ただし，
GenTrap(1κ，q，n，m)：
行列A∈Zqn×m，Λq⊥(A)の基底Tの組(A，T)∈Zqn×m×Zm×mを出力するアルゴリズムであり，
Invert(A，T，c)：
TがΛq⊥(A)の基底であるときc=ATs+eとなるs∈Zqnを出力するアルゴリズムであり，
Hgを，Hg:GF(qn)→Zqnk×nk，Hg(aa)=Dg(H(aa))∈Bnk×nk⊆Zqnk×nkと定義し，
正整数b≧2について，B={0，1，…，b-1}⊆Zq，g=(1，b，…，bk-1)∈Zqk，q≦bkが成立しているとして，a∈Zqについて，dg(a)=(a1，…，ak)T∈Bkを，a=Σi=1kai・bi-1となるような関数として定義し，
Dgを，Dg:Zq→Bk×k，a → [dg(a)dg(ba)…dg(bk-1a)]∈Bk×kと定義し，
行列A={ai,j}∈Zqn×mについてDgの定義域を拡張したものを
【数１】
0005730805.tif 000002
と定義し，
ηを，η：GF(qn)→Zqn，aa=a0+a1X+…+an-1Xn-1 → (a0，…，an-1)Tと定義し，
Hを，H:GF(qn)→Zqn×n，aa=a0+a1X+…+an-1Xn-1 → [η(aa)η(aX)…η(aXn-1)]と定義している。
【００１２】
復号装置は，
鍵生成アルゴリズムDelg(pp，dk(v^1，…，v^j)，(v^j+1，…，v^s))：
dk(v^1，…，v^j)=T(v^1，…，v^j)，δ∈[s]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μとして，
δ∈[s]についてCv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’とし，F(v^1，…，v^j，v^j+1，…，v^s)=[A|Cv^1|…|Cv^s]∈Zqn×(m+sm’)として，T(v^1，…，v^j，v^j+1，…，v^s)←DelgBasis(T(v^1，…，v^j)，F(v^1，…，v^j)，σs)を実行し，dk(v^1，…，v^s)=T(v^1，…，v^s)を出力する鍵生成部をさらに含んでもよい。
ただし，
ExtBasis(T，A^=[A|C])：
TがΛq⊥(A)の基底であるとき，Λq⊥(A^)の基底T’を出力するアルゴリズムであり，
RandBasis(S，s)：
Sが格子Λq⊥(A)の基底であるとき，格子Λq⊥(A)のランダムな基底S’を出力するアルゴリズムであり，
DelgBasis(T，A^=[A|C]，s)：
TがΛq⊥(A)の基底であるとき，A^に対応する行列T’を出力するアルゴリズムであり，S←ExtBasis(T，A^)，T’←RandBasis(S，s)で与えられる。
【発明の効果】
【００１３】
本発明に拠れば，詳細は後述の実施形態に譲るが，具体的には，鍵サイズΩ(μn2 lg2q)，暗号文サイズΩ(μn lg2 q)となる。1/|R|が無視できることが必要な応用であっても，1/|R|=1/qnとなるため，これは無視できる。そのような応用でもq=poly(n)と置くことができ，鍵サイズΩ(μn2 lg2n)，暗号文サイズΩ(μn lg2 n)を達成できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態に関わる階層型内積暗号システムのシステム構成並びにその構成要素である鍵発行装置，暗号化装置，復号装置の機能構成を示す図。
【発明を実施するための形態】
【００１５】
＜準備＞
自然数nについて{1，…，n}を[n]で表す。行列A∈Zqn×mについて格子を
Λq⊥(A)={z∈Zm:z≡ATs (mod q)となるs∈Zqnが存在する}
で定義する。行列やベクトルの右肩の記号Tは転置を表す。
【００１６】
また，以下のアルゴリズムを用いる。
（１）GenTrap(1κ，q，n，m)：
(A，T)∈Zqn×m×Zm×mを出力するアルゴリズムである。TはΛq⊥(A)の基底である。この具体例は，参考文献１，参考文献２，参考文献３に記載されている。
（参考文献１）Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, STOC 2008, pages 197-206. ACM, 2008.
（参考文献２）Joel Alwen and Chris Peikert. Generating shorter bases for hard random lattices. In Susanne Albers and Jean-Yves Marion, editors, STACS 2009, volume 3 of LIPIcs, pages 75-86, Germany, 2009.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,  Germany 
（参考文献３）Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. Cryptology ePrint Archive, Report 2011/501, 2011. To appear in EUROCRYPT 2012. Available at http://eprint.iacr.org/2011/501.
（２）ExtBasis(T，A^=[A|C])：
TがΛq⊥(A)の基底であるとき，Λq⊥(A^)の基底T’を出力するアルゴリズムである。具体例は参考文献４に記載されている。
（参考文献４）David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In Gilbert [6], pages 523-552.
（３）RandBasis(S，s)：
Sが格子Λq⊥(A)の基底であるとき，格子Λq⊥(A)のランダムな基底S’を出力するアルゴリズムである。具体例は参考文献４に記載されている。
（４）Invert(A，T，c)：
TがΛq⊥(A)の基底であるときc=ATs+eとなるs∈Zqnを出力するアルゴリズムである。
【００１７】
さらに，参考文献４に開示されるアルゴリズムを抽象化した以下のアルゴリズムを定義する。
（５）DelgBasis(T，A^=[A|C]，s)：
TがΛq⊥(A)の基底であるとき，A^に対応する行列T’を出力するアルゴリズムである。具体的には，
1. S←ExtBasis(T，A^)とする。
2. T’←RandBasis(S，s)を出力する。
【００１８】
参考文献５（Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice (H)IBE in the standard model. In Gilbert [6], pages 553-572.）などに記載されている，関数H:GF(qn)→Zqn×nを以下で定義する。<gg>は，多項式gg∈Zq[X]で生成される単項イデアルを表す。GF(qn)はn次既約多項式gg∈Zq[X]を用いてGF(qn)=Zq[X]/<gg>として定義されているとする。
まず，写像ηを，η：GF(qn)→Zqn，aa=a0+a1X+…+an-1Xn-1 → (a0，…，an-1)Tで定義する。
次に，写像Hを，H:GF(qn)→Zqn×n，aa=a0+a1X+…+an-1Xn-1 → [η(aa)η(aaX)…η(aaXn-1)]で定義する。
【００１９】
正整数b≧2について，B={0，1，…，b-1}⊆Zqとする。g=(1，b，…，bk-1)∈Zqkとし，q≦bkが成立しているとする。a∈Zqについて，dg(a)=(a1，…，ak)T∈Bkをa=Σi=1kai・bi-1となるような関数として定義する。写像Dgを，Dg:Zq→Bk×k，a → [dg(a)dg(ba)…dg(bk-1a)]∈Bk×kで定義する。
【００２０】
また，適当な行列A={ai,j}∈Zqn×mについてDgの定義域を拡張して
【数２】
0005730805.tif 000003
と定義する。
【００２１】
以上を用いて，写像Hg:GF(qn)→Zqnk×nkをHg(aa)=Dg(H(aa))∈Bnk×nk⊆Zqnk×nkと定義する。
【００２２】
［実施例］
上述の準備に基づいて，階層型内積暗号Π=(Setup; Gen; Enc; Dec; Delg)を構成する。
階層型内積暗号Π=(Setup; Gen; Enc; Dec; Delg)に基づく階層型内積暗号システム１は，鍵発行装置１００と，暗号化装置２００と，復号装置３００を含む。
＝パラメータの説明＝
κ: セキュリティパラメータ
d: 階層の最大の深さを設定するパラメータ
μ: 属性ベクトルの長さ
L: 平文のビット長
n，q，m: 格子用のパラメータ。ただし，ｑは素数である。
σ1，…，σd: 鍵発行用のパラメータ
DΧ: 体Zq上の分布
b，k=┌logb q┐，m’=nk: サイズ用パラメータ（記号┌・┐は天井関数を表す）
(1，b，…，bk-1)∈Zqk
gg=gg(x)∈Zq[x]: GF(qn)=Zq[x]/<gg>を定義するモニック既約多項式
【００２３】
Setup(1κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)：
1. (A，T┬)←GenTrap(1κ，q，n，m)
2. δ∈[d]およびi∈[μ]について，Aδ，i←Zqn×m’をランダムに選ぶ。
3. U←Zqn×Lをランダムに選ぶ。
そして，pp=((κ，d，μ，L，n，q，m，m’，{σi}i∈[d]，b，k，gg)，A，{Aδ，i}，U)とmsk=(T┬，pp)を出力する。
【００２４】
Gen(pp，msk，(v^1，…，v^j))：(v^1，…，v^j)は鍵属性ベクトル。ただし，1≦j≦d。
1. δ∈[j]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μとよみ，Cv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’とおく。
2. F(v^1，…，v^j)=[A|Cv^1|…|Cv^j]∈Zqn×(m+jm’)とおく。
3. 鍵発行装置１００の鍵生成部１０１は，T(v^1，…，v^j)←DelgBasis(T┬，F(v^1，…，v^j)，σj)とする。
そして，dk(v^1，…，v^j)=T(v^1，…，v^j)を出力する。
【００２５】
Enc(pp，(w^1，…，w^h)，m∈{0，1}L)：(w^1，…，w^h)は暗号属性ベクトル。
δ∈[h]について，w^δ=(wwδ，1，…，wwδ，μ)∈GF(qn)μとする。
1. G←In(×)(1，b，…，bk-1)とおく。Inはｎ行ｎ列の単位行列である。(×)はクロネッカー積を表す。
2. 暗号化装置２００の選択部２０１は，s←Zqnをランダムに選ぶ。
3. 暗号化装置２００の選択部２０１は，e←DΧmとf←DΧLをランダムに選択する。
4. 暗号化装置２００の第１暗号要素計算部２０２ａは，c0←ATs+eを計算する。
5. 暗号化装置２００の第２暗号要素計算部２０２ｂは，δ∈[h]とi∈[μ]について，Rδ，i←{-1，+1}m×m’をランダムに選び，cδ，i←(Aδ，i+H(wwδ，i)・G)Ts+Rδ，iTe∈Zqm’を計算する。
6. 暗号化装置２００の第３暗号要素計算部２０２ｃは，c’←UTs+f+└q/2┘mを計算する（記号└・┘は床関数を表す）。
そして，暗号文生成部２０２は，ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)を出力する。
【００２６】
Dec(pp，dk(v^1，…，v^j)，ct)：
dk(v^1，…，v^j)=T(v^1，…，v^j)と暗号文ct=(c0，{cδ，i}δ∈[h]，i∈[μ]，c’)から，
1. 復号装置３００の第１計算部３０１ａは，δ∈[j]についてcv^δ←Σi=1μHg(vvδ，i)・cδ，iを計算する。
2. c←[c0|cv^1|…|cv^j]とおく。
3. 復号装置３００の第２計算部３０１ｂは，s←Invert(F(v^1，…，v^j)，T(v^1，…，v^j)，c)を計算する。
4. 復号装置３００の第３計算部３０１ｃは，d←c’-UTsを計算する。
5. 復号装置３００の復号部３０１は，(2/q)dの各要素を一番近い整数に丸め，各々偶奇を0/1と対応させる。この結果，得られたベクトルをm∈{0，1}Lとして出力する。
【００２７】
Delg(pp，dk(v^1，…，v^j)，(v^j+1，…，v^s))：
dk(v^1，…，v^j)=T(v^1，…，v^j)である。δ∈[s]について，v^δ=(vvδ，1，…，vvδ，μ)∈GF(qn)μとする。
1. δ∈[s]についてCv^δ=Σi=1μAδ，i・Hg(vvδ，i)∈Zqn×m’とおく。
2. F(v^1，…，v^j，v^j+1，…，v^s)=[A|Cv^1|…|Cv^s]∈Zqn×(m+sm’)とおく。
3. 復号装置３００の鍵生成部３０２は，T(v^1，…，v^j，v^j+1，…，v^s)←DelgBasis(T(v^1，…，v^j)，F(v^1，…，v^j)，σs)とする。
そして，dk(v^1，…，v^s)=T(v^1，…，v^s)を出力する。
【００２８】
＜補記＞
階層型内積暗号システムに含まれうるハードウェアエンティティ（鍵発行装置，暗号化装置，復号装置）は，キーボードなどが接続可能な入力部，液晶ディスプレイなどが接続可能な出力部，ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部，ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕，メモリであるＲＡＭやＲＯＭ，ハードディスクである外部記憶装置並びにこれらの入力部，出力部，通信部，ＣＰＵ，ＲＡＭ，ＲＯＭ，外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて，ハードウェアエンティティに，ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては，汎用コンピュータなどがある。
【００２９】
ハードウェアエンティティの外部記憶装置には，上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず，例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい）。また，これらのプログラムの処理によって得られるデータなどは，ＲＡＭや外部記憶装置などに適宜に記憶される。
【００３０】
ハードウェアエンティティでは，外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて，適宜にＣＰＵで解釈実行・処理される。その結果，ＣＰＵが所定の機能（例えば，鍵生成部，選択部，暗号文生成部，復号部など）を実現する。
【００３１】
各実施形態で説明したハードウェアエンティティの細部においては，数論における数値計算処理が必要となる場合があるが，数論における数値計算処理自体は，周知技術と同様にして達成されるので，その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては，例えばＰＡＲＩ／ＧＰ，ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては，例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成24年3月21日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては，例えばインターネット〈URL: http://page.math.tu-berlin.de/~kant/kash.html〉［平成24年3月21日検索］を参照のこと。）。
また，この点に関する文献として，参考文献Ａを挙げることができる。
（参考文献Ａ）H. Cohen，"A Course in Computational Algebraic Number Theory"，GTM 138，Springer-Verlag，1993.
【００３２】
本発明は上述の実施形態に限定されるものではなく，本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また，上記実施形態において説明した処理は，記載の順に従って時系列に実行されるのみならず，処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。上述の実施例では，情報処理に用いられるデータ等の情報の装置間での送受信に関わる説明を省略したが，当然のこととして，或る装置Xにおける或る情報処理に用いられる情報Yは，当該装置Xが当該情報Yを保有していない場合，当該情報処理の実行前に，当該装置Xによって当該情報Yを保有する装置から取得されていることに留意されたい。なお，データ等の情報の装置間での送受信は周知技術を利用して実施される。
【００３３】
また，上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合，ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして，このプログラムをコンピュータで実行することにより，上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００３４】
この処理内容を記述したプログラムは，コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては，例えば，磁気記録装置，光ディスク，光磁気記録媒体，半導体メモリ等どのようなものでもよい。具体的には，例えば，磁気記録装置として，ハードディスク装置，フレキシブルディスク，磁気テープ等を，光ディスクとして，ＤＶＤ（Digital Versatile Disc），ＤＶＤ−ＲＡＭ（Random Access Memory），ＣＤ−ＲＯＭ（Compact Disc Read Only Memory），ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を，光磁気記録媒体として，ＭＯ（Magneto-Optical disc）等を，半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００３５】
また，このプログラムの流通は，例えば，そのプログラムを記録したＤＶＤ，ＣＤ−ＲＯＭ等の可搬型記録媒体を販売，譲渡，貸与等することによって行う。さらに，このプログラムをサーバコンピュータの記憶装置に格納しておき，ネットワークを介して，サーバコンピュータから他のコンピュータにそのプログラムを転送することにより，このプログラムを流通させる構成としてもよい。
【００３６】
このようなプログラムを実行するコンピュータは，例えば，まず，可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを，一旦，自己の記憶装置に格納する。そして，処理の実行時，このコンピュータは，自己の記録媒体に格納されたプログラムを読み取り，読み取ったプログラムに従った処理を実行する。また，このプログラムの別の実行形態として，コンピュータが可搬型記録媒体から直接プログラムを読み取り，そのプログラムに従った処理を実行することとしてもよく，さらに，このコンピュータにサーバコンピュータからプログラムが転送されるたびに，逐次，受け取ったプログラムに従った処理を実行することとしてもよい。また，サーバコンピュータから，このコンピュータへのプログラムの転送は行わず，その実行指示と結果取得のみによって処理機能を実現する，いわゆるＡＳＰ（Application Service Provider）型のサービスによって，上述の処理を実行する構成としてもよい。なお，本形態におけるプログラムには，電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３７】
また，この形態では，コンピュータ上で所定のプログラムを実行させることにより，ハードウェアエンティティを構成することとしたが，これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005730805.tif 000006