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

技术领域

本发明涉及函数型加密中的代理重加密(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中，具有与函数型加密(Functional Encryption：FE)方式有关的记载。在非专利文献3中，具有与FPRE方式有关的记载。

现有技术文献

专利文献

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

非专利文献

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

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

非专利文献3：Yutaka kawai and Katuyuki Takashima,Fully-Anonymous FunctionalProxy-Re-Encryption.Cryptology ePrint Archive：Report 2013/318

非专利文献4：R.Canetti and S.Hohenberger.Chosen-Ciphertext Secure ProxyRe-encryption.In ACMCCS 2007.

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

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

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

发明内容

发明要解决的课题

在非专利文献3所述的FPRE方式中，当对通过加密算法生成的原始密文进行重加密时，密文尺寸成为3倍。当进一步对重密文进行重加密时，密文尺寸进一步成为3倍。即，当执行n次重加密时，与原始密文相比，密文尺寸成为3ⁿ倍，相对于重加密次数，密文尺寸以指数函数的方式增加。

本发明的目的在于，实现抑制了伴随重加密的密文尺寸的增加量的FPRE方式。

用于解决课题的手段

本发明的加密系统实现在2个信息相互对应的情况下，能够利用被设定了一个信息的解密密钥对被设定了另一个信息的密文进行解密的加密方式下的代理重加密功能，其特征在于，所述加密系统具有：加密装置，其输出被设定了相互对应的属性信息x₀、v₀中的一方的密文ct₀；重加密密钥生成装置，其取得被设定了所述属性信息x₀、v₀中的另一方的解密密钥k^*，输出包含解密密钥k^*rk₀和密文ct’₁的重加密密钥rk₁，其中，所述解密密钥k^*rk₀是利用转换信息r₁对所取得的解密密钥k^*进行转换而得到的，所述密文ct’₁是被设定了相互对应的属性信息x₁、v₁中的一方且对所述转换信息r₁进行加密而得到的；以及重加密装置，其输出包含利用所述解密密钥k^*rk₀对所述密文ct₀进行解密而得到的会话密钥K’₀和所述密文ct’₁的重密文ct₁。

发明效果

在本发明的加密系统中，将利用由转换信息转换后的解密密钥对密文进行解密而得到的会话密钥和以传送目的地的利用者能够解密的方式对转换信息进行加密后的密文作为重加密密钥rk。由此，能够抑制伴随重加密的密文尺寸的增加量。

附图说明

图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是示出Setup算法的处理的流程图。

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

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

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

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

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

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

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

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

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

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

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

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

图31是示出实施方式1～4所示的加密系统10的各装置的硬件结构的例子的图。

具体实施方式

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

在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，通过z定义y，或y代入z。

【数式103】

y:＝z

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

【数式104】

A(x)→a

例如，

A(x)→1

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

【数式105】

F_q

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

【数式106】

表示

$(x_1,...,x_n)\in F_q^n.$

数式107表示数式108所示的2个矢量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】

B:＝(b₁,...,b_N),

$B^{*}:=(b_1^{*},\mathrm{...},b_N^{*})$

【数式111】

${(x_1,...,x_N)}_B:={\Sigma }_{i=1}^N{x}_i{b}_i,$

${(y_1,...,y_N)}_{B^{*}}:={\Sigma }_{i=1}^N{y}_i{b}_i^{*}$

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

【数式112】

并且，在以下的说明中，在利用下标或上标表示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

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

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

第2，对用于实现FPRE方式的空间即对偶配对矢量空间(Dual Pairing VectorSpaces：DPVS)这样的具有丰富数学构造的空间进行说明。

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

第4，对该实施方式的FPRE方式进行说明。在该实施方式中，对密文策略的FPRE方式(Ciphertext-Policy FPRE：CP-FPRE)方式进行说明。因此，首先，对CP-FPRE方式的基本结构进行说明。接着，对实现该CP-FPRE方式的加密系统10的基本结构进行说明。然后，对该实施方式的CP-FPRE方式和加密系统10进行详细说明。

<第1.FPRE>

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

FPRE具有以下的2个特征。

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

第二，除了分别对加密密钥和解密密钥设定属性信息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：＝(x1、...、xd)和V：＝(v1、...、vd)。

关于属性信息的成分，每个成分的等号关系(例如{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.对偶配对矢量空间>

首先，对对称双线性配对组进行说明。

对称双线性配对组(q、G、G^T、g、e)是质数q、位数q的循环加法组G、位数q的循环乘法组G^T、g≠0∈G、能够利用多项式时间计算的非退化双线性配对(Nondegenerate>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(x,y):={\Pi }_{i=1}^{N}e(G_i,H_i)\in G_T$

其中，

(G₁,...,G_N):＝x∈V,

(H₁,...,H_N):＝y∈V

这是非退化双线性。即，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】

其中，

(g₁,...g_N):＝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.张成方案>

图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}对应的情况下，张成方案被称作非单调。这里，设张成方案为非单调。而且，使用非单调张成方案构成访问结构(非单调访问结构)。简单地讲，访问结构是指进行对加密的访问控制。即，是指进行是否能够对密文进行解密的控制。

在后面详细叙述，由于张成方案不是单调而是非单调，由此，利用张成方案构成的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、ρ)的秘密分散方式进行说明。

另外，秘密分散方式是指使秘密信息分散而成为没有意义的分散信息。例如，使秘密信息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,\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方式在张成方案中应用内积谓语和秘密分散方式构成访问结构。因此，通过设计张成方案中的矩阵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)、表示重加密次数的上限值的值Q作为输入而输出公开参数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、表示对要进行重加密的密文ctⁿ_S进行重加密的次数的值n作为输入而输出重加密密钥rkⁿ_Γ.S’的概率算法。

(REnc)

REnc算法是将密文ctⁿ_S、重加密密钥rkⁿ_Γ.S’、公开参数pk作为输入而输出重密文ctⁿ⁺¹_S’的概率算法。

(Dec1)

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

(Dec2)

Dec2算法是将密文ctⁿ_S(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)、值Q作为输入来执行Setup算法，生成公开参数pk和主密钥sk。

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

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

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

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

重加密装置400将公开参数pk、重加密密钥rkⁿ_Γ.S’、密文ctⁿ_S作为输入来执行REnc算法，生成重密文ctⁿ⁺¹_S’。重加密装置400向重密文解密装置500发送重密文ctⁿ⁺¹_S’。

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

<第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的功能和动作进行说明。

如图6所示，密钥生成装置100具有主密钥生成部110、主密钥存储部120、信息输入部130、解密密钥生成部140、密钥发送部150(密钥输出部)。并且，解密密钥生成部140具有随机数生成部141、解密密钥k^*生成部142。

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

(S101：初始设定步骤)

主密钥生成部110执行初始设定。

具体而言，主密钥生成部110执行以下的(1)～(3)的处理。

(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、G_T、g、e)的值。

(3)主密钥生成部110在N₀中设定5，关于t＝1、...、d的各整数t，在N_t中设定n_t+w_t+z_t+1。

(S102：重加密次数输入步骤)

主密钥生成部110通过输入装置输入表示重加密次数的上限的值Q。值Q是1以上的整数。

主密钥生成部110反复执行j＝0、...、Q次以下的S103～S105的处理。

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

主密钥生成部110通过处理装置，针对t＝0、...、d的各整数t计算数式122，生成参数param_n→、基B_0.j和基B^*_0.j、基B_t.j和基B^*_t.j。

【数式122】

(1)

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

(2)

(3)

(4)

(5)

$b_{t.j,i}^{*}:={\Sigma }_{j=1}^{N_t}{\nu }_{t,i,j}{a}_{t,j},B_{t,j}^{*}:=(b_{t.j,1}^{*},\mathrm{...},b_{t.j,N_t}^{*})$

(6)

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

(1)主密钥生成部110生成随机数ψ_j。并且，主密钥生成部110在g_T.j中设定e(G、G)^ψj。

关于t＝0、...、d的各整数t，执行(2)～(5)的处理。

(2)主密钥生成部110将安全参数λ、N_t、param_G：＝(q、G、G_T、g、e)的值作为输入来执行算法G_dpvs，生成对偶配对矢量空间的参数param_Vt：＝(q、V_t、G_T、A_t、e)的值。

(3)主密钥生成部110将N_t、F_q作为输入，随机生成线性变换X_t：＝(χ_t、i、j’)_i、j’。另外，GL是General>t、i、j’)_i、j’意味着与矩阵χ_t、i、j’的小标i、j’有关的矩阵。这里，在(χ_t、i、j’)_i、j’中，i、j’＝1、...、N_t。

(4)主密钥生成部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。

(5)主密钥生成部110根据(3)中生成的线性变换X_t，根据(2)中生成的标准基A_t生成基B_t.j。主密钥生成部110根据(4)中生成的(ν_t、i、j’)_i、j’，根据(2)中生成的标准基A_t生成基B^*_t.j。

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

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

主密钥生成部110通过处理装置，如数式123所示生成基B_0.j的部分基B^_0.j、基B_t.j的部分基B^_t.j、基B^*_0.j的部分基B^^*_0.j、基B^*_t.j的部分基B^^*_t.j。

【数式123】

${\hat{B}}_{0.j}^{*}:=(b_{0.j,2}^{*},b_{0.j,4}^{*}),$

主密钥生成部110将安全参数λ、param_n→.j、部分基B^_0.j、B^_t.j、B^^*_0.j、B^^*_t.j作为公开参数pk。

(S105：主密钥生成步骤)

主密钥生成部110将基矢量b^*_0.j.1作为主密钥sk。

(S106：主密钥存储步骤)

主密钥存储部120将(S104)中生成的公开参数pk存储在存储装置中。并且，主密钥存储部120将(S105)中生成的主密钥sk存储在存储装置中。

即，在(S101)～(S105)中，密钥生成装置100执行数式124所示的Setup算法，生成公开参数pk和主密钥sk。然后，在(S106)中，密钥生成装置100将生成的公开参数pk和主密钥sk存储在存储装置中。

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

【数式124】

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

${\mathrm{param}}_G:=(q,G,G_T,g,e)\stackrel{R}{\leftarrow }{G}_{bpg}\left(1^{\lambda }\right),$

N₀:＝5,N_t:＝n_t+w_t+z_t+1for>

for j＝0,...,Q,

${\psi }_j\stackrel{U}{\leftarrow }{F}_q^{\times },g_{T.j}:=e{(g,g)}^{{\psi }_j},$

for t＝0,...,d

$X_t=\left(\begin{array}{c}{\tilde{\chi }}_{t,1}\\ .\\ .\\ .\\ {\tilde{\chi }}_{t,N_t}\end{array}\right):={\left({\chi }_{t,i,j^{\prime }}\right)}_{i,j^{\prime }}\stackrel{U}{\leftarrow }GL(N_t,F_q),$

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

$b_{t.j,i}:={\Sigma }_{j=1}^{N_t}{\chi }_{t,i,j^{\prime }}{a}_{t,j^{\prime }},B_{t.j}:=(b_{t.j,1},\mathrm{...},b_{t.j,N_t}),,$

$b_{t.j,i}^{*}:={\Sigma }_{j=1}^{N_t}{\nu }_{t,i,j^{\prime }}{a}_{t,j^{\prime }},B_{t,j}^{*}:=(b_{t.j,1}^{*},\mathrm{...},b_{t.j,N_t}^{*}),$

${\hat{B}}_{0.j}^{*}:=(b_{0.j,2}^{*},b_{0.j,4}^{*}),$

$sk=\left({\left\{b_{0.j,1}^{*}\right\}}_{j=0,\mathrm{...},Q}\right).$

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

(S201：信息输入步骤)

信息输入部130通过输入装置输入属性集合另外，t也可以不是1以上d以下的全部整数而是1以上d以下的至少一部分整数。并且，属性集合Γ例如设定解密密钥sk_Γ的使用者的属性信息。

(S202：随机数生成步骤)

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

【数式125】

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

解密密钥k^*生成部142通过处理装置，关于j＝0、...、Q的各整数j，如数式126所示生成解密密钥k^*_0、j。

【数式126】

另外，相对于数式110所示的基B和基B^*，是数式111。因此，数式126意味着设定1作为基B^*₀的基矢量b^*_0.j.1的系数，设定δ_j作为基矢量b^*_0.j.2的系数，设定0作为基矢量b^*_0.j.3的系数，设定作为基矢量b^*_0.j.4的系数，设定0作为基矢量b^*_0.j.5的系数。

并且，解密密钥k^*生成部142通过处理装置，关于属性集合Γ中包含的各整数t和j＝0、...、Q的各整数j，如数式127所示生成解密密钥k^*_t.j。

【数式127】

另外，数式127意味着设定δ_jx_t.1、...、δ_jx_t.nt作为基B^*_t的基矢量b^*_t.j.1、...、b^*_t.j.nt的系数，设定0作为基矢量b^*_t.j.nt+1、...、b^*_t.j.nt+wt的系数，设定作为基矢量b^*_t.j.nt+wt+1、...、b^*_t.j.nt+wt+zt的系数，设定0作为基矢量b^*_{t.j.nt+wt+zt+1}的系数。

(S204：密钥发送步骤)

密钥发送部150例如通过通信装置，经由网络秘密地向解密装置300发送将属性集合Γ、解密密钥k^*_0.j、k^*_t.j作为要素的解密密钥sk_Γ。当然，也可以通过其它方法向解密装置300发送解密密钥sk_Γ。

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

【数式128】

$KG=(pk,sk,\Gamma =(\{t,{\overrightarrow{x}}_t)|{\overrightarrow{x}}_t\in F_q^{n_t}\{\overrightarrow{0}\},1\le t\le d\}):$

for j＝0,...,Q

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

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

如图7所示，加密装置200具有公开参数接收部210、信息输入部220、加密部230、密文发送部240(密文输出部)。并且，加密部230具有f矢量生成部231、s矢量生成部232、随机数生成部233、密文c生成部234。

根据图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)。另外，M是L行r列的矩阵。

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

并且，信息输入部220通过输入装置输入重加密次数n。这里输入的重加密次数n通常为0，在后述RKG算法中调出Enc算法的情况下，成为由RKG算法指定的值。

(S303：f矢量生成步骤)

f矢量生成部231通过处理装置，如数式129所示生成矢量f^→。

【数式129】

(S304：s矢量生成步骤)

s矢量生成部232通过处理装置，如数式130所示生成矢量s^→T。

【数式130】

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

并且，s矢量生成部232通过处理装置，如数式131所示生成值s₀。

【数式131】

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

(S305：随机数生成步骤)

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

【数式132】

${\eta }_{0.n},\zeta \stackrel{U}{\leftarrow }{F}_q,$

(S306：密文c生成步骤)

密文c生成部234通过处理装置，如数式133所示生成密文c_0.n。

【数式133】

c_0.n:＝(ζ,-s₀,0,0,η_0.n)B_0.n

并且，密文c生成部234通过处理装置，关于i＝1、...、L的各整数i，如数式134所示生成密文c_i.n。

【数式134】

for i＝1,...,L,

$\begin{array}{cc}if& \rho \left(i\right)=(t,{\overrightarrow{v}}_i)\end{array},$

并且，密文c生成部234通过处理装置，如数式135所示生成密文c_T.n。

【数式135】

$c_{T.n}:=m·g_{T.n}^{\zeta }$

(S307：密文发送步骤)

密文发送部240例如通过通信装置，经由网络向解密装置300发送将访问结构S、密文c_0.n、c_1.n、...、c_L.n、c_T.n、重加密次数n作为要素的密文ctⁿ_S。当然，也可以通过其它方法向解密装置300发送密文ctⁿ_S。

即，在(S301)～(S306)中，加密装置200执行数式136所示的Enc算法，生成密文ctⁿ_S。然后，在(S307)中，加密装置200向解密装置300发送已生成的密文ctⁿ_S。

【数式136】

Enc＝(pk,m,S＝(M,ρ),n):

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

${\eta }_{0.n},\zeta \stackrel{U}{\leftarrow }{F}_q,$

$c_{0.n}:={(\zeta ,-s_0,0,0,{\eta }_{0.n})}_{B_{0.n}},c_{T.n}:=m·g_{T.n}^{\zeta },$

for i＝1,...,L,

$\begin{array}{cc}if& \rho \left(i\right)=(t,{\overrightarrow{v}}_i),{\theta }_{i.n},{\eta }_{i.n}\stackrel{U}{\leftarrow }{F}_q\end{array},$

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

如图8所示，解密装置300具有解密密钥接收部310(解密密钥取得部)、信息输入部320、重加密密钥生成部330、重加密密钥发送部340(重加密密钥输出部)、密文接收部350、张成方案计算部360、补充系数计算部370、配对运算部380、消息计算部390。并且，重加密密钥生成部330具有随机数生成部331、加密部332、解密密钥k^*rk生成部333。

这里，根据图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)。

并且，信息输入部320通过输入装置输入重加密次数n。这里输入的重加密次数n表示生成用于对几次重加密后的密文进行重加密的重加密密钥。即，在生成用于对一次也没重加密的密文ct⁰_S进行重加密的重加密密钥的情况下，输入0作为重加密次数n。并且，在生成用于对一次重加密后的密文ct¹_S进行重加密的重加密密钥的情况下，输入1作为重加密次数n。

(S403：随机数生成步骤)

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

【数式137】

(S404：随机数加密步骤)

加密部332通过处理装置，如数式138所示对随机数r_n+1(转换信息)进行加密，生成密文ct’ⁿ⁺¹_S’。这里，函数E_n+1是从F_q到G_T.n+1的编码函数。

【数式138】

${\mathrm{ct}}_{S^{\prime }}^{\prime n+1}:=(S^{\prime },{\left\{c_{i.n+1}\right\}}_{i=0,...,L},c_{T.n+1})$

$\stackrel{R}{\leftarrow }Enc(pk,E_{n+1}(r_{n+1}),S^{\prime }=(M^{\prime },{\rho }^{\prime }\left)\right)$

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

解密密钥k^*rk生成部333通过处理装置，如数式139所示生成解密密钥k^*rk_0.n。

【数式139】

并且，解密密钥k^*rk生成部333通过处理装置，关于属性集合Γ中包含的各整数t，如数式140所示生成解密密钥k^*rk_t.n。

【数式140】

(S406：密钥发送步骤)

重加密密钥发送部340例如通过通信装置，经由网络秘密地向重加密装置400发送将属性集合Γ、访问结构S’、解密密钥k^*rk_0.n、k^*rk_t.n、密文ct’ⁿ⁺¹_S’、重加密次数n(这里是(S402)中输入的值)作为要素的重加密密钥rkⁿ_Γ、S’。当然，也可以通过其它方法向重加密装置400发送重加密密钥rkⁿ_Γ、S’。

即，在(S401)～(S405)中，解密装置300执行数式141所示的RKG算法，生成重加密密钥rkⁿ_Γ、S’。然后，在(S406)中，解密装置300向重加密装置400发送已生成的重加密密钥rkⁿ_Γ、S’。

【数式141】

RKG＝(pk,skΓ,n,S′):

${\mathrm{ct}}_{S^{\prime }}^{\prime n+1}:=(S^{\prime },{\left\{c_{i.n+1}\right\}}_{i=0,...,L},c_{T.n+1})$

$\stackrel{R}{\leftarrow }Enc(pk,E_{n+1}(r_{n+1}),S^{\prime }=(M^{\prime },{\rho }^{\prime }\left)\right),$

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

如图9所示，重加密装置400具有公开参数接收部410、密文接收部420(密文取得部)、重加密密钥接收部430(重加密密钥取得部)、张成方案计算部440、补充系数计算部450、配对运算部460、重密文发送部470(重密文输出部)。

根据图15对REnc算法的处理进行说明。

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

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

(S502：密文接收步骤)

密文接收部420例如通过通信装置，经由网络接收加密装置200发送的密文ctⁿ_S。

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

重加密密钥接收部430例如通过通信装置，经由网络接收从解密装置300发送的重加密密钥rkⁿ_Γ、S’。

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

张成方案计算部440通过处理装置判定密文ctⁿ_S中包含的访问结构S是否受理重加密密钥rkⁿ_Γ、S’中包含的Γ。访问结构S是否受理Γ的判定方法如实施方式1中的“第3.用于实现FPRE的概念”中说明的那样。

张成方案计算部440在访问结构S受理Γ的情况下(S504：受理)，使处理进入(S505)。另一方面，在访问结构S拒绝Γ的情况下(S504：拒绝)，结束处理。

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

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

【数式142】

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

where M_i>

(S506：配对运算步骤)

配对运算部460通过处理装置计算数式143，生成会话密钥K’_n。

【数式143】

(S507：重密文发送步骤)

重密文发送部470例如通过通信装置，经由网络秘密地向重密文解密装置500发送将会话密钥K’_n、密文c_T.n、访问结构S’、密文ct’ⁿ⁺¹_S’、重加密次数n+1(这里是 (S502)中接收到的密文ctⁿ_S中包含的重加密次数n或(S503)中接收到的重加密密钥rkⁿ_Γ、S’中包含的重加密次数n加1而得到的值)作为要素的重密文ctⁿ⁺¹_S’。当然，也可以通过其它方法向重密文解密装置500发送重密文ctⁿ⁺¹_S’。

另外，这里，假设对加密装置200输出的密文ctⁿ_S(ct⁰_S)进行重加密的情况进行了说明。但是，也可以进一步对重加密装置400输出的重密文ctⁿ⁺¹_S’进行重加密。

该情况下，在(S502)中，密文接收部420代替加密装置200输出的密文ctⁿ_S而取得重加密装置400输出的重密文ctⁿ⁺¹_S’作为密文ctⁿ_S。另外，在密文ctⁿ⁺¹_S’中作为要素包含访问结构S’，但是，为了简便而将该访问结构S’改写成访问结构S。并且，在密文ctⁿ⁺¹_S’中，重加密次数成为n+1，但是，为了简便而将该重加密次数改写成n。

然后，在(S507)中，重密文发送部470向重密文解密装置500发送除了上述要素以外还将(S502)中取得的密文ctⁿ_S中包含的要素(会话密钥{K’_j}_{j＝1、...、n}和密文{c_T.j}_{j＝0、...、n-1})作为要素的重密文ctⁿ⁺¹_S’。

其它处理如上所述。

即，在(S501)～(S506)中，重加密装置400执行数式144所示的REnc算法，生成重密文ctⁿ⁺¹_S’。然后，在(S507)中，重加密装置400向重密文解密装置500发送已生成的重密文ctⁿ⁺¹_S’。

【数式144】

$REnc=(pk,{\mathrm{rk}}_{\Gamma ,S^{\prime }}^n,{\mathrm{ct}}_S^n)$

If S acceptsΓ,then com pute I and{α_i}_i∈I>

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

where M_i>

另外，在(S502)中接收到的密文ctⁿ_S中包含的重加密次数n和(S503)中接收到的重加密密钥rkⁿ_Γ、S’中包含的重加密次数n不一致的情况下，无法进行重加密。

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

如图10所示，重密文解密装置500具有解密密钥接收部510、密文接收部520、张成方案计算部530、补充系数计算部540、配对运算部550、随机数计算部560、消息计算部570。

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

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

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

(S602：密文接收步骤)

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

另外，在REnc算法中是输出重密文ctⁿ⁺¹_S’，但是，这里，将表记变更成重密文ctⁿ_S’。即，在利用重加密密钥rkⁿ_Γ、S’(rk⁰_Γ、S’)对重加密次数0(n＝0)的密文ctⁿ_S(ct⁰_S)进行重加密而生成重密文ctⁿ⁺¹_S(ct⁰⁺¹_S)的情况下，这里，将该重密文ctⁿ⁺¹_S(ct⁰⁺¹_S)表记成重密文ctⁿ_S(ct¹_S)。

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

张成方案计算部530通过处理装置判定重密文ctⁿ_S’中包含的访问结构S’是否受理解密密钥sk_Γ’中包含的Γ’。访问结构S’是否受理Γ’的判定方法如实施方式1中的“第3.用于实现FPRE的概念”中说明的那样。

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

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

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

【数式145】

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

where M_i'>

(S605：配对运算步骤)

配对运算部550通过处理装置计算数式146，生成会话密钥K’_n。

【数式146】

(S606：随机数计算步骤)

随机数计算部560通过处理装置计算数式147，生成随机数r_n。

【数式147】

E_n(r_n):＝c_T.n/K'_n,

r_n:＝decode(E_n(r_n))

进而，在n为2以上的情况下，随机数计算部560通过处理装置，关于j＝n-1、...、1的各整数j，依次计算数式148，生成随机数r₁。

【数式148】

$E_j\left(r_j\right):=c_{T.j}/{\left(K_j^{\prime }\right)}^{r_{j+1}},$

r_j:＝decode(E_j(r_j))

(S607：消息计算步骤)

消息计算部570通过处理装置计算m＝c_T.0/(K’₀)^r1，生成消息m。这里，r1意味着随机数r₁。

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

【数式149】

$Dec1=(pk,{\mathrm{sk}}_{{\Gamma }^{\prime }},{\mathrm{ct}}_{S^{\prime }}^n)$

If S′acceptsΓ′,then com pute I and{α_i}_i∈I>

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

where M_i'is>

E_n(r_n):＝c_T.n/K'_n,r_n:＝decode(E_n(r_n)),

for j＝n-1,...,1,

$E_j\left(r_j\right):=c_{T.j}/{\left(K_j^{\prime }\right)}^{r_{j+1}},r_j:=decode\left(E_j\right(r_j\left)\right),$

m:＝c_T.0/(K'₀)r₁,

return m.

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

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

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

(S702：密文接收步骤)

密文接收部350例如通过通信装置，经由网络接收加密装置200发送的密文ctⁿ_S(ct⁰_S)。

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

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

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

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

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

【数式150】

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

where M_i>

(S705：配对运算步骤)

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

【数式151】

(S706：消息计算步骤)

消息计算部390通过处理装置计算m＝c_T.0/K₀，生成消息m。

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

【数式152】

$Dec2=(pk,{\mathrm{sk}}_{\Gamma },{\mathrm{ct}}_S^0)$

If S acceptsΓ,then com pute I and{α_i}_i∈I>

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

where M_i>

m:＝c_T.0/K₀,

return m.

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

特别地，在实施方式1的加密系统10中，通过一次重加密，密文尺寸增加常数尺寸的要素量。因此，即使执行n次重加密，关于密文尺寸，相对于重加密的执行次数n，仅仅是多项式倍的要素增加。与现有FPRE方式相比，这是非常高效的，能够更加广泛地使用FPRE方式。

另外，在上述说明中，解密装置300兼作重加密密钥生成装置，解密装置300不仅执行Dec2算法，还执行RKG算法。但是，重密文解密装置500作为重加密密钥生成装置，执行RKG算法，生成进一步对重密文ctⁿ_S’进行重加密的情况下的重加密密钥。因此，该情况下，重密文解密装置500还具有解密装置300具有的功能结构中的执行RKG算法所需要的功能结构。

并且，解密装置300(或重密文解密装置500)和重加密密钥生成装置也可以是不同的装置。该情况下，解密装置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₀中设定5。但是，也可以在N₀中设定1+1+w₀+z₀+β₀。这里，w₀、z₀、β₀是0以上的整数。

实施方式2

在实施方式1中说明的FPRE方式中，在Setup算法中，输入表示重加密次数的上限值的值Q，关于j＝1、...、Q的各整数j，分别生成不同的基B_t.j和基B^*_t.j。因此，重加密次数的上限值越大，则公开参数的尺寸越大，加密处理的效率越差。

在实施方式2中，对如下的FPRE方式进行说明：通过使用带索引的方法，消除重加密次数的上限值，并且，与重加密次数的上限值无关地使公开参数的尺寸固定。

在实施方式2中，省略与实施方式1相同的部分的说明，对与实施方式1不同的部分进行说明。

加密系统10的结构与图5所示的实施方式1的加密系统10的结构相同。但是，在Setup算法中不需要输入值Q。并且，构成加密系统10的各装置的结构与图6～图10所示的实施方式1的各装置的结构相同。

图18是示出Setup算法的处理的流程图。其它算法的处理流程与图12～图17所示的各算法的处理流程相同。REnc算法和Dec2算法的处理内容也与实施方式1相同。

根据图18对Setup算法的处理进行说明。

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

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

【数式153】

${\mathrm{param}}_G:=(q,G,G_T,g,e)\stackrel{R}{\leftarrow }{G}_{bpg}\left(1^{\lambda }\right),$

N₀:＝5,N_t:＝2+n_t+w_t+z_t+1for>

$\psi \stackrel{U}{\leftarrow }{F}_q^{\times },g_T:=e{(g,g)}^{\psi },$

for t＝0,...,d,

$X_t=\left(\begin{array}{c}{\tilde{\chi }}_{t,1}\\ .\\ .\\ .\\ {\tilde{\chi }}_{t,N_t}\end{array}\right):={\left({\chi }_{t,i,j}\right)}_{i,j}\stackrel{U}{\leftarrow }GL(N_t,F_q),$

$\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},$

$b_{t,i}:={\Sigma }_{j=1}^{N_t}{\chi }_{t,i,j}{a}_{t,j},B_t:=(b_{t,1},\mathrm{...},b_{t,N_t}),,$

$b_{t,i}^{*}:={\Sigma }_{j=1}^{N_t}{\nu }_{t,i,j}{a}_{t,j},B_t^{*}:=(b_{t,1}^{*},\mathrm{...},b_{t,N_t}^{*}),$

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

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

主密钥生成部110通过处理装置，如数式154所示生成基B₀的部分基B^₀、基B_t的部分基B^_t、基B^*₀的部分基B^^*₀、基B^*_t的部分基B^^*_t。

【数式154】

${\hat{B}}_0^{*}:=(b_{0,2}^{*},b_{0,4}^{*}),$

主密钥生成部110对安全参数λ、param_n→、部分基B^₀、B^_t、B^^*₀、B^^*_t进行合并，设为公开参数pk。

(S803：主密钥生成步骤)

主密钥生成部110将基矢量b^*_0.1作为主密钥sk。

(S804：主密钥存储步骤)

主密钥存储部120将(S802)中生成的公开参数pk存储在存储装置中。并且，主密钥存储部120将(S803)中生成的主密钥sk存储在存储装置中。

即，在(S801)～(S803)中，密钥生成装置100执行数式155所示的Setup算法，生成公开参数pk和主密钥sk。然后，在(S804)中，密钥生成装置100将生成的公开参数pk和主密钥sk存储在存储装置中。

【数式155】

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

${\mathrm{param}}_G:=(q,G,G_T,g,e)\stackrel{R}{\leftarrow }{G}_{bpg}\left(1^{\lambda }\right),$

N₀:＝5,N_t:＝2+n_t+w_t+z_t+1for>

$\psi \stackrel{U}{\leftarrow }{F}_q^{\times },g_T:=e{(g,g)}^{\psi },$

for t＝0,...,d,

$X_t=\left(\begin{array}{c}{\tilde{\chi }}_{t,1}\\ .\\ .\\ .\\ {\tilde{\chi }}_{t,N_t}\end{array}\right):={\left({\chi }_{t,i,j}\right)}_{i,j}\stackrel{U}{\leftarrow }GL(N_t,F_q),$

$\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},$

$b_{t,i}:={\Sigma }_{j=1}^{N_t}{\chi }_{t,i,j}{a}_{t,j},B_t:=(b_{t,1},\mathrm{...},b_{t,N_t}),,$

$b_{t,i}^{*}:={\Sigma }_{j=1}^{N_t}{\nu }_{t,i,j}{a}_{t,j},B_t^{*}:=(b_{t,1}^{*},\mathrm{...},b_{t,N_t}^{*}),$

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

${\hat{B}}_0^{*}:=(b_{0,2}^{*},b_{0,4}^{*}),$

$\mathrm{sk}=\left(b_{\mathrm{0,1}}^{*}\right).$

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

(S201)的处理与实施方式1相同。

(S202：随机数生成步骤)

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

【数式156】

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

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

【数式157】

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

【数式158】

(S204：密钥发送步骤)

密钥发送部150例如通过通信装置，经由网络秘密地向解密装置300发送将属性集合Γ、解密密钥k^*₀、k^*_t作为要素的解密密钥sk_Γ。

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

【数式159】

$KG=(pk,sk,\Gamma =(\{t,{\overrightarrow{x}}_t)|{\overrightarrow{x}}_t\in F_q^{n_t}\{\overrightarrow{0}\},1\le t\le d\}):$

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

(S301)～(S304)和(S307)的处理与实施方式1相同。

(S305：随机数生成步骤)

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

【数式160】

${\eta }_{0.n},\zeta ,{\mu }_n\stackrel{U}{\leftarrow }{F}_q,$

(S306：密文c生成步骤)

密文c生成部234通过处理装置，如数式161所示生成密文c_0.n。

【数式161】

c0.n:＝(ζ,-s0,0,0,η0.n)B₀

并且，密文c生成部234关于i＝1、...、L的各整数i，如数式162所示生成密文c_i.n。

【数式162】

for i＝1,...,L,

$\begin{array}{cc}if& \rho \left(i\right)=(t,{\overrightarrow{v}}_i)\end{array},$

并且，密文c生成部234通过处理装置，如数式163所示生成密文c_T.n。

【数式163】

$c_{T.n}:=m·g_T^{\zeta }$

即，在(S301)～(S306)中，加密装置200执行数式164所示的Enc算法，生成密文ctⁿ_S。然后，在(S307)中，加密装置200向解密装置300发送已生成的密文ctⁿ_S。

【数式164】

Enc＝(pk,m,S＝(M,ρ),n):

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

${\eta }_{0.n},\zeta ,{\mu }_n\stackrel{U}{\leftarrow }{F}_q,$

$c_{0.n}:={(\zeta ,-s_0,0,0,{\eta }_{0.n})}_{B_0},c_{T.n}:=m·g_T^{\zeta },$

for i＝1,...,L,

$\begin{array}{cc}if& \rho \left(i\right)=(t,{\overrightarrow{v}}_i),{\theta }_{i.n},{\eta }_{i.n}\stackrel{U}{\leftarrow }{F}_q\end{array},$

根据图14对RKG算法的处理进行说明。

(S401)～(S402)、(S404)、(S406)的处理与实施方式1相同。

(S403：随机数生成步骤)

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

【数式165】

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

解密密钥k^*rk生成部333通过处理装置，如数式166所示生成解密密钥k^*rk_0.n。

【数式166】

并且，解密密钥k^*rk生成部333关于属性集合Γ中包含的各整数t，如数式167 所示生成解密密钥k^*rk_t.n。

【数式167】

$for(t,{\overrightarrow{x}}_t)\in \Gamma$

即，在(S401)～(S405)中，解密装置300执行数式168所示的RKG算法，生成重加密密钥rkⁿ_Γ、S’。然后，在(S406)中，解密装置300向重加密装置400发送已生成的重加密密钥rkⁿ_Γ、S’。

【数式168】

RKG＝(pk,sk_Γ,n,S′):

${\mathrm{ct}}_{S^{\prime }}^{\prime n+1}:=(S^{\prime },{\left\{c_{i.n+1}\right\}}_{i=0,...,L},c_{T.n+1})$

$\stackrel{R}{\leftarrow }Enc(pk,E_{n+1}(r_{n+1}),S^{\prime }=(M^{\prime },{\rho }^{\prime }\left)\right),$

$for(t,{\overrightarrow{x}}_t)\in \Gamma ,$

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

(S601)～(S604)、(S606)～(S607)的处理与实施方式1相同。

(S605：配对运算步骤)

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

【数式169】

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

【数式170】

$Dec1=(pk,{\mathrm{sk}}_{{\Gamma }^{\prime }},{\mathrm{ct}}_{S^{\prime }}^n)$

If S′acceptsΓ′,then com pute I and{α_i}i∈I>

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

where M_i'is>

E_n(r_n):＝c_T.n/K'_n,r_n:＝decode(E_n(r_n)),

for j＝n-1,...,1,

$E_j\left(r_j\right):=c_{T.j}/{\left(K_j^{\prime }\right)}^{r_{j+1}},r_j:=decode\left(E_j\right(r_j\left)\right),$

m:＝c_T.0/(K'₀)r₁,

return m.

如上所述，实施方式2的加密系统10在密文c_i.0的开头2个基矢量中设定索引μ_n(n、-1)，在解密密钥k^*rk_t.n的开头2个基矢量中嵌入索引σ_n(1、n)。由此，每当进行重加密时，不用使用不同的基，能够使用相同的基进行重加密。

其结果是，不需要设定重加密次数的上限值。并且，能够与重加密次数的上限值无关地使公开参数的尺寸固定。

另外，关于设定了索引的部分，内积的结果为0即可。因此，在上述说明中，在开头2个基矢量的二维中设定了索引，但是不限于此，也可以在三维以上设定索引。并且，作为索引设定的值也不限于上述说明的值，也可以是其它值。

实施方式3

在实施方式1中，对CP-FPRE方式进行了说明。在实施方式3中，对密钥策略 的FPRE方式(Key-Policy FPRE：KP-FPRE)方式进行说明。

在实施方式3中，省略与实施方式1相同的部分的说明，对与实施方式1不同的部分进行说明。

首先，对KP-FPRE方式的基本结构进行说明。接着，对实现该KP-FPRE方式的加密系统10的基本结构进行说明。然后，对该实施方式的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；w₁、...、w_d；z₁、...、z_d)、表示重加密次数的上限值的值Q作为输入而输出公开参数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ⁿ_Γ(ct⁰_Γ)、解密密钥sk_S、公开参数pk作为输入而输出消息m或识别信息⊥的算法。

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

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

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

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

密钥生成装置100将安全参数λ、属性的格式n^→：＝(d；n₁、...、n_d；w₁、...、w_d；z₁、...、z_d)、值Q作为输入来执行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、属性集合Γ’、值n作为输入来执行RKG算法，生成重加密密钥rkⁿ_S、Γ’。解密装置300秘密地向重加密装置400发送重加密密钥rkⁿ_S、Γ’。

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

重加密装置400将公开参数pk、重加密密钥rkⁿ_S、Γ’、密文ctⁿ_Γ作为输入来执行REnc算法，生成重密文ctⁿ⁺¹_Γ’。重加密装置400向重密文解密装置500发送重密文ctⁿ⁺¹_Γ’。

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

<第1-4.KP-FPRE方式和加密系统10的详细>

根据图20～图30对KP-FPRE方式和执行KP-FPRE方式的加密系统10的功能 和动作进行说明。

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

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

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

如图20所示，密钥生成装置100具有主密钥生成部110、主密钥存储部120、信息输入部130、解密密钥生成部140、密钥发送部150(密钥输出部)。并且，解密密钥生成部140具有随机数生成部141、解密密钥k^*生成部142、f矢量生成部143、s矢量生成部144。

Setup算法的处理基本上与实施方式1中说明的Setup算法的处理相同，因此省略说明。但是，基B^₀、基B^_t、基B^*^₀、基B^*^_t中包含的基矢量与实施方式1不同。

密钥生成装置100执行数式171所示的Setup算法，生成公开参数pk和主密钥sk。

【数式171】

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

${\mathrm{param}}_G:=(q,G,G_T,g,e)\stackrel{R}{\leftarrow }{G}_{bpg}\left(1^{\lambda }\right),$

N₀:＝5,N_t:＝n_t+w_t+z_t+1for>

for j＝0,...,Q,

${\psi }_j\stackrel{U}{\leftarrow }{F}_q^{\times },g_{T.j}:=e{(g,g)}^{{\psi }_j},$

for t＝0,...,d,

$X_t=\left(\begin{array}{c}{\tilde{\chi }}_{t,1}\\ .\\ .\\ .\\ {\tilde{\chi }}_{t,N_t}\end{array}\right):={\left({\chi }_{t,i,j^{\prime }}\right)}_{i,j^{\prime }}\stackrel{U}{\leftarrow }GL(N_t,F_q),$

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

$b_{t.j,i}:={\Sigma }_{j=1}^{N_t}{\chi }_{t,i,j^{\prime }}{a}_{t,j^{\prime }},B_{t.j}:=(b_{t.j,1},\mathrm{...},b_{t.j,N_t}),,$

$b_{t.j,i}^{*}:={\Sigma }_{j=1}^{N_t}{\nu }_{t,i,j^{\prime }}{a}_{t,j^{\prime }},B_{t,j}^{*}:=(b_{t.j,1}^{*},\mathrm{...},b_{t.j,N_t}^{*}),$

${\hat{B}}_{0.j}^{*}:=(b_{0.j,2}^{*},b_{0.j,5}^{*}),$

$sk=\left({\left\{b_{0.j,1}^{*}\right\}}_{j=0,...,Q}\right).$

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

(S901：信息输入步骤)

信息输入部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)。

(S902：f矢量生成步骤)

f矢量生成部143通过处理装置，如数式172所示生成矢量f^→。

【数式172】

(S903：s矢量生成步骤)

s矢量生成部144通过处理装置，如数式173所示生成矢量s^→T：＝(s₁、...、s_L)T。

【数式173】

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

并且，s矢量生成部144通过处理装置，如数式174所示生成值s₀。

【数式174】

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

(S904：随机数生成步骤)

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

【数式175】

${\eta }_{0.j}\stackrel{U}{\leftarrow }{F}_q,j=0,...,Q,$

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

解密密钥k^*生成部142通过处理装置，关于j＝0、...、Q的各整数j，如数式176所示生成解密密钥k^*_0.j。

【数式176】

并且，解密密钥k^*生成部142通过处理装置，关于i＝1、...、L的各整数i和j＝0、...、Q的各整数j，如数式177所示生成解密密钥k^*_i.j。

【数式177】

for i＝1,...,L；j＝0,...,Q,

$\begin{array}{cc}if& \rho \left(i\right)=(t,{\overrightarrow{v}}_i)\end{array},$

(S906：密钥发送步骤)

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

即，在(S901)～(S905)中，密钥生成装置100执行数式178所示的KG算法，生成解密密钥sk_S。然后，在(S906)中，密钥生成装置100向解密装置300发送已生成的解密密钥sk_S。

【数式178】

KG＝(pk,sk,S＝(M,ρ)):

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

for j＝0,...,Q

${\eta }_{0.j}\stackrel{U}{\leftarrow }{F}_q,$

$k_{0.j}^{*}:={(1,-s_0,0,0,{\eta }_{0.j})}_{B_{0.j}^{*}},$

for i＝1,...,L,

$\left(\begin{array}{cc}if& \rho \left(i\right)=(t,{\overrightarrow{v}}_i),{\theta }_i,{\eta }_{i.j}\stackrel{U}{\leftarrow }{F}_q,\end{array}\right)$

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

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

如图21所示，加密装置200具有公开参数接收部210、信息输入部220、加密部230、密文发送部240(密文输出部)。并且，加密部230具有随机数生成部233、密文c生成部234。

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

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

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

(S1002：信息输入步骤)

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

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

并且，信息输入部220通过输入装置输入重加密次数n。这里输入的重加密次数n通常为0，在后述RKG算法中调出Enc算法的情况下，成为由RKG算法指定的值。

(S1003：随机数生成步骤)

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

【数式179】

(S1004：密文c生成步骤)

密文c生成部234通过处理装置，如数式180所示生成密文c_0.n。

【数式180】

并且，密文c生成部234通过处理装置，关于属性信息Γ中包含的各整数t，如数式181所示生成密文c_t.n。

【数式181】

并且，密文c生成部234通过处理装置，如数式182所示生成密文c_T.n。

【数式182】

$c_{T.n}:=m·g_{T.n}^{\zeta }$

(S1005：密文发送步骤)

密文发送部240例如通过通信装置，经由网络向解密装置300发送将属性集合Γ、 密文c_0.n、c_t.n、c_T.n作为要素的密文ctⁿ_Γ。当然，也可以通过其它方法向解密装置300发送密文ctⁿ_Γ。

即，在(S1001)～(S1004)中，加密装置200执行数式183所示的Enc算法，生成密文ctⁿ_Γ。然后，在(S1005)中，加密装置200向解密装置300发送已生成的密文ctⁿ_Γ。

【数式183】

$Enc=(pk,m,\Gamma =(\{t,{\overrightarrow{x}}_t)|{\overrightarrow{x}}_t\in F_q^{n_t}\{\overrightarrow{0}\},1\le t\le d\},n):$

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

如图22所示，解密装置300具有解密密钥接收部310、信息输入部320、重加密密钥生成部330、重加密密钥发送部340(重加密密钥输出部)、密文接收部350、张成方案计算部360、补充系数计算部370、配对运算部380、消息计算部390。并且，重加密密钥生成部330具有随机数生成部331、加密部332、解密密钥k^*rk生成部333。

这里，根据图27对RKG算法的处理进行说明。在后面叙述Dec2算法。

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

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

(S1102：信息输入步骤)

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

并且，信息输入部320通过输入装置输入重加密次数n。这里输入的重加密次数n表示生成用于对重加密几次的密文进行重加密的重加密密钥。

(S1103：随机数生成步骤)

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

【数式184】

$r_{n+1},{\eta }_{0.n}^{ran}\stackrel{U}{\leftarrow }{F}_q,$