SortingHat私有决策树评估

私有决策树评估方案

1. 论文的目的的贡献 私有决策树评估（PDTE），即服务器有一个决策树分类模型，而客户使用该模型对其私有数据进行分类，而不向服务器透露数据或分类结果。SortingHat是基于FHE的非交互式安全决策树分类方案。 (1) 设计了一个快速的同态比较函数，其中一个输入可以是明文形式； (2) 在FHE设置中设计了一个高效的二进制决策树评估技术，即文中的同态转码(Homomorphic Transcipher)，与同态比较一起用于评估私有决策树分类器，提高几个数量级的运行时间； (3) 把FiLIP流密码应用于同态比较，降低了通信成本和转码时间。

2. 对照论文 对照论文为Non-interactive private decision tree evaluation

3. 当前解决此问题的现有技术 私有决策树评估（PDTE）的问题可以用安全两方计算问题的技术来解决[HV16,KO04]。但是基于Yao’s garbled circuits[Yao86,BHR12,KRRW18]的此类问题的通用算法并不适合机器学习即服务，只因它们产生很高的计算开销，且需要很多轮的交互，这导致了很高的通信开销。

4. 问题核心 这个方案设计的目的就是保证用户的数据和结果的信息不泄漏给服务器，然后降低计算复杂度和通信量。

5. 同态加密 文中算法可用任何类似GSW的同态加密方案来实例化，例如FHEW、TFHE、GAHE或FINAL。这些方案的有点是利用非对称噪声传播，在一长串同态乘法后保持噪声开销的可加性。 FiLIP加密：FiLIP 是一种基于滤波器置换器和非线性函数的二进制流密码 。 加密和解密算法工作如下： 设 $ K \in {0, 1}^z $ 为密钥； 对于消息的每一位$m_i$，我们使用前向安全 PRNG(伪随机数生成器) 来采样。定义$s_i$是$K$上$z$比特向量，$P_i$是$z$到$z$上的置换（排列），$w_i$是$z$维的二进制向量，称作白化。对于某个具体函数$ f : {0,1}^z \rightarrow {0,1}$，我们计算 $c_i := m_i \oplus f(P_i(s_i) \oplus w_i) \in {0, 1}$。

6. 决策树和秘密决策树估计(PDTE) 定义一个函数 $ T : Z^n \rightarrow {\tau_0, \dots , \tau_k−1 } $ 将属性向量 $ x = (x_0, \dots , x_n−1) $ 映射到有限的分类标签集 ${\tau_0, \dots , \tau_k−1 } $。决策树是具有决策节点和叶节点集合的二叉树结构。 决策树模型 $ \mathcal M = (\mathcal T , t, a) $ 由函数 $\mathcal T$ 和节点函数$t,a$组成。其中，$t : [0, m-1] \rightarrow \mathbb{Z}$决策树节点阈值函数，$a : [0, m-1] \rightarrow [0, n-1]$是节点属性索引函数。 $\mathsf{lab}: [m, M-1] \rightarrow {\tau_0, \dots, \tau_k -1 } $ 是每个叶节点分配一个标签函数。

• 节点索引，给定一棵决策树，通过广度优先遍历计算顺序定义索引，即从索引为 $0 $的根开始，如果树是完整的，则索引为 $v $ 的节点的左子节点为 $ 2v + 1 $，并且右孩子 $2v + 2$。使用这种索引方案，树的叶子从左到右读取，对应于排序$ l_0, \dots, l_{2^s}−1 $，其中 $2^s$ 是完整树的节点数。
• 决策树评估，给定一个属性向量 $ x $和一个决策树模型 $ \mathcal M = (\mathcal T , t, a) $ ，然后从根节点开始，决策树评估在每个决策节点 $ v $处评估索引$ v \in [m] $处评估的决策 $ b \leftarrow [ x_{a(v))} \ge t(v) ] $，并移动到右侧（如果$ b = 0 $）或左侧（如果 $ b = 1$ ）子节点。评估返回到达的叶子的标签作为计算结果，用 $ \mathcal T(x)$ 表示。
• 私有决策树评估（PDTE），客户端发送一个向量$x = (x_0, \cdots , x_n-1) $，服务器存在一个私有的决策树模型$ \mathcal M = (\mathcal T , t, a) $，评估功能函数 $ \mathcal T(x) $ 的只向客户端透露 $ \mathcal T(x) $（除了客户端已经知道的关于树的元参数），而服务器没有学到任何关于 $x $ 的信息。

1. 同态比较函数: í 在决策树中，客户端发送的输入值与每个节点的阈值进行比较。需要一个同态的比较函数，如果输入值大于阈值$d$，则输出$1$，否则输出$0$。

输入: $c = \mathsf {RLWE}_{N,t,q} (X^\mu) = (a, b) = (a, a \cdot s + \Delta \cdot X^u + e)$, $c$为密文。

输出：$c ^\prime = \mathsf {RLWE}_{N,t,q} (\mu(X))$; $ \mu_0 = 1 $ if $ \mu \ge \bar t $ else $ \mu_0 = 0 $，其中 $ \mu_0 $ 是常数项.

1. 定义 $ T(X) := X^{2N-N} + X^{2N - (N-1)} + \cdots + X^{2N - \bar t} $.
2. 令$ c^\prime = (a^\prime, b^\prime) = (a \cdot T(X), b \cdot T(X))$ .
3. 由于$ \bar t \leq \mu \leq N $，可以判断$ \mu_0 = 1 $ if $ \mu \ge \bar t $ else $ \mu_0 = 0 $ .