本发明公开了一种基于稀疏数据集的隐私保护关联规则挖掘方法，主要解决现有挖掘方法需要引入额外计算开销以及隐私泄露的问题。方案包括：1)系统初始化；2)数据拥有者加密上传数据；3)数据挖掘者加密上传查询；4)双云计算查询与交易的内积密文集合，并计算查询的支持度密文；5)双云安全比较支持度和支持度阈值的大小；6)数据挖掘者解密挖掘结果，判断是否是频繁项集，并求频繁项集的非空真子集与查询加密上传；7)双云安全比较置信度和置信度阈值的大小；8)数据挖掘者解密挖掘结果，判断是否属于强关联规则。本发明降低了隐私泄露的风险，能够满足更高的隐私保护要求；同时，有效提高了挖掘计算效率。
1.一种基于稀疏数据集的隐私保护关联规则挖掘方法，其特征在于，包括如下步骤：(1)系统初始化：
(1.1)密钥生成中心根据分布式双陷门密码DT‑PKC生成系统参数，其中包括整数N以及强私钥SK；
(1.2)密钥生成中心根据系统参数为每一个数据拥有者DOi生成拥有者密钥对为数据挖掘者生成挖掘者密钥对(pkM,skM)、为系统生成一个中间转换公钥pkT，将强私钥SK拆分为第一强私钥SK1和第二强私钥SK2两个部分，并分别发送给第一云服务器CA和第二云服务器CB；其中i＝1,2...n表示数据拥有者的编号，n表示数据拥有者的总个数；
(2)数据拥有者使用各自的公钥 逐比特加密二进制交易数据，得到包含m条加密交易的数据集T＝{T1,T2,…,Tj,…,Tm}，并将其发送至第一云服务器CA；其中h表示每条交易的项目总数；
(3)数据挖掘者加密查询相关信息并上传至CA：(3.1)数据挖掘者根据本地数据集选择查询项集Q′＝(q1,…,qh)；并设定参与计算的项目分组总数的上限l2、下限l1及每个分组中的项目个数w；
(3.2)根据查询项集Q′＝(q1,…,qh)，按照下式计算：bσ＝qw(σ‑1)+1∨qw(σ‑1)+2∨…∨qmin(h,wσ)，得到查询分组标记集合
(3.3)遍历查询分组标记集合B'中的所有元素，统计其中“1”的数目，记为temp；并将“0”对应的元素下标σ添加到集合I中；
(3.4)对temp进行如下判断：若temp≥l2，则直接执行步骤(3.5)；若temp＜l2，选择一个随机数χ∈[f(l1‑temp),l2‑temp]，其中函数f定义为 然后从集合I中随机选取χ个数，并将其在B'中对应的元素替换为1，得到更新后查询分组标记集合B；
(3.5)数据挖掘者选定置信度阈值confmin＝ε1/ε2并加密得到密文 和 对查询项集Q'加密得到查询项集密文集合 统计查询项目个数c并加密得到密文 选定支持度阈值suppmin并加密得到密文(3.6)将得到的所有密文与B一起发送给第一云服务器CA；
(4)第一云服务器CA在第二云服务器CB的辅助下计算查询项集与每一条交易的内积密文，获取数据集T的内积密文集合，具体按如下步骤实现：(4.1)判断bσ是否为1，若是，则Tj中对应的交易分组(Tj,w(σ‑1)+1,…,Tj,min(h,wσ))需要参与挖掘，否则，对应项目分组不需要参与挖掘；Tj中第υ个参与挖掘的交易分组记作其中υ∈(1,…,η)，η表示B中存在“1”的个数，kυ是B中第υ个“1”的对应下标值；
(4.2)第一云服务器CA和第二云服务器CB以交易分组Gj,υ与查询Q中对应查询分组为输入，执行安全内积计算协议得到 对所有交易分组与查询对应分组执行安全内积计算协议得到Tj的分组内积密文集合(4.3)第一云服务器CA根据Dj计算Tj的内积密文 得到数据集T的内积密文集合E＝(e1,…,ej,…,em)；
(5)第一云服务器CA在第二云服务器CB的辅助下，计算得到查询项集Q'的支持度密文(5 .1)第一云服务器CA选取一个随机数 计算c盲化后的密文然后使用第一强私钥SK1部分解密得到A的一级解密结果并将{A,A'}发送至第二云服务器CB；
(5.2)第二云服务器CB使用第二强私钥SK2解密得到A的明文 并使用公钥pkT加密后获得转换密钥后的密文 将其发送给第一云服务器CA；
(5.3)第一云服务器CA根据密文 得到公钥pkT加密c的密文结果再选取一个随机数 |N|表示N的二进制位数；
对E中的每个元素，云服务器CA选取两个随机数 满足rj,2＜＜ra，计算 用以更新ej，并使用SK1对其进行部分解密得到ej'；将ej'添加到集合E'中，然后将{E,E'}发送至第二云服务器CB；
(5.4)设定一个集合 第二云服务器CB使用SK2进行解密，得到ej”并判断如下：如果ej”＜N/2，则令 否则令 然后将vj加入集合V中；并将V发送给第一云服务器CA；
(5.5)第一云服务器CA初始化变量 判断是否满足rj,1＝1，如果是则更新否则vj不变；
(5.6)令R＝R·vj，得到查询项集Q的支持度密文(6)第一云服务器CA在第二云服务器CB的辅助下比较 和 对应的明文大小，得到挖掘结果 并发送给数据挖掘者：(6.1)第一云服务器CA选取两个随机数 满足r2＜＜r1，l＜|N|/2‑1，再选取一个随机数 以 和 为输入运行安全加法计算协议得到A1，再对A1进行盲化后得到 然后第一云服务器CA使用SK1对B1进行部分解密得到解密结果 将{B1,B1′}发送给云服务器CB；
(6.2)第二云服务器CB使用SK2解密得到B1的明文 如果B″1＜N/2，则令 否则令 发送t至第一云服务器CA；
(6.3)第一云服务器CA进行判断，如果r3＝0，则令 否则 然后将挖掘结果 发送给数据挖掘者；
(7)数据挖掘者使用自己的私钥解密挖掘结果 得到解密结果s并判断：如果s＝1，则查询项集是频繁项集，如果s＝0，则查询项集是非频繁项集；
(8)数据挖掘者计算出频繁项集的非空真子集 得到Z′的分组标记集合 以及查询项目总数集合 对Z′和P'加密后与ψ一同发给第一云服务器CA；
(8.1)数据挖掘者通过不断选定可能频繁的查询项集向两个云服务器发起询问判断所选查询是否是频繁项集，最终找到的频繁项集记作f'＝(f1',…,fh')，根据f'生成其非空真子集Z′作为新的查询集合；
(8.2)数据挖掘者计算出非空真子集Z′的查询分组计算标记集合ψ，对Z′中每一个项集加密获得 其中 再统计Z′中每一个项集中存在的项目总个数并加密得到集合 将以上加密数据Z和P发送给第一云服务器CA；
(9)第一云服服务器CA在第二云服务器CB的辅助下基于密文比较Z′中每一个项集的置信度与置信度阈值的大小，将比较结果 发送给数据挖掘者；
(10)数据挖掘者使用自己的私钥解密比较结果U，并判断：如果uθ＝1，则 是强关联规则，如果uθ＝0，则 不是强关联规则。
2.根据权利要求1所述的方法，其特征在于：步骤(1.1)中密钥生成中心生成系统参数、整数N以及强私钥SK，具体如下：(1.1.1)密钥生成中心生成两个大素数p和q，且满足 其中， 和 分别是素数p和q的二进制比特长度；
(1.1.2)根据素数p和q，计算整数N＝p×q和SK＝lcm(p‑1,q‑1)/2，其中，lcm(p‑1,q‑1)是p‑1和q‑1的最小公倍数。
3.根据权利要求1所述的方法，其特征在于：步骤(1.2)中将强私钥SK拆分为第一强私2
钥SK1和第二强私钥SK2两个部分，是指：根据公式SK1+SK2≡0modSK以及SK1+SK2≡1modN 求解出SK1和SK2。
4.根据权利要求1所述的方法，其特征在于：步骤(4.2)中安全内积计算协议，具体实现步骤为：假设输入分别为 和(4.2.1)第一云服务器CA选择四个随机数 计算得到以下四个密文：然后CA使用SK1对上述密文进行部分解密获得和 将{A2,B2,C2,D2,A2′,B2′,C2′,D2′}发送给云服务器CB；
(4 .2 .2 ) 第 二云 服 务 器C B 使 用S K 2解 密 得 到以及 其中A2″,B2″,C2″,
D2″分别是A2,B2,C2,D2的明文；然后计算：将{S1,S2,S3}发送至第一云服务器CA；
(4.2.3)第一云服务器CA利用已选取的随机数计算得：(4.2.4)第一云服务器CA计算得到最终结果：
5.根据权利要求1所述的方法，其特征在于：步骤(4.2)中安全内积协议，具体实现步骤为：假设输入为α维的加密数据 以及从γ＝1到α对每一个 和 两个云服务器合作执行安全乘法计算协议，云服务器CA获得 然后第一云服务器CA利用同态加法性质，将所有获得的 相乘得到加密的内积结果
6.根据权利要求1所述的方法，其特征在于：步骤(6.1)中安全加法计算协议，具体实现步骤为：假设输入分别为 和(6.1.1)第一云服务器CA选取两个随机数 计算获得：通过使用SK1对这两个密文进行部分解密获得 和 将{A3,B3,A3′,B3′}发送给第二云服务器CB；
(6.1 .2)第二云服务器CB使用SK2解密得到A3和B3对应的明文分别为和 然后计算出C3发送给云服务器CA，计算公式如下：
7.根据权利要求1所述的方法，其特征在于：步骤(9)中基于密文比较查询的置信度与置信度阈值的大小，具体为：c
(9.1)从θ＝1到2‑2，两个云服务器CA和CB对每一个查询项集zθ求出其支持度密文，加密的支持度集合记作c
(9.2)从θ＝1到2‑2，两个云服务器CA和CB以 和 为输入执行安全乘法计算协议得到 以 和 为输入执行安全乘法计算得到c
(9.3)从θ＝1到2‑2，基于密文 和 进行明文大小比较得到结果 最终得到比较结果 并发送给数据挖掘者。
基于稀疏数据集的隐私保护关联规则挖掘方法
技术领域
[0001] 本发明属于计算机技术领域，进一步涉及信息安全技术，具体为一种基于稀疏数据集的隐私保护关联规则挖掘方法，可用于商场的购物篮分析等具有稀疏交易数据集的场景，在不泄漏用户隐私的前提下实现云外包关联规则挖掘。
背景技术
[0002] 随着网络技术的飞速发展，互联网已经渗透到了人们生活的方方面面，用户数据随着线上业务的普及以前所未有的速度增长，而这庞大的数据集中所蕴藏着的信息具有不容忽视的商业价值。在数据转化为价值的过程中，数据挖掘技术作为中间环节起着举足轻重的作用。数据挖掘是通过分析数据，从海量数据集中提取出潜在有价值的信息与知识的过程，按照挖掘目标可以分为预测性任务(如分类挖掘和回归挖掘)以及描述性任务(如关联规则挖掘和聚类挖掘)。其中关联规则挖掘是数据挖掘技术中最为经典的算法之一，用来挖掘事物与事物之间隐含的关联性信息，目前在多个场景中有着广泛应用，如购物篮分析、银行客户分析、搜索引擎、智能推荐等。在超市购物的场景中，通过从销售数据中挖掘出商品购买的关联性，将习惯一同购买的商品组合摆放在相邻区域或开展联合促销活动，能够有效推动消费。
[0003] 在这个信息爆炸的大数据时代，对数据进行充分利用可以实现数据价值最大化，然而，与此同时数据安全问题也随之显现。海量数据的存储计算对于企业来说越来越具有挑战性，企业中存储与计算资源的短缺限制了业务拓展，导致发展受限，因此各个企业逐渐选择将其拥有的用户数据外包给云服务器进行存储和挖掘计算。在云服务器中存储着来自于不同企业的庞大的用户数据集，其中蕴含着大量的用户敏感信息，但是云服务器并不完全可信，云服务提供商可能会有意或无意泄露企业所提供的数据，还可能会对数据进行过度分析，这样不仅会损害企业利益，甚至还会侵犯用户隐私。例如，商场将所收集到的客户交易信息外包给云服务器进行数据挖掘分析，云服务提供商将挖掘结果泄露给其他具有竞争关系的商场，就会导致该商场利益受损。又比如，现在的各种网络注册大都需要填写个人信息，这些信息可能涉及到用户姓名、电话号码、身份证号等个人隐私，若有不法分子通过非正规渠道窃取用户信息并在网络黑市中进行贩卖，一旦被非法利用所造成的严重后果不堪设想。因此，数据挖掘中的隐私泄露问题越来越受到社会各界的高度重视。
[0004] 目前，隐私保护关联规则挖掘研究的相关工作大致可以分为基于随机化的方法和基于密码学的方法。和基于密码学方法相比，基于随机化的方法不但只能达到有限的安全性，而且挖掘结果的准确性也不能绝对保证。在基于密码学的方法中，同态加密技术展现出了优势，可以在不解密的前提下对加密数据进行计算并得到密态的期望结果,这一特点在云计算中得以应用，能够在不暴露用户敏感信息的同时利用云服务器强大的存储与计算能力完成挖掘任务。
[0005] 在基于同态加密的隐私保护关联规则挖掘研究中，不少方案都采用了两个云服务器。Shuo Qiu等人在文献“Toward Practical Privacy‑Preserving Frequent Itemset Mining on Encrypted Cloud Data”(IEEE Transactions on Cloud Computing，Beijing Jiaotong University，2017)中通过使用Paillier和BGN两种同态加密算法，提出了三种不同隐私级别的频繁项集挖掘方案，其中频繁项集挖掘是关联规则挖掘的核心，然而具有最高隐私级别的方案仍然以明文形式返回挖掘结果，会向云服务器泄露信息。Lin Liu等人在文献“Privacy‑Preserving Mining of Association Rule on Outsourced Cloud Data from Multiple Parties”(ACISP，National University of Defense Technology，2018)中基于BCP同态加密算法提出了第一个多密钥环境下的隐私保护关联规则挖掘方案，该方案允许不同的数据拥有者使用各自的密钥将数据外包给云服务器，但是该方案中存在一个拥有强私钥的云服务器能够解密任何密文，云服务器一旦成功截获系统中的加密数据就可获得其明文，侵害用户隐私。Hongping Pang和Baocang Wang在文献“Privacy‑Preserving Association Rule Mining Using Homomorphic Encryption in a Multikey Environment”(IEEE Systems Journal，Xidian University，2020)中设计了一个支持双解密机制的Paillier变形同态加密算法，并利用该算法实现了多密钥环境下的隐私保护关联规则挖掘，他们通过使用Diffie‑Hellman协议解决了Lin Liu方案中数据上传阶段用户隐私泄露的问题。但是，由于云服务器解密能力过于强大依然存在安全隐患，在挖掘结果发送给数据挖掘者的过程中存在隐私泄露的风险。上述这些方案都需要添加额外的虚假交易集，因为在计算查询项集支持度的步骤中，如果不添加虚假交易集就会直接向其中一个云服务器泄露支持度的值，但是，即使选择在数据中添加了虚假交易集，也不能完美解决支持度泄露的问题，还是会暴露部分隐私，虽然云服务器得到的值不一定是支持度的准确值，但是却可以得知支持度的准确值一定不超过该值，若该值比支持度阈值小，云服务器就可以获知挖掘结果，即该查询项集是非频繁项集，进而造成敏感信息的泄露。此外，这些方案中虚假交易集都是随机选取，需要添加的具体数量并没有进行合理分析，若选择的数量太少，可能会导致大量查询的支持度真实值泄露；若数量太多，过多的额外计算开销会影响整个方案的性能。
发明内容
[0006] 本发明的目的在于针对上述现有技术的不足，提出一种更安全高效的基于稀疏数据集的隐私保护关联规则挖掘方法，用于解决现有技术中存在的引入额外计算开销以及隐私泄露的问题。通过查询分组预处理协议、安全比较协议以及支持度安全计算协议实现安全高效的挖掘方法，其中查询分组预处理协议提高了稀疏数据集的关联规则挖掘效率、安全比较协议保证了基于密文比较明文大小的高效性、支持度安全计算协议实现了挖掘过程中在不添加虚假交易集的同时可以达到更高的安全性。
[0007] 本发明实现上述目的具体步骤如下：
[0008] (1)系统初始化：
[0009] (1.1)密钥生成中心根据分布式双陷门密码DT‑PKC生成系统参数、整数N以及强私钥SK；
[0010] (1.2)密钥生成中心根据系统参数为每一个数据拥有者DOi生成拥有者密钥对为数据挖掘者生成挖掘者密钥对(pkM,skM)、为系统生成一个中间转换公钥pkT，将强私钥SK拆分为第一强私钥SK1和第二强私钥SK2两个部分，并分别发送给第一云服务器CA和第二云服务器CB；其中i＝1,2...n表示数据拥有者的编号，n表示数据拥有者的总个数；
[0011] (2)数据拥有者使用各自的公钥 逐比特加密二进制交易数据，得到包含m条加密交易的数据集T＝{T1,T2,…,Tj,…,Tm}，并将其发送至第一云服务器CA；其中j∈(1,…,m)，h表示每条交易的项目总数；
[0012] (3)数据挖掘者加密查询相关信息并上传至CA：
[0013] (3.1)数据挖掘者根据本地数据集选择查询项集Q′＝(q1,…,qh)；并设定参与计算的项目分组总数的上限l2、下限l1及每个分组中的项目个数w；
[0014] (3.2)根据查询项集Q′＝(q1,…,qh)，按照下式计算：
[0015] bσ＝qw(σ‑1)+1∨qw(σ‑1)+2∨…∨qmin(n,wσ)，
[0016] 得到查询分组标记集合
[0017] (3.3)遍历查询分组标记集合B'中的所有元素，统计其中“1”的数目，记为temp；
[0018] 并将“0”对应的元素下标σ添加到集合I中；
[0019] (3.4)对temp进行如下判断：若temp≥l2，则直接执行步骤(3.5)；若temp＜l2，选择一个随机数χ∈[f(l1‑temp),l2‑temp]，其中函数f定义为 然后从集合I中随机选取χ个数，并将其在B'中对应的元素替换为1，得到更新后查询分组标记集合B；
[0020] (3.5)数据挖掘者选定置信度阈值confmin＝ε1/ε2并加密得到密文 和对查询项集Q'加密得到查询项集密文集合 统计查询项目个数c并加
密得到密文 选定支持度阈值并加密得到密文
[0021] (3.6)将得到的所有密文与B一起发送给第一云服务器CA；
[0022] (4)第一云服务器CA在第二云服务器CB的辅助下计算数据查询与每一条交易的内积密文，获取数据集T的内积密文集合，具体按如下步骤实现：
[0023] (4.1)判断bσ是否为1，若是，则Tj中对应的交易分组(Tj,w(σ‑1)+1,…,Tj,min(h,wσ))需要参与挖掘，否则，对应项目分组不需要参与挖掘；Tj中第υ个参与挖掘的交易分组记作其中υ∈(1,…,η)，η表示B中存在“1”的个数，kυ是B中第υ个“1”的对应下标值；
[0024] (4.2)第一云服务器CA和第二云服务器CB以交易分组Gj,υ与查询Q中对应查询分组为输入，执行安全内积计算协议得到 对所有交易分组与查询对应分组执行安全内积计算协议得到Tj的分组内积密文集合
[0025] (4.3)第一云服务器CA根据Dj计算Tj的内积密文 得到数据集T的内积密文集合E＝(e1,…,ej,…,em)；
[0026] (5)第一云服务器CA在第二云服务器CB的辅助下，计算得到查询项集Q'的支持度密文
[0027] (5.1)第一云服务器CA选取一个随机数 计算c盲化后的密文然后使用第一强私钥SK1部分解密得到A的一级解密结果
并将{A,A'}发送至第二云服务器CB；
[0028] (5.2)第二云服务器CB使用第二强私钥SK2解密得到A的明文并使用公钥pkT加密后获得转换密钥后的密文 将其发送给第一云服务器CA；
[0029] (5.3)第一云服务器CA根据密文 得到公钥pkT加密c的密文结果再选取一个随机数 l＜|N|/2‑1，|N|表示N的二进制位数；
对E中的每个元素，云服务器CA选取两个随机数 满足rj,2＜＜ra，
计算 用以更新ej，并使用SK1对其进行部分解
密得到ej'；将ej'添加到集合E'中，然后将{E,E'}发送至第二云服务器CB；
[0030] (5.4)设定一个集合 第二云服务器CB使用SK2进行解密，得到ej″并判断如下：如果ej″＜N/2，则令 否则令 然后将vj加入集合V中；并将V发送给第一云服务器CA；
[0031] (5.5)第一云服务器CA初始化变量 判断是否满足rj,1＝1，如果是则更新否则vj不变；
[0032] (5.6)令R＝R·vj，得到查询项集Q的支持度密文
[0033] (6)第一云服务器CA在第二云服务器CB的辅助下比较 和 对应的明文大小，得到挖掘结果 并发送给数据挖掘者：
[0034] (6.1)第一云服务器CA选取两个随机数 满足r2＜＜r1，l＜|N|/2‑1，再选取一个随机数 以 和 为输入运行安
全加法计算协议得到A1，再对A1进行盲化后得到 然后第一云服务器
CA使用SK1对B1进行部分解密得到解密结果 将{B1,B′1}发送给云服务器CB；
[0035] (6.2)第二云服务器CB使用SK2解密得到B1的明文 如果B″1＜N/2，则令 否则令 发送t至第一云服务器CA；
[0036] (6 .3)第一云服务器CA进行判断，如果r3＝0，则令 否则然后将挖掘结果 发送给数据挖掘者；
[0037] (7)数据挖掘者使用自己的私钥解密挖掘结果 得到解密结果s并判断：如果s＝1，则查询项集是频繁项集，如果s＝0，则查询项集是非频繁项集；
[0038] (8)数据挖掘者计算出频繁项集的非空真子集 得到Z′的分组标记集合 以及查询项目总数集合 对Z′和P'加
密后与ψ一同发给第一云服务器CA；
[0039] (8.1)数据挖掘者通过不断选定可能频繁的查询项集向两个云服务器发起询问判断所选查询是否是频繁项集，最终找到的频繁项集记作f'＝(f1',…,fh')，根据f'生成其非空真子集Z′作为新的查询集合；
[0040] (8.2)数据挖掘者计算出非空真子集Z′的查询分组计算标记集合ψ，对Z′中每一个项集加密获得 其中 再统计Z′中每一个项集中存在的项目总个数并加密得到集合 将以上加密数据发送
给第一云服务器CA；
[0041] (9)第一云服服务器CA在第二云服务器CB的辅助下基于密文比较Z′中每一个项集的置信度与置信度阈值的大小，将比较结果 发送给数据挖掘者；
[0042] (10)数据挖掘者使用自己的私钥解密比较结果U，并判断：如果uθ＝1，则是强关联规则，如果uθ＝0，则 不是强关联规则。
[0043] 本发明与现有技术相比，具有以下优点：
[0044] 第一、由于本发明采用DT‑PKC分布式同态加密算法加密交易数据集，通过将强私钥一分为二分别交给两个云服务器保管，弱化了单独一个云服务器的解密能力，只有两个云服务器合作才能够解密所有密文，解决了单个云服务器解密能力过大所带来的安全问题，有效降低了隐私泄露的风险；
[0045] 第二、本发明提出了不需要引入额外虚假交易集的支持度安全计算方法，通过设计一个高效的密态数据明文大小比较方法，实现在密文下统计交易集中满足查询的交易个数，进而结合密态数据计算方法完成安全的频繁项集挖掘以及关联规则挖掘；这种安全高效的支持度安全计算方法，使得在支持度计算的过程中不需要添加虚假交易集隐藏支持度的大小，且不会泄露支持度的上限值，从而在不引入额外开销的同时达到更高的安全性；
[0046] 第三、由于本发明针对稀疏交易数据集采用对查询进行分组预处理的方式，从而明显提高了计算效率。
附图说明
[0047] 图1为本发明方法的实现流程图。
具体实施方式
[0048] 下面结合附图对本发明做进一步的描述。
[0049] 参照附图1，本发明提出的一种基于稀疏数据集的隐私保护关联规则挖掘方法，包括如下步骤：
[0050] 步骤1，系统初始化：
[0051] (1.1)密钥生成中心根据分布式双陷门密码DT‑PKC生成系统参数、整数N以及强私钥SK；首先，密钥生成中心生成两个大素数p和q，且满足 其中， 和 分别是素数p和q的二进制比特长度；然后根据素数p和q，计算整数N＝p×q；SK＝lcm(p‑1,q‑
1)/2，其中，lcm(p‑1,q‑1)是p‑1和q‑1的最小公倍数。
[0052] (1.2)密钥生成中心根据系统参数为每一个数据拥有者DOi生成拥有者密钥对为数据挖掘者生成挖掘者密钥对(pkM,skM)、为系统生成一个中间转换公钥pkT，将强私钥SK拆分为第一强私钥SK1和第二强私钥SK2两个部分，具体是指根据公式SK1+
2
SK2≡0modSK以及SK1+SK2≡1modN求解出SK1和SK2；然后将SK1和SK2分别发送给第一云服务器CA和第二云服务器CB；其中i＝1,2...n表示数据拥有者的编号，n表示数据拥有者的总个数。密钥生成中心生成数据挖掘者与数据拥有者的密钥对，具体为：首先密钥生成中心选择阶为(p‑1)(q‑1)/2的生成元g，然后生成私钥 以及对应公钥
[0053] 在大型超市购物篮分析的场景中，数据拥有者和数据挖掘者指拥有有限交易集的大型超市，数据挖掘者既可以是数据拥有者，也可以不是。密钥生成中心是可信第三方机构，用于系统中密钥的生成和管理。云服务器CA和CB是来自于不同云服务提供商的云服务器。
[0054] 步骤2，数据拥有者加密数据后上传至云服务器CA；
[0055] 加密上传的具体步骤为：每一个数据拥有者以二进制形式表示本地数据库中每一条交易，1表示该交易中包含对应商品，0表示不包含，然后使用各自的公钥 逐比特加密数据后发送至云服务器CA，至此数据拥有者的任务已经完成，可以不再参与之后的挖掘工作。
[0056] 数据拥有者使用各自的公钥 逐比特加密二进制交易数据，得到包含m条加密交易的数据集T＝{T1,T2,…,Tj,…,Tm}，并将其发送至第一云服务器CA；其中j∈(1,…,m)，h表示每条交易的项目总数；
[0057] 步骤3，数据挖掘者加密查询相关信息并上传至CA：
[0058] 数据挖掘者根据本地数据集选择可能频繁的项集作为查询，以二进制形式表示为Q′＝(q1,…,qh)，然后将加密的查询 查询项目个数 支持度阈值 以及查询分组标记集合 发送给云服务器CA；
[0059] 查询分组标记集合B的计算具体包括以下步骤：
[0060] (3.1)初始化变量temp＝0，集合 以及 使得其满足：
[0061] bi＝qw(i‑1)+1∨qw(i‑1)+2∨…∨qmin(h,wi)，
[0062] 其中， w为每个分组中的项目个数；
[0063] (3.2)从σ＝0到 依次遍历B'中元素，如果bi＝1则令temp＝temp+1，否则将i添加入集合I中；即遍历查询分组标记集合B'中的所有元素，统计其中“1”的数目，记为temp，并将“0”对应的元素下标σ添加到集合I中；
[0064] (3.3)对temp进行如下判断：若temp≥l2，则直接执行下一步；若temp＜l2，选择一个随机数χ∈[f(l1‑temp),l2‑temp]，其中函数f定义为 然后从集合I中随机选取χ个数，并将其在B'中对应的元素替换为1，得到更新后查询分组标记集合B。其中l2和l1分别为数据挖掘者选定的参与计算的项目分组总数的上限与下限；
[0065] (3.4)数据挖掘者选定置信度阈值confmin＝ε1/ε2并加密得到密文 和对查询项集Q'加密得到查询项集密文集合 统计查询项目个数c并加
密得到密文 选定支持度阈值并加密得到密文
[0066] (3.5)将得到的所有密文与B一起发送给第一云服务器CA；
[0067] 步骤4，第一云服务器CA在第二云服务器CB的辅助下计算数据查询与每一条交易的内积密文，获取数据集T的内积密文集合，具体按如下步骤实现：
[0068] 安全内积计算具体包括以下步骤：
[0069] (4.1)根据 中bσ是否等于1判断对应项目分组是否需要参与挖掘计算。Tj中第υ个参与挖掘的交易分组记作 其中υ∈
(1,…,η)，η表示B中存在“1”的个数，kυ是B中第υ个“1”对应下标值；
[0070] (4.2)对每一个交易，两个云服务器CA和CB利用交易分组Gj,υ与查询Q中对应查询分组 作安全内积计算得到 对所有交易分组与查询对应分组执行安全内积计算协议得到分组内积密文集合 这里的安全内
积协议按如下方式实现：假设输入为α维的加密数据 以及
从γ＝1到α对每一个 和 两个云服务器合作执行安全乘
法计算协议，云服务器CA获得 然后第一云服务器CA利用同态加法性质，将所有获得的 相乘得到加密的内积结果 安全乘法计算协议，假设输入分
别为 和 具体实现步骤为：
[0071] (4.2.1)第一云服务器CA选择四个随机数 计算得到以下四个密文：
[0072]
[0073]
[0074]
[0075]
[0076] 然后CA使用SK1对上述密文进行部分解密获得将{A2,B2,C2,D2,A′2,B′2,C′2,D′2}发送给云服务器
CB。
[0077] (4 .2 .2) 第二云服务器CB使用SK2解密得到以及 其中A″2,B″2,C″2,
D″2分别是A2,B2,C2,D2的明文；然后计算：
[0078]
[0079]
[0080]
[0081] 将{S1,S2,S3}发送至第一云服务器CA；
[0082] (4.2.3)第一云服务器CA利用已选取的随机数计算得：
[0083]
[0084]
[0085] (4.2.4)第一云服务器CA计算得到最终结果：
[0086]
[0087] (4.3)云服务器CA计算出第j条交易与查询之间内积的密文：
[0088]
[0089] 然后，云服务器CA计算获得加密的所有交易的内积密文集合E＝(e1,…,ej,…,em)。
[0090] 步骤5，第一云服务器CA在第二云服务器CB的辅助下，计算得到查询项集Q'的支持度密文
[0091] 支持度的安全计算具体包括以下步骤：
[0092] (5.1)第一云服务器CA选取一个随机数 计算c盲化后的密文然后使用第一强私钥SK1部分解密得到A的一级解密结果
并将{A,A'}发送至第二云服务器CB。其中，使用私钥SK1部分解密得到A的
一级解密结果 密文A＝(C1,C2)，实现如下：
[0093] (5.2)第二云服务器CB使用第二强私钥SK2解密得到A的明文并使用公钥pkT加密后获得转换密钥后的密文 将其发送给第一云服务器CA。其
中使用私钥SK2部分解密得到A的明文
[0094] (5.3)第一云服务器CA根据密文 得到公钥pkT加密c的密文结果再选取一个随机数 l＜|N|/2‑1，|N|表示N的二进制位数；
对E中的每个元素，云服务器CA选取两个随机数 满足rj,2＜＜ra，
计算 用以更新ej，并使用SK1对其进行部分解
密得到ej'；将ej'添加到集合E'中，然后将{E,E'}发送至第二云服务器CB；
[0095] (5.4)设定一个集合 第二云服务器CB使用SK2进行解密，得到ej″并判断如下：如果ej″＜N/2，则令 否则令 然后将vj加入集合V中；并将V发送给第一云服务器CA；
[0096] (5.5)第一云服务器CA初始化变量 判断是否满足rj,1＝1，如果是则更新否则vj不变；
[0097] (5.6)令R＝R·vj，得到查询项集Q的支持度密文
[0098] 步骤6，第一云服务器CA在第二云服务器CB的辅助下比较 和 对应的明文大小，得到挖掘结果 并发送给数据挖掘者：
[0099] 密文的明文比较方法具体包括以下步骤：
[0100] (6.1)第一云服务器CA选取两个随机数 满足r2＜＜r1，l＜|N|/2‑1，再选取一个随机数 对 和 做安全加法计
算得到A，再对A进行盲化后得到B，计算公式如下：
[0101]
[0102] 然后第一云服务器CA使用SK1对B进行部分解密得 将{B,B′}发送给云服务器CB。
[0103] 安全加法计算协议，具体实现步骤为：假设输入分别为 和
[0104] (6.1.1)第一云服务器CA选取两个随机数 计算获得：
[0105]
[0106]
[0107] 通过使 用SK1对这两个 密文进行部分解密获得 和
[0108] 将{A3,B3,A′3,B′3}发送给第二云服务器CB；
[0109] (6.1.2)第二云服务器CB使用SK2解密得到A3和B3对应的明文分别为和 然后计算出C3发送给云服务器CA，计算公式如
下：
[0110]
[0111] (6.1.3)第一云服务器CA计算得到最终结果：
[0112]
[0113] (6.2)第二云服务器CB使用SK2解密得到B的明文 如果B″＜N/2， 否则 发送t至云服务器CA；
[0114] (6.3)如果r3＝0，则 否则
[0115] 步骤7，数据挖掘者使用自己的私钥解密挖掘结果，如果s＝1，则查询项集是频繁项集，如果s＝0，则查询项集是非频繁项集。这里数据挖掘者使用自己的私钥解密挖掘结果[0116] 步骤8，数据挖掘者计算出频繁项集的非空真子集 得到Z′的分组标记集合 以及查询项目总数集合 将ψ与加
密的Z′和P'发给第一云服务器CA。包括如下步骤：
[0117] (8.1)数据挖掘者通过不断选定可能频繁的查询项集向两个云服务器发起询问判断所选查询是否是频繁项集，最终找到的频繁项集记作f'＝(f1',…,fh')，根据f'生成其非空真子集Z′作为新的查询集合；
[0118] (8.2)数据挖掘者计算出非空真子集Z′的查询分组计算标记集合ψ，对Z′中每一个项集加密获得 其中 再统计Z′中每一个项集中存在的项目总个数并加密得到集合 将以上加密数据及ψ发
送给第一云服务器CA。
[0119] 步骤9，第一云服服务器CA在第二云服务器CB的辅助下基于密文比较Z′中每一个项集的置信度与置信度阈值的大小，将比较结果 发送给数据挖掘者；具体步骤如下：
[0120] (9.1)从θ＝1到2c‑2，两个云服务器CA和CB对每一个查询项集zθ求出其支持度密文，加密的支持度集合记作c
[0121] (9.2)从θ＝1到2‑2，两个云服务器CA和CB以 和 为输入执行安全乘法计算协议得到 以 和 为输入执行安全乘法计算得到
[0122] (9.3)从θ＝1到2c‑2，基于密文 和 进行明文大小比较得到结果最终得到比较结果 并发送给数据挖掘者。
[0123] 步骤10，数据挖掘者使用自己的私钥解密比较结果U，并判断：如果uθ＝1，则是强关联规则，如果uθ＝0，则 不是强关联规则。
[0124] 本发明未详细说明部分属于本领域技术人员公知常识。
[0125] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，显然对于本领域的专业人员来说，在了解了本发明内容和原理后，都可能在不背离本发明原理、结构的情况下，进行形式和细节上的各种修正和改变，但是这些基于本发明思想的修正和改变仍在本发明的权利要求保护范围之内。
