LSSS算法实现，基于eigen和pbc密码库【一文搞懂LSSS，原理+代码】

本文主要是介绍LSSS算法实现，基于eigen和pbc密码库【一文搞懂LSSS，原理+代码】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一. LSSS简介

1.1 概述

    秘密共享体制自从 Shamir 和 Blakley 在 1979 年各自独立提出后（Shamir 提出的方案基于插值法, Blakley 提出的方案基于高斯消元法), 作为现代密码学的重要工具之一,在实际中有很多应用。在信息系统中使用的秘密共享, 可以防止系统密钥的遗失、损坏和来自地方的攻击, 减小秘密保存者的责任。在 $(\mathrm{t},\mathrm{n})$ 秘密共享体制中, 秘密分发者将一个秘密信息分成 $n$ 个秘密份额, 分发给 $n$ 个人, 当需要恢复秘密信息时, 任意少于 $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 项目组的测试人员可看, 我们可以将其条件分解为一个属性集合[ 开发部门, $\mathrm{A}$ 项目组, 测试人员], 只有同时满足这个属性集里面的所有条件才可查看该会议文件, 若用 ${\mathrm{P}}_{\mathrm{a}}$ 表示开发部门, ${\mathrm{P}}_{\mathrm{b}}$ 表示 $\mathrm{A}$ 项目组, ${\mathrm{P}}_{\mathrm{c}}$ 表示测试人员, $P$ 表示访问策略, 则该访问策略可表示为 $P=P_a\wedge P_b\wedge P_c$, 那么如何将一个访问策略 (Access Policy) 变成一个可用于计算的矩阵呢? 接下来将进行讲解:

2.1.1 定义

   让每一个属性表示为 $M_U\in Z^{1\times 1}$ 类型的单条目矩阵, 即 $M_U=[1]$ 。存在矩阵 $M_d\in$列, ${\mathrm{R}}_{\mathrm{b}}$ 表示矩阵 ${\mathrm{M}}_{\mathrm{b}}$ 除去第一列的剩余列。

2.1.2 规则 1

   访问策略 $\mathrm{P}$ 中的每个变量 ${\mathrm{a}}_{\mathrm{i}}$ 都可以用矩阵 ${\mathrm{M}}_{\mathrm{U}}$ 表示。

2.1.3 规则 2

   对于任意的或结构 (OR-term) $P=P_a\vee P_b$, 我们可以用矩阵 $M_{OR}\in Z^{\left(d_a+d_b\right)\times \left(e_{a+}{e}_b-1\right)}$来表示访问策略P, 形如下:
$${\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{ 。 }$$

2.1.4 规则 3

   对于任意的与结构 (AND-term) $P=P_a\wedge P_b$, 我们可以用矩阵 $M_{AND}\in Z^{\left(d_a+d_b\right)\times \left(e_a+e_b\right)}$来表示访问策略 $\mathrm{P}$, 形如下:
$${\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}$$

2.1.5 形成线性共享矩阵M

   由访问策略形成的线性秘密共享矩阵 M 的每一行对应一个属性值, 即行向量与属性值形成一一映射的关系 φ : { 1 , ⋯ , d } → P 。 M \varphi:\{1, \cdots, d\} \rightarrow P 。 M φ:{1,⋯,d}→P。M 的行规模指 $M$ 的行数 $l$, 反映了由M所决定的实现访问结构的线性秘密共享体制的有效性, $M$ 的列规模指 $M$ 的列数 $n$, 反映了秘密重构所需要的计算量。例如访问策略为 $P=\left(a_1\wedge a_2\right)\vee \left(a_3\wedge a_4\right)$, 则形成的秘密共享矩阵 $M$ 的每一行按序一次表示属性 $a_1,a_2,a_3,a_4$ (如下图所示)。只有当所拥有的属性集合满足访问策略时 (即已知对应矩阵的行向量), 用户才能重构秘密 $s$, 所以说 $M$ 的行数 $l$反映了由 $M$ 所决定的实现访问结构的线性秘密共享体制的有效性。我们在构建秘密 $\mathrm{s}$ 时, 需要用一个包含多个随机数的秘密分享矩阵 $\rho$ 对其进行加密, 而解密时, 需要与一个矩阵相乘形成一个行数为 $M$ 列数 $n$ 的形如 $\epsilon =(\underset{n}{\underbrace{1,0,0,,0}}{)}^T$ 的矩阵以消去加密时的随机数, 获得秘密值 $s$, 所以说 $M$ 的列数 $n$ 反映了秘密重构所需要的计算量。

   假设存在访问策略 $\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)$, 用 ${\mathrm{P}}_{\mathrm{a}}$ 代表 ${\mathrm{a}}_1\wedge {\mathrm{a}}_2$, 用 ${\mathrm{P}}_{\mathrm{b}}$ 代表 $a_1\wedge a_3\wedge a_4$, 即 $P_a=\left(a_1\wedge a_2\right),P_b=\left(a_1\wedge a_3\wedge a_4\right)$ 。其中 $a_1,a_2,a_3,a_4$ 都用单条目矩阵 [1]表示。由规则 3 可分别对 ${\mathrm{P}}_{\mathrm{a}},{\mathrm{P}}_{\mathrm{b}}$ 的值进行计算, 计算过程如下:
$$P_a=\left(a_1\wedge a_2\right)=[1]\wedge [1],$$
由规则 3 公式：
$$M_{AND}=\begin{array}{cccc}{C}_a& C_a& R_a& 0\\ 0& C_b& 0& R_b\end{array}$$
可得：
$$P_a=\left(\begin{array}{ll}1& 1\\ 0& 1\end{array}\right)。$$
同理：
$$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)。$$

由规则 2 公式：
$$M_{OR}=\begin{array}{ccc}{C}_a& R_a& 0\\ C_b& 0& R_b\end{array}$$

可得, 访问策略矩阵 M 如下
$$\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)。$$

其中每一行按序表示 $a_1,a_2,a_1,a_3,a_4$ 。

2.2 加密过程

   为了分享秘密值的安全, 分享前通常会对密文进行加密, 这里引入一个秘密分享矩阵 $\rho ={\left(\mathrm{s},{\rho }_2,\cdots ,{\rho }_{\mathrm{e}}\right)}^{\mathrm{T}}$, 其中 $\mathrm{s}$ 表示秘密值, ${\rho }_{\mathrm{i}}$ 是一组随机数, 其取值范围取决于不同的加密策略。通过使用秘密分享矩阵 $\rho$ 对矩阵进行计算, 可得出一组加密后的秘密值集合，具体计算形如下:
$$M\cdot \rho ={\left(s_1,\cdots ,s_d\right)}^T\text{ 。 }$$
   假设 $\rho =(2,3,1,4{)}^{\mathrm{T}}$,即想要分享的秘密值 $s=2$, 通过表达式 $M\cdot \rho ={\left(s_1,\cdots ,s_d\right)}^T$可得 $M\cdot \rho =(5,3,7,4,1{)}^{\mathrm{T}}$ 。即加密后的秘密值集合为 $(5,3,7,4,1{)}^{\mathrm{T}}$, 计算过程如下:
$$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)$$

2.3 解密过程

   假设有用户 $A$ 拥有属性 $a_1,a_2$ 所对应的秘密值（即已知属性 $a_1,a_2$ 对应的 $M$. $\rho$ 的值), 则他可以按照如下方式进行解密:

2.3.1 求解 ${\lambda }_{\mathrm{A}}$ 的值

   取矩阵 ${\mathrm{a}}_1$, ${\mathrm{a}}_2$ 属性值对应的行向量进行转秩, 形成一个新的矩阵 ${\mathrm{M}}_{\mathrm{A}}=\left(\begin{array}{ll}1& 0\\ 1& 1\\ 0& 0\\ 0& 0\end{array}\right)$, 通过表达式 ${\mathrm{M}}_{\mathrm{A}}^{\mathrm{T}}{w}_A=\epsilon =(1,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)$$
   为方便计算 $w_{\mathrm{A}}$, 可将其转化成求解增广矩阵 $\left(\begin{array}{lll}1& 0& 1\\ 1& 1& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right)$ 的值, 通过高斯消元法求解,容易解得 $w_{\mathrm{A}}=(1,-1)$ 。

2.3.2 求解秘密值 $\mathrm{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 \epsilon =s$$

   可知, 我们现已知 $M\cdot \rho =(5,3{)}^T,w_A=(1,-1)$, 通过计算可得秘密值 $s$, 计算过程如下所示:
$$s=\left(M_A\cdot \rho \right)\cdot w_A=\left(\genfrac{}{}{0ex}{}{5}{3}\right)\cdot (1,-1)=2$$

通过解密计算得出的秘密值 $s=2$ 与加密时原假设秘密值 $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)$：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// 读取下一个tokenstring readToken() {   // 只有'(' ')' 是特殊字符，其他都是普通字符while (index < text.length()) {char c = text[index];if (c == ' ') {     // 如果是空格，那么继续向后遍历index++;        // string的索引位置向后+1continue;}else if (c == '(') { // 如果是'('那么就返回index++;         // string的索引位置向后+1return "(";}else if (c == ')') { // 如果是')'那么就返回index++;         // string的索引位置向后+1return ")";}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 stringsize_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 和 oiMatrixXd 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，第二个元素为 1MatrixXd 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
-1policy: (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
-1policy: (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 matchedpolicy: 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: 
1policy: 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: 
1policy: 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: 
1policy: 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
-1policy: 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 matchedpolicy: 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 matchedpolicy: ((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
-1policy: ((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
-1policy: ((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)$，其实有了LSSS矩阵可以直接求出解密向量，而不需要再构建策略树。核心就是通过 求解线性方程组，可以通过上述构建增广矩阵的办法。
   下面给出精简之后的源码，主要是对上面的代码删减与访问树构造部分的代码，并增加秘密$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// 读取下一个tokenstring readToken() {   // 只有'(' ')' 是特殊字符，其他都是普通字符while (index < text.length()) {char c = text[index];if (c == ' ') {     // 如果是空格，那么继续向后遍历index++;        // string的索引位置向后+1continue;}else if (c == '(') { // 如果是'('那么就返回index++;         // string的索引位置向后+1return "(";}else if (c == ')') { // 如果是')'那么就返回index++;         // string的索引位置向后+1return ")";}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 stringsize_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 和 oiMatrixXd 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，第二个元素为 1MatrixXd mat(1, 2);mat(0, 0) = atoi(token.c_str());  // 将 token 转换为整数mat(0, 1) = 1;                    // 设置矩阵第二列元素为1return 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_PolicyMatrixWithTagfor (int i = 0; i < PolicyMatrixWithTag.rows(); ++i) {if (attributeSet.find(static_cast<int>(PolicyMatrixWithTag(i, 0))) != attributeSet.end()) {rowsToKeep.push_back(i);}}// 创建子矩阵Sub_PolicyMatrixWithTagMatrixXd 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_PolicyMatrixWithTagfor (int i = 0; i < PolicyMatrixWithTag.rows(); ++i) {if (attributeSet.find(static_cast<int>(PolicyMatrixWithTag(i, 0))) != attributeSet.end()) {rowsToKeep.push_back(i);}}// 创建子矩阵Sub_PolicyMatrixWithTagMatrixXd 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=bFullPivLU<MatrixXd> solver(A);// 检查矩阵A的秩与组合矩阵[A | b]的秩，判断是否有解if (solver.rank() != FullPivLU<MatrixXd>(A).rank()) {return false;  // 无解}// 使用分解求解最小二乘解x = solver.solve(b);// 验证Ax是否确实等于bif (!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 = eif (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();}// 构造向量vVectorXd v(cols);v(0) = s;// 随机生成剩余的元素for (int i = 1; i < cols; ++i) {v(i) = rand() % 10;  // 使用 % 10 的余数生成0到9之间的随机整数}// 打印生成的向量vcout << "Generated vector v: " << v.transpose() << endl;// 计算并返回矩阵乘法结果向量lreturn 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_lamdaVectorXd 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;elsecout<<"解密不成功!!!"<<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

   $\mathrm{Setup}(\lambda ,U)\to (PK,MK)$ : 参数设置算法，由属性授权执行，以安全参数 $\lambda$ 和系统的属性集合 $U$ 为输入，生成系统的公开密钥 $PK$ 和主密钥 $MK$ 。

   具体来说，算法首先运行群生成函数获得系统参数 $\left(G,G_T,p,e\right)$ ，其中 $p$ 为素数， $G$ 和 $G_T$是两个 $p$ 阶循环群， $e$ 是一个双线性映射， $g\in G$ 为生成元。然后算法随机选择参数 $\alpha ,a\in Z_p$ ，另外对于每个属性 $i\in U$ ，算法随机选择参数 $h_1,h_2,\dots ,h_U\in G$ ，最后设置系统的公开密钥为 $PK=\left(g,e(g,g{)}^{\alpha },g^a,h_1,\dots ,h_U\right)$ ，主密钥 $MK=g^{\alpha }$ 。

3.2 KeyGen

   $\mathrm{KeyGen}(PK,MK,S)\to SK$ : 密钥生成算法，由属性授权执行，其中 $S$ 为用户的属性集合，最后生成解密密钥 $SK$ 。

   具体来说，该算法随机选择参数 $t\in Z_p$ 并构造用户解密密钥为
$$SK=\left(K=g^{\alpha }{g}^{at},L=g^t,{\left\{K_x=h_x^t\right\}}_{x\in S}\right)。$$

3.3 Encypt

   $\mathrm{Encrypt}(PK,M,(A,\rho ))\to CT$ ：加密算法，由数据拥有者执行， $M$ 为明文数据， $(A,\rho )$ 为访问策略， $CT$ 为密文。

   具体来说， $A$ 表示一个 $l\times n$ 矩阵， $\rho$ 表示把 $A$ 的每一行映射到相应属性的映射函数。然后随机选择向量 $\vec{v}=\left(s,y_2,\dots ,y_n\right)\in Z_p$ ，对 $A$ 的每一行 $A_i$ 计算内积 ${\lambda }_i=A_i\cdot \vec{v}$ ，并随机选择参数 $r_1,r_2,\dots ,r_l\in Z_p$ ，最后密文表示如下:
$$\begin{array}{rl}CT& =(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),\dots ,\\ (C_l& =g^{a{\lambda }_l}{h}_{\rho (l)}^{-r_l},D_l=g^{r_l}))\end{array}$$

   通过上节介绍的计算 ${\lambda }_i=A_i\cdot \vec{v}$ ，就把秘密值 $s$ 分 $l$ 份份额进行加密，也就是说，在进行矩阵乘时，矩阵 $A$ 的每一行都要乘以向量 $\vec{v}$ ，所以， $\vec{v}$ 中的秘密值 $s$ 就通过矩阵乘隐藏在乘积结果（结果是一个向量) 的每个元素里。

   其中 $C_1=g^{a{\lambda }_1}{h}_{\rho (1)}^{-r_1}$ 的 $\rho (1)$ 对应的便是访问策略中的第一个属性。而在算法初始化阶段公钥 $PK$ 里面已经给系统里所有的属性都生成了其对应的随机值。这样的话， $h_{\rho (1)}$ 其实对应的是访问策略中涉及的第一个属性所对应的随机值。比如说，访问策略中的第一个属性值是 “计算机”，那么 $h_{\rho (1)}$ 就是 $h$ “计算机”，这个值对应的值就是在公钥 $PK$ 中 “计算机” 属性对应的那个随机值。

   接下来，我们将介绍如何利用LSSS解密的。

3.4 Decrypt

   $\mathrm{Decrypt}(SK,CT,PK)\to M$ : 只有当 $SK$ 关联的属性集合 $S$ 满足密文 $CT$ 有关的访问策略 $(A,\rho )$ 时，才能解密成功，并输出明文 $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$ 是系统所有属性的集合的子集。若属性集合 $S$ 满足访问策略 $(A,\rho )$ 且 { λ i } \left\{\lambda_i\right\} {λi​} 为关于访问矩阵 $A$ 的共享密钥 $s$ 的有效份额，那么算法就能在多项式时间内计算出 { w i ∈ Z p } i ∈ I \left\{w_i \in Z_p\right\}_{i \in I} {wi​∈Zp​}i∈I​ ，使得 ${\sum }_{i\in I}{w}_i{\lambda }_i=s$ 。

   具体解密的算法如下:
$$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)$$

   这就是解密公式，我们先不着急对其计算解密，先对其中的个别参数拿出来解释一下。 $K_{\rho (i)}$ 这个参数，乍一看不知道这个参数来自哪里，其实它来自私钥 $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$ 的下标 $x$ 就对应着属性集合里某一个属性，这个属性也可以用 $\rho (i)$ 表示，因为通过上面举的例子，我们知道访问策略矩阵 $A$ 的每一行由可以通过映射函数 $\rho ()$ 将其映射为对应的属性。

   然后我们对上面的解密公式逐步计算解密。

• 首先计算 ：
  $e\left(C^{\prime },K\right)=e\left(g^s,g^{\alpha }{g}^{at}\right)=e\left(g^s,g^{\alpha }\right)e\left(g^s,g^{at}\right)=e(g,g{)}^{\alpha \cdot s}e(g,g{)}^{sat}$ 。

• 再计算
  $$\begin{array}{rl}& \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{)}^{ta{\lambda }_i{w}_i}=e(g,g{)}^{tas}\end{array}$$

• 最后分子除以分母，消掉 $e(g,g{)}^{tas}$ ，最后计算结果是 $e(g,g{)}^{\alpha \cdot s}$ 。

• 然后再用 $C/e(g,g{)}^{\alpha \cdot s}$ 就得到明文 $M$ 。

   在计算过程中我们需要提前计算 { w i ∈ Z p } i ∈ I \left\{w_i \in Z_p\right\}_{i \in I} {wi​∈Zp​}i∈I​ ，使得 ${\sum }_{i\in I}{w}_i{\lambda }_i=s$ ，根据上面举得例子，我们可以知道只有当访问策略满足私钥关联的属性集合时，才能找到这样 { w i } \left\{w_i\right\} {wi​} 集合存在。访问策略不满足私钥关联的属性集时，这样的 { w i } \left\{w_i\right\} {wi​} 就不存在，算法解密公式就不能计算下去，也就解密不出明文。

3.5 源码实现，基于C++和pbc库

   针对上面基于LSSS的属性基加密源码实现如下，这里与上面基于LSSS矩阵访问控制的联系主要是需要上面传入向量$\lambda$和$w$,使得${\sum }_{i\in I}{w}_i{\lambda }_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; // 密文Celement_t C_prime; // 辅助计算元C'element_t C_i[NUM_ALL_ATTRIBUTES]; // 每个属性的密文对C_ielement_t D_i[NUM_ALL_ATTRIBUTES]; // 每个属性的密文对D_i
};// Step3: 定义密钥结构体
struct SecretKey {element_t K, L;                  // 定义私钥K 和 Lelement_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 &params) {element_init_G1(params.g, pairing); // 初始化G1群元素gelement_init_G1(params.ga, pairing); // 初始化G1群元素gaelement_init_G1(params.g_alpha, pairing); // 初始化G1群元素g_alphaelement_init_GT(params.egg_alpha, pairing); // 初始化GT群元素e(g, g)^alphaelement_t alpha, a; // 定义alpha和aelement_init_Zr(alpha, pairing); // 初始化Zr群元素alphaelement_init_Zr(a, pairing); // 初始化Zr群元素aelement_random(alpha); // 生成随机alphaelement_random(a);     // 生成随机aelement_random(params.g); // 生成随机G1群元素gelement_pow_zn(params.ga, params.g, a); // 计算g^aelement_pow_zn(params.g_alpha, params.g, alpha); // 计算g^alphaelement_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群元素并赋值给hfor (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和aelement_clear(alpha);element_clear(a);
}// step2: 加密函数
void encrypt(pairing_t pairing, SystemParams &params, element_t M, Ciphertext &CT, element_t s, element_t *lambda, int num_attrs) {element_init_GT(CT.C, pairing);             // 初始化GT群元素Celement_pow_zn(CT.C, params.egg_alpha, s);  // 计算C = e(g, g)^alpha * selement_mul(CT.C, CT.C, M);                 // 计算C = M * Celement_init_G1(CT.C_prime, pairing);       // 初始化G1群元素C'element_pow_zn(CT.C_prime, params.g, s);    // 计算C' = g^s// 为每个属性计算密文对C_i和D_ifor (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);                // 生成随机relement_pow_zn(tmp_h, params.h[i], h_r); // 计算h[attrs[i]]^relement_invert(tmp_h, tmp_h);       // 计算h[attrs[i]]^-relement_mul(CT.C_i[i], CT.C_i[i], tmp_h); // 计算C_i = C_i * h[attrs[i]]^-relement_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^relement_clear(tmp_h); // 清除临时变量tmp_helement_clear(h_r); // 清除临时变量h_r}
}// step3: 密钥生成函数
void keygen(pairing_t pairing, SystemParams &params, SecretKey &SK, int *attrs, int num_attrs) {element_t t, g_at; // 定义t、g_at和g_at_alphaelement_init_Zr(t, pairing); // 初始化Zr群元素telement_init_G1(g_at, pairing); // 初始化G1群元素g_atelement_init_G1(SK.K, pairing); // 初始化G1群元素Kelement_init_G1(SK.L, pairing); // 初始化G1群元素Lelement_random(t); // 生成随机telement_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); // 清除临时变量telement_clear(g_at); // 清除临时变量g_at
}// step4: 解密函数
void decrypt(pairing_t pairing, SystemParams &params, 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群元素resultelement_init_GT(term1, pairing); // 初始化GT群元素term1element_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群元素productelement_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_ielement_mul(product, product, term1); // 计算product = product * term1}element_div(result, result, product);   // 计算e(C', K) / productelement_div(recovered_M, CT.C, result); // 计算recovered_M = C / resultelement_clear(result);  // 清除临时变量resultelement_clear(term1);   // 清除临时变量term1element_clear(term2);   // 清除临时变量term2element_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() {// 初始化pairingpairing_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 bytesstring M_input = "111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeee";element_t M;   // 明文element_t s;   // 随机数 selement_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群元素Melement_init_GT(recovered_M, pairing); // 初始化GT群元素recovered_M// 将string转成elementstring_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第一个取1element_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转成stringcout << "解密明文为: " << output;  // 解密成功cout<<",长度为"<<output.size()<<endl;} else {cout << "Decryption failed." << endl; // 解密失败}// 清除元素element_clear(M); // 清除明文元素Melement_clear(recovered_M); // 清除恢复的明文元素recovered_Melement_clear(s); // 清除随机数sdelete[] lambda; // 释放lambda数组delete[] omega; //释放omega数组// 清除系统参数element_clear(params.g); // 清除系统参数gelement_clear(params.ga); // 清除系统参数gaelement_clear(params.g_alpha); // 清除系统参数g_alphaelement_clear(params.egg_alpha); // 清除系统参数egg_alphafor (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {element_clear(params.h[i]); // 清除每个属性的公钥元素h[i]}// 清除私钥element_clear(SK.K); // 清除私钥Kelement_clear(SK.L); // 清除私钥Lfor (int i = 0; i < NUM_ALL_ATTRIBUTES; i++) {element_clear(SK.K_rho[i]); // 清除所有私钥元素K_rho[i]}// 清除密文element_clear(CT.C); // 清除密文Celement_clear(CT.C_prime); // 清除密文C_primefor (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$上计算

    在第二章中主要给出了基于矩阵的LSSS计算实现访问控制。第三章主要给出了基于LSSS 的属性基加密机制，这里主要需要第二章传入向量$\lambda$和$w$,使得${\sum }_{i\in I}{w}_i{\lambda }_i=s$ 成立。上述代码中是手动构造假的向量，实际应该真实计算得出并传入，但存在一个主要问题就是矩阵运算得结果都是通用数字，而双线性运算都是在$Z_p$群上的运算，因此需要把$\lambda$和$w$转成$Z_p$群中元素进行运算，下面是基础代码demo:

#include <stdio.h>
#include <pbc/pbc.h>int main() {// 初始化pairingpairing_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及整数sint 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);// 检查内积是否等于sif (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.

四. 参考文献

1. 线性秘密共享方案（LSSS）构造与解密
2. 属性加密访问结构(二)—线性秘密共享方案(LSSS)
3. 属性加密访问结构(一)—访问控制树(超详细)
4. LSSS源码实现
5. 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分把，感谢各位大佬支持！

这篇关于LSSS算法实现，基于eigen和pbc密码库【一文搞懂LSSS，原理+代码】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---