Computer Science ›› 2016, Vol. 43 ›› Issue (4): 127-133.doi: 10.11896/j.issn.1002-137X.2016.04.026

Previous Articles     Next Articles

Secure Multi-party Computation Based on Symbolic Edge-valued Binary Decision Diagram

XU Zhou-bo, YU Qiang-sheng, GU Tian-long and NING Li-hua   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Efficient representation of the decision function is a hot problem in the study of secure multi-party computation.Symbol description technology is a novel method for the decision function representation.Aiming at the problem of leaf nodes expansion which leads to state explosion in the protocol produced by the algebraic decision diagram (ADD) representation of decision function,an edge-valued binary decision diagram (EVBDD) technique was introduced,and then a new method for decision function representation based on EVBDD was proposed.Firstly,the decision function is transformed to symbolic EVBDD form by using the structure of EVBDD,and thus the problem of leaf nodes expansion is avoided.Secondly,through adding virtual nodes,the privacy issues appeared on the computation path is solved.Furthermore,an EVBDD encryption algorithm was proposed,and a new secure two-party computation protocol based on EVBDD was designed.Finally,the correctness,security and efficiency of the new protocol was analyzed,demonstrating a considerable improvement in efficiency of the new protocol compared to the method based on ADD.

Key words: Secure multi-party computation,Decision function,Edge-valued binary decision diagram,State space explosion

[1] Katz J,Malka L.Secure text processing with applications to private DNA matching[C]∥Proceedings of the 17th ACM Conference on Computer and Communications Security.ACM,2010:485-492
[2] Liu Wen,Wang Yong-bin.Secure Multi-Party Comparing protocol and Its Applications[J].Acta Electronica Sinica,2012,40(5):871-876(in Chinese) 刘文,王永滨.安全多方信息比较相等协议及其应用[J].电子学报,2012,40(5):871-876
[3] Li Shun-dong,Wang Dao-shun.Efficient Secure Multiparty Com-putation Based on Homomorphic Encryption[J].Acta Electronica Sinica,2013,41(4):798-803(in Chinese) 李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803
[4] Yao A C.Protocols for secure computations[C]∥2013 IEEE 54th Annual Symposium on Foundations of Computer Science.IEEE,1982:160-164
[5] Yao A C.How to generate and exchange secrets[C]∥27th Annual Symposium on Foundations of Computer Science,1986.IEEE,1986:162-167
[6] Lindell Y,Pinkas B.A proof of security of Yao’s protocol for two-party computation[J].Journal of Cryptology,2009,22(2):161-188
[7] Pinkas B,Schneider T,Smart N P,et al.Secure two-party computation is practical[M]∥Advances in Cryptology-ASIACRYPT 2009.Springer Berlin Heidelberg,2009:250-267
[8] Kolesnikov V,Schneider T.Improved garbled circuit:Free XOR gates and applications[M]∥Automata,Languages and Programming.Springer Berlin Heidelberg,2008:486-498
[9] Naor M,Pinkas B,Sumner R.Privacy preserving auctions and mechanism design[C]∥Proceedings of the 1st ACM Conference on Electronic Commerce.ACM,1999:129-139
[10] Lindell Y,Pinkas B,Smart N P.Implementing two-party computation efficiently with security against malicious adversaries [M]∥Security and Cryptography for Networks.Springer Berlin Heidelberg,2008:2-20
[11] Jarvinen K,Kolesnikov V,Sadeghi A R,et al.Embedded SFE:Offloading server and network using hardware tokens[M]∥Financial Cryptography and Data Security.Springer Berlin Heidelberg,2010:207-221
[12] Iliev A,Smith S W.Small,stupid,and scalable:secure computing with faerieplay[C]∥Proceedings of the fifth ACM Workshop on Scalable Trusted Computing.ACM,2010:41-52
[13] Gunupudi V,Tate S R.Generalized non-interactive oblivioustransfer using count-limited objects with applications to secure mobile agents[M]∥Financial Cryptography and Data Security.Springer Berlin Heidelberg,2008:98-112
[14] Goldwasser S,Kalai Y T,Rothblum G N.One-time programs[M]∥Advances in Cryptology-CRYPTO 2008.Springer Berlin Heidelberg,2008:39-56
[15] Jarvinen K,Kolesnikov V,Sadeghi A R,et al.Garbled circuits for leakage-resilience:Hardware implementation and evaluation of one-time programs[M]∥Cryptographic Hardware and Embedded Systems,CHES 2010.Springer Berlin Heidelberg,2010:383-397
[16] Malkhi D,Nisan N,Pinkas B,et al.Fairplay-Secure Two-Party Computation System[C]∥USENIX Security Symposium.2004:287-302
[17] Ben-David A,Nisan N,Pinkas B.FairplayMP:a system for secure multi-party computation[C]∥Proceedings of the 15th ACM Conference on Computer and Communications Cecurity.ACM,2008:257-266
[18] Kruger L,Jha S,Goh E J,et al.Secure function evaluation with ordered binary decision diagrams[C]∥Proceedings of the 13th ACM Conference on Computer and Communications Security.ACM,2006:410-420
[19] Gu Tian-long,He Zhong-chun,Chang Liang,et al.Secure Evaluation of Classification Algorithms Based on Symbolic ADD and Linear Multi-Branching Program[J].Acta Electronica Sinica,2014,42(5):940-947(in Chinese) 古天龙,何仲春,常亮,等.基于符号ADD和线性多分支程序的分类算法安全评估[J].电子学报,2014,42(5):940-947
[20] Goldreich O.Foundations of cryptography[M].Beijing:Pub-lishing house of electronics industry,2003(in Chinese) Goldreich O.密码学基础:英文版[M].北京:电子工业出版社,2003
[21] Canetti R.Studies in secure multiparty computation and applications[D].The Weizmann Institute of Science,1996
[22] Rabin M O.How To Exchange Secrets with Oblivious Transfer[J].IACR Cryptology ePrint Archive,2005:187
[23] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]∥Advances in Cryptology—EUROCRYPT’99.Springer Berlin Heidelberg,1999:223-238
[24] Lai Y T,Pedram M,Vrudhula S B K.EVBDD-based algorithms for integer linear programming,spectral transformation,and function decomposition[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1994,13(8):959-975
[25] Gu Tian-long,Xu Zhou-bo.Ordered binary decision diagram and its application[M].Beijing:Science Press Ltd.,2009:17-57(in Chinese) 古天龙,徐周波.有序二叉树决策图及应用[M].北京:科学出版社,2009:17-57

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .