Near-Optimal Oblivious Key-Value Stores 实现

源码：https://github.com/felicityin/rb-okvs

有时候需要多方协作来完成一些计算，但每方都不希望暴露自己的数据。所以目标就是确保各方仅仅了解自己的数据，而不要了解到别方的数据。

oblivious key-value stores (OKVS) 可在隐藏 key 的情况下，将 n 个 key-value 编码到长度为 m 的编码中。RB-OKVS 可将 kv 对嵌入到一个用随机矩阵定义的有效可解线性方程组中。矩阵中的每行包括了 w-bit 的随机 band。

volume-hiding encrypted multi-maps (VH-EMM) 的目标是将加密的 multi-maps 外包给一个不被信任的服务器，同时不暴露每个 key 所关联的 value 的数量。

OKVS

• $S ← Encode(I)$：输入是 n 个 kv 对 $I = \left{(k_1 , v_1 ),. . . , (k_n , v_n )\right} ∈ (K × V)^n$，输出是编码 $S ∈ V^m ∪ \left{⊥\right}$

• $v ← Decode(S, k)$：输入是编码 $S ∈ V^m$ 和一个 key $k ∈ K$，输出是对应的 value $v ∈ V$

OKVS 构建

收到 n 个 kv 对 $I = \left{(k_1 , v_1 ),. . . , (k_n , v_n )\right} ∈ (K × V)^n$ 后，使用 key $\left{k_1 , . . . , k_n \right}$ 构建一个随机矩阵 $M ∈ \left{0, 1\right} ^{n×m}$，第 $i$ 行 $M[i] ∈ \left{0, 1\right}^m$ 由第 $i$ 个 key 通过一个哈希函数来生成。

encoding 算法的目标是找到一个解 s，满足 $M · s = [v_1 , v_2 , . . . , v_n ]^⊺$

decoding 算法是对于任意一个 key $k ∈ K$ 和由 encoding 生成的编码 $s ∈ F^m$，先算出 $k$ 对应的行向量 $r(k) ∈ \left{0, 1\right}^m$，然后返回两者的点乘 $r(k_i) · s = M[i] · s = v_i$，也就是返回相应的 value。

构建的矩阵 $M ∈ \left{0, 1\right}^{n×m}$ 中，每一行都包含一个长度为 w-bit 的随机 band $\left{0, 1\right}^w$，band 之外均为 0，也就是一行中至少有 m - w 个元素是 0，例如 n = 3, m = 4, w = 2：

0011 v1
1100 v2
0110 v3

为方便说明，以上例子中，band 中全部取为了 1，实际上应该是随机的 0 或 1。band 的起始位置也是随机的。

然后使用 Dietzfelbinger and Walzer 论文中提到的高斯消除法求解方程组 $M · s = [v_1 , v_2 , . . . , v_n ]^⊺$。具体做法是，先将矩阵的每行根据第一个 1 的位置排序，得到：

1100 v2
0110 v3
0011 v1

然后将矩阵化为上三角矩阵，不过示例中的矩阵已经是上三角矩阵了。最后进行回代。

提升效率

• band 长度是固定的，且比较小，可用 U256 存储，矩阵的的上三角化中只需要用到 U256 的移位和异或。U256 的二进制加速运算具体实现详见源代码。

• 将 band 的第 1 位强制设为 1，可避免用两个位置标记 band：起始位置和起始 1 的位置。

• 将矩阵按照起始 1 的位置排序时，采用 radix sort，如果位置可用 u64 表示的话，最多需要 64 趟排序。

• 并不需要存储整个矩阵，每行只需要存储 band 和 band 的起始位置即可，空间复杂度可由 O(nm) 降低到 O(nw)，而 w 远小于 m

RB-MM

• Setup：输入是 multi-map，输出是 $(K^F, K^E)$ 和加密后的 multi-map EMM。先利用 $K^F$ 将 key 哈希，利用 $K^E$ 将 value 加密。然后将每个 key 对应 value 元组展开，使得 value 元组中的每个 value 都被原先的 key 索引。最后使用 RB-OKVS.Encode 得到编码后的 EMM。
• Query
  • Client：利用 $K^F$ 和 k 生成哈希后的 key，发送到 Server
  • Server：使用 RB-OKVS.Decode 根据 EMM 和哈希后的 key 算出对应的 value 元组，发送到 Client
  • Client：收到 value 元组后，利用 $K^E$ 解密