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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!