计算机科学 ›› 2016, Vol. 43 ›› Issue (4): 127-133.doi: 10.11896/j.issn.1002-137X.2016.04.026
徐周波,俞强生,古天龙,宁黎华
XU Zhou-bo, YU Qiang-sheng, GU Tian-long and NING Li-hua
摘要: 决策函数的有效表示是安全多方计算研究中的热点问题。符号描述技术是表示决策函数的一种新方法。针对基于代数决策图(ADD)的决策函数表示中出现的叶子节点规模膨胀以及导致协议面临的状态空间爆炸问题,引入边值二叉决策图(EVBDD)技术,给出了一种基于EVBDD的决策函数表示方法。该方法首先利用EVBDD结构,将决策函数描述为EVBDD的符号化形式,避免了传统ADD表示中出现的叶子节点规模膨胀现象。然后通过添加虚节点,解决了计算路径上出现的隐私泄露问题。在此基础上,提出了EVBDD的加解密算法,并设计了一种新的基于EVBDD的安全两方计算协议。最后,对协议的正确性、安全性和效率进行了分析。结果表明,与基于代数决策图的解决方案相比,新协议在效率上有明显的提高。
[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! |
|