可搜索加密
# Java PBC 基础
# 依赖导入导出
外部 jar 包导入jpbc-api-2.0.0.jar以及jpbc-plaf-2.0.0.jar
maven 指定主类并设置自动路径
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-jar-plugin</artifactId>
<version>3.2.0</version>
<configuration>
<archive>
<manifest>
<addClasspath>true</addClasspath>
<mainClass>cia.northboat.Main</mainClass>
</manifest>
</archive>
</configuration>
</plugin>
</plugins>
</build>
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
导出 jar 包配置
<build>
<resources>
<resource>
<directory>lib</directory>
<targetPath>/BOOT-INF/lib/</targetPath>
<includes>
<include>**/*.jar</include>
</includes>
</resource>
</resources>
</build>
2
3
4
5
6
7
8
9
10
11
# 初始化
群参数设置为了方便测试时间,选择使用较小阶的循环群,这里需要使用 JPBC 自带的参数生成函数
160 为整数群的阶数,打印参数并保存为a160.properties放在项目根目录使用
由于各算法尽量要在相同参数下进行时间开销测试,所有的系统参数应在 Main 函数中初始化,而后作为参数传入各自的构造函数进行系统初始化
需要注意的是,群上元素的运算会改变元素本身——直接写 g1 = g.add(h) 会让 g 自身也变成 g.add(h)。解决办法是在定义时取 getImmutable() 令其不可变(本文统一采用这种)
Element g = G1.newRandomElement().getImmutable();
Element x = Zr.newRandomElement();
Element g5 = g.powZn(x);
2
3
4
或在计算时取 duplicate() 复制一份而不影响自身
Element g = G1.newRandomElement();
Element x = Zr.newRandomElement();
Element g6 = g.duplicate().powZn(x)
2
3
4
# 双线性群的运算
乘方、乘、加法以及配对运算
Element g = G1.newRandomElement();
Element h = G1.newRandomElement();
Element x = Zr.newRandomElement();
Element g1 = g.add(h);
Element g2 = g.mul(h);
Element g3 = g.powZn(x);
Element g4 = bp.pairing(g, h);
2
3
4
5
6
7
8
验证公式
# 哈希嵌入
第一种方式:先 md5 哈希为 byte 数组(调用 spring 的 DigestUtils),再直接 setFromHash 映射到 G1——但这样会让哈希值与生成元 g 失去联系,故本文采用第二种
第二种:先哈希到整数群 Zp,再利用群 G 上的生成元 g 计算幂指数,从而哈希到指定群 G 上
public static Element hash(byte[] bytes){
Element hash = null;
try{
byte[] md5 = DigestUtils.md5Digest(bytes);
// 映射到 Zr 整数群
Element x = Zr.newElement().setFromHash(md5, 0, md5.length);
// 通过 G1 上的生成元 g 幂运算映射到 G1 群上
hash = g.powZn(x).getImmutable();
}catch (Exception e){
e.printStackTrace();
}
return hash;
}
2
3
4
5
6
7
8
9
10
11
12
13
# 可搜索加密算法
# 接口与抽象类
SE 的仿真绕不开 setup / keygen / enc / trap / search 五个函数,具备密钥更新策略的再扩展 updateKey / updateEnc / constTrap / updateSearch 四个。接口设计就围绕这 8 个函数:enc/trap 各提供单关键词与字符串数组两种重载以适应不同算法的传参形式,不支持的操作维持默认抛异常、由调用方降级处理;另有一个 default 的 test 用于测定三种操作的耗时,各算法按需重载
public interface SearchableEncryption {
void setup();
void keygen();
boolean search();
// 单关键词与批量两种传参,不支持者保持默认抛异常,由调用方降级
default void enc(String w) { throw new UnsupportedOperationException(); }
default void enc(List<String> W) { throw new UnsupportedOperationException(); }
default void trap(String q) { throw new UnsupportedOperationException(); }
default void trap(List<String> Q) { throw new UnsupportedOperationException(); }
// 具备密钥更新策略的算法才实现这四项
default void updateKey() { throw new UnsupportedOperationException(); }
default void updateEnc() { throw new UnsupportedOperationException(); }
default void constTrap(String q) { throw new UnsupportedOperationException(); }
default boolean updateSearch() { throw new UnsupportedOperationException(); }
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CipherSystem 实现该接口,持有几项基本的系统参数:Field G, GT, Zr 为所用到的循环群,Pairing bp 为双线性配对函数,int n 为字符串哈希长度,boolean updatable 标识是否存在密钥更新策略。此外它还封装了哈希、取随机数、配对等语法糖,供各子算法直接调用
public abstract class CipherSystem implements SearchableEncryption{
Field G, GT, Zr;
Pairing bp;
int n;
boolean updatable;
public CipherSystem(Field G, Field GT, Field Zr, Pairing bp, int n, boolean updatable) {
this.G = G; this.GT = GT; this.Zr = Zr; this.bp = bp; this.n = n; this.updatable = updatable;
}
public CipherSystem(Field G, Field GT, Field Zr, Pairing bp, int n) { this(G, GT, Zr, bp, n, false); }
// 各子算法按需取用,其余为语法糖
public Field getG(){ return G; }
public Field getGT(){ return GT; }
public Field getZr(){ return Zr; }
public Pairing getBp(){ return bp; }
public Element[] h(String str){ return HashUtil.hashStr2ZrArr(Zr, str, n); }
public Element randomZ(){ return Zr.newRandomElement().getImmutable(); }
public Element randomG(){ return G.newRandomElement().getImmutable(); }
public Element pairing(Element u, Element v){ return bp.pairing(u, v).getImmutable(); }
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# PECKS 算法实现
以 PECKS 实现为例
# 初始化 setup
继承父类并重载构造函数
public class PECKS extends CipherSystem {
public PECKS(Field G, Field GT, Field Zr, Pairing bp, int n){
super(G, GT, Zr, bp, n);
}
}
2
3
4
5
公钥
私钥
其中
实现线性函数 f 和哈希函数 H
这个 h 哈希在父类中已经定义过,将一个字符串通过 ASCII 码映射为整数数组
private Element g, g1, g2, EK, sk_cs, sk_ts, pk_cs, pk_ts, x_t, b1, a1, b2;
@Override
public void setup(){
g = this.getG().newRandomElement().getImmutable();
a1 = this.getZr().newRandomElement().getImmutable();
b1 = this.getZr().newRandomElement().getImmutable();
b2 = this.getZr().newRandomElement().getImmutable();
x_t = this.getZr().newRandomElement().getImmutable();
sk_cs = this.getZr().newRandomElement().getImmutable();
sk_ts = this.getZr().newRandomElement().getImmutable();
g1 = g.powZn(b1).getImmutable();
g2 = g.powZn(b2).getImmutable();
EK = g.powZn(f(x_t).div(b1)).getImmutable();
pk_cs = g.powZn(sk_cs).getImmutable();
pk_ts = g.powZn(sk_ts).getImmutable();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 密钥生成 Keygen
其中
Element D_i, E_i, F_i, G_i, PK_i;
@Override
public void keygen(){
Element x_ti = this.getZr().newRandomElement().getImmutable();
Element y_i = this.getZr().newRandomElement().getImmutable();
D_i = g2.powZn(f(x_ti).mul(x_t.negate().div(x_ti.sub(x_t)))).getImmutable();
E_i = g2.powZn(b1.mul(x_ti.negate().div(x_t.sub(x_ti)))).getImmutable();
G_i = y_i.getImmutable();
PK_i = g.powZn(y_i).getImmutable();
}
2
3
4
5
6
7
8
9
10
11
# 加密 Enc
定义变量并重写 enc 函数,入参为 List<String> words
密文由多项式系数 π 决定,其中 r 为随机整数
π 来自方程 N(x) = (x−H(w₁))…(x−H(w_l)) + 1 = 1 展开后的系数
由于 π 只与 H(w) 有关,问题就转化为已知 H(w) 数组求其初等对称多项式系数
即 c1 为所有 ai 之和、c2 为两两乘积之和、c3 为三三乘积之和……cn 为全部 ai 之积。采用动态规划求解
public static List<Element> getCoefficients(Field Zr, List<Element> factors){
int l = factors.size();
List<Element> coefficients = new ArrayList<>(l+1);
for (int i = 0; i <= l; i++) {
coefficients.add(Zr.newZeroElement().getImmutable());
}
coefficients.set(0, Zr.newOneElement().getImmutable());
// 动态规划计算系数
for (Element factor: factors) {
for (int j = l; j >= 1; j--) {
// 更新系数:c_j = c_j + c_{j-1} * a_i
coefficients.set(j, coefficients.get(j).add(coefficients.get(j - 1).mul(factor)).getImmutable());
}
}
// 添加符号:c_k = (-1)^k * c_k
for (int k = 1; k <= l; k++) {
if(k % 2 == 1){
coefficients.set(k, coefficients.get(k).negate().getImmutable());
}
}
Collections.reverse(coefficients);
return coefficients;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
最后有一个翻转,因为在加密算法中,最高位恒为 1,最低位为常数位;并且由于多项式在方程中是等于常数 1 的,所以常数位(pi[0])还要人为的加上 One
最后的加密函数长这样
Element[] C1;
Element C2, C3;
int l;
@Override
public void enc(List<String> W) {
Element r = this.getZr().newRandomElement().getImmutable();
C2 = EK.powZn(r).getImmutable();
C3 = g.powZn(r).getImmutable();
l = W.size();
List<Element> factors = new ArrayList<>(l);
for(int i = 0; i < l; i++){
factors.add(H(W.get(i)));
}
System.out.println("function params: " + factors);
List<Element> pi = PolynomialUtil.getCoefficients(this.getZr(), factors);
pi.set(0, pi.get(0).add(this.getZr().newOneElement()).getImmutable());
System.out.println("polynomial coefficients: " + pi);
C1 = new Element[l+1];
for(int i = 0; i <= l; i++){
C1[i] = g1.powZn(r.mul(pi.get(i))).getImmutable();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 陷门计算 Trap
陷门计算,Q 为搜索的关键词
其中
实现上只需注意求和部分:外层 for(int i = 0; i <= l; i++) 把每层 φ 记为 i,内层遍历各关键词哈希后做幂运算并累加,即得每个 Tφ
重写 trap 函数
Element[] T1;
Element T2, T3, T4;
@Override
public void trap(List<String> Q) {
Element s = this.getZr().newRandomElement().getImmutable(), pi = this.getZr().newRandomElement().getImmutable();
T2 = E_i.powZn(s).getImmutable();
T3 = D_i.powZn(s).getImmutable();
T4 = g.powZn(pi).getImmutable();
if(Q.size() > l){
return;
}
T1 = new Element[l+1];
Element m = this.getZr().newElement(Q.size()).getImmutable();
for(int i = 0; i <= l; i++){
Element sum = this.getZr().newZeroElement();
Element fai = this.getZr().newElement(i).getImmutable();
for (String str: Q) {
sum.add(H(str).powZn(fai));
}
sum.getImmutable();
T1[i] = g2.powZn(s.mul(m.invert()).mul(sum)).mul(pk_cs.powZn(pi)).getImmutable();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 搜索 Search
重写 search 函数
@Override
public boolean search() {
Element left = this.getGT().newOneElement();
for(int i = 0; i <= l; i++){
Element cur = this.getBp().pairing(C1[i], T1[i].div(T4.powZn(sk_cs)));
left.mul(cur);
}
left.getImmutable();
Element right = this.getBp().pairing(C2, T2).mul(this.getBp().pairing(C3, T3)).getImmutable();
System.out.println("left: " + left);
System.out.println("right: " + right);
return left.isEqual(right);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 测试 Test
test 用于测定 enc/trap/search 的耗时,各算法的测定方式不同(如随关键词数量变化、随用户数量变化),PECkS 直接复用接口里的 default 实现
# 隐藏矢量加密
本次复现选取了 HVE 与 GO 算法部分进行实现
Secure Alert Zones
# 安全警告区域与 HVE
安全告警区域(Secure Alert Zones)要求用户加密上传自身位置、由服务端在密文上判断是否落入告警区域,以保护蕴含健康、政治倾向、生活方式等敏感属性的位置数据(“接触追踪”是其典型场景);由于传统 SE 面向关键词与范围查询、须先做一层“空间到属性”的映射,而对称方案 SSE 又要求把明文位置交付给可信第三方,故本文选用非对称结构的 HVE,并用马尔可夫模型结合 Monte Carlo 采样刻画告警区域随时间的演化
可搜索加密技术的一种,隐藏向量加密 HVE(Hidden vector encryption)
HVE 支持带通配符的属性查询,可在密文上做子集匹配与范围匹配。三方参与:用户用公钥加密自身位置上传,TA 划定告警区域并签发 Token,服务器持 Token 在密文上匹配而无需获知真实位置。查询代价取决于 Token 中非通配符位的数量——每一位对应一次昂贵的双线性对运算,这正是后面要用 Gray 编码去压缩的东西
设属性向量 I 与查询向量 T 长度均为 l,非通配符集合为 J
1、密钥与公钥:取 g ∈ G、a ∈ Z_p,以及三组逐位的密钥 u、h、w,其原值 U=u, H=h, W=w 直接作为公钥
2、加密:对向量 I 加密出密文 C,其中 M 为明文的哈希值,s 为随机数;C0、C1 为单元素,C2、C3 为矢量
3、Token 构造:仅在 J 上进行,每位各取一对随机数 r1、r2(故 r1、r2 各有 l 个)
4、查询匹配:计算
展开分母的两项
I 与 T 逐位相同时,两项的累乘式完全一致并消去,得 M' = M,匹配成功;任一位不同则无法消去,M' ≠ M
HVE 实现(JPBC)
采用 JPBC 编写,实现一个简化版本的 HVE 加密 + Token 生成 + 匹配功能,用于支持布尔向量上的匹配测试
具体功能
| 步骤 | 内容 |
|---|---|
| 参数生成 | 生成随机群元素,构造密钥结构 |
| 加密 | 输入属性向量 I,输出密文结构 |
| 生成 Token | 输入查询向量 T,构造 Token |
| 匹配判断 | 输入密文与 Token,判断是否匹配 |
这里的 I/T 矢量实际上就是 Gray 编码,只不过要字符上的 1/0 转化为 Zp 群上的 One/Zero 来参与计算,而加密过程中的 M 可以是用户携带的真实消息,例如 userID、标识、通知触发信息等
初始化
加密
Element C0, C1;
Element[] C2, C3;
@Override
public void enc(String w) {
Element s = randomZ();
C0 = M.mul(pairing(g, g).powZn(a.mul(s))).getImmutable();
C1 = g.powZn(s).getImmutable();
C2 = new Element[l];
C3 = new Element[l];
for(int i = 0; i < l; i++){
Element I = w.charAt(i) == '1' ? getI("1") : getI("0");
C2[i] = U[i].powZn(I).mul(H[i]).powZn(s).getImmutable();
C3[i] = W[i].powZn(s).getImmutable();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
陷门计算
String T;
Element K0;
Element[] K1, K2;
@Override
public void trap(String q) {
T = q;
K1 = new Element[l];
K2 = new Element[l];
Element c = this.getG().newOneElement();
for(int i = 0; i < l; i++){
if(q.charAt(i) != '*'){
Element T = q.charAt(i) == '1' ? getI("1") : getI("0");
Element r1 = randomZ(), r2 = randomZ();
K1[i] = g.powZn(r1).getImmutable();
K2[i] = g.powZn(r2).getImmutable();
c.mul(u[i].powZn(T).mul(h[i]).powZn(r1).mul(w[i].powZn(r2)));
}
}
c.getImmutable();
K0 = g.powZn(a).mul(c).getImmutable();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
匹配
@Override
public boolean search() {
Element part1 = pairing(C1, K0);
Element part2 = this.getGT().newOneElement();
for(int i = 0; i < l; i++){
if(T.charAt(i) != '*'){
Element part3 = pairing(C2[i], K1[i]);
Element part4 = pairing(C3[i], K2[i]);
part2.mul(part3.mul(part4));
}
}
part2.getImmutable();
Element M1 = C0.div(part1.div(part2)).getImmutable();
System.out.println("HVE M: " + M);
System.out.println("HVE M': " + M1);
return M.isEqual(M1);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
测试
Gray 编码,输入权重
Map<String, Double> cells = new HashMap<>();
cells.put("A", 0.85);
cells.put("B", 0.15);
cells.put("C", 0.60);
cells.put("D", 0.35);
cells.put("E", 0.95);
2
3
4
5
6
不同编码深度 l = 3、4、5、6、7 下的分配结果不再逐一列出,其共同点是:权重最高的 cell 始终占据 Gray 路径的起点,编码位宽随 l 增长而扩展,且相邻权重之间的 Hamming 距离恒为 1
HVE 加密测试
输入I = {1, 0, 1}, T = {1, *, 1} → 匹配成功
输入I = {1, 0, 1}, T = {1, *, 0} → 匹配失败
# Gray 编码与图嵌入优化
Gray 编码(Gray Code,又称反射二进制码 RGC)是一种重新排列的二进制序列,使得相邻两个编码的 Hamming 距离恒为 1。普通二进制做不到这一点——7 → 8 就是0111 → 1000,四个比特全部翻转。电路设计、模拟转数字以及本文的密文匹配都希望相邻编号的变动尽量小,以避免跳变误差(glitch)、编码抖动和配对计算冗余
3 位 Gray 编码与普通二进制的对比如下
| 十进制 | 二进制 | Gray 编码 |
|---|---|---|
| 0 | 000 | 000 |
| 1 | 001 | 001 |
| 2 | 010 | 011 |
| 3 | 011 | 010 |
| 4 | 100 | 110 |
| 5 | 101 | 111 |
| 6 | 110 | 101 |
| 7 | 111 | 100 |
本文用它把空间网格(cell)编号映射成 HVE 支持的属性向量(如 6 位二进制),使物理上邻近的单元在 Hamming 空间中也彼此接近,从而为下面的图嵌入优化留出空间,最终让 Token 的非星号位更少、配对开销更低
k-bit 的 Gray 编码空间共有 2^k 个编码点,可视为 k 维超立方体上的顶点(如0000、0001、0011…),每个顶点分配给一个 cell
图嵌入优化技术
Graph Embedding
图嵌入要做的,就是把落入同一告警区域的 cell 在 k-cube 中重排到编码相近的位置,用 Binary-Reflected Gray(BRG)路径规则建立 Token 与空间位置的对应,从而压缩 Token 的非星号位、降低配对开销
以一个 3×3 的城市网格为例,告警区域为 {1, 2, 4, 5},网格编号如下
Grid (cell layout):
[0] [1] [2]
[3] [4] [5]
[6] [7] [8]
2
3
4
5
假设有一个告警区域,包含 cell 编号为
Alert Zone: {1, 2, 4, 5}
原始做法:对 9 个 cell 直接编号并做 4 位二进制编码(2^4 = 16 > 9),对应关系如下
| Cell | Binary | Gray Code |
|---|---|---|
| 0 | 0000 | 0000 |
| 1 | 0001 | 0001 |
| 2 | 0010 | 0011 |
| 3 | 0011 | 0010 |
| 4 | 0100 | 0110 |
| 5 | 0101 | 0111 |
| 6 | 0110 | 0101 |
| 7 | 0111 | 0100 |
| 8 | 1000 | 1100 |
此时 cell 1 为 0001、cell 5 为 0111,二者 Hamming 距离为 2,意味着 Token 至少要两个非星号位。重排后的编码如下
| Cell | Optimized Gray Code |
|---|---|
| 1 | 0000 |
| 2 | 0001 |
| 4 | 0011 |
| 5 | 0010 |
| 0 | 0110 |
| 3 | 0111 |
| 6 | 0101 |
| 7 | 0100 |
| 8 | 1100 |
这样,告警区域中所有点{1,2,3,5}之间的 Hamming 距离最多为 2,用于搜索的 Token 只需要最多 2 个非星号位
# 三种启发式优化算法
三个算法做的是同一件事——把高概率 cell 压进 Gray 编码空间中彼此靠近的位置,区别只在规模适应策略
| 算法 | 策略 | 适用规模 | 特性 |
|---|---|---|---|
| GO | 单种子沿 Gray 路径贪心分配 | 小规模,精确嵌入 | O(n),不可并行 |
| MSGO | 按 depth 分簇,每簇独立跑 GO 后合并 | 中等规模 | O(n),可并行 |
| SGO | 每个 cell 各自挑最近的未用编码,不维护路径 | 大规模(1000+) | O(n),可并行 |
Gray Optimizer:以概率最高的 cell 为种子置于路径起点,此后沿 Gray 路径逐点展开,每填入一个位置就取剩余 cell 中概率最大者,编码点只使用一次。4 个 cell 概率为 0.4/0.3/0.2/0.1 时,2-bit 编码按序分配为 00,01,11,10,恰好构成一条 Gray 路径,Token 只需 1~2 个非星号位即可同时命中它们。缺点是线性遍历无法处理大量 cell
Multiple Seed GO:cell 变多(100+)后 Gray 路径过长、冲突概率上升,单路径的局部最优也不再有效。MSGO 按概率排序后每 depth 个切为一簇,各簇独立执行 GO 再合并,用 depth 控制簇大小
Scaled GO:面对 1000+ cell,SGO 让每个 cell 都作为种子,各自挑“最接近”的未用编码,不再维护 Gray 路径结构——GO 中相邻两次分配的编码必定相邻且严格按概率降序,SGO 则可能给出 0011, 0000, 0001 这种不连续序列,本质是“稀疏散列式”分配。以 3 位空间 8 个点为例:概率最高的取 000,第二个挑与 000 Hamming 距离最近的空位(001/010/100 任取其一),第三个取与已分配编码平均距离最小的点,依此类推
GO VS. SGO:GO 每步都要查邻接点、用优先队列挑概率最大的 cell,并保证路径不重复不跳跃,本质是图遍历 + 优先队列 + 贪心搜索;SGO 只需排序加标记数组,还能用预计算的 Hamming 距离矩阵并行分配。两者名义复杂度同为 O(n),SGO 更轻量、更易实现、更缓存友好
复现:Gray 路径构建
对 GO(Gray Optimizer)算法的复现,基于 Gray 编码路径的贪心式映射策略,能将高概率告警区域压缩进 Hamming 空间中的紧凑区域,减少 HVE Token 指定位数,从而降低查询成本
流程是:先算出完整的 Gray 路径,再按权重从高到低的顺序把 cell 依次分配上去。输入输出分别是区域权重集合Map<String, Double>与分配好的 Gray 编码Map<String, String>
Gray 路径就是一条相邻两码 Hamming 距离恒为 1 的序列,本质上是 k 维超立方体上的 Hamiltonian Path,3 位空间下的完整路径为
000 → 001 → 011 → 010 → 110 → 111 → 101 → 100
我们使用 Binary Reflected Gray Code(BRGC) 构造规则,它的思路是:递归生成 n 位 Gray 编码序列
注意这里的 reverse 是把集合倒过来遍历的意思,并非对字符翻转
以 n = 3 为例,0+G(2) 给出 000/001/011/010,1+reverse(G(2)) 给出 110,111,101,100,合起来即为上面那条路径
Gray 路径构造
public List<String> buildGrayPath(int l) {
if (l == 0) return new ArrayList<>(List.of(""));
List<String> prev = buildGrayPath(l-1);
List<String> path = new ArrayList<>();
// 正序添加,前缀 0
for (String code : prev) {
path.add("0" + code);
}
// 反序添加,前缀 1
for (int i = prev.size()-1; i >= 0; i--) {
path.add("1" + prev.get(i));
}
return path;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复现:区域编码
GO 贪心实现
public Map<String, String> grayOptimizer(Map<String, Double> cells, int l){
// 构建长度为 l 的 Gray 编码路径
if(cells.size() > Math.pow(2, l)){
System.out.println("Cells too Much, Can't Encode");
return null;
}
List<String> codes = buildGrayPath(l);
System.out.println(codes);
// 构建大顶堆,对 cells 按照权重从大到小排序
PriorityQueue<String> sortedCells = new PriorityQueue<>((a, b) -> {
if(cells.get(b) - cells.get(a) < 0){
return -1;
} else if(cells.get(b) - cells.get(a) == 0){
return 0;
} else {
return 1;
}
});
for(String cell: cells.keySet()){
sortedCells.offer(cell);
}
// 分配 Gray 编码
Map<String, String> grayCode = new HashMap<>();
int i = 0;
while(!sortedCells.isEmpty()){
String cell = sortedCells.poll();
String code = codes.get(i++);
grayCode.put(cell, code);
}
return grayCode;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 基于 BM25 算法的 SE 系统
采用 BM25 / BM25L 算法实现密文的倒排索引和可搜索加密,流程如下
┌─────────────┐
│ 系统初始化 │
└──────┬──────┘
│
▼
┌─────────────┐
┌──────►│ 身份认证 │◄──────┐
│ └──────┬──────┘ │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ 认证成功? │ │
│ └──────┬──────┘ │
│ │ 否 │
│ └──────────────┘
│
│ 是
▼
┌─────────────┐
│ 文件处理 │
└──────┬──────┘
│
▼
┌─────────────┐
│ 索引构建 │
└──────┬──────┘
│
▼
┌─────────────┐
┌──►│ 范围查询 │
│ └──────┬──────┘
│ │
│ ▼
│ ┌─────────────┐
│ │再次查询? │
│ └──────┬──────┘
│ │ 是
└───────────┘
│ 否
▼
┌─────────────┐
│ 退出系统 │
└─────────────┘
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 身份认证
基于双线性配对的公钥身份认证:初始化两个循环群,对应的整数群,配对函数,以及四份密钥对
身份双向认证:基于双线性验证,采用对方公钥、自身私钥加密,对方利用自身私钥和你的公钥进行认证,反之同理
使用同一个整数 x,计算参与认证的双方的密钥对
H 为哈希函数,ID 为用户 ID,是一个在整数群 Zr 中的元素,注意这里哈希函数的处理为,先将哈希值嵌入 Zr 群,再通过生成元幂运算嵌入 G1 群
计算双线性配对值 k
// 数据私有者和数据用户的 ID
private static Element id_o, id_u, k;
// 用于身份验证(数据私有者和数据用户之间)的两个密钥对
private static KeyPair ao, au;
public static void authKeyInit(){
id_o = Zr.newRandomElement().getImmutable();
id_u = Zr.newRandomElement().getImmutable();
Element x = Zr.newRandomElement();
ao = new KeyPair(hash(id_o.toBytes()).powZn(x).getImmutable(), hash(id_o.toBytes()));
au = new KeyPair(hash(id_u.toBytes()).powZn(x).getImmutable(), hash(id_u.toBytes()));
k = bp.pairing(ao.getSk(), au.getPk()).getImmutable();
}
2
3
4
5
6
7
8
9
10
11
12
13
计算 hash
这里对于多个元素进行哈希值得计算,采用的方式是将三个比特数组参数前后拼接然后通过上述的哈希嵌入得到群 G1 中的元素
// 连接三个比特数组
public static byte[] joinByteArray(byte[] byte1, byte[] byte2, byte[] byte3) {
return ByteBuffer.allocate(byte1.length + byte2.length + byte3.length)
.put(byte1)
.put(byte2)
.put(byte3)
.array();
}
2
3
4
5
6
7
8
计算 CID,这里的sk_{co}是第一步中系统生成的数据所有者的私钥
计算 TID,同样的这里的sk_{tu}也是第一步中数据用户的私钥,pk_{co}是第一步中数据所有者的公钥
// 获取 CID
public static Element getCID(){
Element k1 = bp.pairing(ao.getSk(), au.getPk()).getImmutable();
// 注意这里的命名要和生成元 h 区分开
Element h1 = hash(joinByteArray(ao.getPk().toBytes(), au.getPk().toBytes(), k1.toBytes())).getImmutable();
return h1.powZn(co.getSk()).mul(h).getImmutable();
}
// 获取 TID
public static Element getTID(){
Element k2 = bp.pairing(au.getSk(), ao.getPk()).getImmutable();
Element h2 = hash(joinByteArray(ao.getPk().toBytes(), au.getPk().toBytes(), k2.toBytes())).getImmutable();
return bp.pairing(h2.powZn(tu.getSk()), co.getPk()).getImmutable();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
双线性验证,若相等则认证通过
public static boolean auth(Element CID, Element TID){
Element left = bp.pairing(CID, tu.getPk());
Element right = TID.mul(bp.pairing(tu.getPk(), h));
return left.isEqual(right);
}
2
3
4
5
# BM25 算法
假设我们有一个文档集,视作List<String>,我们需要提取所有文档的关键词,用一个Set存储(去重),同时已知所有文档对应的文档名,即文档 ID
以关键词为行、ID 为列构造这样一个矩阵
| 关键词 \ ID | ID1 | ID2 |
|---|---|---|
其中 R 为 BM25 公式中的一个子式(我们称之为关键词对于单个文档的相关分数)
其中 R 为
矩阵里存的就是 R 值。这样一次查询只需被构造成由 0/1 组成的横向量(命中的关键词位为 1),与矩阵第 j 列做内积即得 q 对文档 dj 的得分——例如查询命中第 7、14 位关键词,取第 j 列这两行的 R 相加即可
各符号含义如下,其中 N 为文档数,n(qi) 为包含词 qi 的文档数
| 符号 | 含义 |
|---|---|
| d / q | 文档 / 查询 |
| qi | 查询中的第 i 个词 |
| f(qi, d) | 词 qi 在文档 d 中的出现频率 |
| |d| / d_avg | 文档长度(词总数) / 文档集平均长度 |
| k1、b、k3 | 调节参数,通常 k1 = 1.2,k3 ∈ (1.2, 2),b = 0.75 |
| IDF(qi) | 逆文档频率,衡量词的重要性 |
注意,当一个文档的关键词个数超过 400 时,判定为长文档,需要采用 BM25L 算法,区别仅在于对每个出现频率 f,变为
# 索引构建
# 文档读入
通过维护的文档名序列从本地读入文件:List<String> names 存名字、Map<String,String> docs 存内容、Map<String,Integer> id 记录各文档在索引矩阵 matrix 中的列下标。读入过程如下
int count = 0;
for(String name: names){
// 从文件中读入文档
docs.put(name, IOUtil.readDocs(name));
// 记录文档并且规定其在矩阵 matrix 中对应的下标
id.put(name, count++);
}
2
3
4
5
6
7
同时记录文档个数 N,并用向量 d 记录各文档的词总数(按空格分割),据此计算文档集的平均词数
# 关键词提取
<dependency>
<groupId>com.hankcs</groupId>
<artifactId>hanlp</artifactId>
<version>portable-1.7.6</version>
</dependency>
2
3
4
5
分词依赖 hanlp(见 DocsUtil.java 的 getKeyword()),提取的关键词存入 Map:既用于去重,也用其值记录在 matrix 中的行下标
count = 0;
// 从 docs 表中取出文档内容
// 通过分词算法提取关键词并存入 keyword 表,值为其在二维数组 matrix 中的下标
for(String content: docs.values()){
List<String> l = DocsUtil.getKeyword("", content);
for(String s: l){
if(!keyword.containsKey(s)){
// 放入关键词,同时规定关键词在矩阵 matrix 中的下标
keyword.put(s, count++);
// 统计关键词在文档中出现次数
n.put(s, 1);
} else {
// 更新关键词在各文档中的出现次数
n.put(s, n.get(s)+1);
}
}
}
matrix = new String[keyword.size()][id.size()];
for(String q: keyword.keySet()){
// matrix 行
int i = keyword.get(q);
for(String s: id.keySet()){
// matrix 列
int j = id.get(s);
// 计算 R
double idf = Math.log((N + 1) / (n.get(q) + 0.5));
// 计算第 i 个关键词在第 j 个文档中的出现频率
int f = DocsUtil.getMatch(q, docs.get(s));
// 若为长文档,需要额外处理 f,加一个常数 a=1
if(d[j] > 400){
f += a;
}
double R = (idf * (f * (k1+1) / (f + k1 * (1 - b + b * d[j] / avg))) * (f * (k3 + 1) / (k3 + f)));
// 加密存储
String encode = VFEPlusUtil.encode((int)R);
matrix[i][j] = encode;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
这里在对评分 R 进行存储时,采用 VFE-Plus 算法进行加密,将整型转换为一个八进制的字符串进行存储,至此索引矩阵构建完毕
# 序列加密
文档 ID 用 AES 对称加密,关键词序列用公钥加密
关键词的公钥加密公式如下
其中,w 是关键词,pk_{svr}是系统初始化时搜索服务器的公钥,sk_{co}和pk_{co}分别是用户的私钥和公钥,h2 和 h1 是两个哈希函数,一定要注意在经过 h2 的嵌入后,哈希值需要映射到整数群 Zr 上(才能进行幂运算),和之前的哈希嵌入(映射到 G1 上)不一样
这里为了简便 h1 = h2,至此加密完毕
# 范围查询
# 关键词匹配
陷门就是对关键词的哈希值再做一次嵌入,用于与已加密的关键词序列比对
沿用上面的关键词加密公式,对 w' 先计算陷门
public static Element getT(String w){
return hashZ(ByteUtil.joinByteArray(k.toBytes(), w.getBytes()));
}
2
3
再以陷门为参数计算
在刚刚生成的 KEYWORD 数组中,采取遍历的方式去匹配这一加密值,若一样则匹配成功,返回其在 KEYWORD 中的下标 i
# 查询向量生成
在关键词匹配的基础上,把整串查询转换为长度为 KEYWORD.length 的 0/1 向量,命中位置置 1
# 相关性计算
查询向量与索引矩阵做内积,即得各文档对本次查询的相关性评分
# 功能测试
功能测试覆盖初始化、认证与可搜索加密全过程,首次涉及五个文档
输出结果
BM25 分数: [4, 1, 0, 0, 0]
测试结果
搜索结果: [test, hello, 6, 8, 15, 16, 17, 18, 19]
搜索时间: 99ms
2