基于符号EVBDD的安全多方计算

doi:10.11896/j.issn.1002-137X.2016.04.026

摘要/Abstract

摘要： 决策函数的有效表示是安全多方计算研究中的热点问题。符号描述技术是表示决策函数的一种新方法。针对基于代数决策图(ADD)的决策函数表示中出现的叶子节点规模膨胀以及导致协议面临的状态空间爆炸问题,引入边值二叉决策图(EVBDD)技术,给出了一种基于EVBDD的决策函数表示方法。该方法首先利用EVBDD结构,将决策函数描述为EVBDD的符号化形式,避免了传统ADD表示中出现的叶子节点规模膨胀现象。然后通过添加虚节点,解决了计算路径上出现的隐私泄露问题。在此基础上,提出了EVBDD的加解密算法,并设计了一种新的基于EVBDD的安全两方计算协议。最后,对协议的正确性、安全性和效率进行了分析。结果表明,与基于代数决策图的解决方案相比,新协议在效率上有明显的提高。

关键词: 安全多方计算,决策函数,边值二叉决策图,状态空间爆炸

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

徐周波,俞强生,古天龙,宁黎华. 基于符号EVBDD的安全多方计算[J]. 计算机科学, 2016, 43(4): 127-133. https://doi.org/10.11896/j.issn.1002-137X.2016.04.026

XU Zhou-bo, YU Qiang-sheng, GU Tian-long and NING Li-hua. Secure Multi-party Computation Based on Symbolic Edge-valued Binary Decision Diagram[J]. Computer Science, 2016, 43(4): 127-133. https://doi.org/10.11896/j.issn.1002-137X.2016.04.026

参考文献

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed