基于属性签名（attribute-based signature，ABS）^[1]是一种特殊数字签名体制，可以为用户提供细粒度的隐私保护，在多个领域有重要应用，因此成为密码学的研究热点.

ABS的隐私保护控制是通过属性和属性集上定义的访问结构实现的.根据访问结构使用位置的不同，基于属性签名分为密钥策略ABS（key-policy attribute-based signature，KP-ABS）和签名策略ABS（signature-policy attribute-based signature，SP-ABS）.在KP-ABS中，用户从属性机构（attribute authority，AA）处获得其所拥有的访问结构所对应的签名密钥，之后可用其对属性满足其访问结构的消息进行签名.签名可以确保消息是由拥有能被指定属性满足的访问结构的用户签发的（不可伪造性），但不能辨认出签名人所拥有的具体访问结构，更不能辨认出签名人的身份（隐私性）.SP-ABS则相反，用户从属性机构处获得其所拥有的属性所对应的签名密钥，然后对具有其属性所满足的访问结构的消息进行签名.

举个简单的说明性例子：ABS可为教学管理系统提供匿名评价功能.假设每个课程都表示为“课程名称、开课教师姓名、开课年份、开课学期”，那么每位学生所选的课程组可以表示成(C₁∧T₁∧Y₁∧S₁)∨(C₂∧T₂∧Y₂∧S₂)∨···∨(C_k∧T_k∧Y_k∧S_k)，其中C_i, T_i, Y_i, S_i分别表示课程名称、开课教师姓名、开课年份和开课学期.在学生选定其课程组后，系统根据其所选课程组所对应的访问结构为其发放签名密钥，此后，学生可以使用其签名密钥匿名发表课程评价.ABS的不可伪造性保证只有选修的学生才能对课程进行评价，其隐私性保证任何人都不能辨认出评价出自哪位学生.不可伪造性保证评价来源的合法性，隐私性保障评价者的隐私权.

由于其良好的性质，ABS在许多领域有重要的应用，如匿名凭证（anonymous credentials）、消息传递（message delivery）、匿名认证（anonymous authentication）、秘密泄露（leaking secrets）、信任协商（trust negotiations）、隐私接入控制（private access control）等等^[1-2].

自ABS被提出以来，众多学者先后提出许多支持各种不同访问结构的方案.Shahandashti等人^[2]、Li等人^[3]、Herranz等人^[4]和Gagne等人^[5]各自提出支持门限（threshold）访问结构的ABS方案；Maji等人^[1]和Gu等人^[6-7]各自提出支持单调（monotone）访问结构的ABS方案；Okamoto等人^[8-9]提出支持非单调（non-monotone）访问结构的ABS方案；Tang等人^[10]和Sakai等人^[11]各自提出电路（circuits）访问结构的ABS方案；Kaafarani等人^[12]提出无界电路（unbounded circuits）访问结构的ABS方案；Zhang等人^[13]提出支持内积（inner-product）访问结构的ABS方案；Datta等人^[14]提出无界算术分支程序（unbounded arithmetic branching programs）访问结构的ABS方案.

为了克服ABS单个属性机构带来的瓶颈和信任过度集中的问题，Maji等人^[1]和Okamoto等人^[15]分别提出多属性机构（multi-authority）ABS和去中心（decentralized）ABS.为了克服ABS计算开销过大，不适用于资源受限场景的缺点，学者们将外包技术引入到ABS中来，Chen等人^[16]提出外包（outsourced）ABS，Mo等人^[17]和Sun等人^[18]分别提出新的外包ABS方案. Huang等人^[19] 指出已有外包ABS方案的隐私性缺陷，进而提出具有完善隐私性的外包ABS方案. Ren等人^[20]进一步提出可验证（verifiable）外包ABS；Cui等人^[21]和Xiong等人^[22]研究了服务器辅助（server-aided）ABS；Wang等人^[23]提出服务器辅助验证（server-aided verification）ABS.

此外，学者们还研究了具有附加性质的ABS，如基于属性环签名（attribute-based ring signature）^[24]、基于属性代理签名（attribute-based proxy signature）^[25]、基于属性签密（attribute-based signcryption）^[26]、基于属性净化签名（attribute-based sanitizable signature）^[27]等.

ABS研究的主要目标是更高的安全性、更高的效率和更强的访问结构表达力.电路是最富表达力的访问结构之一.目前已知有3个ABS方案支持电路访问结构：Tang等人^[10]的方案、Sakai等人^[11]的方案和Kaafarani等人^[12]的方案.文献[11−12]方案的效率都很低，签名的长度都与电路的输入成线性关系.Tang等人^[10]的方案的签名仅为1个群元素，效率最高，但在安全性和访问结构表达力方面却比较弱：

1）Tang等人^[10]方案的不可伪造性是很弱的，只是在选定消息和选定属性攻击下存在不可伪造，只能防止敌手伪造特定消息的签名.

2）Tang等人^[10]的方案仅支持特殊电路，要求兄弟节点的深度必须相同，且都是其父节点的深度加1；要求所有输入节点的深度相同.

本文改进了Tang等人^[10]的方案，提高了安全性、丰富了访问结构表达力、缩短了数据长度并降低了计算开销.本文的主要贡献包括3个方面:

1）增强方案的安全性.从“选定消息和选定属性攻击下存在不可伪造（existentially unforgeable under selective message attack and selective attribute, EUF-sA-sMA）”提升到“自适应选择消息但选定属性攻击下存在不可伪造（existentially unforgeable under adaptive chosen message but selective attribute attack, EUF-sA-CMA）”.EUF-sA-CMA比EUF-sA-sMA强很多，能防止敌手伪造任何自适应选择消息的签名.

2）丰富了访问结构表达力，将访问结构从特殊电路拓展到一般电路.去掉原有的所有限制，允许兄弟节点的深度不同；允许孩子节点的深度比其父节点的深度大于1，即可以跳层；允许输入节点的深度不同.另外，任意电路都可以通过德·摩根（De Morgan）定律转换成非叶子节点为“或门”或“与门”，“非门”只出现在叶子节点的电路.如果将带“非门”的叶子节点定义为1个新属性（比如“不是教授”）作为1个新的输入，就可以支持非单调电路.一般电路的极强表达能力使得方案可支持任意访问结构，达到任意的访问控制粒度.

3）缩短了数据长度并降低了计算开销.在保持签名大小仅为1个群元素的前提下，将主公钥、主私钥和签名钥的大小都显著缩短；将签名密钥生成、签名生成和签名验证的计算开销都显著降低.

1.   预备知识

1.1   符号说明

本文使用的符号和参数的含义如表1所示.

表  1  符号释义

Table  1.  Symbols Interpretation

符号	含义
$\lambda$	系统安全参数
$k$	多线性映射的级数
$p$	$({2^{\lambda - 1}},{2^\lambda })$中的素数
${\mathbb{Z}_p}$	模素数$p$的整数集
$a{ \in _{R}}A$	从集合$A$中随机选取$a$
${ { \mathbb{G} }_i}$	乘法循环群
${g_i}$	乘法循环群$G_i$的生成元
$e$	多线性映射（含双线性映射）
$e(A)$	输入为A时多线性映射e的值
$f$	电路
$n$	电路的输入数
$q$	电路的门节点数
$\ell$	电路的最大深度
$I$	电路的输入节点集
$G$	电路的门节点集
$N$	电路的节点集
$L\left( w \right)$	门节点$w$的左孩子
$R\left( w \right)$	门节点$w$的右孩子
$GT\left( w \right)$	门节点类型函数，输出$w$的门类型
$D\left( w \right)={i_w}$	节点$w$的深度
$\varOmega$	电路的输入
$f\left( \varOmega \right)$	输入为$\varOmega$时电路$f$的输出
${f_w}\left( \varOmega \right)$	输入为$\varOmega$时$f$中门节点$w$的输出
${W_w}\left( \varOmega \right)$	输入为$\varOmega$时$f$中节点$w$的权重
$[1,n]$	表示集合$\left\{ {1,2, \cdots ,n} \right\}$
${\{ 0,1\} ^n}$	长度为n的比特串集合
$\{ 0,1\} ^*$	任意长度比特串的集合
$M$	消息
$\sigma$	签名

下载: 导出CSV 

| 显示表格

1.2   多线性映射与困难性假设

多线性映射. $\mathcal{G}({1^\lambda },k)$为群生成算法，输入安全参数$\lambda$和多线性映射级数$k$，输出素数$p$阶群序列${{\mathbb{G}}_1}, {{\mathbb{G}}_2}, \cdots ,{{\mathbb{G}}_k}$和相应的生成元${g_1},{g_2}, \cdots ,{g_k}$，以及双线性映射序列 ${e_{i,j}}：{{\mathbb{G}}_i} \times {{\mathbb{G}}_j} \to {{\mathbb{G}}_{i + j}}$，$1 \leqslant i \leqslant k - 1$, $1\le j \le k-1, i+j\le k，$ 满足

多线性映射定义为

其中右侧的e为其输入所对应的双线性映射${e_{i,j}}$.

k-MCDH（k-multilinear computational Diffie-Hellman）问题. 给定（$p,{{\mathbb{G}}_1},{{\mathbb{G}}_2}, … ,{{\mathbb{G}}_k},e,{g^{{c_1}}},{g^{{c_2}}}, … ,$ ${g^{{c_k}}}$），计算$g_{k - 1}^{\mathop \prod\limits_{i = 1}^k {c_i}}$，其中${c_1},{c_2}, … ,{c_k}{ \in _{\text{R}}}{\mathbb{Z}_p}$.

k-MCDH假设. 任意概率多项式时间算法$\mathcal{A}$成功解k-MCDH问题的概率都是可忽略的.

1.3   电　路

假设电路有$n$个输入节点，$q$个门节点，记输入节点集合为I = {1, 2, ···, n}，门节点集合为$G = \{ {w_{n + 1}}, {w_{n + 2}}, … ,{w_{n + q}}\}$，所有节点集合为$N = I \cup G$，其中${w_{{\text{top}}}} = {w_{n + q}}$为头部节点.门节点$w$的左、右孩子节点分别记为$L\left( w \right)$和$R\left( w \right)$.$GT\left( w \right)$表示门节点$w$的类型，即“AND”或“OR”.电路记为$f = \left( {n,q,L,R,GT} \right)$.

$D\left( w \right)$表示节点$w$的深度.头部节点的深度为0，其他节点的深度为其到头部节点的最长路的长度.$f\left( \varOmega \right)$表示输入为$\varOmega \in {\left\{ {0,1} \right\}^n}$时，电路$f$的输出.当$f\left( \varOmega \right) = 1$时，称$\varOmega$满足$f$；否则，称$\varOmega$不满足$f$.类似地，${f_w}\left( \varOmega \right)$表示输入为$\varOmega$时，电路$f$中门节点$w$的输出.

为了有效降低计算开销，本文为电路引入节点权重的概念，用${W_w}\left( \varOmega \right)$表示在输入为$\varOmega$时节点w的权重，其计算方法如1）~3）：

1）输入节点.

① 输入为1的节点，${W_w}\left( \varOmega \right) = n - 1$；

② 输入为0的节点，${W_w}\left( \varOmega \right) = \infty$.

2）或门.

① 如果${f_w}(\varOmega ) = 0$，则${W_w}\left( \varOmega \right) = \infty$；

② 否则${W_w}\left( \varOmega \right) = \min \{ {W_{L(w)}}\left( \varOmega \right),{W_{R(w)}}\left( \varOmega \right)\} + 2$.

3）与门.

① 如果${f_w}(\varOmega ) = 0$，则${W_w}\left( \varOmega \right) = \infty$；

② 否则：

如果$D\left( {L(w)} \right) = D\left( {R(w)} \right)$，则

如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$，则

这样定义的节点权重其实就是使用本文方案生成签名时，使用该节点所需要计算的对运算的数量.对运算越少，效率就越高.

图1给出一个一般电路的说明性例子：

图  1  一般电路示例

Figure  1.  Example of general circuit

下载: 全尺寸图片 幻灯片

2.   电路访问结构密钥策略ABS

本节给出访问结构为电路的密钥策略ABS的定义和安全模型.

2.1   算法组成

电路访问结构密钥策略ABS方案由1）~4）算法组成：

1）Setup(${1^\lambda }$, n,$\ell$).输入安全参数$\lambda$、电路输入数$n$和最大深度$\ell$，输出系统公开参数pp和系统主私钥msk.

2）KeyGen(pp, msk, f).输入系统公开参数pp、系统主私钥msk和电路$f$，输出电路$f$所对应的签名密钥$S{K_f}$.

3）Sign(pp,$S{K_f}$, M,$\varOmega$).输入公开参数pp、签名密钥$S{K_f}$、消息M及其属性$\varOmega$，输出关于(M, $\varOmega$)的签名$\sigma$.

4）Verify(pp, M,$\varOmega$,$\sigma$).输入公开参数pp、消息M、属性$\varOmega$和签名$\sigma$.如果$\sigma$是关于(M, $\varOmega$)的有效签名，输出1；否则，输出0.

2.2   安全性模型

定义1. 正确性.一个电路访问结构的密钥策略ABS方案是正确的，如果对于任意的消息$M$和满足$f(\varOmega ) = 1$的任意属性$\varOmega$与电路$f$都有概率，则

不可伪造性.大多数ABS的文献使用如下不可伪造性定义，其形式化模型如Game1：

Game1 （EUF-sA-CMA）.

1）Initialization.敌手$\mathcal{F}$选择挑战属性${\varOmega ^*}$并发送给挑战者$\mathcal{C}$.

2）Setup.挑战者$\mathcal{C}$生成系统公开参数pp并发送给敌手$\mathcal{F}$.

3）KeyGen Oracle.敌手$\mathcal{F}$提交电路$f$给挑战者$\mathcal{C}$.$\mathcal{C}$返回电路$f$的密钥$S{K_f}$给$\mathcal{F}$.

4）Sign Oracle.敌手$\mathcal{F}$提交消息$M$和属性$\varOmega$给挑战者$\mathcal{C}$.$\mathcal{C}$返回($M$,$\varOmega$)的签名$\sigma$给$\mathcal{F}$.

5）Forgery.敌手$\mathcal{F}$输出(${\sigma ^{\text{*}}},{M^{\text{*}}},{\varOmega ^*}$).

如果下面①~③都满足，称敌手赢得Game1.

① ${\sigma ^{\text{*}}}$是关于消息${M^{\text{*}}}$和属性${\varOmega ^{\text{*}}}$的有效签名；

② (${M^{\text{*}}},{\varOmega ^{\text{*}}}$)没有被询问过Sign Oracle；

③ 任何询问过KeyGen Oracle的电路$f$都使$f({\varOmega ^*}) = 0$.

敌手$\mathcal{F}$的优势$Ad{v}_{\text{ABS}, ℱ}^{\text{EUF-sA-CMA}}$定义为其赢得Game 1的概率.

定义2. 一个电路访问结构密钥策略ABS方案称为自适应选择消息但选定属性攻击下存在不可伪造的；如果对于任何多项式时间敌手$\mathcal{F}$，其赢得Game 1的优势$Adv_{{\text{ABS}},\mathcal{F}}^{{\text{EUF - sA - CMA}}}$是可忽略的.

Tang等人^[10]方案的不可伪造性是很弱的“选定消息和选定属性攻击下存在不可伪造”，其Game和Game1基本相同，只是Initialization应改为：

Initialization. 敌手$\mathcal{F}$选择并发送挑战消息${M^*}$和挑战属性${\varOmega ^*}$给挑战者$\mathcal{C}$.

完善隐私性.本文方案和Tang等人^[10]方案都实现了完善隐私性，任何敌手即使拥有无限的计算能力也无法识别用于生成签名的电路.

定义3. 如果对于任何$M$，$\varOmega$和满足${f_0}\left( \varOmega \right) = {f_1}\left( \varOmega \right) = 1$的${f_0},{f_1}$，使用${f}_{0}和{f}_{1}$所产生的签名分布

是信息论意义不可区分的，则称该电路访问结构密钥策略ABS方案具有完善隐私性.

3.   一般电路密钥策略ABS方案

本节提出一个支持一般电路的密钥策略ABS方案.

3.1   主要设计思想

本文方案是基于Tang等人^[10]方案改进而来的，改进的主要思想如1）~4）所描述：

1）以唯一的头部节点为参照原点，其他节点都参照它进行定位，以便支持一般电路.而Tang等人^[10]方案采用叶子（输入）节点为参照原点，所以需要假设所有输入节点均有相同的深度.

2）引入节点权重的概念并采用“从上到下”递归的方式计算签名，只计算必须计算的且权重较小的节点的${E_w}$.而Tang等人^[10]方案“自下而上”计算所有输出为1的节点的${E_w}$，许多不必要的${E_w}$也计算了，浪费了计算资源.

3）充分利用左右孩子节点的对称性，将孩子节点同深度的门节点的密钥都减少了1个分量，“或门”的密钥减少了25%，“与门”的密钥减少了33.33%.孩子节点有不同深度的门节点的密钥没有减少，只是为了在安全性证明中方便仿真密钥.实际使用时同深度和不同深度的门节点可不加区别，都减少1个分量.

4）通过使用安全Hash函数，将不可伪造性提升到“自适应选择消息但选定属性攻击下存在不可伪造”，同时将主公钥和主私钥长度各减少2m个元素（m为消息的长度）.

3.2   签名方案

本文所提出的一般电路密钥策略ABS方案的算法为：

Setup. 输入安全参数$\lambda$、电路最大深度$\ell$和电路输入数$n$.

1）运行$\mathcal{G}({1^\lambda },k = n + \ell + 3)$得到阶为素数p的群序列${{\mathbb{G}}_1},{{\mathbb{G}}_2}, … ,{{\mathbb{G}}_k}$和对应的生成元序列${g_1}(g=g_1),{g_2}, \cdots {g_k}$，以及其上的多线性映射$e$.

2）随机选取${a_{i,\beta }}{ \in _{R}}{\mathbb{Z}_p}$，$i \in \left[ {1,n} \right],\beta \in \left\{ {0,1} \right\}$，计算${A_{i,\beta }} = {g^{{a_{i,\beta }}}}$.记$a = \left\{ {{a_{1,0}},{a_{1,1}},{a_{2,0}},{a_{2,1}}, … ,{a_{n,0}},{a_{n,1}}} \right\}$，$A = \{ {A_{1,0}},{A_{1,1}}, {A_{2,0}},{A_{2,1}},$$… ,{A_{n,0}},{A_{n,1}}\}$.

3）随机选取$\alpha { \in _{R}}{\mathbb{Z}_P}$，计算$Y = g_{\ell + 2}^\alpha$.

4）选取防碰撞Hash函数$H:{\left\{ {0,1} \right\}^*} \to {\mathbb{G}_1}$.

输出系统公开参数$pp = \{ Y,A,n,\ell ,p,{{\mathbb{G}}_1},{{\mathbb{G}}_2}, … ,$ ${{\mathbb{G}}_k},{g_1},{g_2}, … ,{g_k},e,H\}$和主私钥msk =$\{ \alpha ,a$}.

KeyGen. 输入系统公开参数pp、系统主私钥msk和电路f = (n, q, L, R, GT).

1）令${v_{{w_{{\text{top}}}}}} = \alpha$，随机选取${v_w}{ \in _{R}}{\mathbb{Z}_p}$, $w\in N \backslash \{{w}_{\text{top}}\}$和${z_w}{ \in _{R}}{\mathbb{Z}_p}$,$w\in G$.

2）采用“自下而上”的方式计算密钥组成部分${K_w}$.

① 输入节点. $w \in I = \left[ {1,n} \right]$，$D\left( w \right) = {i_w}$，计算

② 或门. $w \in G$，$GT\left( w \right) = {\text{OR}}$，$D\left( w \right) = {i_w}$.

（i）如果$D\left( {L(w)} \right) = D\left( {R(w)} \right)$, 即${i_{L(w)}} = {i_{R(w)}}$,计算

令${K_w} = \left( {{K_{w,1}},{K_{w,2}},{K_{w,3}}} \right)$.

（ii）如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, 选取${z_w'}{ \in _{R}}{\mathbb{Z}_p}$, 计算

令${K_w} = \left( {{K_{w,1}},{{K}_{w,1}'},{K_{w,2}},{K_{w,3}}} \right)$.

③ 与门. $w \in G$，$GT\left( w \right) = {\text{AND}}$，$D\left( w \right) = {i_w}$.

（i）如果$D\left( {L(w)} \right) = D\left( {R(w)} \right)$, 即${i_{L(w)}} = {i_{R(w)}}$,计算

令${K_w} = \left( {{K_{w,1}},{K_{w,2}}} \right)$.

（ii）如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, 选取${z_w'}{ \in _{R}}{\mathbb{Z}_p}$, 计算

令${K_w} = \left( {{K_{w,1}},{{K}_{w,1}'},{K_{w,2}}} \right)$.

3）输出签名密钥$S{K_f} = {\left\{ {{K_w}} \right\}_{w \in N}}$.

Sign. 输入公开参数pp、签名密钥$S{K_f}$、消息M和属性$\varOmega = ({\varOmega _1},{\varOmega _2}, … ,{\varOmega _n}) \in {\{ 0,1\} ^n}$，计算$f(\varOmega )$和各节点的权重.如果$f\left( \varOmega \right) = 0$，无法签名，停止；如果$f\left( \varOmega \right) = 1$，按“从上到下”递归方法计算必要节点的${E_w}$.

1）计算$E = e({\{ {A_{i,{\varOmega _i}}}\} _{i \in [1,n]}})$.

2）或门. $w \in G$，$GT\left( w \right) = {\text{OR}}$.

如果${W_{L(w)}}\left( \varOmega \right) \leqslant {W_{R(w)}}\left( \varOmega \right)$，调用其左孩子节点的${E_{L\left( w \right)}}$，计算

否则，调用其右孩子节点的${E_{R\left( w \right)}}$.

如果$D(L(w)) = D(R(w))$，计算

如果$D(L(w)) \ne D(R(w))$，计算

3）与门. $w \in G$，$GT\left( w \right) = {{\rm{AND}}}$，调用其孩子节点的${E_{L\left( w \right)}}$和${E_{R\left( w \right)}}$.

如果$D(L(w)) = D(R(w))$，计算

如果$D(L(w)) \ne D(R(w))$，计算

4）输入节点. $w \in I$. 计算

5）计算并输出签名

Verify. 输入待验证的签名$\sigma$及相应的消息$M$和属性$\varOmega$.如果等式

成立，输出1；否则，输出0.

4.   安全性证明与性能效率分析

本节证明所提出方案的安全性，并分析其性能和效率.

4.1   安全性证明

定理1.本文所提出的一般电路密钥策略基于属性签名方案是正确的.

证明.容易知道，在签名递归过程所有被计算的节点都有${f_w}\left( \varOmega \right) = 1$.下面，用数学归纳法证明签名生成过程中所有的${E_w}$都有${E_w} = g_{n + \ell - {i_w} + 1}^{{v_w}\times \varrho \left( \varOmega \right)}$，其中$\varrho \left( \varOmega \right) = {\prod\limits_{i \in \left[ {1,n} \right]}}{a_{i,{\varOmega _i}}}$.

1）当$w$为输入节点时，即$w \in I$，$D\left( w \right) = {i_w}$，有

2）假设${E_{L(w)}} = g_{n + \ell - {i_{L\left( w \right)}} + 1}^{{v_{L\left( w \right)}}\times \varrho \left( \varOmega \right)}$和${E_{R(w)}} = g_{n + \ell - {i_{R\left( w \right)}} + 1}^{{v_{R\left( w \right)}}\times \varrho \left( \varOmega \right)}$成立，那么有${E_w} = g_{n + \ell - {i_w} + 1}^{{v_w}\times \varrho \left( \varOmega \right)}$成立.

① 或门. $w \in G$，$GT\left( w \right) = {\text{OR}}$.

（i）如果是调用左孩子节点，有

（ii）如果是调用右孩子节点，且D(L(w)) = D(R(w))，有

（iii）如果是调用右孩子节点，但$D(L(w)) \ne$ $D(R(w))$，有

② 与门. $w \in G$，$GT\left( w \right) = {\text{AND}}$.

（i）如果$D(L(w)) = D(R(w))$，即${i_{L(w)}} = {i_{R(w)}}$, 有

（ii）如果$D(L(w)) \ne D(R(w))$，有

由数学归纳法可知：${E_w} = g_{n + \ell - {i_w} + 1}^{{v_w}\times \varrho \left( \varOmega \right)}$对所有被计算的节点都成立.

当$w = {w_{{\text{top}}}}$时，有${v_w} = \alpha$，${i_w} = D\left( w \right) = 0$，所以有

从而有

验证方程成立，所提出的方案是正确的. 证毕.

定理2. 如果k-MCDH假设成立，则所提出的一般电路密钥策略ABS方案是自适应选择消息但选定属性攻击下存在不可伪造的.

证明.假设$\mathcal{F}$是具有优势$\varepsilon$的EUF-sA-CMA敌手，$\mathcal{C}$是k-MCDH问题的挑战者，我们构建如下的算法$\mathcal{B}$，利用$\mathcal{F}$来解k-MCDH问题.

$\mathcal{B}$维护一个初始化为空的列表${\mathbb{L}_H}$.令${q_{\text{s}}}$为查询Sign Oracle的最大次数.

k-MCDH Gen.

1）$\mathcal{C}$运行$\mathcal{G}\left( {{1^\lambda },k = n + \ell + 3} \right)$得到阶为素数p的群序列${{\mathbb{G}}_1},{{\mathbb{G}}_2}, … ,{{\mathbb{G}}_k}$和对应的生成元序列${g_1},{g_2}, … {g_k}$，以及其上的多线性映射$e$.

2）随机选取${g^{{c_1}}},{g^{{c_2}}}, … ,{g^{{c_k}}}$$\in {\mathbb{G}_1}$.

3）发送$(n,\ell ,p,{{\mathbb{G}}_1},{{\mathbb{G}}_2}, … ,{{\mathbb{G}}_k},{g_1}(g=g_1),{g_2}, … ,{g_k},e,$ ${g^{{c_1}}}, {g^{{c_2}}}, … , {g^{{c_k}}})$给$\mathcal{B}$.

Initialization. 敌手$\mathcal{F}$选取并发送挑战属性${\varOmega ^*} = \left( {\varOmega _1^*,\varOmega _2^*, … ,\varOmega _n^*} \right)$给$\mathcal{B}$.

Setup.

1）令$Y = e\left( {{g^{{c_{n + 1}}}},{g^{{c_{n + 2}}}}, … ,{g^{{c_{n + \ell + 2}}}}} \right)$. 这里隐含地令$\alpha = {c_{n + 1}}{c_{n + 2}} … {c_{n + \ell + 2}}$.

2）选取${a_i}{ \in _{R}}{\mathbb{Z}_p}$，并令

当$\varOmega _i^* = \beta$时，隐含地令${a_{i,\beta }} = {c_i}$.

3）$\mathcal{B}$发送公开参数$pp = \{ Y,A,n,\ell ,p,$ ${{\mathbb{G}}_1}, {{\mathbb{G}}_2}, … , {{\mathbb{G}}_k},$${g_1},{g_2}, … ,{g_k},e\}$给敌手$\mathcal{F}$.

KeyGen Oracle. 当敌手$\mathcal{F}$询问关于电路f = (n, q, L, R, GT)的密钥时，如果$f({\varOmega ^*}) = 1$，拒绝；否则，采用“自下而上”的方式计算密钥组成部分${K_w}$.

1）输入节点. $w \in I$，$D\left( w \right) = {i_w}$.

① 如果$\varOmega _w^* = 1$，选取${v_w}{ \in _{R}}{\mathbb{Z}_p}$，计算

② 如果$\varOmega _w^* = 0$，选取${\eta _w}{ \in _{R}}{\mathbb{Z}_p}$，计算

这里隐含地令${v_w} = {c_{n + 1}}\times {c_{n + 2}} \times … \times {c_{n + \ell - {i_w} + 2}} + {\eta _w}$.

2）或门. $w \in G$，$GT\left( w \right) = {\text{OR}}$，$D\left( w \right) = {i_w}$.

① 如果${f_w}({\varOmega ^*}) = 1$，选取${z_w},{v_w}{ \in _{R}}{\mathbb{Z}_p}$.

（i）计算${K_{w,1}} = g_{{i_{L(w)}} - {i_w}}^{{z_w}}$.

（ii）如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, 选取${z'_w}{ \in _{R}}{\mathbb{Z}_p}$, 计算${K'_{w,1}} = g_{{i_{R(w)}} - {i_w}}^{{{z'}_w}}$.

（iii）如果${f_{L\left( w \right)}}({\varOmega ^*}) = 1$，计算${K_{w,2}}$$= g_{\ell - {i_w} + 1}^{{v_w} - {z_w}\times {v_{L\left( w \right)}}}$.

（iv）如果${f_{L\left( w \right)}}({\varOmega ^*}) = 0$，此时${v_{L\left( w \right)}} = {c_{n + 1}}\times {c_{n + 2}} \times … \times$ ${c_{n + \ell - {i_{L(w)}} + 2}}$$+ {\eta _{L\left( w \right)}}$，计算

（v）如果${f_{R\left( w \right)}}({\varOmega ^*}) = 1$，计算

（vi）如果${f_{R\left( w \right)}}({\varOmega ^*}) = 0$，此时${v_{R\left( w \right)}} = {c_{n + 1}}\times {c_{n + 2}}\times … \times$ ${c_{n + \ell - {i_{R(w)}} + 2}} + {\eta _{R\left( w \right)}}$.如果$D\left( {L(w)} \right) =$ $D\left( {R(w)} \right)$，使用${z_w}$；否则，使用${z'_w}$，计算

② 如果${f_w}({\varOmega ^*}) = 0$，则${f_{L\left( w \right)}}({\varOmega ^*}) =$ ${f_{R\left( w \right)}}({\varOmega ^*}) = 0$，有${v_{L\left( w \right)}} \;=\; {c_{n + 1}} \times {c_{n + 2}}\times … \times {c_{n + \ell - {i_{L(w)}} + 2}}$ + ${\eta _{L\left( w \right)}}$ 和${v_{R\left( w \right)}} \;=\; {c_{n + 1}} \times {c_{n + 2}} \times … \times {c_{n + \ell - {i_{R(w)}} + 2}} + {\eta _{R\left( w \right)}}$.选取${\psi _w},{\eta _w}{ \in _{R}}{\mathbb{Z}_p}$（如果$w = {w_{{\text{top}}}} = {w_{n + q}}$，令${\eta _{n + q}} = 0$，下同）.

（i）如果$D\left( {L(w)} \right) = D\left( {R(w)} \right)$, 即${i_{L(w)}} = {i_{R(w)}}$,计算

${K_{w,3}}$的仿真同${K_{w,2}}$，只是得将L(w)改为R(w).

这里隐含地令${z_w} = {c_{n + \ell - {i_{L(w)}} + 3}}\times {c_{n + \ell - {i_{L(w)}} + 4}} \times … \times$ ${c_{n + \ell - {i_w} + 2}} + {\psi _w}$, ${v_w} = {c_{n + 1}}\times {c_{n + 2}} \times … \times {c_{n + \ell - {i_w} + 2}} + {\eta _w}$.

（ii）如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, ${K_{w,1}}$,${K_{w,2}}$, ${K_{w,3}}$的仿真同(i)中的${K_{w,1}},{K_{w,2}},{K_{w,3}}$

这里隐含地令${z_w} = {c_{n + \ell - {i_{L(w)}} + 3}}\times{c_{n + \ell - {i_{L(w)}} + 4}}\times …\times$ ${c_{n + \ell - {i_w} + 2}}$+${\psi _w}$, ${z'_w} = {c_{n + \ell - {i_{R(w)}} + 3}}\times{c_{n + \ell - {i_{R(w)}} + 4}} \times…\times{c_{n + \ell - {i_w} + 2}}+{\psi _w}$，${v_W} = {c_{n + 1}}\times{c_{n + 2}} \times…\times {c_{n + \ell - {i_w} + 2}} + {\eta _w}$.

(i)和(ii)的区别在于${i_{L(w)}}$与${i_{R(w)}}$是否相等，如果相等则${z_w}$与${z'_w}$相同，不必区别处理；否则必须区别处理.

③ 如果$D\left( {L(w)} \right) =$ $D\left( {R(w)} \right)$，令${K_w} = \{ {K_{w,1}},$ ${K_{w,2}},{K_{w,3}}\}$；否则，令${K_w} = \{ {K_{w,1}},{K'_{w,1}},{K_{w,2}},$${K_{w,3}}\}$.

3）与门. $w \in G$，$GT\left( w \right) = {\text{AND}}$，$D\left( w \right) = {i_w}$.

① 如果${f_w}\left( {{\varOmega ^*}} \right) = 1$且$D\left( {L(w)} \right) = D\left( {R(w)} \right)$, 选取${z_w}, {v_w}{ \in _{R}}{\mathbb{Z}_p}$，计算

② 如果${f_w}\left( {{\varOmega ^*}} \right) = 1$但$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, 选取${z_w}, {z'_w},{v_w}{ \in _{R}}{\mathbb{Z}_p}$, 计算

③ 如果${f_{L\left( w \right)}}\left( {{\varOmega ^*}} \right) = {f_{R\left( w \right)}}\left( {{\varOmega ^*}} \right) = 0$，此时有${v_{L\left( w \right)}} = {c_{n + 1}} \times {c_{n + 2}} \;\times\;…\;\times\; {c_{n + \ell - {i_{L(w)}} + 2}}$+${\eta _{L\left( w \right)}}$ 和${v_{R\left( w \right)}} \;=\; {c_{n + 1}}\;\times\;{c_{n + 2}}\;\times\; … \;\times$ ${c_{n + \ell - {i_{R(w)}} + 2}} + {\eta _{R\left( w \right)}}$.选取${\psi _w},{\eta _w}{ \in _{R}}{\mathbb{Z}_p}$.

（i）如果$D\left( {L(w)} \right) = D\left( {R(w)} \right)$, 即${i_{L(w)}} = {i_{R(w)}}$, 计算

这里隐含地令${z_w} = {2^{ - 1}}({c_{n + \ell - {i_{L(w)}} + 3}} \times… \times{c_{n + \ell - {i_w} + 2}}) + {\psi _w}$, ${v_w} = {c_{n + 1}}\times{c_{n + 2}} \times…\times {c_{n + \ell - {i_w} + 2}} + {\eta _w}$.

（ii）如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, 选取${z'_w}{ \in _{R}}{\mathbb{Z}_p}$，计算

这里隐含地令${z_w} = {c_{n + \ell - {i_{L(w)}} + 3}} \times … \times {c_{n + \ell - {i_w} + 2}} + {\psi _w}$，${v_w} = {c_{n + 1}}\times {c_{n + 2}} \times…\times {c_{n + \ell - {i_w} + 2}} + {\eta _w}$.

④ 如果${f_{L\left( w \right)}}\left( {{\varOmega ^*}} \right) = 0$而${f_{R\left( w \right)}}\left( {{\varOmega ^*}} \right) = 1$.

（i）如果$D\left( {L(w)} \right) = D\left( {R(w)} \right)$, 即${i_{L(w)}} = {i_{R(w)}}$, 选取${\psi _w},{\eta _w}{ \in _{R}}{\mathbb{Z}_p}$，计算

这里隐含地令${z_w} = {c_{n + \ell - {i_{L(w)}} + 3}}\times … \times$ ${c_{n + \ell - {i_w} + 2}}{\text{ + }}{\psi _w}$, ${v_w} = {c_{n + 1}}\times {c_{n + 2}}\times …\times {c_{n + \ell - {i_w} + 2 }}+{\eta _w}$.

（ii）如果$D\left( {L(w)} \right) \ne D\left( {R(w)} \right)$, 选取${z'_w}{ \in _{R}}{\mathbb{Z}_p}$，计算

这里隐含地令${z_w} = {c_{n + \ell - {i_{L(w)}} + 3}}\times … \times$${c_{n + \ell - {i_w} + 2}}{\text{ + }}{\psi _w}$, ${v_w} = {c_{n + 1}}\times {c_{n + 2}} \times…\times {c_{n + \ell - {i_w} + 2 }}+ {\eta _w}$.

⑤ 如果${f_{L\left( w \right)}}\left( {{\varOmega ^*}} \right) = 1$而${f_{R\left( w \right)}}\left( {{\varOmega ^*}} \right) = 0$，与${f_{L\left( w \right)}}\left( {{\varOmega ^*}} \right) = 0$而${f_{R\left( w \right)}}\left( {{\varOmega ^*}} \right) = 1$类似，只是得将L(w)改为R(w).

⑥ 如果$D\left( {L(w)} \right) =$ $D\left( {R(w)} \right)$，令${K_w} = \{ {K_{w,1}},$ ${K_{w,2}}\}$；否则，令${K_w} = \{ {K_{w,1}},{K'_{w,1}},{K_{w,2}}\}$.

4）最后，返回$S{K_f} = {\left\{ {{K_w}} \right\}_{w \in N}}$给敌手$\mathcal{F}$.

H-Oracle. 当敌手$\mathcal{F}$询问消息${M_i}$的Hash值时，如果${M_i}$在${\mathbb{L}_H}$中，则返回相应的${h_i}$；否则，$\mathcal{B}$响应如1)~4):

1）选取${\rho _i} \in \{ 0,1\}$，使${\rho _i} = 0$的概率为${\left( {{q_{\text{s}}} + 1} \right)^{ - 1}}$.

2）如果${\rho _i} = 1$，选取${r_i}{ \in _{R}}{\mathbb{Z}_p}$，令${h_i} = {g^{{r_i}}}$.

3）如果${\rho _i} = 0$，令${h_i} = {g^{{c_{n + \ell + 3}}}}$，${r_i} = \bot$.

4）返回${h_i}$给敌手$\mathcal{F}$，添加$\left( {{M_i},{h_i},{r_i},{\rho _i}} \right)$到${\mathbb{L}_H}$.

Sign Oracle. 当敌手$\mathcal{F}$询问关于消息${M_j}$和属性${\varOmega _j}$的签名时，$\mathcal{B}$先请求关于消息${M_j}$的H-Oracle服务，从${\mathbb{L}_H}$中得到相应的${r_j}$和${\rho _j}$.如果${\rho _j} = 0$，则中止；否则，计算并返回

Forgery. 敌手$\mathcal{F}$输出关于$\left( {{M^*},{\varOmega ^*}} \right)$的签名${\sigma ^*}$.

Output. 从${\mathbb{L}_H}$中找到与${M^*}$对应的${r_i}^*$和${\rho _i}^*$.如果${\rho _i}^* = 1$，则中止；否则，$\mathcal{B}$输出${\sigma ^*}$作为给定k-MCDH问题的解.

当${\rho _i}^* = 0$并且${\sigma ^*}$是关于$\left( {{M^*},{\varOmega ^*}} \right)$的有效签名时，则

因此，${\sigma ^*} = g_{k - 1}^{\prod\limits_{i \in [1,k]} {{c_i}} }$是k-MCDH问题的解.

由于上述Setup，KeyGen，H-Oracle, Sign Oralce的仿真都是完善的，如果$\mathcal{B}$没有中止，$\mathcal{F}$输出1个有效签名的概率至少为$\varepsilon$.

因为${\rho _i} = 0$的概率是${({q_{\text{s}}} + 1)^{ - 1}}$，$\mathcal{B}$在Sign Oralce中不中止的概率至少为${(1 - {({q_{\text{s}}} + 1)^{ - 1}})^{{q_{\text{s}}}}}$，因此，$\mathcal{B}$解k-MCDH问题的概率至少为

当$n \to \infty$时，概率等于$\dfrac{1}{\text{e}{q}_{\text{s}}}\varepsilon$，因此，在k-MCDH假设下，所提出的一般电路密钥策略基于属性签名方案是自适应选取消息但选定属性攻击下存在不可伪造的. 证毕.

定理3. 所提出的一般电路密钥策略基于属性签名方案具有完善隐私性.

证明.对于任何$M,\varOmega$和满足${f_0}\left( \varOmega \right) = {f_1}\left( \varOmega \right) = 1$的${f_0},{f_1}$，对应于${f_0},{f_1}$的签名分布${\sigma _0} \leftarrow Sign\left( {S{K_{{f_0}}},M,\varOmega } \right)$和${\sigma _1} \leftarrow Sign\left( {S{K_{{f_1}}},M,\varOmega } \right)$分别为

分布$\{\sigma _0\}$和$\{\sigma _1\}$是完全一样的, 因此是信息论意义不可区分的，所以所提出的方案具有完善隐私性.证毕.

4.2   性能与效率分析

与已有方案相比，本文方案有2个显著优点：一是访问结构的表达能力达到最强，可以支持任意访问结构；二是签名只有1个群元素，长度达到最短.

正前文所指出的，目前只有3个支持电路访问结构的基于属性签名方案：Tang等人^[10]方案、Sakai等人^[11]方案和Kaafarani等人^[12]方案.文献[11-12]方案的签名的长度都与电路的大小成线性增长关系，效率都很低，Tang等人^[10]方案的签名大小也仅为1个群元素.

将本文方案与Tang等人^[10]方案进行比较，结果如表2所示.本文方案在安全性和访问结构的表达力方面都有明显优势.

表  2  方案性能比较

Table  2.  Performance Comparison of Schemes

性质	Tang等人[10]方案	本文方案
不可伪造性	EUF-sA-sMA	EUF-sA-CMA
隐私性	完善隐私性	完善隐私性
访问结构	特殊电路	一般电路

下载: 导出CSV 

| 显示表格

因为不同的电路会有不同的数据规模和计算开销，本文以图1的电路和1个输入为$n = 64$的电路为例进行效率比较，结果如表3所示.当$n = 64$，属性的数量是2⁶⁴（>7.38×10¹⁹），电路$f$的数量更是不受限制，因此能完全满足应用需要.

表  3  方案效率对比（m = 160）

Table  3.  Efficiency Comparison of Schemes with m Equals 160

属性数n	比较项	Tang等人[10]方案	本文方案	指标比值%
64	主公钥大小	449$|{\mathbb{G}}|$	129$|{\mathbb{G}}|$	28.73
	主私钥大小	449$|{\mathbb{Z} }|$	129$|{\mathbb{Z} }|$	28.73
	签名钥大小	285$|{\mathbb{G}}|$	222$|{\mathbb{G}}|$	77.89
	签名钥生成开销	285 E	222 E	77.89
	签名生成开销	2401 P	1508 P	62.81
	签名验证开销	225 P	66 P	29.33
6	主公钥大小	333$|{\mathbb{G}}|$	13$|{\mathbb{G}}|$	3.90
	主私钥大小	333$|{\mathbb{G}}|$	13$|{\mathbb{G}}|$	3.90
	签名钥大小	30$|{\mathbb{G}}|$	25$|{\mathbb{G}}|$	83.33
	签名钥生成开销	30 E	25 E	83.33
	签名生成开销	194 P	18 P	9.28
	签名验证开销	167 P	8 P	4.79
注：$|{\mathbb {G} }|$和$|{\mathbb {Z} }|$分别表示群${ {\mathbb {G} }_i}$和集合${\mathbb{Z}_p}$中元素的长度；E和P分别表示1次幂指数运算和1次双线性对运算开销；指标比值是本文方案指标与Tang等人[10]方案指标的比值.

下载: 导出CSV 

| 显示表格

比较结果表明：本文方案在数据长度和计算开销2方面性能都具有优势.

5.   结　　论

ABS能提供灵活的隐私保护，在许多场景有重要应用.本文使用多线性映射构造了一个密钥策略的ABS方案，可支持一般电路作为访问结构.与同类方案相比，本文方案在安全性、访问结构表达力、数据长度和计算开销等方面都有明显优势.

进一步研究的方向将是提出自适应选择消息且自适应选择属性攻击下存在不可伪造的方案，且在标准模型下证明其安全性.

作者贡献声明：黄振杰负责方案设计、安全性证明和定稿；林志伟负责方案设计、性能分析和初稿撰写.