加密系统、加密装置、重加密密钥生成装置、重加密装置以及加密程序

技术领域

本发明涉及函数型加密中的代理人重加密(FunctionalProxyRe-Encryption， FPRE)方式。本发明尤其涉及能够指定用于进行重加密的条件的FPRE(Functional ConditionalProxyRe-Encryption、FCPRE)方式。

背景技术

代理人重加密(ProxyRe-Encryption、PRE)是没有对加密文进行解密就向其他人 委托加密文的解密权限的系统。在非专利文献1中具有涉及基于ID的加密中的PRE (Identity-BasedPRE、IBPRE)方式的记载。在非专利文献2中具有涉及基于属性的加密中 的PRE(Attribute-BasedPRE、ABPRE)方式的记载。在非专利文献2所记载的PRE方式中，可 对加密文仅指定由逻辑“与”和“非”构成的属性。

在非专利文献3中，具有关于能够指定用于进行重加密的条件的代理人重加密 (ConditionalProxyRe-Encryption，CPRE)方式的记载。

在专利文献1中，具有涉及函数型加密(FunctionalEncryption、FE)方式的记载。 在非专利文献4中，具有涉及FPRE方式的记载。

现有技术文献

专利文献

专利文献1：日本特开2012-133214号公报

非专利文献

非专利文献1：M.Green，andG.Ateniese，Identity-BasedProxyRe- encryption.InAppliedCryptographyandNetworkSecurity.volume4521ofLNCS，pp 288-306，2007.

非专利文献2：XiaohuiLiang，ZhenfuCao，HuangLin，JunShao.Attribute basedproxyre-encryptionwithdelegatingcapabilities.ASIACCS2009pp.276- 286.

非专利文献3：J.Weng，Y.YangQ.Tang，R.H.Deng，andF.Bao，“Efficient ConditionalProxyRe-EncryptionwithChosen-CiphertextSecurity”inISC2009.

非专利文献4：YutakakawaiandKatuyukiTakashima，Fully-Anonymous FunctionalProxy-Re-Encryption.CryptologyePrintArchive：Report2013/318

非专利文献5：Okamoto，TTakashima，K.：DecentralizedAttribute-Based Signatures.ePrinthttp：//eprint.iacr.org/2011/701

非专利文献6：Okamoto，TTakashima，K.：FullySecureUnboundedInner- ProductandAttribute-BasedEncryption.ePrinthttp：//eprint.iacr.org/2012/671

非专利文献7：Okamoto，T.，Takashima，K.：AchievingShortCiphertextsor ShortSecret-KeysforAdaptivelySecureGeneralInner-ProductEncryption.CANS 2011，LNCS，vol.7092，pp.138-159SpringerHeidelberg(2011).

发明内容

发明要解决的课题

因为非专利文献3所记载的CPRE方式不是函数型加密中的方式，所以，对解密者的 指定或重加密条件的指定具有制约，不能灵活地应对。

非专利文献4所记载的FPRE方式可利用某接收者生成的重加密密钥，对该接收者 能解密的全部加密文进行重加密，不能指定接收者进行重加密的加密文。

本发明的目的是在生成重加密密钥时，可灵活地指定能够重加密的加密文的条 件。

解决问题的手段

本发明的加密系统实现以下这样的加密方式中的代理人重加密功能，该加密方式 是在两个信息相互对应的情况下，能够利用设定有一个信息的解密密钥对设定有另一个信 息的加密文进行解密，其特征在于，该加密系统具备：加密装置，其输出加密文ct，该加密文 ct包含设定有相互对应的属性信息x、v中的一个的加密文c和设定有相互对应的属性信息 y、z中的一个的加密文c^～；重加密密钥生成装置，其取得设定有所述属性信息x、v中的另一 个的解密密钥k^＊，输出重加密密钥rk，该重加密密钥rk包含利用转换信息W₁对所取得的解 密密钥k^＊进行转换而得到的解密密钥k^＊rk、设定有所述属性信息y、z中的另一个的解密密钥 k^～＊rk、设定有相互对应的属性信息x’、v’中的一个而对所述转换信息W₁进行加密后的加密 转换信息ψ^rk；以及重加密装置，其输出重加密文rct，该重加密文rct包含有在所述加密文ct 内设定相互对应的追加信息Η、Θ中的一个而得到的加密文c^renc、在所述重加密密钥rk内 设定所述追加信息Η、Θ中的另一个而得到的解密密钥k^＊renc。

发明效果

在本发明的加密系统中，加密装置不仅仅设定加密文ct的解密条件(属性信息x、v 中的一个属性信息)，还能够设定用于设定加密文ct的可重加密的条件的信息(属性信息y、 z中的一个属性信息)，来生成加密文ct。另外，重加密密钥生成装置不仅仅设定重加密文 rct的解密条件(属性信息x’、v’中的一个属性信息)，还能够设定可重加密的条件(属性信 息y、z中的另一个属性信息)，来生成重加密密钥rk。另外，没有关于所设定的属性信息的制 约，可灵活地指定解密条件或重加密的条件。

附图说明

图1是矩阵M＾的说明图。

图2是矩阵M_δ的说明图。

图3是s₀的说明图。

图4是s^→T的说明图。

图5是执行CP-FCPRE方式的加密处理系统10的结构图。

图6是示出密钥生成装置100的功能的功能框图。

图7是示出加密装置200的功能的功能框图。

图8是示出解密装置300的功能的功能框图。

图9是示出重加密装置400的功能的功能框图。

图10是示出重加密文解密装置500的功能的功能框图。

图11是示出Setup算法的处理的流程图。

图12是示出KG算法的处理的流程图。

图13是示出Enc算法的处理的流程图。

图14是示出RKG算法的处理的流程图。

图15是示出REnc算法的处理的流程图。

图16是示出Dec1算法的处理的流程图。

图17是示出Dec2算法的处理的流程图。

图18是执行KP-FCPRE方式的加密处理系统10的结构图。

图19是示出密钥生成装置100的功能的功能框图。

图20是示出加密装置200的功能的功能框图。

图21是示出解密装置300的功能的功能框图。

图22是示出重加密装置400的功能的功能框图。

图23是示出重加密文解密装置500的功能的功能框图。

图24是示出KG算法的处理的流程图。

图25是示出Enc算法的处理的流程图。

图26是示出RKG算法的处理的流程图。

图27是示出REnc算法的处理的流程图。

图28是示出Dec1算法的处理的流程图。

图29是示出Dec2算法的处理的流程图。

图30是示出密钥生成装置100、加密装置200、解密装置300、重加密装置400、重加 密文解密装置500的硬件结构的一例的图。

具体实施方式

以下，根据图来说明发明的实施方式。

在以下的说明中，处理装置是后述的CPU911等。存储装置是后述的ROM913、 RAM914、磁盘920等。通信装置是后述的通信板915等。输入装置是后述的键盘902、通信板 915等。即，处理装置、存储装置、通信装置、输入装置是硬件。

对以下说明中的记法进行说明。

在A是随机的变量或分布时，式101表示根据A的分布而从A中随机选择y。即，在式 101中，y是随机数。

【式101】

$y\stackrel{R}{\leftarrow }A$

在A是集合时，式102表示均匀地从A中选择y。即，在式102中，y是均匀随机数。

【式102】

$y\stackrel{U}{\leftarrow }A$

式103表示y是利用z进行定义的集合或者y是代入z的集合。

【式103】

y:＝z

在a是常数时，式104表示机器(算法)A对于输入x而输出a。

【式104】

A(x)→a

例如，

A(x)→1

式105即F_q表示位数q的有限体。

【式105】

矢量标记表示有限体F_q中的矢量标识。即，是式106。

【式106】

表示

式107表示式108所示的两个矢量x^→与v^→的式109所示的内积。

【式107】

$\overrightarrow{x}·\overrightarrow{v}$

【式108】

$\overrightarrow{x}=(x_1,...,x_n),$

$\overrightarrow{v}=(v_1,...,v_n)$

【式109】

${\Sigma }_{i=1}^n{x}_i{v}_i$

X^T表示矩阵X的转置矩阵。

针对式110所示的基底B和基底B^＊，是式111。

【式110】

【式111】

e^→_j表示式112所示的标准基底矢量。

【式112】

对于j＝1，...，n，

另外，在以下的说明中，当利用下标或上标表示Vt、nt、wt、zt、nu、wu、zu时，该Vt、 nt、wt、zt、nu、wu、zu表示V_t、n_t、w_t、z_t、n_u、w_u、z_u。同样，当用上标表示δi、j时，该δi、j表示 δ_i、j。

另外，当在下标文字或上标文字上标注表示矢量的→时，该→表示在下标文字或 上标文字上用上标进行标注的情况。另外，当对下标文字或上标文字标注～时，该～表示在 下标文字或上标文字上用上标标注的情况。

实施方式1.

在该实施方式中，说明作为实现FCPRE方式的基础的概念，还说明该实施方式的 FCPRE方式的结构。

第1，简单地说明FCPRE。

第2，说明用于实现FCPRE方式的空间即双对配对矢量空间(DualPairingVector Spaces，DPVS)这样的具有丰富的数学构造的空间。

第3，说明用于实现FCPRE方式的概念。这里，说明张成方案、属性矢量的内积和访 问构造、秘密分散方式(秘密共享方式)。

第4，说明该实施方式的FCPRE方式。在该实施方式中，说明加密文策略的FCPRE方 式(Ciphertext-PolicyFCPRE、CP-FCPRE)方式。因此，首先说明CP-FCPRE方式的基本结构。 接着，说明实现该CP-FCPRE方式的加密系统10的基本结构。接着，说明为了实现该CP-FCPRE 方式而采用的部件。然后，详细地说明该实施方式的CP-FCPRE方式以及加密系统10。

＜第1.FCPRE＞

首先，说明FPRE。FPRE是使加密密钥(ek)、解密密钥(dk)与重加密密钥(rk)的关系 进一步高度化并且变得灵活的代理人重加密方式。

FPRE具有以下的两个特征。

关于第一个特征，加密密钥和解密密钥分别设定了属性信息x和属性信息v。然后， 针对关系R，仅在R(x，v)成立的情况下，解密密钥dk_v能够对由加密密钥ek_x加密的加密文进 行解密。

关于第二个特征，除了对加密密钥和解密密钥分别设定属性信息x和属性信息v之 外，重加密密钥还设定了两个属性信息(x’，v)。并且，仅在R(x，v)成立的情况下，重加密密 钥rk_(x’，v)能够将由加密密钥ek_x加密的加密文变更为可利用R(x’，v’)成立的解密密钥dk_v’解密的加密文即由加密密钥ek_x’加密的加密文。

仅在关系R是等号关系的情况即x＝v的情况下，当R(x，v)成立时，PRE方式是 IDPRE。

作为比IDPRE一般化的PRE，具有ABPRE。在ABPRE中，对加密密钥和解密密钥设定的 属性信息是属性信息的组。例如，对加密密钥和解密密钥设定的属性信息分别是X：＝ (x₁，...，x_d)和V：＝(v₁，...，v_d)。

关于属性信息的成分，对访问结构S输入每个组件的等号关系(例如，{x_t＝v_t}t∈ {1，...，d})。然后，仅在访问结构S受理输入的情况下，R(X，V)成立。即，可利用解密密钥来 解密由加密密钥加密的加密文。非专利文献2提出了在加密文中填入访问结构S的加密文策 略的PRE方式。此时的访问结构是仅由逻辑“与”和“非”构成的构造。

接着，说明FCPRE。FCPRE是能够指定用于重加密的条件的FPRE。

在FCPRE中，除了对加密密钥和解密密钥分别设定属性信息x和属性信息v以及对 重加密密钥设定两个属性信息(x’，v)之外，还对加密文和重加密密钥分别设定属性信息z 和属性信息y。然后，针对关系R，仅在R(x，v)成立且R(z，y)成立的情况下，能够将由加密密 钥ek_x加密的加密文变更为可利用R(x’，v’)成立的解密密钥dk_v’解密的加密文即由加密密 钥ek_x’加密的加密文。

此外，具有不存在加密文的转发功能即不存在重加密密钥的通常的FE。在FE中，不 存在重加密密钥生成处理、重加密处理，加密密钥和解密密钥分别设定有属性信息x和属性 信息v。并且，针对关系R，仅在R(x，v)成立的情况下，解密密钥dk_v：＝(dk，v)能够对由加密 密钥ek_x：＝(ek，x)加密的加密文进行解密。

＜第2.双对配对矢量空间＞

首先，说明对称双线形配对组。

对称双线形配对组(q，G，G^T，g，e)是质数q、位数q的循环加法组G、位数q的循环乘 法组G^T、g≠0∈G与可利用多项式时间进行计算的非退化双线形配对(Nondegenerate BilinearPairing)e：G×G→G_T的组。非退化双线形配对是e(sg，tg)＝e(g，g)^st，e(g，g)≠ 1。

在以下的说明中，将G_bpg作为如下这样的算法，该算法将1^λ作为输入，输出将安全 参数作为λ的双线形配对组的参数param_G：＝(q，G，G_T，g，e)的值。

接着，说明双对配对矢量空间。

双对配对矢量空间(q，V，G_T，A，e)可由对称双线形配对组(param_G：＝(q，G，G_T，g， e))的直积构成。双对配对矢量空间(q，V，G_T，A，e)是质数q、式113所示的F_q上的N维矢量空间 V、位数q的循环组G_T、空间V的标准基底A：＝(a₁，...，a_N)的组，具有以下的运算(1)(2)。这 里，a_i如式114所示。

【式113】

【式114】

运算(1)：非退化双线形配对

空间V中的配对利用式115进行定义。

【式115】

这里，

这是非退化双线形。即，是e(sx，ty)＝e(x，y)^st，针对全部的y∈V，在e(x，y)＝1的 情况下，x＝0。另外，针对全部的i和j，e(a_i，a_j)＝e(g，g)^δi，j。这里，当i＝j时，δ_i，j＝1，当i≠ j时，δ_i，j＝0。另外，e(g，g)≠1∈G_T。

运算(2)：失真映射

式116所示的空间V中的线形转换可进行式117。

【式116】

φ_i,j(a_j)＝a_i，

如果k≠j，则φ_i,j(ak)＝0。

【式117】

这里，

(g1,...gN):＝x。

这里，将线形转换称为失真映射。

在以下的说明中，将G_dpvs作为如下这样的算法，该算法是将1^λ(λ∈自然数)、N∈自 然数、双线形配对组的参数param_G：＝(q，G，G_T，g，e)的值作为输入，输出安全参数是λ、且作 为N维空间V的双对配对矢量空间的参数param_V：＝(q，V，G_T，A，e)的值。

此外，这里，说明利用上述的对称双线形配对组来构成双对配对矢量空间的情况。 此外，也可以利用非对称双线形配对组来构成双对配对矢量空间。容易将以下的说明应用 到利用非对称双线形配对组构成双对配对矢量空间的情况。

＜第3.用于实现FCPRE方式的概念＞

＜第3-1.张成方案＞

图1是矩阵M＾的说明图。

将{p₁，...，p_n}作为变量的集合。M＾：＝(M，ρ)是带标签的矩阵。这里，矩阵M是F_q上 的(L行×r列)的矩阵。另外，ρ是对矩阵M的各个行附加的标签，与{p₁，...，p_n，￢p₁，...，￢ p_n}中的任意一个常量对应。此外，对M的全部行附加的标签ρ_i(i＝1，...，L)与任意一个常量 对应。即，ρ：{1，...，L}→{p₁，...，p_n，￢p₁，...，￢p_n}。

针对全部的输入列δ∈{0，1}ⁿ，定义矩阵M的部分矩阵M_δ。矩阵M_δ是由通过输入列δ 使值“1”与标签ρ对应的矩阵M的行构成的部分矩阵。即，矩阵M_δ是由与使得δ_i＝1的p_i对应的 矩阵M的行和与使得δ_i＝0的￢p_i对应的矩阵M的行构成的部分矩阵。

图2是矩阵M_δ的说明图。此外，在图2中，设为n＝7、L＝6、r＝5。即，变量的集合是 {p₁，...，p₇}，矩阵M是(6行×5列)的矩阵。另外，在图2中，关于标签ρ，ρ₁与￢p₂对应，ρ₂与p₁对应，ρ₃与p₄对应，ρ₄与￢p₅对应，ρ₅与￢p₃对应，ρ₆与p₅对应。

这里，输入列δ∈{0，1}⁷是δ₁＝1、δ₂＝0、δ₃＝1、δ₄＝0、δ₅＝0、δ₆＝1、δ₇＝1。在此情况 下，由与用虚线包围的常量(p₁、p₃、p₆、p₇、￢p₂、￢p₄、￢p₅)对应的矩阵M的行构成的部分矩 阵是矩阵M_δ。即，由矩阵M的第1行(M₁)、第2行(M₂)、第4行(M₄)构成的部分矩阵是矩阵M_δ。

换言之，在映射γ：{1，...，L}→{0，1}是[ρ(j)＝p_i]∧[δ_i＝1]或[ρ(j)＝￢p_i]∧ [δ_i＝0]的情况下，γ(j)＝1，在其它情况下，γ(j)＝0。在此情况下，M_δ：＝(M_j)_γ(j)＝1。这里， M_j是矩阵M的第j行。

即，在图2中，映射γ(j)＝1(j＝1，2，4)，映射γ(j)＝0(j＝3，5，6)。因此， (M_j)_γ(j)＝1是M₁、M₂、M₄，是矩阵M_δ。

即，根据映射γ(j)的值是“0”还是“1”，决定矩阵M的第j行是否包含于矩阵M_δ内。

仅在1^→∈span＜M_δ＞的情况下，张成方案M＾受理输入列δ，在其它情况下拒绝输入 列δ。即，仅在对通过输入列δ从矩阵M＾获得的矩阵M_δ的行进行线形结合而获得1^→的情况下， 张成方案M＾受理输入列δ。此外，1^→是各要素为值“1”的行矢量。

例如，在图2的例子中，仅在对由矩阵M的第1、2、4行构成的矩阵M_δ的各行进行线形 结合而获得1→的情况下，张成方案M＾受理输入列δ。即，当存在使得α₁(M₁)+α₂(M₂)+α₄(M₄)＝ 1^→的α₁、α₂、α₄时，张成方案M＾受理输入列δ。

这里，在标签ρ仅与正的常量{p₁，...，p_n}对应的情况下，张成方案被称为单调。另 一方面，在标签ρ与常量{p₁，...，p_n，￢p₁，...，￢p_n}对应的情况下，张成方案被称为非单 调。这里，假设张成方案为非单调。并且，采用非单调张成方案，构成访问结构(非单调访问 结构)。所谓访问结构，简单说是进行对加密的访问控制。即，进行是否能够解密加密文的控 制。

后面详细地进行叙述，由于张成方案不是单调而是非单调，从而利用张成方案构 成的FCPRE方式的利用范围变广。

＜第3-2.属性信息的内积和访问结构＞

这里，采用属性信息的内积来计算上述的映射γ(j)。即，采用属性信息的内积来 决定在矩阵M_δ中包含矩阵M的哪行。

是部分全集合(sub-universe)，是属性的集合。 并且，U_t分别包含部分全集合的识别信息(t)和n维矢量(v^→)。即，U_t是(t，v^→)。这里，是t∈ {1，...，d}，是v→∈F_qⁿ。

U_t：＝(t，v^→)成为张成方案M＾：＝(M，ρ)中的变量p。即，是p：＝(t，v→)。并且，将变 量(p：＝(t，v^→)，(t，v’^→)，...)的张成方案M＾：＝(M，ρ)作为访问结构S。

即，访问结构S：＝(M，ρ)，ρ：{1，...，L}→{(t，v^→)，(t，v’^→)，...，￢(t，v^→)，￢(t， v’^→)，...}。

接着，将Γ作为属性的集合。即，Γ：＝{(t，x^→_t)|x^→_t∈F_qⁿ，1≤t≤d}。

当对访问结构S赋予Γ时，如以下这样地定义与张成方案M＾：＝(M，ρ)相对的映射 γ：{1，...，L}→{0，1}。关于i＝1，...，L的各个整数i，在[ρ(i)＝(t，v^→_i)]∧[(t，x^→_t)∈Γ] ∧[v^→_i·x^→_t＝0]或[ρ(i)＝￢(t，v^→_i)]∧[(t，x^→_t)∈Γ]∧[v^→_i·x^→_t≠0]时，γ(j)＝1，在 其它情况下，γ(j)＝0。

即，根据属性信息v^→与x^→的内积，计算映射γ。并且，如上所述，利用映射γ，决定 在矩阵M_δ中包含矩阵M的哪行。即，利用属性信息v^→与x→的内积，决定在矩阵M_δ中包含矩阵M 的哪行，仅在1^→∈span＜(Mi)_γ(i)＝1＞的情况下，访问结构S：＝(M，ρ)受理Γ。

＜第3-3.秘密分散方式＞

说明针对访问结构S：＝(M，ρ)的秘密分散方式。

此外，秘密分散方式是指，使秘密信息分散，成为没有意义的分散信息。例如，使秘 密信息s分散为10个，生成10个分散信息。这里，10个分散信息各自不具有秘密信息s的信 息。因此，即使得到某1个分散信息，也无法获得关于秘密信息s的任何信息。另一方面，当全 部得到10个分散信息时，可恢复秘密信息s。

另外，还具有以下这样的秘密分散方式：即使10个分散信息未全部得到，当仅得到 一部分(例如8个)时也能够恢复秘密信息s。这样，将能够利用10个分散信息中的8个来恢复 秘密信息s的情况称为8-out-of-10。即，将能够利用n个分散信息中的t个来恢复秘密信息s 的情况称为t-out-of-n。将该t称为阈值。

另外，还具有以下这样的秘密分散方式：在生成d₁、...、d₁₀这10个分散信息的情况 下，如果是d₁、...、d₈这8个分散信息，则能够恢复秘密信息s，如果是d₃、...、d₁₀这8个分散信 息，则不能恢复秘密信息s。即，还具有以下这样的秘密分散方式：除了得到的分散信息的个 数以外，还根据分散信息的组合，控制是否能够恢复秘密信息s。

图3是s₀的说明图。图4是s^→T的说明图。

将矩阵M设为(L行×r列)的矩阵。将f^→T设为式118所示的列矢量。

【式118】

${\overrightarrow{f}}^T:={(f_1,...f_r)}^T\stackrel{U}{\leftarrow }{F}_q^r$

将式119所示的s₀设为共享的秘密信息。

【式119】

$s_0:=\overrightarrow{1}·{\overrightarrow{f}}^T:={\Sigma }_{k=1}^r{f}_k$

另外，将式120所示的s^→T设为s₀的L个分散信息的矢量。

【式120】

${\overrightarrow{s}}^T:={(s_1,...s_L)}^T:=M·{\overrightarrow{f}}^T$

并且，将分散信息s_i设为属于ρ(i)的信息。

在访问结构S：＝(M，ρ)受理Γ的情况即关于γ：{1，...，L}→{0，1}是1^→∈span＜ (M_i)_γ(i)＝1＞的情况下，存在使得的常数{α_i∈F_q|i∈I}。

因为在图2的例子中已说明了当存在作为α₁(M₁)+α₂(M₂)+α₄(M₄)＝1^→的α₁、α₂、α₄时 张成方案M＾受理输入列δ的情况，所以，这是显然的。即，当存在使得α₁(M₁)+α₂(M₂)+α₄(M₄)＝ 1^→的α₁、α₂、α₄时，如果张成方案M＾受理输入列δ，则存在使得α₁(M₁)+α₂(M₂)+α₄(M₄)＝1^→的α₁、 α₂、α₄。

然后，是式121。

【式121】

∑_i∈Iα_is_i:＝s₀

此外，常数{α_i}可利用矩阵M的尺寸中的多项式时间进行计算。

如上所述，以下的实施方式的FCPRE方式在张成方案中应用内积述语和秘密分散 方式来构成访问结构。因此，可通过设计张成方案中的矩阵M或内积述语中的属性信息x以 及属性信息v(述语信息)，来自由地设计访问控制。即，能够以非常高的自由度进行访问控 制的设计。此外，矩阵M的设计相当于秘密分散方式的阈值等的条件设计。

例如，上述的基于属性的加密方式在以下实施方式的FCPRE方式的访问结构中，相 当于将内积述语的设计限定为某个条件的情况。即，基于属性的加密方式中的访问结构与 以下实施方式的FCPRE方式中的访问结构相比，没有内积述语中的属性信息x以及属性信息 v(述语信息)的设计自由度，相应地，访问控制的设计的自由度较低。此外，具体地说，基于 属性的加密方式相当于将属性信息{x^→_t}_{t∈{1、...、d}}与{v^→_t}_{t∈{1、...、d}}限定为与等号关系相对 的2维矢量例如x^→_t：＝(1，x_t)与v^→_t：＝(v_t，-1)的情况。

另外，内积述语加密方式中的PRE在以下实施方式的FCPRE方式的访问结构中，相 当于将张成方案中的矩阵M的设计限定为某个条件的情况。即，内积述语加密方式中的访问 结构与以下实施方式的FCPRE方式中的访问结构相比，没有张成方案中的矩阵M的设计自由 度，相应地，访问控制的设计的自由度较低。此外，具体地说，内积述语加密方式是将秘密分 散方式限定为1-out-of-1(或者d-out-of-d)的情况。

尤其，以下实施方式的FCPRE方式中的访问结构构成采用非单调张成方案的非单 调访问结构。因此，访问控制的设计的自由度更高。

具体地说，因为在非单调张成方案中包含否定形的常量(￢p)，所以能够设定否定 形的条件。例如，在第1公司中，具有A部、B部、C部和D部这4个岗位。这里，希望进行仅能够访 问(能够解密)第1公司的B部以外的岗位所属的用户这样的访问控制。在此情况下，当不能 设定否定形的条件时，需要设定“属于第1公司的A部、C部和D部中的任意部”这样的条件。另 一方面，当能够设定否定形的条件时，可设定“是第1公司的员工且属于B部以外”这样的条 件。即，由于能够设定否定形的条件，从而能够进行自然的条件设定。此外，可知，这里，虽然 岗位的个数较少，但在岗位的个数较多的情况下也非常有效。

＜第4.FCPRE方式的基本结构＞

＜第4-1.CP-FCPRE方式的基本结构＞

简单说明CP-FCPRE方式的结构。此外，所谓CP(加密文策略)，表示在加密文中填入 Policy的情况即填入访问结构的情况。

CP-FCPRE方式具备Setup、KG、Enc、RKG、REnc、Dec1、Dec2这7个算法。

(Setup)

Setup算法是将安全参数λ和属性的格式n^→：＝(d；n₁、...、n_d；w₁、...、w_d；z₁、...、 z_d)作为输入、输出公开参数pk和主密钥sk的概率性算法。

(KG)

KG算法是将属性集合Γ：＝{(t、x^→_t)|x^→_t∈F_q^nt、1≤t≤d}、公开参数pk和主密钥sk 作为输入、输出解密密钥sk_Γ的概率性算法。

(Enc)

Enc算法是将消息m、访问结构S＝(M、ρ)、S～＝(M～、ρ～)和公开参数pk作为输入、 输出加密文ct_S的概率性算法。

(RKG)

RKG算法是将解密密钥sk_Γ、访问结构S’：＝(M’、ρ’)、属性集合Γ～和公开参数pk 作为输入、输出重加密密钥rk_Γ、S’的概率性算法。

(REnc)

REnc算法是将加密文ct_S、重加密密钥rk_Γ、S’和公开参数pk作为输入、输出重加密 文rct_S’的概率性算法。

(Dec1)

Dec1算法是将重加密文rct_S’、解密密钥sk_Γ’和公开参数pk作为输入、输出消息m或 识别信息⊥的算法。

(Dec2)

Dec2算法是将加密文ct_S、解密密钥sk_Γ和公开参数pk作为输入、输出消息m或识别 信息⊥的算法。

＜第4-2.加密系统10＞

对执行CP-FCPRE方式的算法的加密系统10进行说明。

图5是执行CP-FCPRE方式的加密系统10的结构图。

加密系统10具备密钥生成装置100、加密装置200、解密装置300(重加密密钥生成 装置)、重加密装置400、重加密文解密装置500。

密钥生成装置100将安全参数λ和属性的格式n^→：＝(d；n₁、...、n_d；w₁、...、w_d； z₁、...、z_d)作为输入来执行Setup算法，生成公开参数pk和主密钥sk。

然后，密钥生成装置100将公开参数pk进行公开。另外，密钥生成装置100将属性集 合Γ作为输入来执行KG算法，生成解密密钥sk_Γ，秘密地发送给解密装置300。另外，密钥生 成装置100将属性集合Γ’作为输入来执行KG算法，生成解密密钥sk_Γ’，秘密地发送给重加 密文解密装置500。

加密装置200将消息m、访问结构S、S～和公开参数pk作为输入来执行Enc算法，生 成加密文ct_S。加密装置200向重加密装置400发送加密文ct_S。

解密装置300将解密密钥sk_Γ、访问结构S’、属性集合Γ～和公开参数pk作为输入 来执行RKG算法，生成重加密密钥rk_Γ、S’。解密装置300将重加密密钥rk_Γ、S’秘密地发送给重 加密装置400。

另外，解密装置300将公开参数pk、解密密钥sk_Γ和加密文ct_S作为输入来执行Dec2 算法，输出消息m或识别信息⊥。

重加密装置400将重加密密钥rk_Γ、S’、加密文ct_S和公开参数pk作为输入，来执行 REnc算法，生成重加密文rct_S’。重加密装置400向重加密文解密装置500发送重加密文 rct_S’。

重加密文解密装置500将解密密钥sk_Γ’、重加密文rct_S’和公开参数pk作为输入，来 执行Dec1算法，输出消息m或识别信息⊥。

＜第4-3.为了实现CP-FCPRE方式而采用的部件＞

为了实现CP-FCPRE方式，采用加密文策略的函数型加密(CP-FE)和一次性签名。因 为都是公知的技术，所以这里简单地说明在以下的说明中采用的方式。此外，关于CP-FE方 式，在专利文献1中记载了一例。

CP-FE方式具备Setup_CP-FE，KG_CP-FE，Enc_CP-FE，Dec_CP-FE这4个算法。

(Setup_CP-FE)

Setup_CP-FE算法是将安全参数λ和属性的格式n^→：＝(d；n₁、...、n_d)作为输入、输出 公开参数pk^CP-FE和主密钥sk^CP-FE的概率性算法。

(KG_CP-FE)

KG_CP-FE算法是将属性集合Γ：＝{(t、x^→_t)|x^→_t∈F_q^nt、1≤t≤d}、公开参数pk^CP-FE和 主密钥sk^CP-FE作为输入、输出解密密钥sk_Γ^CP-FE的概率性算法。

(Enc_CP-FE)

Enc_CP-FE算法是将消息m、访问结构S＝(M、ρ)和公开参数pk^CP-FE作为输入、输出加密 文ψ的概率性算法。

(Dec_CP-FE)

Dec_CP-FE算法是将加密文ψ、解密密钥sk_Γ^CP-FE和公开参数pk^CP-FE作为输入、输出消息 m或识别信息⊥的算法。

一次性签名方式具备SigKG、Sig、Ver这3个算法。

(SigKG)

SigKG算法是将安全参数λ作为输入、输出签名密钥sigk和验证密钥verk的概率性 算法。

(Sig)

Sig算法是将签名密钥sigk和消息m作为输入、输出签名S的概率性算法。

(Ver)

Ver算法是这样的算法：将验证密钥verk、消息m和签名S作为输入，当签名S相对于 验证密钥verk和消息m是合法时，输出1，当不是合法时，输出0。

＜第4-4.CP-FCPRE方式以及加密处理系统10的详细内容＞

根据图6至图17，说明CP-FCPRE方式以及执行CP-FCPRE方式的加密处理系统10的 功能和动作。

图6是示出密钥生成装置100的功能的功能框图。图7是示出加密装置200的功能的 功能框图。图8是示出解密装置300的功能的功能框图。图9是示出重加密装置400的功能的 功能框图。图10是示出重加密文解密装置500的功能的功能框图。

图11和图12是示出密钥生成装置100的动作的流程图。此外，图11是示出Setup算 法的处理的流程图，图12是示出KG算法的处理的流程图。图13是示出加密装置200的动作的 流程图，是示出Enc算法的处理的流程图。图14是示出解密装置300的动作的流程图，是示出 RKG算法的处理的流程图。图15是示出重加密装置400的动作的流程图，是示出REnc算法的 处理的流程图。图16是示出重加密文解密装置500的动作的流程图，是示出Dec1算法的处理 的流程图。图17是示出解密装置300的动作的流程图，是示出Dec2算法的处理的流程图。

对密钥生成装置100的功能和动作进行说明。

如图6所示，密钥生成装置100具备主密钥生成部110、主密钥存储部120、信息输入 部130、解密密钥生成部140、密钥发送部150(密钥输出部)。另外，解密密钥生成部140具备 CP-FE密钥生成部141、随机数生成部142、解密密钥k^＊生成部143。

首先，根据图11来说明Setup算法的处理。

(S101：标准正交基底生成步骤)

主密钥生成部110利用处理装置来计算式122-1、式122-2，生成参数param_n→、基 底B₀以及基底B^＊₀、基底B_t以及基底B^＊_t和基底H_t以及H^＊_t。

【式122-1】

(1)input1λ，

(2)

(3)N₀：＝9，N_t：＝n_t+w_t+z_t+1_对于t＝1，..，d，

gT:＝e(g，g)ψ

关于t＝0、...、d的各个整数t，执行(4)至(10)的处理，

(4)

(5)

(6)$\left(\begin{array}{c}{\overrightarrow{v}}_{t,1}\\ .\\ .\\ .\\ {\overrightarrow{v}}_{t,N_t}\end{array}\right):={\left(v_{t,i,j}\right)}_{i,j}:=\psi ·{\left(X_t^T\right)}^{-1}$

(7)

【式122-2】

(8)

(9)$\left(\begin{array}{c}{\overrightarrow{v}}_{t,1}^{\prime }\\ .\\ .\\ .\\ {\overrightarrow{v}}_{t,N_t}^{\prime }\end{array}\right):={\left(v_{t,i,j}^{\prime }\right)}_{i,j}:=\psi ·{\left(X_t^{\prime T}\right)}^{-1}$

(10)

(11)

即，主密钥生成部110执行以下的处理。

(1)主密钥生成部110利用输入装置来输入安全参数λ(1^λ)和属性的格式n→：＝ (d；n₁、...、n_d；w₁、...、w_d；z₁、...、z_d)。这里，d是1以上的整数，关于t＝1、...、d的各个整数 t，n_t是1以上的整数，w_t、z_t是0以上的整数。

(2)主密钥生成部110利用处理装置，将在(1)中输入的安全参数λ作为输入来执行 算法G_bpg，生成双线形配对组的参数param_G：＝(q、G、GT、g、e)的值。

(3)主密钥生成部110对N₀设定9，关于t＝1、...、d的各个整数t，对N_t设定n_t+w_t+z_t+ 1。另外，主密钥生成部110生成随机数ψ。另外，主密钥生成部110对g_T设定e(G、G)^ψ。

接着，主密钥生成部110关于t＝0、...、d的各个整数t，执行以下的(4)至(10)的处 理。

(4)主密钥生成部110将在(1)中输入的安全参数λ和在(3)中设定的N_t和在(2)中 生成的param_G：＝(q、G、GT、g、e)的值作为输入来执行算法Gdpvs，生成双对配对矢量空间的 参数param_Vt：＝(q、V_t、G_T、A_t、e)的值。

(5)主密钥生成部110将在(3)中设定的N_t和F_q作为输入，随机地生成线形转换X_t： ＝(χ_t、i、j)_i、j。此外，GL是GeneralLinear的缩写。即，GL是一般线形组，是矩阵式不为0的方 矩阵的集合，是关于乘法的组。另外，(χ_t、i、j)_i、j是与矩阵χ_t、i、j的后缀i、j相关的矩阵的意 思。这里，(χ_t、i、j)_i、j是i、j＝1、...、N_t。

(6)主密钥生成部110根据随机数ψ和线形转换X_t，生成(ν_t、i、j)_i、j：＝ψ·(X_t^T)^-1。此 外，(ν_t、i、j)_i、j也与(χ_t、i、j)_i、j同样是与矩阵ν_t、i、j的后缀i、j相关的矩阵这样的意思。这里， (ν_t、i、j)_i、j是i、j＝1、...、N_t。

(7)主密钥生成部110根据在(5)中生成的线形转换X_t，根据在(4)中生成的标准基 底A_t生成基底B_t。主密钥生成部110根据在(6)中生成的(ν_t、i、j)_i、j，根据在(4)中生成的标准 基底A_t生成基底b^＊_t。

(8)主密钥生成部110与(5)同样地将在(3)中设定的N_t和F_q作为输入，随机地生成 线形转换X’_t：＝(χ’_t、i、j)_i、j。

(9)主密钥生成部110与(6)同样地根据随机数ψ和线形转换X’_t，生成(ν’_t、i、j)_i、j： ＝ψ·(X’_t^T)^-1。

(10)主密钥生成部110基于在(8)中生成的线形转换X’_t，根据在(4)中生成的基底 A_t生成基底H_t。主密钥生成部110基于在(9)中生成的(ν’_t、i、j)_i、j，根据在(4)中生成的基底A_t生成基底H^＊_t。

(11)主密钥生成部110对param_n→设定在(4)中生成的{param_Vt}_{t＝0、...、d}和g_T。

(S102：CP-FE主密钥生成步骤)

主密钥生成部110利用处理装置来计算式123，生成函数型加密的公开参数pk^CP-FE和主密钥sk^CP-FE。

【式123】

$({\mathrm{pk}}^{CP-FE},{\mathrm{sk}}^{CP-FE})\stackrel{R}{\leftarrow }{\mathrm{Setup}}_{CP-FE}(1^{\lambda },\overrightarrow{n})$

(S103：公开参数生成步骤)

主密钥生成部110利用处理装置如式124所示地生成基底B₀的部分基底B＾₀、基底B_t的部分基底B＾_t、基底H_t的部分基底H＾_u、基底B^＊₀的部分基底B＾^＊₀、基底b^＊_t的部分基底B＾^＊_t、 基底H^＊_t的部分基底H＾^＊_u。

【式124】

对于＇t＝1，…，d，

对于＇u＝1，...，d，

对于′t＝1，...，d，

对于＇u＝1，...，d

主密钥生成部110组合公开参数pk^CP-FE、安全参数λ、param_n→、部分基底B＾₀、B＾_t、H ＾_u、B＾^＊₀、B＾^＊_t、H＾^＊_u，作为公开参数pk。

(S104：主密钥生成步骤)

主密钥生成部110将主密钥sk^CP-FE、基底矢量b^＊_0，1和式125所示的基底H＊_u的一部 分基底矢量作为主密钥sk。

【式125】

${\{h_{u,1}^{*},...,h_{u,n_u}^{*}\}}_{u=1,\mathrm{...},d}$

(S105：主密钥存储步骤)

主密钥存储部120将在(S103)中生成的公开参数pk存储于存储装置内。另外，主密 钥存储部120将在(S104)中生成的主密钥sk存储于存储装置内。

即，在(S101)至(S104)中，密钥生成装置100执行式126-1、式126-2所示的Setup算 法，来生成公开参数pk和主密钥sk。然后，在(S105)中，密钥生成装置100将所生成的公开参 数pk和主密钥sk存储于存储装置内。

此外，公开参数例如经由网络进行公开，成为加密装置200、解密装置300、重加密 装置400、重加密文解密装置500可取得的状态。

【式126-1】

$Setup(1^{\lambda },\overrightarrow{n}=(d;n_1,\mathrm{...},n_d;w_1,...,w_d;z_1,...,z_d\left)\right):$

N₀：＝9，N_t:＝n_t+w_t+z_t+1fort＝1，...，d，

g_T:＝e(g，g)ψ，

对于t＝0，...，d，

$\left(\begin{array}{c}{\overrightarrow{v}}_{t,1}\\ .\\ .\\ .\\ {\overrightarrow{v}}_{t,N_t}\end{array}\right):={\left(v_{t,i,j}\right)}_{i,j}:=\psi ·{\left(X_t^T\right)}^{-1},$

${\mathrm{param}}_{\overrightarrow{n}}:=\left({\left\{{\mathrm{param}}_t\right\}}_{t=0,\mathrm{...},d,g_T}\right),$

$\left(\begin{array}{c}{\overrightarrow{v}}_{t,1}^{\prime }\\ .\\ .\\ .\\ {\overrightarrow{v}}_{t,N_t}^{\prime }\end{array}\right):={\left(v_{t,i,j}^{\prime }\right)}_{i,j}:=\psi ·{\left(X_t^{\prime T}\right)}^{-1},$

【式126-2】

$({\mathrm{pk}}^{CP-FE},{\mathrm{sk}}^{CP-FE})\stackrel{R}{\leftarrow }{\mathrm{Setup}}_{CP-FE}(1^{\lambda },\overrightarrow{n})$

接着，根据图12，来说明KG算法的处理。

(S201：信息输入步骤)

信息输入部130利用输入装置来输入属性集合Γ：＝{(t、x^→_t：＝(x_t、1、...、x_t、n_t∈ F_q^nt{0^→}))|1≤t≤d}。此外，t可以不是1以上d以下的全部整数，而是1以上d以下的至少一 部分整数。另外，属性集合Γ例如设定有解密密钥sk_Γ的使用者的属性信息。

(S202：CP-FE解密密钥生成步骤)

CP-FE密钥生成部141利用处理装置来计算式127，来生成函数型加密的解密密钥 sk_Γ^CP-FE。

【式127】

${\mathrm{sk}}_{\Gamma }^{CP-FE}\stackrel{R}{\leftarrow }{\mathrm{KG}}^{CP-FE}({\mathrm{pk}}^{CP-FE},{\mathrm{sk}}^{CP-FE},\Gamma )$

(S203：随机数生成步骤)

随机数生成部142利用处理装置如式128所示地生成随机数。

【式128】

对于

对于u＝1，...，d

(S204：解密密钥k^＊生成步骤)

解密密钥k^＊生成部143利用处理装置如式129所示地生成解密密钥k^＊₀。

【式129】

此外，相对于式110所示的基底B和基底B＊，是式111。因此，式129表示以下的情 况：设定1作为基底B^＊₀的基底矢量b^＊_0，1的系数，设定δ作为基底矢量b^＊_0，2的系数，设定0作为 基底矢量b^＊_0，3、...、b^＊_0，6的系数，设定作为基底矢量b^＊_0，7、b^＊_0，8的系数，设定0作 为基底矢量b^＊_0，9的系数。

另外，解密密钥k^＊生成部143利用处理装置，关于属性集合Γ所包含的各个整数t， 如式130所示地生成解密密钥k^＊_t。

【式130】

对于

此外，式130表示以下的情况：设定δ_xt，1、...、δx_t，nt作为基底B^＊_t的基底矢量b ^＊_t，1、...、b^＊_t，nt的系数，设定0作为基底矢量b^＊_t、nt+1、...、b^＊_t，nt+wt的系数，设定作为基底矢量b^＊_t，nt+wt+1、...、b^＊_t，nt+wt+zt的系数，设定0作为基底矢量 b^＊_{t，nt+wt+zt+1}的系数。

另外，解密密钥k^＊生成部143利用处理装置，关于u＝1、...、d和i＝1、...、n_u的各 个整数u、i，如式131所示地生成解密密钥k^～＊_u、i。

【式131】

对于u＝1，…，d；i＝1，…，n_u

(S205：密钥发送步骤)

密钥发送部150例如通过通信装置经由网络秘密地向解密装置300发送将属性集 合Γ、函数型加密的解密密钥sk_Γ^CP-FE和解密密钥k^＊₀、k^＊_t、k^～＊_u、i作为要素的解密密钥sk_Γ。 当然，也可以利用其它方法向解密装置300发送解密密钥sk_Γ。

即，在(S201)至(S204)中，密钥生成装置100执行式132所示的KG算法，来生成解密 密钥sk_Γ。然后，在(S205)中，密钥生成装置100向解密装置300发送解密密钥sk_Γ。

【式132】

${\mathrm{sk}}_{\Gamma }^{CP-FE}\stackrel{R}{\leftarrow }{\mathrm{KG}}^{CP-FE}({\mathrm{pk}}^{CP-FE},{\mathrm{sk}}^{CP-FE},\Gamma ),$

对于u＝1，...，d，

对于

对于u＝1，...，d；；i＝1，...，n_u，

此外，密钥生成装置100在(S201)中输入设定有解密密钥sk_Γ’的使用者的属性信 息的属性集合Γ’：＝{(t、x’^→_t：＝(x’t、1、...、x’t、nt∈F_q^nt{0^→}))|1≤t≤d}，来执行KG 算法，生成解密密钥sk_Γ’。并且，密钥生成装置100向重加密文解密装置500发送解密密钥 sk_Γ’：＝(Γ’、sk_Γ’^CP-FE、k’^＊₀、{k’^＊_t}_{(t、x→t)∈Γ}、{k’^～＊_t、i}u＝_{1、...、d；i＝1、...、nu})。

对加密装置200的功能和动作进行说明。

如图7所示，加密装置200具备公开参数接收部210、信息输入部220、签名处理部 230、加密部240、加密文发送部250(加密文输出部)。另外，加密部240具备f矢量生成部241、 s矢量生成部242、随机数生成部243、加密文c生成部244。

根据图13，说明Enc算法的处理。

(S301：公开参数接收步骤)

公开参数接收部210例如通过通信装置经由网络来接收密钥生成装置100所生成 的公开参数pk。

(S302：信息输入步骤)

信息输入部220利用输入装置来输入访问结构S：＝(M、ρ)、S^～：＝(M^～、ρ^～)。此外，访 问结构S、S^～根据希望实现的系统的条件进行设定。另外，访问结构S的ρ例如设定有可对加 密文ct_S进行解密的用户的属性信息。另外，访问结构S^～的ρ^～例如设定有用于设定可重加密 的条件的信息。这里，ρ(i)＝(t、v^→_i：＝(v_i、1、...、v_i、nt)∈F_q^nt{0^→})(v_i、nt≠0)。另外，是ρ^～(i)＝(u、z^→i：＝(z_i、1、...、z_i、nu)∈F_q^nu{0^→})(z_i、nu≠0)。此外，M是L行r列的矩阵，M^～是L^～行 r^～列的矩阵。

另外，信息输入部220利用输入装置输入向解密装置300发送的消息m。

(S303：签名密钥生成步骤)

签名处理部230利用处理装置来计算式133，生成一次性签名的签名密钥sigk和验 证密钥verk。

【式133】

$(sigk,verk)\stackrel{R}{\leftarrow }SigKG\left(1^{\lambda }\right)$

(S304：f矢量生成步骤)

f矢量生成部241利用处理装置如式134所示地随机生成矢量f^→、f^～→。

【式134】

(S305：s矢量生成步骤)

s矢量生成部242利用处理装置如式135所示地生成矢量s^→T、s^～→T。

【式135】

${\overrightarrow{s}}^T:={(s_1,...,s_L)}^T:=M·{\overrightarrow{f}}^T,$

${\overrightarrow{\tilde{s}}}^T:={({\tilde{s}}_1,...,{\tilde{s}}_{\tilde{L}})}^T:=\tilde{M}·{\overrightarrow{\tilde{f}}}^T$

另外，s矢量生成部242利用处理装置如式136所示地生成值s₀、s^～₀。

【式136】

$s_0:=\overrightarrow{1}·{\overrightarrow{f}}^T,$

${\tilde{s}}_0:=\overrightarrow{1}·{\overrightarrow{\tilde{f}}}^T$

(S306：随机数生成步骤)

随机数生成部243利用处理装置如式137所示地生成随机数。

【式137】

对于i＝1，...，L，

对于

(S307：加密文c生成步骤)

加密文c生成部244利用处理装置如式138所示地生成加密文c₀。

【式138】

另外，加密文c生成部244利用处理装置，关于i＝1、...、L的各个整数i如式139所 示地生成加密文c_i。

【式139】

对于i＝1，...，L，

如果

如果

另外，加密文c生成部244利用处理装置如式140所示地生成加密文c_T。

【式140】

$c_T:=m·g_T^{\zeta }$

另外，加密文c生成部244利用处理装置如式141所示地生成加密文c^～₀。

【式141】

另外，加密文c生成部244利用处理装置，关于j＝1、...、L^～的各个整数j，如式142 所示地生成加密文c^～_j。

【式142】

对于

如果

如果

另外，加密文c生成部244利用处理装置如式143所示地生成加密文c^～_T。

【式143】

${\tilde{c}}_T:=m·g_T^{\tilde{\zeta }}$

(S308：签名生成步骤)

签名处理部230利用处理装置来计算式144，生成与加密文ct_S的要素C相应的签名 Sig。

【式144】

(S309：加密文发送步骤)

加密文发送部250例如通过通信装置经由网络向解密装置300发送将访问结构S、S ^～、加密文c₀、c₁、...、c_L、c_T、c^～₀、c^～₁、...、c^～_L～、c^～_T、验证密钥verk和签名Sig作为要素的加密 文ct_S。当然，也可以利用其它方法向解密装置300发送加密文ct_S。

即，在(S301)至(S308)中，加密装置200执行式145-1、式145-2所示的Enc算法，生 成加密文ct_S。并且，在(S309)中，加密装置200向解密装置300发送所生成的加密文ct_S。

【式145-1】

$(sigk,verk)\stackrel{R}{\leftarrow }SigKG\left(1^{\lambda }\right),$

${\overrightarrow{s}}^T:={(s_1,...,s_L)}^T:=M·{\overrightarrow{f}}^T,s_0:=\overrightarrow{1}·{\overrightarrow{f}}^T,$

${\overrightarrow{\tilde{s}}}^T:={({\tilde{s}}_1,...,{\tilde{s}}_{\tilde{L}})}^T:=\tilde{M}·{\overrightarrow{\tilde{f}}}^T,{\tilde{s}}_0:=\overrightarrow{1}·{\overrightarrow{\tilde{f}}}^T,$

$c_T:=m·g_T^{\zeta },{\tilde{c}}_T:=m·g_T^{\tilde{\zeta }},$

【式145-2】

对于i＝1，...，L，

如果

如果

对于

如果

如果

对解密装置300的功能和动作进行说明。

如图8所示，解密装置300具备解密密钥接收部310、信息输入部320、重加密密钥生 成部330、重加密密钥发送部340(重加密密钥输出部)、加密文接收部350、验证部360、增补 系数计算部370、配对运算部380、消息计算部390。另外，重加密密钥生成部330具备随机数 生成部331、转换信息W₁生成部332、转换信息W₁加密部333、解密密钥k^＊rk生成部334、转换部 335。另外，验证部360具备张成方案计算部361、签名验证部362。

这里，根据图14来说明RKG算法的处理。后面叙述Dec2算法。

(S401：解密密钥接收步骤)

解密密钥接收部310例如利用通信装置经由网络来接收从密钥生成装置100发送 的解密密钥sk_Γ。另外，解密密钥接收部310接收密钥生成装置100所生成的公开参数pk。

(S402：信息输入步骤)

信息输入部320利用输入装置来输入访问结构S’：＝(M’、ρ’)。此外，访问结构S’根 据希望实现的系统的条件进行设定。另外，访问结构S’的ρ’例如设定有可对重加密文rctS’ 进行解密的用户的属性信息。这里，ρ’(i)＝(t、v→’i：＝(v’i、1、...、v’_i、nt)∈F_q^nt{0^→}) (v’_i、nt≠0)。

另外，信息输入部130利用输入装置来输入属性集合Γ^～：＝{(u、y^→_u：＝(y_u、1、...、 y_u、nu∈F_q^nu{0^→}))|1≤u≤d}。此外，u可以不是1以上d以下的全部整数，而是1以上d以下的 至少一部分整数。另外，属性集合Γ～例如设定有表示可重加密的条件的属性信息。

(S403：随机数生成步骤)

随机数生成部331利用处理装置如式146所示地生成随机数。

【式146】

对于

对于

(S404：转换信息W₁生成步骤)

转换信息W₁生成部332利用处理装置如式147所示地生成转换信息W_1，0、W_1，t、W^～_1，u。

【式147】

对于

对于

(S405：转换信息W₁加密步骤)

转换信息W₁加密部333利用处理装置来计算式148，通过函数型加密对转换信息 W_1，0、W_1，t、W^～_1，u进行加密，生成加密转换信息ct^rk_S’(ψ^rk)。因为将访问结构S’作为输入而利用 函数型加密来加密转换信息W_1，0、W_1，t、W^～_1，u，所以，可对重加密文rct_S’进行解密的用户的属 性信息被设定并加密。

【式148】

(S406：解密密钥k^＊rk生成步骤)

解密密钥k^＊rk生成部334利用处理装置如式149所示地生成解密密钥k^＊rk₀、k ^＊rk_0，ran。

【式149】

另外，解密密钥k^＊rk生成部334利用处理装置，关于属性集合Γ所包含的各个整数 t，如式150所示地生成解密密钥k^＊rk_t、k^＊rk_t，ran。

【式150】

另外，解密密钥k^＊rk生成部334利用处理装置，关于属性集合Γ^～所包含的各个整数 u，如式151所示地生成解密密钥k^～＊rk_u。

【式151】

对于

$\left(\begin{array}{cc}{\tilde{k}}_u^{*rk}:={\Sigma }_{i=1}^{n_u}{\tilde{k}}_{u,i}^{*rk}& (u,{\overrightarrow{y}}_u)\in \tilde{\Gamma }\end{array}\right)$

(S407：转换步骤)

转换部335利用处理装置来计算式152，生成基底D＾^＊₀、D＾^＊_t、U＾^＊_u。

【式152】

对于t＝1，...，d，

对于u＝1，...，d

(S408：密钥发送步骤)

重加密密钥发送部340例如利用通信装置经由网络秘密地向重加密装置400发送 将属性集合Γ、Γ^～、访问结构S’、解密密钥k^＊rk₀、k^＊rk_0，ran、k^＊rk_t、k^＊rk_t，ran、k^～＊rk_u、加密转换信 息ct^rk_S’和基底D＾^＊₀、D＾^＊_t、U＾^＊_u作为要素的重加密密钥rk_Γ、S’。当然，可利用其它方法向重加 密装置400发送重加密密钥rk_Γ、S’。

即，在(S401)至(S407)中，解密装置300执行式153-1、式153-2所示的RKG算法，生 成重加密密钥rk_Γ、S’。然后，在(S408)中，解密装置300向重加密装置400发送所生成的重加 密密钥rk_Γ、S’。

【式153-1】

对于

对于

对于

对于

【式153-2】

对于

对于

对于

$\begin{array}{cc}{\tilde{k}}_u^{*rk}:={\Sigma }_{i=1}^{n_u}{\tilde{k}}_{u,i}^{*rk}& (u,{\overrightarrow{y}}_u)\in \tilde{\Gamma }\end{array},$

对于t＝1，...，d，

对于·u＝1，...，d，

对重加密装置400的功能和动作进行说明。

如图9所示，重加密装置400具备公开参数接收部410、加密文接收部420、重加密密 钥接收部430、验证部440、加密部450、重加密文发送部460(重加密文输出部)。另外，验证部 440具备张成方案计算部441、签名验证部442。另外，加密部450具备随机数生成部451、f矢 量生成部452、s矢量生成部453、转换信息W₂生成部454、转换信息W₂加密部455、加密文c^renc生成部456、解密密钥k^＊renc生成部457。

根据图15，来说明REnc算法的处理。

(S501：公开参数接收步骤)

公开参数接收部410例如利用通信装置经由网络来接收密钥生成装置100所生成 的公开参数pk。

(S502：加密文接收步骤)

加密文接收部420例如利用通信装置经由网络来接收加密装置200所发送的加密 文ct_S。

(S503：重加密密钥接收步骤)

重加密密钥接收部430例如利用通信装置经由网络来接收从解密装置300发送的 重加密密钥rk_Γ、S’。

(S504：张成方案计算步骤)

张成方案计算部441利用处理装置，来判定加密文ct_S所包含的访问结构S是否受 理重加密密钥rk_Γ，S’所包含的Γ，并且判定加密文ct_S所包含的访问结构S^～是否受理重加密 密钥rk_Γ，S’所包含的Γ^～。访问结构S是否受理Γ以及访问结构S^～是否受理Γ^～的判定方法如 在实施方式1的“第3.用于实现FCPRE的概念”中所说明的那样。

张成方案计算部441在访问结构S受理Γ且访问结构S^～受理Γ^～的情况下(在S504 中为受理)，使处理前进至(S505)。另一方面，在访问结构S拒绝Γ或访问结构S^～拒绝Γ^～的 情况下(在S504中为拒绝)，结束处理。

(S505：签名验证步骤)

签名验证部442利用处理装置，来判定计算式154的结果是否是1。签名验证部442 在结果是1的情况下(在S505中为合法)，使处理前进至(S506)。另一方面，签名验证部442在 结果是0的情况下(在S505中为非法)，结束处理。

【式154】

Ver(verk,C,Sig)

这里，

(S506：随机数生成步骤)

随机数生成部451利用处理装置，如式155所示地生成随机数。

【式155】

对于

对于

对于i＝1，...，L，

对于

(S507：f矢量生成步骤)

f矢量生成部452利用处理装置，如式156所示随机地生成矢量f^→’、f^～→’。

【式156】

(S508：s矢量生成步骤)

s矢量生成部453利用处理装置，如式157所示地生成矢量s^～→’T、s^～→’T。

【式157】

${\overrightarrow{s}}^{\prime T}:={(s_1^{\prime },...,s_L^{\prime })}^T:=M·{\overrightarrow{f}}^{\prime T},$

${\overrightarrow{\tilde{s}}}^{\prime T}:={({\tilde{s}}_1^{\prime },...,{\tilde{s}}_L^{\prime })}^T:=\tilde{M}·{\overrightarrow{\tilde{f}}}^{\prime T}$

另外，s矢量生成部453利用处理装置，如式158所示地生成值s₀’、s^～₀’。

【式158】

$s_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{f}}^{\prime T},$

${\tilde{s}}_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{\tilde{f}}}^{\prime T}$

(S509：转换信息W₂生成步骤)

转换信息W₂生成部454利用处理装置，如式159所示地生成转换信息W₂。

【式159】

(S510：转换信息W₂加密步骤)

转换信息W₂加密部455利用处理装置来计算式160，通过函数型加密对转换信息W₂进行加密，来生成加密转换信息ct^renc_S’(ψ^renc)。因为转换信息W₂将访问结构S’作为输入而利 用函数型加密进行加密，所以，可对重加密文rct_S’进行解密的用户的属性信息被设定并加 密。

【式160】

(S511：加密文c^renc生成步骤)

加密文c^renc生成部456利用处理装置，如式161所示地生成加密文c^～renc₀。

【式161】

另外，加密文c^renc生成部456利用处理装置，关于i＝1、...、L的各个整数i，如式 162所示地生成加密文c^renc_i。

【式162】

对于i＝1，...，L，

如果

如果

另外，加密文c^renc生成部456利用处理装置，如式163所示地生成加密文c^～renc_T。

【式163】

${\tilde{c}}_T^{renc}:=c_T·{\tilde{c}}_T·g_T^{{\zeta }^{\prime }}$

另外，加密文c^renc生成部456利用处理装置，关于j＝1、...、L^～的各个整数i，如式 164所示地生成加密文c^～renc_j。

【式164】

对于

如果

如果

(S512：解密密钥k^＊renc生成步骤)

解密密钥k^＊renc生成部457利用处理装置，如式165所示地生成解密密钥k^＊renc₀。

【式165】

另外，解密密钥k^＊renc生成部457利用处理装置，关于属性集合Γ所包含的各个整 数t，如式166所示地生成解密密钥k^＊renc_t。

【式166】

另外，解密密钥k^＊renc生成部457利用处理装置，关于属性集合Γ～所包含的各个 整数u，如式167所示地生成解密密钥k^～＊renc_u。

【式167】

对于

(S513：重加密文发送步骤)

重加密文发送部460例如利用通信装置经由网络秘密地向重加密文解密装置500 发送将访问结构S’、S、S^～、属性集合Γ、Γ^～、解密密钥k^＊renc₀、k^＊renc_t、k^～＊renc_u、加密文c^～renc₀、 c^renc_i、c^～renc_T、c^～renc_j、加密转换信息ct^rk_S’和加密转换信息ct^renc_S’作为要素的重加密文 rct_S’。当然，也可以利用其它方法向重加密文解密装置500发送重加密文rct_S’。

即，在(S501)至(S512)中，重加密装置400执行式168-1、式168-2、式168-3所示的 REnc算法，生成重加密文rct_S’。然后，在(S513)中，重加密装置400向重加密文解密装置500 发送所生成的重加密文rct_S’。

【式168-1】

如果受理Γ、受理且Ver(verk，C，Sig)＝1

则执行以下

对于

对于

$s_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{f}}^{\prime T},$

${\tilde{c}}_T^{renc}:=c_T·{\tilde{c}}_T·g_T^{{\zeta }^{\prime }},$

【式168-2】

对于i＝1，...，L，

如果

如果

对于

如果

如果

【式168-3】

对于

对于

对重加密文解密装置500的功能和动作进行说明。

如图10所示，重加密文解密装置500具备解密密钥接收部510、加密文接收部520、 张成方案计算部530、增补系数计算部540、转换信息生成部550、转换部560、配对运算部 570、消息计算部580。此外，将配对运算部570和消息计算部580总称为解密部。

根据图16来说明Dec1算法的处理。

(S601：解密密钥接收步骤)

解密密钥接收部510例如利用通信装置经由网络来接收从密钥生成装置100发送 的解密密钥sk_Γ’。另外，解密密钥接收部310接收密钥生成装置100所生成的公开参数pk。

(S602：加密文接收步骤)

加密文接收部520例如利用通信装置经由网络来接收重加密装置400所发送的重 加密文rct_S’。

(S603：张成方案计算步骤)

张成方案计算部530利用处理装置来判定重加密文rct_S’所包含的访问结构S’是否 受理解密密钥sk_Γ’所包含的Γ’，并且判定重加密文rct_S’所包含的访问结构S^～是否受理重 加密文rct_S’所包含的Γ^～。访问结构S’是否受理Γ’以及访问结构S^～是否受理Γ^～的判定方 法如在实施方式1的“第3.用于实现FCPRE的概念”中所说明的那样。

张成方案计算部530在访问结构S’受理Γ’且访问结构S^～受理Γ^～的情况下(在 S603中为受理)，使处理前进至(S604)。另一方面，在访问结构S’拒绝Γ’或访问结构S^～拒绝 Γ^～的情况下(在S603中为拒绝)，结束处理。

(S604：增补系数计算步骤)

增补系数计算部540利用处理装置，来计算作为式169的I、J和常数(增补系数) {α_i}_i∈I、{α^～_j}_j∈J。

【式169】

其中M_i是M的第i行，的第j行

并且，

(S605：转换信息生成步骤)

转换信息生成部550利用处理装置，如式170所示地生成转换信息W_1，0、W_1，t、W^～_1，u、 W₂。

【式170】

(S606：转换步骤)

转换部560利用处理装置，如式171所示地生成解密密钥k^＊₀、k^＊_t、k^～＊_u，并且生成加 密文c^～₀。

【式171】

$k_0^{*}:=k_0^{*renc}{W}_{1,0}^{-1},$

${\tilde{c}}_0:={\tilde{c}}_0^{renc}{W}_2^{-1}$

(S607：配对运算步骤)

配对运算部570利用处理装置，来计算式172，生成会话密钥K^～。

【式172】

(S608：消息计算步骤)

消息计算部580利用处理装置，来计算m’＝c^～renc_T/K^～，生成消息m’(＝m)。

即，在(S601)至(S608)中，重加密文解密装置500执行式173-1，式173-2所示的 Dec1算法，生成消息m’(＝m)。

【式173-1】

如果受理Γ′并且受理

那么计算I，J和{α_i}_i∈I，

其中M_i是M的第i行，的第j行

并且

【式173-2】

$k_0^{*}:=k_0^{*renc}{W}_{1,0}^{-1},$

对于

对于

${\tilde{c}}_0:={\tilde{c}}_0^{renc}{W}_2^{-1},$

$m^{\prime }:={\tilde{c}}_T^{renc}/\tilde{K},$

returnm＇

根据图17，来说明Dec2算法的处理。

(S701：解密密钥接收步骤)

解密密钥接收部310例如利用通信装置经由网络接收从密钥生成装置100发送的 解密密钥sk_Γ。另外，解密密钥接收部310接收密钥生成装置100所生成的公开参数pk。

(S702：加密文接收步骤)

加密文接收部350例如利用通信装置经由网络接收重加密装置400所发送的加密 文ct_S。

(S703：张成方案计算步骤)

张成方案计算部361利用处理装置判定加密文ct_S所包含的访问结构S是否受理解 密密钥sk_Γ所包含的Γ。访问结构S是否受理Γ的判定方法是如实施方式1的“第3.用于实现 FCPRE的概念”中所说明的那样。

张成方案计算部361在访问结构S受理Γ的情况下(在S703中为受理)，使处理前进 至(S704)。另一方面，在访问结构S拒绝Γ的情况下(在S703中为拒绝)，结束处理。

(S704：签名验证步骤)

签名验证部362利用处理装置判定计算式174的结果是否是1。签名验证部362在结 果是1的情况下(在S704中为合法)，使处理前进至(S705)。另一方面，签名验证部362在结果 是0的情况下(在S704中为非法)，结束处理。

【式174】

Ver(verk，C，Sig)

这里，

(S705：增补系数计算步骤)

增补系数计算部370利用处理装置，计算成为式175的I和常数(增补系数){α_i}i∈ I。

【式175】

其中M_i是M的第i行

(S706：配对运算步骤)

配对运算部380利用处理装置来计算式176，生成会话密钥K。

【式176】

(S707：消息计算步骤)

消息计算部390利用处理装置来计算m’＝c_T/K，生成消息m’(＝m)。

即，在(S701)至(S707)中，解密装置300执行式177所示的Dec2算法，生成消息m’ (＝m)。

【式177】

If受理

并且Ver(verk，C，Sig)＝1，

那么计算I和{α_i}_i∈I

$\overrightarrow{1}=\underset{i\in I}{\Sigma }{\alpha }_i{M}_i$

其中M_i是M的第i行

m＇＝c_T/K，

returnm＇.

如以上那样，实施方式1的加密系统可实现CP-FCPRE方式。因此，可利用1个重加密 密钥，对各个种类的用户的集合转发加密文。此外，还能够指定对重加密的加密文进行指定 的条件。

此外，在上述说明中，解密装置300兼作重加密密钥生成装置，解密装置300不仅执 行Dec2算法，还执行RKG算法。但是，解密装置300和重加密密钥生成装置也可以是分开的装 置。在此情况下，解密装置300执行Dec2算法，重加密密钥生成装置执行RKG算法。因此，在此 情况下，解密装置300具备执行Dec2算法所需的功能结构，重加密密钥生成装置具备执行 RKG算法所需的功能结构。

另外，中上述说明中，对N_t设定n_t+w_t+z_t+1。但是，也可以对N_t设定n_t+w_t+z_t+β_t。这 里，β_t是0以上的整数。

另外，在上述说明中，对N₀设定9。但是，也可以对N₀设定1+1+2+w₀+z₀+β₀。这里，w₀、 z₀、β₀是0以上的整数。

另外，在上述说明中，在S511内生成的加密文c^～renc₀的π’(verk，1)是追加信息Η， 在S512内生成的解密密钥k^＊renc₀的σ(-1，verk)是追加信息Θ。追加信息Η、Θ是对应的，利 用在S607中执行的配对运算来抵消。

实施方式2.

在实施方式1中，说明了CP-FCPRE方式。在实施方式2中，说明密钥策略的FCPRE方 式(Key-PolicyFCPRE、KP-FCPRE)方式。

首先，说明KP-FCPRE方式的基本结构。接着，说明实现该KP-FCPRE方式的加密处理 系统10的基本结构。然后，说明为了实现该KP-FCPRE方式而采用的部件。然后，详细地说明 该实施方式的KP-FCPRE方式以及加密处理系统10。

对KP-FCPRE方式的结构简单地进行说明。此外，所谓KP(密钥策略)是指，在密钥中 填入Policy即填入访问结构。

＜第1-1.KP-FCPRE方式的基本结构＞

KP-FCPRE方式具备Setup、KG、Enc、RKG、REnc、Dec1、Dec2这7个算法。

(Setup)

Setup算法是将安全参数λ和属性的格式n^→：＝(d；n₁、...、n_d；w₁、...、w_d；z₁、...、 z_d)作为输入、输出公开参数pk和主密钥sk的概率性算法。

(KG)

KG算法是将访问结构S＝(M，ρ)、公开参数pk和主密钥sk作为输入来输出解密密钥 sk_S的概率性算法。

(Enc)

Enc算法是将消息m、属性集合Γ：＝{(t，x^→_t)|x^→_t∈F_q^nt、1≤t≤d}、Γ^～：＝{(u、y ^→_u)|y^→_u∈Fq^nu、1≤y≤d}和公开参数pk作为输入、输出加密文ct_Γ的概率性算法。

(RKG)

RKG算法是将解密密钥sk_S、属性集合Γ’：＝{(t，x’^→_t)|x’^→_t∈F_q^nt、1≤t≤d}、访问 结构S^～＝(M^～，ρ^～)和公开参数pk作为输入、输出重加密密钥rk_S、Γ’的概率性算法。

(REnc)

REnc算法是将加密文ct_Γ、重加密密钥rk_S、Γ’和公开参数pk作为输入、输出重加密 文rct_Γ’的概率性算法。

(Dec1)

Dec1算法是将重加密文rct_Γ’、解密密钥sk_S’和公开参数pk作为输入、输出消息m或 识别信息⊥的算法。

(Dec2)

Dec2算法是将加密文ct_Γ、解密密钥sk_S和公开参数pk作为输入、输出消息m或识别 信息⊥的算法。

＜第1-2.加密处理系统10＞

说明执行KP-FCPRE方式的算法的加密处理系统10。

图18是执行KP-FCPRE方式的加密处理系统10的结构图。

加密处理系统10与图5所示的加密处理系统10同样地具备：密钥生成装置100、加 密装置200、解密装置300(重加密密钥生成装置)、重加密装置400、重加密文解密装置500。

密钥生成装置100将安全参数λ和属性的格式n^→：＝(d；n₁、...、n_d；w₁、...、w_d； z₁、...、z_d)作为输入来执行Setup算法，生成公开参数pk和主密钥sk。

然后，密钥生成装置100对公开参数pk进行公开。另外，密钥生成装置100将访问结 构S作为输入来执行KG算法，生成解密密钥sk_S，秘密地发送给解密装置300。另外，密钥生成 装置100将访问结构S’作为输入来执行KG算法，生成解密密钥sk_S’，秘密地发送给重加密文 解密装置500。

加密装置200将消息m、属性集合Γ、Γ^～和公开参数pk作为输入来执行Enc算法，生 成加密文ct_Γ。加密装置200向重加密装置400发送加密文ct_Γ。

解密装置300将公开参数pk、解密密钥sk_S、属性集合Γ’和访问结构S^～作为输入来 执行RKG算法，生成重加密密钥rk_S、Γ’。解密装置300向重加密装置400秘密地发送重加密密 钥rk_S、Γ’。

另外，解密装置300将公开参数pk、解密密钥sk_S和加密文ct_Γ作为输入来执行Dec2 算法，输出消息m或识别信息⊥。

重加密装置400将公开参数pk、重加密密钥rk_S、Γ’和加密文ct_Γ作为输入，执行REnc 算法，生成重加密文rct_Γ’。重加密装置400向重加密文解密装置500发送重加密文rct_Γ’。

重加密文解密装置500将公开参数pk、解密密钥sk_S’和重加密文rct_Γ’作为输入，来 执行Dec1算法，输出消息m或识别信息⊥。

＜第1-3.为了实现KP-FCPRE方式而采用的部件＞

为了实现KP-FCPRE方式，采用密钥策略的函数型加密(KP-FE)和一次性签名。因为 都是公知的技术，所以，这里简单地说明在以下的说明中采用的方式。此外，关于KP-FE方 式，在专利文献1中记载了一例。另外，关于一次性签名，因为如在实施方式1中说明的那样， 所以，这里省略说明。

KP-FE方式具备Setup_KP-FE、KG_KP-FE、Enc_KP-FE、Dec_KP-FE这4个算法。

(Setup_KP-FE)

Setup_KP-FE算法是将安全参数λ和属性的格式n^→：＝(d；n₁、...、n_d)作为输入、输出 公开参数pk_KP-FE和主密钥sk_KP-FE的概率性算法。

(KG_KP-FE)

KG_KP-FE算法是将访问结构S＝(M，ρ)、公开参数pk^KP-FE和主密钥sk^KP-FE作为输入、输 出解密密钥sk_S^KP-FE的概率性算法。

(Enc_KP-FE)

Enc_KP-FE算法是将消息m、属性集合Γ：＝{(t，x^→_t)|x^→_t∈F_q^nt、1≤t≤d}和公开参数 pk^KP-FE作为输入、输出加密文ψ的概率性算法。

(Dec_KP-FE)

Dec_KP-FE算法是将加密文ψ、解密密钥sk_S^KP-FE和公开参数pk^KP-FE作为输入、输出消息 m或识别信息⊥的算法。

＜第1-4.KP-FCPRE方式以及加密处理系统10的详细内容＞

根据图19至图29，来说明KP-FCPRE方式以及执行KP-FCPRE方式的加密处理系统10 的功能和动作。

图19是示出密钥生成装置100的功能的功能框图。图20是示出加密装置200的功能 的功能框图。图21是示出解密装置300的功能的功能框图。图22是示出重加密装置400的功 能的功能框图。图23是示出重加密文解密装置500的功能的功能框图。

图24是示出密钥生成装置100的动作的流程图，是示出KG算法的处理的流程图。图 25是示出加密装置200的动作的流程图，是示出Enc算法的处理的流程图。图26是示出解密 装置300的动作的流程图，是示出RKG算法的处理的流程图。图27是示出重加密装置400的动 作的流程图，是示出REnc算法的处理的流程图。图28是示出重加密文解密装置500的动作的 流程图，是示出Dec1算法的处理的流程图。图29是示出解密装置300的动作的流程图，是示 出Dec2算法的处理的流程图。

说明密钥生成装置100的功能和动作。

如图19所示，密钥生成装置100具备主密钥生成部110、主密钥存储部120、信息输 入部130、解密密钥生成部140、密钥发送部150(密钥输出部)。另外，解密密钥生成部140具 备随机数生成部142、解密密钥k^＊生成部143、KP-FE密钥生成部144、f矢量生成部145、s矢量 生成部146。

因为Setup算法的处理与在实施方式1中说明的Setup算法的处理相同，所以，省略 说明。其中，在实施方式1的S102内，生成了CP-FE中的公开参数pk^CP-FE和主密钥sk^CP-FE，但在 实施方式2中，生成KP-FE的公开参数pk^KP-FE和主密钥sk^KP-FE。

即，密钥生成装置100执行式178-1、式178-2所示的Setup算法，生成公开参数pk和 主密钥sk。

【式178-1】

N₀：＝9，N_t：＝n_t+w_t+z_t+1fort＝1，...，d，g_T:＝e(g，g)ψ，

fort＝0，...，d，

$\left(\begin{array}{c}{\overrightarrow{v}}_{t,1}\\ .\\ .\\ .\\ {\overrightarrow{v}}_{t,N_t}\end{array}\right):={\left(v_{t,i,j}\right)}_{i,j}:=\psi ·{\left(X_t^T\right)}^{-1},$

${\mathrm{param}}_{\overrightarrow{n}}:=\left({\left\{{\mathrm{param}}_t\right\}}_{t=0,\mathrm{...},d,g_T}\right),$

$\left(\begin{array}{c}{\overrightarrow{v}}_{t,1}^{\prime }\\ .\\ .\\ .\\ {\overrightarrow{v}}_{t,N_t}^{\prime }\end{array}\right):={\left(v_{t,i,j}^{\prime }\right)}_{i,j}:=\psi ·{\left(X_t^{\prime T}\right)}^{-1},$

【式178-2】

根据图24，来说明KG算法的处理。

(S801：信息输入步骤)

信息输入部130利用输入装置来输入访问结构S：＝(M，ρ)。此外，访问结构S的矩阵 M根据希望实现的系统的条件进行设定。另外，访问结构S的ρ例如设定有解密密钥sk_S的使 用者的属性信息。这里，ρ(i)＝(t、v^→_i：＝(vi.1、...、vi.nt)∈F_q^nt{0^→})(v_i，nt≠0)。

(S802：KP-FE解密密钥生成步骤)

KP-FE密钥生成部144利用处理装置来计算式179，生成函数型加密。

【式179】

(S803：f矢量生成步骤)

f矢量生成部145利用处理装置，如式180所示地随机生成矢量f^→。

【式180】

(S804：s矢量生成步骤)

s矢量生成部146利用处理装置，如式181所示地生成矢量s^→T：＝(s₁、...、s_L)^T。

【式181】

另外，s矢量生成部146利用处理装置，如式182所示地生成值s₀。

【式182】

$s_0:=\overrightarrow{1}·{\overrightarrow{f}}^T$

(S805：随机数生成步骤)

随机数生成部142利用处理装置，如式183所示地生成随机数。

【式183】

(S806：解密密钥k^＊生成步骤)

解密密钥k^＊生成部143利用处理装置，如式184所示地生成解密密钥k^＊₀。

【式184】

另外，解密密钥k^＊生成部143利用处理装置，关于i＝1、...、L的各个整数i，如式 185所示地生成解密密钥k^＊_i。

【式185】

fori＝1，...，L，

if

if

(S807：密钥发送步骤)

密钥发送部150例如利用通信装置经由网络秘密地向解密装置300发送将访问结 构S、解密密钥sk_S^KP-FE和解密密钥k^＊₀、k^＊_i作为要素的解密密钥sk_S。当然，也可利用其它方法 向解密装置300发送解密密钥sk_S。

即，在(S801)至(S806)中，密钥生成装置100执行式186所示的KG算法，来生成解密 密钥sk_S。然后，在(S807)中，密钥生成装置100向解密装置300发送所生成的解密密钥sk_S。

【式186】

${\overrightarrow{s}}^T:={(s_1,...,s_L)}^T:=M·{\overrightarrow{f}}^T,s_0:=\overrightarrow{1}·{\overrightarrow{f}}^T,$

fori＝1，...，L，

if

if

此外，密钥生成装置100在(S801)中，输入设定有解密密钥sk_S’的使用者的属性信 息的访问结构S’：＝(M’，ρ’)，来执行KG算法，生成解密密钥sk_S’。然后，向重加密文解密装置 500发送解密密钥sk_S’：＝(S’、sk_S^KP-FE、k’^＊₀、k’^＊_i)。这里，ρ’(i)＝(t、v^→’i：＝(v’_i.1、...、 v’_i.nt)∈F_q^nt{0^→})(v’_i，nt≠0)。

说明加密装置200的功能和动作。

如图20所示，加密装置200具备公开参数接收部210、信息输入部220、签名处理部 230、加密部240、加密文发送部250(加密文输出部)。另外，加密部240具备随机数生成部 243、加密文c生成部244。

根据图25，说明Enc算法的处理。

(S901：公开参数接收步骤)

公开参数接收部210例如利用通信装置经由网络接收密钥生成装置100所生成的 公开参数pk。

(S902：信息输入步骤)

信息输入部220利用输入装置，输入属性集合Γ：＝{(t、x^→_t：＝(x_t.1、...、x_t.nt∈ F_q^nt))|1≤t≤d}、Γ^～：＝{(u、y^→_u)|y^→_u∈F_q^nu、1≤y≤d}。此外，t、u可以不是1以上d以下的全 部整数，而是1以上d以下的至少一部分整数。另外，属性集合Γ例如设定有可解密的用户的 属性信息。另外，属性集合Γ^～例如设定有用于设定可重加密的条件的信息。

另外，信息输入部220利用输入装置，输入向解密装置300发送的消息m。

(S903：签名密钥生成步骤)

签名处理部230利用处理装置，计算式187，生成一次性签名的签名密钥sigk和验 证密钥verk。

【式187】

$(sigk,verk)\stackrel{R}{\leftarrow }SigKG\left(1^{\lambda }\right)$

(S904：随机数生成步骤)

随机数生成部243利用处理装置，如式188所示地生成随机数。

【式188】

(S905：加密文c生成步骤)

加密文c生成部234利用处理装置，如式189所示地生成加密文c₀。

【式189】

另外，加密文c生成部234利用处理装置，关于属性信息Γ所包含的各个整数t，如 式190所示地生成加密文c_t。

【式190】

另外，加密文c生成部234利用处理装置，如式191所示地生成加密文c_T。

【式191】

$c_T:=m·g_T^{\zeta }$

另外，加密文c生成部234利用处理装置，如式192所示地生成加密文c^～₀。

【式192】

另外，加密文c生成部234利用处理装置，如式193所示地生成加密文c^～_u。

【式193】

另外，加密文c生成部234利用处理装置，如式194所示地生成加密文c^～_T。

【式194】

${\tilde{c}}_T:=m·g_T^{\tilde{\zeta }}$

(S906：签名生成步骤)

签名处理部230利用处理装置来计算式195，生成与加密文ct_Γ的要素C相应的签名 Sig。

【式195】

$\left(\begin{array}{c}Sig\stackrel{R}{\leftarrow }Sig(sigk,C:=(\Gamma ,\tilde{\Gamma },c_0,{\left\{c_t\right\}}_{(t,{\overrightarrow{x}}_t)\in \Gamma },\\ {\left\{{\tilde{c}}_u\right\}}_{(u,{\overrightarrow{y}}_u)\in \tilde{\Gamma }},c_T\left)\right)\end{array}\right)$

(S907：加密文发送步骤)

加密文发送部250例如利用通信装置经由网络向解密装置300发送将属性集合Γ、 Γ^～、加密文c₀、c_t、c_T、c^～_u、验证密钥verk和签名Sig作为要素的加密文ct_Γ。当然，可利用其 它方法向解密装置300发送加密文ct_Γ。

即，在(S901)至(S906)中，加密装置200执行式196所示的Enc算法，来生成加密文 ct_Γ。并且，在(S907)中，加密装置200向解密装置300发送所生成的加密文ct_Γ。

【式196】

$(sigk,verk)\stackrel{R}{\leftarrow }SigKG\left(1^{\lambda }\right),$

$c_T:=m·g_T^{\zeta },{\tilde{c}}_T:=m·g_T^{\tilde{\zeta }},$

$\left(\begin{array}{c}Sig\stackrel{R}{\leftarrow }Sig(sigk,C:=(\Gamma ,\tilde{\Gamma },c_0,{\left\{c_t\right\}}_{(t,{\overrightarrow{x}}_t)\in \Gamma },\\ {\left\{{\tilde{c}}_u\right\}}_{(u,{\overrightarrow{y}}_u)\in \tilde{\Gamma }},c_T\left)\right),\end{array}\right)$

${\mathrm{ct}}_{\Gamma }:=(\Gamma ,\tilde{\Gamma },c_0,{\left\{c_t\right\}}_{(t,{\overrightarrow{x}}_t)\in \Gamma },{\left\{{\tilde{c}}_u\right\}}_{(u,{\overrightarrow{y}}_u),\in \tilde{\Gamma }},c_T,verk,Sig).$

说明解密装置300的功能和动作。

如图21所示，解密装置300具备解密密钥接收部310、信息输入部320、重加密密钥 生成部330、重加密密钥发送部340(重加密密钥输出部)、加密文接收部350、验证部360、增 补系数计算部370、配对运算部380、消息计算部390。另外，重加密密钥生成部330具备随机 数生成部331、转换信息W₁生成部332、转换信息W₁加密部333、解密密钥k^＊rk生成部334、转换 部335、f矢量生成部336、s矢量生成部337。另外，验证部360具备张成方案计算部361、签名 验证部362。

这里，根据图26，说明RKG算法的处理。后面叙述Dec2算法。

(S1001：解密密钥接收步骤)

解密密钥接收部310例如利用通信装置经由网络接收从密钥生成装置100发送的 解密密钥sk_S。另外，解密密钥接收部310接收密钥生成装置100所生成的公开参数pk。

(S1002：信息输入步骤)

信息输入部320利用输入装置，输入属性集合Γ’：＝{(t、x’^→_t：＝(x’_t.1、...、x’_t.nt∈F_q^nt{0^→}))|1≤t≤d}。此外，t可以不是1以上d以下的全部整数，而是1以上d以下的至少 一部分整数。另外，属性集合Γ’例如设定有能够对重加密文rct_Γ’进行解密的用户的属性 信息。

另外，信息输入部320利用输入装置，输入访问结构S^～：＝(M^～，ρ^～)。此外，访问结构 S^～的矩阵M^～根据希望实现的系统的条件进行设定。另外，访问结构S^～的ρ^～例如设定有表示 可重加密的条件的属性信息。这里，ρ(i)＝(t、v^→_i：＝(v_i.1、...、v_i.nt)∈F_q^nt{0^→})(v_i，nt≠ 0)。

(S1003：随机数生成步骤)

随机数生成部331利用处理装置，如式197所示地生成随机数。

【式197】

(S1004：f矢量生成步骤)

f矢量生成部336利用处理装置，如式198所示地随机生成矢量f^～→。

【式198】

(S1005：s矢量生成步骤)

s矢量生成部337利用处理装置，如式199所示地生成矢量S^～→T。

【式199】

${\overrightarrow{\tilde{s}}}^T:={({\tilde{s}}_1,...,{\tilde{s}}_{\tilde{L}})}^T:=\tilde{M}·{\overrightarrow{\tilde{f}}}^T$

另外，s矢量生成部337利用处理装置，如式200所示地生成值s^～₀。

【式200】

(S1006：转换信息W₁生成步骤)

转换信息W₁生成部332利用处理装置，如式201所示地生成转换信息W_1，0、W_1，i、W ^～_1，j。

【式201】

(S1007：转换信息W₁加密步骤)

转换信息W₁加密部333利用处理装置来计算式202，通过函数型加密对转换信息 W_1，0、W_1，i、W^～_1，j进行加密，生成加密转换信息ct^rk_Γ’(ψ^rk)。转换信息W_1，0、W_1，i、W^～_1，j将属性信息 Γ’作为输入，利用函数型加密进行加密，因此，可对重加密文rct_Γ’进行解密的用户的属性 信息被设定并加密。

【式202】

(S1008：解密密钥k^＊rk生成步骤)

解密密钥k^＊rk生成部334利用处理装置，如式203所示地生成解密密钥k^＊rk₀。

【式203】

另外，解密密钥k^＊rk生成部334利用处理装置，关于i＝1、...、L的各个整数i，如式 204所示地生成解密密钥k^＊rk_i。

【式204】

另外，解密密钥k^＊rk生成部334利用处理装置，关于j＝1、...、L^～的各个整数j，如式 205所示地生成解密密钥k^～＊rk_j。

【式205】

for

if

if

(S1009：转换步骤)

转换部335利用处理装置来计算式206，生成基底D^＾＊₀、D^＾＊_i、U^＾＊_j。

【式206】

fort＝1，...，L，

for

(S1010：密钥发送步骤)

重加密密钥发送部340例如利用通信装置经由网络秘密地向重加密装置400发送 将访问结构S、S～、属性集合Γ’、解密密钥k^＊rk₀、k^＊rk_i、k^～＊rk_j、加密转换信息ct^rk_Γ’和基底D ^＾＊₀、D^＾＊_i、U^＾＊_j作为要素的重加密密钥rk_S、Γ’。当然，也可以利用其它方法向重加密装置400发 送重加密密钥rk_S、Γ’。

即，在(S1001)至(S1009)中，解密装置300执行式207-1、式207-2所示的RKG算法， 生成重加密密钥rk_S、Γ’。并且，在(S1010)中，解密装置300向重加密装置400发送所生成的重 加密密钥rk_S、Γ’。

【式207-1】

${\overrightarrow{\tilde{s}}}^T:={({\tilde{s}}_1,...,{\tilde{s}}_{\tilde{L}})}^T:=\tilde{M}·{\overrightarrow{\tilde{f}}}^T,s_0:=\overrightarrow{1}·{\overrightarrow{\tilde{f}}}^T,$

【式207-2】

for

if

if

fort＝1，...，L，

for

说明重加密装置400的功能和动作。

如图22所示，重加密装置400具备公开参数接收部410、加密文接收部420、重加密 密钥接收部430、验证部440、加密部450、重加密文发送部460(重加密文输出部)。另外，验证 部440具备张成方案计算部441、签名验证部442。另外，加密部450具备随机数生成部451、f 矢量生成部452、s矢量生成部453、转换信息W₂生成部454、转换信息W₂加密部455、加密文 c^renc生成部456、解密密钥k^＊renc生成部457。

根据图27，说明REnc算法的处理。

(S1101：公开参数接收步骤)

公开参数接收部410例如利用通信装置经由网络，接收密钥生成装置100所生成的 公开参数pk。

(S1102：加密文接收步骤)

加密文接收部420例如利用通信装置经由网络接收加密装置200所发送的加密文 ct_Γ。

(S1103：重加密密钥接收步骤)

重加密密钥接收部430例如利用通信装置经由网络接收从解密装置300发送的重 加密密钥rk_S、Γ’。

(S1104：张成方案计算步骤)

张成方案计算部441利用处理装置，判定重加密密钥rk_S、Γ’所包含的访问结构S是 否受理加密文ct_Γ所包含的Γ，并且判定重加密密钥rk_S、Γ’所包含的访问结构S^～是否受理加 密文ct_Γ所包含的Γ^～。访问结构S是否受理Γ以及访问结构S^～是否受理Γ^～的判定方法是如 实施方式1的“第3.用于实现FCPRE的概念”中所说明的那样。

张成方案计算部441在访问结构S受理Γ且访问结构S^～受理Γ^～的情况下(在S1104 中为受理)，使处理前进至(S1105)。另一方面，在访问结构S拒绝Γ或访问结构S^～拒绝Γ^～的 情况下(在S1104中为拒绝)，结束处理。

(S1105：签名验证步骤)

签名验证部442利用处理装置，判定计算式208的结果是否是1。签名验证部442在 结果是1的情况下(在S1105中为合法)，使处理前进至(S1106)。另一方面，签名验证部442在 结果是0的情况下(在S1105中为非法)，结束处理。

【式208】

Ver(verk，C，Sig)

这里，

(S1106：随机数生成步骤)

随机数生成部451利用处理装置，如式209所示地生成随机数。

【式209】

(S1107：f矢量生成步骤)

f矢量生成部452利用处理装置，如式210所示随机地生成矢量f^→’、f^～→’。

【式210】

(S1108：s矢量生成步骤)

s矢量生成部453利用处理装置，如式211所示地生成矢量s^→’T、s^～→’T。

【式211】

${\overrightarrow{s}}^{\prime T}:={(s_1^{\prime },...,s_L^{\prime })}^T:=M·{\overrightarrow{f}}^{\prime T},$

${\overrightarrow{\tilde{s}}}^{\prime T}:={({\tilde{s}}_1^{\prime },...,{\tilde{s}}_{\tilde{L}}^{\prime })}^T:=\tilde{M}·{\overrightarrow{\tilde{f}}}^{\prime T}$

另外，s矢量生成部453利用处理装置，如式212所示地生成值s₀’、s^～₀’。

【式212】

$s_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{f}}^{\prime T},$

${\tilde{s}}_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{\tilde{f}}}^{\prime T}$

(S1109：转换信息W₂生成步骤)

转换信息W₂生成部454利用处理装置，如式213所示地生成转换信息W_2，0、W_2，t、W_2，u。

【式213】

(S1110：转换信息W₂加密步骤)

转换信息W₂加密部455利用处理装置，计算式214，利用函数型加密对转换信息 W_2，0、W_2，t、W_2，u进行加密，生成加密转换信息ct^renc_S’(ψ^renc)。因为转换信息W_2，0、W_2，t、W_2，u将属 性信息Γ’作为输入，利用函数型加密进行加密，所以，可对重加密文rct_Γ’进行解密的用户 的属性信息被设定并加密。

【式214】

$\left(\begin{array}{c}{\mathrm{ct}}_{{\Gamma }^{\prime }}^{renc}\stackrel{R}{\leftarrow }{\mathrm{Enc}}_{KP-FE}({\mathrm{pk}}^{KP-FE},{\Gamma }^{\prime },W_{2,0},\\ ({\left\{W_{2,t}\right\}}_{(t,{\overrightarrow{x}}_t)\in \Gamma )},{\left\{W_{2,u}\right\}}_{(u,{\overrightarrow{y}}_u)\in \tilde{\Gamma }}))\end{array}\right)$

(S1111：加密文c^renc生成步骤)

加密文c^renc生成部456利用处理装置，如式215所示地生成加密文c^renc₀。

【式215】

另外，加密文c^renc生成部456利用处理装置，关于属性信息Γ所包含的各个整数t， 如式216所示地生成加密文c^renc_t。

【式216】

另外，加密文c^renc生成部456利用处理装置，如式217所示地生成加密文c^renc_T。

【式217】

$c_T^{renc}:=c_T·{\tilde{c}}_T·g_T^{{\zeta }^{\prime }}$

另外，加密文c^renc生成部456利用处理装置，关于属性信息Γ^～所包含的各个整数 u，如式218所示地生成加密文c^renc_u。

【式218】

(S1112：解密密钥k^＊renc生成步骤)

解密密钥k^＊renc生成部457利用处理装置，如式219所示地生成解密密钥k^＊renc₀。

【式219】

另外，解密密钥k^＊renc生成部457利用处理装置，关于i＝1、...、L的各个整数i，如 式220所示地生成解密密钥k^＊renc_i。

【式220】

fori＝1，...，L，

if

if

另外，解密密钥k^＊renc生成部457利用处理装置，关于j＝1、...、L～的各个整数j， 如式221所示地生成解密密钥k^～＊renc_j。

【式221】

for

if

if

(S1113：重加密文发送步骤)

重加密文发送部460例如利用通信装置经由网络秘密地向重加密文解密装置500 发送将属性集合Γ’、Γ、Γ^～、访问结构S、S^～、解密密钥k^＊renc₀、k^＊renc_i、k^～＊renc_j、加密文c^renc₀、 c^renc_t、cr^enc_T、c^～renc_u和加密转换信息ct^rk_Γ’以及ct^renc_Γ’作为要素的重加密文rct_Γ’。当然，也 可以利用其它方法向重加密文解密装置500发送重加密文rct_Γ’。

即，在(S1101)至(S1112)中，重加密装置400执行式222-1、式222-2、式222-3所示 的REnc算法，生成重加密文ct_Γ’。并且，在(S1113)中，重加密装置400向重加密文解密装置 500发送所生成的重加密文ct_Γ’。

【式222-1】

如果受理Γ，受理Ver(verk,C,Sig)＝1

那么计算

$s_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{f}}^{\prime T},$

${\tilde{s}}_0^{\prime }:=\overrightarrow{1}·{\overrightarrow{\tilde{f}}}^{\prime T},$

对于

对于

【式222-2】

$\left(\begin{array}{c}{\mathrm{ct}}_{{\Gamma }^{\prime }}^{renc}\stackrel{R}{\leftarrow }{\mathrm{Enc}}_{KP-FE}({\mathrm{pk}}^{KP-FE},{\Gamma }^{\prime },W_{2,0},\\ ({\left\{W_{2,t}\right\}}_{(t,{\overrightarrow{x}}_t)\in \Gamma )},{\left\{W_{2,u}\right\}}_{(u,{\overrightarrow{y}}_u)\in \tilde{\Gamma }})),\end{array}\right)$

$c_T^{renc}:=c_T·{\tilde{c}}_T·g_T^{{\zeta }^{\prime }},$

fori＝1，...，L，

if

if

【式222-3】

for

if

if

说明重加密文解密装置500的功能和动作。

如图23所示，重加密文解密装置500具备解密密钥接收部510、加密文接收部520、 张成方案计算部530、增补系数计算部540、转换信息生成部550、转换部560、配对运算部 570、消息计算部580。此外，将配对运算部570和消息计算部580总称为解密部。

根据图28，来说明Dec1算法的处理。

(S1201：解密密钥接收步骤)

解密密钥接收部510例如利用通信装置经由网络接收从密钥生成装置100发送的 解密密钥sk_S’。另外，解密密钥接收部310接收密钥生成装置100所生成的公开参数pk。

(S1202：加密文接收步骤)

加密文接收部520例如利用通信装置经由网络接收重加密装置400所发送的重加 密文rct_Γ’。

(S1203：张成方案计算步骤)

张成方案计算部530利用处理装置，判定是否解密密钥sk_S’所包含的访问结构S’受 理重加密文rct_Γ’所包含的Γ’并且重加密文rct_Γ’所包含的访问结构S^～受理重加密文rct_Γ’所包含的Γ^～。访问结构S’是否受理Γ’以及访问结构S^～是否受理Γ^～的判定方法如在实施 方式1的“第3.用于实现FCPRE的概念”中所说明的那样。

张成方案计算部530在访问结构S’受理Γ’且访问结构S^～受理Γ^～的情况下(在 S1203中为受理)，使处理前进至(S1204)。另一方面，在访问结构S’拒绝Γ’或访问结构S^～拒 绝Γ^～的情况下(在S1203中为拒绝)，结束处理。

(S1204：增补系数计算步骤)

增补系数计算部540利用处理装置，计算成为式223的I、J和常数(增补系数) {α_i}_i∈I、{α^～_j}_j∈J。

【式223】

$\overrightarrow{1}={\Sigma }_{i\in I}{\alpha }_i{M}_i,\overrightarrow{1}={\Sigma }_{j\in J}{\tilde{\alpha }}_j{\tilde{M}}_j$

其中，M_i是M的第i行是的第j行

并且

(S1205：转换信息生成步骤)

转换信息生成部550利用处理装置，如式224所示地生成转换信息W_1，0、W_1，t、W^～_1，u、 W_2，0、W_2，t、W^～_2，u。

【式224】

(S1206：转换步骤)

转换部560利用处理装置，如式225所示地生成解密密钥k^＊₀、k^＊_i、k^～＊_j，并且生成加 密文c₀、c_t、c^～_u。

【式225】

$k_0^{*}:=k_0^{*renc}{W}_{1,0}^{-1},$

$c_0:=c_0^{renc}{W}_{2,0}^{-1},$

(S1207：配对运算步骤)

配对运算部570利用处理装置，计算式226，生成会话密钥K^～。

【式226】

(S1208：消息计算步骤)

消息计算部580利用处理装置，计算m’＝c^～renc_T/K^～，生成消息m’(＝m)。

即，在(S1201)至(S1208)中，重加密文解密装置500执行式227-1、式227-2所示的 Dec1算法，生成消息m’(＝m)。

【式227-1】

如果受理Γ′并且受理

那么计算I，Jand{α_i}_i∈I，

其中M_i是M的第i行是的第j行

并且

【式227-2】

$k_0^{*}:=k_0^{*renc}{W}_{1,0}^{-1},$

$c_0:=c_0^{renc}{W}_{2,0}^{-1},$

$m^{\prime }:={\tilde{c}}_T/\tilde{K},$

returnm＇.

根据图29，来说明Dec2算法的处理。

(S1301：解密密钥接收步骤)

解密密钥接收部310例如利用通信装置经由网络接收从密钥生成装置100发送的 解密密钥sk_S。另外，解密密钥接收部310接收密钥生成装置100所生成的公开参数pk。

(S1302：加密文接收步骤)

加密文接收部350例如利用通信装置经由网络接收重加密装置400所发送的加密 文ct_Γ。

(S1303：张成方案计算步骤)

张成方案计算部361利用处理装置，判定解密密钥sk_S所包含的访问结构S是否受 理加密文ct_Γ所包含的Γ。访问结构S是否受理Γ的判定方法如在实施方式1的“第3.用于实 现FCPRE的概念”中所说明的那样。

张成方案计算部361在访问结构S受理Γ的情况下(在S1303中为受理)，使处理前 进至(S1304)。另一方面，在访问结构S拒绝Γ的情况下(在S1303中为拒绝)，结束处理。

(S1304：签名验证步骤)

签名验证部362利用处理装置，判定计算式228的结果是否是1。签名验证部362在 结果是1的情况下(在S1304中为合法)，使处理前进至(S1305)。另一方面，签名验证部362在 结果是0的情况下(在S1304中为非法)，结束处理。

【式228】

Ver(verk,C,Sig)

这里，

$C:=(\Gamma ,\tilde{\Gamma },c_0,{\left\{c_t\right\}}_{(t,{\overrightarrow{x}}_t),\in \Gamma },{\left\{{\tilde{c}}_u\right\}}_{(u,{\overrightarrow{y}}_u),\in \tilde{\Gamma }},c_T)$

(S1305：增补系数计算步骤)

增补系数计算部370利用处理装置，计算成为式229的I和常数(增补系数){α_i}_i∈I。

【式229】

$\overrightarrow{1}=\underset{i\in I}{\Sigma }{\alpha }_i{M}_i$

其中，M_i是M的第i行，

(S1306：配对运算步骤)

配对运算部380利用处理装置，计算式230，生成会话密钥K。

【式230】

(S1307：消息计算步骤)

消息计算部390利用处理装置，计算m’＝c^enc_d+1/K，生成消息m’(＝m)。

即，在(S1301)至(S1307)中，解密装置300执行式231所示的Dec2算法，生成消息m’ (＝m)。

【式231】

If受理

并且Ver(verk，C，Sig)＝1，

那么计算Iand{α_i}_i∈I

$\overrightarrow{1}=\underset{i\in I}{\Sigma }{\alpha }_i{M}_i$

其中，M_i是M的第i行，

m＇＝c_T/K，

returnm＇.

如以上那样，实施方式2的加密系统能够实现KP-FCPRE方式。因此，利用1个重加密 密钥，能够向各个种类的用户的集合转发加密文。此外，能够指定对重加密的加密文进行指 定的条件。

此外，在上述说明中，解密装置300兼作重加密密钥生成装置，解密装置300不仅执 行Dec2算法，还执行RKG算法。但是，解密装置300和重加密密钥生成装置也可以是分开的装 置。在此情况下，解密装置300执行Dec2算法，重加密密钥生成装置执行RKG算法。因此，在此 情况下，解密装置300具备执行Dec2算法所需的功能结构，重加密密钥生成装置具备执行 RKG算法所需的功能结构。

另外，在上述说明中，对N_t设定n_t+w_t+z_t+1。但是，也可以对N_t设定n_t+w_t+z_t+β_t。这 里，β_t是0以上的整数。

另外，在上述说明中，对N₀设定9。但是，也可以对N₀设定1+1+2+w₀+z₀+β₀。这里，w₀、 z₀、β₀是0以上的整数。

另外，在上述说明中，在S1111内生成的加密文c^～renc0的π’(verk、1)是追加信息 Η，在S1112内生成的解密密钥k^＊renc₀的σ(-1、verk)是追加信息Θ。追加信息Η、Θ是对应 的，利用在S1207内执行的配对运算进行抵消。此外，虽然可能稍微降低安全性，但也可以在 追加信息中包含随机数等的值来取代verk。

在以上的实施方式中说明了以下的情况：假定利用FE来加密消息后发送到送达目 的地的情况，重加密装置400对加密文进行重加密，变更加密文的送达目的地。

FE不仅可以实现加密消息后发送到送达目的地的功能，还可以实现能够在不用对 加密文进行解密的情况下就进行检索的可检索加密。在利用FE来实现可检索加密的情况 下，能够通过在以上的实施方式中说明的算法，变更所设定的检索关键字。

在以上的实施方式中，在加密文内设定的属性信息指定了能够解密的用户。并且， 通过变更属性信息，变更加密文的送达目的地。在利用FE实现可检索加密的情况下，在加密 文内设定的属性信息的一部分指定能够检索的用户，剩余属性信息的一部分指定检索关键 字。因此，可以利用在以上的实施方式中说明的算法，变更属性信息中的指定了检索关键字 的部分，由此，变更所设定的检索关键字。

另外，在以上的实施方式中，1台的密钥生成装置100生成解密密钥。但是，也可以 使以上实施方式的算法与非专利文献5所记载的分散多管理者的方式进行组合，利用多个 密钥生成装置100来生成1个解密密钥。

另外，在以上的实施方式中，当追加属性的分类时(增加属性的格式n^→中的d的值 时)，需要重新发行公开参数。但是，也可以使以上实施方式的算法与非专利文献6所记载的 Unbounded的方式进行组合，追加属性的分类，而不用重新发行公开参数。

另外，在以上的实施方式中，在设用于内积加密的矢量的长度为N时，公开参数或 主私钥的大小与N²成比例，在对用户赋予的解密密钥的生成或加密的处理中花费与N²成比 例的时间。但是，也能够使以上实施方式的算法与非专利文献7所记载的方式进行组合，减 小公开参数或主私钥的大小，并且也能够缩短在对用户赋予的解密密钥的生成处理或加密 处理中花费的时间。

另外，在以上的实施方式中，向发送目的地的装置发送密钥或加密文。但是，取而 代之，也可对CD或DVD等存储介质输出密钥或加密文，发送目的地的装置读取存储介质。

实施方式3.

在以上的实施方式中，说明了在双对矢量空间内实现加密处理的方法。在实施方 式3中，说明在双对模块内实现加密处理的方法。

即，在以上的实施方式中，在质数位数q的循环组内实现了加密处理。但是，在采用 合成数M如式232那样表示环R的情况下，即使在将环R作为系数的模块中，也能够应用上述 实施方式所说明的加密处理。

【式232】

这里，

Z：整数，

M：合成数。

只要将以上实施方式所说明的算法中的F_q变更为R，就能够实现双对模块中的加 密处理。

此外，在以上的实施方式中，根据安全性证明的观点，关于i＝1、...、L的各个整数 i的ρ(i)可限定为是关于各不相同的识别信息t的肯定形式的组(t，v^→)或否定形式的组￢ (t，v^→)。

换言之，在ρ(i)＝(t，v^→)或ρ(i)＝￢(t，v^→)的情况下，将函数ρ^～设为ρ^～(i)＝t即 {1、...、L}→{1、...d}的映射。在此情况下，可限定为ρ^～是单射。此外，ρ(i)是上述的访问结 构S：＝(M、ρ(i))的ρ(i)。

接着，说明实施方式中的加密系统10(密钥生成装置100、加密装置200、解密装置 300、重加密装置400、重加密文解密装置500)的硬件结构。

图30是示出密钥生成装置100、加密装置200、解密装置300、重加密装置400、重加 密文解密装置500的硬件结构的一例的图。

如图30所示，密钥生成装置100、加密装置200、解密装置300、重加密装置400、重加 密文解密装置500具备执行程序的CPU911(也称为Central·Processing·Unit：中央处理 器、中央处理装置、处理装置、运算装置、微型处理器、微型计算机、处理器)。CPU911经由总 线912与ROM913、RAM914、LCD901(LiquidCrystalDisplay：液晶显示器)、键盘902(K/B)、 通信板915、磁盘装置920连接，并控制这些硬件设备。代替磁盘装置920(固定盘装置)，可以 是光盘装置、存储卡读写装置等存储装置。磁盘装置920经由预定的固定盘接口进行连接。

ROM913、磁盘装置920是非易失性存储器的一例。RAM914是挥发性存储器的一例。 ROM913、RAM914和磁盘装置920是存储装置(存储器)的一例。另外，键盘902、通信板915是输 入装置的一例。另外，通信板915是通信装置的一例。此外，LCD901是显示装置的一例。

在磁盘装置920或ROM913等中，存储有操作系统921(OS)、窗口系统922、程序组 923、文件组924。利用CPU911、操作系统921、窗口系统922来执行程序组923的程序。

在上述说明中，在程序组923内存储有执行作为“主密钥生成部110”、“主密钥存储 部120”、“信息输入部130”、“解密密钥生成部140”、“密钥发送部150”、“公开参数接收部 210”、“信息输入部220”、“签名处理部230”、“加密部240”、“加密文发送部250”、“解密密钥 接收部310”、“信息输入部320”、“重加密密钥生成部330”、“重加密密钥发送部340”、“加密 文接收部350”、“验证部360”、“增补系数计算部370”、“配对运算部380”、“消息计算部390”、 “公开参数接收部410”、“加密文接收部420”、“重加密密钥接收部430”、“验证部440”、“加密 部450”、“重加密文发送部460”、“解密密钥接收部510”、“加密文接收部520”、“张成方案计 算部530”、“增补系数计算部540”、“转换信息生成部550”、“转换部560”、“配对运算部570”、 “消息计算部580”等进行说明的功能的软件、程序或其它程序。利用CPU911读出并执行程 序。

在上述说明中，在文件组924内存储有“公开参数pk”、“主私钥sk”、“解密密钥sk_S、 sk_Γ”、“加密文ct_Γ、ct_S”、“重加密密钥rk_Γ、S’、rk_S、Γ’”、“重加密文rct_S’、rct_Γ’”、“访问结构S、 S’、S^～”、“属性集合Γ、Γ’、Γ^～”、“消息m”等信息、数据、信号值、变量值或参数，作为“文件” 或“数据库”的各个项目。在盘或存储器等记录介质中存储“文件”或“数据库”。经由读写电 路，利用CPU911在主存储器或缓存存储器中读出存储于盘或存储器等存储介质内的信息、 数据、信号值、变量值或参数，并应用于提取、检索、参照、比较、运算、计算、处理、输出、印 刷、显示等CPU911的动作。在提取、检索、参照、比较、运算、计算、处理、输出、印刷、显示的 CPU911的动作之间，在主存储器、缓存存储器或缓冲存储器中临时性存储信息、数据、信号 值、变量值或参数。

另外，上述说明中的流程图的箭头部分主要表示数据或信号的输入输出，在 RAM914的存储器、其它光盘等记录介质或IC芯片内记录有数据或信号值。另外，利用总线 912、信号线、电缆之外的传送介质或电波来在线传送数据或信号。

另外，在上述说明中作为“～部”说明的内容可以是“～电路”、“～装置”、“～设 备”、“～单元”、“～功能”，另外，可以是“～步骤”、“～顺序”、“～处理”。另外，作为“～装置” 说明的内容可以是“～电路”、“～设备”、“～单元”、“～功能”，另外，可以是“～步骤”、“～顺 序”、“～处理”。此外，作为“～处理”说明的内容也可以是“～步骤”。即，作为“～部”说明的 内容也可以利用存储于ROM913内的固件来实现。或者也可以仅利用软件或者仅利用元件、 设备、基板、布线等硬件或者利用软件与硬件的组合以及与固件的组合来实施。固件和软件 作为程序存储于ROM913等记录介质内。利用CPU911读出程序，并由CPU911来执行。即，程序 是使计算机等作为上述描述的“～部”发挥功能。或者，使计算机等执行上述描述的“～部” 的顺序或方法。

标号说明

100密钥生成装置，110主密钥生成部，120主密钥存储部，130信息输入部，140解密 密钥生成部，141CP-FE密钥生成部，142随机数生成部，143解密密钥k^＊生成部，144KP-FE 密钥生成部，145f矢量生成部，146s矢量生成部，150密钥发送部，200加密装置，210公开 参数接收部，220信息输入部，230签名处理部，240加密部，241f矢量生成部，242s矢量生 成部，243随机数生成部，244加密文c生成部，250加密文发送部，300解密装置，310解密密钥 接收部，320信息输入部，330重加密密钥生成部，331随机数生成部，332转换信息W₁生成部， 333转换信息W₁加密部，334解密密钥k^＊rk生成部，335转换部，336f矢量生成部，337s矢量 生成部，340重加密密钥发送部，350加密文接收部，360验证部，361张成方案计算部，362签 名验证部，370增补系数计算部，380配对运算部，390消息计算部，400重加密装置，410公开 参数接收部，420加密文接收部，430重加密密钥接收部，440验证部，441张成方案计算部， 442签名验证部，450加密部，451随机数生成部，452f矢量生成部，453s矢量生成部，454转 换信息W₂生成部，455转换信息W₂加密部，456加密文c^renc生成部，457解密密钥k^＊renc生成部， 460重加密文发送部，500重加密文解密装置，510解密密钥接收部，520加密文接收部，530张 成方案计算部，540增补系数计算部，550转换信息生成部，560转换部，570配对运算部，580 消息计算部。