面向位置感知推荐系统的隐私保护方法

摘要

本发明涉及一种面向位置感知推荐系统的隐私保护方法。本发明公开了一种基于密码学的位置感知推荐系统的隐私保护方法，主要解决现有系统在保护推荐用户隐私的同时会带来信息损失，降低推荐服务质量的问题。其技术方案是：先将所有的历史数据均以密文的形式在云计算平台进行存储；服务提供者采用Paillier加密算法计算推荐用户访问过的各位置点之间的相似度；推荐用户和服务提供者采用Paillier加密算法、El-Gamal加密算法和可比较加密算法计算出满足用户要求的推荐结果。仿真测试的结果表明法能够在保证了推荐用户的隐私数据及服务提供商的私有数据的安全的条件下实现快速高效的推荐服务。可用于云计算环境下数据外包系统中的隐私保护。

说明书

技术领域

本发明属于信息安全领域，涉及一种隐私保护方法，可用于云计算环境下数据外包系统中的隐私保护。

背景技术

随着城市计算和GPS设备的快速发展，基于位置的服务LBS已经广泛应用在人们的日常生活中，为我们的生活提供了更多的便利。例如，Foursquare允许推荐用户检索自己感兴趣的位置点POI，并允许推荐用户在离开时对所获得的服务进行评价。然而，随着各种各样的服务的出现，大量的LBS服务充斥在我们的生活当中，因此，如何快速高效、准确的获取我们想要的服务成为推荐用户亟需解决的问题。推荐系统的出现正是对如上所述问题的完美解决。推荐系统可以根据推荐用户的喜好以及推荐用户的评价信息进行推荐预测，并将预测结果反馈给服务请求者。然而，与传统的推荐系统相比，基于位置感知的推荐系统不仅要考虑推荐用户的评价信息，还要考虑推荐用户的时空位置信息。因此，基于位置感知的推荐系统能够为推荐用户提供指定区域内的推荐服务。

目前，推荐系统主要的挑战在于如何在大量的位置点中实现安全高效地为推荐用户进行推荐。然而，传统的推荐技术无法直接应用于LBS服务的推荐，原因主要有如下两点：首先，由于时空位置数据是多样性的并且是快速变化的，传统的推荐系统需要消耗大量的资源来存储和计算这些数据，因此，大量的LBS服务提供者开始借助云计算服务来实现数据的存储和计算。通过将推荐用户数据和推荐计算迁移到云计算平台，服务提供者可以在保证推荐质量的前提下大大降低自身资源的消耗。例如，Netflix在2015年8月份关闭了其自身拥有的最后一个数据中心，将所有的数据迁移到亚马逊云计算平台进行存储。然而，将数据迁移到第三方云计算平台又将带来其他的隐私保护问题。由于推荐用户提交的数据和推荐结果包含许多隐私信息，例如，位置信息，偏好信息等，云计算平台服务器可以通过这些信息推断哪个推荐用户什么时间位于哪个位置。因此，云计算平台可能会跟踪某些推荐用户或者将推荐用户的偏好信息发送给其他攻击者。如果服务提供商不能很好的保护推荐用户的隐私信息，推荐用户可能会因担心泄露隐私而拒绝使用服务提供商提供的推荐服务，所以，隐私保护问题是阻碍推荐系统服务发展的另一个重大因素。

鉴于以上因素，保护推荐用户的隐私是基于位置感知推荐系统发展的关键。然而，数据的保护不仅仅只包括推荐用户的隐私信息，还包括服务提供商收集到的推荐用户历史数据信息。服务提供商作为一家商业公司，其收集到的数据可以认为是其私有资产，不能无偿的对外公开，因此，当服务提供商将其拥有的数据发送到云计算平台时，必须对数据处理后再上传，使得云计算平台无法获得其原始信息。

现有的推荐服务隐私保护，如：“用于推荐服务的隐私保护系统的架构”专利申请(申请号：201380031170.X)和“基于关联规则满足推荐用户隐私保护的个性化推荐方法及系统”(申请号：201410283430.9))大都采用匿名机制或者差分隐私机制，因此，这些系统在保护推荐用户隐私的同时也会带来一定的信息损失，从而降低了推荐服务质量。

在半可信的云计算环境中进行数据外包，其安全性必然是系统设计实现的关键，同时，如何在保证安全性的前提下，能够为推荐用户提供高质量的推荐服务也是位置感知推荐系统设计的关键所在。

发明内容

本发明要解决的技术问题是针对位置感知推荐系统中的隐私问题，提出一种面向位置感知推荐系统的隐私保护方法，以保证推荐用户隐私安全和推荐用户信息的正确性，提高推荐服务质量。

本发明的技术思路是：针对位置关联数据的多样性以及动态变化性，提出推荐系统服务提供商将推荐用户的历史数据存储在云端，服务提供商只需要定期收集推荐用户的历史数据，并在加密后上传给第三方云计算平台；针对数据外包后的安全问题以及推荐用户的隐私问题，提出基于密码学理论的隐私保护机制，使得服务提供商在保证推荐用户隐私安全的前提下为推荐用户提供推荐服务。其实现方案如下：

面向位置感知推荐系统的隐私保护方法，其特征在于将密码学理论以及数据外包计算理论应用到推荐系统中，其步骤包括：

(1)服务提供者对推荐用户位置点的属性信息进行扩展，并对扩展后的属性信息进行加密，再将加密后的信息发送给云计算平台进行存储；

(2)服务提供者定期收集推荐用户的历史评价信息,并对收集到的历史评价信息利用Paillier加密算法加密后发送给云计算平台；

(3)云计算平台收到服务提供者发送的历史评价信息后，将其整合到已经存储在云端的数据集中，再对该数据集进行聚合运算，并将聚合结果发回给服务提供者；

(4)服务提供者解密聚合结果并计算各个位置点之间的相似度，再对相似度矩阵进行转化后，发送给云计算平台进行存储；

(5)推荐用户直接向云计算平台发送用可比较加密算法加密后的感兴趣区域，云计算平台收到数据后，利用可比较加密算法筛选出满足推荐用户感兴趣区域内的位置点；

(6)云计算平台再对筛选出位置点的属性信息用可交换加密算法加密，得到双层加密的结果,同时，提取该推荐用户的历史评价信息和对应的相似度信息，并进行聚合运算，再将双层加密的结果和聚合结果发送给服务提供者；

(7)服务提供者收到云计算平台发送的双层加密的结果后，对其用可交换解密算法解密内层加密，得到推荐用户密钥加密的属性信息，同时，对云计算平台的聚合结果用Paillier算法解密并进行计算，得到预测信息，并将该属性信息和预测信息发送给推荐用户；

(8)推荐用户对收到的属性信息用可交换解密算法解密，得到属性信息明文，同时对收到的预测信息进行计算，得到预测评价信息明文，依次选择预测评价信息最高的k个位置点,并根据其属性信息在推荐用户感兴趣区域上显示这k个位置点。

本发明具有如下优点：

1.服务提供者用Paillier算法加密历史评价信息，使得推荐用户的历史评价信息在云计算平台上以密文形式计算，保证了云计算平台上历史评价信息的安全性。

2.服务提供者用可交换加密算法对位置点的属性信息加密，用可比较加密算法对扩展出的属性信息加密，使得位置点的属性信息在云计算平台上以密文形式计算，保证了云计算平台上位置点的属性信息的安全性。

3.推荐用户用可比较加密算法对其感兴趣的区域加密，云计算平台用可交换加密算法对位置点属性信息加密，使得推荐用户的位置信息和预测推荐结果以密文的形式在服务提供者和云计算平台上进行计算，保证了预测推荐结果在服务提供者和云计算平台上的数据安全。

综上，本发明保证了推荐用户的隐私数据及服务提供商的私有数据的安全，实现了面向位置感知推荐系统的隐私保护。

附图说明

图1是本发明使用的位置感知推荐系统模型图；

图2是本发明的实现流程图；

图3是本发明中计算相似度过程中历史评价信息聚合的示意图；

图4是本发明的推荐质量仿真评估图。

具体实施方式

以下结合附图对本发明进行详细描述：

参照图1，本发明使用的一个具有隐私保护功能的位置感知推荐系统服务模型，由可信中心、服务提供者、云计算平台以及推荐用户构成。可信中心主要负责生成密钥，并为推荐用户和服务提供者分配密钥，在该系统中，可信中心是唯一完全可信的实体；服务提供者主要为推荐用户提供推荐服务，服务提供者会定期收集推荐用户的历史评价信息，并将收集到的信息发送给云计算平台存储，在该系统中，服务提供者具有有限的存储资源和计算资源，因此，其会将收集到的信息外包给云计算平台进行存储和处理，同时，服务提供者是半可信的，其能够为推荐用户正确地计算推荐结果，但也会“偷窥”推荐用户的隐私；云计算平台是系统中主要的存储和计算中心，拥有无限的存储和计算能力，主要负责安全存储服务提供者上传的信息，并辅助服务提供者为推荐用户进行推荐计算，在该系统中，云计算平台也是半可信的，其能够正确的帮助其他推荐用户处理数据，但是也对服务提供者的源数据和推荐用户的隐私信息感兴趣。

本发明基于图1系统隐私保护分为两个阶段：相似度计算阶段和推荐用户预测评价信息阶段。相似度计算阶段主要是指服务提供者数据外包的过程，在该阶段中，云计算平台除了对数据进行安全存储外，还负责在密文的情况下辅助服务提供者计算各位置点之间的相似度；推荐用户预测评价信息阶段则主要负责在保证推荐用户隐私安全的情况下计算满足该推荐用户请求的推荐结果。

参照图2，本发明的实现步骤如下：

步骤1，服务提供者对位置点属性结构体进行扩展并分别加密。

服务提供者把各个位置点的属性信息存储在云端，这些属性信息包括位置信息、名称代号等。为了保证这些属性信息在加密后还能恢复，同时保证加密后的位置坐标具有可比较性，需要对该结构体进行扩展，步骤如下：

1a)服务提供者将位置点的属性信息<I_N,I_L>扩展为<＜I_N,I_L>,I_L>，其中I_N表示各位置点的名称代号坐标集合，I_L表示各位置点的位置坐标集合；

1b)服务提供者对原属性信息＜I_N,I_L＞用服务提供者的可交换加密密钥加密得到密文对扩展出的位置属性＜I_L＞用可可比较加密算法加密得到密文Enc(I_L)；

1c)服务提供者将密文发送给云计算平台进行存储。

步骤2，服务提供者收集历史评价数据并将数据外包给云计算平台。

2a)服务提供者会定期收集推荐用户的历史评价信息，生成历史评价信息矩阵R_t，并将对信息矩阵进行拷贝得到备份矩阵R_t'；

2b)服务提供者用Paillier加密算法对历史评价信息矩阵R_t加密生成的密文

2c)按照Γ(m,s,α)＝s*(m*α²+c)的转化规则对备份矩阵R_t'进行转化,得到转化后的结果为：A_t＝Γ(R_t',s,α)，其中s为随机数，c为随机数，α为大素数，m表示需要转化的数据，A_t表示历史评价信息转化矩阵。

2d)服务提供者将密文发送给云计算平台。

步骤3，云计算平台对历史评价信息进行聚合运算。

参照图3，本步骤具体实现如下：

3a)云计算平台接收到服务提供者发送的密文后进行整合：

首先，将对历史评价信息矩阵R_t加密生成的密文和云计算平台上已经存储的对历史评价信息矩阵R'加密生成的密文进行整合，得到整合后的对历史评价信息矩阵R加密生成的密文

然后，将历史评价信息转化矩阵A_t和云计算平台上已经存储的历史评价信息转化矩阵A'整合，得到整合后的历史评价信息转化矩阵A；

3b)将上述密文与整合后的历史评价信息转化矩阵A进行聚合运算，得到聚合矩阵B：

其中，r_ji表示第i个推荐用户对第j个位置点的历史评价信息，a_ki表示第i个推荐用户对第k个位置点的历史评价信息的转化信息，v表示推荐用户个数，

经过聚合运算后，使得存储在云计算平台的数据矩阵得到了压缩，降低了对服务提供者存储能力需求；

3c)云计算平台将聚合矩阵B发送给服务提供者，服务提供者在有足够的空间中进行存储。

步骤4，服务提供者计算各个位置点之间的相似度。

4a)服务提供者收到云计算平台发送的聚合矩阵B后，用Paillier解密算法对聚合矩阵B进行解密，得到聚合后的明文矩阵其中表示用Paillier解密算法对矩阵B解密；

4b)服务提供者对聚合后的明文矩阵B'的元素b'_jk进行转化，得到位置点j与位置点k的评价信息的点乘运算结果：

4c)对d_jk进行运算得到第j个位置点与第k个位置点之间的相似度sim_jk:

其中s^-1表示随机数s的逆，表示第j个位置点的所有评价信息的模，表示第k个位置点的所有评价信息的模；

用第j个位置点与第k个位置点之间的相似度sim_jk构成相似度矩阵Sim；

4d)对相似度矩阵Sim进行转化：

由于服务提供者具有有限的计算资源，因此，本发明将相似度矩阵发送到云计算平台端进行存储，并进行响应客户的请求。但是，相似度矩阵作为服务提供者的私有财产，不能直接以明文的形式存储在云计算平台中，所以本发明按照Γ(m,s,α)＝s*(m*α²+c)的转化规则对相似度矩阵Sim进行转化,得到转化后的相似度矩阵F＝Γ(Sim,s,α)；

4d)服务提供者将转化后的相似度矩阵F发送到云计算平台进行存储。

步骤5，云计算平台筛选出位置点。

5a)推荐用户使用可比较加密算法对其感兴趣的区域{x_u±Δx,y_u±Δy}进行加密，得到密文Enc(x_u±Δx,y_u±Δy)和Der(x_u±Δx,y_u±Δy)，其中(x_u,y_u)表示推荐用户的坐标，Δx表示x_u的变化范围，Δy表示y_u的变化范围，Enc(x_u±Δx,y_u±Δy)表示用可比较加密对用户感兴趣区域范围加密的密文，Der(x_u±Δx,y_u±Δy)表示用可比较加密对用户感兴趣区域范围加密生成的令牌；

5b)推荐用户向服务提供者注册服务请求，服务提供者发送参数α给推荐用户；

5c)推荐用户将上述密文Enc(x_u±Δx,y_u±Δy)和令牌Der(x_u±Δx,y_u±Δy)，s′,β²,α²γ发送给云计算平台，其中s′为一个随机数，β为一个大素数，γ为一个大素数；

5c)云计算平台收到推荐用户的密文和令牌后，利用可比较加密算法筛选出推荐用户感兴趣区域内的位置点，筛选条件如下：

其中param表示可比较加密算法的参数，Enc(v_ix)表示利用可比较加密对云计算平台上存储的位置点的横坐标加密的密文，Enc(v_iy)表示利用可比较加密对云计算平台上存储的位置点的纵坐标加密的密文；

5d)将筛选出位置点的属性信息保存在集合H中。

步骤6，云计算平台加密位置点属性信息并对用户的信息进行聚合运算。

6a)云计算平台对集合H中的位置点的属性采用可交换加密算法再次加密，得到密文其中I'_N表示集合H中位置点的名称代号坐标集合，I'_L表示集合H中位置点的位置坐标集合，表示服务提供者可交换加密公钥对位置点属性(I'_N,I'_L)加密的密文，表示用推荐用户的可交换加密公钥对加密的密文；

6b)云计算平台提取推荐用户的历史评价信息和集合H中位置点与该推荐用户访问过的位置点的相似度信息；

6c)对提取的相似度信息求和运算，对提取的评价信息进行聚合计算：

其中，t_i表示位置点i上所有相似度之和，q_ui表示推荐用户u的历史评价信息的聚合结果，f_il表示转化后的位置点i与位置点l之间的相似度，z_il为随机数，r_l表示推荐用户的历史评价信息，N表示Paillier加密算法中的参数,t_i构成相似度集合T，q_ui构成评价信息集合Q；

6d)云计算平台将数据集发送给服务提供者。

步骤7，服务提供者计算得到含有随机数的预测信息。

7a)服务提供者收到云计算平台发送的双层加密的结果后，对其用可交换加密算法解密内层加密，得到推荐用户密钥加密后的属性信息

7b)服务提供者对收到的评价信息集合Q用Paillier解密算法解密得到明文

7c)按照逆转化转化规则，对上述集合T和进行逆转化，计算得到含有随机数的预测信息

7d)服务提供者将属性信息和预测信息R'发送给推荐用户。

步骤8，推荐用户依次选择预测评价信息最高的k个位置点。

8a)服务提供者对收到的属性信息用Paillier解密算法解密，得到筛选区域的预测评价数据〈I'_N,I'_L〉；

8b)推荐用户对收到的预测信息R'进行逆转化，得到其对应的明文预测评价信息R_p＝Γ^-1(R',s',β)；

8c)推荐用户依次选择预测评价信息最高的k个位置点,并根据其属性信息在推荐用户感兴趣区域上显示这k个位置点。

本发明的效果可通过以下实验进一步说明面向位置感知推荐系统的隐私保护方法的推荐质量。

本发明采用Foursquare真是数据集对本发明进行测试，该集合包含2153471个推荐用户对1143092个位置点的2809581个历史评价信息。通过仿真程序测试，得到本发明推荐质量的测试结果如图4所示。

测试结果表明，预测评价信息误差个数为0的概率为78.3％，预测评价信息误差个数为4和5的概率分别为7.5％和3.8％，说明本发明的推荐质量足够高，能满足用户的需求。