高效可验证的雾辅助私有集合交集计算

王强; 周福才; 马铁民; 徐紫枫

doi:10.1631/FITEE.1800518

Your Location：

Home >

Browse articles >

高效可验证的雾辅助私有集合交集计算

网络空间安全专辑 | Updated：2022-05-19

- 高效可验证的雾辅助私有集合交集计算
- Faster fog-aided private set intersection with integrity preserving
- 信息与电子工程前沿（英文） 2018年19卷第12期页码：1558-1568
- Affiliations：
  
  Software College, Northeastern University, Shenyang 100819, China
  School of Computer Science and Engineering, Northeastern University, Shenyang 100819, China
- Author bio：
  
  [ "Qiang WANG, E-mail: wangq3635@126.com" ]
  Fu-cai ZHOU, E-mail: fczhou@mail.neu.edu.cn
  [ "Tie-min MA, E-mail: mtmwx@163.com" ]
  [ "Zi-feng XU, E-mail: dk@tnimdk.com" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61872069, 61772127, 61703088, and 61472184)
- DOI：10.1631/FITEE.1800518
  中图分类号： TP309
- 收稿：2018-08-30，
  
  修回：2018-12-17，
  
  纸质出版：2018-12
- Accepted：
Scan QR Code
王强, 周福才, 马铁民, 等. 高效可验证的雾辅助私有集合交集计算[J]. 信息与电子工程前沿（英文）, 2018,19(12):1558-1568.

Qiang WANG, Fu-cai ZHOU, Tie-min MA, et al. Faster fog-aided private set intersection with integrity preserving[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(12): 1558-1568.
王强, 周福才, 马铁民, 等. 高效可验证的雾辅助私有集合交集计算[J]. 信息与电子工程前沿（英文）, 2018,19(12):1558-1568. DOI： 10.1631/FITEE.1800518.

Qiang WANG, Fu-cai ZHOU, Tie-min MA, et al. Faster fog-aided private set intersection with integrity preserving[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(12): 1558-1568. DOI： 10.1631/FITEE.1800518.

摘要

私有集合交集计算允许两方实体在不泄露除交集结果以外其他信息的前提下计算出两方实体的集合交集。随着雾计算的发展，将集合交集外包至雾的需求应运而生。然而，目前私有集合交集计算都是基于全同态加密和配对操作，所需代价较高且不支持移动，难以在雾计算中应用。提出一种高效可验证的雾辅助私有集合交集计算方案。在该方案中，实体将私有集合交集计算外包至雾，雾在没有解密能力的前提下计算集合交集。该方案不依赖全同态加密和配对操作，极大提高了计算效率。此外，构建并证明了该方案的安全性。最后，对比分析本方案与其他方案的通信复杂度和计算复杂度。分析结果表明，该方案更高效，更具现实意义。

Abstract

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.

关键词

Keywords

references

A Abadi , , , S Terzis , , , CY Dong . . VD-PSI: verifiable delegated private set intersection on outsourced private datasets . . Proc Int Conf on Financial Cryptography and Data Security , , 2016 . . p.149 - - 168 . . DOI: 10.1007/978-3-662-54970-4_9 http://doi.org/10.1007/978-3-662-54970-4_9 . .

G Ateniese , , , E de Cristofaro , , , G Tsudik . . (If) size matters: size-hiding private set intersection . . Proc Int Workshop on Public Key Cryptography , , 2011 . . p.156 - - 173 . . DOI: 10.1007/978-3-642-19379-8_10 http://doi.org/10.1007/978-3-642-19379-8_10 . .

P Baldi , , , R Baronio , , , E de Cristofaro , , , 等 . . Countering GATTACA: efficient and secure testing of fully-sequenced human genomes . . Proc 18 th ACM Conf on Computer and Communications Security , , 2011 . . p.691 - - 702 . . DOI: 10.1145/2046707.2046785 http://doi.org/10.1145/2046707.2046785 . .

H Chen , , , K Laine , , , P Rindal . . Fast private set intersection from homomorphic encryption . . Proc ACM SIGSAC Conf on Computer and Communications Security , , 2017 . . p.1243 - - 1255 . . DOI: 10.1145/3133956.3134061 http://doi.org/10.1145/3133956.3134061 . .

BH Falk , , , D Noble , , , R Ostrovsky . . Private Set Intersection with Linear Communication from General Assumptions . . Cryptology ePrint Archive: Report 2018/238 , , 2018 . . .

MJ Freedman , , , K Nissim , , , B Pinkas . . Efficient private matching and set intersection . . Proc Int Conf on the Theory and Applications of Cryptographic Techniques , , 2004 . . p.1 - - 19 . . DOI: 10.1007/978-3-540-24676-3_1 http://doi.org/10.1007/978-3-540-24676-3_1 . .

E Ghosh , , , O Ohrimenko , , , D Papadopoulos , , , 等 . . Zero-Knowledge Accumulators and Set Operations . . Cryptology ePrint Archive: 2015/404 , , 2015 . . http://www.iacr.org/cryptodb/data/paper.php?pubkey=26395 http://www.iacr.org/cryptodb/data/paper.php?pubkey=26395 , , . .

ZT Guan , , , J Li , , , LF Wu , , , 等 . . Achieving efficient and secure data acquisition for cloud-supported Internet of Things in smart grid . . IEEE Internet Things J , , 2017 . . 4 ( ( 6 ): ): 1934 - - 1944 . . DOI: 10.1109/JIOT.2017.2690522 http://doi.org/10.1109/JIOT.2017.2690522 . .

M Ion , , , B Kreuter , , , E Nergiz , , , 等 . . Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions . . Cryptology ePrint Archive: Report 2017/738 , , 2017 . . .

S Kamara , , , P Mohassel , , , M Raykova , , , 等 . . Scaling private set intersection to billion-element sets . . Proc Int Conf on Financial Cryptography and Data Security , , 2014 . . p.195 - - 215 . . DOI: 10.1007/978-3-662-45472-5_13 http://doi.org/10.1007/978-3-662-45472-5_13 . .

CF Kerry , , , A Secretary , , , CR Director . . Federal Information Processing Standards Publication Digital Signature Standard (DSS), FIPS PUB 186-4 . . National Institute of Standards and Technology of America , , 2013 . . .

V Kolesnikov , , , R Kumaresan , , , M Rosulek , , , 等 . . Efficient batched oblivious PRF with applications to private set intersection . . Proc ACM SIGSAC Conf on Computer and Communications Security , , 2016 . . p.818 - - 829 . . DOI: 10.1145/2976749.2978381 http://doi.org/10.1145/2976749.2978381 . .

V Kolesnikov , , , N Matania , , , B Pinkas , , , 等 . . Practical multi-party private set intersection from symmetric-key techniques . . Proc ACM SIGSAC Conf on Computer and Communications Security , , 2017 . . p.1257 - - 1272 . . DOI: 10.1145/3133956.3134065 http://doi.org/10.1145/3133956.3134065 . .

M Nagy , , , E de Cristofaro , , , A Dmitrienko , , , 等 . . Do I know you . . : efficient and privacy-preserving common friend-finder protocols and applications. Proc 29 th Annual Computer Security Applications Conf , , 2013 . . p.159 - - 168 . . DOI: 10.1145/2523649.2523668 http://doi.org/10.1145/2523649.2523668 . .

A Narayanan , , , N Thiagarajan , , , M Lakhani , , , 等 . . Location privacy via private proximity testing . . Network and Distributed System Security Symp , , 2011 . . .

K Nyberg , , , RA Rueppel . . Message recovery for signature schemes based on the discrete logarithm problem . . Proc Workshop on the Theory and Application of Cryptographic Techniques , , 1994 . . p.182 - - 193 . . DOI: 10.1007/BFb0053434 http://doi.org/10.1007/BFb0053434 . .

M Orr , , , E Orsini , , , P Scholl . . Actively secure 1-out-of- N OT extension with application to private set intersection . . Proc Cryptographers' Track at the RSA Conf , , 2017 . . p.381 - - 396 . . DOI: 10.1007/978-3-319-52153-4_22 http://doi.org/10.1007/978-3-319-52153-4_22 . .

C Papamanthou , , , R Tamassia , , , N Triandopoulos . . Optimal verification of operations on dynamic sets . . 31 st Annual Cryptology Conf , , 2011 . . p.91 - - 110 . . DOI: 10.1007/978-3-642-22792-9_6 http://doi.org/10.1007/978-3-642-22792-9_6 . .

B Pinkas , , , T Schneider , , , M Zohner . . Faster private set intersection based on OT extension . . Proc 23 rd USENIX Conf on Security Symp , , 2014 . . p.797 - - 812 . . . .

B Pinkas , , , T Schneider , , , G Segev , , , 等 . . Phasing: private set intersection using permutation-based hashing . . Proc 24 th USENIX Conf on Security Symp , , 2015 . . p.515 - - 530 . . . .

B Pinkas , , , T Schneider , , , M Zohner . . Scalable private set intersection based on OT extension . . ACM Trans Priv Secur , , 2018 . . 21 ( ( 2 ): ): 7.1 - - 7.35 . . DOI: 10.1145/3154794 http://doi.org/10.1145/3154794 . .

P Rindal , , , M Rosulek . . Improved private set intersection against malicious adversaries . . Proc 36th Annual Int Conf on the Theory and Applications of Cryptographic Techniques , , 2017a . . p.235 - - 259 . . DOI: 10.1007/978-3-319-56620-7_9 http://doi.org/10.1007/978-3-319-56620-7_9 . .

P Rindal , , , M Rosulek . . Malicious-secure private set intersection via dual execution . . Proc ACM SIGSAC Conf on Computer and Communications Security , , 2017b . . p.1229 - - 1242 . . DOI: 10.1145/3133956.3134044 http://doi.org/10.1145/3133956.3134044 . .

University Stanford . . The Pairing-Based Cryptography Library . . 2013 . . https://crypto.stanford.edu/pbc https://crypto.stanford.edu/pbc , , . .

J Wu , , , MX Dong , , , K Ota , , , 等 . . Big data analysis-based secure cluster management for optimized control plane in software-defined networks . . IEEE Trans Netw Serv Manag , , 2018 . . 15 ( ( 1 ): ): 27 - - 38 . . DOI: 10.1109/TNSM.2018.2799000 http://doi.org/10.1109/TNSM.2018.2799000 . .

E Zhang , , , FH Li , , , B Niu , , , 等 . . Server-aided private set intersection based on reputation . . em Inform Sci , , 2017 . . 387 180 - - 194 . . DOI: 10.1016/j.ins.2016.09.056 http://doi.org/10.1016/j.ins.2016.09.056 . .

QJ Zheng , , , SH Xu . . Verifiable delegated set intersection operations on outsourced encrypted data . . Proc IEEE Int Conf on Cloud Engineering , , 2015 . . p.175 - - 184 . . DOI: 10.1109/IC2E.2015.38 http://doi.org/10.1109/IC2E.2015.38 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

FedSTGCN: a novel federated spatiotemporal graph learning-based network intrusion detection method for the Internet of Things

SIoTFog: Byzantine-resilient IoT fog networking

Cryptanalysis of an identity-based public auditing protocol for cloud storage