签名处理系统、密钥生成装置、签名装置、验证装置、签名处理方法以及签名处理程序

技术领域

本发明涉及基于属性的签名(Attribute-Based Signatures，ABS) 方式。

背景技术

在非专利文献26、29、30、34-37、45、51中，存在与基于属性的 签名方式有关的记载。特别是，在非专利文献36、37中，存在关于支 持单调谓词的基于属性的签名方式的记载。

非专利文献1：Beimel，A.，Secure schemes for secret sharing  and key distribution.PhD Thesis，Israel Institute of Tech-nology， Technion，Haifa，Israel，1996.

非专利文献2：Belenkiy，M.，Camenisch，J.，Chase，M.， Kohlweiss，M.，Lysyanskaya，A.and Shacham，H.： Randomizable proofs and delegatable anonymous credentials. CRYPTO2009.LNCS，Springer Heidelberg(2009)

非专利文献3：Belenkiy，M.，Chase，M.，Kohlweiss，M. and Lysyanskaya，A.：P-signatures and noninteractive anonymous  credentials.TCC2008，LNCS，Springer Heidelberg(2008)

非专利文献4：Bethencourt，J.，Sahai，A.，Waters，B.： Ciphertext-policy attribute-based encryption.In：2007IEEE  Sym-posium on Security and Privacy，pp.321.334.IEEE Press(2007)

非专利文献5：Boneh，D.，Boyen，X.：Efficient selective-ID  secure identity based encryption without random oracles.In：Cachin， C.，Camenisch，J.(eds.)EUROCRYPT2004.LNCS，vol.3027， pp.223.238.Springer Heidelberg(2004)

非专利文献6：Boneh，D.，Boyen，X.：Secure identity based  encryption without random oracles.In：Franklin，M.K.(ed.) CRYPTO2004.LNCS，vol.3152，pp.443.459.Springer Heidelberg  (2004)

非专利文献7：Boneh，D.，Boyen，X.，Goh，E.：Hierarchical  identity based encryption with constant size ciphertext.In：Cramer， R.(ed.)EUROCRYPT2005.LNCS，vol.3494，pp.440.456.Springer  Heidelberg(2005)

非专利文献8：Boneh，D.，Franklin，M.：Identity-based  encryption from the Weil pairing.In：Kilian，J.(ed.)CRYPTO2001. LNCS，vol.2139，pp.213.229.Springer Heidelberg(2001)

非专利文献9：Boneh，D.，Hamburg，M.：Generalized  identity based and broadcast encryption scheme.In：Pieprzyk， J.(ed.)ASIACRYPT2008.LNCS，vol.5350，pp.455.470.Springer  Heidelberg(2008)

非专利文献10：Boneh，D.，Katz，J.，Improved efficiency  for CCA-secure cryptosystems built using identity based encryp-tion. RSA-CT2005，LNCS，Springer Verlag(2005)

非专利文献11：Boneh，D.，Waters，B.：Conjunctive， subset，and range queries on encrypted data.In：Vadhan，S.P.(ed.) TCC2007.LNCS，vol.4392，pp.535.554.Springer Heidelberg  (2007)

非专利文献12：X.Boyen：Mesh signatures.EUROCRYPT， LNCS，vol.4515，pp.210.227.Springer(2007).

非专利文献13：Boyen，X.，Waters，B.：Anonymous  hierarchical identity-based encryption(without random oracles).In： Dwork，C.(ed.)CRYPTO2006.LNCS，vol.4117，pp.290.307. Springer Heidelberg(2006)

非专利文献14：Camenisch，J.and Gross，T.：Efficient  attributes for anonymous credentials.CCS2008.

非专利文献15：Camenisch，J.and Lysyanskaya，A.：An  efficient system for non-transferable anonymous credentials with  optinal anonymity revocation.Eurocrypt2001.

非专利文献16：Camenisch，J.and Lysyanskaya，A.： Signature schemes and anonymous credentials from bilinear maps. Crypto2004.

非专利文献17：Canetti，R.，Halevi S.，Katz J.， Chosen-ciphertext security from identity-based encryption. EUROCRYPT2004，LNCS，Springer-Verlag(2004)

非专利文献18：Chaum，D.：Security without identification： Transaction systems to make big brother obsolete.CACM(1985).

非专利文献19：D.Chaum and E.van Heyst：Group signatures. In proceedings of EUROCRYPT’91，LNCS，vol.547，pp.257.265 (1991).

非专利文献20：Cocks，C.：An identity based encryption  scheme based on quadratic residues.In：Honary，B.(ed.)IMA Int. Conf.LNCS，vol.2260，pp.360.363.Springer Heidelberg(2001)

非专利文献21：Gentry，C.：Practical identity-based encryption  without random oracles.In：Vaudenay，S.(ed.)EURO-CRYPT2006. LNCS，vol.4004，pp.445.464.Springer Heidelberg(2006)

非专利文献22：Gentry，C.，Halevi，S.：Hierarchical  identity-based encryption with polynomially many levels.In： Reingold，O.(ed.)TCC2009.LNCS，vol.5444，pp.437.456. Springer Heidelberg(2009)

非专利文献23：Gentry，C.，Silverberg，A.：Hierarchical  ID-based cryptography.In：Zheng，Y.(ed.)ASIACRYPT 2002.LNCS，vol.2501，pp.548.566.Springer Heidelberg(2002)

非专利文献24：Goyal，V.，Pandey，O.，Sahai，A.，Waters， B.：Attribute-based encryption for fine-grained access control of  encrypted data.In：ACM Conference on Computer and  Communication Security2006，pp.89.98，ACM(2006)

非专利文献25：Groth，J.，Sahai，A.：Efficient  non-interactive proof systems for bilinear groups.In：Smart，N.P. (ed.)EUROCRYPT2008.LNCS，vol.4965，pp.415.432.Springer  Heidelberg(2008)

非专利文献26：S.Guo and Y.Zeng：Attribute-based Signature  Scheme，In ISA’08，pp.509.511(2008).

非专利文献27：Horwitz，J.，Lynn，B.：Towards hierarchical  identity-based encryption.In：Knudsen，L.R.(ed.)EURO-CRYPT 2002.LNCS，vol.2332，pp.466.481.Springer Heidelberg(2002)

非专利文献28：Katz，J.，Sahai，A.，Waters，B.：Predicate  encryption supporting disjunctions，polynomial equations，and  inner products.In：Smart，N.P.(ed.)EUROCRYPT2008.LNCS， vol.4965，pp.146.162.Springer Heidel-berg(2008)

非专利文献29：D.Khader：Attribute Based Group Signatures， Cryptology ePrint Archive，Report2007/159(2007).http： //eprint.iacr.org/2007/159.

非专利文献30：D.Khader：Attribute Based Group Signature  with Revocation.Cryptology ePrint Archive，Report2007/241， (2007).http：//eprint.iacr.org/2007/241.

非专利文献31：Lewko，A.，Okamoto，T.，Sahai，A.， Takashima，K.and Waters，B.：Fully Secure Functional  Encryption：Attribute-Based Encryption and(Hierarchical)Inner  Product Encryption，EUROCRYPT2010.LNCS，Springer  Heidelberg(2010)

非专利文献32：Lewko，A.B.，Waters，B.：Fully secure HIBE  with short ciphertexts.ePrint，IACR，http： //eprint.iacr.org/2009/482

非专利文献33：Lewko，A.B.，Waters，B.：Decentralizing  Attribute-Based Encryption，ePrint，IACR，http： //eprint.iacr.org/2010/351.

非专利文献34：Jin Li，Man Ho Au，Willy Susilo，Dongqing  Xie，Kui Ren：Attribute-based Signature and its Application， ASIACCS’2010，ACM(2010)

非专利文献35：J.Li and K.Kim：Attribute-based ring  signatures.2008.Available at http：//eprint.iacr.org/2008/394.To  appear in Journal of Information Sciences.

非专利文献36：Maji，H.，Prabhakaran，M.，Rosulek，M.： Attribute-Based Signatures：Achieving Attribute-Privacy and  Collusion-Resistance.ePrint，IACR，http：//eprint.iacr.org/2008/328

非专利文献37：Maji，H.，Prabhakaran，M.，Rosulek，M.： Attribute-Based Signatures.http：//www.cs.uiuc.edu/ mmp/research.html

非专利文献38：Okamoto，T.，Takashima，K.：Homomorphic  encryption and signatures from vector decomposition.In：Galbraith， S.D.，Paterson，K.G.(eds.)Pairing2008.LNCS，vol.5209，pp. 57.74.Springer Heidelberg(2008)

非专利文献39：Okamoto，T.，Takashima，K.：Hierarchical  predicate encryption for Inner-Products，In：ASIACRYPT2009， Springer Heidelberg(2009)

非专利文献40：Okamoto，T.，Takashima，K.：Fully Secure  Functional Encryption with General Relations from the Deci-sional  Linear Assumption，In：CRYPTO2010，Springer Heidelberg (2010)

非专利文献41：Ostrovsky，R.，Sahai，A.，Waters，B.： Attribute-based encryption with non-monotonic access structures.In： ACM Conference on Computer and Communication Security2007， pp.195.203，ACM(2007)

非专利文献42：Pirretti，M.，Traynor，P.，McDaniel，P.， Waters，B.：Secure attribute-based systems.In：ACM Conference  on Computer and Communication Security2006，pp.99.112，ACM， (2006)

非专利文献43：Pirretti，M.，Traynor，P.，McDaniel，P.， Waters，B.：Secure attribute-based systems.In：ACM Conference  on Computer and Communication Security2006，pp.99.112，ACM， (2006)

非专利文献44：Sahai，A.，Waters，B.：Fuzzy identity-based  encryption.In：Cramer，R.(ed.)EUROCRYPT2005.LNCS，vol. 3494，pp.457.473.Springer Heidelberg(2005)

非专利文献45：S.F.Shahandashti and R.Safavi-Naini： Threshold attribute-based signatures and their application to  anonymous credential systems.In AFRICACRYPT’09，pp.198.216 (2009).

非专利文献46：A.Shamir：Identity-based cryptosystems and  signature schemes.In CRYPTO’84，pp.47.53(1984).

非专利文献47：Shi，E.，Waters，B.：Delegating capability  in predicate encryption systems.In：Aceto，L.，Damg°ard，I.， Goldberg，L.A.，Halldorsson，M.M.，Ingolfsdottir，A.， Walukiewicz，I.(eds.)ICALP(2)2008.LNCS，vol.5126，pp. 560.578.Springer Heidelberg(2008)

非专利文献48：Shi，E.，Waters，B.：Delegating capability  in predicate encryption systems.In：Aceto，L.，Damg°ard，I.， Goldberg，L.A.，Halldorsson，M.M.，Ingolfsdottir，A.， Walukiewicz，I.(eds.)ICALP(2)2008.LNCS，vol.5126，pp. 560.578.Springer Heidelberg(2008)

非专利文献49：Waters，B.：Ciphertext-policy attribute-based  encryption：an expressive，efficient，and provably secure  realization.ePrint，IACR，http：//eprint.iacr.org/2008/290

非专利文献50：Waters，B.：Dual system encryption：Realizing  fully secure IBE and HIBE under simple assumptions.In：Halevi，S. (ed.)CRYPTO2009.LNCS，vol.5677，pp.619.636.Springer  Heidelberg(2009)

非专利文献51：Waters，B.：Dual system encryption：Realizing  fully secure IBE and HIBE under simple assumptions.In：Halevi，S. (ed.)CRYPTO2009.LNCS，vol.5677，pp.619.636.Springer  Heidelberg(2009)

发明内容

发明要解决的问题

在以往的基于属性的签名方式中，不支持非单调谓词。

本发明的目的在于，提供一种支持非单调谓词的基于属性的签名 方式。

用于解决问题的方案

本发明所涉及的签名处理系统具备密钥生成装置、签名装置以及 验证装置，使用关于t=0，···，d+1(d是1以上的整数)的各整数t的基底 B_t和基底B＊_t来执行签名处理，该签名处理系统的特征在于，

所述密钥生成装置具备：

第一信息输入部，针对t=1，···，d的至少一个以上的整数t，输 入包含识别信息t和属性信息x_t的属性集合Γ；

密钥要素0生成部，生成作为基底B＊₀的基底矢量b＊_0，1的系数 设定了规定的值δ的密钥要素k＊₀；

密钥要素t生成部，针对所述第一信息输入部所输入的属性集合 Γ中包含的各识别信息t，生成作为基底B＊_t的基底矢量b＊_t，1的系数 设定了所述规定的值δ，作为基底矢量b＊_t，2的系数设定了对属性信息 x_t乘以所述规定的值δ所得的δx_t的密钥要素k＊_t；

密钥要素d+1生成部，生成作为基底B＊_d+1的基底矢量b＊_d+1，1的系数设定了所述规定的值δ的密钥要素k＊_d+1，1以及作为基底B＊_d+1的基底矢量b＊_d+1，2的系数设定了所述规定的值δ的密钥要素k＊_d+1，2； 以及

签名密钥发送部，向所述签名装置发送包含所述密钥要素0生成 部所生成的密钥要素k＊₀、所述密钥要素t生成部所生成的关于所述属 性集合Γ中包含的各识别信息t的密钥要素k＊_t、所述密钥要素d+1 生成部所生成的密钥要素k＊_d+1，1和密钥要素k＊_d+1，2以及所述属性集 合Γ的签名密钥sk_Γ，

所述签名装置具备：

第二信息输入部，输入关于i=1，···，L(L是1以上的整数)的各 整数i的变量ρ(i)、L行r列(r是1以上的整数)的规定的矩阵M以及 消息m，其中，上述变量ρ(i)是识别信息t(t=1，···，d中的任一个整 数)与属性信息v_i的肯定形的组(t，v_i)和否定形的组￢(t，v_i)中的任一 个；

签名密钥获取部，获取所述签名密钥发送部所发送的签名密钥 sk_Γ；

补充系数计算部，基于所述第二信息输入部所输入的变量ρ(i)和 所述签名密钥获取部所获取的签名密钥sk_Γ中包含的属性集合Γ，确 定集合I，并且针对所确定的集合I中包含的i，基于作为所述第二信 息输入部所输入的矩阵M的第i行的要素的M_i，计算在将α_iM_i合计 时成为规定的矢量h^→的补充系数α_i，其中，所述集合I是i=1，···，L 的各整数i中的、变量ρ(i)是肯定形的组(t，v_i)且该组的v_i与该组的识 别信息t所表示的属性集合Γ中包含的x_t相等的i以及变量ρ(i)为否 定形的组￢(t，v_i)且该组的v_i与该组的识别信息t所表示的属性集合Γ 中包含的x_t不同的i的集合；

签名要素0生成部，生成包含所述签名密钥sk_Γ中包含的密钥要 素k＊₀的签名要素s＊₀；

签名要素i生成部，针对i=1，···，L的各整数i，在是所述补充 系数计算部所确定的集合I中包含的整数i、且变量ρ(i)是肯定形的组 (t，v_i)的情况下设为值γ_i：=α_i，在是所述集合I中包含的i、且变量ρ(i) 为否定形的组￢(t，v_i)的情况下设为值γ_i：=α_i/(v_i－x_t)，在是不包含在 所述集合I中的整数i的情况下设为值γ_i：=0，来生成包含对所述签 名密钥sk_Γ中包含的密钥要素k＊_t乘以所述值γ_i所得的γ_ik＊_t的签名要 素s＊_i；

签名要素L+1生成部，生成包含所述签名密钥sk_Γ中包含的密钥 要素k＊_d+1，1与对所述密钥要素k＊_d+1，2乘以使用所述消息m来生成的 值m’所得的m’·k＊_d+1，2之和的签名要素s＊_L+1；以及

签名数据发送部，向所述验证装置发送包含所述签名要素0生成 部所生成的签名要素s＊₀、所述签名要素i生成部所生成的关于i=1，···， L的各整数i的签名要素s＊_i、所述签名要素L+1生成部所生成的签名 要素s＊_L+1、所述消息m、所述变量ρ(i)以及所述矩阵M的签名数据σ，

所述验证装置具备：

数据获取部，获取所述签名数据发送部所发送的签名数据σ；

验证要素0生成部，作为基底B₀的基底矢量b_0，1的系数设定 -s₀-s_L+1来生成验证要素c₀，其中，-s₀-s_L+1是根据使用具有r个要素的 矢量f^→和所述矢量h^→来生成的值s₀：=h^→·f^→T和规定的值s_L+1计算 的；

验证要素i生成部，使用基于所述矢量f^→和所述数据获取部所获 取的签名数据σ中包含的矩阵M生成的列矢量s^→T：=(s₁，···，s_L)^T： =M·f_→T和关于i=1，···，L的各整数i的规定的值θ_i，针对i=1，···， L的各整数i，在变量ρ(i)是肯定形的组(t，v_i)的情况下，作为该组的 识别信息t所表示的基底B_t的基底矢量b_t，1的系数设定s_i+θ_iv_i，作为 基底矢量b_t，2的系数设定－θ_i来生成验证要素c_i，在变量ρ(i)是否定形 的组￢(t，v_i)的情况下，作为该组的识别信息t所表示的基底矢量b_t，1的系数设定s_iv_i，作为基底矢量b_t，2的系数设定－s_i来生成验证要素 c_i；

验证要素L+1生成部，作为基底B_d+1的基底矢量b_d+1，1的系数设 定根据所述规定的值s_L+1、所述值m’以及规定的值θ_L+1计算的 s_L+1-θ_L+1m’，作为基底矢量b_d+1，2的系数设定所述规定的值θ_L+1来生成 验证要素c_L+1；以及

配对运算部，针对所述验证要素0生成部所生成的验证要素c₀、所 述验证要素i生成部所生成的验证要素c_i、所述验证要素L+1生成部所 生成的验证要素c_L+1以及所述签名数据σ中包含的签名要素s＊₀、s＊_i、 s＊_L+1，进行配对运算Π_i=0^L+1e(c_i，s＊_i)，验证所述签名数据σ的正当性。

发明的效果

在本发明所涉及的基于属性的签名方式中，支持非单调谓词。因 此，实现了利用范围广的基于属性的签名方式。

附图说明

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

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

图3是s_０的说明图。

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

图5是执行基于属性的签名方式的签名处理系统10的结构图。

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

图7是表示签名装置200的功能的功能框图。

图8是表示验证装置300的功能的功能框图。

图9是表示Setup算法的处理的流程图。

图10是表示KeyGen算法的处理的流程图。

图11是表示Sig算法的处理的流程图。

图12是表示Ver算法的处理的流程图。

图13是多管理者的说明图。

图14是执行基于分散多管理者属性的签名方式的签名处理系统 10的结构图。

图15是表示各密钥生成装置100的功能的功能框图。

图16是表示签名装置200的功能的功能框图。

图17是表示验证装置300的功能的功能框图。

图18是表示GSetup算法的处理的流程图。

图19是表示ASetup算法的处理的流程图。

图20是表示AttrGen算法的处理的流程图。

图21是表示Sig算法的处理的流程图。

图22是表示Ver算法的处理的流程图。

图23是表示密钥生成装置100、签名装置200、验证装置300的 硬件结构的一例的图。

（附图标记说明）

10：签名处理系统；100：密钥生成装置；110：主密钥生成部； 111：全局参数生成部；112：管理者秘密密钥生成部；120：主密钥存 储部；130：信息输入部；140：签名密钥生成部；141：随机数生成部； 142：密钥要素0生成部；143：密钥要素t生成部；144：密钥要素 d+1生成部；145：密钥要素生成部；150：密钥分发部；200：签名装 置；210：签名密钥获取部；220：信息输入部；221：谓词信息输入部； 222：消息输入部；230：张成方案计算部；240：补充系数计算部；250： 签名数据生成部；251：随机数生成部；252：签名要素0生成部；253： 签名要素i生成部；254：签名要素L+1生成部；255：签名要素生成 部；260：签名数据发送部；300：验证装置；310：公开参数获取部； 320：数据接收部；330：验证密钥生成部；331：随机数生成部；332f： 矢量生成部；333：s矢量生成部；334：验证要素0生成部；335：验 证要素i生成部；336：验证要素L+1生成部；337：验证要素生成部； 340：配对运算部。

具体实施方式

下面，基于附图来说明发明的实施方式。

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

说明以下说明中的记述方法。

当A为随机的变量或分布时，式101表示按照A的分布从A随 机选择y。也就是说，在式101中，y是随机数。

[式101]

当A为集合时，式102表示从A均匀地选择y。也就是说，在式 102中，y是均匀随机数（uniform random number）。

[式102]

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

[式103]

y∶＝z

当a为常数时，式104表示设备(算法)A针对输入x输出a。

[式104]

Ａ（ｘ）→ａ

例如，

Ａ（ｘ）→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的转置矩阵。

当b_i(i=1，···，n)是空间V的矢量的要素时、即在是式110时， 式111表示通过式112生成的部分空间。

[式110]

[式111]

[式112]

$b_1,...,b_n(\mathrm{resp}.{\overrightarrow{x}}_1,...,{\overrightarrow{x}}_n)$

针对式113所示的基底B和基底B＊，是式114。

[式113]

[式114]

另外，在以下说明中，param_Vt中的Vt是V_t。

同样地，F_q^nt中的nt是n_t。

同样地，sk_{gid，(t，xt)}中的xt是x_t。

同样地，在以上标表示“δi，j”的情况下，该δi，j是指δ_i，j。

另外，在表示矢量的“→”附加在下标文字或上标文字的情况下， 该“→”表示以上标附加在下标文字或上标文字。

另外，在以下说明中，签名处理包括密钥生成处理、签名处理、 验证处理。

实施方式1.

在本实施方式中，说明“基于属性的签名方式”。

第1，简单说明基于属性的签名。

第2，说明具有作为用于实现基于属性的签名方式的空间的“对偶 配对矢量空间(Dual Pairing Vector Spaces，DPVS)”这样的丰富的数学 结构的空间。

第3，说明用于实现基于属性的签名方式的概念。在此，说明“张 成方案(Span Program)”、“属性矢量的内积和访问架构（access  structure）”、“秘密分散方式(秘密共享方式)”。另外，还说明“抗冲 突哈希函数(Collision Resistant Hash Functions)”。

第4，说明本实施方式所涉及的“基于属性的签名方式”。首先， 说明“基于属性的签名方式”的基本结构。接着，说明实现“基于属性的 签名方式”的“签名处理系统10”的基本结构。然后，详细说明本实施 方式所涉及的“基于属性的签名方式”和“签名处理系统10”。

<第一.基于属性的签名>

数字签名的概念由Diffie和Hellman于1976年已在论文中介绍。 其中，数字签名的概念被设为，针对签名者生成保密的签名密钥sk和 公开的验证密钥pk的对，使用签名密钥sk生成的消息m的签名σ利 用对应的验证密钥pk被验证。也就是说，设为利用验证密钥pk来确 认使用签名密钥sk签名的消息(m，σ)的签名者。

这是数字签名的必要条件之一。但是，由于签名密钥sk与验证 密钥pk的关系紧密，在签名者与利用签名来证明的内容之间的关系 上没有灵活性、隐秘性。

通过使签名密钥与验证密钥的关系变得更灵活或精练来研究了 用途广、提高了隐秘性的数字签名的改进型。

在签名的该类型中，签名密钥和验证密钥分别利用属性x和谓词 （predicate）v被参数化。而且，被签名的消息(m，σ)是利用伴随参 数x的签名密钥sk_x生成的，仅在利用公开的密钥pk和参数v而谓词 v受理属性x的情况(v(x)成立的情况)下，验证出正确。

签名的该类型中的签名者的隐秘性是指，利用签名密钥sk_x生成 的针对谓词v的签名除了v(x)成立的情况以外不泄露与属性x有关的 信息。

在谓词v是与参数v的等号关系的情况下(也就是说，仅在x=v时 v(x)成立的情况)，针对该谓词的签名的类型是基于ID的签名 (Identity-Based Signatures，IBS)(参照非专利文献46)。

此外，在基于ID的签名中，如x=v那样，谓词v唯一地识别作 为签名者的秘密密钥的sk_x的属性x。因此，在基于ID的签名中没有 隐秘性的余地。

群组签名(Group Signatures)是签名的该类型中包含的签名(参照 非专利文献19)。群组签名是伴随仅在谓词的参数v是群组标识符且属 性x是群组v的成员的标识符(或者pk_v是识别群组v的公开密钥且sk_x是 群组v的成员x的秘密密钥)的情况下v(x)成立这样的谓词v的签名。

基于隐秘性的必要条件，使用秘密密钥sk_x生成的签名除了x为 群组v的成员的情况以外不泄露与标识符x有关的信息。

基于属性的签名是签名的该类型中包含的签名，是伴随更精练的 谓词的签名(参照非专利文献26、29、30、34-36、45、51)。在基于属 性的签名中，针对签名密钥sk_x的x是属性(x₁，···，x_i)的组，用于验证 的v是阈值或访问架构的谓词。

存在的基于属性的签名方式中的谓词最广的类型是单调访问架 构(参照非专利文献36、37)。在单调访问架构中，谓词v是通过伴随 属性(v₁，···，v_j)的组的单调张成方案(M，ρ)(MSP(M，ρ))确定，仅在 MSP(M，ρ)受理(T(x_{i_1}=v₁)，···，T(x_{i_j}=v_j))的真值的矢量的情况下v(x) 成立。在此，在φ是真的情况下，T(φ)：=1，在φ是假的情况下，T(φ)： =1。例如在x=v的情况下，T(x=v)：=1，在x≠v的情况下，T(x=v)： =0。

这种单调谓词能够表现AND、OR、阈值的门（gate）。

说明针对基于属性的签名的单调谓词v的例子。

作为单调谓词v的例子，是(Institute=Univ.A)AND(TH2((Depart  ment=Biology)，(Gender=Female)，(Age=50‘s))OR(Position=Professo  r))。在此，TH2是指阈值的值为2的阈值门(也就是说，要求成立两 个以上的门)。

设Alice的属性xA是(Institute=Univ.A)，(Department=Biology)， (Position=Postdoc)，(Age=30)，(Gender=Female)，Bob的属性x_B是 (Institute=Univ.A)，(Department=Mathematics)，(Position=Professor)， (Age=45)，(Gender=Male)。属性x_A与属性x_B完全不同，但是v(x_A) 和v(x_B)都成立，这是显然的。另外，存在满足谓词v的其它大量的属 性，这是显然的。

因此，Alice和Bob能够生成该谓词中的签名。另外，根据基于 属性的签名的隐秘性必要条件，除了签名者的属性满足谓词v的情况 以外，针对谓词v的签名不泄露与签名者、即Alice和Bob(或其他) 的属性有关的信息。

在基于属性的签名中存在基于属性的消息传送(Attributed-Based  Massaging，ABM)、基于属性的认证(Attributed-Based authentication)、 trust-negotiation、leaking secrets等大量的应用(参照非专利文献36， 37)。

但是，针对非单调谓词的基于属性的签名方式连安全性弱的方式 也不存在。非单调谓词与AND、OR、阈值门同样地，能够表现NOT 的门。

也就是说，在单调谓词中，如(Institute=Univ.A)那样能够设定肯 定形的条件，但是无法如(Institute≠Univ.A)(也就是说， Not(Institute=Univ.A))那样设定否定形的条件。与此相对，在非单调 谓词中，能够设定否定形的条件。

在大学除了Univ.A以外还大量存在的情况下，难以仅使用肯定 形的条件来设定Univ.A以外这样的否定形的条件(记述变复杂)。从这 一点也可知非单调谓词的有用性。

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

首先，说明对称双线性配对群(Symmetric Bilinear Pairing  Groups)。

对称双线性配对群(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。

在以下说明中，将式115设为以1^λ为输入而输出将保密参数设为 λ的双线性配对群的参数paramG：=(q，G，G_T，g，e)的值的算法。

[式115]

g_bpg

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

对偶配对矢量空间(q，V，G_T，A，e)能够由对称双线性配对群 (param_G：=(q，G，G_T，g，e))的直积构成。对偶配对矢量空间(q，V， G_T，A，e)是素数q、式116所示的F_q上的N维矢量空间V、阶数q 的循环群G_T、空间V的标准基底A：=(a₁，···，a_N)的组，具有以下的 运算(1)(2)。在此，a_i如式117所示。

[式116]

[式117]

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

空间V中的配对由式118定义。

[式118]

在此，

这是非退化双线性。即，在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)：畸变映射

式119所示的空间V中的线性变换φ_i，j能够进行式120。

[式119]

φ_i,j(a_j)＝a_i

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

[式120]

在此，

x:=(g₁，…g_N)

在此，将线性变换φ_i，j称为畸变映射。

在以下说明中，将式121设为以1^λ(λ∈自然数)、N∈自然数、双线 性配对群的参数param_G：=(q，G，G_T，g，e)的值为输入而输出保密 参数为λ、设为N维空间V的对偶配对矢量空间的参数param_V：=(q，V， G_T，A，e)的值的算法。

[式121]

g_dpvs

此外，在此，说明由上述的对称双线性配对群构成对偶配对矢量 空间的情况。此外，还能够由非对称双线性配对群构成对偶配对矢量 空间。将以下的说明应用于由非对称双线性配对群构成对偶配对矢量 空间的情况是很容易的。

<第3.用于实现基于属性的签名方式的概念>

<第3-1.张成方案>

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

将{p₁，···，p_n}设为变量的集合。M＾：=(M，ρ)是带标签的矩阵。 在此，矩阵M是F_q上的(L行×r列)的矩阵。另外，ρ是对矩阵M的 各列附加的标签，与{p₁，···，p_n，￢p₁，···，￢p_n}中的某一个字面值 (literal)对应。此外，对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}对应起来的情况下，张成方案被称为非单调。在此，设张成方案 为非单调。而且，使用非单调张成方案构成访问架构(非单调访问架 构)。

如上所述，通过张成方案不是单调而是非单调，利用张成方案来 构成的基于属性的签名方式的利用范围变广。

<第3-2.属性矢量的内积和访问架构>

在此，使用属性矢量的内积计算上述映射γ(j)。也就是说，使用 属性矢量的内积决定将矩阵M的哪个行包含在矩阵M_δ中。

是部分全集合(sub-universe)，是属 性的集合。而且，U_t分别包含部分全集合的识别信息(t)和n_t维矢量(v^→)。 也就是说，U_t是(t，v^→)。在此，t∈{1，···，d}，v^→∈F_q^nt。

将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^nt， 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，ρ)受 理Γ。

在关于t∈{1，···，d}的所有整数t设为n_t=2且x^→：=(1，x)、v^→： =(v，-1)的情况下，该访问架构中的内积谓词的关系变为更简单的形 式。

在该情况下，(t，x^→_t)：=(t，(1，x))，(t，v^→_i)：=(t，(v_i，-1))。 但是，将这些简化来表示为(t，x_t)、(t，v_i)。于是，访问架构S成为ρ： ={1，···，L}→{(t，v)，(t’、v’)，···，￢(t，v)，￢(t’，v’)，···}(v，v’，···∈ F_q)的S：=(M，ρ)。另外，属性的集合Γ成为Γ：={(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]、或者[ρ(i)=￢(t， v_i)]∧[(t，x_t)∈Γ]∧[v_i≠x_t]的情况下，γ(j)=1，在其它情况下，γ(j)=0。

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

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

此外，秘密分散方式是指，使秘密信息分散，来设为无意义的分 散信息。例如使秘密信息s分散为10个，生成10个分散信息。在此， 10个分散信息各自不具有秘密信息s的信息。因而，即使获取到某一 个分散信息，也无法获取关于秘密信息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设为式122所示的列矢 量。

[式122]

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

[式123]

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

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

[式124]

${\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^→的α₁、α₂、α₄。

而且是式125。

[式125]

${\Sigma }_{i\in I}{\alpha }_i{s}_i:=s_0$

此外，常数{α_i}能够通过矩阵M的尺寸的多项式时间来计算。

本实施方式以及以下的实施方式所涉及的基于属性的签名方式 如上所述那样在张成方案中应用内积谓词和秘密分散方式来构成访问 架构。因此，通过设计张成方案中的矩阵M、内积谓词中的属性信息x 以及属性信息v(谓词信息)，能够自由地设计访问控制。也就是说，能 够以非常高的自由度进行访问控制的设计。此外，矩阵M的设计相当 于秘密分散方式的阈值等的条件设计。

特别是，本实施方式以及以下的实施方式所涉及的基于属性的签 名方式中的访问架构构成使用了非单调张成方案的非单调访问架构。 也就是说，本实施方式以及以下的实施方式所涉及的基于属性的签名 方式是伴随非单调谓词的签名方式。因此，访问控制的设计的自由度 变得更高。

<第3-4.抗冲突哈希函数>

抗冲突哈希函数是指难以发现输出相同的两个输入的哈希函数。

将自然数λ设为保密参数。关于与算法G_bpg有关的抗冲突哈希函数 系H和多项式poly(λ)，可以说以下的两点。

1.密钥空间系通过λ被附加索引。各密钥空间是通过KH_λ表示的 位列中的概率空间。存在以1^λ为输入的情况下的输出分布与KH_λ相等 的概率性多项式时间算法。

2.哈希函数系通过λ、从KH_λ随机地选择的hk以及D：={0，1}^poly(λ)被附加索引。在此，各函数H_hk^λ，D是从D的要素向F_q^X的映射。此外， q是算法G_bpg(1^λ)的输出param_G的最初的要素。存在以1^λ、hk和d∈ D为输入而输出H_hk^λ，D(d)的决定性多项式时间算法。

设ε为概率性多项式时间设备。针对所有λ定义式126。

[式126]

在此，

D∶＝{0，1}poly(λ)，

如果是对于任何概率性多项式时间攻击者ε，Adv_ε^H,CR(λ)都是可 忽视的程度，则H是抗冲突哈希函数系。

<第4.基于属性的签名方式的结构>

<第4-1.基于属性的签名方式的基本结构>

基于属性的签名方式具备Setup、KeyGen、Sig、Ver这四个算 法。

(Setup)

Setup算法是以保密参数λ和属性的格式n^→：=((d；n_t，u_t，w_t， z_t(t=1，···，d))为输入而输出公开参数pk和主密钥sk的概率性算法。

(KeyGen)

KeyGen算法是以作为属性的集合的Γ：={(t，x^→_t)|x^→_t∈F_q^nt\{0^→}， 1≦t≦d}、公开参数pk以及主密钥sk为输入而输出签名密钥sk_Γ的概 率性算法。

(Sig)

Sig算法是以消息m、如受理属性的集合Γ那样的访问架构S： =(M，ρ)、签名密钥sk_Γ以及公开参数pk为输入而输出包含签名s^→＊、 消息m以及访问架构S的签名数据σ的概率性算法。

(Ver)

Ver算法是以签名数据σ和公开参数pk为输入而输出布尔值 （Boolean value）1(受理)或0(拒绝)的算法。

基于属性的签名方式针对式127所示的所有公开参数pk及主密钥 sk、所有消息m、所有属性的集合Γ、式128所示的所有签名密钥sk_Γ、 受理属性的集合Γ的所有访问架构S以及式129所示的所有签名数据σ， 以概率1成立1=Ver(pk，m，S，σ)。

[式127]

[式128]

[式129]

<第4-2.签名处理系统10>

说明执行上述的基于属性的签名方式的算法的签名处理系统10。

图5是执行基于属性的签名方式的算法的签名处理系统10的结 构图。

签名处理系统10具备密钥生成装置100、签名装置200、验证装 置300。

密钥生成装置100以保密参数λ和属性的格式n^→：=((d；n_t，u_t， w_t，z_t(t=1，···，d))为输入来执行Setup算法，生成公开参数pk和主 密钥sk。而且，密钥生成装置100公开所生成的公开参数pk。另外， 密钥生成装置100以作为属性的集合的Γ：={(t，x^→_t)|x^→_t∈F_q^nt\{0^→}， 1≦t≦d}、公开参数pk和主密钥sk为输入来执行KeyGen算法，生成 签名密钥sk_Γ并向签名装置200秘密地分发。

签名装置200以消息m、如受理属性的集合Γ那样的访问架构S： =(M，ρ)、签名密钥sk_Γ以及公开参数pk为输入来执行Sig算法，生 成包含签名s^→＊、消息m以及访问架构S的签名数据σ。签名装置200 向验证装置300发送所生成的签名数据σ。

验证装置300以签名数据σ和公开参数pk为输入来执行Ver算 法，输出布尔值1(受理)或0(拒绝)。

<第4-3.基于属性的签名方式和签名处理系统10的细节>

基于图6至图12，说明基于属性的签名方式、以及执行基于属性 的签名方式的签名处理系统10的功能和动作。

图6是表示密钥生成装置100的功能的功能框图。图7是表示签 名装置200的功能的功能框图。图8是表示验证装置300的功能的功 能框图。

图9和图10是表示密钥生成装置100的动作的流程图。此外， 图9是表示Setup算法的处理的流程图，图10是表示KeyGen算法的 处理的流程图。图11是表示签名装置200的动作的流程图，是表示 Sig算法的处理的流程图。图12是表示验证装置300的动作的流程图， 是表示Ver算法的处理的流程图。

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

如图6所示，密钥生成装置100具备主密钥生成部110、主密钥 存储部120、信息输入部130(第一信息输入部)、签名密钥生成部140、 密钥分发部150(签名密钥发送部)。

另外，签名密钥生成部140具备随机数生成部141、密钥要素0 生成部142、密钥要素t生成部143、密钥要素d+1生成部144。

此外，在以下说明中，H：=(KH_λ，H_hk^λ，D)是上述的抗冲突哈希 函数系。

首先，基于图9，说明密钥生成装置100所执行的Setup算法的处 理。

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

主密钥生成部110通过处理装置计算式130，针对param_n→和 t=0，···，d+1的各整数t随机地生成基底B_t和基底B＊_t。

[式130]

$\left(1\right)\mathrm{input}{1}^{\lambda },\overrightarrow{n}:=(d;n_t,u_t,w_t,z_t)(t=0,...,d+1)$

N_t∶＝n_t+u_t+w_t+z_t for t＝0,...,d+1

关于t＝0,...,d+1的各t，执行(4)至(8)的处理。

$\left(6\right){\left(v_{t,i,j}\right)}_{i,j}:=\Psi ·{\left(X_t^T\right)}^{-1}$

(9)gT:=e(g，g)Ψ，

也就是说，主密钥生成部110执行以下的处理。

(1)主密钥生成部110通过输入装置输入保密参数λ(1^λ)和属性的 格式n^→：=((d；n_t，u_t，w_t，z_t(t=0，···，d+1))。在此，d是1以上的 整数。关于t=0的n_t是1，关于t=1，···，d的各整数t，n_t是1以上 的整数，关于t=d+1的n_t是2。关于t=0，···，d+1的各整数t，u_t、 w_t、z_t是1以上的整数。

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

(3)主密钥生成部110通过处理装置生成随机数ψ。另外，主密钥 生成部110针对t=0，···，d+1的各整数t，对N_t设定n_t+u_t+w_t+z_t。

接着，主密钥生成部110针对t=0，···，d+1的各整数t执行以下的 (4)至(8)的处理。

(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有 关的矩阵，在此，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有关的矩阵，在此，i，j=1，···，n_t。

(7)主密钥生成部110通过处理装置，基于(5)中生成的线性变换 X_t，根据(4)中生成的标准基底A_t生成基底B_t。

(8)主密钥生成部110通过处理装置，基于(6)中生成的(ν_t，i，j)_i，j， 根据(4)中生成的标准基底A_t生成基底B＊_t。

(9)主密钥生成部110通过处理装置对g_T设定e(g，g)^ψ。另外， 主密钥生成部110对param_n→设定(4)中生成的{param_Vt}_{t=0，···，d+1}和g_T。 此外，针对t=0，···，d+1和i=1，···，N_t的各整数t、i，g_T=e(b_t，i，b＊_t，i)。

即，在(S101)中，主密钥生成部110执行式131所示的算法G_ob，针 对param_n→和t=0，···，d+1的各整数t，生成基底B_t和基底B＊_t。

[式131]

N_t：n_t+u_t+w_t+z_t for t＝0,...,d+1,

For t＝0,...,d+1,

(S102：哈希密钥生成步骤)

主密钥生成部110通过处理装置计算式132，来随机地生成哈希 密钥hk。

[式132]

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

主密钥生成部110通过处理装置，针对基底B₀的部分基底B＾₀和t=1，···，d的各整数t，如式133所示那样生成基底B_t的部分基底 B＾_t和基底B_d+1的部分基底B＾_d+1。

[式133]

另外，主密钥生成部110通过处理装置，针对t=1，···，d的各整 数t，如式134所示那样生成基底B*_t的部分基底B＾＊_t和基底B_d+1的 部分基底B＾＊_d+1。

[式134]

主密钥生成部110将所生成的部分基底B＾_t(t=0，···，d+1)和部 分基底B＾＊_t(t=1，···，d+1)、(S101)中输入的保密参数λ(1^λ)、(S101) 中生成的param_n→、(S102)中生成的哈希密钥hk以及基底矢量b＊₀， _1+u0+1，···，b＊_0，1+u0+w0(在此，u0、w0是u₀、w₀)合在一起设为公开参 数pk。

(S104：主密钥生成步骤)

主密钥生成部110将基底B*₀的基底矢量b＊_0，1设为主密钥sk。

(S105：主密钥存储步骤)

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

也就是说，在(S101)至(S104)中，密钥生成装置100执行式135所 示的Setup算法来生成公开参数pk和主密钥sk。然后，在(S105)中，密 钥生成装置100将所生成的公开参数pk和主密钥sk存储在存储装置中。

此外，公开参数例如经由网络被公开，被设为签名装置200、验 证装置300能够获取的状态。

[式135]

$\mathrm{Setup}(1^{\lambda },\overrightarrow{n}:=(d;n_t,u_t,w_t,z_t)(t=0,...,d+1))$

$\mathrm{sk}:=b_{\mathrm{0,1}}^{*},$

return sk,pk.

接着，基于图10说明密钥生成装置100所执行的KeyGen算法的处 理。

(S201：信息输入步骤)

信息输入部130通过输入装置输入属性的集合Γ：={(t，x^→_t： =(x_t，i)(i=1，···，n_t))|1≦t≦d}。t也可以不是1以上且d以下的所有整 数，而是1以上且d以下的至少一部分整数。

(S202：随机数生成步骤)

随机数生成部141通过处理装置，如式136所示那样生成随机数 δ和随机数φ₀，φ_t，ι，φ_d+1，1，ι，φ_d+1，2，ι(t=1，···，d；ι=1，···，w_t)。

[式136]

(S203：密钥要素0生成步骤)

密钥要素0生成部142通过处理装置，如式137所示那样生成作 为签名密钥sk_Γ的要素的密钥要素k＊₀。

[式137]

此外，如上所述，对于式113所示的基底B和基底B＊，是式114。 因而，式137是指如下设定了基底B＊₀的基底矢量的系数。在此，简 化标记，仅用基底矢量b＊_0，i中的i的部分来确定基底矢量。例如，如 果是基底矢量1则意味着基底矢量b＊_0，1。另外，如果是基底矢量1，···， 3则意味着基底矢量b＊_0，1，···，b＊_0，3。

作为基底B＊₀的基底矢量1的系数，设定随机数δ。作为基底矢 量1+1，···，1+u₀的系数，设定0。作为基底矢量1+u₀+1，···，1+u₀+w₀的系数，设定随机数φ_0，1，···，φ_0，wo(在此，w0是w₀)。作为基底矢量 1+u₀+w₀+1，···，1+u₀+w₀+z₀的系数，设定0。

(S204：密钥要素t生成步骤)

密钥要素t生成部143通过处理装置，针对属性的集合Γ中包含 的(t，x^→_t)的各整数t，如式138所示那样生成作为签名密钥sk_Γ的要 素的密钥要素k＊_t。

[式138]

也就是说，式138与式137同样地，意味着如下设定基底B＊_t的 基底矢量的系数。此外，在此，简化标记，仅用基底矢量b＊_t，i中的i 的部分确定基底矢量。例如，如果是基底矢量1则意味着基底矢量b＊_t，1。另外，如果是基底矢量1，···，3则意味着基底矢量b＊_t，1，···，b＊_t，3。

作为基底矢量1，···，n_t的系数，设定δx_t，1，···，δx_t，nt(在此， nt是n_t)。作为基底矢量n_t+1，···，n_t+u_t的系数，设定0。作为基底矢 量n_t+u_t+1，···，n_t+u_t+w_t的系数，设定随机数φ_t，1，···，φ_t，wt(在此， wt是w_t)。作为基底矢量n_t+u_t+w_t+1，···，n_t+u_t+w_t+z_t的系数，设定0。

(S205：密钥要素d+1生成步骤)

密钥要素d+1生成部144通过处理装置，如式139所示那样生成 作为签名密钥sk_Γ的要素的密钥要素k＊_d+1，1和密钥要素k＊_d+1，2。

[式139]

也就是说，式139与式137同样地，意味着如下设定基底B＊_d+1的基底矢量的系数。此外，在此，简化标记，仅用基底矢量b＊_d+1，i中 的i的部分确定基底矢量。例如，如果是基底矢量1则意味着基底矢 量b＊_d+1，1。另外，如果是基底矢量1，···，3则意味着基底矢量b＊_d+1，1，···，b＊_d+1，3。

首先，针对密钥要素k＊_d+1，1，作为基底矢量1的系数设定随机数 δ。作为基底矢量2的系数设定0。作为基底矢量2+1，···，2+u_d+1的 系数设定0。作为基底矢量2+u_d+1+1，···，2+u_d+1+w_d+1的系数设定随 机数φ_d+1，1，1，···，φ_{d+1，1，wd+1}(在此，wd+1是w_d+1)。作为基底矢量 2+u_d+1+w_d+1+1，···，2+u_d+1+w_d+1+z_d+1的系数设定0。

另外，针对密钥要素k*_d+1，2，作为基底矢量1的系数设定0。作 为基底矢量2的系数设定随机数δ。作为基底矢量2+1，···，2+u_d+1的 系数设定0。作为基底矢量2+u_d+1+1，···，2+u_d+1+w_d+1的系数设定随 机数φ_d+1，2，1，···，φ_{d+1，2，wd+1}(在此，wd+1是w_d+1)。作为基底矢量 2+u_d+1+w_d+1+1，···，2+u_d+1+w_d+1+z_d+1的系数设定0。

(S206：密钥分发步骤)

密钥分发部150将以属性的集合Γ、密钥要素k＊₀、密钥要素k＊_t(t 是属性的集合Γ中包含的(t，x^→_t)中的t)、密钥要素k＊_d+1，1以及密钥 要素k＊_d+1，2为要素的签名密钥sk_Γ例如通过通信装置经由网络向签名 装置200秘密分发。当然，签名密钥sk_Γ也可以通过其它方法向签名 装置200分发。

也就是说，在(S201)至(S205)中，密钥生成装置100执行式140所 示的KeyGen算法来生成签名密钥sk_Γ。然后，在(S206)中，密钥生成装 置100将所生成的签名密钥sk_Γ向签名装置200分发。

[式140]

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

$T:\{0,(d+\mathrm{1,1}),(d+\mathrm{1,2})\}\cup \left\{t\right|1\le t\le d,(t,{\overrightarrow{x}}_t)\in \Gamma \},$

$\mathrm{return}{\mathrm{sk}}_{\Gamma }:=(\Gamma ,{\left\{k_t^{*}\right\}}_{t\in T}).$

说明签名装置200的功能和动作。

如图7所示，签名装置200具备签名密钥获取部210、信息输入 部220(第二信息输入部)、张成方案计算部230、补充系数计算部240、 签名数据生成部250、签名数据发送部260(签名数据输出部)。

另外，信息输入部220具备谓词信息输入部221、消息输入部222。 另外，签名数据生成部250具备随机数生成部251、签名要素0生成 部252、签名要素i生成部253、签名要素L+1生成部254。

基于图11说明签名装置200所执行的Sig算法的处理。

(S301：签名密钥获取步骤)

签名密钥获取部210例如通过通信装置经由网络获取密钥生成装 置100所生成的签名密钥sk_Γ。另外，签名密钥获取部210获取密钥 生成装置100所生成的公开参数pk。

(S302：信息输入步骤)

谓词信息输入部221通过输入装置输入访问架构S：=(M，ρ)。 此外，矩阵M是L行×r列的矩阵。L、r是1以上的整数。

另外，消息输入部222通过输入装置输入附加签名的消息m。

此外，关于访问架构S的矩阵M的设定，根据想要实现的系统 的条件进行设定。

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

张成方案计算部230通过处理装置，判定(S302)中输入的访问架 构S是否受理(S301)中获取的签名密钥sk_Γ中包含的属性的集合Γ。

此外，访问架构是否受理属性的集合的判定方法如在“第3.用于 实现函数型密码的概念”中说明的那样。

张成方案计算部230在访问架构S受理属性的集合Γ的情况下 (S303中受理)，使处理进入(S304)。另一方面，在访问架构S拒绝属 性的集合Γ的情况下(S303中拒绝)，结束处理。

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

补充系数计算部430通过处理装置，计算出成为式141的I和针 对I中包含的各整数i的常数(补充系数)α_i。

[式141]

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

此外，M_i是矩阵M的第i行。

(S305：随机数生成步骤)

随机数生成部251通过处理装置如式142所示那样生成随机数ξ 和随机数β_i(i=1，···，L)。

[式142]

(S306：签名要素0生成步骤)

签名要素0生成部252通过处理装置如式143所示那样生成作为 签名数据σ的要素的签名要素s*₀。

[式143]

$s_0^{*}:=\xi k_0^{*}+r_0^{*}$

在此，r＊₀是式144(参照式110至式112以及这些数式的说明)。

[式144]

(S307：签名要素i生成步骤)

签名要素i生成部253通过处理装置，关于i=1，···，L的各整数 i，如式145所示那样生成作为签名数据σ的要素的签名要素s＊_i。

[式145]

$s_i^{*}:={\gamma }_i·\xi k_t^{*}+{\Sigma }_{t=1}^{n_t}{y}_{i,t}·b_{t,t}^{*}+r_i^{*}\mathrm{for}1\le i\le L$

在此，r*_i是式146(参照式110至式112以及这些数式的说明)。

[式146]

另外，γ_i和y^→i：=(y_i，i’(i’=1，···，n_t)是式147。

[式147]

${\gamma }_i:=\frac{{\alpha }_i}{{\overrightarrow{v}}_i·{\overrightarrow{x}}_t},$

${\gamma }_i:=0,$

(S308：签名要素L+1生成步骤)

签名要素L+1生成部254通过处理装置如式148所示那样生成作 为签名数据σ的要素的签名要素s＊_L+1。

[式148]

在此，r＊_L+1是式149(参照式110至式112以及这些数式的说明)。

[式149]

(S309：数据发送步骤)

签名数据发送部260将包含签名要素s＊₀、签名要素s＊_i(i=1，···， L)、签名要素s＊_L+1、消息m以及访问架构S：=(M，ρ)的签名数据σ 例如通过通信装置经由网络发送给验证装置300。当然，签名数据σ 也可以通过其它方法发送给验证装置300。

也就是说，在(S301)至(S308)中，签名装置200执行式150所示的 Sig算法来生成签名数据σ。然后，在(S309)中，签名装置200将所生成 的签名数据σ向验证装置300分发。

[式150]

then compute I and{α_i}_i∈Isuch that

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

$s_i^{*}:={\gamma }_i·\xi k_t^{*}+{\Sigma }_{t=1}^{n_t}{y}_{i,t}·b_{t,t}^{*}+r_i^{*},\mathrm{for}1\le i\le L,$

$\mathrm{and}{\gamma }_i,{\overrightarrow{y}}_i:=(y_{i,1},...,y_{i,n_t})\mathrm{aredefinedas}$

γ_i∶=α_i

${\gamma }_i:=\frac{{\alpha }_i}{{\overrightarrow{v}}_i·{\overrightarrow{x}}_t},$

γ_i∶=0，

γ_i∶＝0，

$\mathrm{return}{\overrightarrow{s}}^{*}:=(s_0^{*},...,s_{L+1}^{*}).$

说明验证装置300的功能和动作。

如图8所示，验证装置300具备公开参数获取部310、数据接收 部320、验证密钥生成部330、配对运算部340。

另外，验证密钥生成部330具备随机数生成部331、f矢量生成 部332、s矢量生成部333、验证要素0生成部334、验证要素i生成 部335、验证要素L+1生成部336。

基于图12说明验证装置300所执行的Ver算法的处理。

(S401：公开参数获取步骤)

公开参数获取部310例如通过通信装置经由网络获取密钥生成装 置100所生成的公开参数pk。

(S402：签名数据接收步骤)

数据接收部320例如通过通信装置经由网络接收签名装置200所 发送的签名数据σ。

(S403：f矢量生成步骤)

f矢量生成部332通过处理装置如式151所示那样随机地生成具 有r个要素的矢量f^→。

[式151]

(S404：s矢量生成步骤)

s矢量生成部333通过处理装置，基于(S402)中接收到的签名数 据σ中包含的访问架构S的(L行×r列)的矩阵M和(S403)中生成的具 有r个要素的矢量f^→，如式152所示那样生成矢量s^→T。

[式152]

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

另外，s矢量生成部333通过处理装置，基于(S403)中生成的矢 量f^→，如式153所示那样生成值s₀。此外，1^→是所有要素为值1的矢 量。

[式153]

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

(S405：随机数生成步骤)

随机数生成部331通过处理装置，如式154所示那样生成针对 i=1，···，z₀的各整数i的随机数η_0，i、针对i=1，···，z_d+1的各整数i 的随机数η_L+1，i、随机数θ_L+1以及随机数s_L+1。

[式154]

(S406：验证要素0生成步骤)

验证要素0生成部334通过处理装置，如式155所示那样生成作 为验证密钥的要素的验证要素c₀。

[式155]

此外，如上所述，对于式113所示的基底B和基底B*，是式114。 因而，式155是指如下设定基底B₀的基底矢量的系数。在此，简化标 记，仅用基底矢量b_0，i中的i的部分确定基底矢量。例如，如果是基 底矢量1则意味着基底矢量b_0，1。另外，如果是基底矢量1，···，3则 意味着基底矢量b_0，1，···，b_0，3。

作为基底B₀的基底矢量1的系数，设定-s₀-s_L+1。作为基底矢量 1+1，···，1+u₀+w₀的系数，设定0。作为基底矢量1+u₀+w₀+1，···， 1+u₀+w₀+z₀的系数，设定随机数η_0，1，···，η_0，z0(在此，z0是z₀)。

(S407：验证要素i生成步骤)

验证要素i生成部335通过处理装置，针对i=1，···，L的各整数 i，如式156所示那样生成作为验证密钥的要素的验证要素c_i。

[式156]

也就是说，式156与式155同样地，意味着如下设定基底B_t的 基底矢量的系数。此外，在此，简化标记，仅用基底矢量b_t，i中的i 的部分确定基底矢量。例如，如果是基底矢量1则意味着基底矢量b_t，1。另外，如果是基底矢量1，···，3则意味着基底矢量b_t，1，···，b_t，3。

在ρ(i)是肯定形的组(t，v^→_i)的情况下，作为基底矢量1的系数设 定s_i+θ_iv_i，1。作为基底矢量2，···，n_t的系数设定θ_iv_i，2，···，θ_iv_i，nt(在 此，nt是n_t)。作为基底矢量n_t+1，···，n_t+u_t+w_t的系数设定0。作为 基底矢量n_t+u_t+w_t+1，···，n_t+u_t+w_t+z_t的系数设定η_i，1，···，η_i，zt(在此， zt是z_t)。

另一方面，在ρ(i)为否定形的组￢(t，v^→_i)的情况下，作为基底矢 量1，···，n_t的系数设定s_iv_i，1，···，θ_iv_i，nt(在此，nt是n_t)。作为基底 矢量2的系数设定-s_i。作为基底矢量n_t+1，···，n_t+u_t+w_t的系数设定0。 作为基底矢量n_t+u_t+w_t+1，···，n_t+u_t+w_t+z_t的系数设定η_i，1，···，η_i，zt(在 此，zt是z_t)。

此外，θ_i和η_i，i’(i’=1，···，z_t)是由随机数生成部233生成的均匀 随机数。

(S408：签名要素L+1生成步骤)

验证要素L+1生成部336通过处理装置如式157所示那样生成作 为验证密钥的要素的验证要素c_L+1。

[式157]

也就是说，式157与式155同样地，意味着如下设定基底B_d+1的基底矢量的系数。此外，在此，简化标记，仅用基底矢量b_d+1，i中 的i的部分确定基底矢量。例如，如果是基底矢量1则意味着基底矢 量b_d+1，1。另外，如果是基底矢量1，···，3则意味着基底矢量b_d+1，1，···， b_d+1，3。

作为基底矢量1的系数设定s_L+1-θ_L+1·H_hk^λ,D(m||S)。作为基底矢 量2的系数设定θ_L+1。作为基底矢量2+1，···，2+u_d+1+w_d+1的系数设 定0。作为基底矢量2+u_d+1+w_d+1+1，···，2+u_d+1+w_d+1+z_d+1的系数设定 随机数η_L+1，1，···，η_L+1，zd+1(在此，zd+1是z_d+1)。

(S409：第一配对运算步骤)

配对运算部340通过处理装置计算配对运算e(b_0，1，s＊₀)。

如果计算配对运算e(b_0，1，s＊₀)的结果为值1，则配对运算部340 输出表示签名的验证失败的值0，来结束处理。另一方面，如果计算 配对运算e(b_0，1，s＊₀)的结果不是值1，则配对运算部340使处理进入 S410。

(S410：第二配对运算步骤)

配对运算部340通过处理装置计算式158所示的配对运算。

[式158]

${\Pi }_{i=0}^{L+1}e(c_i,s_i^{*})$

如果计算式158所示的配对运算的结果为值1，则配对运算部340 输出表示签名的验证成功的值1。另一方面，如果是其它值，则配对 运算部340输出表示签名的验证失败的值0。

此外，通过如式159所示那样计算式158，如果签名数据σ是正 当的，则得到值1。

[式159]

${\Pi }_{i=0}^{L+1}e(c_i,s_i^{*})$

$=e(c_0,k_0^{*})\xi ·{\Pi }_{i\in I}e(c_i,k_t^{*}){\gamma }_i\xi ·{\Pi }_{i=1}^L{\Pi }_{t=1}^{n_t}e(c_i,b_{t,t}^{*})y_{i,t}·e(c_{L+1},s_{L+1}^{*})$

$=g_T^{\mathrm{\xi \delta }(-s_0-s_{L+1})}·{\Pi }_{i\in I}{g}_T^{\mathrm{\xi \delta }{\alpha }_i{s}_i}{\Pi }_{i=1}^L{g}_T^{{\beta }_i{s}_i}·g_T^{\mathrm{\xi \delta }{s}_{L+1}}$

$=g_T^{\mathrm{\xi \delta }(-s_0-s_{L+1})}·g_T^{\mathrm{\xi \delta }{s}_0}:g_T^{\mathrm{\xi \delta }{s}_{L+1}}=1.$

也就是说，在(S401)至(S410)中，验证装置300执行式160所示的 Ver算法来验证签名数据σ。

[式160]

for 1≤i≤L,

$\mathrm{return}0\mathrm{ife}(b_{\mathrm{0,1}},s_0^{*})=1,$

$\mathrm{return}1\mathrm{if}{\Pi }_{i=0}^{L+1}e(c_i,s_i^{*})=1,\mathrm{return}0\mathrm{otherwise}.$

如上所述，实施方式1所涉及的签名处理系统10使用利用张成方 案、内积谓词以及秘密分散构成的访问架构S，实现基于属性的签名 方式。特别是，实施方式1所涉及的签名处理系统10使用非单调张成方 案，因此实现伴随非单调谓词的基于属性的签名方式。

实施方式1所涉及的签名处理系统10所实现的基于属性的签名方 式的安全性高，满足隐秘性必要条件。此外，安全性高是指，被他人 伪造签名的可能性低。

此外，(S409)中进行配对运算e(b_0，1，s＊₀)是为了确认签名数据σ 并非是不使用保密的(作为主密钥sk的)基底矢量b＊_0，1而生成的签名数 据。

配对运算e(b_0，1，s＊₀)是确认签名要素s＊₀中是否包含基底矢量b＊_0，1、即作为基底矢量b＊_0，1的系数是否设定了0以外的值的运算。如果 配对运算e(b_0，1，s＊₀)=1，则在签名要素s＊₀中作为基底矢量b＊_0，1的 系数设定了0，签名数据σ是不使用基底矢量b＊_0，1而生成的签名数据。 因而，在该情况下，认为签名数据σ是不正当的。

此外，在上述说明中，u_t、w_t、z_t(t=0，···，d+1)的维度是为了提 高安全性而设置的维度。因而，虽然导致安全性变低，但是也可以将 u_t、w_t、z_t(t=0，···，d+1)分别设为0，来不设置u_t、w_t、z_t(t=0，···，d+1) 的维度。

另外，在上述说明中，在(S101)中对N_t设定了n_t+u_t+w_t+z_t。但是， 也可以将n_t+u_t+w_t+z_t设为n_t+n_t+n_t+1来对N_t设定3n_t+1。在此，n₀是1， n_t(t=1，···，d+1)是2。

在该情况下，式135所示的Setup算法如式161那样被改写。此 外，G_ob如式162那样被改写。

[式161]

$\mathrm{Setup}(1^{\lambda },\overrightarrow{n}:=(d;2,...,2))$

$\mathrm{sk}:=b_{\mathrm{0,1}}^{*},$

return sk,pk.

[式162]

$g_{\mathrm{ob}}(1^{\lambda },\overrightarrow{n}:=(d;2,...,2)):$

n₀:=1,n_d+1:=2,N_t:=3n_t+1for t=0，...，d+1,

For t=0，...，d+1,

${\left(v_{t,i,j}\right)}_{i,j}:=\psi ·{\left(X_t^T\right)}^{-1},$

g_T:=e(g,g)ψ,

另外，式140所示的KeyGen算法如式163那样被改写。

[式163]

KeyGen(pk,sk,Γ∶＝{(t,x_t)|1≤t≤d})

for(t,x_t)∈Г，

T:＝{0,(d+1,1),(d+1,2)}∪{t|1≤t≤d,(t,x_t)∈Γ}，

$\mathrm{returns}{k}_{\Gamma }:=(\Gamma ,{\left\{k_t^{*}\right\}}_{t\in T}).$

另外，式150所示的Sig算法如式164那样被改写。

[式164]

then compute I and{α_i}_i∈I,such that

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

$s_i^{*}:={\gamma }_i·\xi k_t^{*}+{\Sigma }_{t=1}^2{y}_{i,t}·b_{t,t}^{*}+r_i^{*},\mathrm{for}1\le i\le L,$

$\mathrm{and}{\gamma }_i,{\overrightarrow{y}}_i:=(y_{i,1},y_{i,2})\mathrm{aredefinedas}$

${\gamma }_i:=0,{\overrightarrow{y}}_i:={\beta }_i(1,v_i),$

$\mathrm{return}{\overrightarrow{s}}^{*}:=(s_0^{*},...,s_{L+1}^{*}).$

另外，式159所示的Ver算法如式165那样被改写。

[式165]

for1≤i≤L,

ifρ(i)=(t,v_i)，

$\mathrm{return}0\mathrm{ife}\left(b_{\mathrm{0,1}}{s}_0^{*}\right)=1,$

$\mathrm{return}1\mathrm{if}{\Pi }_{i=0}^{L+1}e(c_i,s_i^{*})=1,$return0otherwise.

另外，Setup算法只要在设置签名处理系统10时执行一次即可， 不需要在每次生成签名密钥时都执行。另外，在上述说明中，设为由 密钥生成装置100执行Setup算法和KeyGen算法，但是也可以由各自不 同的装置执行Setup算法和KeyGen算法。

实施方式2.

在本实施方式中，说明“基于分散多管理者属性的签名方式”。

第1，说明“分散多管理者(Decentralized Multi-Authority)”的概 念。

第2，说明本实施方式所涉及的“基于分散多管理者属性的签名方 式”。首先，说明“基于分散多管理者属性的签名方式”的基本结构。接 着，说明实现“基于分散多管理者属性的签名方式”的“签名处理系统 10”的基本结构。然后，详细说明本实施方式所涉及的“基于分散多管 理者属性的签名方式”以及“签名处理系统10”。

<第1.分散多管理者的概念>

首先，说明“多管理者”。多管理者是指，存在多个生成签名密钥 的管理者。

在一般的签名处理系统中，系统整体的保密性依赖于某一个机关 (管理者)。例如，如果是在实施方式1中说明的签名处理系统10，则 系统整体的保密性依赖于生成主密钥sk的密钥生成装置100。在密钥 生成装置100的保密性被破坏或主密钥sk被泄漏的情况下，签名处理 系统10的整体不发挥功能。

但是，通过设为多管理者，即使在一部分管理者的保密性被破坏 或一部分管理者的秘密密钥(主密钥)被泄漏的情况下，也只是签名处 理系统的一部分不发挥功能，能够将其它部分设为正常地发挥功能的 状态。

图13是多管理者的说明图。

在图13中，政府机关对住所、电话号码、年龄等的属性进行管 理。另外，警察对驾驶执照的种类等的属性进行管理。另外，公司A 对公司A中的职务、公司A中的所属等的属性进行管理。而且，政府 机关发行用于表示政府机关所管理的属性的签名密钥1，警察发行用 于表示警察所管理的属性的签名密钥2，公司A发行用于表示公司A 所管理的属性的签名密钥3。

进行签名的签名者使用将政府机关、警察、公司A等的各管理者 所发行的签名密钥1、2、3合在一起的签名密钥，来生成签名数据。 也就是说，从签名者来看，将从各管理者发行的签名密钥合在一起的 是对自己所发行的一个签名密钥。

例如在公司A的主密钥被泄漏的情况下，签名处理系统关于公司 A的属性不发挥功能，但是关于由其他管理者管理的属性发挥功能。 也就是说，在实现了签名数据的验证的情况下，虽然不能信赖由公司 A管理的属性，但是可信赖其它属性。

另外，从图13的例子也可知，在基于属性的签名中，存在多个管 理者，各管理者对属性中的某个范畴(部分空间)或定义域进行管理， 发行关于该范畴中的用户的属性的签名密钥(的一片)，这是自然的。

接着，说明“分散(Decentralized)”。分散是指，任何机关都能够 成为管理者，无需与其它机关交换而能够发行签名密钥(的一片)，各 用户无需与其它机关交换而能够从管理者获取签名密钥(的一片)。

例如在存在中央管理者的情况下，不能说是分散。中央管理者是 其他管理者的上位的管理者。在中央管理者的保密性被破坏的情况下， 导致所有管理者的保密性被破坏。

<第2.基于分散多管理者属性的签名方式的结构>

<第2-1.基于分散多管理者属性的签名方式的基本结构>

基于分散多管理者属性的签名方式具备GSetup、ASetup、 AttrGen、Sig、Ver这四个算法。

(GSetup)

GSetup算法是被输入保密参数λ而输出公开参数gparam的概率 性算法。

(ASetup)

ASetup算法是以公开参数gparam和管理者的识别信息t为输入 而输出管理者秘密密钥ask_t和管理者公开参数apk_t的概率性算法。

(AttrGen)

AttrGen算法是以公开参数gparam、管理者的识别信息t、管理 者秘密密钥ask_t、用户的识别信息gid以及属性x^→_t：=(x_t，i)(i=1，···， n_t)∈F_q为输入而输出签名密钥usk_{gid，(t，xt)}的概率性算法。

(Sig)

Sig算法是以公开参数gparam、签名密钥usk_{gid，(t，xt)}、消息m 以及访问架构S：=(M，ρ)为输入来输出包含签名s^→＊、消息m以及 访问架构S的签名数据σ的概率性算法。

(Ver)

Ver算法是以签名数据σ、公开参数gparam以及管理者公开参 数apk_t为输入而输出布尔值1(受理)或0(拒绝)的算法。

<第2-2.签名处理系统10>

说明执行上述的基于分散多管理者属性的签名方式的算法的签 名处理系统10。

图14是执行基于分散多管理者属性的签名方式的算法的签名处 理系统10的结构图。

签名处理系统10具备多个密钥生成装置100、签名装置200、验 证装置300。

某(一个)密钥生成装置100以保密参数λ为输入来执行GSetup 算法，生成公开参数gparam。然后，该密钥生成装置100公开所生 成的公开参数gparam。

各密钥生成装置100以公开参数gparam和分配给该密钥生成装 置100的识别信息t为输入来执行ASetup算法，生成管理者秘密密钥 ask_t和管理者公开参数apk_t。然后，各密钥生成装置100以公开参数 gparam、分配给该密钥生成装置100的识别信息t、管理者秘密密钥 ask_t、用户的识别信息gid以及属性x_t：=(x_t，i)(i=1，···，n_t)∈F_q为输 入来执行AttrGen算法，生成签名密钥usk_{gid，(t，xt)}并向签名装置200 秘密分发。

签名装置200以公开参数gparam、签名密钥usk_{gid，(t，xt)}、消息 m以及访问架构S：=(M，ρ)为输入来执行Sig算法，生成包含签名s^→＊、 消息m以及访问架构S的签名数据σ。签名装置200将所生成的签名 数据σ发送给验证装置300。

验证装置300以签名数据σ、公开参数gparam以及管理者公开 参数apk_t为输入来执行Ver算法，输出布尔值1(受理)或0(拒绝)。

<第2-3.基于分散多管理者属性的签名方式以及签名处理系统10 的细节>

基于图15至图22，说明基于分散多管理者属性的签名方式以及 执行基于分散多管理者属性的签名方式的签名处理系统10的功能和 动作。

图15是表示各密钥生成装置100的功能的功能框图。图16是表 示签名装置200的功能的功能框图。图17是表示验证装置300的功能 的功能框图。

图18至图20是表示密钥生成装置100的动作的流程图。此外， 图18是表示GSetup算法的处理的流程图，图19是表示ASetup算法 的处理的流程图，图20是表示AttrGen算法的处理的流程图。图21 是表示签名装置200的动作的流程图，是表示Sig算法的处理的流程 图。图22是表示验证装置300的动作的流程图，是表示Ver算法的 处理的流程图。

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

如图15所示，密钥生成装置100具备主密钥生成部110、主密钥 存储部120、信息输入部130(第一信息输入部)、签名密钥生成部140、 密钥分发部150(签名密钥发送部)。

另外，主密钥生成部110具备全局参数生成部111、管理者秘密 密钥生成部112。签名密钥生成部140具备随机数生成部141、密钥要 素生成部145。

首先，基于图18说明密钥生成装置100所执行的GSetup算法的处 理。此外，如上所述，GSetup算法只要由多个密钥生成装置100中的 一个密钥生成装置100执行即可。

(S501：保密参数输入步骤)

全局参数生成部111通过输入装置输入保密参数λ(1^λ)。

(S502：双线性配对群生成步骤)

全局参数生成部111通过处理装置，以S501中输入的保密参数 λ(1^λ)为输入来执行算法G_bpg，随机地生成双线性配对群的参数 paramG：=(q，G，G_T，g，e)的值。

(S503：参数生成步骤)

将哈希函数H₁和H₂设为式166所示的哈希函数。

[式166]

全局参数生成部111通过处理装置，生成式167所示的全局参数 gparam的要素G₀、G₁、G₂、G₃、G₄。

[式167]

另外，全局参数生成部111设为g_t：=e(G₀，G₁)、g₄：=e(G₀， G₄)。

(S504：参数存储步骤)

主密钥存储部120将(S502)中生成的param_G、(S503)中由全局参 数生成部111所设定的哈希函数H₁、H₂、所生成的要素G₀、G₁、G₂、 G₃、G₄以及所设定的值g_t、g₄作为全局参数gparam存储在存储装置 中。

也就是说，在(S501)至(S503)中，密钥生成装置100执行式168所 示的GSetup算法来生成全局参数gparam。然后，在(S504)中，密钥生 成装置100将所生成的全局参数gparam存储在存储装置中。

此外，全局参数gparam例如经由网络被公开，被设为其它密钥 生成装置100、签名装置200、验证装置300能够获取的状态。

[式168]

g_T:=e(G₀,G₁),g₄:=e(G₀,G₄)，

接着，基于图19说明密钥生成装置100所执行的ASetup算法的处 理。此外，如上所述，ASetup算法既可以由多个密钥生成装置100全 部执行，也可以仅由多个密钥生成装置100中的一部分密钥生成装置 100执行。

(S601：信息输入步骤)

信息输入部130通过输入装置输入分配给自己(该密钥生成装置 100)的识别信息t。此外，对各密钥生成装置100分配有分别不同的识 别信息t。

另外，信息输入部130例如通过通信装置经由网络获取全局参数 gparam。此外，在自己是生成了全局参数gparam的密钥生成装置100 的情况下，只要从主密钥存储部120读出全局参数gparam即可。

(S602：空间生成步骤)

管理者秘密密钥生成部112通过处理装置，以保密参数λ(1^λ)、 N_t=2n_t+2+u_t+w_t+z_t以及param_G：=(q，G，G_T，g，e)的值为输入来执 行算法G_dpvs，生成对偶配对矢量空间的参数param_Vt：=(q，V_t，G_T， A_t，e)的值。

此外，n_t、u_t、w_t、z_t是1以上的整数。

(S603：基底U生成步骤)

管理者秘密密钥生成部112通过处理装置，针对1=1，···，4的各 整数l如式169所示那样生成基底U_l。

[式169]

forl＝0,...,4;i＝1,...,N_t

(S604：线性变换生成步骤)

管理者秘密密钥生成部112通过处理装置，以n_t+u_t+w_t+z_t和F_q为输入来如式170所示那样随机地生成线性变换X_t：=(χ_t，i，j)_i，j。

[式170]

(S605：基底B生成步骤)

管理者秘密密钥生成部112通过处理装置，如式171所示那样生 成基底B_t和基底B＊_t。

[式171]

另外，管理者秘密密钥生成部112将π，π’，μ∈F_q设为成为 G₂=πG₁、G₃=π’G₁、G₃=μG₁的值。于是，成为式172。

[式172]

(S606：基底B＾生成步骤)

管理者秘密密钥生成部112通过处理装置，如式173所示那样生 成基底B_t的部分基底B＾_t和基底B＊的部分基底B＾＊_t。

[式173]

(S607：主密钥存储步骤)

主密钥存储部120将(S602)中生成的参数param_Vt、(S606)中生成 的部分基底B＾_t以及部分基底B＾＊_t作为管理者公开参数apk_t存储在 存储装置中。另外，主密钥存储部120将(S604)中生成的线性变换X_t作为管理者秘密密钥ask_t存储在存储装置中。

也就是说，在(S601)至(S606)中，密钥生成装置100执行式174所 示的ASetup算法来生成管理者公开参数apk_t和管理者秘密密钥ask_t。 然后，在(S607)中，密钥生成装置100将所生成的管理者公开参数apk_t和管理者秘密密钥ask_t存储在存储装置中。

此外，管理者公开参数apk_t例如经由网络被公开，被设为签名装 置200、验证装置300能够获取的状态。

[式174]

ASetup(gparam，t)∶

N_t∶＝2n_t+2+u_t+w_t+z_t，

for l＝0,...,4;i＝1,...,N_t，

return(ask_t,apk_t).

接着，基于图20说明密钥生成装置100所执行的AttrGen算法的处 理。此外，如上所述，AttrGen算法是由多个密钥生成装置100中的、 执行了ASetup算法的密钥生成装置100执行。

(S701：信息输入步骤)

信息输入部130通过输入装置输入分配给自己(该密钥生成装置 100)的识别信息t、发行签名密钥的用户的识别信息gid以及属性信息 x^→_t：=(x_t，i)(i=1，···，n_t)。

另外，信息输入部130例如通过通信装置经由网络获取全局参数 gparam。此外，在自己是生成了全局参数gparam的密钥生成装置100 的情况下，只要从主密钥存储部120读出全局参数gparam即可。

另外，信息输入部130从主密钥存储部120读出管理者秘密密钥 ask_t。

(S702：随机数生成步骤)

随机数生成部141通过处理装置，针对识别信息t和j=1，2的各 整数j，如式175所示那样生成随机数φ^→_t，j。

[式175]

(S703：密钥要素生成步骤)

设为式176。

[式176]

密钥要素生成部145通过处理装置，针对识别信息t和j=1，2 的各整数j，如式177所示那样生成作为签名密钥usk_{gid，(t，xt)}的要素的 密钥要素k＊_t，j。

[式177]

for j＝1,2

此外，如上所述，对于式113所示的基底B和基底B＊，是式114。 因而，式177意味着如下设定基底B＊_t的基底矢量的系数。在此，简 化标记，仅用基底矢量b＊_t，i中的i的部分确定基底矢量。例如，如果 是基底矢量1，则意味着基底矢量b＊_t，1。另外，如果是基底矢量1，···， 3，则意味着基底矢量b＊_t，1，···，b＊_t，3。

作为基底矢量1，···，n_t的系数，设定(δ_j+1)x_t，1，···，(δ_j+1)x_t，nt(在 此，nt是n_t)。作为基底矢量n_t+1，···，2n_t的系数，设定-δ_jx_t，1，···， -δ_jx_t，nt(在此，nt是n_t)。作为基底矢量2n_t+1，···，2n_t+2+u_t的系数， 设定0。作为基底矢量2n_t+2+u_t+1，···，2n_t+2+u_t+w_t的系数，设定随 机数φ_t，j、1，···，φ_t，j，wt(在此，wt是w_t)。作为基底矢量2n_t+2+u_t+w_t+1，···， 2n_t+2+u_t+w_t+z_t的系数，设定0。

(S704：密钥分发步骤)

密钥分发部150将以用户的识别信息gid、识别信息t及属性信 息x^→_t、密钥要素k＊_t，j为要素的签名密钥usk_{gid，(t，xt)}例如通过通信装 置经由网络向签名装置200秘密分发。当然，也可以通过其它方法向 签名装置200分发签名密钥usk_{gid，(t，xt)}。

也就是说，在(S701)至(S703)中，密钥生成装置100执行式178所 示的AttrGen算法来生成签名密钥usk_{gid，(t，xt)}。然后，在(S704)中，密 钥生成装置100将所生成的签名密钥usk_{gid，(t，xt)}向签名装置200分发。

[式178]

for j＝1，2，

$\mathrm{return}({\mathrm{usk}}_{\mathrm{gid},(t,x_t)}:=(\mathrm{gid},(t,{\overrightarrow{x}}_t),{\left\{k_{t,j}^{*}\right\}}_{j=\mathrm{1,2}})).$

说明签名装置200的功能和动作。

如图16所示，签名装置200具备签名密钥获取部210、信息输入 部220(第二信息输入部)、张成方案计算部230、补充系数计算部240、 签名数据生成部250、签名数据发送部260(签名数据输出部)。

另外，信息输入部220具备谓词信息输入部221、消息输入部222。 另外，签名数据生成部250具备随机数生成部251、签名要素生成部 255。

基于图21说明签名装置200所执行的Sig算法的处理。

(S801：签名密钥获取步骤)

签名密钥获取部210例如通过通信装置经由网络获取各密钥生成 装置100所生成的签名密钥usk_{gid，(t，xt)}。另外，签名密钥获取部210 获取密钥生成装置100所生成的全局参数gparam。

(S802：信息输入步骤)

谓词信息输入部221通过输入装置输入访问架构S：=(M，ρ)。 此外，矩阵M是L行×r列的矩阵。L、r是1以上的整数。

另外，消息输入部222通过输入装置输入附加签名的消息m。

此外，关于访问架构S的矩阵M的设定，根据想要实现的系统 的条件进行设定。

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

张成方案计算部230通过处理装置判定(S802)中输入的访问架构 S是否受理(S801)中获取的签名密钥usk_{gid，(t，xt)}中包含的属性信息x^→_t的集合Γ。

此外，访问架构是否受理属性的集合的判定方法如实施方式1中 的“第3.用于实现函数型密码的概念”中说明的那样。

张成方案计算部230在访问架构S受理属性的集合Γ的情况下 (S803中受理)，使处理进入(S804)。另一方面，在访问架构S拒绝属 性信息x^→_t的集合Γ的情况下(S803中拒绝)，结束处理。

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

补充系数计算部430通过处理装置，计算成为式179的I和针对 I中包含的各整数i的常数(补充系数)α_i。

[式179]

$\overrightarrow{1}:={\Sigma }_{i\in I}{\alpha }_i{M}_i,$

此外，M_i是指矩阵M的第i行。

(S805：随机数生成步骤)

随机数生成部251通过处理装置如式180所示那样生成随机数 ξ₁、ξ₂和随机数β_i、β_i’(i=1，···，L)。

[式180]

(S806：签名要素生成步骤)

签名要素生成部255通过处理装置，针对i=1，···，L的各整数i， 如式181所示那样生成作为签名数据σ的要素的签名要素s*_i。

[式181]

for1≤i≤L

在此，r*_i是式182(参照式110至式112以及这些数式的说明)。

[式182]

另外，γ_i、y^→_i：=(y_i，i’)(i’=1，···，n_t)和y’^→_i：=(y’_i，i’)(i’=1，···， n_t)是式183。

[式183]

(S807：数据发送步骤)

签名数据发送部260将包含签名要素s＊_i(i=1，···，L)、消息m、 访问架构S：=(M，ρ)以及g₀：=g₄^ξ2(在此，ξ2是ξ₂)的签名数据σ例如 通过通信装置经由网络发送给验证装置300。当然，签名数据σ也可 以通过其它方法发送给验证装置300。

也就是说，在(S801)至(S806)中，签名装置200执行式184所示的 Sig算法来生成签名数据σ。然后，在(S807)中，签名装置200将所生成 的签名数据σ向验证装置300分发。

[式184]

then compute I and{α_i}_i∈I such that

$\overrightarrow{1}:={\Sigma }_{i\in I}{\alpha }_i{M}_i\mathrm{where}{M}_i\mathrm{isthei}-\mathrm{throwofM},$

$g_0:=g_4^{{\xi }_2},$

$\mathrm{and}{\gamma }_i,{\overrightarrow{y}}_i;=(y_{i,1},...,y_{i,n_t}),{{\overrightarrow{y}}^{\prime }}_i:=({y^{\prime }}_{i,1},...,{y^{\prime }}_{i,n_t})\mathrm{aredefinedas}$

$\mathrm{return}{\overrightarrow{s}}^{*}:=(s_0^{*},...,s,g_0).$

说明验证装置300的功能和动作。

如图17所示，验证装置300具备公开参数获取部310、数据接收 部320(数据获取部)、验证密钥生成部330、配对运算部340。

另外，验证密钥生成部330具备随机数生成部331、f矢量生成 部332、s矢量生成部333、验证要素生成部337。

基于图22说明验证装置300所执行的Ver算法的处理。

(S901：公开参数获取步骤)

公开参数获取部310例如通过通信装置经由网络获取各密钥生成 装置100所生成的全局参数gparam和管理者公开参数apk_t。

(S902：签名数据接收步骤)

数据接收部320例如通过通信装置经由网络接收签名装置200所 发送的签名数据σ。

(S903：f矢量生成步骤)

f矢量生成部332通过处理装置如式185所示那样随机地生成具 有r个要素的矢量f^→。

[式185]

(S904：s矢量生成步骤)

s矢量生成部333通过处理装置，基于(S902)中接收到的签名数 据σ中包含的访问架构S的(L行×r列)的矩阵M和(S903)中生成的具 有r个要素的矢量f^→，如式186所示那样生成矢量s^→T。

[式186]

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

另外，s矢量生成部333通过处理装置，基于(S903)中生成的矢 量f^→，式187所示那样生成值s₀。此外，1^→是所有要素为值1的矢量。

[式187]

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

(S905：f’矢量生成步骤)

f矢量生成部332通过处理装置如式188所示那样随机地生成具 有r个要素的矢量f^→’。

[式188]

(S906：s’矢量生成步骤)

s矢量生成部333通过处理装置，基于(L行×r列)的矩阵M和具 有r个要素的矢量f^→’，如式189所示那样生成矢量(s^→’)^T。

[式189]

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

(S907：随机数生成步骤)

随机数生成部331通过处理装置如式190所示那样生成随机数 σ^→和值σ₀。

[式190]

${\sigma }_0:=\overrightarrow{1}·{\overrightarrow{\sigma }}^T$

(S908：验证要素生成步骤)

验证要素生成部337通过处理装置，针对i=1，···，L的各整数i， 如式191所示那样生成作为验证密钥的要素的验证要素c_i。

[式191]

for1≤i≤L，

$\mathrm{if\rho }\left(i\right)=(t,{\overrightarrow{v}}_i),$

此外，如上所述，对于式113所示的基底B和基底B＊，是式114。 因而，式191意味着如下设定基底B_t的基底矢量的系数。在此，简化 标记，仅用基底矢量b_t，i中的i的部分确定基底矢量。例如，如果是 基底矢量1则意味着基底矢量b_t，1。另外，如果是基底矢量1，···，3， 则意味着基底矢量b_t，1，···，b_t，3。

在ρ(i)是肯定形的组(t，v^→_i)的情况下，作为基底矢量1的系数设 定s_i+θ_iv_i，1。作为基底矢量2，···，n_t的系数设定θ_iv_i,2，···，θ_iv_i，nt(在 此，nt是n_t)。作为基底矢量n_t+1的系数设定s_i’+θ_i’v_i，1。作为基底矢 量n_t+2，···，2n_t的系数设定θ_i’v_i，2，···，θ_i’v_i，nt(在此，nt是n_t)。作 为基底矢量2n_t+1的系数设定σ_i-θ_i’’H₂(m，S)。此外，H₂(m，S)是指， 作为哈希函数H₂的输入提供消息m和访问架构S。例如也可以设为 H₂(m||S)。作为基底矢量2n_t+2的系数设定θ_i’’。作为基底矢量 2n_t+2+1，···，2n_t+2+u_t+w_t的系数设定0。作为基底矢量 2n_t+2+u_t+w_t+1，···，2n_t+2+u_t+w_t+z_t的系数设定η_i，1，···，η_i，zt(在此， zt是z_t)。

另一方面，在ρ(i)是否定形的组￢(t，v^→_i)的情况下，作为基底矢 量1，···，n_t的系数设定s_iv_i，1，···，s_iv_i，nt(在此，nt是n_t)。作为基底 矢量n_t+1，···，2n_t的系数设定s_i’v_i，1，···，s_i’v_i，nt(在此，nt是n_t)。作 为基底矢量2n_t+1的系数设定σ_i-θ_i’’H₂(m，S)。作为基底矢量2n_t+2 的系数设定θ_i’’。作为基底矢量2n_t+2+1，···，2n_t+2+u_t+w_t的系数设定 0。作为基底矢量2n_t+2+u_t+w_t+1，···，2n_t+2+u_t+w_t+z_t的系数设定η_i，1，···， η_i，zt(在此，zt是z_t)。

(S909：配对运算步骤)

配对运算部340通过处理装置计算式192所示的配对运算。

[式192]

${\Pi }_{i=1}^{L}e(c_i,s_i^{*})$

如果计算式192所示的配对运算的结果是值g_T^s0g₀^σ0(在此，s0是 s₀，σ0是σ₀)，则配对运算部340输出表示签名的验证成功的值1。另 一方面，如果是其它值，则配对运算部340输出表示签名的验证失败 的值0。

此外，通过如式193所示那样计算式192，如果签名数据σ是正 当的，则得到值1。

[式193]

${\Pi }_{i=1}^{L}e(c_i,s_i^{*})$

$={\Pi }_{i\in I}e(c_i,k_{t,1}^{*}){\gamma }_i{\xi }_1·{\Pi }_{i\in I}e(c_i,k_{t,2}^{*}){\gamma }_i(1-{\xi }_1).$

${\Pi }_{i=1}^L{\Pi }_{t=1}^{n_t}e{(c_i,b_{t,t}^{*})}^{\pi y_{i,t}}.$

${\Pi }_{i=1}^L{\Pi }_{t=1}^{n_t}e{(c_i,b_{t,n_t+t}^{*})}^{{\pi }^{\prime }{y^{\prime }}_{i,t}}.$

也就是说，在(S901)至(S909)中，验证装置300执行式194所示的 Ver算法来验证签名数据σ。

[式194]

for1≤i≤L，

$\mathrm{if\rho }\left(i\right)=(t,{\overrightarrow{v}}_i),$

$\mathrm{return}1\mathrm{if}{\Pi }_{i=1}^{L}e(c_i,s_i^{*})=g_T^{s_0}{g}_0^{{\sigma }_0},\mathrm{return}0\mathrm{otherwise}.$

如上所述，实施方式2所涉及的签名处理系统10实现多个密钥生 成装置100生成签名密钥的基于多管理者属性的签名方式。特别是，签 名处理系统10所实现的签名方式是不存在中央管理者的基于分散多管 理者属性的签名方式。

此外，实施方式2所涉及的签名处理系统10与实施方式1所涉 及的签名处理系统10同样地实现伴随非单调谓词的基于属性的签名 方式。

实施方式2所涉及的签名处理系统10所实现的基于属性的签名方 式的安全性高，满足隐秘性必要条件。

此外，在上述说明中，u_t、w_t、z_t(t=1，···，d)的维度是为了提高 安全性而设置的维度。因而，虽然导致安全性变低，但是也可以将u_t、 w_t、z_t(t=1，···，d)分别设为0来不设置u_t、w_t、z_t(t=1，···，d)的维度。

另外，在上述说明中，将基底B_t和基底B＊_t的维数设定为 2n_t+2+u_t+w_t+z_t。但是，也可以将2n_t+2+u_t+w_t+z_t设为2+2+2+6+4+1来 将基底B_t和基底B＊_t的维数设为17。

在该情况下，式168所示的GSetup算法如式195那样被改写。

[式195]

g_T∶=e(G₀，G₁)，g₄∶=e(G₀，G₄)，

另外，式174所示的ASetup算法如式196那样被改写。

[式196]

ASetup(gparam,t):

retur(ask_t，apk_t).

另外，式178所示的AttrGen算法如式197那样被改写。

[式197]

for j＝1,2,

$\mathrm{return}({\mathrm{usk}}_{\mathrm{gid},(t,x_t)}:=(\mathrm{gid},(t,x_t),{\left\{k_{t,j}^{*}\right\}}_{j=\mathrm{1,2}})).$

另外，式184所示的Sig算法如式198那样被改写。

[式198]

then compute I and{α_i}_i∈Isuch that

$\overrightarrow{1}:={\Sigma }_{i\in I}{\alpha }_i{M}_i\mathrm{where}{M}_i\mathrm{isthei}-\mathrm{throwofM},$

$g_0:=g_4^{{\xi }_2},$

$\mathrm{and}{\gamma }_i,{\overrightarrow{y}}_i;=(y_{i,1},...,y_{i,4})\mathrm{aredefiedas}$

$\mathrm{return}{\overrightarrow{s}}^{*}:=(s_0^{*},...,s_L^{*},g_0).$

另外，式194所示的Ver算法如式199那样被改写。

[式199]

for1≤i≤L，

if p(i)=(t,v_i),

$\mathrm{return}1\mathrm{if}{\Pi }_{i=1}^{L}e(c_i,s_i^{*})=g_T^{s_0}{g}_0^{{\sigma }_0},\mathrm{return}0\mathrm{otherwise}.$

另外，GSetup算法只要在设置签名处理系统10时由某一个密钥生 成装置100执行一次即可，不需要在每次生成签名密钥时都执行。同样 地，ASetup算法只要在设置签名处理系统10时由各密钥生成装置100 执行一次即可，不需要在每次生成签名密钥时都执行。

另外，在上述说明中，设为由密钥生成装置100执行GSetup算 法、ASetup算法以及KeyGen算法，但是也可以由各自不同的装置执 行GSetup算法、ASetup算法和KeyGen算法。

实施方式3.

在以上的实施方式中，说明了在对偶矢量空间中实现签名处理的 方法。在本实施方式中，说明在对偶加群（dual additive group）中实 现签名处理的方法。

也就是说，在以上的实施方式中，在素数阶数q的循环群中实现 了签名处理。但是，在使用合成数M如式200那样表示环R的情况下， 在以环R为系数的加群中也能够应用在上述实施方式中说明的签名处 理。

[式200]

在此，

Z：整数

M：合成数。

如果在以环R为系数的加群中实现实施方式1中说明的基于属性 的签名方式，则成为如式201至式205那样。

[式201]

$\mathrm{Setup}(1^{\lambda },\overrightarrow{n};=(d;n_t,u_t,w_t,z_t)(t=0,...,d+1))$

$\mathrm{sk}:=b_{\mathrm{0,1}}^{*},$

return sk,pk

[式202]

N_t∶＝n_t+u_t+w_t+z_t for t＝0,...,d+1，

For t＝0,...,d+1,

[式203]

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

$T:=\{0,(d+\mathrm{1,1}),(d+\mathrm{1,2})\}\cup \left\{t\right|1\le t\le d,(t,{\overrightarrow{x}}_t)\in \Gamma \},$

$\mathrm{return}{\mathrm{sk}}_{\Gamma }:=(\Gamma ,{\left\{k_t^{*}\right\}}_{t\in T}).$

[式204]

then compute I and{α_i}_i∈Isuch that

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

$s_i^{*};={\gamma }_i·\xi k_t^{*}+{\Sigma }_{t=1}^{n_t}{y}_{i,t}·b_{t,t}^{*}+r_i^{*},\mathrm{for}1\le i\le L,$

$\mathrm{and}{\gamma }_i{\overrightarrow{y}}_i;=(y_{i,1},...,y_{i,n_t})\mathrm{aredefinedas}$

${\overrightarrow{y}}_i\stackrel{U}{\leftarrow }\left\{{\overrightarrow{y}}_i\right|{\overrightarrow{y}}_i·{\overrightarrow{v}}_i={\beta }_i\},$

$\mathrm{return}{\overrightarrow{s}}^{*}:=(s_0^{*},...,s_{L+1}^{*}).$

[式205]

for 1≤i≤L,

$\mathrm{return}0\mathrm{ife}(b_{\mathrm{0,1}},s_0^{*})=1,$

$\mathrm{return}1\mathrm{if}{\Pi }_{i=0}^{L+1}e(c_i,s_i^{*})=1,\mathrm{return}0\mathrm{otherwise}.$

如果在以环R为系数的加群中实现实施方式2中说明的基于分散 多管理者属性的签名方式，则成为如式206至式210那样。

[式206]

g_T∶＝e(C₀，C₁)，g₄∶＝e(G₀，G₄)，

[式207]

ASetup(gparam，t):

N_t∶＝2n_t+2+u_t+w_t+z_t，

for l＝0,...,4;i＝1,...,N_t，

return(ask_t,apk_t).

[式208]

fof j=1，2，

$\mathrm{return}({\mathrm{usk}}_{\mathrm{gid},(t,x_t)};=(\mathrm{gid},(t,{\overrightarrow{x}}_t),{\left\{k_{t,j}^{*}\right\}}_{j=\mathrm{1,2}})).$

[式209]

then compute I and{α_i}_i∈I such that

$\overrightarrow{1}:={\Sigma }_{i\in I}{\alpha }_i{M}_i\mathrm{where}{M}_i\mathrm{isthei}-\mathrm{throwofM},$

$\mathrm{return}{\overrightarrow{s}}^{*};=(s_0^{*},...,s,g_0).$

[式210]

for 1≤i≤L，

$\mathrm{if\rho }\left(i\right)=(t,{\overrightarrow{v}}_i),$

$\mathrm{return}1\mathrm{if}{\Pi }_{i=1}^{L}e(c_i,s_i^{*})=g_T^{s_0}{g}_T^{{\sigma }_0},\mathrm{return}0\mathrm{otherwise}.$

此外，从安全性的证明的观点出发，在以上的实施方式中，也可 以限定为关于i=1，···，L的各整数i的ρ(i)是关于分别不同的识别信息t 的肯定形的组(t，v^→_i)或否定形的组￢(t，v^→_i)。

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

另外，在上述说明中，设张成方案M＾仅限于将通过输入列δ从 矩阵M＾得到的矩阵M_δ的行进行线性结合而得到1^→的情况下，受理输 入列δ。但是，也可以设为张成方案M＾仅限于不是得到1^→而是得到 其它矢量h^→的情况下，受理输入列δ。

在该情况下，在KeyGen算法中，不是s₀：=1^→·f^→T，而是设为 s₀：=h^→·f^→T即可。

接着，说明实施方式中的签名处理系统10(密钥生成装置100、签 名装置200、验证装置300)的硬件结构。

图23是表示密钥生成装置100、签名装置200、验证装置300的 硬件结构的一例的图。

如图23所示，密钥生成装置100、签名装置200、验证装置300 具备执行程序的CPU911(Central·Processing·Unit，还称为中央处 理装置、处理装置、运算装置、微处理器、微计算机、处理器)。CPU 911经由总线912与ROM913、RAM914、LCD901(Liquid Crystal  Display：液晶显示器)、键盘902(K/B)、通信板915、磁盘装置920 连接，控制这些硬件设备。代替磁盘装置920(固定盘装置)，也可以使 用光盘装置、存储卡读写装置等存储装置。磁盘装置920经由规定的 固定盘接口进行连接。

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

在磁盘装置920或ROM913等中存储有操作系统921(OS)、视窗系 统922、程序群923、文件群924。程序群923的程序是由CPU911、操 作系统921、视窗系统922执行。

在程序群923中存储有执行在上述的说明中作为“主密钥生成部 110”、“主密钥存储部120”、“信息输入部130”、“签名密钥生成部140”、 “密钥分发部150”、“签名密钥获取部210”、“信息输入部220”、“张成 方案计算部230”、“补充系数计算部240”、“签名数据生成部250”、“签 名数据发送部260”、“公开参数获取部310”、“数据接收部320”、“验证 密钥生成部330”、“配对运算部340”等说明的功能的软件、程序、其它 程序。通过CPU911读出并执行程序。

在文件群924中，作为“文件”、“数据库”的各项目存储有在上述 的说明中的“公开参数”、“主密钥”、“签名数据σ”、“签名密钥”、“访 问架构S”、“属性信息”、“属性的集合Γ”、“消息m”等的信息、数据、 信号值、变量值、参数。“文件”、“数据库”存储在盘、存储器等记录 介质中。由CPU911经由读写电路将存储在盘、存储器等的存储介质 中的信息、数据、信号值、变量值、参数读出到主存储器、高速缓冲 存储器中，用于提取、搜索、参照、比较、运算、计算、处理、输出、 打印、显示等CPU911的动作。在提取、搜索、参照、比较、运算、 计算、处理、输出、打印、显示的CPU911的动作的期间，将信息、 数据、信号值、变量值、参数暂时存储到主存储器、高速缓冲存储器、 缓冲存储器中。

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

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