1.引言

在IBE和ABE中较为经典的方案[1,2]都用到了一个关键的撤销树，在文献[1]中叫做MT树，文献[2]中叫做KEK树，两个方案的基本实现方法都是寻找最小覆盖集合.现在将  寻找最小覆盖集合的代码加以实现。

2.基本思路

在IBE中，对所有用户需要构建这样的一颗二叉树，若v是叶子节点，则PATH(v)表示从v到根集合的所有节点集合(包括叶子节点v和根节点)，若v是一个非叶子节点，则表示v的左孩子节点,表示其右孩子节点，我们假设树中的节点被编码为唯一的字符串。

定义一个函数KUNodes，用于计算需要为其发布密钥更新的最小节点集，以便只有在t时刻没有撤销的用户才能解密密文。函数输入二叉树T,撤销列表rl和时间t。输出一个节点集合Y,其为T中节点的最小集合：

集合Y中的任何节点都不是rl中对应时间<=t的节点(在时间t或之前撤销)的祖先（或本身），而所有其他叶节点（对应于未撤销的用户）在集合中恰好有一个祖先（或本身）。

该函数的操作如下。首先将已撤销节点的所有祖先标记为已撤销节点，然后输出已撤销节点的所有未撤销子节点。

算法如下：

上述算法感觉较为晦涩，举一个例子：

第一个图是用户未被撤销,第二个图是用户u3被撤销。得到的最小覆盖集为画勾的节点。

3.代码实现

注意：

1.本代码实现的是满二叉树，即叶子节点个数为2^n.

2.由于只是用于实验，并未考虑时间t.

首先写出树中节点的类：

package tree; public class TreeNode { private String id; private TreeNode parent; private TreeNode leftChild; private TreeNode rightChild; public boolean isLeaf; TreeNode() { } TreeNode(String id) { this.id = id; } @Override public boolean equals(Object obj) { if (!(obj instanceof TreeNode)) { return false; } return this.id == ((TreeNode) obj).id; } public String getId() { return id; } public void setId(String id) { this.id = id; } public TreeNode getParent() { return parent; } public void setParent(TreeNode parent) { this.parent = parent; } public TreeNode getLeftChild() { if (!isLeaf) return leftChild; else return null; } public void setLeftChild(TreeNode leftChild) { if (!isLeaf) this.leftChild = leftChild; } public TreeNode getRightChild() { if (!isLeaf) return rightChild; else return null; } public void setRightChild(TreeNode rightChild) { if (!isLeaf) this.rightChild = rightChild; } }

再给出对树的基本操作类：

package tree; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class TreeUtil { /** * 返回树中节点个数 * @param root * @return */ public static int getTreeNodeNum(TreeNode root){ if(root.getLeftChild()==null && root.getRightChild()==null){ return 1; } return getTreeNodeNum(root.getLeftChild())+ getTreeNodeNum(root.getRightChild())+1; } /** * 返回叶子节点到树根的路径 * @param leaf * @return */ public static List<TreeNode> getPath(TreeNode leaf){ if(leaf==null){ return null; } List<TreeNode> pathNodeList=new ArrayList<TreeNode>(); TreeNode TempNode=leaf; while(TempNode.getParent()!=null){ pathNodeList.add(TempNode); TempNode=TempNode.getParent(); } pathNodeList.add(TempNode); return pathNodeList; } /** * 获得最小覆盖集 * @param T * @param reList * @return */ public static Set<TreeNode> KUNNodes(TreeNode T,List<TreeNode> reList){ Set<TreeNode> X=new HashSet<TreeNode>(); Set<TreeNode> Y=new HashSet<TreeNode>(); for (TreeNode treeNode : reList) { X.addAll(getPath(treeNode)); } for (TreeNode treeNode : X) { if(treeNode.getLeftChild()!=null && !X.contains(treeNode.getLeftChild())){ Y.add(treeNode.getLeftChild()); } if(treeNode.getRightChild()!=null && !X.contains(treeNode.getRightChild())){ Y.add(treeNode.getRightChild()); } } if(Y.isEmpty()) Y.add(T); return Y; } /** * 创建包含n个叶子节点的树 * @param n * @return */ public static TreeNode createTree(int n){ List<TreeNode> nodeList=new ArrayList<TreeNode>(); nodeList.add(new TreeNode("node"+0));//node0为占位节点 int depth=(int)(Math.log(n)/Math.log(2))+1; for(int i=1;i<=depth;i++){ for(int j=(int)(Math.pow(2, i-1));j<(int)(Math.pow(2, i));j++){ nodeList.add(new TreeNode("node"+j)); nodeList.get(j).isLeaf=false; if(i==depth){ nodeList.get(j).isLeaf=true; } } } for(int i=1;i<nodeList.size();i++){ if(i!=1) nodeList.get(i).setParent(nodeList.get(i/2)); if(!nodeList.get(i).isLeaf){ nodeList.get(i).setLeftChild(nodeList.get(2*i)); nodeList.get(i).setRightChild(nodeList.get(2*i+1)); } } return nodeList.get(1); } }

最后写出测试类进行测试：

package tree; import java.util.ArrayList; import java.util.List; import java.util.Set; public class Test2 { public static void main(String[] args) { TreeNode node1=TreeUtil.createTree(8); //创建含8个叶子节点的访问树 TreeNode node10=node1.getLeftChild().getRightChild().getLeftChild(); TreeNode node14=node1.getRightChild().getRightChild().getLeftChild(); System.out.println(node10.getId()); System.out.println(node14.getId()); List<TreeNode> revList=new ArrayList<TreeNode>(); revList.add(node10); revList.add(node14); Set<TreeNode> Y=TreeUtil.KUNNodes(node1, revList); for (TreeNode treeNode : Y) { System.out.println(treeNode.getId()); } } }

得到结果为：

解释一下结果：

整棵树的构造为：

node10和node14为我们需要撤销的用户集合，

所以最后最小覆盖集应该为：node4,node11,node6,node15

4.结语

这里只是对算法进行了简单实现，后续会将算法改进，加入到具体的IBE或ABE撤销方案中。

5.参考文献

[1] Boldyreva, Alexandra & Goyal, Vipul & Kumar, Virendra. (2008). Identity-based encryption with efficient revocation. 417-426. 10.1145/1455770.1455823. 

[2] Hur, Junbeom & Noh, Dong Kun. (2011). Attribute-Based Access Control with Efficient Revocation in Data Outsourcing Systems. Parallel and Distributed Systems, IEEE Transactions on. 22. 1214 - 1221. 10.1109/TPDS.2010.203.