Private set intersection(PSI) allows two parties to compute the intersection of their private sets while revealing nothing except the intersection. With the development of fog computing, the need has arisen to delegat...Private set intersection(PSI) allows two parties to compute the intersection of their private sets while revealing nothing except the intersection. With the development of fog computing, the need has arisen to delegate PSI on outsourced datasets to the fog. However, the existing PSI schemes are based on either fully homomorphic encryption(FHE) or pairing computation. To the best of our knowledge, FHE and pairing operations consume a huge amount of computational resource. It is therefore an untenable scenario for resource-limited clients to carry out these operations. Furthermore, these PSI schemes cannot be applied to fog computing due to some inherent problems such as unacceptable latency and lack of mobility support. To resolve this problem, we first propose a novel primitive called " faster fog-aided private set intersection with integrity preserving", where the fog conducts delegated intersection operations over encrypted data without the decryption capacity. One of our technical highlights is to reduce the computation cost greatly by eliminating the FHE and pairing computation. Then we present a concrete construction and prove its security required under some cryptographic assumptions. Finally, we make a detailed theoretical analysis and simulation, and compare the results with those of the state-of-the-art schemes in two respects: communication overhead and computation overhead. The theoretical analysis and simulation show that our scheme is more efficient and practical.展开更多
In modern society,it is necessary to perform some secure computations for private sets between different entities.For instance,two merchants desire to calculate the number of common customers and the total number of u...In modern society,it is necessary to perform some secure computations for private sets between different entities.For instance,two merchants desire to calculate the number of common customers and the total number of users without disclosing their own privacy.In order to solve the referred problem,a semi-quantum protocol for private computation of cardinalities of set based on Greenberger-Horne-Zeilinger(GHZ)states is proposed for the first time in this paper,where all the parties just perform single-particle measurement if necessary.With the assistance of semi-honest third party(TP),two semi-quantum participants can simultaneously obtain intersection cardinality and union cardinality.Furthermore,security analysis shows that the presented protocol can stand against some well-known quantum attacks,such as intercept measure resend attack,entangle measure attack.Compared with the existing quantum protocols of Private Set Intersection Cardinality(PSI-CA)and Private Set Union Cardinality(PSU-CA),the complicated oracle operations and powerful quantum capacities are not required in the proposed protocol.Therefore,it seems more appropriate to implement this protocol with current technology.展开更多
分布式计算有很多应用需要参与各方协同执行集合的一些计算但不泄露各自数据集的信息.保密集合交集(private set intersection,PSI)计算已经成为数据匹配、数据挖掘、推荐系统等应用中保护用户隐私的一个重要工具.本文的主要工作是构造...分布式计算有很多应用需要参与各方协同执行集合的一些计算但不泄露各自数据集的信息.保密集合交集(private set intersection,PSI)计算已经成为数据匹配、数据挖掘、推荐系统等应用中保护用户隐私的一个重要工具.本文的主要工作是构造无匹配差错的安全两方保密集合交集运算协议.着重探讨三个问题:(1)开发构造无匹配差错的两方保密集合交集计算所需要的工具(①面向有理数且具有语义安全性的加密方案,②便于集合匹配计算的称之为集合的定长向量编码方法);(2)无匹配差错的两方保密集合交集计算问题;(3)元素为有理数的保密集合交集计算问题.首先在标准模型下设计了一个能够加密有理数的方案,并证明了该方案能抗自适应性地选择明文攻击;而后又提出了一种便于集合匹配计算的,称之为集合的定长向量编码方法;最后基于有理数加密方案和集合的定长向量编码方法构造了两个面向有理数的、无匹配差错的两方保密集合交集协议.与先前的两方保密集合交集协议相较之,这两个协议不仅解决了无匹配差错的两方保密集合交集计算,还拓展了保密集合交集问题中隐私保护的范畴:除了可以保护各参与方的隐私数据外,还可以保护各参与方隐私数据的数量.展开更多
隐私集合求交(private set intersection,简称PSI)是一种重要的密码原语.提出基于单态的量子隐私集合求交(quantum private set intersection,简称QPSI)协议.在该协议中,单态作为信息载体由一个半可信第三方制备,两个参与者根据各自的...隐私集合求交(private set intersection,简称PSI)是一种重要的密码原语.提出基于单态的量子隐私集合求交(quantum private set intersection,简称QPSI)协议.在该协议中,单态作为信息载体由一个半可信第三方制备,两个参与者根据各自的私有数据集将信息编码至载体粒子.参与者在半可信第三方协助下能获得正确的交集,且不会得到交集以外另一方集合的任何信息.该文协议能抵抗一些常见的外部攻击和内部攻击.该文协议可推广至多方情形,具有良好的扩展性。展开更多
支持模糊匹配的带标签隐私集合交集计算协议(Fuzzy Labeled Private Set Intersection,FLPSI)是PSI协议的变体,其特点在于发送方与接收方的集合元素并不完全相等,而是存在相似性,且发送方集合中的每个元素均关联一个标签,接收方仅得到...支持模糊匹配的带标签隐私集合交集计算协议(Fuzzy Labeled Private Set Intersection,FLPSI)是PSI协议的变体,其特点在于发送方与接收方的集合元素并不完全相等,而是存在相似性,且发送方集合中的每个元素均关联一个标签,接收方仅得到相似匹配元素的标签,而不会泄露其他信息。现有的FLPSI协议大多使用汉明距离来判断二进制向量之间的匹配程度,协议基于昂贵的公钥密码来构建,计算开销大导致协议运行缓慢。对此,提出了一种基于对称密码构造的更加高效的FLPSI协议,通过模拟范例证明了协议在半诚实模型下是安全的,参与方均无法窃取额外的隐私信息。与现有方案相比,协议将整体通信复杂度与发送方的计算复杂度由O(n^(2))降低为O(n)。实验仿真结果表明,所提方法在平衡场景下比现有FLPSI协议快3~10倍,通信量降低89%~95%;在非平衡场景下比现有FLPSI协议快7~10倍,与类似的模糊匹配协议相比具有明显优势。此外,还设计了FLPSI协议在隐私保护条件下人脸识别的应用,通过调整参数可以满足不同场景的要求。展开更多
隐私集合交集(private set intersection,PSI)是隐私计算中的热点,其允许参与两方在不泄露任何额外信息的要求下计算交集.现有的隐私集合交集计算方案对参与双方的计算能力要求高,且计算能力差的参与方无法在保证集合数据隐私的前提下...隐私集合交集(private set intersection,PSI)是隐私计算中的热点,其允许参与两方在不泄露任何额外信息的要求下计算交集.现有的隐私集合交集计算方案对参与双方的计算能力要求高,且计算能力差的参与方无法在保证集合数据隐私的前提下将计算安全外包给云服务器.设计了一种新的不经意两方分布式伪随机函数,允许半可信的云服务器参与相等性测试,又不泄露参与方任何集合信息.基于该不经意伪随机函数构建了半可信云服务器辅助的隐私集合交集计算协议,将主要计算量外包给云服务器.在半诚实模型下证明了协议的安全性.同时,该协议可保密地计算隐私集合交集的基数.通过与现有协议分析与实验性能比较,该协议效率高,计算复杂度与通信复杂度均与集合大小呈线性关系,适用于客户端设备受限的应用场景.展开更多
随着物联网和大数据技术的发展,在计算机和手机上出现了大量分布式应用程序.然而现有的分布式数据处理方式已不能很好地满足用户对隐私保护的需求.隐私集合交集(private set intersection,PSI)协议作为一项典型的面向隐私保护的分布式...随着物联网和大数据技术的发展,在计算机和手机上出现了大量分布式应用程序.然而现有的分布式数据处理方式已不能很好地满足用户对隐私保护的需求.隐私集合交集(private set intersection,PSI)协议作为一项典型的面向隐私保护的分布式集合计算技术,允许各参与方输入其私有集合,共同计算集合的交集,且不泄露除交集以外的任何信息.PSI协议作为安全多方计算的一种重要应用,已被广泛应用于隐私计算领域,具有重要的理论和实践意义.首先介绍PSI协议的基本密码技术、敌手模型、安全证明、编程框架等基础知识;其次系统总结了构造传统PSI协议的设计框架:基于公钥加密体制的框架、基于混淆电路的框架、基于不经意传输的框架;随后介绍PSI协议核心的隐私集合元素比较技术工具:不经意伪随机函数、不经意多项式评估、布隆过滤器等;进一步地详细阐述了适应新型应用场景的PSI方案:基于云辅助的PSI、非平衡型PSI、基于阈值的PSI和多方PSI;最后总结并展望面向隐私保护的集合交集计算中亟待解决问题和发展方向.展开更多
基金Project supported by the National Natural Science Foundation of China(Nos.61872069,61772127,61703088,and 61472184)
文摘Private set intersection(PSI) allows two parties to compute the intersection of their private sets while revealing nothing except the intersection. With the development of fog computing, the need has arisen to delegate PSI on outsourced datasets to the fog. However, the existing PSI schemes are based on either fully homomorphic encryption(FHE) or pairing computation. To the best of our knowledge, FHE and pairing operations consume a huge amount of computational resource. It is therefore an untenable scenario for resource-limited clients to carry out these operations. Furthermore, these PSI schemes cannot be applied to fog computing due to some inherent problems such as unacceptable latency and lack of mobility support. To resolve this problem, we first propose a novel primitive called " faster fog-aided private set intersection with integrity preserving", where the fog conducts delegated intersection operations over encrypted data without the decryption capacity. One of our technical highlights is to reduce the computation cost greatly by eliminating the FHE and pairing computation. Then we present a concrete construction and prove its security required under some cryptographic assumptions. Finally, we make a detailed theoretical analysis and simulation, and compare the results with those of the state-of-the-art schemes in two respects: communication overhead and computation overhead. The theoretical analysis and simulation show that our scheme is more efficient and practical.
基金supported by the National Natural Science Foundation of China(61802118)Natural Science Foundation of Heilongjiang Province(YQ2020F013)supported by the Advanced Programs of Heilongjiang Province for the Overseas Scholars and the Outstanding Youth Fund of Heilongjiang University and the Heilongjiang University Innovation Fund(YJSCX2022-247HLJU)
文摘In modern society,it is necessary to perform some secure computations for private sets between different entities.For instance,two merchants desire to calculate the number of common customers and the total number of users without disclosing their own privacy.In order to solve the referred problem,a semi-quantum protocol for private computation of cardinalities of set based on Greenberger-Horne-Zeilinger(GHZ)states is proposed for the first time in this paper,where all the parties just perform single-particle measurement if necessary.With the assistance of semi-honest third party(TP),two semi-quantum participants can simultaneously obtain intersection cardinality and union cardinality.Furthermore,security analysis shows that the presented protocol can stand against some well-known quantum attacks,such as intercept measure resend attack,entangle measure attack.Compared with the existing quantum protocols of Private Set Intersection Cardinality(PSI-CA)and Private Set Union Cardinality(PSU-CA),the complicated oracle operations and powerful quantum capacities are not required in the proposed protocol.Therefore,it seems more appropriate to implement this protocol with current technology.
文摘分布式计算有很多应用需要参与各方协同执行集合的一些计算但不泄露各自数据集的信息.保密集合交集(private set intersection,PSI)计算已经成为数据匹配、数据挖掘、推荐系统等应用中保护用户隐私的一个重要工具.本文的主要工作是构造无匹配差错的安全两方保密集合交集运算协议.着重探讨三个问题:(1)开发构造无匹配差错的两方保密集合交集计算所需要的工具(①面向有理数且具有语义安全性的加密方案,②便于集合匹配计算的称之为集合的定长向量编码方法);(2)无匹配差错的两方保密集合交集计算问题;(3)元素为有理数的保密集合交集计算问题.首先在标准模型下设计了一个能够加密有理数的方案,并证明了该方案能抗自适应性地选择明文攻击;而后又提出了一种便于集合匹配计算的,称之为集合的定长向量编码方法;最后基于有理数加密方案和集合的定长向量编码方法构造了两个面向有理数的、无匹配差错的两方保密集合交集协议.与先前的两方保密集合交集协议相较之,这两个协议不仅解决了无匹配差错的两方保密集合交集计算,还拓展了保密集合交集问题中隐私保护的范畴:除了可以保护各参与方的隐私数据外,还可以保护各参与方隐私数据的数量.
文摘隐私集合求交(private set intersection,简称PSI)是一种重要的密码原语.提出基于单态的量子隐私集合求交(quantum private set intersection,简称QPSI)协议.在该协议中,单态作为信息载体由一个半可信第三方制备,两个参与者根据各自的私有数据集将信息编码至载体粒子.参与者在半可信第三方协助下能获得正确的交集,且不会得到交集以外另一方集合的任何信息.该文协议能抵抗一些常见的外部攻击和内部攻击.该文协议可推广至多方情形,具有良好的扩展性。
文摘支持模糊匹配的带标签隐私集合交集计算协议(Fuzzy Labeled Private Set Intersection,FLPSI)是PSI协议的变体,其特点在于发送方与接收方的集合元素并不完全相等,而是存在相似性,且发送方集合中的每个元素均关联一个标签,接收方仅得到相似匹配元素的标签,而不会泄露其他信息。现有的FLPSI协议大多使用汉明距离来判断二进制向量之间的匹配程度,协议基于昂贵的公钥密码来构建,计算开销大导致协议运行缓慢。对此,提出了一种基于对称密码构造的更加高效的FLPSI协议,通过模拟范例证明了协议在半诚实模型下是安全的,参与方均无法窃取额外的隐私信息。与现有方案相比,协议将整体通信复杂度与发送方的计算复杂度由O(n^(2))降低为O(n)。实验仿真结果表明,所提方法在平衡场景下比现有FLPSI协议快3~10倍,通信量降低89%~95%;在非平衡场景下比现有FLPSI协议快7~10倍,与类似的模糊匹配协议相比具有明显优势。此外,还设计了FLPSI协议在隐私保护条件下人脸识别的应用,通过调整参数可以满足不同场景的要求。
文摘隐私集合交集(private set intersection,PSI)是隐私计算中的热点,其允许参与两方在不泄露任何额外信息的要求下计算交集.现有的隐私集合交集计算方案对参与双方的计算能力要求高,且计算能力差的参与方无法在保证集合数据隐私的前提下将计算安全外包给云服务器.设计了一种新的不经意两方分布式伪随机函数,允许半可信的云服务器参与相等性测试,又不泄露参与方任何集合信息.基于该不经意伪随机函数构建了半可信云服务器辅助的隐私集合交集计算协议,将主要计算量外包给云服务器.在半诚实模型下证明了协议的安全性.同时,该协议可保密地计算隐私集合交集的基数.通过与现有协议分析与实验性能比较,该协议效率高,计算复杂度与通信复杂度均与集合大小呈线性关系,适用于客户端设备受限的应用场景.
文摘随着物联网和大数据技术的发展,在计算机和手机上出现了大量分布式应用程序.然而现有的分布式数据处理方式已不能很好地满足用户对隐私保护的需求.隐私集合交集(private set intersection,PSI)协议作为一项典型的面向隐私保护的分布式集合计算技术,允许各参与方输入其私有集合,共同计算集合的交集,且不泄露除交集以外的任何信息.PSI协议作为安全多方计算的一种重要应用,已被广泛应用于隐私计算领域,具有重要的理论和实践意义.首先介绍PSI协议的基本密码技术、敌手模型、安全证明、编程框架等基础知识;其次系统总结了构造传统PSI协议的设计框架:基于公钥加密体制的框架、基于混淆电路的框架、基于不经意传输的框架;随后介绍PSI协议核心的隐私集合元素比较技术工具:不经意伪随机函数、不经意多项式评估、布隆过滤器等;进一步地详细阐述了适应新型应用场景的PSI方案:基于云辅助的PSI、非平衡型PSI、基于阈值的PSI和多方PSI;最后总结并展望面向隐私保护的集合交集计算中亟待解决问题和发展方向.
