引用本文
  • 强佳玉,罗明.基于TFHE方案的非平衡隐私集合协议[J].信息安全学报,已采用    [点击复制]
  • Qiang Jiayu,Luo Ming.Private Set Intersection from TFHE for Unbalanced Scenarios[J].Journal of Cyber Security,Accept   [点击复制]
【打印本页】 【下载PDF全文】 查看/发表评论下载PDF阅读器关闭

过刊浏览    高级检索

本文已被:浏览 978次   下载 0  
基于TFHE方案的非平衡隐私集合协议
强佳玉, 罗明
0
(中国科学院信息工程研究所)
摘要:
在很多使用云服务器计算的隐私集合求交集(Private Set Intersection, PSI)运算场景中,客户端一般拥有比云服务器更小的数据集和更低的计算能力。在这篇文章中,我们首次使用TFHE全同态加密方案<sub>[27]</sub>,代替以往的层次型全同态加密来构造隐私集合求交集协议。我们关注非平衡隐私集合场景,考虑在线通讯量、客户端计算量、云服务器计算量等重要指标。此外,还考虑了协议在实际运行中,服务器的数据库实时更新等动态特性。#$NL 我们使用TFHE方案构造了一个理论通信复杂度为O(|Y|)(低于文献[5](CCS17),其中Y为客户端数据集合大小)、支持任意比特元素的隐私集合求交集协议。TFHE方案支持任意深度的同态运算,因此无需加入为了减少电路深度而进行的优化<sub>[5]</sub>,从而避免了这些电路深度优化技术带来的额外的计算和通信复杂度。我们提出的基础协议可以高效地计算短数据的交集,然后我们提出了动态哈希到箱子策略,哈希和分片技术,并由此提出了可以支持任意长度数据求交集的完整协议。最终实验结果表明,该协议只需一轮交互和2.3 MB的在线通信量就可以将13个任意大小的集合元素和服务器集合进行求交集运算。
关键词:  隐私集合求交集  全同态加密  非平衡场景
DOI:
投稿时间:2020-11-30修订日期:2021-02-10
基金项目:国家自然科学基金项目(面上项目,重点项目,重大项目)
Private Set Intersection from TFHE for Unbalanced Scenarios
Qiang Jiayu, Luo Ming
(Institute of Information Engineering,Chinese Academy of Sciences)
Abstract:
In most scenarios of Private Set Intersection (PSI) computed on a cloud server, the client has a smaller set size and lower computation ability than that of the cloud server, which is known as the unbalanced setting. We use TFHE fully homomorphic encryption scheme[27] for the first time instead of the leveled ones to construct a PSI protocol. We focus on unbalanced scenarios and its important indicators, such as the online communication cost, the computing cost of client and cloud server. In addition, we also pay attention to the dynamic characteristics of the protocol in practical applications, such as server"s real-time updated database. We use TFHE to construct a PSI protocol for unbounded items with a lower communication complexity of O(|Y|) than [5](CCS17), where Y is the length of client’s sets. TFHE support arbitrary depth of homomorphic operations so that enables to avoid those optimizations[5] made to reduce the depth of the circuit, which resulting in additional computation and communication complexity. We propose a basic protocol that can efficiently compute the intersection with small items and then we apply the strategy of dynamic hashing to bins, hashing and partitioning technique to our full protocol in order to support unbounded items. Our implementation shows that it takes just 2.3 MB of online communication with one round trip to intersect 13 unbounded items with server’s items.
Key words:  private set intersection  fully homomorphic encryption  unbalanced scenarios