(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210819670.0 (22)申请日 2022.07.13 (71)申请人 哈尔滨工业大 学 （深圳） 地址 518055 广东省深圳市南 山区桃源街 道深圳大 学城哈尔滨工业大 学校区 (72)发明人 郑宜峰　王炜博　王松磊　 (74)专利代理 机构 深圳市君胜知识产权代理事 务所(普通 合伙) 44268 专利代理师 李晓凤 (51)Int.Cl. G06F 21/62(2013.01) G06F 21/60(2013.01) (54)发明名称 一种隐私保护的Skyl ine查询方法及系统 (57)摘要 本发明公开了一种隐私保护的Skyline查询 方法及系统， 本发明提供的方法中， 使用轻量级 加密技术对原始数据库和查询内容进行加密， 并 且可以实现安全的数据库映射、 安全的Skyline 元组获取以及安全的Skyline和被支配元组消 除， 在Skyline查询过程中， 第一计算终端和第二 计算终端不会获取到原始数据库内容、 查询元组 和查询结果， 也不会获取到数据库的元组之间的 支配关系， 实现了高效的隐私保护的Skyline查 询。 权利要求书5页 说明书19页 附图6页 CN 115186295 A 2022.10.14 CN 115186295 A 1.一种隐私保护的Skyl ine查询方法， 其特 征在于， 所述方法包括： 第一计算终端和第 二计算终端基于加性秘密共享， 根据本地持有的查询元组 的加性秘 密共享份额和原始数据库的加性秘密 共享份额获取映射数据库的加性秘密 共享份额， 所述 映射数据库中的第i个元组中的第k个数值为所述原始数据库中的第i个元组的第k个属性 值与所述 查询元组的第k个属性 值的差的绝对值； 所述第一计算终端和所述第二计算终端基于加性秘密共享获取第一比较结果的加性 秘密共享份额， 所述第一比较结果为所述映射数据库中的元组的属 性和的比较结果， 所述 第一计算终端和所述第二计算终端基于所述第一比较结果的加 性秘密共享份额获取所述 映射数据库中最小的属 性和的加性秘密共享份额， 其中， 元组的属 性和为元组中各个值的 和； 所述第一计算终端和所述第二计算终端根据所述第一比较结果获取所述映射数据库 中的一个Skyline元组的加性秘密共享份额以及所述原始数据库中的一个Skyline元组的 加性秘密共享份额， 将所述原始数据库中的Skyline元组的加性秘密共享份额加入至查询 结果集中； 所述第一计算终端和所述第二计算终端获取所述映射数据库中最小的属性和与预设 最大值的第二比较结果的加性秘密 共享份额， 所述第一计算 终端和所述第二计算 终端交换 本地持有的所述第二比较结果的加性秘密共享份额， 得到所述第二比较结果的明文信息； 若所述明文信 息为所述映射数据库中最小的属性和小于所述预设最大值， 则所述第 一 计算终端和所述第二计算终端基于加性秘密共享， 根据所述映射数据库中Skyline元组的 加性秘密共享份额分别获取所述映射数据库中的元组的第一标识信息和第二标识信息的 加性秘密共享份额， 其中， 所述第一标识信息用于区分所述映射数据库中的一个Skyline元 组和其他元组， 所述第二标识信息用于区分所述映射数据库中的第一元组和第二元祖， 所 述第一元组为Skyline元组或被Skyline元组支配的元组， 所述第二元祖为既不是Skyline 元组也不是被Skyl ine元组支配的元组； 所述第一计算终端和所述第二计算终端基于本地持有的所述第二标识信息和所述第 一标识信息的加性秘密共享份额对所述映射数据库中被Skyline元组支配的元组和一个 Skyline元组的属性和的加性秘密共享份额进行更新， 以使 得所述映射数据库中被Skyline 元组支配的元组和一个Skyl ine元组的属性和为所述预设最大值； 所述第一计算终端和所述第二计算终端重复执行所述基于加性秘密共享获取第一比 较结果的加性秘密 共享份额的步骤， 直至所述明文信息为所述映射数据库中最小的属性和 不小于所述预设最大值。 2.根据权利要求1所述的隐私保护的Skyline查询方法， 其特征在于， 所述第一计算终 端和所述第二计算终端基于加性秘密 共享， 根据本地持有的查询元组的加性秘密 共享份额 和原始数据库的加性秘密共享份额获取映射数据库的加性秘密共享份额， 包括： 所述第一计算终端和所述第二计算终端执行如下操作以获取a和b的差值的绝对值的 加性秘密共享份额： 所述第一计算终端和所述第 二计算终端基于加性秘密共享计算第 一差值， 以使得所述 第一计算 终端持有所述第一差值的一个加性秘密 共享份额， 所述第二计算终端持有所述第 二差值的另一个加性秘密共享份额， 其中， 所述第一差值 为a减去b得到的差值；权　利　要　求　书 1/5 页 2 CN 115186295 A 2所述第一计算终端和所述第 二计算终端基于加性秘密共享计算第 二差值， 以使得所述 第一计算 终端持有所述第二差值的一个加性秘密 共享份额， 所述第二计算终端持有所述第 二差值的另一个加性秘密共享份额， 其中， 所述第二差值 为b减去a得到的差值； 所述第一计算终端和所述第二计算终端获取a和b的比较结果的比特数据的最高有效 位的布尔加性秘密共享份额， 其中， 当a<b时， a和b的比较结果的最高有效位为1， 当a≥b时， a和b的比较结果的最高有效位 为0； 所述第一计算终端和所述第 二计算终端基于加性秘密共享计算第 一预设公式以得到a 和b的差值的绝对值的加性秘密共享份额； 所述第一预设公式为： 其中， 表示取反操作， 当a<b的时候， (a<b)＝1， 当a≥b的时候， (a<b)＝0； 在基于加性秘密共享计算所述第 一预设公式时， 所述第 一计算终端和所述第 二计算终 端通过两轮计算， 在所述第一计算终端和所述第二计算终端分别持有x的两个布尔加 性秘 密共享份额， 并且所述第一计算终端和所述第二计算终端分别持有y的两个算术加 性秘密 共享份额的情况 下， 获取x和y的乘积的加性秘密共享份额； 其中， 在第一轮计算中， 所述第一计算终端作为发送方， 所述第二计算终端作为接收 方， 在第二轮 计算中， 所述第一计算终端作为接收方， 所述第二计算终端作为发送方； 在每轮计算中， 发送方生成随机数r， 并计算消息 之后所述发送方保存所述随机数并将m0,m1发送给接收方， 其中， 为所述发送方本地保 存的x的布尔加性秘密共享份额， 为所述发送方本地保存的y的算术加性秘密共享份 额； 所述接收方确定本地保存的布尔加性秘密共享份额是否为0， 若是， 则保存m0， 若否， 则 保存m1； 两轮计算结束后， 所述第一计算终端/所述第二计算终端将本地生成的所述随机数和 保存的所述消息求和， 分别得到x和y的乘积的一个加性秘密共享份额。 3.根据权利要求2所述的隐私保护的Skyline查询方法， 其特征在于， 所述第一计算终 端和所述第二计算终端获取a和b的比较结果的比特数据的最高有效位的布尔加 性秘密共 享份额， 包括： 所述第一计算终端和所述第二计算终端将本地持有的所述第一差值的加性秘密共享 份额转换为比特数据， 通过并行前缀加法电路进 行计算以使得所述第一计算 终端获取a和b 的比较结果的比特数据的最高有效位的一个布尔加性秘密 共享份额， 所述第二计算 终端获 取a和b的比较结果的最高有效位的另一个布尔加性秘密共享份额。 4.根据权利要求2所述的隐私保护的Skyline查询方法， 其特征在于， 所述第一计算终 端和所述第二计算终端基于所述第一比较结果的加 性秘密共享份额获取所述映射数据库 中最小的属性和的加性秘密共享份额， 包括： 所述第一计算终端和所述第二计算终端通过如下操作获取a和b之间的最小值的加性 秘密共享份额： 所述第一计算终端和所述第二计算终端获取a和b的比较结果的比特数据的最高有效权　利　要　求　书 2/5 页 3 CN 115186295 A 3