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

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

作　　者：徐周波[1] 俞强生 古天龙[1] 宁黎华[1] 

机构地区：[1]桂林电子科技大学广西可信软件重点实验室,桂林541004

出　　处：《计算机科学》2016年第4期127-133,共7页Computer Science

基　　金：国家自然科学基金(61100025;61262030;61363030);广西自然科学基金(2014GXNSFAA118354);广西高等学校高水平创新团队;卓越学者计划资助

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

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

分 类 号：TP309[自动化与计算机技术—计算机系统结构]