加密系统、重加密密钥生成装置、重加密装置、加密方法和加密程序

摘要

目的在于实现函数型加密中的代理重加密方式。解密装置300将使用转换信息W1对设定了相互对应的属性信息x、v中的一个属性信息的解密密钥k*进行转换而得到的解密密钥k*rk以及设定相互对应的属性信息x'、v'中的一个属性信息并对转换信息W1进行加密而得到的加密转换信息Ψrk发送给重加密装置400。重加密装置400将在设定了属性信息x、v中的另一个属性信息的密文cenc中设定了相互对应的追加信息Η、Θ中的至少一个追加信息而得到的密文crenc以及在解密密钥k*rk中设定了追加信息Η、Θ中的至少另一个追加信息而得到的解密密钥k*renc作为重加密密文CT。

说明书

技术领域

本发明涉及函数型加密中的代理重加密(Functional Proxy Re-Encryption、FPRE)。

背景技术

代理重加密(Proxy Re-Encryption、PRE)是不对密文进行解密而将密文的解密 权限授权给第三方的系统。在非专利文献1中具有与ID基加密中的PRE (Identity-Based PRE、IBPRE)方式有关的记载。在非专利文献2中具有与属性基加 密中的PRE(Attribute-Based PRE、ABPRE)方式有关的记载。在非专利文献2所记 载的PRE方式中，能够在密文中仅指定由逻辑积和否定构成的属性。

在专利文献1中具有与函数型加密(FE)有关的记载。

现有技术文献

专利文献

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

非专利文献

非专利文献1：M.Green,and G.Ateniese,Identity-Based Proxy Re-encryption.In  Applied Cryptography and Network Security.volume 4521of LNCS,pp 288-306,2007.

非专利文献2：Xiaohui Liang,Zhenfu Cao,Huang Lin,Jun Shao.Attribute based proxy  re-encryption with delegating capabilities.ASIACCS 2009pp.276-286.

非专利文献3：Okamoto,T Takashima,K.：Decentralized Attribute-Based  Signatures.ePrint http：//eprint.iacr.org/2011/701

非专利文献4：Okamoto,T Takashima,K.：Fully Secure Unbounded Inner-Product and  Attribute-Based Encryption.ePrint http：//eprint.iacr.org/2012/671

非专利文献5：Okamoto,T.,Takashima,K.：Achieving Short Ciphertexts or Short  Secret-Keys for Adaptively Secure General Inner-Product Encryption.CANS 2011,LNCS, vol.7092,pp.138-159Springer Heidelberg(2011).

发明内容

发明要解决的课题

以往，没有实现FPRE方式。

以往实现的PRE方式存在能够利用1个重加密密钥授权的第三方仅为1个用户 或限于具有受到严格制约的属性的用户这样的课题。

本发明的目的在于，提供能够灵活选择能够利用1个重加密密钥授权的第三方的 PRE方式。

用于解决课题的手段

本发明的加密系统实现在2个信息相互对应的情况下能够对设定了一个信息的 密文通过设定了另一个信息的解密密钥进行解密的加密方式中的代理重加密功能，该 加密系统具有重加密密钥生成装置和重加密装置，其特征在于，

所述重加密密钥生成装置具有：

解密密钥k^*rk生成部，其使用转换信息W₁对设定了相互对应的属性信息x、v 中的一个属性信息的解密密钥k^*进行转换，生成解密密钥k^*rk；

转换信息W₁加密部，其设定相互对应的属性信息x’、v’中的一个属性信息，对 所述转换信息W₁进行加密，生成加密转换信息ψ^rk；以及

重加密密钥发送部，其将所述解密密钥k^*rk和所述加密转换信息ψ^rk作为重加密 密钥rk发送给所述重加密装置，

所述重加密装置具有：

密文接收部，其接收设定了所述属性信息x、v中的另一个属性信息的密文c^enc；

密文c^renc生成部，其在所述密文接收部接收到的密文c^enc中设定相互对应的追加 信息Η、Θ中的至少一个追加信息，生成密文c^renc；

解密密钥k^*renc生成部，其在所述重加密密钥rk中包含的所述解密密钥k^*rk中设 定所述追加信息Η、Θ中的至少另一个追加信息，生成解密密钥k^*renc；以及

重加密密文发送部，其发送所述密文c^renc、所述解密密钥k^*renc和所述加密转换 信息ψ^rk作为重加密密文CT。

发明效果

在本发明的加密系统中，能够实现FPRE方式。因此，能够利用1个重加密密钥 对各个种类的用户的集合转送密文。具体而言，能够在重加密密钥中嵌入具有非单调 性的一般的访问结构，不存在针对要转送的用户的限制，能够进行灵活的转送设定。

附图说明

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

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

图3是s₀的说明图。

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

图5是执行CP-FPRE方式的加密处理系统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-FPRE方式的加密处理系统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的硬件结构的一例的图。

具体实施方式

下面，根据附图对发明的实施方式进行说明。

在以下说明中，处理装置是后述的CPU 911等。存储装置是后述的ROM 913、 RAM 914、磁盘920等。通信装置是后述的通信板(communication board)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所示的2个向量与的数式109所示的内积。

【数式107】

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

【数式108】

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

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

【数式109】

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

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

对于数式110所示的基B和基B^*为数式111。

【数式110】

【数式111】

e^→_j表示数式112所示的标准基向量(orthonormal basis vector)。

【数式112】

并且，在以下说明中，在“Vt”、“nt”、“ut”、“zt”用下标或上标表示的 情况下，意味着该Vt、nt、ut、zt为V_t、n_t、u_t、z_t。同样，在“δi，j”用上标表示的 情况下，意味着该δi，j为δ_i、j。

并且，在表示向量的“→”标注在下标文字或上标文字上的情况下，意味着该“→” 用上标标注在下标文字或上标文字上。

并且，在以下说明中，加密处理包含密钥生成处理、加密处理、重加密密钥生成 处理、重加密处理、解密处理、重加密密文解密处理。

实施方式1.

在该实施方式中，对实现FPRE方式的基础概念进行说明后，对该实施方式的 FPRE方式的结构进行说明。

第1，对FPRE进行简单说明。

第2，对用于实现FPRE方式的空间即称为对偶配对向量空间(Dual Pairing Vector  Spaces、DPVS)的具有丰富数学结构的空间进行说明。

第3，对用于实现FPRE方式的概念进行说明。这里，对跨度程序(span program)、 属性向量的内积与访问结构(access structure)、秘密分散方式(secret distribution  scheme，秘密共享方式)进行说明。

第4，对该实施方式的FPRE方式进行说明。在该实施方式中，对密文方针的FPRE 方式(Ciphertext-Policy FPRE、CP-FPRE)方式进行说明。因此，首先，对CP-FPRE 方式的基本结构进行说明。接着，对实现该CP-FPRE方式的加密处理系统10的基本 结构进行说明。接着，对为了实现该CP-FPRE方式而使用的部件进行说明。然后， 对该实施方式的CP-FPRE方式和加密处理系统10进行详细说明。

<第1.FPRE>

FPRE是使加密密钥(ek)、解密密钥(dk)、重加密密钥(rk)的关系更加高 度化且灵活的代理重加密方式。

FPRE具有以下2个特征。第1，加密密钥和解密密钥分别被设定了属性信息x 和属性信息v。而且，针对关系R，仅在R(x、v)成立的情况下，解密密钥dk_v能 够对利用加密密钥ek_x加密的密文进行解密。第2，除了在加密密钥和解密密钥中分 别设定属性信息x和属性信息v以外，重加密密钥还被设定了2个属性信息(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)。

关于属性信息的组成部分，每个组成部分的等号关系(例如{x_t＝v_t}t∈{1，...， d})被输入到访问结构S。然后，仅在访问结构S受理了输入的情况下，R(X，V) 成立。即，能够利用解密密钥对利用加密密钥加密后的密文进行解密。在非专利文献 2中，提出了访问结构S被嵌入在密文中的密文方针的PRE方式。此时的访问结构 是仅由逻辑积和否定构成的结构。

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

<第2.对偶配对向量空间>

首先，说明对称双线性配对群(symmetrix bilinear pairing group)。

对称双线性配对群(q，G，G^T，g，e)是质数q、阶数q的循环加法群G、阶数 q的循环乘法群G^T、g≠0∈G、能够利用多项式时间计算的非退化双线性配对 (Nondegenerate Bilinear Pairing)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)的值。

接着，说明对偶配对向量空间(dual pairing vector space)。

对偶配对向量空间(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(a_k)＝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.用于实现FPRE方式的概念>

<第3-1.跨度程序(span program)>

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

设{p₁,...,p_n}为变量的集合。M^：＝(M，ρ)是贴了标签的矩阵。这里，矩阵M 是F_q上的(L行×r列)的矩阵。并且，ρ是对矩阵M的各列附加的标签，与{p₁，...， p_n，￢p₁，...，￢p_n}中的任意1个文字(literal)对应。另外，对M的全部行附加的 标签ρ_i(i＝1，...，L)与任意1个文字对应。即，ρ：{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_δ的行进行线性合并(linear  combination)而得到1^→的情况下，跨度程序M^受理输入列δ。另外，1^→是各要素为 值“1”的行向量。

例如，如果是图2的例子，则仅在对由矩阵M的第1、2、4行构成的矩阵M_δ的各行进行线性合并而得到1^→的情况下，跨度程序M^受理输入列δ。即，在存在成 为α₁(M₁)+α₂(M₂)+α₄(M₄)＝1^→的α₁、α₂、α₄的情况下，跨度程序M^受理输入 列δ。

这里，在标签ρ仅与正文字(positive literal){p₁，...，p_n}对应的情况下，跨度 程序被称为单调(monotone)。另一方面，在标签ρ与文字{p₁，...，p_n，￢p₁，...， ￢p_n}对应的情况下，跨度程序被称为非单调(non-monotone)。这里，使跨度程序 为非单调。而且，使用非单调跨度程序构成访问结构(非单调访问结构)。简单地讲， 访问结构是进行针对加密的访问控制。即，进行是否能够对密文进行解密的控制。

详细情况在后面叙述，但是，通过使跨度程序不为单调而成为非单调，利用跨度 程序构成的FPRE方式的利用范围扩大。

<第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∈Fqⁿ、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<(M_i)_γ(i)＝1>的情况下，访问结构 S：＝(M，ρ)受理Γ。

<第3-3.秘密分散方式>

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

另外，秘密分散方式是指使秘密信息分散而成为没有意义的分散信息。例如，使 秘密信息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】

设数式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,\mathrm{...}{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的尺寸中的多项式时间进行计算。

在以下实施方式的FPRE方式中，如上所述，在跨度程序中应用内积谓词 (inner-product predicate)和秘密分散方式来构成访问结构。因此，通过设计跨度程 序中的矩阵M、内积谓词中的属性信息x和属性信息v(谓词信息)，能够自由设计 访问控制。即，能够以非常高的自由度进行访问控制的设计。另外，矩阵M的设计 相当于秘密分散方式的阈值等的条件设计。

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

并且，内积谓词加密方式的PRE相当于如下情况：在以下实施方式的FPRE方 式的访问结构中，将跨度程序中的矩阵M的设计限定为某个条件。即，与以下实施 方式的FPRE方式的访问结构相比，内积谓词加密方式的访问结构不具有跨度程序中 的矩阵M的设计的自由度，相应地，访问控制的设计的自由度低。另外，具体而言， 内积谓词加密方式相当于将秘密分散方式限定为1-out-of-1(或d-out-of-d)的情况。

特别地，以下实施方式的FPRE方式的访问结构构成使用非单调跨度程序的非单 调访问结构。因此，访问控制的设计的自由度更高。

具体而言，由于在非单调跨度程序中包含否定形的文字(￢p)，所以，能够设 定否定形的条件。例如，设在第1公司中存在A部、B部、C部、D部这4个部门。 这里，设为希望进行仅属于第1公司的B部以外的部门的用户能够进行访问(能够 解密)这样的访问控制。该情况下，当无法进行否定形的条件的设定时，需要设定“属 于第1公司的A部、C部、D部中的任意一方”这样的条件。另一方面，当能够进行 否定形的条件的设定时，能够设定“第1公司的职员且属于B部以外”这样的条件。 即，由于能够设定否定形的条件，能够进行自然的条件设定。另外，这里，部门的数 量较少，但是，可知的是，在部门的数量较多的情况等中非常有效。

<第4.FPRE方式的基本结构>

<第4-1.CP-FPRE方式的基本结构>

对CP-FPRE方式的结构进行简单说明。另外，CP(密文方针)意味着在密文中 嵌入Policy、即嵌入访问结构。

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

(Setup)

Setup算法是如下的概率算法：将保密参数λ和属性的格式n^→：＝ (d；n₁,...,n_d；u₁,...,u_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，ρ)、公开参数pk 作为输入，输出密文ct_S。

(RKG)

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

(REnc)

REnc算法是如下的概率算法：将密文ct_S、重加密密钥rk_(Γ.S’)、公开参数pk作 为输入，输出重加密密文CT_S’。

(Dec1)

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

(Dec2)

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

<第4-2.加密处理系统10>

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

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

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

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

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

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

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

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

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

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

<为了实现第4-3.CP-FPRE方式而使用的部件>

为了实现CP-FPRE方式，使用密文方针的函数型加密(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作为输入，针对验证 密钥verk和消息m，如果签名S正当则输出1，如果不正当则输出0。

<第4-4.CP-FPRE方式和加密处理系统10的详细情况>

根据图6～图17，对执行CP-FPRE方式和CP-FPRE方式的加密处理系统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的功能和动作进行说明。

密钥生成装置100具有主密钥生成部110、主密钥存储部120、信息输入部130、 解密密钥生成部140、密钥发送部150。并且，解密密钥生成部140具有CP-FE密钥 生成部141、随机数生成部142、解密密钥k^*生成部143。

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

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

主密钥生成部110通过处理装置计算数式122，生成参数param_n→、基B₀和基 B^*₀、基B_t和基B^*_t。

【数式122】

针对t＝0,...,d的各整数t，执行(4)～(7)的处理

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

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

(1)主密钥生成部110通过输入装置输入保密参数λ(1^λ)和属性的格式n^→：＝ (d；n₁，...，n_d；u₁，...，u_d；z₁，...，z_d)。这里，d是1以上的整数，关于t＝1、...、d 的各整数t，n_t为1以上的整数，u_t、z_t为0以上的整数。

(2)主密钥生成部110通过处理装置将(1)中输入的保密参数λ作为输入来执 行算法G_bpg，生成双线性配对群的参数param_G：＝(q，G，G_T，g，e)的值。

(3)主密钥生成部110将N₀设定为7，对于t＝1、...、d的各整数t，将N_t设定 为n_t+u_t+z_t+1。并且，主密钥生成部110生成随机数ψ。并且，主密钥生成部110将 g_T设定为e(G、G)^ψ。

接着，主密钥生成部110针对t＝0、...、d的各整数t，执行以下的(4)～(7) 的处理。

(4)主密钥生成部110将(1)中输入的保密参数λ(1^λ)、(3)中设定的N_t、 (2)中生成的param_G：＝(q，G，G_T，g，e)的值作为输入来执行算法G_dpvs，生成 对偶配对向量空间的参数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是General Linear的缩写。即，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在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。

【数式124】

主密钥生成部110合并公开参数pk^CP-FE、保密参数λ、param_n→、部分基B^₀和部 分基B^_t、基向量b^*_0.2、b^*_0.3、b^*_0.4、b^*_0.6、与t＝1、...、d的各整数t有关的基向量b^*_t.1，...， b^*_t.nt，b^*_t.nt+ut+1，...，b^*_t.nt+ut+zt，作为公开参数pk。

(S104：主密钥生成步骤)

主密钥生成部110如数式125所示生成在(S101)中生成的基B^*₀的部分基B^^*₀。

【数式125】

主密钥生成部110将主密钥sk^CP-FE和基向量b^*_0.1作为主密钥sk。

(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】

【数式126-2】

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

(S201：信息输入步骤)

信息输入部130通过输入装置输入属性集合Γ：＝{(t、x^→_t：＝(x_t.1，...，x_t.nt∈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】

(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.5的系数，设定作为基向量b^*_0.6的系数，设定0作为基向量b^*_0.7的系数。

并且，解密密钥k^*生成部143通过处理装置，针对属性集合Γ中包含的各整数t， 如数式130所示生成解密密钥k^*_t。

【数式130】

另外，数式130设定δx_t.1，...，δx_t.nt作为基B^*_t的基向量b^*_t.1，...，b^*_t.nt的系数， 设定0作为基向量b^*_t.nt+1，...，b^*_t.nt+ut的系数，设定作为基向量b^*_t.nt+ut+1，...， b^*_t.nt+ut+zt的系数，设定0作为基向量b^*_t.nt+ut+zt+1的系数。

(S205：密钥发送步骤)

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

即，在(S201)～(S204)中，密钥生成装置100执行数式131所示的KG算法， 生成解密密钥sk_Γ。然后，在(S205)中，密钥生成装置100将解密密钥sk_Γ发送给 解密装置300。

【数式131】

另外，密钥生成装置100在(S201)中输入设定了解密密钥sk_Γ’的使用者的属性 信息的属性集合Γ’：＝{(t，x’^→_t：＝(x’_t.1，...，x’_t.nt∈F_q^nt\{0^→}))|1≦t≦d}，执行 KG算法，生成解密密钥sk_Γ’。然后，密钥生成装置100将解密密钥sk_Γ’：＝(sk_Γ’^CP-FE， Γ’，k’^*₀，{k’^*_t}_{(t，x→t)∈Γ’})发送给重加密密文解密装置500。

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

加密装置200具有公开参数接收部210、信息输入部220、签名处理部230、加 密部240、密文发送部250。并且，加密部240具有f向量生成部241、s向量生成部 242、随机数生成部243、密文c^enc生成部244。

根据图13对Enc算法的处理进行说明。

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

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

(S302：信息输入步骤)

信息输入部220通过输入装置输入访问结构S：＝(M，ρ)。另外，关于访问结 构S的设定，根据希望实现的系统的条件来进行设定。并且，访问结构S的ρ例如设 定能够对密文ct_S进行解密的用户的属性信息。这里，ρ(i)＝(t，v^→_i：＝(v_i.1，...， v_i.nt)∈F_q^nt\{0^→})(v_i，nt≠0)。

并且，信息输入部220通过输入装置输入要发送给解密装置300的消息m。

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

签名处理部230通过处理装置计算数式132，生成一次性签名的签名密钥sigk和 验证密钥verk。

【数式132】

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

(S304：f向量生成步骤)

f向量生成部241通过处理装置，如数式133所示随机生成具有r个要素的向量 f^→。

【数式133】

(S305：s向量生成步骤)

s向量生成部242通过处理装置，根据访问结构S中包含的(L行×r列)的矩阵 M、向量f^→，如数式134所示生成向量s^→T。

【数式134】

${\overrightarrow{S}}^T:={(S_1,\mathrm{...},S_L)}^T:=M·{\overrightarrow{f}}^T$

并且，s向量生成部242通过处理装置，根据向量f^→，如数式135所示生成值s₀。

【数式135】

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

(S306：随机数生成步骤)

随机数生成部243通过处理装置，如数式136所示生成随机数。

【数式136】

(S307：密文c^enc生成步骤)

密文c^enc生成部244通过处理装置，如数式137所示生成密文c^enc₀。

【数式137】

并且，密文c^enc生成部244通过处理装置，针对i＝1、...、L的各整数i，如数式 138所示生成密文c^enc_i。

【数式138】

并且，密文c^enc生成部244通过处理装置，如数式139所示生成密文c^enc_d+1。

【数式139】

$c_{d+1}^{enc}=m·g_T^{\zeta }$

(S308：签名生成步骤)

签名处理部230通过处理装置计算数式140，生成针对密文ct_S的要素C：＝(S， {c^enc_i}_{i＝0，...，L}，c^enc_d+1)的签名Sig。

【数式140】

(S309：密文发送步骤)

密文发送部250通过例如通信装置，经由网络向解密装置300发送将访问结构S、 密文c^enc₀、c^enc₁、...、c^enc_L、c^enc_d+1、验证密钥verk、签名Sig作为要素的密文ct_S。当 然，密文ct_S也可以通过其它方法发送给解密装置300。

即，在(S301)～(S308)中，加密装置200执行数式141所示的Enc算法， 生成密文ct_S。然后，在(S309)中，加密装置200将所生成的密文ct_S发送给解密装 置300。

【数式141】

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

解密装置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’的ρ’例 如被设定了能够对重加密密文CT_S’进行解密的用户的属性信息。这里，ρ’(i)＝(t， v^→’_i：＝(v’_i.1，...，v’_i.nt)∈F_q^nt\{0^→})(v’_i，nt≠0)。

(S403：随机数生成步骤)

随机数生成部331通过处理装置，如数式142所示生成随机数。

【数式142】

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

转换信息W₁生成部332通过处理装置，如数式143所示生成转换信息W₁。

【数式143】

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

转换信息W₁加密部333通过处理装置计算数式144，通过函数型加密对转换信 息W₁进行加密，生成加密转换信息ψ^rk。由于转换信息W₁以访问结构S’作为输入并 通过函数型加密被加密，所以，转换信息W₁被设定能够对重加密密文CT_S’进行解密 的用户的属性信息并被加密。

【数式144】

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

解密密钥k^*rk生成部334通过处理装置，如数式145所示生成解密密钥k^*rk₀。

【数式145】

并且，解密密钥生成部334通过处理装置，针对属性集合Γ中包含的各整数t， 如数式146所示生成解密密钥k^*rk_t。

【数式146】

(S407：转换步骤)

转换部335通过处理装置计算数式147，生成基D^{^*}₀。

【数式147】

(S408：密钥发送步骤)

重加密密钥发送部340通过例如通信装置，经由网络秘密地向重加密装置400 发送以属性集合Γ、访问结构S’、解密密钥k^*rk₀、k^*rk_t、加密转换信息ψ^rk、基D^{^*}₀作为要素的重加密密钥rk_(Γ.S’)。当然，重加密密钥rk_(Γ.S’)也可以通过其它方法发送 给重加密装置400。

即，在(S401)～(S407)中，解密装置300执行数式148所示的RKG算法， 生成重加密密钥rk_(Γ.S’)。然后，在(S408)中，解密装置300将所生成的重加密密 钥rk_(Γ.S’)发送给重加密装置400。

【数式148】

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

重加密装置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’)中包含的Γ。访问结构S是否受理Γ的判定方法如实施方式1中的 “第3.用于实现FPRE的概念”中说明的那样。

跨度程序计算部441在访问结构S受理Γ的情况下(S504：受理)使处理进入 (S505)。另一方面，在访问结构S拒绝Γ的情况下(S504：拒绝)结束处理。

(S505：签名验证步骤)

签名验证部442通过处理装置判定计算数式149的结果是否为1。签名验证部442 在结果为1的情况下(S505：正当)使处理进入(S506)。另一方面，签名验证部 442在结果为0的情况下(S505：不当)结束处理。

【数式149】

(S506：随机数生成步骤)

随机数生成部451通过处理装置，如数式150所示生成随机数。

【数式150】

(S507：f向量生成步骤)

f向量生成部452通过处理装置，如数式151所示随机生成具有r个要素的向量 f^→’。

【数式151】

(S508：s向量生成步骤)

s向量生成部453通过处理装置，根据访问结构S中包含的(L行×r列)的矩阵 M、向量f^→’，如数式152所示生成向量s^→’T。

【数式152】

${{\overrightarrow{S}}^{\prime }}^T:={(S_1^{\prime },\mathrm{...},S_L^{\prime })}^T:=M·{{\overrightarrow{f}}^{\prime }}^T$

并且，s向量生成部453通过处理装置，根据向量f^→’，如数式153所示生成值 s₀’。

【数式153】

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

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

转换信息W₂生成部454通过处理装置，如数式154所示生成转换信息W₂。

【数式154】

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

转换信息W₂加密部455通过处理装置计算数式155，通过函数型加密对转换信 息W₂进行加密，生成加密转换信息ψ^renc。由于转换信息W₂以访问结构S’作为输入 并通过函数型加密被加密，所以，转换信息W₂被设定能够对重加密密文CT_S’进行 解密的用户的属性信息并被加密。

【数式155】

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

密文c^renc生成部456通过处理装置，如数式156所示生成密文c^renc₀。

【数式156】

并且，密文c^renc生成部456通过处理装置，针对i＝1、...、L的各整数i，如数式 157所示生成密文c^renc_i。

【数式157】

并且，密文c^renc生成部456通过处理装置，如数式158所示生成密文c^renc_d+1。

【数式158】

$c_{d+1}^{renc}=c_{d+1}^{enc}·g_T^{{\zeta }^{\prime }}$

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

解密密钥k^*renc生成部457通过处理装置，如数式159所示生成解密密钥k^*renc₀。

【数式159】

并且，解密密钥k^*renc生成部457通过处理装置，针对属性集合Γ中包含的各整 数t，如数式160所示生成解密密钥k^*renc_t。

【数式160】

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

重加密密文发送部460通过例如通信装置，经由网络秘密地向重加密装置400 发送将访问结构S’、访问结构S、属性集合Γ、解密密钥k^*renc₀、k^*renc_t、密文c^renc₀、 c^renc_i、c^renc_d+1、加密转换信息ψ^rk、加密转换信息ψ^renc作为要素的重加密密文CT_S’。 当然，重加密密文CT_S’也可以通过其它方法发送给重加密装置400。

即，在(S501)～(S512)中，重加密装置400执行数式161-1、数式161-2所 示的REnc算法，生成重加密密文CT_S’。然后，在(S513)中，重加密装置400将所 生成的重加密密文CT_S’发送给重加密密文解密装置500。

【数式161-1】

【数式161-2】

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

重加密密文解密装置500具有解密密钥接收部510、密文接收部520、跨度程序 计算部530、补充系数计算部540、转换信息生成部550、转换部560、配对运算部 570、消息计算部580。另外，将配对运算部570和消息计算部580统称为解密部。

根据图16对Dec1算法的处理进行说明。

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

解密密钥接收部510通过例如通信装置，经由网络接收从密钥生成装置100发送 的解密密钥sk_Γ’。并且，解密密钥接收部310接收密钥生成装置100生成的公开参数 pk。

(S602：密文接收步骤)

密文接收部520通过例如通信装置，经由网络接收重加密装置400发送的重加密 密文CT_S’。

(S603：跨度程序计算步骤)

跨度程序计算部530通过处理装置判定重加密密文CT_S’中包含的访问结构S是 否受理重加密密文CT_S’中包含的Γ，并且判定重加密密文CT_S’中包含的访问结构S’ 是否受理解密密钥sk_Γ’中包含的Γ’。访问结构S是否受理Γ以及访问结构S’是否受 理Γ’的判定方法如实施方式1中的“第3.用于实现FPRE的概念”中说明的那样。

跨度程序计算部530在访问结构S受理Γ且访问结构S’受理Γ’的情况下(S603： 受理)使处理进入(S604)。另一方面，在访问结构S拒绝Γ或访问结构S’拒绝Γ’ 的情况下(S603：拒绝)结束处理。

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

补充系数计算部540通过处理装置计算成为数式162的I、常数(补充系数) {α_i}_i∈I。

【数式162】

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

转换信息生成部550通过处理装置，如数式163所示生成转换信息W₁^～、W₂^～。

【数式163】

${\tilde{W}}_1\stackrel{R}{\leftarrow }{\mathrm{Dec}}_{CP-FE}({\mathrm{pk}}^{CP-FE},{\mathrm{sk}}_{\Gamma }^{CP-FE},{\psi }^{rk}),$

${\tilde{W}}_2\stackrel{R}{\leftarrow }{\mathrm{Dec}}_{CP-FE}({\mathrm{pk}}^{CP-FE},{\mathrm{sk}}_{\Gamma }^{CP-FE},{\psi }^{renc})$

(S606：转换步骤)

转换部560通过处理装置，如数式164所示对解密密钥k^*renc₀的基进行转换并生 成解密密钥并且对密文c^renc₀的基进行转换并生成密文c₀^～。

【数式164】

${\tilde{k}}_0^{*}:=k_0^{*renc}{\tilde{W}}_1^{-1},$

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

(S607：配对运算步骤)

配对运算部570通过处理装置计算数式165，生成会话密钥K^～。

【数式165】

(S608：消息计算步骤)

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

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

【数式166】

根据图17对Dec2算法的处理进行说明。

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

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

(S702：密文接收步骤)

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

(S703：跨度程序计算步骤)

跨度程序计算部361通过处理装置判定密文ct_S中包含的访问结构S是否受理解 密密钥sk_Γ中包含的Γ。访问结构S是否受理Γ的判定方法如实施方式1中的“第3. 用于实现FPRE的概念”中说明的那样。

跨度程序计算部361在访问结构S受理Γ的情况下(S703：受理)使处理进入 (S704)。另一方面，在访问结构S拒绝Γ的情况下(S703：拒绝)结束处理。

(S704：签名验证步骤)

签名验证部362通过处理装置判定计算数式167的结果是否为1。签名验证部442 在结果为1的情况下(S704：正当)使处理进入(S705)。另一方面，签名验证部 442在结果为0的情况下(S704：不当)结束处理。

【数式167】

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

补充系数计算部370通过处理装置计算成为数式168的I、常数(补充系数) {α_i}_i∈I。

【数式168】

(S706：配对运算步骤)

配对运算部380通过处理装置计算数式169，生成会话密钥K。

【数式169】

(S707：消息计算步骤)

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

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

【数式170】

如上所述，实施方式1的加密系统能够实现CP-FPRE方式。因此，能够利用1 个重加密密钥向各个种类的用户的集合转送密文。

其结果，例如，不用对网络上存在的各种密文进行解密而能够安全地转送给具有 各种属性的用户。由此，能够安全且实用地将密文的处理委托给可信的第三方。

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

实施方式2.

在实施方式1中，对CP-FPRE方式进行了说明。在实施方式2中，对密钥方针 的FPRE方式(Key-Policy FPRE、KP-FPRE)方式进行说明。

首先，对KP-FPRE方式的基本结构进行说明。接着，对实现该KP-FPRE方式的 加密处理系统10的基本结构进行说明。接着，对为了实现该KP-FPRE方式而使用的 部件进行说明。然后，对该实施方式的KP-FPRE方式和加密处理系统10进行详细说 明。

对KP-FPRE方式的结构进行简单说明。另外，KP(密钥方针)意味着在密钥中 嵌入Policy(方针)、即嵌入访问结构。

<第1-1.KP-FPRE方式的基本结构>

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

(Setup)

Setup算法是如下的概率算法：将保密参数λ和属性的格式n^→：＝(d；n₁，...，n_d；u₁，...， u_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}、 公开参数pk作为输入，输出密文ct_Γ。

(RKG)

RKG算法是如下的概率算法：将解密密钥sk_S、属性集合Γ’：＝{(t、x’^→_t)|x’^→_t∈F_q^nt、 1≦t≦d}、公开参数pk作为输入，输出重加密密钥rk_(S.Γ’)。

(REnc)

REnc算法是如下的概率算法：将密文ct_Γ、重加密密钥rk_(S.Γ’)、公开参数pk作 为输入，输出重加密密文CT_Γ’。

(Dec1)

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

(Dec2)

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

<第1-2.加密处理系统10>

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

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

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

密钥生成装置100将保密参数λ和属性的格式n^→：＝(d；n₁，...，n_d；u₁，...，u_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将密文ct_Γ发送给重加密装置400。

解密装置300将公开参数pk、解密密钥sk_S、属性集合Γ’作为输入来执行RKG 算法，生成重加密密钥rk_(S.Γ’)。解密装置300将重加密密钥rk_(S.Γ’)秘密地发送给重 加密装置400。

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

重加密装置400将公开参数pk、重加密密钥rk_(S.Γ’)、密文ct_Γ作为输入来执行 REnc算法，生成重加密密文CT_Γ’。重加密装置400将重加密密文CT_Γ’发送给重加密 密文解密装置500。

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

<第1-3.为了实现KP-FPRE方式而使用的部件>

为了实现KP-FPRE方式，使用密钥方针的函数型加密(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-FPRE方式和加密处理系统10的详细情况>

根据图19～图29对执行KP-FPRE方式和KP-FPRE方式的加密处理系统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的功能和动作进行说明。

密钥生成装置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。并且， 部分基B^₀、B^_t、B^^*₀、B^^*_t如数式171那样构成，与实施方式1不同。

【数式171】

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

【数式172-1】

【数式172-2】

根据图24对KG算法的处理进行说明。

(S801：信息输入步骤)

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

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

KP-FE密钥生成部144通过处理装置计算数式173，生成函数型加密的解密密钥 sk_S^KP-FE。

【数式173】

(S803：f向量生成步骤)

f向量生成部145通过处理装置，如数式174所示随机生成具有r个要素的向量 f^→。

【数式174】

(S804：s向量生成步骤)

s向量生成部146通过处理装置，根据访问结构S中包含的(L行×r列)的矩阵 M、向量f^→，如数式175所示生成向量s^→T：＝(s₁，...，s_L)^T。

【数式175】

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

并且，s向量生成部146通过处理装置，根据向量f^→，如数式176所示生成值s₀。

【数式176】

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

(S805：随机数生成步骤)

随机数生成部142通过处理装置，如数式177所示生成随机数。

【数式177】

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

解密密钥k^*生成部143通过处理装置，如数式178所示生成解密密钥k^*₀。

【数式178】

并且，解密密钥k^*生成部143通过处理装置，针对i＝1、...、L的各整数i，如数 式179所示生成解密密钥k^*_i。

【数式179】

(S807：密钥发送步骤)

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

即，在(S801)～(S806)中，密钥生成装置100执行数式180所示的KG算法， 生成解密密钥sk_S。然后，在(S807)中，密钥生成装置100将所生成的解密密钥sk_S发送给解密装置300。

【数式180】

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

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

加密装置200具有公开参数接收部210、信息输入部220、签名处理部230、加 密部240、密文发送部250。并且，加密部240具有随机数生成部243、密文c^enc生成 部244。

根据图25对Enc算法的处理进行说明。

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

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

(S902：信息输入步骤)

信息输入部220通过输入装置输入属性集合Γ：＝{(t，x^→_t：＝(x_t.1，...，x_t.nt∈Fq^nt)) |1≦t≦d}。另外，t也可以不是1以上d以下的全部整数，而是1以上d以下的至少 一部分整数。并且，属性集合Γ例如被设定了能够解密的用户的属性信息。并且，信 息输入部220通过输入装置输入要发送给解密装置300的消息m。

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

签名处理部230通过处理装置计算数式181，生成一次性签名的签名密钥sigk和 验证密钥verk。

【数式181】

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

(S904：随机数生成步骤)

随机数生成部243通过处理装置，如数式182所示生成随机数。

【数式182】

(S905：密文c^enc生成步骤)

密文c^enc生成部232通过处理装置，如数式183所示生成密文c^enc₀。

【数式183】

并且，密文c^enc生成部232通过处理装置，针对属性信息Γ中包含的各整数t， 如数式184所示生成密文c^enc_t。

【数式184】

并且，密文c^enc生成部232通过处理装置，如数式185所示生成密文c^enc_d+1。

【数式185】

$c_{d+1}^{enc}=m·g_T^{\zeta }$

(S906：签名生成步骤)

签名处理部230通过处理装置计算数式186，生成针对密文ct_Γ的要素C：＝(S， c^enc₀，{c^enc_t}_{(t、xt→)∈Γ}，c^enc_d+1)的签名Sig。

【数式186】

(S907：密文发送步骤)

密文发送部250通过例如通信装置，经由网络向解密装置300发送将属性集合Γ、 密文c^enc₀、c^enc_t、c^enc_d+1、验证密钥verk、签名Sig作为要素的密文ct_Γ。当然，密文 ct_Γ也可以通过其它方法发送给解密装置300。

即，在(S901)～(S906)中，加密装置200执行数式187所示的Enc算法， 生成密文ct_Γ。然后，在(S907)中，加密装置200将所生成的密文ct_Γ发送给解密装 置300。

【数式187】

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

解密装置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以下 的至少一部分整数。并且，属性集合Γ’例如被设定了能够对重加密密文CT_Γ’进行解 密的用户的属性信息。

(S1003：随机数生成步骤)

随机数生成部331通过处理装置，如数式188所示生成随机数。

【数式188】

(S1004：f向量生成步骤)

f向量生成部336通过处理装置，如数式189所示随机生成具有r个要素的向量 f^→’。

【数式189】

(S1005：s向量生成步骤)

s向量生成部337通过处理装置，根据访问结构S中包含的(L行×r列)的矩阵 M、向量f^→’，如数式190所示生成向量s^→’T。

【数式190】

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

并且，s向量生成部337通过处理装置，根据向量f^→’，如数式191所示生成值 s₀’。

【数式191】

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

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

转换信息W₁生成部332通过处理装置，如数式192所示生成转换信息W₁。

【数式192】

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

转换信息W₁加密部333通过处理装置计算数式193，通过函数型加密对转换信 息W₁进行加密，生成加密转换信息ψ^rk。由于转换信息W₁将属性信息Γ’作为输入并 通过函数型加密进行加密，所以，转换信息W₁被设定能够对重加密密文CT_Γ’进行解 密的用户的属性信息而被加密。

【数式193】

${\psi }^{rk}\stackrel{R}{\leftarrow }{\mathrm{Enc}}_{KP-FE}({\mathrm{pk}}^{KP-FE},{\Gamma }^{\prime },W_1)$

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

解密密钥生成部334通过处理装置，如数式194所示生成解密密钥k^*rk₀。

【数式194】

并且，解密密钥生成部334通过处理装置，针对i＝1、...、L的各整数i，如数式 195所示生成解密密钥k^*rk_i。

【数式195】

(S1009：转换步骤)

转换部335通过处理装置计算数式196，生成基D^{^*}₀。

【数式196】

(S1010：密钥发送步骤)

重加密密钥发送部340通过例如通信装置，经由网络秘密地向重加密装置400 发送将访问结构S、属性集合Γ’、解密密钥k^*rk₀、k^*rk_i、加密转换信息ψ^rk、基D^{^*}₀作为要素的重加密密钥rk_(S.Γ’)。当然，重加密密钥rk_(S.Γ’)也可以通过其它方法发送 给重加密装置400。

即，在(S1001)～(S1009)中，解密装置300执行数式197所示的RKG算法， 生成重加密密钥rk_(S.Γ’)。然后，在(S1010)中，解密装置300将所生成的重加密密 钥rk_(S.Γ’)发送给重加密装置400。

【数式197】

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

重加密装置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_Γ中包含的Γ。访问结构S是否受理Γ的判定方法如实施方式1中的“第 3.用于实现FPRE的概念”中说明的那样。

跨度程序计算部441在访问结构S受理Γ的情况下(S1104：受理)使处理进入 (S1105)。另一方面，在访问结构S拒绝Γ的情况下(S1104：拒绝)结束处理。

(S1105：签名验证步骤)

签名验证部442通过处理装置判定计算数式198的结果是否为1。签名验证部442 在结果为1的情况下(S1105：正当)使处理进入(S1106)。另一方面，签名验证部 442在结果为0的情况下(S1105：不当)结束处理。

【数式198】

$Ver(verk,C=(\Gamma ,c_0^{enc},{\left\{c_t^{enc}\right\}}_{(t,{\overrightarrow{x}}_t)\in \Gamma },c_{d+1}^{enc}),Sig)$

(S1106：随机数生成步骤)

随机数生成部451通过处理装置，如数式199所示生成随机数。

【数式199】

(S1107：f向量生成步骤)

f向量生成部452通过处理装置，如数式200所示随机生成具有r个要素的向量 f^→”。

【数式200】

(S1108：s向量生成步骤)

s向量生成部453通过处理装置，根据访问结构S中包含的(L行×r列)的矩阵 M、向量f^→”，如数式201所示生成向量s^→”T。

【数式201】

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

并且，s向量生成部453通过处理装置，根据向量f^→”，如数式202所示生成值 s₀”。

【数式202】

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

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

转换信息W₂生成部454通过处理装置，如数式203所示生成转换信息W₂。

【数式203】

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

转换信息W₂加密部455通过处理装置计算数式204，通过函数型加密对转换信 息W₂进行加密，生成加密转换信息ψ^renc。由于转换信息W₂将属性信息Γ’作为输入 并通过函数型加密进行加密，所以，转换信息W₂被设定能够对重加密密文CT_Γ’进行 解密的用户的属性信息并被加密。

【数式204】

${\psi }^{renc}\stackrel{R}{\leftarrow }{\mathrm{Enc}}_{KP-FE}({\mathrm{pk}}^{KP-FE},{\Gamma }^{\prime },W_2)$

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

密文c^renc生成部456通过处理装置，如数式205所示生成密文c^renc₀。

【数式205】

并且，密文c^renc生成部456通过处理装置，针对属性信息Γ中包含的各整数t， 如数式206所示生成密文c^renc_t。

【数式206】

并且，密文c^renc生成部456通过处理装置，如数式207所示生成密文c^renc_d+1。

【数式207】

$c_{d+1}^{renc}=c_{d+1}^{enc}·g_T^{{\zeta }^{\prime }}$

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

解密密钥k^*renc生成部457通过处理装置，如数式208所示生成解密密钥k^*renc₀。

【数式208】

并且，解密密钥k^*renc生成部457通过处理装置，针对i＝1、...、L的各整数i， 如数式209所示生成解密密钥k^*renc_i。

【数式209】

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

重加密密文发送部460通过例如通信装置，经由网络秘密地向重加密装置400 发送将属性集合Γ’、访问结构S、属性集合Γ、解密密钥k^*renc₀、k^*renc_i、密文c^renc₀、 c^renc_t、c^renc_d+1、加密转换信息ψ^rk、加密转换信息ψ^renc作为要素的重加密密文CT_Γ’。 当然，重加密密文CT_Γ’也可以通过其它方法发送给重加密装置400。

即，在(S1101)～(S1112)中，重加密装置400执行数式210-1、数式210-2 所示的REnc算法，生成重加密密文CT_Γ’。然后，在(S1113)中，重加密装置400 将所生成的重加密密文CT_Γ’发送给重加密密文解密装置500。

【数式210-1】

【数式210-2】

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

重加密密文解密装置500具有解密密钥接收部510、密文接收部520、跨度程序 计算部530、补充系数计算部540、转换信息生成部550、转换部560、配对运算部 570、消息计算部580。另外，将配对运算部570和消息计算部580统称为解密部。

根据图28对Dec1算法的处理进行说明。

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

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

(S1202：密文接收步骤)

密文接收部520通过例如通信装置，经由网络接收重加密装置400发送的重加密 密文CT_Γ’。

(S1203：跨度程序计算步骤)

跨度程序计算部530通过处理装置判定重加密密文CT_Γ’中包含的访问结构S是 否受理重加密密文CT_Γ’中包含的Γ，并且判定解密密钥sk_S’中包含的访问结构S’是否 受理重加密密文CT_Γ’中包含的Γ’。访问结构S是否受理Γ以及访问结构S’是否受理 Γ’的判定方法如实施方式1中的“第3.用于实现FPRE的概念”中说明的那样。

跨度程序计算部530在访问结构S受理Γ且访问结构S’受理Γ’的情况下(S1203： 受理)，使处理进入(S1204)。另一方面，在访问结构S拒绝Γ或访问结构S’拒绝 Γ’的情况下(S1203：拒绝)结束处理。

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

补充系数计算部540通过处理装置计算成为数式211的I、常数(补充系数) {α_i}_i∈I。

【数式211】

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

转换信息生成部550通过处理装置，如数式212所示生成转换信息W₁^～、W₂^～。

【数式212】

${\tilde{W}}_1\stackrel{R}{\leftarrow }{\mathrm{Dec}}_{KP-FE}({\mathrm{pk}}^{KP-FE},{\mathrm{sk}}_{\Gamma }^{KP-FE},{\psi }^{rk}),$

${\tilde{W}}_2\stackrel{R}{\leftarrow }{\mathrm{Dec}}_{KP-FE}({\mathrm{pk}}^{KP-FE},{\mathrm{sk}}_{\Gamma }^{KP-FE},{\psi }^{renc})$

(S1206：转换步骤)

转换部560通过处理装置，如数式213所示对解密密钥k^*renc₀的基进行转换，生 成解密密钥k^*₀^～，并且对密文c^renc₀的基进行转换，生成密文c₀^～。

【数式213】

${\tilde{k}}_0^{*}:=k_0^{*renc}{\tilde{W}}_1^{-1},$

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

(S1207：配对运算步骤)

配对运算部570通过处理装置计算数式214，生成会话密钥K^～。

【数式214】

(S1208：消息计算步骤)

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

即，在(S1201)～(S1208)中，重加密密文解密装置500执行数式215所示的 Dec1算法，生成消息m’(＝m)。

【数式215】

根据图29对Dec2算法的处理进行说明。

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

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

(S1302：密文接收步骤)

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

(S1303：跨度程序计算步骤)

跨度程序计算部361通过处理装置判定解密密钥sk_S中包含的访问结构S是否受 理密文ct_Γ中包含的Γ。访问结构S是否受理Γ的判定方法如实施方式1中的“第3. 用于实现FPRE的概念”中说明的那样。

跨度程序计算部361在访问结构S受理Γ的情况下(S1303：受理)使处理进入 (S1304)。另一方面，在访问结构S拒绝Γ的情况下(S1303：拒绝)结束处理。

(S1304：签名验证步骤)

签名验证部362通过处理装置判定计算数式216的结果是否为1。签名验证部442 在结果为1的情况下(S1304：正当)使处理进入(S1305)。另一方面，签名验证部 442在结果为0的情况下(S1304：不当)结束处理。

【数式216】

$Ver(verk,C=(\Gamma ,c_0^{enc},{\left\{c_t^{enc}\right\}}_{(t,x_t)\in \Gamma },c_{d+1}^{enc}),Sig)$

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

补充系数计算部370通过处理装置计算成为数式217的I、常数(补充系数) {α_i}_i∈I。

【数式217】

(S1306：配对运算步骤)

配对运算部570通过处理装置计算数式218，生成会话密钥K。

【数式218】

(S1307：消息计算步骤)

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

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

【数式219】

如上所述，实施方式2的加密系统能够实现KP-FPRE方式。因此，能够利用1 个重加密密钥向各个种类的用户的集合转送密文。

其结果，例如，不用对网络上存在的各种密文进行解密而能够安全地转送给具有 各种属性的用户。由此，能够安全且实用地将密文的处理委托给可信的第三方。

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

在以上的实施方式中，假设了通过FE对消息进行加密并发送到目的地的情况， 说明了重加密装置400对密文进行重加密并对密文的目的地进行变更的情况。

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

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

并且，在以上的实施方式中，设1台密钥生成装置100生成解密密钥。但是，也 可以将以上的实施方式的算法与非专利文献3所记载的分散多管理者的方式进行组 合，通过多个密钥生成装置100生成1个解密密钥。

并且，在以上的实施方式中，在追加属性范畴的情况下(增加属性的格式n^→中 的d的值的情况下)，需要再次发行公开参数。但是，也可以将以上的实施方式的算 法与非专利文献4所记载的Unbounded的方式进行组合，不用再次发行公开参数， 就能够追加属性范畴。

并且，在以上的实施方式中，当设内积加密中使用的向量的长度为N时，公开 参数和主秘密密钥的尺寸与N²成比例，在针对用户的解密密钥的生成和加密的处理 中与N²成比例需要时间。但是，也可以将以上的实施方式的算法与非专利文献5所 记载的方式进行组合，能够减小公开参数和主秘密密钥的尺寸，并且，能够缩短针对 用户的解密密钥的生成的处理和加密的处理中的时间。

实施方式3.

在以上的实施方式中，对在对偶向量空间中实现加密处理的方法进行了说明。在 实施方式3中，对在对偶加群中实现加密处理的方法进行说明。

即，在以上的实施方式中，在质数阶数q的循环群中实现了加密处理。但是，在 使用合成数M如数式220所示表示环R的情况下，在将环R作为系数的加群中，也 可以应用上述实施方式中说明的加密处理。

【数式220】

其中

整数

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，也称作 中央处理装置、处理装置、运算装置、微处理器、微计算机、处理器)。CPU 911经 由总线912与ROM 913、RAM 914、LCD 901(Liquid Crystal Display)、键盘902 (K/B)、通信板915、磁盘装置920连接，对这些硬件设备进行控制。代替磁盘装 置920(固定盘装置)，也可以是光盘装置、存储卡读写装置等存储装置。磁盘装置 920经由规定的固定盘接口进行连接。

ROM 913、磁盘装置920是非易失性存储器的一例。RAM 914是易失性存储器 的一例。ROM913、RAM914、磁盘装置920是存储装置(存储器)的一例。并且， 键盘902、通信板915是输入装置的一例。并且，通信板915是通信装置的一例。进 而，LCD 901是显示装置的一例。

在磁盘装置920或ROM 913等中存储有操作系统921(OS)、Windows系统922、 程序组923、文件组924。程序组923的程序由CPU 911、操作系统921、Windows 系统922执行。

在程序组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”等说明的功能 的软件、程序及其它程序。程序由CPU 911读出并执行。

在文件组924中存储有上述说明中的“公开参数pk”、“主秘密密钥sk”、“解 密密钥sk_S、sk_Γ”、“密文ct_Γ、ct_S”、“重加密密钥rk_(Γ、S’)、rk_(S、Γ’)”、“重加密 密文CT_S’、CT_Γ’”、“访问结构S、S’”、“属性集合Γ、Γ’”、“消息m”等信息、 数据、信号值、变量值、参数作为“文件”或“数据库”的各项目。“文件”或“数 据库”存储在盘或存储器等记录介质中。盘或存储器等存储介质中存储的信息、数据、 信号值、变量值、参数经由读写电路而由CPU 911读出到主存储器或超高速缓冲存 储器中，用于进行提取、检索、参照、比较、运算、计算、处理、输出、打印、显示 等的CPU 911的动作。在提取、检索、参照、比较、运算、计算、处理、输出、打 印、显示等的CPU 911的动作的期间内，信息、数据、信号值、变量值、参数暂时 存储在主存储器、超高速缓冲存储器、缓冲存储器中。

并且，上述说明中的流程图的箭头部分主要表示数据、信号的输入输出，数据、 信号值记录在RAM 914的存储器、其它光盘等记录介质、IC芯片中。并且，数据、 信号通过总线912、信号线、缆线、其它传送介质或电波进行在线传送。

并且，在上述说明中，作为“～部”说明的部分也可以是“～电路”、“～装置”、“～ 设备”、“～单元”、“～功能”，并且，还可以是“～步骤”、“～顺序”、“～处理”。并且， 作为“～装置”说明的部分也可以是“～电路”、“～设备”、“～单元”、“～功能”，并且， 还可以是“～步骤”、“～顺序”、“～处理”。进而，作为“～处理”说明的部分也可以是“～ 步骤”。即，作为“～部”说明的部分也可以由ROM 913中存储的固件实现。或者，可 以仅由软件实施，或者，仅由元件、器件、基板、布线等硬件实施，或者，由软件与 硬件的组合以及与固件的组合实施。固件和软件作为程序存储在ROM 913等记录介 质中。程序由CPU 911读出并由CPU 911执行。即，程序使计算机等作为上述“～部” 发挥功能。或者，使计算机等执行上述“～部”的顺序、方法。

标号说明

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