基于属性的全同态签名方案

Attribute-Based Fully Homomorphic Signature Scheme

摘要

基于属性的签名是基于身份的签名的扩展和延伸，相比基于身份的签名具有显著的优势。本文首先利用Gorbunov-Vaikuntanathan-Wichs基于格的层次型全同态签名方案的构建技术，构造了一个支持门限策略的层次型基于属性的全同态签名方案；然后在标准模型下基于小整数解（small integer solution， SIS）问题的困难性证明了所构造的方案满足固定选择消息攻击下的选择性策略的强不可伪造性；最后给出了所构造的方案的参数设置和性能分析。

Abstract

An attribute-based signature is an extension of an identity-based signature, which has significant advantages over an identity-based signature. At first, we construct a leveled attribute-based fully homomorphic signature scheme supporting threshold access policy by using the building technique of Gorbunov-Vaikuntanathan-Wichs leveled fully homomorphic signature scheme over lattices. We then demonstrate that the proposed scheme achieves strong unforgeability under a selectively chosen message attack, grounded in the hardness of the Small Integer Solution (SIS) problem within the standard model. Finally, we provide the constructed scheme’s parameter setting and performance analysis.

关键词

全同态签名 / 属性 / 强不可伪造性 / 小整数解问题

Key words

fully homomorphic signature / attribute / strong unforgeability / small integer solution (SIS) problem

0　 引 言

基于属性的签名(Attribute-Based Signature, ABS)是基于身份的签名(Identity-Based Signature, IBS)的扩展和延伸。IBS中，用户的身份为用户标识，如E-mail地址、电话号码等。ABS中，用户的身份为属性集合。属性集合相比单一的用户标识具有更为丰富的表达能力。通过引入访问策略，ABS还能够实现匿名认证和细粒度访问控制。因此，ABS相比IBS具有显著的优势。2011年Maji等^[1]给出了ABS的定义和安全模型。此后研究人员提出了大量的支持不同访问策略的ABS方案，例如支持门限策略的ABS方案^[2]、支持树形策略的ABS方案^[3]和支持电路策略的ABS方案^[4]等。关于ABS的研究综述可参见文献[5]。

全同态签名(Fully Homomorphic Signature, FHS)是一种具有附加性质的签名体制，允许在没有签名私钥的情况下，对已认证的数据进行计算，并同态地产生计算结果的有效签名，即f(({\mu }_{\mathrm{1}},{\sigma }_{\mathrm{1}}=\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}({\mu }_{\mathrm{1}})),\dots ,({\mu }_k,{\sigma }_k=\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}({\mu }_k)))=(\mu \mathrm{\text{'}}=f({\mu }_{\mathrm{1}},\dots ,{\mu }_k),\sigma \mathrm{\text{'}}=\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(f({\mu }_{\mathrm{1}},\dots ,{\mu }_k)))，其中f表示任意函数，Sign表示签名算法，\mu表示消息，\sigma表示签名。FHS的安全性包括隐私性和不可伪造性，其中隐私性是指同态计算的签名{\sigma }^{\text{'}}，除计算的消息{\mu }^{\text{'}}外，不应泄露原始消息{\mu }_{\mathrm{1}},\dots ,{\mu }_k。Gorbunov等^[6]提出了一种基于格的层次型全同态签名方案(Gorbunov-Vaikuntanathan-Wichs，简称GVW)，并在标准模型下基于小整数解(Small Integer Solution, SIS)问题的困难性，证明了该方案满足固定选择消息攻击下的存在不可伪造性(Existential Unforgeability under static Chosen-Message Attacks, EU-sCMA)。在层次型全同态签名方案中，方案的参数依赖于方案所能计算的电路的深度。Boyen等^[7]也提出了一种基于格的层次型全同态签名方案(Boyen-Fan-Shi，简称BFS)，并在标准模型下基于SIS问题的困难性，证明了该方案满足适应性选择消息攻击下的存在不可伪造性(Existential Unforgeability under Adaptive Chosen-Message Attacks, EU-CMA)。GVW能够提供弱上下文隐藏的隐私性，BFS却不能够提供任何程度的隐私性，因此不适用于许多现实的应用场合。此外，研究人员还提出了高效的基于格的全同态签名方案^[8]、基于NTRU格的全同态签名方案^[9]和基于格的全同态签密方案^[10]。关于全同态签名的研究进展可参见文献[11]。本文专注于层次型全同态签名方案，在叙述时将省略“层次型”一词。

近十年来，研究人员提出了一些基于身份的全同态签名(Identity-Based Fully Homomorphic Signature, IBFHS)方案^[12~15]，但基于属性的全同态签名(Attribute-Based Fully Homomorphic Signature, ABFHS)方案尚未被提出。

本文认为，将ABS和FHS结合，能够实现匿名认证和细粒度访问控制。鉴于此，构造了一个基于格的支持门限策略的ABFHS方案。具体地，首先给出了支持门限策略的ABFHS方案的形式化定义和固定选择消息攻击下选择性策略的强不可伪造性(selective-Policy Strong Unforgeability under static Chosen-Message Attacks, sP-SU-sCMA)的安全模型；其次，基于GVW的设计技术构造了一个支持门限策略的ABFHS方案，并在标准模型下基于SIS问题的困难性证明了所构造的方案满足sP-SU-sCMA安全性；最后给出了所构造的方案的参数设置和性能分析，并与文献[12，13]中的IBFHS方案进行了对比。

1　 预备知识

1.1　符号约定

本文中的一些符号如表1所示。

1.2　统计距离与最小熵

定义1 统计距离。对离散随机变量X\leftarrow \mathrm{𝒳}和Y\leftarrow \mathrm{𝒴}，它们的统计距离定义为：

\Delta (X,Y)=\frac{\mathrm{1}}{\mathrm{2}}\sum _{a\in \mathrm{𝒳}\bigcup \mathrm{𝒴}}\left|\left.\mathrm{P}\mathrm{r}[X=a]-\mathrm{P}\mathrm{r}[Y=a]\right|\right.

如果\Delta (X,Y)=\mathrm{n}\mathrm{e}\mathrm{l}\mathrm{g}(\lambda )，则称随机变量X和Y是统计接近的。

定义2 最小熵。随机变量X的最小熵定义为H_{\mathrm{\infty }}(X)=-\mathrm{l}\mathrm{o}\mathrm{g}(\underset{x}{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{P}\mathrm{r}[X=x])。X以Y为条件的平均最小熵定义为：

H_{\mathrm{\infty }}(X|Y)=-\mathrm{l}\mathrm{o}\mathrm{g}(E_{y\leftarrow \mathrm{𝒴}}[\underset{x}{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{P}\mathrm{r}[X=x|Y=y]])

其中，E表示数学期望。给定相关的Y，敌手猜测X的最优概率为{\mathrm{2}}^{-H_{\mathrm{\infty }}(X|Y)}。

引理1^[16] 假设X\leftarrow \mathrm{𝒳}和Y\leftarrow \mathrm{𝒴}为任意的随机变量，那么有H_{\mathrm{\infty }}(X|Y)\ge H_{\mathrm{\infty }}(X)-\mathrm{l}\mathrm{o}\mathrm{g}(\left|\mathrm{𝒴}\right|)。

1.3　格

定义3 格。令矩阵\mathit{B}=({\mathit{b}}_{\mathrm{1}}|\cdots |{\mathit{b}}_k)\in {\mathbb{R}}^{m\times k}，其列向量{\mathit{b}}_{\mathrm{1}},\dots ,{\mathit{b}}_k是一组线性无关向量，格\Lambda定义为：

\Lambda =\{\mathit{y}\in {\mathbb{R}}^m\mathrm{s}.\mathrm{t}.\exists z\in {\mathbb{Z}}^k,\mathit{y}=\mathit{B}z=\sum _{i\in [k]}{z}_i{\mathit{b}}_i\}

其中，\mathit{B}为\Lambda的一组基，m为\Lambda的维数，k为\Lambda的秩，且k\le m，当k=m时，\Lambda称为满秩格。

定义4q模格。对素数q、矩阵\mathit{A}\in {\mathbb{Z}}_q^{n\times m}和向量\mathit{u}\in {\mathbb{Z}}_q^n，定义两个m维整数格：

{\Lambda }^{\perp }(\mathit{A})=\{\mathit{e}\in {\mathbb{Z}}^m\mathrm{s}.\mathrm{t}.\mathit{A}\mathit{e}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q\}

{\Lambda }_{\mathit{u}}^{\perp }(\mathit{A})=\{\mathit{e}\in {\mathbb{Z}}^m\mathrm{s}.\mathrm{t}.\mathit{A}\mathit{e}=\mathit{u}\mathrm{m}\mathrm{o}\mathrm{d}q\}

可以看出，如果\mathit{t}\in {\Lambda }_{\mathit{u}}^{\perp }(\mathit{A})，则{\Lambda }_{\mathit{u}}^{\perp }(\mathit{A})={\Lambda }^{\perp }(\mathit{A})+\mathit{t}，因此{\Lambda }_{\mathit{u}}^{\perp }(\mathit{A})是{\Lambda }^{\perp }(\mathit{A})的一个陪集。

定义5 离散高斯分布。对任意向量\mathit{c}\in {\mathbb{R}}^m、实数s>\mathrm{0}和m维格\Lambda，\Lambda以 c 和s分别为中心和参数的离散高斯分布定义为：

\forall \mathit{x}\in \Lambda ,D_{\Lambda ,s,\mathit{c}}(\mathit{x})=\frac{{\rho }_{s,\mathit{c}}(\mathit{x})}{{\rho }_{s,\mathit{c}}(\Lambda )}

其中，{\rho }_{s,\mathit{c}}(\mathit{x})=\mathrm{e}\mathrm{x}\mathrm{p}(-\mathrm{\pi }{‖\mathit{x}-\mathit{c}‖}^{\mathrm{2}}/s^{\mathrm{2}})是{\mathbb{R}}^n上以\mathit{c}和s分别为中心和参数的高斯函数。

引理2^[17] 对任意m维格\Lambda、向量\mathit{c}\in {\mathbb{R}}^m和实数、s\ge {\eta }_{\mathrm{ϵ}}(\Lambda )，有：

\mathrm{P}{\mathrm{r}}_{\mathit{x}\leftarrow D_{\Lambda ,s,\mathit{c}}}\left[\Vert \mathit{x}-\mathit{c} \Vert >s\sqrt[]{m}\right]\le \frac{\mathrm{1}+\mathrm{ϵ}}{\mathrm{1}-\mathrm{ϵ}}\cdot {\mathrm{2}}^{-m}

这里{\eta }_{\mathrm{ϵ}}(\Lambda )是\Lambda的光滑参数，并且{\eta }_{\mathrm{ϵ}}(\Lambda )\le \Vert \tilde{\mathit{B}} \Vert \cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}n})，其中\mathit{B}为\Lambda的任意一组基。

引理3^[18] 令n和q为正整数，且q为素数，令m\ge \mathrm{2}n\mathrm{l}\mathrm{o}\mathrm{g}q，则对几乎所有的\mathit{A}\in {\mathbb{Z}}_q^{n\times m}以及对任意的s\ge \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}m})，\mathit{u}=\mathit{A}\mathit{e}\mathrm{m}\mathrm{o}\mathrm{d}q的分布统计接近{\mathbb{Z}}_q^n上的均匀分布，其中\mathit{e}\leftarrow D_{{\mathbb{Z}}^m,s}。

引理4^[19] 存在概率多项式时间算法\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^n)，它输入正整数n、q\ge \mathrm{2}和m\ge \mathrm{6}n\mathrm{l}\mathrm{o}\mathrm{g}q，输出矩阵\mathit{A}\in {\mathbb{Z}}_q^{n\times m}和{\Lambda }^{\perp }(\mathit{A})的一组基{\mathit{T}}_{\mathit{A}}\in {\mathbb{Z}}^{m\times m}，并且满足\mathit{A}统计接近{\mathbb{Z}}_q^{n\times m}上的均匀分布，\Vert \widetilde{{\mathit{T}}_{\mathit{A}}}\Vert \le O(\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}q})。

引理5^[20] 存在确定性多项式时间算法\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}({\mathit{T}}_{\mathit{A}},\mathit{F}=(\mathit{A}|{\mathit{A}}_{\mathrm{1}}))，它输入{\Lambda }^{\perp }(\mathit{A})的一组基{\mathit{T}}_{\mathit{A}}\in {\mathbb{Z}}^{m\times m}和\mathit{F}=(\mathit{A}|{\mathit{A}}_{\mathrm{1}})\in {\mathbb{Z}}_q^{n\times (m+m_{\mathrm{1}})}，其中\mathit{A}\in {\mathbb{Z}}_q^{n\times m}，{\mathit{A}}_{\mathrm{1}}\in {\mathbb{Z}}_q^{n\times m_{\mathrm{1}}}，并且\mathit{A}的秩\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\mathit{A})=n，输出{\Lambda }^{\perp }(\mathit{F})的一组基{\mathit{T}}_{\mathit{F}}\in {\mathbb{Z}}^{(m+m_{\mathrm{1}})\times (m+m_{\mathrm{1}})}，满足\Vert \widetilde{{\mathit{T}}_{\mathit{F}}}\Vert =\Vert \widetilde{{\mathit{T}}_{\mathit{A}}}\Vert。即使任意排列\mathit{F}的列，这个结论仍是成立的。

引理6^[20] 存在概率多项式时间算法\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}(\mathit{T},s)，它输入m维整数格\Lambda的一组基\mathit{T}和高斯参数s\ge \Vert \tilde{\mathit{T}}\Vert \cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}m})，输出\Lambda的一组基{\mathit{T}}^{\text{'}}，并且\Vert {\mathit{T}}^{\text{'}} \Vert \le s\sqrt[]{m}。对\Lambda的任意两组基{\mathit{T}}_{\mathrm{0}}和{\mathit{T}}_{\mathrm{1}}以及任意高斯参数s\ge \mathrm{m}\mathrm{a}\mathrm{x}\{\Vert \widetilde{{\mathit{T}}_{\mathrm{0}}}\Vert ,\Vert \widetilde{{\mathit{T}}_{\mathrm{1}}}\Vert \}\cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}n})，\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}({\mathit{T}}_{\mathrm{0}},s)和\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}({\mathit{T}}_{\mathrm{1}},s)的输出是统计接近的。

引理7^[18] 存在概率多项式时间算法\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}(\mathit{A},{\mathit{T}}_{\mathit{A}},s,\mathit{u})，它输入矩阵\mathit{A}\in {\mathbb{Z}}_q^{n\times m}、{\Lambda }^{\perp }(\mathit{A})的一组基{\mathit{T}}_{\mathit{A}}\in {\mathbb{Z}}^{m\times m}、高斯参数s\ge \Vert \widetilde{{\mathit{T}}_{\mathit{A}}}\Vert \cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}m})和向量\mathit{u}\in {\mathbb{Z}}_q^n，其中q\ge \mathrm{2}，m>n，它从统计接近D_{{\Lambda }_{\mathit{u}}^{\perp }(\mathit{A}),s}的分布输出抽样\mathit{e}\in {\mathbb{Z}}^m。

1.4　SIS问题

定义6 SIS问题。给定整数q、矩阵\mathit{A}\in {\mathbb{Z}}_q^{n\times m}和实数\beta，寻找一个非零整数向量\mathit{e}\in {\mathbb{Z}}^m\backslash \{\mathrm{0}\}，满足\mathit{A}\mathit{e}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q和\Vert \mathit{e} \Vert \le \beta。

对于函数q\left(n\right)、m\left(n\right)和\beta (n)，\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }是实例(q(n),\mathit{A},\beta (n))的集合，其中\mathit{A}\in {\mathbb{Z}}_{q(n)}^{n\times m(n)}是均匀随机的。

引理8^{[17, 18]} 对于任意多项式界的m=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)和\beta =\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)以及对于任意素数q\ge \beta \cdot \omega (\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}n})，平均情况下的小整数解问题\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }与最差情况下的近似最短独立向量问题\mathrm{S}\mathrm{I}\mathrm{V}{\mathrm{P}}_{\gamma }一样困难，其中近似因子\gamma =\beta \cdot \tilde{O}(\sqrt[]{n})。

2　 基于属性的全同态签名与安全性的定义

2.1　形式化定义

一个支持门限策略的层次型 ABFHS方案包括七个多项式时间算法，具体如下：

\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },{\mathrm{1}}^d,{\mathrm{1}}^N,\mathrm{𝒰})：输入安全参数\lambda、电路的最大深度d、消息数据集的最大尺寸N和属性全集\mathrm{𝒰}，输出公开参数prms。公开参数prms包含消息空间\mathrm{ℳ}的定义。

\mathrm{M}\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}，输出主私钥\mathrm{m}\mathrm{s}\mathrm{k}和对应的主公钥mpk。

KeyGen(prms,mpk,msk,P)：输入公开参数prms、主公钥mpk、主私钥msk和属性集合P\subset \mathrm{𝒰}，输出私钥\mathrm{s}{\mathrm{k}}_P。

\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_P,\Gamma ,\{{\mu }_i{\in \mathrm{ℳ}\}}_{i\in [N]})：输入公开参数prms、主公钥mpk、属性集合P的私钥\mathrm{s}{\mathrm{k}}_P、门限策略\Gamma =(t,S)和消息集合\{{\mu }_i{\in \mathrm{ℳ}\}}_{i\in [N]}，其中S\subset \mathrm{𝒰}为属性集合，\mathrm{1}\le t\le \left|S\right|为门限，并且\left|P\bigcap S\right|\ge t，即属性集合P满足门限策略\Gamma =(S,t)。输出签名集合\{{\sigma }_i{\}}_{i\in [N]}。

\mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f,\{({\mu }_i,{\sigma }_i{)\}}_{i\in [N]})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}和来自同一签名人的消息‑签名对\{({\mu }_i,{\sigma }_i={\mathit{U}}_i{)\}}_{i\in [N]}，同态计算并输出消息{\mu }^{\#}=f({\mu }_{\mathrm{1}},\dots ,{\mu }_N)的签名{\sigma }^{\#}。

\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f)：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，同态计算并输出电路f的“公钥”{\alpha }_f。

\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\Gamma ,{\alpha }_f,{\mu }^{\#},{\sigma }^{\#})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、主公钥\mathrm{m}\mathrm{p}\mathrm{k}、门限策略\Gamma =(t,S)、电路f的“公钥”{\alpha }_f、消息{\mu }^{\#}\in \mathrm{ℳ}和签名{\sigma }^{\#}，其中S\subset \mathrm{𝒰}为属性集合，\mathrm{1}\le t\le \left|S\right|为门限。如果{\sigma }^{\#}是针对{\alpha }_f的有效签名，则输出\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}认为{\mu }^{\#}确实是f的输出，否则输出\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}。

定义7 正确性。对任意的\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },{\mathrm{1}}^d,{\mathrm{1}}^N,\mathrm{𝒰})、P\subset \mathrm{𝒰}、\{{\mu }_i{\in \mathrm{ℳ}\}}_{i\in [N]}、\Gamma =(t,S)和f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，满足\left|P\bigcap S\right|\ge t,设定(\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k})\leftarrow \mathrm{M}\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s})、\mathrm{s}{\mathrm{k}}_P\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k},P)和\{{\sigma }_i{\}}_{i\in [N]}\leftarrow\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_P,\Gamma ,\{{\mu }_i{\}}_{i\in [N]}),若有：\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\Gamma ,{\alpha }_f,{\mu }^{\#},{\sigma }^{\#})=\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}，其中{\mu }^{\#}=f({\mu }_{\mathrm{1}},\dots ,{\mu }_N)，{\sigma }^{\#}\leftarrow \mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f,\{({\mu }_i,{\sigma }_i{)\}}_{i\in [N]})，{\alpha }_f\leftarrow \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f),我们就称这个ABFHS方案是正确的。

2.2　安全性

ABFHS方案应满足两项安全需求，即签名人身份的隐私性和同态计算签名的不可伪造性，其中签名人身份的隐私性是指在验证签名时，只能确定签名人的属性集合是否满足声明的签名策略，而不能确定签名人的具体身份信息。

定义8 完美隐私性。对任意的\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },{\mathrm{1}}^d,{\mathrm{1}}^N,\mathrm{𝒰})、(\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k})\leftarrow \mathrm{M}\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s})、P_{\mathrm{1}}\subset \mathrm{𝒰}、P_{\mathrm{2}}\subset \mathrm{𝒰}、\mathrm{s}{\mathrm{k}}_{P_{\mathrm{1}}}\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k},P_{\mathrm{1}})、\mathrm{s}{\mathrm{k}}_{P_{\mathrm{2}}}\leftarrow\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k},P_{\mathrm{2}})、\{{\mu }_i{\in \mathrm{ℳ}\}}_{i\in [N]}和\Gamma =(t,S),满足：\left|P_{\mathrm{1}}\bigcap S\right|\ge t和\left|P_{\mathrm{2}}\bigcap S\right|\ge t，若\{{\sigma }_i^{(P_{\mathrm{1}})}{\}}_{i\in [N]}\leftarrow\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{P_{\mathrm{1}}},\Gamma ,\{{\mu }_i{\}}_{i\in [N]})和\{{\sigma }_i^{(P_{\mathrm{2}})}{\}}_{i\in [N]}\leftarrow\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{P_{\mathrm{2}}},\Gamma ,\{{\mu }_i{\}}_{i\in [N]})的分布是相同的。我们就称这个ABFHS方案是完美隐私的。

考虑强不可伪造性安全概念sP-SU-sCMA，它要求攻击者在看到\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}和\mathrm{m}\mathrm{p}\mathrm{k}之前宣布攻击的目标策略和签名询问的消息列表。我们通过一个游戏给出这一安全性概念的定义。

定义9 强不可伪造性。考虑下面这个在敌手\mathrm{𝒜}和他的挑战者之间的游戏。

初始化： \mathrm{𝒜}输出目标门限策略{\Gamma }^{\mathrm{*}}=(t,S)以及签名询问的消息列表\{{\mu }_i{\}}_{i\in [N]}，其中S\subset \mathrm{𝒰}，\mathrm{1}\le t\le \left|S\right|。

设置： 挑战者运行\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },{\mathrm{1}}^d,{\mathrm{1}}^N,\mathrm{𝒰})和(mpk,msk)←MKGen(prms)，并把prms和mpk发送给\mathrm{𝒜}。

私钥询问：\mathrm{𝒜}提交属性集合P\subset \mathrm{𝒰}询问其私钥，其中，挑战者运行sk _P ←KeyGen(prms,mpk,msk,P)，并把\mathrm{s}{\mathrm{k}}_P发送给\mathrm{𝒜}。

签名询问： 挑战者任意选择一个属性集合P\subset \mathrm{𝒰}，其满足\left|P\bigcap S\right|\ge t，运行\mathrm{s}{\mathrm{k}}_P\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k},P)和\{{\sigma }_i{\}}_{i\in [N]}\leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_P,{\Gamma }^{\mathrm{*}},\{{\mu }_i{\}}_{i\in [N]})，并把\{{\sigma }_i{\}}_{i\in [N]}发送给\mathrm{𝒜}。

伪造： 最后，\mathrm{𝒜}输出电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}、消息{\mu }^{\mathrm{*}}和签名{\sigma }^{\mathrm{*}}，并且\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(f)\le d。如果满足以下条件：

1) {\sigma }^{\mathrm{*}}\cancel{=}{\sigma }^{\#}，其中{\sigma }^{\#}\leftarrow \mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f,\{({\mu }_i,{\sigma }_i{)\}}_{i\in [N]})；

2) \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},{\Gamma }^{\mathrm{*}},{\alpha }_f,{\mu }^{\mathrm{*}},{\sigma }^{\mathrm{*}})=\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}，其中{\alpha }_f\leftarrow \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f)。

则\mathrm{𝒜}获胜。\mathrm{𝒜}攻击ABFHS方案的sP-SU-sCMA安全性的优势定义为：

\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{𝒜},\mathrm{A}\mathrm{B}\mathrm{F}\mathrm{H}\mathrm{S}}^{\mathrm{s}\mathrm{P}-\mathrm{S}\mathrm{U}-\mathrm{s}\mathrm{C}\mathrm{M}\mathrm{A}}\left(\lambda \right)=\mathrm{P}\mathrm{r}[\mathrm{𝒜}\mathrm{获胜}]

如果对任意的敌手\mathrm{𝒜}，\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{𝒜},\mathrm{A}\mathrm{B}\mathrm{F}\mathrm{H}\mathrm{S}}^{\mathrm{s}\mathrm{P}-\mathrm{S}\mathrm{U}-\mathrm{s}\mathrm{C}\mathrm{M}\mathrm{A}}\left(\lambda \right)=\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )，我们就称这个ABFHS方案是sP-SU-sCMA安全的。

3　 基于属性的全同态签名的构造与安全性分析

引理9^[21] 令\mathrm{𝓁}为正整数。给定j\in [\mathrm{2}\mathrm{𝓁}]和集合J\subset [\mathrm{2}\mathrm{𝓁}]，定义拉格朗日系数为：

L_j=\prod _{i\in J,i\cancel{=}j}\frac{-i}{j-i}

令C=({(\mathrm{2}\mathrm{𝓁})!)}^{\mathrm{2}}。对每一j\in J，C{L}_j为整数，并且\left|C{L}_j\right|\le C^{\mathrm{2}}=({(\mathrm{2}\mathrm{𝓁})!)}^{\mathrm{4}}。

引理10^[22] 对任意m\ge n\cdot ⌈\mathrm{l}\mathrm{o}\mathrm{g}q⌉，存在一个固定的可计算的矩阵\mathit{G}\in {\mathbb{Z}}_q^{n\times m}和一个确定性的多项式时间算法{\mathit{G}}^{-\mathrm{1}}，它们具有以下性质：对于矩阵\mathit{V}\in {\mathbb{Z}}_q^{n\times m^{\text{'}}}，{\mathit{G}}^{-\mathrm{1}}(\mathit{V})\in {\{\mathrm{0,1}\}}^{m\times m^{\text{'}}}为比特矩阵，且满足\mathit{G}{\mathit{G}}^{-\mathrm{1}}(\mathit{V})=\mathit{V}。

3.1　构 造

利用GVW全同态签名方案的设计技术，设计一个支持门限策略的层次型ABFHS方案。

\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },{\mathrm{1}}^d,{\mathrm{1}}^N,\mathrm{𝒰})：输入安全参数\lambda、电路的最大深度d、消息数据集的最大尺寸N和属性全集\mathrm{𝒰}=\{\mathrm{1},\dots ,\mathrm{𝓁}\}，依次执行：

1） 设置默认属性集合{\mathrm{𝒰}}^{†}=\{\mathrm{𝓁}+\mathrm{1},\dots ,\mathrm{2}\mathrm{𝓁}\}。注意，系统中每个用户都拥有默认属性集合{\mathrm{𝒰}}^{†}。

2） 设置参数n、q和m=O (n\mathrm{l}\mathrm{o}\mathrm{g}q)。设置高斯参数s_{\mathrm{1}}和s_{\mathrm{2}}。

3） 令消息空间\mathrm{ℳ}=\{\mathrm{0,1}\}。

4） 对于i\in [N]，随机选择N个矩阵{\mathit{V}}_i\in {\mathbb{Z}}_q^{n\times m}。

5） 输出公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}=(\lambda ,d,N,\mathrm{𝒰},{\mathrm{𝒰}}^{†},n,q,m,s_{\mathrm{1}},s_{\mathrm{2}},\mathrm{ℳ},\{{\mathit{V}}_i{\}}_{i\in [N]})。

\mathrm{M}\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}，执行：

1） 对每一属性i\in \mathrm{𝒰}\bigcup {\mathrm{𝒰}}^{†}，调用\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^n)产生矩阵{\mathit{A}}_i\in {\mathbb{Z}}_q^{n\times m}和{\Lambda }^{\perp }({\mathit{A}}_i)的一组基{\mathit{T}}_{{\mathit{A}}_i}\in {\mathbb{Z}}^{m\times m}，满足\Vert \stackrel{̃}{{\mathit{T}}_{{\mathit{A}}_i}}\Vert \le O (\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}q})。

2） 输出主公钥\mathrm{m}\mathrm{p}\mathrm{k}=(\{{\mathit{A}}_i{\}}_{i\in [\mathrm{2}\mathrm{𝓁}]})和主私钥\mathrm{m}\mathrm{s}\mathrm{k}=(\{{\mathit{T}}_{{\mathit{A}}_i}{\}}_{i\in [\mathrm{2}\mathrm{𝓁}]})。

\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{m}\mathrm{s}\mathrm{k},P)：输入公开参数prms、主公钥mpk、主私钥msk和属性集合P\subset \mathrm{𝒰}，执行：

1） 构造矩阵\mathit{M}：

\mathit{M}={\left(\begin{array}{cccc}\ddots & & & \\ & {\mathit{A}}_i& & \\ & & \ddots & \\ & & & {\mathit{A}}_{\mathrm{2}\mathrm{𝓁}}\end{array}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\left|P\right|)n\times (\mathrm{𝓁}+\left|P\right|)m}

易见，{\Lambda }^{\perp }(\mathit{M})的一组基为：

{\mathit{T}}_{\mathit{M}}={\left(\begin{array}{cccc}\ddots & & & \\ & {\mathit{T}}_{{\mathit{A}}_i}& & \\ & & \ddots & \\ & & & {\mathit{T}}_{{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}}}\end{array}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{𝓁}+\left|P\right|)m}

2） 随机选择一个\mathrm{𝓁}次多项式\varphi (x)\in {\mathbb{Z}}_q[x]，使得\varphi (\mathrm{0})=\mathrm{0}。注意，对于J\subset [\mathrm{2}\mathrm{𝓁}]，如果\left|J\right|\ge \mathrm{𝓁}+\mathrm{1}，则\sum _{j\in J}{L}_j\varphi (j)=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q，其中L_j为拉格朗日系数。

3） 对i\in [\mathrm{𝓁}]，随机选择\mathrm{𝓁}个矩阵{\mathit{Z}}_i\in {\mathbb{Z}}_q^{n\times m}。

4） 构造矩阵\mathit{N}：

\mathit{N}={\left(\begin{array}{ccc}⋮& \ddots & ⋮\\ \varphi (i){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (i){\mathit{Z}}_{\mathrm{𝓁}}\\ ⋮& \ddots & ⋮\\ \varphi (\mathrm{2}\mathrm{𝓁}){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (\mathrm{2}\mathrm{𝓁}){\mathit{Z}}_{\mathrm{𝓁}}\end{array}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\left|P\right|)n\times \mathrm{𝓁}m}

5） 令\mathit{F}=\left(\mathit{M}|\mathit{N}\right)\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\left|P\right|)n\times (\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}。

6） 调用\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}(\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}({\mathit{T}}_{\mathit{M}},\mathit{F}),s_{\mathrm{1}})产生{\Lambda }^{\perp }(\mathit{F})的一组基{\mathit{T}}_{\mathit{F}}\in {\mathbb{Z}}^{(\mathrm{2}\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}。注意，\mathit{F}\cdot {\mathit{T}}_{\mathit{F}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q，且\Vert {\mathit{T}}_{\mathit{F}}\Vert \le s_{\mathrm{1}}\sqrt[]{(\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}。

7） 输出私钥\mathrm{s}{\mathrm{k}}_P={\mathit{T}}_{\mathit{F}}。

\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_P,\Gamma ,\{{\mu }_i{\}}_{i\in [N]})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、主公钥\mathrm{m}\mathrm{p}\mathrm{k}、私钥\mathrm{s}{\mathrm{k}}_P={\mathit{T}}_{\mathit{F}}\in {\mathbb{Z}}^{(\mathrm{2}\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}、门限策略\Gamma =(t,S)和消息集合\{{\mu }_i{\in \mathrm{ℳ}\}}_{i\in [N]}，其中S\subset \mathrm{𝒰}，\mathrm{1}\le t\le \left|S\right|，并且\left|P\bigcap S\right|\ge t，执行：

1） 令C=({(\mathrm{2}\mathrm{𝓁})!)}^{\mathrm{2}}。

2） 选择属性集合R\subseteq P\bigcap S，使得\left|R\right|=t。令R^{†}=\{\mathrm{𝓁}+\mathrm{1},\dots ,\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t\}，则\left|R^{†}\right|=\mathrm{𝓁}+\mathrm{1}-t。易见，R\bigcup R^{†}\subset [\mathrm{2}\mathrm{𝓁}]，并且\left|R\bigcup R^{†}\right|=\mathrm{𝓁}+\mathrm{1}。

3） 对i\in P\bigcup {\mathrm{𝒰}}^{†}和集合R\bigcup R^{†}\subset [\mathrm{2}\mathrm{𝓁}]，计算拉格朗日系数L_i。

4） 计算矩阵：

\mathit{Q}=

{\left(\cdots |C{L}_i{\mathit{I}}_n\mathrm{o}\mathrm{r}{\mathrm{0}}_{n\times n}|\cdots |C{L}_{\mathrm{2}\mathrm{𝓁}}{\mathit{I}}_n\mathrm{o}\mathrm{r}{\mathrm{0}}_{n\times n}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}\in {\mathbb{Z}}_q^{n\times (\mathrm{𝓁}+\left|P\right|)n}

其中，对于i\in P\bigcup {\mathrm{𝒰}}^{†}，若i\in R\bigcup R^{†}，则该项为C{L}_i{\mathit{I}}_n，否则该项为{\mathrm{0}}_{n\times n}。

5） \mathit{F}\cdot {\mathit{T}}_{\mathit{F}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q，故\mathit{Q}\cdot \mathit{F}\cdot {\mathit{T}}_{\mathit{F}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q。即：\mathit{Q}\cdot \left(\mathit{M}|\mathit{N}\right)\cdot {\mathit{T}}_{\mathit{F}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q,\left(\mathit{Q}\cdot \mathit{M}|\mathit{Q}\cdot \mathit{N}\right)\cdot {\mathit{T}}_{\mathit{F}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q。

因为\left|R\bigcup R^{†}\right|=\mathrm{𝓁}+\mathrm{1}，所以\mathit{Q}\mathit{N}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q。故\left(\mathit{Q}\mathit{M}|{\mathrm{0}}_{n\times \mathrm{𝓁}m}\right)\cdot {\mathit{T}}_{\mathit{F}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q。

于是：\mathit{Q}\mathit{M}\cdot {\mathit{T}}_{{\mathit{F}}^{\text{'}}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q,{\mathit{M}}^{\text{'}}{\mathit{Q}}^{\text{'}}\cdot {\mathit{T}}_{{\mathit{F}}^{\text{'}}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q。

其中，{\mathit{M}}^{\text{'}}={\left(\cdots |{\mathit{A}}_i|\cdots |{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}\in {\mathbb{Z}}_q^{n\times (\mathrm{𝓁}+\left|P\right|)m}，{\mathit{Q}}^{\text{'}}=

{\left(\begin{array}{cccc}\ddots & & & \\ & C{L}_i{\mathit{I}}_m\mathrm{o}\mathrm{r}{\mathrm{0}}_{m\times m}& & \\ & & \ddots & \\ & & & C{L}_{\mathrm{2}\mathrm{𝓁}}{\mathit{I}}_m\mathrm{o}\mathrm{r}{\mathrm{0}}_{m\times m}\end{array}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}，{\mathit{Q}}^{\text{'}}\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{𝓁}+\left|P\right|)m}，{\mathit{T}}_{{\mathit{F}}^{\text{'}}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{𝓁}+\left|P\right|)m}为{\mathit{T}}_{\mathit{F}}的左上子块。

调整{\mathit{Q}}^{\text{'}}、{\mathit{M}}^{\text{'}}和{\mathit{T}}_{{\mathit{F}}^{\text{'}}}的行列顺序，可得到：

{\mathit{M}}^{″}{\mathit{Q}}^{″}\cdot {\mathit{T}}_{{\mathit{F}}^{″}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q

其中，{\mathit{M}}^{″}={\left(\cdots |{\mathit{A}}_i|\cdots |{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t}\right)}_{i\in R\bigcup R^{†}}\in {\mathbb{Z}}_q^{n\times (\mathrm{𝓁}+\mathrm{1})m},{\mathit{Q}}^{″}={\left(\begin{array}{cccc}\ddots & & & \\ & C{L}_i{\mathit{I}}_m& & \\ & & \ddots & \\ & & & C{L}_{\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t}{\mathit{I}}_m\end{array}\right)}_{i\in \mathrm{ℛ}\bigcup {\mathrm{ℛ}}^{†}}\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\mathrm{1})m\times (\mathrm{𝓁}+\mathrm{1})m}，{\mathit{T}}_{{\mathit{F}}^{″}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1})m\times (\mathrm{𝓁}+\mathrm{1})m}为{\mathit{T}}_{{\mathit{F}}^{\text{'}}}的左上子块。这样，就得到了{\Lambda }^{\perp }({\mathit{M}}^{″})的一组基{\mathit{T}}_{{\mathit{M}}^{″}}={\mathit{Q}}^{″}\cdot {\mathit{T}}_{{\mathit{F}}^{″}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1})m\times (\mathrm{𝓁}+\mathrm{1})m}。并且，\Vert {\mathit{Q}}^{″}\cdot {\mathit{T}}_{{\mathit{F}}^{″}}\Vert \le C^{\mathrm{2}} \cdot \Vert {\mathit{T}}_{{\mathit{F}}^{″}} \Vert \le C^{\mathrm{2}} \cdot \Vert {\mathit{T}}_{\mathit{F}}\Vert \le C^{\mathrm{2}}\cdot s_{\mathrm{1}}\sqrt[]{(\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}。

6） 设置矩阵\mathit{W}={\left(\cdots |{\mathit{A}}_i|\cdots |{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t}\right)}_{i\in S\bigcup R^{†}}\in{\mathbb{Z}}_q^{n\times (\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

7） 调用\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}({\mathit{T}}_{{\mathit{M}}^{″}},\mathit{W})产生{\Lambda }^{\perp }(\mathit{W})的一组基{\mathit{T}}_{\mathit{W}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m\times (\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

8） 对于i\in [N]，调用\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}(\mathit{W},{\mathit{T}}_{\mathit{W}},{\mathit{V}}_i-{\mu }_i\cdot \mathit{G},s_{\mathrm{2}})产生{\mathit{U}}_i\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m\times m}。注意，\mathit{W}{\mathit{U}}_i={\mathit{V}}_i-{\mu }_i\cdot \mathit{G}\mathrm{m}\mathrm{o}\mathrm{d}q，即\mathit{W}{\mathit{U}}_i+{\mu }_i\cdot \mathit{G}={\mathit{V}}_i\mathrm{m}\mathrm{o}\mathrm{d}q，并且\Vert {\mathit{U}}_i\Vert \le {\beta }_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}=s_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

9） 输出签名集合\{{\sigma }_i={\mathit{U}}_i{\}}_{i\in [N]}。

\mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f,\{({\mu }_i,{\sigma }_i{)\}}_{i\in [N]})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}和来自同一签名人的消息‑签名对\{({\mu }_i,{\sigma }_i={\mathit{U}}_i{)\}}_{i\in [N]}，执行：

1） 对加法门f({\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}})={\mu }_{\mathrm{1}}+{\mu }_{\mathrm{2}}，定义{\mathit{U}}^{+}={\mathit{U}}_{\mathrm{1}}+{\mathit{U}}_{\mathrm{2}}；对乘法门f({\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}})={\mu }_{\mathrm{1}}\cdot {\mu }_{\mathrm{2}}，定义{\mathit{U}}^{\times }={\mathit{U}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})+{\mu }_{\mathrm{1}}\cdot {\mathit{U}}_{\mathrm{2}}。对电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，通过迭代调用这里定义的加法门和乘法门，同态计算签名{\mathit{U}}^{\#}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m\times m}。

2） 输出{\sigma }^{\#}={\mathit{U}}^{\#}。

\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f)：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，执行：

1） 对加法门f({\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}})={\mu }_{\mathrm{1}}+{\mu }_{\mathrm{2}}，定义{\mathit{V}}_{+}={\mathit{V}}_{\mathrm{1}}+{\mathit{V}}_{\mathrm{2}}；对乘法门f({\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}})={\mu }_{\mathrm{1}}\cdot {\mu }_{\mathrm{2}}，定义{\mathit{V}}_{\times }={\mathit{V}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})。对电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，通过迭代调用这里定义的加法门和乘法门，同态计算电路f的“公钥”{\mathit{V}}_f\in {\mathbb{Z}}_q^{n\times m}。

2） 输出{\alpha }_f={\mathit{V}}_f。

\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},\mathrm{m}\mathrm{p}\mathrm{k},\Gamma ,{\mathit{V}}_f,{\mu }^{\#},{\sigma }^{\#})：输入公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}、主公钥\mathrm{m}\mathrm{p}\mathrm{k}、门限策略\Gamma =(t,S)、电路f的“公钥”{\alpha }_f={\mathit{V}}_f\in {\mathbb{Z}}_q^{n\times m}、消息{\mu }^{\#}\in \mathrm{ℳ}和签名{\sigma }^{\#}={\mathit{U}}^{\#}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m\times m}，执行：

1） 计算矩阵\mathit{W}={\left(\cdots |{\mathit{A}}_i|\cdots |{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t}\right)}_{i\in S\bigcup R^{†}}\in{\mathbb{Z}}_q^{n\times (\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

2） 如果满足：\mathit{W}{\mathit{U}}^{\#}+{\mu }^{\#}\cdot \mathit{G}={\mathit{V}}_f\mathrm{m}\mathrm{o}\mathrm{d}q，其中，\Vert {\mathit{U}}^{\#}\Vert \le {(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。则输出\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}认为{\mu }^{\#}是电路f的正确输出，否则输出\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}。

以上构造的支持门限策略的ABFHS方案满足正确性约束条件。

定理1 所构造的ABFHS方案是正确的。

证 对于门限策略\Gamma =(t,S)，假定

\mathit{W}{\mathit{U}}_{\mathrm{1}}+{\mu }_{\mathrm{1}}\cdot \mathit{G}={\mathit{V}}_{\mathrm{1}}\mathrm{m}\mathrm{o}\mathrm{d}q

\mathit{W}{\mathit{U}}_{\mathrm{2}}+{\mu }_{\mathrm{2}}\cdot \mathit{G}={\mathit{V}}_{\mathrm{2}}\mathrm{m}\mathrm{o}\mathrm{d}q

其中，\Vert {\mathit{U}}_{\mathrm{1}}\Vert \le B和\Vert {\mathit{U}}_{\mathrm{2}}\Vert \le B。

对加法门f({\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}})={\mu }_{\mathrm{1}}+{\mu }_{\mathrm{2}}，可以看出：\mathit{W}{\mathit{U}}^{+}+({\mu }_{\mathrm{1}}+{\mu }_{\mathrm{2}})\cdot \mathit{G}=\mathit{W}({\mathit{U}}_{\mathrm{1}}+{\mathit{U}}_{\mathrm{2}})+({\mu }_{\mathrm{1}}+{\mu }_{\mathrm{2}})\cdot \mathit{G}={\mathit{V}}_{\mathrm{1}}+{\mathit{V}}_{\mathrm{2}}={\mathit{V}}_{+}，且\Vert {\mathit{U}}^{\#}\Vert =\Vert {\mathit{U}}_{\mathrm{1}}+{\mathit{U}}_{\mathrm{2}}\Vert \le \Vert {\mathit{U}}_{\mathrm{1}}\Vert +\Vert {\mathit{U}}_{\mathrm{2}}\Vert \le \mathrm{2}B。

对乘法门f({\mu }_{\mathrm{1}},{\mu }_{\mathrm{2}})={\mu }_{\mathrm{1}}\cdot {\mu }_{\mathrm{2}}，可以看出：

\mathit{W}{\mathit{U}}^{\times }+{\mu }_{\mathrm{1}}{\mu }_{\mathrm{2}}\cdot \mathit{G}=

\mathit{W}({\mathit{U}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})+{\mu }_{\mathrm{1}}\cdot {\mathit{U}}_{\mathrm{2}})+{\mu }_{\mathrm{1}}{\mu }_{\mathrm{2}}\cdot \mathit{G}=

\mathit{W}{\mathit{U}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})+{\mu }_{\mathrm{1}}\cdot \mathit{W}{\mathit{U}}_{\mathrm{2}}+{\mu }_{\mathrm{1}}{\mu }_{\mathrm{2}}\cdot \mathit{G}=

({\mathit{V}}_{\mathrm{1}}-{\mu }_{\mathrm{1}}\cdot \mathit{G}){\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})+{\mu }_{\mathrm{1}}\cdot \mathit{W}{\mathit{U}}_{\mathrm{2}}+{\mu }_{\mathrm{1}}{\mu }_{\mathrm{2}}\cdot \mathit{G}=

{\mathit{V}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})-{\mu }_{\mathrm{1}}{\mathit{V}}_{\mathrm{2}}+{\mu }_{\mathrm{1}}({\mathit{V}}_{\mathrm{2}}-{\mu }_{\mathrm{2}}\cdot \mathit{G})+{\mu }_{\mathrm{1}}{\mu }_{\mathrm{2}}\cdot \mathit{G}=

{\mathit{V}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})={\mathit{V}}_{\times }

且，\Vert {\mathit{U}}^{\times }\Vert =\Vert {\mathit{U}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}})+{\mu }_{\mathrm{1}}\cdot {\mathit{U}}_{\mathrm{2}}\Vert \le

\Vert {\mathit{U}}_{\mathrm{1}}{\mathit{G}}^{-\mathrm{1}}({\mathit{V}}_{\mathrm{2}}) \Vert +\Vert {\mu }_{\mathrm{1}}\cdot {\mathit{U}}_{\mathrm{2}}\Vert \le

m\cdot \Vert {\mathit{U}}_{\mathrm{1}}\Vert +\Vert {\mathit{U}}_{\mathrm{2}}\Vert \le (m+\mathrm{1})B。

因此，对电路f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，有：

\mathit{W}{\mathit{U}}^{\#}+f({\mu }_{\mathrm{1}},\dots ,{\mu }_N)\cdot \mathit{G}={\mathit{V}}_f

并且，如果\Vert {\mathit{U}}_{\mathrm{1}}\Vert ,\dots ,\Vert {\mathit{U}}_N\Vert \le B，有\Vert {\mathit{U}}^{\#}\Vert \le{(m+\mathrm{1})}^{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(f)}B\le {(m+\mathrm{1})}^{d}B。其中电路f的深度\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(f)\le d。

对于i\in [N]，初始签名{\mathit{U}}_i都满足\Vert {\mathit{U}}_i\Vert \le {\beta }_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}=s_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}，所以：

\Vert {\mathit{U}}^{\#}\Vert \le {(m+\mathrm{1})}^{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(f)}{\beta }_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\le {(m+\mathrm{1})}^d{\beta }_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}=

{(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}

因此，所构造的方案是正确的。

3.2　安全性分析

3.2.1　隐私性

定理2 所构造的ABFHS方案是完美隐私的。

证 对于属性集合P_{\mathrm{1}}和P_{\mathrm{2}}、消息\{{\mu }_i{\}}_{i\in [N]}以及门限策略\Gamma =(t,S)，其中\left|P_{\mathrm{1}}\bigcap S\right|\ge t，\left|P_{\mathrm{2}}\bigcap S\right|\ge t，易见，\{{\sigma }_i^{(P_{\mathrm{1}})}{\}}_{i\in [N]}和\{{\sigma }_i^{(P_{\mathrm{2}})}{\}}_{i\in [N]}的分布都为：

D_{{\Lambda }_{{\mathit{V}}_{\mathrm{1}}-{\mu }_{\mathrm{1}}\cdot \mathit{G}}^{\perp }(\mathit{W}),s_{\mathrm{2}}}\times \cdots \times D_{{\Lambda }_{{\mathit{V}}_N-{\mu }_N\cdot \mathit{G}}^{\perp }(\mathit{W}),s_{\mathrm{2}}}

即它们的分布是相同的。因此，所构造的方案是完美隐私的。

3.2.2　不可伪造性

定理3 如果存在多项式时间敌手\mathrm{𝒜}，它能在第2.2节定义的强不可伪造性安全游戏中以概率\epsilon攻破所构造的ABFHS方案，则存在多项式时间算法\mathrm{ℬ}，它能以优势\epsilon -\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )求解\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题。

证 假设存在这样的敌手\mathrm{𝒜}。我们构造算法\mathrm{ℬ}模拟\mathrm{𝒜}的挑战者，并利用\mathrm{𝒜}的伪造求解\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题。

\mathrm{ℬ}输入一个\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题实例\mathit{B}\in {\mathbb{Z}}_q^{n\times \mathrm{2}\mathrm{𝓁}m}，希望找到一个向量\mathit{e}\in {\mathbb{Z}}^{\mathrm{2}\mathrm{𝓁}m}，满足\mathit{e}\cancel{=}\mathrm{0}、\mathit{B}\mathit{e}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q和\Vert \mathit{e}\Vert \le \beta。

初始化：\mathrm{𝒜}向\mathrm{ℬ}宣布目标门限策略{\Gamma }^{\mathrm{*}}=(t,S)和签名询问的消息列表\{{\mu }_i{\}}_{i\in [N]}，其中S\subset \mathrm{𝒰}，\mathrm{1}\le t\le \left|S\right|。

设置： \mathrm{ℬ}构造公开参数\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}和主公钥\mathrm{m}\mathrm{p}\mathrm{k}如下：

① 解析\mathit{B}=\left({\mathit{L}}_{\mathrm{1}}|\cdots |{\mathit{L}}_{\mathrm{2}\mathrm{𝓁}}\right)\in {\mathbb{Z}}_q^{n\times \mathrm{2}\mathrm{𝓁}m}，其中对i\in [\mathrm{2}\mathrm{𝓁}]，{\mathit{L}}_i\in {\mathbb{Z}}_q^{n\times m}。

② 令{\mathrm{𝒰}}^{†}=\{\mathrm{𝓁}+\mathrm{1},\dots ,\mathrm{2}\mathrm{𝓁}\}。

③ 令R^{†}=\{\mathrm{𝓁}+\mathrm{1},\dots ,\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t\}。

④ 对i\in S\bigcup R^{†}，令{\mathit{A}}_i={\mathit{L}}_i。对i\in (\mathrm{𝒰}-S)\bigcup({\mathrm{𝒰}}^{†}-R^{†})，调用\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^n)产生矩阵{\mathit{A}}_i\in {\mathbb{Z}}_q^{n\times m}和{\Lambda }^{\perp }({\mathit{A}}_i)的一组基{\mathit{T}}_{{\mathit{A}}_i}\in {\mathbb{Z}}^{m\times m}。

⑤ 令\mathit{W}={\left(\cdots |{\mathit{A}}_i|\cdots |{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t}\right)}_{i\in S\bigcup R^{†}}\in {\mathbb{Z}}_q^{n\times (\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

⑥ 对i\in [N]，选取抽样{\mathit{U}}_i\leftarrow D_{\mathbb{Z},s_{\mathrm{2}}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m\times m}，并计算{\mathit{V}}_i=\mathit{W}{\mathit{U}}_i+{\mu }_i\cdot \mathit{G}\mathrm{m}\mathrm{o}\mathrm{d}q。

⑦ 令\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s}=(\{{\mathit{V}}_i{\}}_{i\in [N]})，\mathrm{m}\mathrm{p}\mathrm{k}=(\{{\mathit{A}}_i{\}}_{i\in [\mathrm{2}\mathrm{𝓁}]})，并把它们发送给\mathrm{𝒜}。

私钥询问：假设\mathrm{𝒜}询问属性集合P的私钥\mathrm{s}{\mathrm{k}}_P，其中，\mathrm{ℬ}如下产生\mathrm{s}{\mathrm{k}}_P：

① 构造矩阵\mathit{M}={\left(\begin{array}{cccc}\ddots & & & \\ & {\mathit{A}}_i& & \\ & & \ddots & \\ & & & {\mathit{A}}_{\mathrm{2}\mathrm{𝓁}}\end{array}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}

② 随机选择一个\mathrm{𝓁}次多项式\varphi (x)\in {\mathbb{Z}}_q[x]，使得\varphi (\mathrm{0})=\mathrm{0}。

③ 令。令。对i\in [r]，调用\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^n)产生矩阵{\mathit{Z}}_i\in {\mathbb{Z}}_q^{n\times m}和{\Lambda }^{\perp }({\mathit{Z}}_i)的一组基{\mathit{T}}_{{\mathit{Z}}_i}\in {\mathbb{Z}}^{m\times m}。对i\in [\mathrm{𝓁}]\backslash [r]，随机选择\mathrm{𝓁}-r个矩阵{\mathit{Z}}_i\in {\mathbb{Z}}_q^{n\times m}。

④ 构造矩阵\mathit{N}：

\mathit{N}={\left(\begin{array}{ccc}⋮& \ddots & ⋮\\ \varphi (i){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (i){\mathit{Z}}_{\mathrm{𝓁}}\\ ⋮& \ddots & ⋮\\ \varphi (\mathrm{2}\mathrm{𝓁}){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (\mathrm{2}\mathrm{𝓁}){\mathit{Z}}_{\mathrm{𝓁}}\end{array}\right)}_{i\in P\bigcup {\mathrm{𝒰}}^{†}}

⑤ 令\mathit{F}=\left(\mathit{M}|\mathit{N}\right)\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\left|P\right|)n\times (\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}。

⑥ 构造矩阵\overline{\mathit{M}}：

\overline{\mathit{M}}={\left(\begin{array}{cccc}\ddots & & & \\ & {\mathit{A}}_i& & \\ & & \ddots & \\ & & & {\mathit{A}}_{\mathrm{2}\mathrm{𝓁}}\end{array}\right)}_{i\in (P-P\bigcap S)\bigcup ({\mathrm{𝒰}}^{†}-R^{†})}

⑦ 依据P\bigcup {\mathrm{𝒰}}^{†}=((P-P\bigcap S)\bigcup ({\mathrm{𝒰}}^{†}-R^{†}))\bigcup((P\bigcap S)\bigcup R^{†})，构造矩阵\overline{\mathit{N}}：

\overline{\mathit{N}}=\left(\begin{array}{c}{\overline{\mathit{N}}}_{\mathrm{1}}\\ {\overline{\mathit{N}}}_{\mathrm{2}}\end{array}\right)=

\left(\begin{array}{ccc}⋮& \ddots & ⋮\\ \varphi (i){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (i){\mathit{Z}}_r\\ ⋮& \ddots & ⋮\\ \varphi (\mathrm{2}\mathrm{𝓁}){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (\mathrm{2}\mathrm{𝓁}){\mathit{Z}}_r\\ ⋮& \ddots & ⋮\\ \varphi (\mathrm{𝓁}+\mathrm{1}){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (\mathrm{𝓁}+\mathrm{1}){\mathit{Z}}_r\\ ⋮& \ddots & ⋮\\ \varphi (\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t){\mathit{Z}}_{\mathrm{1}}& \cdots & \varphi (\mathrm{2}\mathrm{𝓁}+\mathrm{1}-t){\mathit{Z}}_r\end{array}\right)

其中，i\in ((P-P\bigcap S)\bigcup (U^{+}-R^{+}))\bigcup ((P\bigcap S)\bigcup R^{+})。

⑧ 构造矩阵\overline{\mathit{F}}=\left(\begin{array}{cc}\overline{\mathit{M}}& {\overline{\mathit{N}}}_{\mathrm{1}}\\ \mathrm{0}& {\overline{\mathit{N}}}_{\mathrm{2}}\end{array}\right)\in {\mathbb{Z}}_q^{(\mathrm{𝓁}+\left|P\right|)n\times (\mathrm{𝓁}+\left|P\right|)m}。

因为\varphi (x)\in {\mathbb{Z}}_q[x]是\mathrm{𝓁}次多项式，又，所以矩阵\overline{\mathit{N}}的秩\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\overline{\mathit{N}})\ge \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}({\overline{\mathit{N}}}_{\mathrm{2}})=r\cdot n。所以矩阵\overline{\mathit{F}}的秩\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\overline{\mathit{F}})=(\mathrm{𝓁}+\left|P\right|)\cdot n。{\Lambda }^{\perp }(\overline{\mathit{F}})的一组基如（1）式所示，{\mathit{T}}_{\overline{\mathit{F}}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{𝓁}+\left|P\right|)m}。

{\mathit{T}}_{\overline{\mathit{F}}}=\left(\begin{array}{ccccccc}\ddots & & & & & & \\ & {\mathit{T}}_{{\mathit{A}}_i}& & & & & \\ & & \ddots & & & & \\ & & & {\mathit{T}}_{{\mathit{A}}_{\mathrm{2}\mathrm{𝓁}}}& & & \\ & & & & {\mathit{T}}_{{\mathit{Z}}_{\mathrm{1}}}& & \\ & & & & & \ddots & \\ & & & & & & {\mathit{T}}_{{\mathit{Z}}_r}\end{array}\right)（1）

⑨ 调用\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}(\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}({\mathit{T}}_{\overline{\mathit{F}}},\mathit{F}),s_{\mathrm{1}})产生{\Lambda }^{\perp }(\mathit{F})的一组基{\mathit{T}}_{\mathit{F}}\in {\mathbb{Z}}^{(\mathrm{2}\mathrm{𝓁}+\left|P\right|)m\times (\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}。

⑩ 令\mathrm{s}{\mathrm{k}}_P={\mathit{T}}_{\mathit{F}}，并把它返回给\mathrm{𝒜}。

签名询问： 对i\in [N]，\mathrm{ℬ}令{\sigma }_i={\mathit{U}}_i。于是\{{\sigma }_i={\mathit{U}}_i{\}}_{i\in [N]}为关于消息\{{\mu }_i{\}}_{i\in [N]}和策略{\Gamma }^{\mathrm{*}}=(t,S)的签名集合。\mathrm{ℬ}把\{{\sigma }_i={\mathit{U}}_i{\}}_{i\in [N]}返回给\mathrm{𝒜}。

伪造： 依据引理3，敌手\mathrm{𝒜}在原始游戏和模拟游戏中的视图是统计接近的。具体地，\mathrm{𝒜}在模拟游戏中获胜的优势为\epsilon -\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )。在模拟游戏中\mathrm{𝒜}最后输出(f,{\mu }^{\mathrm{*}},{\sigma }^{\mathrm{*}})，其中f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}，{\mu }^{\mathrm{*}}\in \mathrm{ℳ}，{\sigma }^{\mathrm{*}}={\mathit{U}}^{\mathrm{*}}，并且\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(f)\le d。如果\mathrm{𝒜}获胜，\mathrm{ℬ}能利用\mathrm{𝒜}的伪造给出\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题实例\mathit{B}\in {\mathbb{Z}}_q^{n\times \mathrm{2}\mathrm{𝓁}m}的一个解答。具体如下：

关于策略{\Gamma }^{\mathrm{*}}=(t,S)和消息集合\{{\mu }_i{\}}_{i\in [N]}的签名集合为\{{\sigma }_i={\mathit{U}}_i{\}}_{i\in [N]}。\mathrm{ℬ}依据f:{\mathrm{ℳ}}^N\to \mathrm{ℳ}计算{\mathit{V}}_f\leftarrow \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f)、{\mu }^{\#}=f({\mu }_{\mathrm{1}},\dots ,{\mu }_N)和{\mathit{U}}^{\#}\leftarrow\mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}(\mathrm{p}\mathrm{r}\mathrm{m}\mathrm{s},f,\{({\mu }_i,{\sigma }_i{)\}}_{i\in [N]})。一方面，\mathrm{𝒜}获胜，所以\mathit{W}{\mathit{U}}^{\mathrm{*}}+{\mu }^{\mathrm{*}}\cdot \mathit{G}={\mathit{V}}_f\mathrm{m}\mathrm{o}\mathrm{d}q，并且{\mathit{U}}^{\mathrm{*}}\cancel{=}{\mathit{U}}^{\#}。另一方面，电路f的深度\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(f)\le d，此时，同态计算的签名{\mathit{U}}^{\#}是有效的，所以\mathit{W}{\mathit{U}}^{\#}+{\mu }^{\#}\cdot \mathit{G}={\mathit{V}}_f\mathrm{m}\mathrm{o}\mathrm{d}q。于是有：

\mathit{W}({\mathit{U}}^{\mathrm{*}}-{\mathit{U}}^{\#})+({\mu }^{\mathrm{*}}-{\mu }^{\#})\cdot \mathit{G}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q

令{\mathit{U}}^{\diamond }={\mathit{U}}^{\mathrm{*}}-{\mathit{U}}^{\#}，{\mu }^{\diamond }={\mu }^{\mathrm{*}}-{\mu }^{\#}，则有：

\mathit{W}{\mathit{U}}^{\diamond }+{\mu }^{\diamond }\cdot \mathit{G}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q

其中，{\mathit{U}}^{\mathrm{*}}\cancel{=}{\mathit{U}}^{\#}，故{\mathit{U}}^{\diamond }\cancel{=}\mathrm{0}。因为：

\Vert {\mathit{U}}^{\mathrm{*}}\Vert \le {(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}，

\Vert {\mathit{U}}^{\#}\Vert \le {(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}，

故：\Vert {\mathit{U}}^{\diamond }\Vert \le \mathrm{2}{(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

分两种情况进行讨论。

① {\mu }^{\mathrm{*}}={\mu }^{\#}。

在这种情况下，{\mu }^{\diamond }=\mathrm{0}，故：\mathit{W}{\mathit{U}}^{\diamond }=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q。其中，{\mathit{U}}^{\diamond }\cancel{=}\mathrm{0}，且\Vert {\mathit{U}}^{\diamond }\Vert \le \mathrm{2}{(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

从矩阵{\mathit{U}}^{\diamond }\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m\times m}中适当地选取列向量{\mathit{e}}^{\text{'}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}，其满足：\mathit{W}{\mathit{e}}^{\text{'}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q、{\mathit{e}}^{\text{'}}\cancel{=}\mathrm{0}和\Vert {\mathit{e}}^{\text{'}} \Vert \le \mathrm{2}{(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

② {\mu }^{\mathrm{*}}\ne {\mu }^{\#}。

在这种情况下，{\mu }^{\diamond }\cancel{=}\mathrm{0}，故：\mathit{W}{\mathit{U}}^{\diamond }=-{\mu }^{\diamond }\cdot \mathit{G}\mathrm{m}\mathrm{o}\mathrm{d}q。其中{\mathit{U}}^{\diamond }\cancel{=}\mathrm{0}，且\Vert {\mathit{U}}^{\diamond }\Vert \le \mathrm{2}{(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。

利用{\mathit{U}}^{\diamond }和{\mu }^{\diamond }给出\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题实例\mathit{B}\in {\mathbb{Z}}_q^{n\times \mathrm{2}\mathrm{𝓁}m}的一个解答。随机选择\mathit{x}\in {\{\mathrm{0,1}\}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。令\mathit{y}=\mathit{W}\mathit{x}\in {\mathbb{Z}}_q^n。于是：

\mathit{W}({\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))-\mathit{x})=

\mathit{W}{\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))-\mathit{W}\mathit{x}=

-{\mu }^{\diamond }\cdot \mathit{G}{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))-\mathit{y}=

\mathit{y}-\mathit{y}=\mathrm{0}

令{\mathit{e}}^{\text{'}}={\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))-\mathit{x}，则\mathit{W}{\mathit{e}}^{\text{'}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q，且：

\Vert {\mathit{e}}^{\text{'}}\Vert =\Vert {\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))-\mathit{x}\Vert \le

\Vert {\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))\Vert +\Vert \mathit{x}\Vert \le

\sqrt[]{m}\cdot \Vert {\mathit{U}}^{\diamond }\Vert \cdot \Vert {\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))\Vert +\Vert \mathit{x} \Vert \le

(\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}

还需证明{\mathit{e}}^{\text{'}}\cancel{=}\mathrm{0}，即\mathit{x}\cancel{=}{\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))。利用最小熵证明这一点。因为：

H_{\mathrm{\infty }}(\mathit{x}|{\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond })))=H_{\mathrm{\infty }}(\mathit{x}|\mathit{y})\ge

H_{\mathrm{\infty }}(\mathit{x}|\mathit{W}\mathit{x})\ge (\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m-n\mathrm{l}\mathrm{o}\mathrm{g}q=

O(n\mathrm{l}\mathrm{o}\mathrm{g}q)

其中第一个不等式是由\mathit{y}=\mathit{W}\mathit{x}\in {\mathbb{Z}}_q^n得出的，第二个不等式是由引理1得出的，故：

\mathrm{P}\mathrm{r}[\mathit{x}={\mathit{U}}^{\diamond }{\mathit{G}}^{-\mathrm{1}}(\mathit{y}/(-{\mu }^{\diamond }))]\le

{\mathrm{2}}^{-O(n\mathrm{l}\mathrm{o}\mathrm{g}q)}\le \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )

在以上两种情况下，\mathrm{ℬ}都能得到向量{\mathit{e}}^{\text{'}}\in {\mathbb{Z}}^{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}，并且满足\mathit{W}{\mathit{e}}^{\text{'}}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q、{\mathit{e}}^{\text{'}}\cancel{=}\mathrm{0}和\Vert {\mathit{e}}^{\text{'}}\Vert \le (\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}。通过向{\mathit{e}}^{\text{'}}中添加零分量，可得到向量\mathit{e}\in {\mathbb{Z}}^{\mathrm{2}\mathrm{𝓁}m}，并且满足\mathit{B}\mathit{e}=\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}q、\mathit{e}\cancel{=}\mathrm{0}和\Vert \mathit{e}\Vert \le (\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}\le \beta。即\mathrm{ℬ}利用\mathrm{𝒜}的伪造给出了\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题实例\mathit{B}\in {\mathbb{Z}}_q^{n\times \mathrm{2}\mathrm{𝓁}m}的一个解答。因为\mathrm{𝒜}能以优势\epsilon -\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )赢得模拟游戏，故\mathrm{ℬ}成功求解\mathrm{S}\mathrm{I}{\mathrm{S}}_{q,m,\beta }问题的概率为\epsilon -\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )。

3.3　参数设置

本文提出的ABFHS方案如要满足正确性和安全性，其参数应满足以下几项约束条件：

1) 对于\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}算法，要求m\ge \mathrm{6}n\mathrm{l}\mathrm{o}\mathrm{g}q。

2) 对于\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}和\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}算法，要求

s_{\mathrm{1}}\ge O(\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}q})\cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}((\mathrm{2}\mathrm{𝓁}+\left|P\right|)m)})=

O(\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}q})\cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)})

3) 对于\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{P}\mathrm{r}\mathrm{e}和\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}算法，要求s_{\mathrm{2}}\ge \Vert {\mathit{T}}_{{\mathit{M}}^{″}}\Vert \cdot \omega (\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m})=\Vert {\mathit{Q}}^{″}\cdot {\mathit{T}}_{{\mathit{F}}^{″}}\Vert \cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)})，而\Vert {\mathit{Q}}^{″}\cdot {\mathit{T}}_{{\mathit{F}}^{″}}\Vert \le C^{\mathrm{2}} \cdot \Vert {\mathit{T}}_{{\mathit{F}}^{″}} \Vert \le C^{\mathrm{2}} \cdot \Vert {\mathit{T}}_{\mathit{F}}\Vert \le C^{\mathrm{2}}\cdot s_{\mathrm{1}}\sqrt[]{(\mathrm{2}\mathrm{𝓁}+\left|P\right|)m}\le C^{\mathrm{2}}\cdot s_{\mathrm{1}}\sqrt[]{\mathrm{3}\mathrm{𝓁}m}。故：s_{\mathrm{2}}\ge C^{\mathrm{2}}\cdot s_{\mathrm{1}}\sqrt[]{\mathrm{3}\mathrm{𝓁}m}\cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)})。

4) 对于安全性归约证明，要求\beta \ge (\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}，而(\mathrm{2}m+\mathrm{1})(m+{\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{(\mathrm{𝓁}+\mathrm{1}-t+\left|S\right|)m}\le (\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{\mathrm{3}\mathrm{𝓁}m}。故：\beta \ge (\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d{s}_{\mathrm{2}}\sqrt[]{\mathrm{3}\mathrm{𝓁}m}。

5) 对于\mathrm{S}\mathrm{I}\mathrm{S}问题困难性，要求m=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)、\beta =\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)以及q\ge \beta \cdot \omega (\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}n})。

在这些约束条件下，参数具体设置如下：

C=({(\mathrm{2}\mathrm{𝓁})!)}^{\mathrm{2}},n=\lambda,m=\mathrm{6}n\mathrm{l}\mathrm{o}\mathrm{g}q,

s_{\mathrm{1}}=\sqrt[]{m}\cdot \omega (\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)}),

s_{\mathrm{2}}=\sqrt[]{\mathrm{3}\mathrm{𝓁}}{C}^{\mathrm{2}}m\cdot \omega {(\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)})}^{\mathrm{2}},

\beta =\mathrm{3}\mathrm{𝓁}{C}^{\mathrm{2}}{m}^{\mathrm{3}/\mathrm{2}}(\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d\omega {(\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)})}^{\mathrm{2}},

q=\mathrm{3}\mathrm{𝓁}{C}^{\mathrm{2}}{m}^{\mathrm{2}}(\mathrm{2}m+\mathrm{1}){(m+\mathrm{1})}^d\omega {(\sqrt[]{\mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{𝓁}m)})}^{\mathrm{3}},

其中，d应使得m=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)、\beta =\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)和q\ge \beta \cdot \omega (\sqrt[]{n\mathrm{l}\mathrm{o}\mathrm{g}n})，故选取d=O(\mathrm{l}\mathrm{o}\mathrm{g}\lambda )。

3.4　性能分析

本文首次提出了基于属性的全同态签名方案ABFHS。ABFHS方案和文献[12,13]中的IBFHS方案都是利用GVW的设计技术构造的。ABFHS方案用户的身份由唯一标识符扩展为多个属性的集合使得该方案实现了签名人身份的匿名认证（参见3.2.1节）和签名验证的细粒度访问控制（参见3.1节）。在通信开销和时间开销上，尽管ABFHS方案比文献[12，13]中IBFHS方案的开销大，但处于可接受的范围之内（表2，表3）。

4　 结 语

本文首次提出了一个基于格的支持门限策略的层次型ABFHS方案，并在标准模型下基于SIS问题的困难性证明了它是sP-SU-sCMA安全的。ABFHS方案的通信开销和计算开销虽然比文献[12,13]的IBFHS方案的大了一些，但也在可接受的范围内，且具备匿名认证和细粒度访问控制等优良特性。接下来，我们将致力于构造支持其他访问策略的ABFHS方案，例如支持树形策略的ABFHS方案、支持电路策略的ABFHS方案等，此外，还将致力于探讨ABFHS方案在云计算、无线传感网络等领域的具体应用案例。

参考文献

[1] MAJI H K， PRABHAKARAN M， ROSULEK M. Attribute-based signatures［C］//Cryptographers’ Track at the RSA Conference. Berlin： Springer， 2011： 376-392. DOI： 10.1007/978-3-642-19074-2_24 .

[2] 张健， 黄振杰， 陈群山. 无对的去中心基于属性指定证实者签名［J］. 计算机应用研究， 2020， 37（12）： 3712-3716，3725. DOI： 10.19734/j.issn.1001-3695.2019.08.0566 .

[3] ZHANG J， HUANG Z J， CHEN Q S. Decentralized attribute-based designated confirmer signature without pairings［J］. Application Research of Computers， 2020， 37（12）： 3712-3716，3725. DOI： 10.19734/j.issn.1001-3695.2019.08.0566（Ch ）.

[4] 唐飞， 凌国玮， 单进勇. 基于国产密码算法SM9的可追踪属性签名方案［J］. 电子与信息学报， 2022， 44（10）： 3610-3617. DOI： 10.11999/JEIT210747 .

[5] TANG F， LING G W， SHAN J Y. Traceable attribute signature scheme based on domestic cryptographic SM9 algorithm［J］. Journal of Electronics & Information Technology， 2022， 44（10）： 3610-3617. DOI： 10.11999/JEIT210747（Ch ）.

[6] 黄振杰， 林志伟. 支持一般电路的高效安全基于属性签名［J］. 计算机研究与发展， 2023， 60（2）： 351-361. DOI： 10.7544/issn1000-1239.202110920 .

[7] HUANG Z J， LIN Z W. Efficient and secure attribute-based signatures for general circuits［J］. Journal of Computer Research and Development， 2023， 60（2）： 351-361. DOI： 10.7544/issn1000-1239.202110920（Ch ）.

[8] OBERKO P S K， OBENG V H K S， XIONG H， et al. A survey on attribute-based signatures［J］. Journal of Systems Architecture， 2022， 124： 102396. DOI： 10.1016/j.sysarc.2022.102396 .

[9] GORBUNOV S， VAIKUNTANATHAN V， WICHS D. Leveled fully homomorphic signatures from standard lattices［C］//Proceedings of the 47th Annual ACM Symposium on Theory of Computing. New York： ACM， 2015： 469-477. DOI： 10.1145/2746539.2746576 .

[10] BOYEN X， FAN X， SHI E. Adaptively secure fully homomorphic signatures based on lattices［EB/OL］. ［2015-11-14］.

[11] LUO F C， WANG F Q， WANG K P， et al. A more efficient leveled strongly unforgeable fully homomorphic signature scheme［J］. Information Sciences， 2019， 480： 70-89. DOI： 10.1016/j.ins.2018.12.025 .

[12] LI R N， WANG F Q， ZHANG R J， et al. NTRU-based fully homomorphic signature［J］. Security and Communication Networks， 2022， 2022： 9942717. DOI： 10.1155/2022/9942717 .

[13] JIN X D， WANG F Q， ZHANG R J， et al. Leveled fully homomorphic signcryption from lattices［J］. IEEE Access， 2023， 11： 35232-35242. DOI： 10.1109/ACCESS.2023.3264497 .

[14] 吴华麟， 陈文彬， 高崇志， 等. 同态签名研究综述［J］. 密码学报， 2021， 8（5）： 758-777. DOI： 10.13868/j.cnki.jcr.000475 .

[15] WU H L， CHEN W B， GAO C Z， et al. A survey of homomorphic signature schemes［J］. Journal of Cryptologic Research， 2021， 8（5）： 758-777. DOI： 10.13868/j.cnki.jcr.000475（Ch ）.

[16] WANG F Q， WANG K P， LI B， et al. Leveled strongly unforgeable identity-based fully homomorphic signatures［C］//International Conference on Information Security. Berlin： Springer， 2015： 42-60. DOI： 10.1007/978-3-319-23318-5_3 .

[17] WANG Y K， WANG M Q. A new fully homomorphic signatures from standard lattices［C］//International Conference on Wireless Algorithms， Systems， and Applications. Berlin： Springer， 2020： 494-506. DOI： 10.1007/978-3-030-59016-1_41 .

[18] 李明祥， 安妮. 一种基于身份的全同态签名方案［J］. 武汉大学学报（理学版）， 2016， 62（2）： 141-147. DOI： 10.14188/j.1671-8836.2016.02.007 .

[19] LI M X， AN N. Identity-based （leveled） fully homomorphic signature scheme［J］. Journal of Wuhan University （Natural Science Edition）， 2016， 62（2）： 141-147. DOI： 10.14188/j.1671-8836.2016.02.007（Ch ）.

[20] WANG C F， WU B， YAO H L. Leveled adaptively strong-unforgeable identity-based fully homomorphic signatures［J］. IEEE Access， 2020， 8： 119431-119447. DOI： 10.1109/ACCESS.2020.3003685 .

[21] DODIS Y， OSTROVSKY R， REYZIN L， et al. Fuzzy extractors： How to generate strong keys from biometrics and other noisy data［J］. SIAM Journal on Computing， 2008， 38（1）： 97-139. DOI： 10.1137/060651380 .

[22] MICCIANCIO D， REGEV O. Worst-case to average-case reductions based on Gaussian measures［C］//45th Annual IEEE Symposium on Foundations of Computer Science. New York： IEEE Press， 2004： 372-381. DOI： 10.1109/FOCS.2004.72 .

[23] GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions［C］//Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206. DOI： 10.1145/1374376.1374407 .

[24] ALWEN J， PEIKERT C. Generating shorter bases for hard random lattices［J］. Theory of Computing Systems， 2011， 48（3）： 535-553. DOI： 10.1007/s00224-010-9278-3 .

[25] CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees， or how to delegate a lattice basis［J］. Journal of Cryptology， 2012， 25（4）： 601-639. DOI： 10.1007/s00145-011-9105-2 .

[26] AGRAWAL S， BOYEN X， VAIKUNTANATHAN V， et al. Functional encryption for threshold functions （or fuzzy IBE） from lattices［C］//International Workshop on Public Key Cryptography. Berlin： Springer， 2012： 280-297. DOI： 10.1007/978-3-642-30057-8_17 .

[27] MICCIANCIO D， PEIKERT C. Trapdoors for lattices： Simpler， tighter， faster， smaller［C］//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012： 700-718. DOI： 10.1007/978-3-642-29011-4_41 .

基金资助

国家自然科学基金(61802124)

中央高校基本科研业务费专项资金资助项目(2023MS137)