Encrypted Classification Using Secure K-Nearest Neighbour Computation.读书笔记

Reddy B P, Chatterjee A. Encrypted Classification Using Secure K-Nearest Neighbour Computation.[J]. Space, 2019: 176-194.

该论文是19年Reddy等人发表在Space期刊上，以下内容是本人在阅读该论文时的一些读书笔记整理，若有不足之处欢迎指正。

 

摘要：

对FHE数据的处理不能直接按照传统的指令执行流程进行，需要基于特殊电路的算法表示。

在本文中，我们着重于在加密数据上实现k近邻(KNN)计算，其中数据使用广义加密表示存储。

这种表示法可以很容易地扩展到支持多个加密学习者的加密集成学习框架中，以获得更高的精度。

 

本文指出secure knn classification using VHE(2018)只适用于低维度的加密数据,关于secure kNN classification using VHE ,我上传的资源中有个关于他的PPT汇报，有兴趣的也可以去看看。

 

安全性：

尽管云计算有很多承诺，但安全性仍然是使云适应全球应用程序的主要瓶颈。

由于对谁可以访问敏感数据的控制不完全，以及对进出云应用程序的数据的监视能力有限，因此从云域窃取数据非常常见。

 

为什么要如此重视云计算的安全性？以及如何实现云数据安全？

如何实现云数据安全：

最直接的方式就是对所有的数据做加密处理，FHE可以在密文上做处理，但是所有现有的FHE方案是基于电路设计的，不适用于传体算法的非电路表示。因此需要对加密形式的数据进行分类或者回归分析，要将合适的算法转化为相应的加密算法

注意：这个方案是不完整的，并且在某种程度上同态的，因为操作之后的结果超过了素数模数p（噪音过大？），那么解密就失败了。（即最后的结果c>p）

为了解决该问题，Gentry通过生成一个包含解密提示的公钥来解决这个问题。此提示允许对加密域中的中间结果进行同构解密，这意味着参数的明文仍然未知。有了密文空间中的明文，就有可能对明文进行重新加密，从而产生具有降低噪声的明文的新密码。本文中使用TFHE库作为底层同态方案，标准化过程引用参考文献[41]

 

注：

TorusFHE (TFHE）方案对按位加密的输入进行操作，并尝试进行优化以实现任意计算。在需要按位加密输入的情况下，例如在涉及加密数字比较，排序或类似非多项式运算的计算中，诸如TFHE 之类的方案可能是最有效的解决方案。TFHE 方案具有相同名称的库

来自 <https://blog.****.net/weixin_43476788/article/details/105327360>

 

注：

显然AND电路和XOR电路是属于permitted functions集合里的（为什么？因为AND电路是对应的是两个二进制位相乘，XOR对应的是两个二进制位相加，上述同态方案肯定能够正确执行这两个运算，因为就是一次乘法或者一次加法，既然能够正确执行，所以它们就属于permitted functions集合）。

 

可以通过重加密技术降低噪音呀！具体如何做呢？很简单：给AND电路上接一个解密电路，给XOR电路上也接一个解密电路，任何密文在进入AND电路或XOR电路之前，先让它进入解密电路进行重加密，之后从解密电路里出来的密文就是一个类似于新鲜密文的密文，噪音比进来前降低了，然后再让这个新的密文进入AND电路或XOR电路，这样我们就可以对密文正确的做任意功能的计算了！而接了解密电路的AND电路或XOR电路就称为增强电路。

 

来自 <https://zhuanlan.zhihu.com/p/60281238>

 

kNN算法流程图如下：

 

加密的减法计算：

考虑到b位特征大小，需要设计b位减法器进行距离计算。首先按位设计减法电路，然后在循环中迭代逐位减法器进行b位减法计算。

对于位减法，半减器设计在两位个位(X`和Y`)之间。如果下一位出现了借位，那么我们需要完成三个位之间的减法。因此，这个具有两个输入位和借位输入的全减法器产生两个输出，Difference(D)和Borrow Out(Bout)，根据以下公式

 

 

这里有一些关于数据的流动，汇报的时候留下的墨迹，就不去掉了。

 

在计算绝对值的时候，我们需要预先计算 x`-y` 的正负性,这里是通过MSB来判断的，如果MSB是Ｅnc(0)，直接计算即可，如果MSB是Enc(1)，需要将其转换为 -(x`-y`)，具体见参考文献[28]，一个负数用其补码来表示，然后计算结果加上Enc(1)。如果 x-y<0 那么|x-y|=-(x-y)

距离排序

参考文献[29]证明，冒泡排序适用于加密数据的排序问题（从小到大），有兴趣的可以看看参考文献[29]

if dist[i] > dist[i+1].则交换二者的顺序

 

如何判断 dist[i]` 与 dist[i+1]`之间的大小关系？当 dist[i]` > dist[i+1]`时，MSB的值为Enc(0),进入FHE_mux1,此时排序数组的 i 位置将保存lower value作为FHE_mux1的输出。具体流程见图六。最终能够获得一个从小到大的排序数据，之后根据选定的K值，选取k个最近的距离点，根据投票原则，分配测试数据所属的类标签。

 

kNN投票原则和分配类标签

需要注意的是，该文中只设计到positive 和 negative 两个标签，通过计算k个距离点中，positive and negaative标签的和大小比较，判断属于哪个类标签。

 

下图7执行Li( 此处的类标签Li被加密成Enc(1)或者是Enc(0) )和Enc(1)之间的相等性比较,比较结果发送给FHE_mux1和FHE_mux2，如果Li=Enc(1),则positive+1,否则negative+1

negCount`和posCount作为FHE_sub的输入，如果negCount>posCount,则输出MSB=Enc(0),即意味着该测试数据属于negative class label.  反之…….

 

结果分析

数据集采用的是UCI机器学习中的鸢尾花数据集，有150个样本，每个样本包含一个类标签和四个特征数，所有样本共划分为三类，这里为了能够实现二进制分类，只保留Iris versicolor和 Iris setosa两类记为postive和negative，各有50个样本

实验结果见论文P190

 

该论文实验结果与参考文献[2]做对比，但是实际上[2]中使用的是Lsun数据集，有400个样本，每个样本有两个特征，3个集群的执行时间是0.85个月，大约是2,203,200s,而且是基于k-means聚类算法

 

总结

能够提供准确的隐私保护训练和分类，可以用于某些特定的医疗或者是金融长期决策场景，但是其性能限制，不适用于实时的应用程序

由于该论文使用了TFHE库，只支持单线程计算，无法做多线程并行计算，从而性能受到了限制。

在未来的工作中，作者打算提高底层库的性能，支持适当的并行处理和GPU或FPGA加速，以提高整体性能。

 

参考文献

2. J¨aschke, A., Armknecht, F.: Unsupervised machine learning on encrypted. In: Cid,C., Jacobson Jr., M. (eds.) SAC 2018. LNCS. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7 21

6. Kesarwani, M., et al.: Efficient secure k-nearest neighbours over encrypted data.In: EDBT (2018). https://doi.org/10.5441/002/edbt.2018.67

7. Yang, H., He, W., Li, J., Li, H.: Efficient and secure kNN classification over encrypted data using vector homomorphic encryption. In: 2018 IEEE International Conference on Communications (ICC), pp. 1–7 (2018)

8. Chen, H., et al.: Logistic regression over encrypted data from fully homomorphic encryption. BMC Med. Genomics 11, 81 (2018)

28. Chatterjee, A., Sengupta, I.: Translating algorithms to handle fully homomorphic encrypted data on the cloud. IEEE Trans. Cloud Comput. 6, 287–300 (2018)

29. Chatterjee, A., Sengupta, I.: Searching and sorting of fully homomorphic encrypted data on cloud. IACR Cryptology ePrint Archive 2015: 981 (2015)

41. Chillotti, I., Gama, N., Georgieva, M., Izabach`ene, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016).
https://doi.org/10.1007/978-3-662-53887-6 1