文章目录
- 一. LSSS简介
- 1.1 概述
- 1.2 线性秘密分享方案（LSSS）与 Shamir的秘密分享方案对比LSSS
- 1.2.1 Shamir的秘密分享方案
- 1.2.2 线性秘密分享方案（LSSS）
- 1.2.3 主要区别
- 二. 基于矩阵的LSSS加解密原理分析
- 2.1 LSSS矩阵构造
- 2.1.1 定义
- 2.1.2 规则 1
- 2.1.3 规则 2
- 2.1.4 规则 3
- 2.1.5 形成线性共享矩阵M
- 2.2 加密过程
- 2.3 解密过程
- 2.4 源码实现，基于C++和eigen库
- 2.4.1 实现方法一，构造访问树求解w
- 2.4.2 实现方法二，直接通过LSSS矩阵求解w
- 三. 基于LSSS进行属性基加密
- 3.1 Setup
- 3.2 KeyGen
- 3.3 Encypt
- 3.4 Decrypt
- 3.5 源码实现，基于C++和pbc库
- 3.6 如何将LSSS矩阵转到双线性映射中 Z p Z_p Zp上计算
- 四. 参考文献
- 五. 感谢支持
一. LSSS简介
1.1 概述
秘密共享体制自从 Shamir 和 Blakley 在 1979 年各自独立提出后（Shamir 提出的方案基于插值法, Blakley 提出的方案基于高斯消元法), 作为现代密码学的重要工具之一,在实际中有很多应用。在信息系统中使用的秘密共享, 可以防止系统密钥的遗失、损坏和来自地方的攻击, 减小秘密保存者的责任。在
(
t
,
n
)
(\mathrm{t}, \mathrm{n})
(t,n) 秘密共享体制中, 秘密分发者将一个秘密信息分成
n
n
n 个秘密份额, 分发给
n
n
n 个人, 当需要恢复秘密信息时, 任意少于
t
t
t个的秘密保存者都得不到该秘密的任何信息。现目前进行秘密共享的主流方案有基于访问控制树和秘密共享矩阵的。基于访问控制树进行秘密分享时, 通过门限控制进行合理的多项式构造, 最终将秘密分享给树的每一个子节点。而LSSS将访问策略转换成矩阵M从而支持更好的计算性能。
基于访问控制树的方案在解密中随着访问控制树的结构变得复杂，和用户私钥绑定的属性个数也越来越多，层层递归解密的计算量还是很大的。目前研究的大多数属性加密方案的访问控制结构都采用了线性秘密共享方案(LSSS)，下面将主要介绍LSSS构造方案。
1.2 线性秘密分享方案（LSSS）与 Shamir的秘密分享方案对比LSSS
LSSS和Shamir的秘密分享方案都是通过分割秘密信息为多个份额，并将它们分配给多个参与者的方法。尽管两者在目的上相似，即保护秘密信息的安全性，但它们在实现上有一些关键的区别：
1.2.1 Shamir的秘密分享方案
- 基于多项式插值，尤其是拉格朗日插值。
- 在Shamir的方案中，秘密被嵌入到一个随机选择的多项式的常数项中。为了分割秘密，这个多项式在不同的点上被计算，产生的值形成分享给参与者的份额。
- 为了重建秘密，任何数量等于或超过门限值（多项式的次数加一）的份额可以被用来重构多项式，并通过多项式的常数项恢复秘密信息。
- 安全性基于多项式的特性，即通过少于门限值的份额无法确定多项式的确切形式。
1.2.2 线性秘密分享方案（LSSS）
- 基于线性代数及矩阵运算。
- 在LSSS中，秘密同样被编码为一个数学结构的一部分，但使用的是矩阵而不是多项式。每个参与者获得的份额对应矩阵中的一行或一组线性方程。
- 秘密的重建通常需要解一个线性方程组，这需要收集足够数量的份额以形成可解的方程组。
- 安全性来源于线性代数的原理，即没有足够的份额就无法解出线性方程组。
1.2.3 主要区别
- 数学基础：Shamir方案基于多项式和插值理论，而LSSS基于线性代数和矩阵运算。
- 分享和重建机制：Shamir使用多项式的值作为份额，LSSS使用矩阵的行作为份额。
- 灵活性：LSSS提供了一定程度上更多的灵活性，在某些复杂的访问控制和安全协议中可能更适用。
二. 基于矩阵的LSSS加解密原理分析
2.1 LSSS矩阵构造
大多数秘密在进行分享时都有一个属性策略, 即满足怎样的条件才能获得秘密值。例如现存在一份会议文件, 只有开发部门的 A 项目组的测试人员可看, 我们可以将其条件分解为一个属性集合[ 开发部门, A \mathrm{A} A 项目组, 测试人员], 只有同时满足这个属性集里面的所有条件才可查看该会议文件, 若用 P a \mathrm{P}_{\mathrm{a}} Pa 表示开发部门, P b \mathrm{P}_{\mathrm{b}} Pb 表示 A \mathrm{A} A 项目组, P c \mathrm{P}_{\mathrm{c}} Pc 表示测试人员, P P P 表示访问策略, 则该访问策略可表示为 P = P a ∧ P b ∧ P c P=P_a \wedge P_b \wedge P_c P=Pa∧Pb∧Pc, 那么如何将一个访问策略 (Access Policy) 变成一个可用于计算的矩阵呢? 接下来将进行讲解:
2.1.1 定义
让每一个属性表示为 M U ∈ Z 1 × 1 M_U \in Z^{1 \times 1} MU∈Z1×1 类型的单条目矩阵, 即 M U = [ 1 ] M_U=[1] MU=[1] 。存在矩阵 M d ∈ M_d \in Md∈列, R b \mathrm{R}_{\mathrm{b}} Rb 表示矩阵 M b \mathrm{M}_{\mathrm{b}} Mb 除去第一列的剩余列。
2.1.2 规则 1
访问策略 P \mathrm{P} P 中的每个变量 a i \mathrm{a}_{\mathrm{i}} ai 都可以用矩阵 M U \mathrm{M}_{\mathrm{U}} MU 表示。
2.1.3 规则 2
对于任意的或结构 (OR-term)
P
=
P
a
∨
P
b
P=P_a \vee P_b
P=Pa∨Pb, 我们可以用矩阵
M
O
R
∈
Z
(
d
a
+
d
b
)
×
(
e
a
+
e
b
−
1
)
M_{O R} \in Z^{\left(d_a+d_b\right) \times\left(e_{a+} e_b-1\right)}
MOR∈Z(da+db)×(ea+eb−1)来表示访问策略P, 形如下:
M
O
R
=
C
a
R
a
0
C
b
0
R
b
。
\mathrm{M}_{\mathrm{OR}}=\begin{array}{ccc} \mathrm{C}_{\mathrm{a}} & \mathrm{R}_{\mathrm{a}} & 0 \\ \mathrm{C}_{\mathrm{b}} & 0 & \mathrm{R}_{\mathrm{b}} \end{array} \text { 。 }
MOR=CaCbRa00Rb 。
2.1.4 规则 3
对于任意的与结构 (AND-term)
P
=
P
a
∧
P
b
P=P_a \wedge P_b
P=Pa∧Pb, 我们可以用矩阵
M
A
N
D
∈
Z
(
d
a
+
d
b
)
×
(
e
a
+
e
b
)
M_{A N D} \in Z^{\left(d_a+d_b\right) \times\left(e_a+e_b\right)}
MAND∈Z(da+db)×(ea+eb)来表示访问策略
P
\mathrm{P}
P, 形如下:
M
A
N
D
=
C
a
C
a
R
a
0
0
C
b
0
R
b
。
\mathrm{M}_{\mathrm{AND}}=\begin{array}{cccc} \mathrm{C}_{\mathrm{a}} & \mathrm{C}_{\mathrm{a}} & \mathrm{R}_{\mathrm{a}} & 0 \\ 0 & \mathrm{C}_{\mathrm{b}} & 0 & \mathrm{R}_{\mathrm{b}} \text { 。 } \end{array}
MAND=Ca0CaCbRa00Rb 。
2.1.5 形成线性共享矩阵M
由访问策略形成的线性秘密共享矩阵 M 的每一行对应一个属性值, 即行向量与属性值形成一一映射的关系
φ
:
{
1
,
⋯
,
d
}
→
P
。
M
\varphi:\{1, \cdots, d\} \rightarrow P 。 M
φ:{1,⋯,d}→P。M 的行规模指
M
M
M 的行数
l
l
l, 反映了由M所决定的实现访问结构的线性秘密共享体制的有效性,
M
M
M 的列规模指
M
M
M 的列数
n
n
n, 反映了秘密重构所需要的计算量。例如访问策略为
P
=
(
a
1
∧
a
2
)
∨
(
a
3
∧
a
4
)
P=\left(a_1 \wedge a_2\right) \vee\left(a_3 \wedge a_4\right)
P=(a1∧a2)∨(a3∧a4), 则形成的秘密共享矩阵
M
M
M 的每一行按序一次表示属性
a
1
,
a
2
,
a
3
,
a
4
a_1, a_2, a_3, a_4
a1,a2,a3,a4 (如下图所示)。只有当所拥有的属性集合满足访问策略时 (即已知对应矩阵的行向量), 用户才能重构秘密
s
s
s, 所以说
M
M
M 的行数
l
l
l反映了由
M
M
M 所决定的实现访问结构的线性秘密共享体制的有效性。我们在构建秘密
s
\mathrm{s}
s 时, 需要用一个包含多个随机数的秘密分享矩阵
ρ
\rho
ρ 对其进行加密, 而解密时, 需要与一个矩阵相乘形成一个行数为
M
M
M 列数
n
n
n 的形如
ε
=
(
1
,
0
,
0
,
,
0
⏟
n
)
T
\varepsilon=(\underbrace{1,0,0,, 0}_n)^T
ε=(n
1,0,0,,0)T 的矩阵以消去加密时的随机数, 获得秘密值
s
s
s, 所以说
M
M
M 的列数
n
n
n 反映了秘密重构所需要的计算量。
假设存在访问策略
P
=
(
a
1
∧
a
2
)
∨
(
a
1
∧
a
3
∧
a
4
)
\mathrm{P}=\left(\mathrm{a}_1 \wedge \mathrm{a}_2\right) \vee\left(\mathrm{a}_1 \wedge \mathrm{a}_3 \wedge \mathrm{a}_4\right)
P=(a1∧a2)∨(a1∧a3∧a4), 用
P
a
\mathrm{P}_{\mathrm{a}}
Pa 代表
a
1
∧
a
2
\mathrm{a}_1 \wedge \mathrm{a}_2
a1∧a2, 用
P
b
\mathrm{P}_{\mathrm{b}}
Pb 代表
a
1
∧
a
3
∧
a
4
a_1 \wedge a_3 \wedge a_4
a1∧a3∧a4, 即
P
a
=
(
a
1
∧
a
2
)
,
P
b
=
(
a
1
∧
a
3
∧
a
4
)
P_a=\left(a_1 \wedge a_2\right), P_b=\left(a_1 \wedge a_3 \wedge a_4\right)
Pa=(a1∧a2),Pb=(a1∧a3∧a4) 。其中
a
1
,
a
2
,
a
3
,
a
4
a_1, a_2, a_3, a_4
a1,a2,a3,a4 都用单条目矩阵 [1]表示。由规则 3 可分别对
P
a
,
P
b
\mathrm{P}_{\mathrm{a}}, \mathrm{P}_{\mathrm{b}}
Pa,Pb 的值进行计算, 计算过程如下:
P
a
=
(
a
1
∧
a
2
)
=
[
1
]
∧
[
1
]
,
P_a=\left(a_1 \wedge a_2\right)=[1] \wedge[1],
Pa=(a1∧a2)=[1]∧[1],
由规则 3 公式：
M
A
N
D
=
C
a
C
a
R
a
0
0
C
b
0
R
b
M_{A N D}=\begin{array}{cccc} C_a & C_a & R_a & 0 \\ 0 & C_b & 0 & R_b \end{array}
MAND=Ca0CaCbRa00Rb
可得：
P
a
=
(
1
1
0
1
)
。
P_a=\left(\begin{array}{ll} 1 & 1 \\ 0 & 1 \end{array}\right) 。
Pa=(1011)。
同理：
P
b
=
(
a
1
∧
a
3
∧
a
4
)
=
(
1
1
1
0
0
1
0
1
0
)
。
P_b=\left(a_1 \wedge a_3 \wedge a_4\right)=\left(\begin{array}{lll} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right) 。
Pb=(a1∧a3∧a4)=
100101110
。
由规则 2 公式：
M
O
R
=
C
a
R
a
0
C
b
0
R
b
M_{O R}=\begin{array}{ccc} C_a & R_a & 0 \\ C_b & 0 & R_b \end{array}
MOR=CaCbRa00Rb
可得, 访问策略矩阵 M 如下
M
=
P
a
∨
P
b
=
(
1
1
0
1
)
∨
(
1
1
1
0
0
1
0
1
0
)
=
(
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
0
1
0
)
。
\mathrm{M}=P_a \vee P_b=\left(\begin{array}{ll} 1 & 1 \\ 0 & 1 \end{array}\right) \vee\left(\begin{array}{lll} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right)=\left(\begin{array}{llll} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right) 。
M=Pa∨Pb=(1011)∨
100101110
=
10100110000010100110
。
其中每一行按序表示 a 1 , a 2 , a 1 , a 3 , a 4 a_1, a_2, a_1, a_3, a_4 a1,a2,a1,a3,a4 。
2.2 加密过程
为了分享秘密值的安全, 分享前通常会对密文进行加密, 这里引入一个秘密分享矩阵
ρ
=
(
s
,
ρ
2
,
⋯
,
ρ
e
)
T
\rho=\left(\mathrm{s}, \rho_2, \cdots, \rho_{\mathrm{e}}\right)^{\mathrm{T}}
ρ=(s,ρ2,⋯,ρe)T, 其中
s
\mathrm{s}
s 表示秘密值,
ρ
i
\rho_{\mathrm{i}}
ρi 是一组随机数, 其取值范围取决于不同的加密策略。通过使用秘密分享矩阵
ρ
\rho
ρ 对矩阵进行计算, 可得出一组加密后的秘密值集合，具体计算形如下:
M
⋅
ρ
=
(
s
1
,
⋯
,
s
d
)
T
。
M \cdot \rho=\left(s_1, \cdots, s_d\right)^T \text { 。 }
M⋅ρ=(s1,⋯,sd)T 。
假设
ρ
=
(
2
,
3
,
1
,
4
)
T
\rho=(2,3,1,4)^{\mathrm{T}}
ρ=(2,3,1,4)T,即想要分享的秘密值
s
=
2
s=2
s=2, 通过表达式
M
⋅
ρ
=
(
s
1
,
⋯
,
s
d
)
T
M \cdot \rho=\left(s_1, \cdots, s_d\right)^T
M⋅ρ=(s1,⋯,sd)T可得
M
⋅
ρ
=
(
5
,
3
,
7
,
4
,
1
)
T
M \cdot \rho=(5,3,7,4,1)^{\mathrm{T}}
M⋅ρ=(5,3,7,4,1)T 。即加密后的秘密值集合为
(
5
,
3
,
7
,
4
,
1
)
T
(5,3,7,4,1)^{\mathrm{T}}
(5,3,7,4,1)T, 计算过程如下:
M
⋅
ρ
=
(
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
0
1
0
)
⋅
(
2
3
1
4
)
=
(
5
3
7
4
1
)
M \cdot \rho=\left(\begin{array}{llll} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right) \cdot\left(\begin{array}{l} 2 \\ 3 \\ 1 \\ 4 \end{array}\right)=\left(\begin{array}{l} 5 \\ 3 \\ 7 \\ 4 \\ 1 \end{array}\right)
M⋅ρ=
10100110000010100110
⋅
2314
=
53741
2.3 解密过程
假设有用户 A A A 拥有属性 a 1 , a 2 a_1, a_2 a1,a2 所对应的秘密值（即已知属性 a 1 , a 2 a_1, a_2 a1,a2 对应的 M M M. ρ \rho ρ 的值), 则他可以按照如下方式进行解密:
2.3.1 求解 λ A \lambda_{\mathrm{A}} λA 的值
取矩阵
a
1
\mathrm{a}_1
a1,
a
2
\mathrm{a}_2
a2 属性值对应的行向量进行转秩, 形成一个新的矩阵
M
A
=
(
1
0
1
1
0
0
0
0
)
\mathrm{M}_{\mathrm{A}}=\left(\begin{array}{ll}1 & 0 \\ 1 & 1 \\ 0 & 0 \\ 0 & 0\end{array}\right)
MA=
11000100
, 通过表达式
M
A
T
w
A
=
ε
=
(
1
,
0
,
.
.
.
.
,
0
)
\mathrm{M}_{\mathrm{A}}^{\mathrm{T}} w_A=\varepsilon=(1,0,....,0)
MATwA=ε=(1,0,....,0) 可得:
M
A
T
w
A
=
(
1
0
1
1
0
0
0
0
)
⋅
w
A
=
(
1
0
0
0
)
M_A^T w_A=\left(\begin{array}{ll} 1 & 0 \\ 1 & 1 \\ 0 & 0 \\ 0 & 0 \end{array}\right) \cdot w_A=\left(\begin{array}{l} 1 \\ 0 \\ 0 \\ 0 \end{array}\right)
MATwA=
11000100
⋅wA=
1000
为方便计算
w
A
w_{\mathrm{A}}
wA, 可将其转化成求解增广矩阵
(
1
0
1
1
1
0
0
0
0
0
0
0
)
\left(\begin{array}{lll}1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{array}\right)
110001001000
的值, 通过高斯消元法求解,容易解得
w
A
=
(
1
,
−
1
)
w_{\mathrm{A}}=(1,-1)
wA=(1,−1) 。
2.3.2 求解秘密值 s \mathrm{s} s
由表达式
S
A
T
⋅
w
A
=
(
M
A
⋅
ρ
)
⋅
w
A
=
ρ
T
⋅
(
M
A
T
⋅
w
A
)
=
ρ
T
⋅
ε
=
s
S_A^T \cdot w_A=\left(M_A \cdot \rho\right) \cdot w_A=\rho^T \cdot\left(M_A^T \cdot w_A\right)=\rho^T \cdot \varepsilon=s
SAT⋅wA=(MA⋅ρ)⋅wA=ρT⋅(MAT⋅wA)=ρT⋅ε=s
可知, 我们现已知
M
⋅
ρ
=
(
5
,
3
)
T
,
w
A
=
(
1
,
−
1
)
M \cdot \rho=(5,3)^T, \quad w_A=(1,-1)
M⋅ρ=(5,3)T,wA=(1,−1), 通过计算可得秘密值
s
s
s, 计算过程如下所示:
s
=
(
M
A
⋅
ρ
)
⋅
w
A
=
(
5
3
)
⋅
(
1
,
−
1
)
=
2
s=\left(M_A \cdot \rho\right) \cdot w_A=\binom{5}{3} \cdot(1,-1)=2
s=(MA⋅ρ)⋅wA=(35)⋅(1,−1)=2
通过解密计算得出的秘密值 s = 2 s=2 s=2 与加密时原假设秘密值 s s s 为 2 符合, 解密完成。
2.4 源码实现，基于C++和eigen库
2.4.1 实现方法一，构造访问树求解w
下面是LSSS结合访问树的算法设计思路，在生成LSSS矩阵的同时将访问策略生成一个策略树，具体步骤如下：
- 对访问策略string进行解析：policies—>Lexer；
- 将访问策略转换成访问矩阵：parse—>parseToken+parseLogic—>andWithTag+orWithTag—>andItem+orItem；
- 在生成策略矩阵的同时生成访问策略树：parseLogic—>createAndNode+createOrNode+TreeNode ;
- 根据访问策略树计算解密向量 w A = ( w 1 , w 2 , . . . , w n ) w_A=(w_1,w_2,...,w_n) wA=(w1,w2,...,wn)：calculateWByTree;
创建c++源码：lsss.cpp
#include <iostream>
#include <vector>
#include <string>
#include <Eigen/Dense>
#include <stdexcept>
using namespace std;
using namespace Eigen;
// 词法分析器类，用于解析访问策略中的单词
class Lexer {
public:
Lexer(const string& str) : text(str), index(0) {} // 初始构造index=0
// 读取下一个token
string readToken() { // 只有'(' ')' 是特殊字符，其他都是普通字符
while (index < text.length())
{
char c = text[index];
if (c == ' ') { // 如果是空格，那么继续向后遍历
index++; // string的索引位置向后+1
continue;
}
else if (c == '(') { // 如果是'('那么就返回
index++; // string的索引位置向后+1
return "(";
}
else if (c == ')') { // 如果是')'那么就返回
index++; // string的索引位置向后+1
return ")";
}
if (isalpha(c) || isdigit(c) || c == '_') { // 如果是字母或者数字，或者下划线那么作为正常处理
size_t start = index; // 记录起始的索引位置
// 读取一个完整的属性名
while (index < text.length() && (isalpha(text[index]) || isdigit(text[index]) || text[index] == '_')) {
index++;
}
return text.substr(start, index - start); // 返回一个完整的关键字，可能是and or，也可能是属性信息
}
throw runtime_error("bad policy(" + text + ") at " + to_string(index)); // 如果是特殊字符（如#$%），那么直接抛出异常，不满足策略基本要求
}
return ""; // 如果没有有效字符，那么返回空字符
}
private:
string text; // 策略policy string
size_t index; // 记录当前解析位置
};
class TreeNode {
public:
TreeNode(TreeNode* left, TreeNode* right, bool isLeaf, bool isAndNode, const string& attr)
: left(left), right(right), isLeaf(isLeaf), isAndNode(isAndNode), attr(attr), index(-1) {}
int initIndex(int base) {
if (isLeaf) {
index = base;
return base + 1;
}
int baseNext = left->initIndex(base);
return right->initIndex(baseNext);
}
// 返回：属性集是否满足策略要求+若满足属性路径为
pair<bool, vector<int>> match(const vector<string>& attrSet) {
if (isLeaf) {
return make_pair(find(attrSet.begin(), attrSet.end(), attr) != attrSet.end(), vector<int>{index});
}
if (isAndNode) {
auto leftMatch = left->match(attrSet);
if (!leftMatch.first) return make_pair(false, vector<int>());
auto rightMatch = right->match(attrSet);
if (!rightMatch.first) return make_pair(false, vector<int>());
leftMatch.second.insert(leftMatch.second.end(), rightMatch.second.begin(), rightMatch.second.end());
return leftMatch;
}
auto leftMatch = left->match(attrSet);
if (leftMatch.first) return leftMatch;
auto rightMatch = right->match(attrSet);
if (rightMatch.first) return rightMatch;
return make_pair(false, vector<int>());
}
bool isLeaf;
bool isAndNode;
string attr;
int index;
private:
TreeNode* left;
TreeNode* right;
};
// 辅助函数构建树节点
TreeNode* createLeafNode(const string& attr) {
return new TreeNode(nullptr, nullptr, true, false, attr);
}
TreeNode* createAndNode(TreeNode* left, TreeNode* right) {
return new TreeNode(left, right, false, true, "");
}
TreeNode* createOrNode(TreeNode* left, TreeNode* right) {
return new TreeNode(left, right, false, false, "");
}
/**
* @brief 执行LSSS矩阵中的OR运算,检查矩阵列数，处理极端情况。将两个矩阵中的第一列（标签列）合并，其他列根据具体情况拼接。
* @param[in] pa 矩阵，代表OR运算的左侧操作数
* @param[in] pb 矩阵，代表OR运算的右侧操作数
* @param[out] MatrixXd 返回合并后的矩阵
*/
MatrixXd orItem(const MatrixXd& pa, const MatrixXd& pb) {
// 有矩阵为空，则直接输出异常
if (pa.cols() == 0 || pa.rows() == 0 || pb.cols() == 0 || pb.rows() == 0) {
throw runtime_error("[orItem]: empty pa or pb!!!");
}
MatrixXd tmp1(pa.rows() + pb.rows(), 1);
tmp1 << pa.col(0), pb.col(0);
MatrixXd result(pa.rows() + pb.rows(), (pa.cols() > 1 ? pa.cols() - 1 : 0) + (pb.cols() > 1 ? pb.cols() - 1 : 0) + 1);
int current_col = 1;
if (pa.cols() > 1) {
MatrixXd tmp2 = MatrixXd::Zero(pa.rows() + pb.rows(), pa.cols() - 1);
tmp2.topRows(pa.rows()) = pa.rightCols(pa.cols() - 1);
result.block(0, current_col, pa.rows() + pb.rows(), pa.cols() - 1) = tmp2;
current_col += pa.cols() - 1;
}
if (pb.cols() > 1) {
MatrixXd tmp3 = MatrixXd::Zero(pa.rows() + pb.rows(), pb.cols() - 1);
tmp3.bottomRows(pb.rows()) = pb.rightCols(pb.cols() - 1);
result.block(0, current_col, pa.rows() + pb.rows(), pb.cols() - 1) = tmp3;
}
result.block(0, 0, pa.rows() + pb.rows(), 1) = tmp1;
return result;
}
/**
* @brief 执行LSSS矩阵中的AND运算,检查矩阵列数
* @param[in] pa 矩阵，代表AND运算的左侧操作数
* @param[in] pb 矩阵，代表AND运算的右侧操作数
* @param[out] MatrixXd 返回合并后的矩阵
*/
MatrixXd andItem(const MatrixXd& pa, const MatrixXd& pb) {
// 有矩阵为空，则直接输出异常
if (pa.cols() == 0 || pa.rows() == 0 || pb.cols() == 0 || pb.rows() == 0) {
throw runtime_error("[andItem]: empty pa or pb!!!");
}
// 调用 orItem 函数进行 OR 运算
MatrixXd oi = orItem(pa, pb);
// 扩展并填充第一列
MatrixXd temp = MatrixXd::Zero(pa.rows() + pb.rows(), 1);
temp.topRows(pa.rows()) = pa.leftCols(1);
// 拼接 temp 和 oi
MatrixXd result(pa.rows() + pb.rows(), temp.cols() + oi.cols());
result << temp, oi;
return result;
}
// 带属性标签的OR运算
MatrixXd orWithTag(const MatrixXd& pa, const MatrixXd& pb) {
MatrixXd tmp0(pa.rows() + pb.rows(), 1);
tmp0 << pa.col(0), pb.col(0);
MatrixXd tmp1 = orItem(pa.rightCols(pa.cols() - 1), pb.rightCols(pb.cols() - 1));
MatrixXd result(tmp0.rows(), tmp0.cols() + tmp1.cols());
result << tmp0, tmp1;
return result;
}
// 带属性标签的AND运算
MatrixXd andWithTag(const MatrixXd& pa, const MatrixXd& pb) {
MatrixXd tmp0(pa.rows() + pb.rows(), 1);
tmp0 << pa.col(0), pb.col(0);
MatrixXd tmp1 = andItem(pa.rightCols(pa.cols() - 1), pb.rightCols(pb.cols() - 1));
MatrixXd result(tmp0.rows(), tmp0.cols() + tmp1.cols());
result << tmp0, tmp1;
return result;
}
// 解析访问策略
pair<MatrixXd, TreeNode*> parse(Lexer& lex, int level);
pair<MatrixXd, TreeNode*> parseToken(Lexer& lex, int level) {
string token = lex.readToken();
if (token.empty() || token == ")") {
throw runtime_error("bad token at parseToken: " + token);
}
if (token == "(") {
return parse(lex, level + 1);
}
if (token == "and" || token == "or") {
throw runtime_error("bad token at parseToken: " + token);
}
// 设置矩阵第一个元素为 token，第二个元素为 1
MatrixXd mat(1, 2);
mat(0, 0) = atof(token.c_str()); // 将 token 转换为浮点数
mat(0, 1) = 1;
return make_pair(mat, createLeafNode(token));
}
/**
* @brief 解析逻辑运算符
* @param[in] lex 策略string形成的类
* @param[in] level 策略层数
* @param[out] pair<MatrixXd, Node*> 矩阵和节点
*/
pair<pair<MatrixXd, TreeNode*>, string> parseLogic(Lexer& lex, pair<MatrixXd, TreeNode*> left, int level) {
string token = lex.readToken();
if (token == ")") {
return make_pair(left, ")");
}
if (token.empty()) {
return make_pair(left, "EOF");
}
if (token == "and") {
auto [right_mat, right_node] = parseToken(lex, level);
MatrixXd mat = andWithTag(left.first, right_mat); // 生成矩阵
TreeNode* node = createAndNode(left.second, right_node); // 生成访问树
return make_pair(make_pair(mat, node), "token");
}
if (token == "or") {
auto [right_mat, right_node] = parseToken(lex, level);
MatrixXd mat = orWithTag(left.first, right_mat);
TreeNode* node = createOrNode(left.second, right_node);
return make_pair(make_pair(mat, node), "token");
}
throw runtime_error("bad token at parseLogic: " + token);
}
/**
* @brief 将Bool类型策略string解析成矩阵
* @param[in] lex 策略string形成的类
* @param[in] level 策略层数
* @param[out] pair<MatrixXd, Node*> 矩阵和节点
*/
pair<MatrixXd, TreeNode*> parse(Lexer& lex, int level) {
auto begin = parseToken(lex, level);
auto next_token = begin;
while (true) {
auto [next, tag] = parseLogic(lex, next_token, level);
next_token = next;
if (tag == ")") {
if (level == 0) {
throw runtime_error("bad ) at parse");
}
return next_token;
}
if (tag == "EOF") {
return next_token;
}
if (next_token.first.size() == 0) {
break;
}
}
return begin;
}
// 根据访问树计算w值
VectorXd calculateWByTree(const MatrixXd& mat, const vector<int>& w_index) {
MatrixXd ret(w_index.size(), mat.cols() - 1);
for (size_t i = 0; i < w_index.size(); ++i) {
ret.row(i) = mat.row(w_index[i]).tail(mat.cols() - 1);
}
MatrixXd filtered = ret.transpose();
MatrixXd a(filtered.rows(), filtered.cols());
int rowCount = 0;
for (int i = 0; i < filtered.rows(); ++i) {
if (!filtered.row(i).isZero()) {
a.row(rowCount++) = filtered.row(i);
}
}
a.conservativeResize(rowCount, NoChange);
VectorXd b = VectorXd::Zero(a.rows());
b(0) = 1;
return a.colPivHouseholderQr().solve(b);
}
// 判断用户属性是否满足策略要求
void judge(const string& policy, const vector<string>& attr_set) {
cout << "policy: " << policy << endl;
cout << "attr_set: ";
for (const auto& attr : attr_set) {
cout << attr << " ";
}
cout << endl;
Lexer lex(policy); // 初始化词法分析器
auto parsed_policy = parse(lex, 0); // 解析策略
MatrixXd mat = parsed_policy.first; // 获取矩阵
TreeNode* tree = parsed_policy.second; // 获取树的根节点
cout << "matrix: " << endl << mat << endl;
tree->initIndex(0); // 初始化节点索引
auto match_result = tree->match(attr_set); // 判断属性集是否满足策略
if (match_result.first) {
cout << "attr_path: ";
for (int i : match_result.second) {
cout << i << " ";
}
cout << endl;
} else {
cout << "not matched" << endl;
cout << endl;
return;
}
VectorXd w = calculateWByTree(mat, match_result.second); // 计算w值
cout << "w_result: " << endl << w << endl << endl;
}
int main() {
// 定义DU策略集合
string s3 = "(1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)";
string s4 = "1111 or 2222 or 3333 or 4444 or 5555";
string s5 = "1111 and 2222 and 3333 and 4444 and 5555 and 6666";
string s6 = "((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666";
vector<string> policies = {s3, s4, s5, s6}; // 定义DU策略集合
// 定义DO属性集合
vector<string> us = {"1111", "2222", "3333", "4444", "5555", "6666"}; // 满足策略集合要求
vector<string> us2 = {"1111", "3333", "4444", "6666"}; // 满足策略集合要求
vector<string> us3 = {"1111"}; // 不满足策略集合要求
vector<vector<string>> all_attr_sets = {us, us2,us3};// 定义DO属性集合
for (const auto& policy : policies) {
for (const auto& attr_set : all_attr_sets) {
judge(policy, attr_set);
}
}
return 0;
}
编译与测试：
g++ lsss.cpp
./a.out
执行结果如下：
policy: (1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)
attr_set: 1111 2222 3333 4444 5555 6666
matrix:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
attr_path: 0 1
w_result:
1
-1
policy: (1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)
attr_set: 1111 3333 4444 6666
matrix:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
attr_path: 2 3 4
w_result:
1
-1
-1
policy: (1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)
attr_set: 1111
matrix:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
not matched
policy: 1111 or 2222 or 3333 or 4444 or 5555
attr_set: 1111 2222 3333 4444 5555 6666
matrix:
1111 1
2222 1
3333 1
4444 1
5555 1
attr_path: 0
w_result:
1
policy: 1111 or 2222 or 3333 or 4444 or 5555
attr_set: 1111 3333 4444 6666
matrix:
1111 1
2222 1
3333 1
4444 1
5555 1
attr_path: 0
w_result:
1
policy: 1111 or 2222 or 3333 or 4444 or 5555
attr_set: 1111
matrix:
1111 1
2222 1
3333 1
4444 1
5555 1
attr_path: 0
w_result:
1
policy: 1111 and 2222 and 3333 and 4444 and 5555 and 6666
attr_set: 1111 2222 3333 4444 5555 6666
matrix:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
attr_path: 0 1 2 3 4 5
w_result:
1
-1
-1
-1
-1
-1
policy: 1111 and 2222 and 3333 and 4444 and 5555 and 6666
attr_set: 1111 3333 4444 6666
matrix:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
not matched
policy: 1111 and 2222 and 3333 and 4444 and 5555 and 6666
attr_set: 1111
matrix:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
not matched
policy: ((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666
attr_set: 1111 2222 3333 4444 5555 6666
matrix:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
attr_path: 0 1 9
w_result:
1
-1
-1
policy: ((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666
attr_set: 1111 3333 4444 6666
matrix:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
attr_path: 2 3 4 9
w_result:
1
-1
-1
-1
policy: ((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666
attr_set: 1111
matrix:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
not matched
上述代码的源代码参考自python代码，感谢作者：LSSS源代码参考python
2.4.2 实现方法二，直接通过LSSS矩阵求解w
通过前面的分析可以发现，解密LSSS的关键就在于如何求解解密向量解密向量
w
A
=
(
w
1
,
w
2
,
.
.
.
,
w
n
)
w_A=(w_1,w_2,...,w_n)
wA=(w1,w2,...,wn)，其实有了LSSS矩阵可以直接求出解密向量，而不需要再构建策略树。核心就是通过 求解线性方程组，可以通过上述构建增广矩阵的办法。
下面给出精简之后的源码，主要是对上面的代码删减与访问树构造部分的代码，并增加秘密
s
s
s恢复的过程代码。
创建c++源码：lsss.cpp
#include <iostream>
#include <vector>
#include <string>
#include <Eigen/Dense>
#include <stdexcept>
#include <unordered_set>
using namespace std;
using namespace Eigen;
// 词法分析器类，用于解析访问策略中的单词
class Lexer {
public:
Lexer(const string& str) : text(str), index(0) {} // 初始构造index=0
// 读取下一个token
string readToken() { // 只有'(' ')' 是特殊字符，其他都是普通字符
while (index < text.length())
{
char c = text[index];
if (c == ' ') { // 如果是空格，那么继续向后遍历
index++; // string的索引位置向后+1
continue;
}
else if (c == '(') { // 如果是'('那么就返回
index++; // string的索引位置向后+1
return "(";
}
else if (c == ')') { // 如果是')'那么就返回
index++; // string的索引位置向后+1
return ")";
}
if (isalpha(c) || isdigit(c) || c == '_') { // 如果是字母或者数字，或者下划线那么作为正常处理
size_t start = index; // 记录起始的索引位置
// 读取一个完整的属性名
while (index < text.length() && (isalpha(text[index]) || isdigit(text[index]) || text[index] == '_')) {
index++;
}
return text.substr(start, index - start); // 返回一个完整的关键字，可能是and or，也可能是属性信息
}
throw runtime_error("bad policy(" + text + ") at " + to_string(index)); // 如果是特殊字符（如#$%），那么直接抛出异常，不满足策略基本要求
}
return ""; // 如果没有有效字符，那么返回空字符
}
private:
string text; // 策略policy string
size_t index; // 记录当前解析位置
};
/**
* @brief 执行LSSS矩阵中的OR运算,检查矩阵列数，处理极端情况。将两个矩阵中的第一列（标签列）合并，其他列根据具体情况拼接。
* @param[in] pa 矩阵，代表OR运算的左侧操作数
* @param[in] pb 矩阵，代表OR运算的右侧操作数
* @param[out] MatrixXd 返回合并后的矩阵
*/
MatrixXd orItem(const MatrixXd& pa, const MatrixXd& pb) {
// 有矩阵为空，则直接输出异常
if (pa.cols() == 0 || pa.rows() == 0 || pb.cols() == 0 || pb.rows() == 0) {
throw runtime_error("[orItem]: empty pa or pb!!!");
}
MatrixXd tmp1(pa.rows() + pb.rows(), 1);
tmp1 << pa.col(0), pb.col(0);
MatrixXd result(pa.rows() + pb.rows(), (pa.cols() > 1 ? pa.cols() - 1 : 0) + (pb.cols() > 1 ? pb.cols() - 1 : 0) + 1);
int current_col = 1;
if (pa.cols() > 1) {
MatrixXd tmp2 = MatrixXd::Zero(pa.rows() + pb.rows(), pa.cols() - 1);
tmp2.topRows(pa.rows()) = pa.rightCols(pa.cols() - 1);
result.block(0, current_col, pa.rows() + pb.rows(), pa.cols() - 1) = tmp2;
current_col += pa.cols() - 1;
}
if (pb.cols() > 1) {
MatrixXd tmp3 = MatrixXd::Zero(pa.rows() + pb.rows(), pb.cols() - 1);
tmp3.bottomRows(pb.rows()) = pb.rightCols(pb.cols() - 1);
result.block(0, current_col, pa.rows() + pb.rows(), pb.cols() - 1) = tmp3;
}
result.block(0, 0, pa.rows() + pb.rows(), 1) = tmp1;
return result;
}
/**
* @brief 执行LSSS矩阵中的AND运算,检查矩阵列数
* @param[in] pa 矩阵，代表AND运算的左侧操作数
* @param[in] pb 矩阵，代表AND运算的右侧操作数
* @param[out] MatrixXd 返回合并后的矩阵
*/
MatrixXd andItem(const MatrixXd& pa, const MatrixXd& pb) {
// 有矩阵为空，则直接输出异常
if (pa.cols() == 0 || pa.rows() == 0 || pb.cols() == 0 || pb.rows() == 0) {
throw runtime_error("[andItem]: empty pa or pb!!!");
}
// 调用 orItem 函数进行 OR 运算
MatrixXd oi = orItem(pa, pb);
// 扩展并填充第一列
MatrixXd temp = MatrixXd::Zero(pa.rows() + pb.rows(), 1);
temp.topRows(pa.rows()) = pa.leftCols(1);
// 拼接 temp 和 oi
MatrixXd result(pa.rows() + pb.rows(), temp.cols() + oi.cols());
result << temp, oi;
return result;
}
// 带属性标签的OR运算
MatrixXd orWithTag(const MatrixXd& pa, const MatrixXd& pb) {
MatrixXd tmp0(pa.rows() + pb.rows(), 1);
tmp0 << pa.col(0), pb.col(0);
MatrixXd tmp1 = orItem(pa.rightCols(pa.cols() - 1), pb.rightCols(pb.cols() - 1));
MatrixXd result(tmp0.rows(), tmp0.cols() + tmp1.cols());
result << tmp0, tmp1;
return result;
}
// 带属性标签的AND运算
MatrixXd andWithTag(const MatrixXd& pa, const MatrixXd& pb) {
MatrixXd tmp0(pa.rows() + pb.rows(), 1);
tmp0 << pa.col(0), pb.col(0);
MatrixXd tmp1 = andItem(pa.rightCols(pa.cols() - 1), pb.rightCols(pb.cols() - 1));
MatrixXd result(tmp0.rows(), tmp0.cols() + tmp1.cols());
result << tmp0, tmp1;
return result;
}
// 解析访问策略
MatrixXd parse(Lexer& lex, int level);
MatrixXd parseToken(Lexer& lex, int level) {
string token = lex.readToken();
if (token.empty() || token == ")") {
throw runtime_error("bad token at parseToken: " + token);
}
if (token == "(") {
return parse(lex, level + 1);
}
if (token == "and" || token == "or") {
throw runtime_error("bad token at parseToken: " + token);
}
// 设置矩阵第一个元素为 token，第二个元素为 1
MatrixXd mat(1, 2);
mat(0, 0) = atoi(token.c_str()); // 将 token 转换为整数
mat(0, 1) = 1; // 设置矩阵第二列元素为1
return mat;
}
/**
* @brief 解析逻辑运算符
* @param[in] lex 策略string形成的类
* @param[in] level 策略层数
* @param[out] MatrixXd 矩阵
*/
pair<MatrixXd, string> parseLogic(Lexer& lex, MatrixXd left, int level) {
string token = lex.readToken();
if (token == ")") {
return make_pair(left, ")");
}
if (token.empty()) {
return make_pair(left, "EOF");
}
if (token == "and") {
auto matrix = parseToken(lex, level); // 解密策略Token生成矩阵
MatrixXd mat = andWithTag(left, matrix); // 生成矩阵
return make_pair(mat, "token");
}
if (token == "or") {
auto matrix = parseToken(lex, level);
MatrixXd mat = orWithTag(left, matrix);
return make_pair(mat, "token");
}
throw runtime_error("bad token at parseLogic: " + token);
}
/**
* @brief 将Bool类型策略string解析成矩阵
* @param[in] lex 策略string形成的类
* @param[in] level 策略层数
* @param[out] MatrixXd 矩阵
*/
MatrixXd parse(Lexer& lex, int level) {
auto begin = parseToken(lex, level);
auto next_token = begin;
while (true) {
auto [next, tag] = parseLogic(lex, next_token, level);
next_token = next;
if (tag == ")") {
if (level == 0) {
throw runtime_error("bad ) at parse");
}
return next_token;
}
if (tag == "EOF") {
return next_token;
}
if (next_token.size() == 0) {
break;
}
}
return begin;
}
/**
* @brief 生成带标签的策略矩阵
* @param[in] policy 策略描述string
* @param[out] 带标签的策略矩阵
*/
MatrixXd generatePolicyMatrixWithTag(const string& policy) {
Lexer lex(policy); // 根据策略初始化词法分析器
MatrixXd PolicyMatrixWithTag = parse(lex, 0); // 解析策略获取带属性标签的策略矩阵
return PolicyMatrixWithTag;
}
/**
* @brief 生成策略矩阵
* @param[in] policy 策略描述string
* @param[out] 策略矩阵
*/
MatrixXd generatePolicyMatrix(const string& policy) {
MatrixXd PolicyMatrixWithTag = generatePolicyMatrixWithTag(policy); // 生成带标签的策略矩阵
// 删除策略矩阵PolicyMatrixWithTag首列的Tag值
MatrixXd PolicyMatrix = PolicyMatrixWithTag.block(0, 1, PolicyMatrixWithTag.rows(), PolicyMatrixWithTag.cols() - 1);
return PolicyMatrix;
}
/**
* @brief 生成带标签的策略子矩阵
* @param[in] PolicyMatrixWithTag 带标签的策略矩阵
* @param[in] attr_set 属性集
* @param[out] 带标签的策略子矩阵
*/
MatrixXd generateSubPolicyMatrixWithTag(const MatrixXd& PolicyMatrixWithTag, const vector<string>& attr_set,vector<int>& rowsToKeep) {
// 将属性集合的字符串转换为整数集合
unordered_set<int> attributeSet;
for (const auto &attr : attr_set) {
attributeSet.insert(stoi(attr)); // 将字符串转为整数并插入集合
}
// 找到与属性集合有交集的行，构建子矩阵Sub_PolicyMatrixWithTag
for (int i = 0; i < PolicyMatrixWithTag.rows(); ++i) {
if (attributeSet.find(static_cast<int>(PolicyMatrixWithTag(i, 0))) != attributeSet.end()) {
rowsToKeep.push_back(i);
}
}
// 创建子矩阵Sub_PolicyMatrixWithTag
MatrixXd Sub_PolicyMatrixWithTag(rowsToKeep.size(), PolicyMatrixWithTag.cols());
for (size_t i = 0; i < rowsToKeep.size(); ++i) {
Sub_PolicyMatrixWithTag.row(i) = PolicyMatrixWithTag.row(rowsToKeep[i]);
}
return Sub_PolicyMatrixWithTag;
}
/**
* @brief 生成策略子矩阵
* @param[in] PolicyMatrixWithTag 策略矩阵
* @param[in] attr_set 属性集
* @param[out] 策略子矩阵
*/
MatrixXd generateSubPolicyMatrix(const MatrixXd& PolicyMatrixWithTag, const vector<string>& attr_set,vector<int>& rowsToKeep) {
// 将属性集合的字符串转换为整数集合
unordered_set<int> attributeSet;
for (const auto &attr : attr_set) {
attributeSet.insert(stoi(attr)); // 将字符串转为整数并插入集合
}
// 找到与属性集合有交集的行，构建子矩阵Sub_PolicyMatrixWithTag
for (int i = 0; i < PolicyMatrixWithTag.rows(); ++i) {
if (attributeSet.find(static_cast<int>(PolicyMatrixWithTag(i, 0))) != attributeSet.end()) {
rowsToKeep.push_back(i);
}
}
// 创建子矩阵Sub_PolicyMatrixWithTag
MatrixXd Sub_PolicyMatrixWithTag(rowsToKeep.size(), PolicyMatrixWithTag.cols());
for (size_t i = 0; i < rowsToKeep.size(); ++i) {
Sub_PolicyMatrixWithTag.row(i) = PolicyMatrixWithTag.row(rowsToKeep[i]);
}
MatrixXd Sub_PolicyMatrix = Sub_PolicyMatrixWithTag.block(0, 1, Sub_PolicyMatrixWithTag.rows(), Sub_PolicyMatrixWithTag.cols() - 1);
return Sub_PolicyMatrix;
}
/**
* @brief 求解线性方程组Ax=b,若有解则根据策略矩阵生成解密向量w={w1,w2,...,wn}
* @param[in] A 策略矩阵A
* @param[in] b e={1,0,....,0}
* @param[in] x 待求向量w={w1,w2,...,wn}
* @param[out] true:方程组有解 false:方程组无解
*/
bool solveLinearSystem(const MatrixXd& A, const VectorXd& b, VectorXd& x) {
// 使用FullPivLU分解求解Ax=b
FullPivLU<MatrixXd> solver(A);
// 检查矩阵A的秩与组合矩阵[A | b]的秩，判断是否有解
if (solver.rank() != FullPivLU<MatrixXd>(A).rank()) {
return false; // 无解
}
// 使用分解求解最小二乘解
x = solver.solve(b);
// 验证Ax是否确实等于b
if (!x.allFinite() || (A * x).isApprox(b, 1e-6) == false) {
return false; // 无解或有多解
}
return true; // 有解并返回解x
}
/**
* @brief 求解解密向量w={w1,w2,...,wn}
* @param[in] A 策略矩阵A
* @param[in] b e={1,0,....,0}
* @param[in] x 待求向量w={w1,w2,...,wn}
* @param[out] true:方程组有解 false:方程组无解
*/
bool calculateWByMatrix(const string& policy,const vector<string>& attr_set,VectorXd& w,vector<int>& rowsToKeep) {
MatrixXd PolicyMatrixWithTag = generatePolicyMatrixWithTag(policy); // 生成带标签的策略矩阵
MatrixXd Sub_PolicyMatrix = generateSubPolicyMatrix(PolicyMatrixWithTag, attr_set,rowsToKeep); // 生成子矩阵
VectorXd e = VectorXd::Zero(Sub_PolicyMatrix.cols()); // 构建目标向量 e = {1, 0, 0, ..., 0}
e(0) = 1;
MatrixXd Sub_PolicyMatrix_t = Sub_PolicyMatrix.transpose(); // 转置矩阵A以便求解 Sub_PolicyMatrix_t x w = e
// 使用函数求解线性方程组 Sub_PolicyMatrix_t x w = e
if (solveLinearSystem(Sub_PolicyMatrix_t, e, w)) {
return true;
} else {
return false;
}
}
/**
* @brief 使用矩阵PolicyMatrix对向量v进行加密计算以生成向量l
* @param[in] PolicyMatrix 策略矩阵
* @param[in] s 向量v的第一个元素
* @return 返回矩阵乘法结果向量l
*/
VectorXd encryptSByMatrix(const MatrixXd& PolicyMatrix, int s) {
// 获取矩阵的列数
int cols = PolicyMatrix.cols();
// 如果策略矩阵没有列，直接返回空向量
if (cols == 0) {
return VectorXd();
}
// 构造向量v
VectorXd v(cols);
v(0) = s;
// 随机生成剩余的元素
for (int i = 1; i < cols; ++i) {
v(i) = rand() % 10; // 使用 % 10 的余数生成0到9之间的随机整数
}
// 打印生成的向量v
cout << "Generated vector v: " << v.transpose() << endl;
// 计算并返回矩阵乘法结果向量l
return PolicyMatrix * v;
}
/**
* @brief 使用解密向量w解密lamda向量获得秘密s
* @param[in] lamda 加密后向量
* @param[in] w 解密向量
* @param[in] rowsToKeep 属性对应的策略矩阵行
* @return s 返回矩阵乘法结果向量l
*/
int decryptSByW(const VectorXd& lamda, const VectorXd& w, const vector<int>& rowsToKeep) {
// 构建子向量sub_lamda
VectorXd sub_lamda(rowsToKeep.size());
for (size_t i = 0; i < rowsToKeep.size(); ++i) {
sub_lamda(i) = lamda(rowsToKeep[i]);
}
// 计算w的转置与sub_lamda的内积
double result = w.transpose() * sub_lamda;
return static_cast<int>(result);
}
// 判断用户属性是否满足策略要求
void test(const string& policy, const vector<string>& attr_set) {
cout << "policy: " << policy << endl;
cout << "attr_set: ";
for (const auto& attr : attr_set) {
cout << attr << " ";
}cout << endl;
/**********************step0：根据策略和属性生成各种矩阵************************/
vector<int> temp1,temp2;
MatrixXd PolicyMatrixWithTag = generatePolicyMatrixWithTag(policy); // 生成带标签的策略矩阵
cout << "PolicyMatrixWithTag: " << endl << PolicyMatrixWithTag << endl;
MatrixXd PolicyMatrix = generatePolicyMatrix(policy); // 生成策略矩阵
cout << "PolicyMatrix: " << endl << PolicyMatrix << endl;
MatrixXd Sub_PolicyMatrixWithTag = generateSubPolicyMatrixWithTag(PolicyMatrixWithTag,attr_set,temp1);// 生成带标签的策略子矩阵
cout << "Sub_PolicyMatrixWithTag:\n" << Sub_PolicyMatrixWithTag << endl;
MatrixXd Sub_PolicyMatrix = generateSubPolicyMatrix(PolicyMatrixWithTag,attr_set,temp2);// 生成策略子矩阵
cout << "Sub_PolicyMatrix:\n" << Sub_PolicyMatrix << endl;
/**********************step1：使用策略矩阵加密s************************/
int s = 11;
VectorXd lamda = encryptSByMatrix(PolicyMatrix, s); // 使用策略矩阵加密s生成lamda加密后向量
cout << "Encrypted vector lamda: " << lamda.transpose() << endl;
/**********************step2：判断是否满足策略要求，若满足输出解密向量w************************/
VectorXd w;
vector<int> rowsToKeep;
bool result = calculateWByMatrix(policy,attr_set,w,rowsToKeep);
cout << "rowsToKeep: ";
for_each(rowsToKeep.begin(), rowsToKeep.end(), [](const auto &i){std::cout << i << " "; });
cout << "\n";
if (!result) { // 属性不满足策略
cout << "The attribute set cannot satisfied the policy!" << endl;
return;
}
cout << "The vector w is: " << w.transpose() << endl;
/**********************step3：满足之后，解密获得s************************/
int decrypt_s = decryptSByW(lamda, w, rowsToKeep);
cout<<"decrypt_s: "<<decrypt_s<<endl;
if(decrypt_s == s)
cout<<"解密成功!"<<endl;
else
cout<<"解密不成功!!!"<<endl;
}
int main() {
// 定义DU策略集合
string policy1 = "(1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)";
string policy2 = "1111 or 2222 or 3333 or 4444 or 5555";
string policy3 = "1111 and 2222 and 3333 and 4444 and 5555 and 6666";
string policy4 = "((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666";
vector<string> policies = {policy1, policy2, policy3, policy4}; // 定义DU策略集合
// 定义DO属性集合
vector<string> attribute1 = {"1111", "2222", "3333", "4444", "5555", "6666"}; // 满足策略集合要求
vector<string> attribute2 = {"1111", "3333", "4444", "6666"}; // 满足策略集合要求
vector<string> attribute3 = {"1111", "2222"};
vector<vector<string>> all_attr_sets = {attribute1, attribute2,attribute3};// 定义DO属性集合
for (const auto& policy : policies) {
for (const auto& attr_set : all_attr_sets) {
test(policy, attr_set); // 对多个策略和属性进行联合测试
cout<<"---------------------------------------------------------------"<<endl;
}
}
return 0;
}
编译与测试：
g++ lsss.cpp
./a.out
执行结果如下：
policy: (1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)
attr_set: 1111 2222 3333 4444 5555 6666
PolicyMatrixWithTag:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
PolicyMatrix:
1 1 0 0 0 0
0 1 0 0 0 0
1 0 1 1 0 0
0 0 0 1 0 0
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 0 1 0
1 0 0 0 0 1
0 0 0 0 0 1
Sub_PolicyMatrixWithTag:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
Sub_PolicyMatrix:
1 1 0 0 0 0
0 1 0 0 0 0
1 0 1 1 0 0
0 0 0 1 0 0
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 0 1 0
1 0 0 0 0 1
0 0 0 0 0 1
Generated vector v: 11 3 6 7 5 3
Encrypted vector lamda: 14 3 24 7 6 16 5 14 3
rowsToKeep: 0 1 2 3 4 5 6 7 8
The vector w is: 1 -1 0 0 0 0 0 0 0
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: (1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)
attr_set: 1111 3333 4444 6666
PolicyMatrixWithTag:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
PolicyMatrix:
1 1 0 0 0 0
0 1 0 0 0 0
1 0 1 1 0 0
0 0 0 1 0 0
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 0 1 0
1 0 0 0 0 1
0 0 0 0 0 1
Sub_PolicyMatrixWithTag:
1111 1 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
1111 1 0 0 0 0 1
Sub_PolicyMatrix:
1 1 0 0 0 0
1 0 1 1 0 0
0 0 0 1 0 0
0 0 1 0 0 0
1 0 0 0 1 0
1 0 0 0 0 1
Generated vector v: 11 5 6 2 9 1
Encrypted vector lamda: 16 5 19 2 6 20 9 12 1
rowsToKeep: 0 2 3 4 5 7
The vector w is: 0 1 -1 -1 0 0
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: (1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)
attr_set: 1111 2222
PolicyMatrixWithTag:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
3333 0 0 0 1 0 0
4444 0 0 1 0 0 0
4444 1 0 0 0 1 0
5555 0 0 0 0 1 0
1111 1 0 0 0 0 1
5555 0 0 0 0 0 1
PolicyMatrix:
1 1 0 0 0 0
0 1 0 0 0 0
1 0 1 1 0 0
0 0 0 1 0 0
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 0 1 0
1 0 0 0 0 1
0 0 0 0 0 1
Sub_PolicyMatrixWithTag:
1111 1 1 0 0 0 0
2222 0 1 0 0 0 0
1111 1 0 1 1 0 0
1111 1 0 0 0 0 1
Sub_PolicyMatrix:
1 1 0 0 0 0
0 1 0 0 0 0
1 0 1 1 0 0
1 0 0 0 0 1
Generated vector v: 11 2 7 0 9 3
Encrypted vector lamda: 13 2 18 0 7 20 9 14 3
rowsToKeep: 0 1 2 7
The vector w is: 1 -1 0 0
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: 1111 or 2222 or 3333 or 4444 or 5555
attr_set: 1111 2222 3333 4444 5555 6666
PolicyMatrixWithTag:
1111 1
2222 1
3333 1
4444 1
5555 1
PolicyMatrix:
1
1
1
1
1
Sub_PolicyMatrixWithTag:
1111 1
2222 1
3333 1
4444 1
5555 1
Sub_PolicyMatrix:
1
1
1
1
1
Generated vector v: 11
Encrypted vector lamda: 11 11 11 11 11
rowsToKeep: 0 1 2 3 4
The vector w is: 1 0 0 0 0
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: 1111 or 2222 or 3333 or 4444 or 5555
attr_set: 1111 3333 4444 6666
PolicyMatrixWithTag:
1111 1
2222 1
3333 1
4444 1
5555 1
PolicyMatrix:
1
1
1
1
1
Sub_PolicyMatrixWithTag:
1111 1
3333 1
4444 1
Sub_PolicyMatrix:
1
1
1
Generated vector v: 11
Encrypted vector lamda: 11 11 11 11 11
rowsToKeep: 0 2 3
The vector w is: 1 0 0
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: 1111 or 2222 or 3333 or 4444 or 5555
attr_set: 1111 2222
PolicyMatrixWithTag:
1111 1
2222 1
3333 1
4444 1
5555 1
PolicyMatrix:
1
1
1
1
1
Sub_PolicyMatrixWithTag:
1111 1
2222 1
Sub_PolicyMatrix:
1
1
Generated vector v: 11
Encrypted vector lamda: 11 11 11 11 11
rowsToKeep: 0 1
The vector w is: 1 0
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: 1111 and 2222 and 3333 and 4444 and 5555 and 6666
attr_set: 1111 2222 3333 4444 5555 6666
PolicyMatrixWithTag:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
PolicyMatrix:
1 1 1 1 1 1
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
Sub_PolicyMatrixWithTag:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
Sub_PolicyMatrix:
1 1 1 1 1 1
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
Generated vector v: 11 6 0 6 2 6
Encrypted vector lamda: 31 6 2 6 0 6
rowsToKeep: 0 1 2 3 4 5
The vector w is: 1 -1 -1 -1 -1 -1
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: 1111 and 2222 and 3333 and 4444 and 5555 and 6666
attr_set: 1111 3333 4444 6666
PolicyMatrixWithTag:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
PolicyMatrix:
1 1 1 1 1 1
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
Sub_PolicyMatrixWithTag:
1111 1 1 1 1 1 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
6666 0 1 0 0 0 0
Sub_PolicyMatrix:
1 1 1 1 1 1
0 0 0 0 1 0
0 0 0 1 0 0
0 1 0 0 0 0
Generated vector v: 11 1 8 7 9 2
Encrypted vector lamda: 38 2 9 7 8 1
rowsToKeep: 0 2 3 5
The attribute set cannot satisfied the policy!
---------------------------------------------------------------
policy: 1111 and 2222 and 3333 and 4444 and 5555 and 6666
attr_set: 1111 2222
PolicyMatrixWithTag:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
3333 0 0 0 0 1 0
4444 0 0 0 1 0 0
5555 0 0 1 0 0 0
6666 0 1 0 0 0 0
PolicyMatrix:
1 1 1 1 1 1
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
Sub_PolicyMatrixWithTag:
1111 1 1 1 1 1 1
2222 0 0 0 0 0 1
Sub_PolicyMatrix:
1 1 1 1 1 1
0 0 0 0 0 1
Generated vector v: 11 0 2 3 7 5
Encrypted vector lamda: 28 5 7 3 2 0
rowsToKeep: 0 1
The attribute set cannot satisfied the policy!
---------------------------------------------------------------
policy: ((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666
attr_set: 1111 2222 3333 4444 5555 6666
PolicyMatrixWithTag:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
PolicyMatrix:
1 1 1 0 0 0 0
0 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
1 1 0 0 0 1 0
0 0 0 0 0 1 0
1 1 0 0 0 0 1
0 0 0 0 0 0 1
0 1 0 0 0 0 0
Sub_PolicyMatrixWithTag:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
Sub_PolicyMatrix:
1 1 1 0 0 0 0
0 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
1 1 0 0 0 1 0
0 0 0 0 0 1 0
1 1 0 0 0 0 1
0 0 0 0 0 0 1
0 1 0 0 0 0 0
Generated vector v: 11 9 2 2 8 9 7
Encrypted vector lamda: 22 2 30 8 2 29 9 27 7 9
rowsToKeep: 0 1 2 3 4 5 6 7 8 9
The vector w is: 1 -1 0 0 0 0 0 0 0 -1
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: ((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666
attr_set: 1111 3333 4444 6666
PolicyMatrixWithTag:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
PolicyMatrix:
1 1 1 0 0 0 0
0 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
1 1 0 0 0 1 0
0 0 0 0 0 1 0
1 1 0 0 0 0 1
0 0 0 0 0 0 1
0 1 0 0 0 0 0
Sub_PolicyMatrixWithTag:
1111 1 1 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
1111 1 1 0 0 0 0 1
6666 0 1 0 0 0 0 0
Sub_PolicyMatrix:
1 1 1 0 0 0 0
1 1 0 1 1 0 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
1 1 0 0 0 1 0
1 1 0 0 0 0 1
0 1 0 0 0 0 0
Generated vector v: 11 3 6 1 2 9 3
Encrypted vector lamda: 20 6 17 2 1 23 9 17 3 3
rowsToKeep: 0 2 3 4 5 7 9
The vector w is: 0 1 -1 -1 0 0 -1
decrypt_s: 11
解密成功!
---------------------------------------------------------------
policy: ((1111 and 2222) or (1111 and 3333 and 4444) or (4444 and 5555) or (1111 and 5555)) and 6666
attr_set: 1111 2222
PolicyMatrixWithTag:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
3333 0 0 0 0 1 0 0
4444 0 0 0 1 0 0 0
4444 1 1 0 0 0 1 0
5555 0 0 0 0 0 1 0
1111 1 1 0 0 0 0 1
5555 0 0 0 0 0 0 1
6666 0 1 0 0 0 0 0
PolicyMatrix:
1 1 1 0 0 0 0
0 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
1 1 0 0 0 1 0
0 0 0 0 0 1 0
1 1 0 0 0 0 1
0 0 0 0 0 0 1
0 1 0 0 0 0 0
Sub_PolicyMatrixWithTag:
1111 1 1 1 0 0 0 0
2222 0 0 1 0 0 0 0
1111 1 1 0 1 1 0 0
1111 1 1 0 0 0 0 1
Sub_PolicyMatrix:
1 1 1 0 0 0 0
0 0 1 0 0 0 0
1 1 0 1 1 0 0
1 1 0 0 0 0 1
Generated vector v: 11 1 9 4 7 8 4
Encrypted vector lamda: 21 9 23 7 4 20 8 16 4 1
rowsToKeep: 0 1 2 7
The attribute set cannot satisfied the policy!
---------------------------------------------------------------
三. 基于LSSS进行属性基加密
在这里我们引用了Brent Waters在2011年的文章 《Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization》，结合该文章里的算法来说明上述LSSS在属性基加密中的应用。
3.1 Setup
Setup ( λ , U ) → ( P K , M K ) \operatorname{Setup}(\lambda, U) \rightarrow(P K, M K) Setup(λ,U)→(PK,MK) : 参数设置算法，由属性授权执行，以安全参数 λ \lambda λ 和系统的属性集合 U U U 为输入，生成系统的公开密钥 P K P K PK 和主密钥 M K M K MK 。
具体来说，算法首先运行群生成函数获得系统参数 ( G , G T , p , e ) \left(G, G_T, p, e\right) (G,GT,p,e) ，其中 p p p 为素数， G G G 和 G T G_T GT是两个 p p p 阶循环群， e e e 是一个双线性映射， g ∈ G g \in G g∈G 为生成元。然后算法随机选择参数 α , a ∈ Z p \alpha, a \in Z_p α,a∈Zp ，另外对于每个属性 i ∈ U i \in U i∈U ，算法随机选择参数 h 1 , h 2 , … , h U ∈ G h_1, h_2, \ldots, h_U \in G h1,h2,…,hU∈G ，最后设置系统的公开密钥为 P K = ( g , e ( g , g ) α , g a , h 1 , … , h U ) P K=\left(g, e(g, g)^\alpha, g^a, h_1, \ldots, h_U\right) PK=(g,e(g,g)α,ga,h1,…,hU) ，主密钥 M K = g α M K=g^\alpha MK=gα 。
3.2 KeyGen
KeyGen ( P K , M K , S ) → S K \operatorname{KeyGen}(P K, M K, S) \rightarrow S K KeyGen(PK,MK,S)→SK : 密钥生成算法，由属性授权执行，其中 S S S 为用户的属性集合，最后生成解密密钥 S K S K SK 。
具体来说，该算法随机选择参数
t
∈
Z
p
t \in Z_p
t∈Zp 并构造用户解密密钥为
S
K
=
(
K
=
g
α
g
a
t
,
L
=
g
t
,
{
K
x
=
h
x
t
}
x
∈
S
)
。
S K=\left(K=g^\alpha g^{a t}, L=g^t,\left\{K_x=h_x^t\right\}_{x \in S}\right) 。
SK=(K=gαgat,L=gt,{Kx=hxt}x∈S)。
3.3 Encypt
Encrypt ( P K , M , ( A , ρ ) ) → C T \operatorname{Encrypt}(P K, M,(A, \rho)) \rightarrow C T Encrypt(PK,M,(A,ρ))→CT ：加密算法，由数据拥有者执行， M M M 为明文数据， ( A , ρ ) (A, \rho) (A,ρ) 为访问策略， C T C T CT 为密文。
具体来说，
A
A
A 表示一个
l
×
n
l \times n
l×n 矩阵，
ρ
\rho
ρ 表示把
A
A
A 的每一行映射到相应属性的映射函数。然后随机选择向量
v
⃗
=
(
s
,
y
2
,
…
,
y
n
)
∈
Z
p
\vec{v}=\left(s, y_2, \ldots, y_n\right) \in Z_p
v=(s,y2,…,yn)∈Zp ，对
A
A
A 的每一行
A
i
A_i
Ai 计算内积
λ
i
=
A
i
⋅
v
⃗
\lambda_i=A_i \cdot \vec{v}
λi=Ai⋅v ，并随机选择参数
r
1
,
r
2
,
…
,
r
l
∈
Z
p
r_1, r_2, \ldots, r_l \in Z_p
r1,r2,…,rl∈Zp ，最后密文表示如下:
C
T
=
(
C
=
M
⋅
e
(
g
,
g
)
α
⋅
s
,
C
′
=
g
s
,
(
C
1
=
g
a
λ
1
h
ρ
(
1
)
−
r
1
,
D
1
=
g
r
1
)
,
…
,
(
C
l
=
g
a
λ
l
h
ρ
(
l
)
−
r
l
,
D
l
=
g
r
l
)
)
\begin{aligned} C T & =\left(C=M \cdot e(g, g)^{\alpha \cdot s}, C^{\prime}=g^s,\left(C_1=g^{a \lambda_1} h_{\rho(1)}^{-r_1}, D_1=g^{r_1}\right), \ldots,\right. \\ \left(C_l\right. & \left.\left.=g^{a \lambda_l} h_{\rho(l)}^{-r_l}, D_l=g^{r_l}\right)\right) \end{aligned}
CT(Cl=(C=M⋅e(g,g)α⋅s,C′=gs,(C1=gaλ1hρ(1)−r1,D1=gr1),…,=gaλlhρ(l)−rl,Dl=grl))
通过上节介绍的计算 λ i = A i ⋅ v ⃗ \lambda_i=A_i \cdot \vec{v} λi=Ai⋅v ，就把秘密值 s s s 分 l l l 份份额进行加密，也就是说，在进行矩阵乘时，矩阵 A A A 的每一行都要乘以向量 v ⃗ \vec{v} v ，所以， v ⃗ \vec{v} v 中的秘密值 s s s 就通过矩阵乘隐藏在乘积结果（结果是一个向量) 的每个元素里。
其中 C 1 = g a λ 1 h ρ ( 1 ) − r 1 C_1=g^{a \lambda_1} h_{\rho(1)}^{-r_1} C1=gaλ1hρ(1)−r1 的 ρ ( 1 ) \rho(1) ρ(1) 对应的便是访问策略中的第一个属性。而在算法初始化阶段公钥 P K P K PK 里面已经给系统里所有的属性都生成了其对应的随机值。这样的话， h ρ ( 1 ) h_{\rho(1)} hρ(1) 其实对应的是访问策略中涉及的第一个属性所对应的随机值。比如说，访问策略中的第一个属性值是 “计算机”，那么 h ρ ( 1 ) h_{\rho(1)} hρ(1) 就是 h h h “计算机”，这个值对应的值就是在公钥 P K P K PK 中 “计算机” 属性对应的那个随机值。
接下来，我们将介绍如何利用LSSS解密的。
3.4 Decrypt
Decrypt ( S K , C T , P K ) → M \operatorname{Decrypt}(S K, C T, P K) \rightarrow M Decrypt(SK,CT,PK)→M : 只有当 S K S K SK 关联的属性集合 S S S 满足密文 C T C T CT 有关的访问策略 ( A , ρ ) (A, \rho) (A,ρ) 时，才能解密成功，并输出明文 M M M 。
令 I ⊂ { 1 , 2 , … , l } I \subset\{1,2, \ldots, l\} I⊂{1,2,…,l} 且定义 I = { i : ρ ( i ) ∈ S } I=\{i: \rho(i) \in S\} I={i:ρ(i)∈S} ，这里 I I I 是系统所有属性的集合的子集。若属性集合 S S S 满足访问策略 ( A , ρ ) (A, \rho) (A,ρ) 且 { λ i } \left\{\lambda_i\right\} {λi} 为关于访问矩阵 A A A 的共享密钥 s s s 的有效份额，那么算法就能在多项式时间内计算出 { w i ∈ Z p } i ∈ I \left\{w_i \in Z_p\right\}_{i \in I} {wi∈Zp}i∈I ，使得 ∑ i ∈ I w i λ i = s \sum_{i \in I} w_i \lambda_i=s ∑i∈Iwiλi=s 。
具体解密的算法如下:
e
(
C
′
,
K
)
/
(
∏
i
∈
I
(
e
(
C
i
,
L
)
⋅
e
(
D
i
,
K
ρ
(
i
)
)
)
w
i
)
e\left(C^{\prime}, K\right) /\left(\prod_{i \in I}\left(e\left(C_i, L\right) \cdot e\left(D_i, K_{\rho(i)}\right)\right)^{w_i}\right)
e(C′,K)/(i∈I∏(e(Ci,L)⋅e(Di,Kρ(i)))wi)
这就是解密公式，我们先不着急对其计算解密，先对其中的个别参数拿出来解释一下。 K ρ ( i ) K_{\rho(i)} Kρ(i) 这个参数，乍一看不知道这个参数来自哪里，其实它来自私钥 S K S K SK 里，我们回头看 S K = ( K = g α g a t , L = g t , { K x = h x t } x ∈ S ) S K=\left(K=g^\alpha g^{a t}, L=g^t,\left\{K_x=h_x^t\right\}_{x \in S}\right) SK=(K=gαgat,L=gt,{Kx=hxt}x∈S) ，其实 K x K_x Kx 的下标 x x x 就对应着属性集合里某一个属性，这个属性也可以用 ρ ( i ) \rho(i) ρ(i) 表示，因为通过上面举的例子，我们知道访问策略矩阵 A A A 的每一行由可以通过映射函数 ρ ( ) \rho() ρ() 将其映射为对应的属性。
然后我们对上面的解密公式逐步计算解密。
-
首先计算 ：
e ( C ′ , K ) = e ( g s , g α g a t ) = e ( g s , g α ) e ( g s , g a t ) = e ( g , g ) α ⋅ s e ( g , g ) s a t e\left(C^{\prime}, K\right)=e\left(g^s, g^\alpha g^{a t}\right)=e\left(g^s, g^\alpha\right) e\left(g^s, g^{a t}\right)=e(g, g)^{\alpha \cdot s} e(g, g)^{s a t} e(C′,K)=e(gs,gαgat)=e(gs,gα)e(gs,gat)=e(g,g)α⋅se(g,g)sat 。 -
再计算
∏ i ∈ I ( e ( C i , L ) ⋅ e ( D i , K ρ ( i ) ) ) w i = ∏ i ∈ I ( e ( g a λ i h ρ ( i ) − r i , g t ) e ( g r i , h ρ ( i ) t ) ) w i = ∏ i ∈ I ( e ( g a λ i , g t ) e ( h ρ ( i ) − r i , g t ) e ( g r i , h ρ ( i ) t ) ) w i = ∏ i ∈ I e ( g , g ) t a λ i w i = e ( g , g ) t a s \begin{aligned} & \prod_{i \in I}\left(e\left(C_i, L\right) \cdot e\left(D_i, K_{\rho(i)}\right)\right)^{w_i}=\prod_{i \in I}\left(e\left(g^{a \lambda_i} h_{\rho(i)}^{-r_i}, g^t\right) e\left(g^{r_i}, h_{\rho(i)}^t\right)\right)^{w_i}= \\ & \prod_{i \in I}\left(e\left(g^{a \lambda_i}, g^t\right) e\left(h_{\rho(i)}^{-r_i}, g^t\right) e\left(g^{r_i}, h_{\rho(i)}^t\right)\right)^{w_i}=\prod_{i \in I} e(g, g)^{t a \lambda_i w_i}=e(g, g)^{t a s} \end{aligned} i∈I∏(e(Ci,L)⋅e(Di,Kρ(i)))wi=i∈I∏(e(gaλihρ(i)−ri,gt)e(gri,hρ(i)t))wi=i∈I∏(e(gaλi,gt)e(hρ(i)−ri,gt)e(gri,hρ(i)t))wi=i∈I∏e(g,g)taλiwi=e(g,g)tas -
最后分子除以分母，消掉 e ( g , g ) t a s e(g, g)^{t a s} e(g,g)tas ，最后计算结果是 e ( g , g ) α ⋅ s e(g, g)^{\alpha \cdot s} e(g,g)α⋅s 。
-
然后再用 C / e ( g , g ) α ⋅ s C / e(g, g)^{\alpha \cdot s} C/e(g,g)α⋅s 就得到明文 M M M 。
在计算过程中我们需要提前计算 { w i ∈ Z p } i ∈ I \left\{w_i \in Z_p\right\}_{i \in I} {wi∈Zp}i∈I ，使得 ∑ i ∈ I w i λ i = s \sum_{i \in I} w_i \lambda_i=s ∑i∈Iwiλi=s ，根据上面举得例子，我们可以知道只有当访问策略满足私钥关联的属性集合时，才能找到这样 { w i } \left\{w_i\right\} {wi} 集合存在。访问策略不满足私钥关联的属性集时，这样的 { w i } \left\{w_i\right\} {wi} 就不存在，算法解密公式就不能计算下去，也就解密不出明文。
3.5 源码实现，基于C++和pbc库
针对上面基于LSSS的属性基加密源码实现如下，这里与上面基于LSSS矩阵访问控制的联系主要是需要上面传入向量 λ \lambda λ和 w w w,使得 ∑ i ∈ I w i λ i = s \sum_{i \in I} w_i \lambda_i=s ∑i∈Iwiλi=s 成立，这里手动构造了两个向量使得上述等式满足，实际应该由上述LSSS矩阵计算并转换（3.6节）之后给出。
创建c++源码：lsss.cpp
#include <pbc/pbc.h> // 包含PBC库头文件
#include <cstring> // 包含cstring头文件
#include <iostream> // 包含标准输入输出流
#include <vector>
#include <algorithm>
using namespace std;
// 定义全局变量和系统参数
#define NUM_ALL_ATTRIBUTES 5 // 定义全部属性数量：加密时使用
#define NUM_CLIENT_ATTRIBUTES 3 // 定义用户所拥有的属性数量：生成密钥和解密时使用
const int ELEMENT_SIZE = 2048; // 假设曲线元素的字节大小
// Step1: Initialization 定义系统参数结构体
struct SystemParams {
element_t g, ga, g_alpha,egg_alpha; // 定义g, ga, g_alpha 和 e(g^alpha, g)用于配对计算
element_t h[NUM_ALL_ATTRIBUTES]; // 定义属性元 h 数组
};
// Step2: 定义密文结构体
struct Ciphertext {
element_t C; // 密文C
element_t C_prime; // 辅助计算元C'
element_t C_i[NUM_ALL_ATTRIBUTES]; // 每个属性的密文对C_i
element_t D_i[NUM_ALL_ATTRIBUTES]; // 每个属性的密文对D_i
};
// Step3: 定义密钥结构体
struct SecretKey {
element_t K, L; // 定义私钥K 和 L
element_t K_rho[NUM_ALL_ATTRIBUTES]; // 定义属性相关的私钥元
};
void print_element(const char *name, element_t element) {
printf("%s: ", name);
element_printf("%B\n", element);
}
// step1: 系统初始化函数
void setup(pairing_t pairing, SystemParams ¶ms) {
element_init_G1(params.g, pairing); // 初始化G1群元素g
element_init_G1(params.ga, pairing); // 初始化G1群元素ga
element_init_G1(params.g_alpha, pairing); // 初始化G1群元素g_alpha
element_init_GT(params.egg_alpha, pairing); // 初始化GT群元素e(g, g)^alpha
element_t alpha, a; // 定义alpha和a
element_init_Zr(alpha, pairing); // 初始化Zr群元素alpha
element_init_Zr(a, pairing); // 初始化Zr群元素a
element_random(alpha); // 生成随机alpha
element_random(a); // 生成随机a
element_random(params.g); // 生成随机G1群元素g
element_pow_zn(params.ga, params.g, a); // 计算g^a
element_pow_zn(params.g_alpha, params.g, alpha); // 计算g^alpha
element_pairing(params.egg_alpha, params.g, params.g); // 计算e(g, g)
element_pow_zn(params.egg_alpha, params.egg_alpha, alpha); // 计算e(g, g)^alpha
// 为每个属性生成随机G1群元素并赋值给h
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
element_init_G1(params.h[i], pairing); // 初始化G1群元素h[i]
element_random(params.h[i]); // 生成随机的h[i]
}
// 清除临时变量alpha和a
element_clear(alpha);
element_clear(a);
}
// step2: 加密函数
void encrypt(pairing_t pairing, SystemParams ¶ms, element_t M, Ciphertext &CT, element_t s, element_t *lambda, int num_attrs) {
element_init_GT(CT.C, pairing); // 初始化GT群元素C
element_pow_zn(CT.C, params.egg_alpha, s); // 计算C = e(g, g)^alpha * s
element_mul(CT.C, CT.C, M); // 计算C = M * C
element_init_G1(CT.C_prime, pairing); // 初始化G1群元素C'
element_pow_zn(CT.C_prime, params.g, s); // 计算C' = g^s
// 为每个属性计算密文对C_i和D_i
for (int i = 0; i < num_attrs; i++) {
element_init_G1(CT.C_i[i], pairing); // 初始化G1群元素C_i[i]
element_pow_zn(CT.C_i[i], params.ga, lambda[i]); // 计算C_i = ga^lambda[i]
element_t tmp_h, h_r;
element_init_G1(tmp_h, pairing); // 初始化临时变量
element_init_G1(h_r, pairing); // 初始化临时变量
element_init_Zr(h_r, pairing); // 初始化临时变量
element_random(h_r); // 生成随机r
element_pow_zn(tmp_h, params.h[i], h_r); // 计算h[attrs[i]]^r
element_invert(tmp_h, tmp_h); // 计算h[attrs[i]]^-r
element_mul(CT.C_i[i], CT.C_i[i], tmp_h); // 计算C_i = C_i * h[attrs[i]]^-r
element_init_G1(CT.D_i[i], pairing); // 初始化G1群元素D_i[i]
element_pow_zn(CT.D_i[i], params.g, h_r); // 计算D_i = g^r
element_clear(tmp_h); // 清除临时变量tmp_h
element_clear(h_r); // 清除临时变量h_r
}
}
// step3: 密钥生成函数
void keygen(pairing_t pairing, SystemParams ¶ms, SecretKey &SK, int *attrs, int num_attrs) {
element_t t, g_at; // 定义t、g_at和g_at_alpha
element_init_Zr(t, pairing); // 初始化Zr群元素t
element_init_G1(g_at, pairing); // 初始化G1群元素g_at
element_init_G1(SK.K, pairing); // 初始化G1群元素K
element_init_G1(SK.L, pairing); // 初始化G1群元素L
element_random(t); // 生成随机t
element_pow_zn(g_at, params.ga, t); // 计算g^{at}
element_mul(SK.K, params.g_alpha, g_at); // 计算K = g_alpha * g^{at}
element_pow_zn(SK.L, params.g, t); // 计算L = g^t
// 首先对全部密钥元素进行初始化
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
element_init_G1(SK.K_rho[i], pairing); // 初始化G1群元素K_rho[attrs[i]]
}
// 为选择的属性生成对应的私钥成分
for (int i = 0; i < num_attrs; i++) {
element_pow_zn(SK.K_rho[attrs[i]], params.h[attrs[i]], t); // 计算K_rho = h_{\rho(i)}^t
}
// 清除临时变量
element_clear(t); // 清除临时变量t
element_clear(g_at); // 清除临时变量g_at
}
// step4: 解密函数
void decrypt(pairing_t pairing, SystemParams ¶ms, SecretKey &SK, Ciphertext &CT, int *attrs, int num_attrs, element_t recovered_M, element_t *omega) {
element_t result, term1, term2; // 定义用于中间计算的变量
element_init_GT(result, pairing); // 初始化GT群元素result
element_init_GT(term1, pairing); // 初始化GT群元素term1
element_init_GT(term2, pairing); // 初始化GT群元素term2
// 计算配对运算
element_pairing(result, CT.C_prime, SK.K); // 计算e(C', K)
element_t product;
element_init_GT(product, pairing); // 初始化GT群元素product
element_set1(product); // 设置初始化值为1
// 对每个属性进行解密运算
for (int i = 0; i < num_attrs; i++) {
element_pairing(term1, CT.C_i[attrs[i]], SK.L); // 计算e(C_i, L)
element_pairing(term2, CT.D_i[attrs[i]], SK.K_rho[attrs[i]]); // 计算e(D_i, K_rho)
element_mul(term1, term1, term2); // 计算e(C_i, L) * e(D_i, K_rho)
element_pow_zn(term1, term1, omega[i]); // 计算(term1)^omega_i
element_mul(product, product, term1); // 计算product = product * term1
}
element_div(result, result, product); // 计算e(C', K) / product
element_div(recovered_M, CT.C, result); // 计算recovered_M = C / result
element_clear(result); // 清除临时变量result
element_clear(term1); // 清除临时变量term1
element_clear(term2); // 清除临时变量term2
element_clear(product); // 清除临时变量product
}
// 将字符串转换为element
void string_to_element(element_t& element, const string& str) {
int len = str.size();
// 确保缓冲区包含固定大小并为字符串文字和填充可能更长的元素而设计
vector<unsigned char> buffer(ELEMENT_SIZE, 0);
memcpy(buffer.data(), str.c_str(), len);
element_from_bytes(element, buffer.data());
}
// 将element转换为字符串
void element_to_string(element_t& element, string& str) {
int length = element_length_in_bytes(element);
vector<unsigned char> buffer(length);
element_to_bytes(buffer.data(), element);
// 从缓冲区中提取原始字符串内容
auto pos = std::find(buffer.begin(), buffer.end(), 0);
str.assign(reinterpret_cast<char*>(buffer.data()), pos != buffer.end() ? pos - buffer.begin() : length);
}
// 主函数
int main() {
// 初始化pairing
pairing_t pairing;
char param[2048];
// 此处应该替换为你的参数文件路径，在安装的文件夹中
FILE *param_file = fopen("/home/hututu/instllpkg/pbc-0.5.14/param/a.param", "r"); // 可以选择其他曲线参数
size_t count = fread(param, 1, 2048, param_file);
fclose(param_file);
if (!count) pbc_die("input error");
pairing_init_set_buf(pairing, param, count);
SystemParams params; // 系统参数
SecretKey SK; // 密钥
Ciphertext CT; // 密文
// 当前曲线最大加密长度为128 bytes，现在输入是140 bytes，但是后面解密智能恢复前面128 bytes
string M_input = "111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee";
element_t M; // 明文
element_t s; // 随机数 s
element_t *lambda = new element_t[NUM_ALL_ATTRIBUTES]; // lambda 数组
element_t *omega = new element_t[NUM_CLIENT_ATTRIBUTES]; // omega数组
element_t recovered_M; // 恢复后的明文
element_init_GT(M, pairing); // 初始化GT群元素M
element_init_GT(recovered_M, pairing); // 初始化GT群元素recovered_M
// 将string转成element
string_to_element(M, M_input);
// 初始化随机数s，作为秘密值
element_init_Zr(s, pairing);
element_random(s);
// 这里直接构造加密后向量lambda={s,l1,l2,....,ln}
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
element_init_Zr(lambda[i], pairing);
if (i == 1) {// 第二个元素是s，要和attrs_client第一个值一致，因为omega第一个取1
element_set(lambda[i], s);
} else {
element_random(lambda[i]); // 随机生成其余元素
}
}
// 这里直接构造解密向量omega={1,0,......,0}
for (int i = 0; i < NUM_CLIENT_ATTRIBUTES; i++) {
element_init_Zr(omega[i], pairing);
if (i == 0) {
element_set1(omega[i]); // 第一个属性权重为1
} else {
element_set0(omega[i]); // 其他属性权重为0
}
}
/*
注意！！！！这里能解密的关键就是omega*lambda=s！！！！,
实际情况应该结合上面的LSSS矩阵运算生成实际的lambda和omega向量，这里是为了
能够解密成功，人为构造的两个向量，要和矩阵访问控制结合起来，就需要根据实际计算生成这两个向量！！！
*/
int attrs_client[NUM_CLIENT_ATTRIBUTES] = {1,4,2}; // 属性数组
/***********************************step1:系统初始化阶段*******************************************/
setup(pairing, params);
// 打印系统参数
cout<<"********************************************step1:系统初始化阶段***************************************************"<<endl;
print_element("g", params.g);
print_element("ga", params.ga);
print_element("g_alpha", params.g_alpha);
print_element("egg_alpha", params.egg_alpha);
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
printf("params.h[%d]", i);
print_element("", params.h[i]);
}
/***********************************step2:加密阶段*******************************************/
encrypt(pairing, params, M, CT, s, lambda, NUM_ALL_ATTRIBUTES);
// 打印系统参数
cout<<"********************************************step2:加密阶段***************************************************"<<endl;
print_element("M", M);
print_element("CT.C", CT.C);
print_element("CT.C_prime", CT.C_prime);
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
printf("CT.C_i[%d]", i);
print_element("", CT.C_i[i]);
printf("CT.D_i[%d]", i);
print_element("", CT.D_i[i]);
}
/***********************************step3:密钥生成阶段*******************************************/
keygen(pairing, params, SK, attrs_client, NUM_CLIENT_ATTRIBUTES);
cout<<"********************************************step3:密钥生成阶段***************************************************"<<endl;
print_element("SK.K", SK.K);
print_element("SK.L", SK.L);
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
printf("SK.K_rho[%d]", i);
print_element("", SK.K_rho[i]);
}
/***********************************step4:解密阶段*******************************************/
decrypt(pairing, params, SK, CT, attrs_client, NUM_CLIENT_ATTRIBUTES, recovered_M, omega);
cout<<"********************************************step4:解密阶段***************************************************"<<endl;
print_element("recovered_M", recovered_M);
// 验证解密结果是否正确
if (element_cmp(M, recovered_M) == 0) {
cout << "Decryption successful!" << endl; // 解密成功
string output;
element_to_string(recovered_M, output); // 将element转成string
cout << "解密明文为: " << output; // 解密成功
cout<<",长度为"<<output.size()<<endl;
} else {
cout << "Decryption failed." << endl; // 解密失败
}
// 清除元素
element_clear(M); // 清除明文元素M
element_clear(recovered_M); // 清除恢复的明文元素recovered_M
element_clear(s); // 清除随机数s
delete[] lambda; // 释放lambda数组
delete[] omega; //释放omega数组
// 清除系统参数
element_clear(params.g); // 清除系统参数g
element_clear(params.ga); // 清除系统参数ga
element_clear(params.g_alpha); // 清除系统参数g_alpha
element_clear(params.egg_alpha); // 清除系统参数egg_alpha
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
element_clear(params.h[i]); // 清除每个属性的公钥元素h[i]
}
// 清除私钥
element_clear(SK.K); // 清除私钥K
element_clear(SK.L); // 清除私钥L
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
element_clear(SK.K_rho[i]); // 清除所有私钥元素K_rho[i]
}
// 清除密文
element_clear(CT.C); // 清除密文C
element_clear(CT.C_prime); // 清除密文C_prime
for (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {
element_clear(CT.C_i[i]); // 清除密文中的C_i部分
element_clear(CT.D_i[i]); // 清除密文中的D_i部分
}
pairing_clear(pairing); // 清除配对参数
return 0; // 返回0表示程序成功执行
}
编译与测试：
g++ lsss.cpp -lgmp -lpbc -L/usr/local/lib/pbc
./a.out
执行结果如下：
********************************************step1:系统初始化阶段***************************************************
g: [12051990801929539122095229710661104485849325232122319082458099521979977075177152909386499554650838780785640245848980146821311703458385803846069709668765, 3052565691220450717439503064456871236152185785944211523740771470011259956280094009764230828407616599945781019459010337648345591986814429902800951417839293]
ga: [206711205966324777714380993816326153102469808970027069683306908859797099934049494051932254571662806801383094809553784551548295612643134010601645340348677, 6509951986871117010561879018790325429217543447362158399770727893243984831021009488973994363650347249679505696732878390197087205061958474471712525095600190]
g_alpha: [5000486429837963444726400343961923359742047039575676716973227516935480163155948411841522093996281523236297528160077423550832282924894804055695311842180401, 3745919815266598166569656993757913866733496995889838365013167422421425555641432967650448059757207375245879641129431235643378803497464481326492181325681447]
egg_alpha: [7564591056095140916572726499246243677238139587375586806946925561877139021660808689593098086424988850231362774600010621407594647571053651752427465135278419, 7857561419780861561888692195456579050640872936635001269745896776912585487542728249775679012965880402892663294378349096707564754837389294042555765505079132]
params.h[0]: [8504411958848359892125362014829831613151643147078889409716027896908706877392228789565250900252692543264360308239127529761665029418534135298418358693210389, 2114613680003096482207359965178083765547438927069844636168527177465216200800135859467719289635557538428978437192570925170316472279268086518726379566108931]
params.h[1]: [8030882040276376789027931932267181610074718597096474126194678304400026155793310845956963472723763355949644740969779800064153003350303329216627851861722446, 792245186515755073903598694895781437324653006671349645744904150899508850067751847315636783489162154202452525640829840581084738570708753908475875603585566]
params.h[2]: [3653504674225048744089116970814050439550488076900000267299585914247409781402505685306421363672465992809620254058297373467460620577120738075071403552866701, 2425949351192013269140264711772090986076712803599816006470500971377157471625510685900682327767273704536649603136639865408868710057396352651465585347685060]
params.h[3]: [1413665581803168416651656362315319862024587668770226792111323401994907370126884090275821891157756597882097781377248405843702091788115099659720681385605109, 7697690316440578976518812302542328509651638783742744460853412462526058396930729138497667327382499481450362449901164654012212914963057775876968450288407878]
params.h[4]: [8136908194633005597269092386085607074353229031582076693898754120785865438623712445804890334157158731514223517479308847308507865379522461344313508582620241, 7639557929125674046437670841619161664694404183618564524176031136572361561578370634126365049431602305026837629199223167263009294341411459671355873940946369]
********************************************step2:加密阶段***************************************************
M: [2576402308106616697565204847069667595018621033422326219902954057937886989286430828444039621615291477076235724243708447649955459199989603932268809602676535, 2891880141752325051414407883679273396281919983870757622173523034323829759724168439911981196813500510373302996519505297135919943750047738982924216283980900]
CT.C: [5528174613379119928259857158531440368212813659917857286745597056019434210219630646617638996323832584122233096483699854263290191274613528337035443976861005, 1172704294569606352395332564575983871256611616245017338849350420867000374855799133715824974064315457583956407324319937037657507087783108662004507253949605]
CT.C_prime: [2915329437079037796051005135343852977334731951958396156665810246675671580220498886293389768494879364330128814574337282188015912902287447164362390323744718, 7053635110943258036078058150657650998759555459621734974272632578054751045429196032325950913795843235265165753152924861324527909408534984156419663395702148]
CT.C_i[0]: [3336434868311398459266702272765816812290038852789850576669890778037345683444541164791721833843462347564392077021345894939603038743921409933742668238951587, 6196625040006486662940337206394134387802641668561149094403548952979547011252970282377441095072679027841168486363119982050738336901926301601454718543151825]
CT.D_i[0]: [1570600233968185104408501608863081572541345968120297054605904666882733911590904223960873811112083038856005457847310244366712912904203701158112720967973513, 7786079395362184296092923918369821274699499195241121771670523123707743211002708497650078521435775476976907134876669195816240413991728967524672922714668366]
CT.C_i[1]: [2628310630964099320254884721288860620666646026202594798227989447369800672544079104399367859881364081957645451448473632917145752749929870795694310794518909, 6907764277091643576659295568598695362038810305795312626903810891765256749621273795888646513297306226519355062083587894291074268990235447131402643751710396]
CT.D_i[1]: [6102247060899749935263992826825734281995018150456247519329687152249792554548964599019968575809461210154768884771608006841977021085060139620937934735430443, 3982190614199606731547105116307467235035400576437833348817268772550106200625929240854912565140527755989624537650281662670128714385386075976035933020540076]
CT.C_i[2]: [3682737485725457965986078108429646995841972149537584191622793675993933199422462676451483656571731039115860896641256361996960632707318052216050177195528251, 878864611673047224158221107346840288170112542551389268579639090019343936269676007342626464939510704613793357842414572153999072271960000556134432926340456]
CT.D_i[2]: [8636075101800639261146243155732675529584041002683476593889219108503578883469663169096714818223324064032181728882890939600398241812775546354006500893661988, 8472709668247630827824144347467682728213829540942995196225251412725141873636424366279165372922735874982126620940895789797655307046582096892852498056057559]
CT.C_i[3]: [4319136302768866762501690024387831692701360591710836011221395414854377474113143528149383103351435956661971157395915790847278688810429695459776906110330886, 5302387923293144512109670548089575176090622483801731147835106154160256553178197554714887189294628148231577309562036139826803948187811306663678720674014909]
CT.D_i[3]: [2116157425583308349949317527018747785836342232819662039023269812575226072576600924221447102078862348153276676381955854464349005520907213154855719868135184, 6025174342542636526778624576247657820373910211689316015287988972570695011950388697959035284471328276691669960972139034776188019784836097365588261075059858]
CT.C_i[4]: [3327339892132393371455939478158952217781516012327226892851187614612558529820826764786865187203476021682698754161823525152803581164339353281259397752141542, 8717174631088751972206357242874484261703242781096369196155681343547736071500927462177352800698676077547605219033173524825738310987356177118064544503434479]
CT.D_i[4]: [7777838935912295863603816902919969010883547984807346803202470279459811924138481860907804461597787090073176001760176096802388133169528936598603243468199584, 3678219518992894847060214948728162538413728479273588116168800803581350055634424583514315653159211020446250952139797904240152901159950235225184422300518197]
********************************************step3:密钥生成阶段***************************************************
SK.K: [4340941831853607903310521468898702475868903847021721762875714461417382224356837469794312058128377792577945563819632115315157284583206777600957437136864478, 2524721753370929417120961663619374126592449155512326010812977645145820068408710887282239847160609022843307558016229228936782537007104498729826038762101868]
SK.L: [5393921388816243440573860690526570859826801810605836751931497706694039594314138675412936064312918862175376874052216268987094366301032284160499955205165364, 3584197703448462586457332110386708207262277843566147141022416817513486008724846017102729227860827218576051643140538911080182426839972007063995312296661399]
SK.K_rho[0]: O
SK.K_rho[1]: [8704872917858900294731537655204416151746207942193982363865672293236599228504785104656925321979806326182247672090800201294707646699156325977230273257080457, 6074037635873387719029053493099255377369965136603465903503973977169012822671097791586610720591332872157939907447159437809580861067403842764827982270652021]
SK.K_rho[2]: [479291789084451248119189409959394468673445107897176829289854574030654929027920680758676895129930010519098737766499557607781640509123075008795131394822367, 4490671727127796284090736642824409158080345907809319076691577967506974799735243724003387511724259310659437249195062248222771816528462043748475886676727161]
SK.K_rho[3]: O
SK.K_rho[4]: [4695338820583936645244222281709413839075943581958271707457930315148455087234023562704418837518461600162882152399427888522142351609290544653769078713141561, 1968351624356745833059943314725537546880951369453644187202952485384180137416176704531919388070769482085537450470984442722764989678728351685650785749754491]
********************************************step4:解密阶段***************************************************
recovered_M: [2576402308106616697565204847069667595018621033422326219902954057937886989286430828444039621615291477076235724243708447649955459199989603932268809602676535, 2891880141752325051414407883679273396281919983870757622173523034323829759724168439911981196813500510373302996519505297135919943750047738982924216283980900]
Decryption successful!
解密明文为: 111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999aaaaaaaaaabbbbbbbbbbccccccccccdddddddd,长度为128
3.6 如何将LSSS矩阵转到双线性映射中 Z p Z_p Zp上计算
在第二章中主要给出了基于矩阵的LSSS计算实现访问控制。第三章主要给出了基于LSSS 的属性基加密机制，这里主要需要第二章传入向量 λ \lambda λ和 w w w,使得 ∑ i ∈ I w i λ i = s \sum_{i \in I} w_i \lambda_i=s ∑i∈Iwiλi=s 成立。上述代码中是手动构造假的向量，实际应该真实计算得出并传入，但存在一个主要问题就是矩阵运算得结果都是通用数字，而双线性运算都是在 Z p Z_p Zp群上的运算，因此需要把 λ \lambda λ和 w w w转成 Z p Z_p Zp群中元素进行运算，下面是基础代码demo:
#include <stdio.h>
#include <pbc/pbc.h>
int main() {
// 初始化pairing
pairing_t pairing;
char param[1024];
FILE *param_file = fopen("/home/hututu/instllpkg/pbc-0.5.14/param/a.param", "r");
size_t count = fread(param, 1, 1024, param_file);
fclose(param_file);
if (!count) pbc_die("input error");
pairing_init_set_buf(pairing, param, count);
// 定义向量omega和lambda及整数s
int omega[3] = {1, 2, 3};
int lambda[3] = {4, 5, 6};
int s = 32; // 1*4 + 2*5 + 3*6 = 32
// 初始化并将向量元素映射到Z_p上
element_t omega_zp[3], lambda_zp[3], s_zp, inner_product;
for (int i = 0; i < 3; i++) {
element_init_Zr(omega_zp[i], pairing);
element_init_Zr(lambda_zp[i], pairing);
element_set_si(omega_zp[i], omega[i]); // 将整数omega[i]映射到Z_p上
element_set_si(lambda_zp[i], lambda[i]); // 将整数lambda[i]映射到Z_p上
}
element_init_Zr(s_zp, pairing);
element_init_Zr(inner_product, pairing);
element_set_si(s_zp, s); // 将整数c映射到Z_p上
// 计算向量内积并映射到Z_p上
element_set0(inner_product);
for (int i = 0; i < 3; i++) {
element_t temp;
element_init_Zr(temp, pairing);
element_mul(temp, omega_zp[i], lambda_zp[i]); // 计算omega[i] * lambda[i]
element_add(inner_product, inner_product, temp); // 求和
element_clear(temp);
}
// 打印结果
element_printf("Inner product in Z_p = %B\n", inner_product);
element_printf("s in Z_p = %B\n", s_zp);
// 检查内积是否等于s
if (element_cmp(inner_product, s_zp) == 0) {
printf("The equation omega * lambda = s holds in Z_p.\n");
} else {
printf("The equation omega * lambda = s does not hold in Z_p.\n");
}
// 清理
for (int i = 0; i < 3; i++) {
element_clear(omega_zp[i]);
element_clear(lambda_zp[i]);
}
element_clear(s_zp);
element_clear(inner_product);
pairing_clear(pairing);
return 0;
}
编译：
g++ test.cpp -lgmp -lpbc -L/usr/local/lib/pbc
执行：./a.out
结果：
Inner product in Z_p = 32
s in Z_p = 32
The equation omega * lambda = s holds in Z_p.
四. 参考文献
- 线性秘密共享方案（LSSS）构造与解密
- 属性加密访问结构(二)—线性秘密共享方案(LSSS)
- 属性加密访问结构(一)—访问控制树(超详细)
- LSSS源码实现
- Waters B. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[C]//International workshop on public key cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011: 53-70.
五. 感谢支持
完结撒花！密码学实属复杂深奥的问题，不仅在原理上难以理解，在代码实现上更是难的一批，写这篇文章花了我很大精力，遇到了无数问题，个个都让人头大。也感谢开源小伙伴提供的代码，分析和思考，给了我很大帮助。希望看到这里的小伙伴能点个关注，我后续会持续更新更多关于密码学原理分析和实现，也欢迎大家广泛交流。
码字实属不易，如果本文对你有10分帮助，就赏个10分把，感谢各位大佬支持！
