Zhu D, Zhu H, Liu X, et al. CREDO: Efficient and privacy-preserving multi-level medical pre-diagnosis based on ML-kNN[J]. Information Sciences, 2020: 244-262.

隐私保护的kNN能够运用于医疗的某些特定场景，但是现有的方案都是针对单标签数据设计，例如Encrypted Classification Using Secure K-Nearest Neighbour Computation（2019)只能适用于每个样本都只有一个类标签，且类标签只有两类。然而在医疗场景中，一个患者可能同时患有多种不同的疾病，因此当一个样本有多个标签时，如何实现隐私保护的knn分类。

Service provider首先基于k-means聚类来缩小需要计算的医疗实例的范围，然后基于ML-kNN分类为医疗用户提供服务。

加密后的查询向量被发送至service provider并且由service provider直接操作，同时与诊断结果仅仅通过medical user来实现。

该系统主要由配备智能电子设备的医疗用户（MU）和带有参数生成中心的服务提供者（SP）组成。

由于MU的查询向量通常包含用户的敏感信息，所以会对MU的查询向量加密后再发送给SP，此外为了提高系统的整体效率，MU会选择ｋ－means聚类后的簇。

MU选择采用k-means算法进行聚类的分组，以减少计算时间

SP为MU提供在线注册和预诊断服务，在预诊断的过程中，SP和MU交互两次，一次是基于ｋ-means聚类预诊断导航，另一次是基于ML-kNN分类。

SP和MU之间的通信道能够防窃听和防篡改。引入了Bonehead-Lynn-Sham(BLS)短签名技术[1],来为MU和SP之间发送的每个消息创建签名，并且只有signature maker拥有私钥，这也就意味着攻击者不能再通信期间伪造或者是篡改信息，并且所有未公开的信息，在发送给另一方之前都对其进行了加密，也就是说，即使攻击者获得了传输中的消息，也无法正确解密获得原始信息。

威胁模型

该文中，认为MU和SP都是诚实且好奇的，但是MU和SP不会相互勾结，因为MU的医疗数据可能包含MU的隐私信息，SP中的预诊断模型则是属于SP的私有资产。

假设MU输入x,SP输入y，MU执行f1(x,y),SP 执行f2(x,y)，所以MU只能学习到{x,f1(x,y)},SP 只能学习到{y,f2(x,y)}

诚实且好奇的敌手定义：

Preliminaries

Spearman distance:即欧式距离的平方

（建议看一下）先验概率、后验概率以及贝叶斯准则：https://www.cnblogs.com/cyberniklee/p/8072440.html

在日常使用中，如贝叶斯分类、贝叶斯回归、贝叶斯滤波等算法，普遍使用迭代和归一化的方法来计算似然度，为了更好的了解归一化的方法，这里还有一个基础概念，叫全概率公式。

ML-kNN

参考链接 <https://blog.csdn.net/Kodoo/article/details/49905877>

多标签kNN的主要思想是对于每一个新实例(instance)，距离它最近的k个实例(特征空间中与它的距离最小的k个实例)可以首先得到，然后得到这些实例的标签集合，之后通过最大后验概率准则来确定新实例的标签集合。

BLS短签名

参考链接：https://blog.csdn.net/shangsongwww/article/details/89486686

（可以直接看下面的BLS短签名三个步骤，但是该链接能帮助更好的理解BLS）

曲线哈希：哈希函数保持不变，将得到的哈希值作为点的 x 值寻找椭圆曲线上的对应点。通常来说（比如比特币所用的曲线），椭圆曲线有 2²⁵⁶ 个点，而 SHA-256 哈希算法的值也恰好是 256 位。不过，一个有效的 x 坐标，会对应一正一负两个 y 坐标（因为（x, y）和（x, -y）都是曲线 y²=x³+ax+b 上的点）。换句话说，新的哈希算法大约有 50% 的概率在曲线上找到 2 个对应点，另 50% 的概率则一个点也找不到（校对注：因为椭圆曲线只有 2^256 个点，如果要让每个哈希值都能找到对应点，椭圆曲线得有 2^257 个点才行）。

曲线配对：

能够把一条（或2条不同的）曲线上的两个点 P 和 Q 映射为一个数：

e(P, Q) → n

此函数还要有一个重要的特性。即对于未知数 x 和两个点 P 、 Q ，无论哪个点乘以 x，结果相同，即

e(x*P, Q) = e(P, x*Q)

如此，除了乘数交换仍能保持等式成立外，更进一步，以下所有的交换都要保持等式成立：

e(a*P, b*Q) = e(P, ab*Q)

            = e(ab*P, Q)

            = e(P, Q)^(ab)

我们用 pk 代表私钥，P = pk*G 代表公钥（注意不要混淆），m 代表要签名的消息。

为了计算签名，先对消息求曲线哈希 H(m) ，再将获取的结果（曲线坐标点）乘以私钥即可：S = pk*H(m)。大功告成！不需要随机数，不需要额外的步骤，仅仅将哈希结果乘以私钥即可。签名结果是一个曲线上的点，用压缩的序列化格式保存，只占 33 个字节。

提出CREDO方案

CREDO框架

一、系统初始化

(1) SP生成一系列的系统参数，为MU注册提供服务

(2) 计算先验概率和后验概率矩阵

(3) k-means聚类

PK和MU分别有自己的私钥和公钥，MU是在注册阶段生成自己的PK和SK

问题1:为什么要引入k-means聚类？

因为如果MU从ML-kNN的数据中想要获得预诊断的结果，则MU必要计算N次，这里的N是医疗样本数。

引入k-means后能大大的缩小查询的范围

未完待续。。。。。。