排序问题的安全多方计算协议  

Secure multi-party computation protocol for sequencing problem

作　　者：唐春明[1,2] 石桂花[1] 姚正安[3] 

机构地区：[1]广州大学数学与信息科学学院,广州510006 [2]中国科学院软件研究所信息安全国家重点实验室,北京100080 [3]中山大学数学与计算科学学院,广州510275

出　　处：《中国科学：信息科学》2011年第7期789-797,共9页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:10871222)资助项目

摘　　要：为某些特殊问题构造有效的安全多方计算协议是多方计算研究领域的一个重要分支.文中使用密钥共享方案为排序问题构造了一个有效的安全多方计算协议,该协议在n个参与者中至多只有t个不诚实者,若t≤(n-1)/2,则它在被动攻击下是完全安全的;若t<n/3时,它在主动攻击下是完全安全的.排序问题的最简单形式就是"百万富翁"问题.In multi-party computation field,one important branch is to construct an efficient and secure multiparty computation for some special problems.In this paper,we make use of secret sharing scheme to construct an efficient and secure multi-party computation for sequencing problem.Our protocols are perfectly secure against passive adversary if it can corrupt at most t≤（n-1）/2 participants,and is perfectly secure against active adversary if it can corrupt at most tn/3 participants.The simplest sequencing problem is millionaire problem.

关 键 词：安全多方计算 排序问题 密钥分享 

分 类 号：O223[理学—运筹学与控制论]