Research and Implementation of Privacy Preserving Set Union in Boolean Circuits
SUN Maohua① HU Lei① ZHU Hongliang② LI Qi②
①(Information School, Capital University of Economics and Business, Beijing 100070, China) ②(School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China)
Privacy-preserving technology is the focus of information security area. Unfortunately, rare implementation of private set union protocol is developed. To solve the issue above, a novel private set union protocol based on the YAO’s garbled circuit technology is presented. The specially designed circuits include the private set merge circuit, the private set filter circuit and the private set confusion circuit. Then, the security of the novel protocol is proven in semi-honest model. Finally, a prototype of the protocol is built based on the MightBeEvil framework. The simulation results show that this protocol is more efficient than the existing one when evaluating the union of sparse sets in a privacy-preserving manner.
孙茂华,胡磊,朱洪亮,李祺. 布尔电路上保护隐私集合并集运算的研究与实现[J]. 电子与信息学报, 2016, 38(6): 1412-1418.
SUN Maohua, HU Lei, ZHU Hongliang, LI Qi. Research and Implementation of Privacy Preserving Set Union in Boolean Circuits. JEIT, 2016, 38(6): 1412-1418.
KISSNER L and SONG D X. Privacy-preserving set operations[C]. Advances in Cryptology- CRYPTO, Santa Barbara, USA, 2005: 241-257.doi: 10.1007/11535218_15.
[2]
FRIKKEN K B. Privacy-preserving set union[C]. Applied Cryptography and Network Security, Zhuhai, China, 2007: 237-252. doi: 10.1007/978-3-540-72738-5_16.
[3]
SEO J H, CHEON J H, and KAZA J. Constant-round multi- party private set union using reversed laurent series[C]. Proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, 2012: 398-412. doi: 10.1007/978-3-642-30057-8_24.
[4]
MANY D, BURKHART M, and DIMITROPOULOS X. Fast private set operations with sepia[OL]. http://sepia.ee.ethz. ch/publications/setops_TIK-Report-345.pdf, 2012.
[5]
KERSCHBAUM F. Outsourced private set intersection using homomorphic encryption[C]. Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, Seoul, Republic of Korea, 2012: 85-86. doi: 10. 1145/2414456.2414506.
[6]
DONG C Y, CHEN L Q, and WEN Z K. When private set intersection meets big data: an efficient and scalable protocol [C]. Proceedings of the 2013 ACM SIGSAC conference on Computer & Communication Security, New York, 2013: 789-800.
[7]
KAMARA S, MOHASSEL P, RAYKOVA M, et al. Scaling private set intersection to billion-element sets[C]. Financial Cryptography and Data Security, Barbados, West Indies, 2014: 195-215.
[8]
FREEDMAN J F, HAZAY C, NISSIM K, et al. Efficient set-intersection with simulation-based security[J]. Journal of Cryptology, 2016, 29(1): 115-155. doi: 10.1007/s00145- 014-9190-0.
[9]
PINKAS B, SCHNEIDER T, and ZOHNER M. Faster private set intersection based on OT extension[C]. Proceedings of the 23rd USENIX Security Symposium, San Diego, 2014: 797-812.
[10]
HAZAY C. Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs[C]. Theory of Cryptography Conference, Warsaw, Poland, 2015: 90-120. doi: 10.1007/978-3-662-46497-7_4.
[11]
D’ARCO P, VASCO M I G, DEL POZO A L P, et al. Size- hiding in private set intersection: What can be done and how to do it without random oracles[OL]. https://eprint.iacr. org/2015/321. 2015.
[12]
ZHENG Q J and XU S H. Verifiable delegated set intersection operations on outsourced encrypted data[C]. 2015 IEEE International Conference on Cloud Engineering, Tempe, AZ, USA, 2015: 175-184. doi: 10.1109/IC2E.2015.38.
[13]
WANG T T, ZHU Y Q, and LUO X Z. Publicly verifiable delegation of set intersection[C]. 2014 International Conference on Cloud Computing and Internet of Things, Changchun, China, 2014: 26-30. doi: 10.1109/CCIOT.2014. 7062500.
[14]
LIU F, WEE K N, ZHANG W, et al. Encrypted set intersection protocol for outsourced datasets[C]. 2014 International Conference on Cloud Engineering, Boston, USA, 2014: 135-140.
XIA F, YANG B, ZHANG M W, et al. Secure two-party computation for set intersection and set equality problems based on LWE[J]. Journal of Electronics & Information Technology, 2012, 34(2): 462-467. doi: 10.3724/SP.J.1146. 2011.00541.
[16]
BRICKELL J and SHMATIKOV V. Privacy-preserving graph algorithms in the semi-honest model[C]. Advances in Cryptology-ASIACRYPT, Chennai, India, 2005: 236-252.
[17]
HUANG Y, EVANS D, and KATZ J. Private set intersection: Are garbled circuits better than custom protocols?[C]. Proceedings of the 19th Network and Distributed Security Symposium, San Diego, CA, USA, 2012.
[18]
PINKAS B, SCHNEIDER T, SEGEV G, et al. Phasing: private set intersection using permutation-based hashing[C]. Proceedings of the 24th Conference on USENIX Security Symposium, Washington D.C., 2015: 515-530.
[19]
KOLESNIKOV V, SADEGHI A R, and SCHNEIDER T. Improved garbled circuit building blocks and applications to auctions and computing minima[C]. Proceedings of the 8th International Conference on Cryptology and Network Security, Kanazawa, Japan, 2009: 1-20. doi: 10.1007/978-3- 642-10433-6_1.
[20]
KOLESNIKOV V and SCHNEIDER T. Improved garbled circuit: free XOR gates and applications[C]. International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, 2008: 486-498.
[21]
DE CRISTOFARO E and TSUDIK G. Practical private set intersection protocols with linear complexity[C]. Financial Cryptography and Data Security, Tenerife, Canary Islands, 2010: 143-159. doi: 10.1007/978-3-642-14577-3_13.
[22]
NAOR M and PINKAS B. Efficient oblivious transfer protocols[C]. Proceedings of the 12th Annual Symposium on Discrete Alogrithms, Washington, D.C., USA, 2001: 448-457.
[1]
张少波, Md Zakirul Alam Bhuiyan,刘琴,孟大程,王国军. 移动社交网络中基于代理转发机制的轨迹隐私保护方法[J]. 电子与信息学报, 2016, 38(9): 2158-2164.
