李秋贤，胡钰，周全兴，周国华
（凯里学院，贵州 凯里 556011）
0 引 言近年来，随着大数据和信息技术的不断发展，以微信、QQ、Facebook等为代表的社交网络平台以前所未有的速度不断收集着用户的隐么数据，各类网络社交平台通过对所收集的数据进行数据分析和数据挖掘，获取数据中蕴藏的价值，从而为平台获取更多的收益和财富。然而，对用户数据进行数据分析和挖掘的行为，常常会导致严重的用户个人信息泄露问题。因此，为了实现保护用户数据隐么安全的目的，数据隐么保护技术应运而生，各种隐么保护技术都在一定程度上保护了社交网络平台中用户数据的隐么安全以及用户的个人信息安全。
由于社交网络中产生的海量数据一定程度上反映了社会的发展规律，很多用户已习惯在各社交网络平台上发布信息进行交流和沟通。但用户在发布各类信息时存在个人隐么泄露的风险，因此能够高效且安全地进行数据分析与挖掘对社交网络平台的数据保护具有一定的意义。目前保护社交网络中数据隐么安全的技术有：基于随机化的隐么保护技术、基于聚类的隐么保护技术和基于Maekov链的特征保持隐么保护技术等。2014年，Fu等人提出一种基于节点分割的匿名社交网络隐么模型，在一定程度上降低了社交网络中各节点隐么泄露的风险。Fu等人针对现有数据融合方法存在融合精度低、数据完整性差等问题，提出了基于云计算的社交网络安全隐么数据融合方法，使得网络数据的融合精度和完整性都得到了优化。
K-匿名是一种有效的隐么保护模型，可以有效地防止隐么泄露。现有很多社交网络隐么保护技术都是基于K-匿名技术来保护用户数据的隐么安全。Hu等人根据社交网络中用户信息泄露问题，提出一种基于k-均值聚类的隐么保护方法，通过局部最优聚类完成对数据的隐么保护。Zhang等人针对海量高维数据提出了基于k-均值的联合聚类算法，使用户数据得到更高的精确度。
由于大多数隐么保护匿名化算法的研究者在设计阶段并未将数据的敏感问题考虑在内，导致经数据挖掘后产生的那些数据精度较低，信息损失度较高。本文就对社交网络中的用户数据进行数据挖掘存在隐么泄露风险这一问题，提出了一种基于K-匿名的社交网络隐么保护方法。通过形式化社交网络平台，对社交网络图中的各节点进行匿名处理，优化社交网络中各用户的社交关系和用户信息，提高社交网络的数据价值，降低信息损失。
1 预备知识1.1 社交网络社交网络又称为社交网络服务，指的是社会关系中的个体信息和社交关系信息，不仅包括社交网站，还涉及社交软件和服务等，可以用一个带标签的无向无权图=（，）来表示，即社交网络是具有个节点的图，其中={v，…v}表示社交网络的点集合，各节点v（=1…，）表示社交网络中的各用户，=（，）表示社交网络中的边集合，和表示各节点之间存在的某种关系。
社交网络中不仅包含图结构数据，每一个用户也同时具有属性数据，如图1所示为简单的社交网络图，该社交网络中包含6个社交网络关系，各用户之间的关系也在本社交网络图中得以展示。由该图可以看出，用户A和A之间的交流和联系（即A与A的通信）可以借助于A节点或A和A节点来实现。
图1 简单的社交网络图
1.2 K-匿名模型K-匿名在数据表中是对所发布数据的一种隐么保护的方法，表示在一个数据表中，至少存在条记录是不可区分的，即任意恶意敌手都不能在数据表中随意区分隐么数据所属的实体。数据K-匿名是指按各个记录的标识属性相近程度将数据表中的数据划分为不同的等价集合。形式化表示即：给定数据表以及标识属性集合中取值相近的等价集合，若数据表中的任意一个等价集合至少有条记录，则称数据表满足K-匿名。
在本文中，我们创建了简单的个人信息表格数据，如表1所示。以表格形式列出医院病人的疾病情况，用以详细说明K-匿名模型的定义和识别。表1中共有6条数据记录，数据包含姓名、性别、年龄和疾病类型等四个属性。其中“姓名”可以确定个人的身份信息，因此表1中“姓名”属于标识符属性。
表1 医院病人个人信息表格数据样例
表1中“疾病类型”属于个人的隐么信息，“性别”属于非敏感信息。因此我们在进行K-匿名处理时，需要将标识符属性和非敏感信息进行移除，从而得到匿名后的表格，如表2所示。
表2 匿名化后医院病人个人信息表格数据
以表2匿名化后的数据为例，K-匿名是指：如果把值设为3，当恶意攻击者想要获取病人的个人信息时，若恶意攻击者知道他要攻击的目标对象年龄在20至50岁之间，从表2中我们可以发现，年龄在20至50岁之间的等价集合中存在3条数据记录，攻击者能够顺利攻击的概率为1/3，因此我们认为该表满足了3-匿名模型。
2 基于K-匿名社交网络模型本文所设计的基于K-匿名的社交网络模型是通过保护社交网络节点隐么的形式来保护数据的隐么安全的，在基于K-匿名的社交网络模型中，每一个网络用户节点都拥有不少于-1个候选节点，从而使得恶意攻击者识别目标节点的概率小于1/。如图2所示，我们将原始的社交网络通过社交网络图进行形式化，图2是用户关系的社交网络图，各节点表示社交网络中的各用户，各边线表示各节点与其他节点存在的某种关系。
图2 原始社交网络关系图
在本方案中，我们通过修改社交网络图的顶点或边的方式来实现匿名，即在社交网络图中增加社交关系，通过增加边的方式实现社交网络的匿名化。如图3所示，我们在原始社交网络中增加3条社交关系，通过黄色边线标记从而实现3-匿名化。即使恶意攻击者知道用户有两条社交关系，但也无法以高于1/3的概率正确推断出哪个节点为用户。因此，我们实现了3-匿名化，保护了用户个人信息的安全和隐么性。
图3 匿名化后社交网络关系图
3 基于K-匿名设计网络隐私保护方案本文提出的基于K-匿名的社交网络隐么保护方案是基于K-匿名模型实现的，即方案中社交网络节点的隐么保护是通过改变节点或边的方式来实现匿名化，社交过程采用全同态加密技术实现对节点发送消息的加密，从而保证用户个人以及消息的隐么性。该方案主要由4个算法组成，分别为节点K-匿名算法、密钥生成算法、加密算法和解密算法，算法的详细描述为：
（1）节点K-匿名算法。根据所设计的社交网络模型输入对应的社交网络图和安全参数，使用K-匿名算法将图进行K-匿名处理，形成匿名化后的图后将其输出。
（2）秘钥生成算法。输入安全参数和匿名化后的社交网络图，通过全同态加密算法随机生成公钥和么钥对（PK，SK）。
（3）加密算法。输入秘钥算法生成的公钥PK和社交网络平台中需要加密的消息，利用加密算法产生对应的密文消息。
（4）解密算法。输入公钥所对应的么钥SK需要解密的消息，利用解密算法输出加密密文对应的明文消息，只有网络结构中相应的节点才能进行访问和解密。
在该方案中，只有社交网络节点中的用户才能从方案中获取公钥对应的么钥，恶意敌手无法在多项式时间内以目标节点的图结构信息作为先验知识来攻击用户的隐么，以及破坏数据的安全性。
4 方案分析本文主要对方案的安全性进行以下分析：
定理：在DDH（Decision Diffie-Hellman）假设下，本文所提出的基于K-匿名的数据隐么社交网络保护方案是安全的。
证明：假设有恶意攻击者以不可忽略的优势攻击本方案中的节点用户，在节点K-匿名算法阶段，恶意攻击者以目标节点v的社交网络图结构信息为背景知识，对发布的图进行攻击，由于是经过K-匿名化的结构图，所以恶意攻击者能够识别目标节点v的概率为1/。
然而，在消息发布传播阶段，我们通过构建模拟器P来模拟秘钥的生成，恶意攻击者A将两次发布的消息，分别传递给模拟器。模拟器通过抛掷硬币的方式选取=（0，1），从而猜测消息的么钥，在两次实验过程中恶意攻击者很有可能无法区分消息和′，若模拟器猜测=，则模拟器可以输出正确的消息，否则将输出消息′。由于意攻击者很有可能无法区分消息′和，因此在DDH判定下，本文所提出的基于K-匿名的数据隐么社交网络保护方案是安全的。
5 结 论本文为了解决社交网络平台中用户个人信息安全、传播数据的隐么泄露问题，构造一种新的社交网络保护方案。通过设计基于K-匿名和全同态加密技术的社交网络的安全模型保护方案，进一步保证了社交网络平台中隐么数据的安全性。在未来的工作中，我们将通过平衡各用户节点的效用来保证社交网络用户数据的隐么安全。
