Research and Implementation of Privacy Preserving Set Union in Boolean Circuits

SUN Maohua; HU Lei; ZHU Hongliang; LI Qi

doi:10.11999/JEIT150911

Volume 38 Issue 6

Jun. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(6): 1412-1418

SUN Maohua, HU Lei, ZHU Hongliang, LI Qi. Research and Implementation of Privacy Preserving Set Union in Boolean Circuits[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1412-1418. doi: 10.11999/JEIT150911

Citation:

SUN Maohua, HU Lei, ZHU Hongliang, LI Qi. Research and Implementation of Privacy Preserving Set Union in Boolean Circuits[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1412-1418. doi: 10.11999/JEIT150911

Citation:

PDF( 609 KB)

Research and Implementation of Privacy Preserving Set Union in Boolean Circuits

doi: 10.11999/JEIT150911

1.
(Information School, Capital University of Economics and Business, Beijing 100070, China)
2.
(School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China)

Funds:

Young Scientific Research Starting Foundation of CUEB 2014, Young Scientists Program of CUEB (2014XJQ016), The National Natural Science Foundation of China (61302087), Improve Scientific Rescarch Foundation of Beijing Education 2016

Received Date: 2015-08-05
Rev Recd Date: 2016-02-29
Publish Date: 2016-06-19

Abstract

Abstract

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 YAOs 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.
- Secure multi-party computation,
- YAOs garbled circuit technology,
- Private set operation

FullText(HTML)

References(22)

References

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.

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.

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.

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.

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.

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.

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.

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.

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.

DARCO 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.

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.

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.

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.

夏峰, 杨波, 张明武, 等. 基于LWE的集合相交和相等的两方保密计算[J]. 电子与信息学报, 2012, 34(2): 462-467. doi: 10.3724/SP.J.1146.2011.00541.

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.

BRICKELL J and SHMATIKOV V. Privacy-preserving graph algorithms in the semi-honest model[C]. Advances in Cryptology-ASIACRYPT, Chennai, India, 2005: 236-252.

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.

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.

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.

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.

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.

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.

Relative Articles

Supplements(0)

Cited By

Proportional views