推荐星级：
- 1
- 2
- 3
- 4
- 5
集合成员关系的安全多方计算及其应用
资料介绍
集合成员关系的安全多方计算在保密数据挖掘和保密数据查询等方面有着重要的应用价值.针对以往方案在集合规模较大时的低效问题,本文将原问题转化成多项式一次性求值问题,在此基础上共设计了四个协议.利用同态加密设计了平凡协议1;利用离散对数设计了高效协议2,此协议非常简洁.最后,针对不同的应用场景又分别设计了云计算环境下外包用户计算的协议3和抗抵赖环境下可公开保密判定的协议4.通过分析和比较显示,我们的方案除了集合的势,其余任何信息都没有泄露,并且在集合规模较大时,相比以往方案高效而简洁.
部分文件列表
| 文件名 | 大小 |
| 集合成员关系的安全多方计算及其应用.pdf | 1M |
部分页面预览
（完整内容请下载后查看）5
Vol． 45 No． 5
May 2017
第
期
电
子
学
报
2017
5
ACTA ELECTRONICA SINICA
年
月
集合成员关系的安全多方计算及其应用
1
2
3
4
1
， ， ， ，
陈振华 李顺东 王道顺 黄 琼 张卫国
( 1．
，
西安科技大学计算机科学与技术学院 陕西西安
710054; 2．
，
710062;
陕西师范大学计算机科学学院 陕西西安
， 510642)
华南农业大学数学与信息学院 广东广州
3． ， 100084; 4．
清华大学计算机科学与技术系 北京
:
．
集合成员关系的安全多方计算在保密数据挖掘和保密数据查询等方面有着重要的应用价值 针对以往
摘
要
， ， ．
方案在集合规模较大时的低效问题 本文将原问题转化成多项式一次性求值问题 在此基础上共设计了四个协议 利
1; 2， ． ，
用同态加密设计了平凡协议 利用离散对数设计了高效协议 此协议非常简洁 最后 针对不同的应用场景又分别
3 4． ，
设计了云计算环境下外包用户计算的协议 和抗抵赖环境下可公开保密判定的协议 通过分析和比较显示 我们的
， ， ，
方案除了集合的势 其余任何信息都没有泄露 并且在集合规模较大时 相比以往方案高效而简洁
．
:
;
;
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
集合成员 安全多方计算 同态加密 离散对数 云计算 抗抵赖
TP309 0372-2112 ( 2017) 05-1109-08
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 05． 013
:
:
A
:
文章编号
文献标识码
电子学报
Secure Multiparty Computation of Set Membership and Its Applications
1
2
3
4
1
CHEN Zhen-hua ，LI Shun-dong ，WANG Dao-shun ，HUANG Qiong ，ZHANG Wei-guo
( 1． School of Computer Science and Technology，Xi’an University of Science and Technology，Xi’an，Shaanxi 710054，China;
2． School of Computer Science，Shaanxi Normal University，Xi’an，Shaanxi 710062，China;
3． Department of Computer Science and Technology，Tsinghua University，Beijing 100084，China;
4． College of Mathematics and Informatics，South China Agricultural University，Guangzhou，Guangdong 510642，China)
Abstract: Secure multiparty computation of set membership is significant to privacy-preserving data mining，data que-
ry，etc． In this paper，we first transform the original problem into the one-time evaluation problem for polynomial，and then
construct four protocols． We design the trivial protocol 1 using homomorphic encryption and construct the efficient protocol 2
using discrete logarithm instead of encryption，which is very concise． Lastly，according to the different application scenarios，
we also propose protocol 3 and protocol 4: the former can be used to outsource computation in cloud computing environ-
ment; the latter can be used for public secure computation against repudiation． The analysis and comparison show that our
protocols are more efficient and concise than previously known．
Key words:
set membership; secure multi-party computation; homomorphic encryption; discrete logarithm; cloud
computing; against repudiation
［8］
Goldwasser
曾预言安全多方计算所处的地位就如
1
引言
10
，
年前所处的地位一样重要 它是计算
同公钥密码学
［1］
Yao
，
提出 是指在不泄漏各
安全多方计算最早由
， ．
科学一个极其重要的工具 而实际应用才刚起步 因此
( ) ，
方的输入数据 隐私性 的条件下 能正确完成输入数
丰富其理论将使它成为计算科学和现实应用中一个必
［9，10］
( ) ．
据的函数计算 正确性 安全多方计算的特点使得人
．
不可少的工具 接着
，Goldreich
等人
给出了安全多
们能够最大限度的利用私有数据完成所需的计算任务
，
方计算问题的通用解决方案 从理论上证明了一般的
［2］
．
、
而不破坏数据的隐私性 因此它在科学计算
保密数
、
云计算 等方面有着广
，
多方保密计算问题是可解的 并引入了安全多方计算
［3，4］
［5，6］
［7］
、
据挖掘
保密数据查询
． ，
的安全性形式化定义与模拟范例 但同时他们指出 由
．
泛的应用
，
于效率问题 利用通用的解决方案解决安全多方计算
: 2015-11-02;
: 2016-05-12;
:
责任编辑 马兰英
收稿日期
修回日期
:
基金项目 西安科技大学博士启动基金
( No． 2015QDJ008) ;
( No． 2016-MS-19)
信息安全国家重点实验室开放课题基金
1110
2017
年
电
子
学
报
， ，
问题虽在理论上可行 而在实际中并不可行 应该具体
( 2)
，
在将原问题转化成其他问题的基础上 设计了
． Goldwasser Gold-
问题研究具体的解决方案 的预言和
等人的工作使得针对特定领域构造安全多方计算
4
:
个协议
( i)
reich
1．
利用同态加密算法设计了平凡协议
，
的高效解决方案 成为了现代密码学的研究热点之一
．
( ii)
，
利用离散对数而非加密的方法 设计了高效
，
本文也正是针对这一点 就具体问题进行了具体
2， ．
协议 此协议非常简洁
．
的研究
( iii)
，
2-DFN( Dis-
的同态加密算法设计了应用
，
首次针对云外包计算场景 利用
［11］
Du
，
在前人的基础上 进一步研究了一些具
等人
junctive Normal Form，DNF)
， 、
体的安全多方计算问题及其应用 包括科学计算 几何
3;
型协议 首次针对抗抵赖环境 利用离散对数和双线
、 ．
计算 统计分析等问题 集合问题的保密计算也是安全
4．
性对设计了可公开保密计算的协议
．
多方计算中一个很重要的组成部分 针对此
，Freedman
2
预备知识
［12］
、
等人 研 究 了 集 合 相 交 交 集 的 势 等 问 题
． Kissner
［13］
2． 1
、 ．
等人研究了集合相交 包含等问题 而集合成员关系
问题的描述及集合的多项式表示
( 1)
集合成员关系的安全多方计算
，
的安全计算是集合问题中的一个分支 它要求保密地
Alice
a，Bob X = ( x ，x ，…，
拥有集合
2
．
判断一方所拥有的元素是否在另一方的集合中 比如
拥有元素
Bob
1
x ) ． Alice
n
a X
都想知道元素 是否为集合 中的成
:
和
以下的场景
， X ，
员 除了集合 的势 而不泄露
a
X
．
中的任何信息
， ，
由于目前航空事件频发 为了乘客的安全 航空安
与
( 2)
检部门需要检查准备登机的乘客中是否有人出现在安
集合的多项式表示
“ ” ．
全局所持有的 黑名单 里 一方面航空公司的安检部
X = ( x ，x ，…，x )
，
为一个集合 则此集合可表示为
n
1
2
; ，
门有责任对正常乘客的个人信息进行保密 但是 另一
n
一个 次的多项式
“ ” ，
方面安全局的 黑名单 属于机密文件 不能轻易泄密
．
f( x) = ( x － x ) ( x － x ) …( x － x )
n
1
2
n
因此这两个部门如何在不泄露各自隐私的前提下检查
n
i
= a + a x + … + a x =
0
a x
∑
i
1
n
“ ”
是否有乘客出现在 黑名单 中呢
?
i = 0
1
a X f( a) = 0．
若 ∈
定理
，
以上场景属于保密数据查询问题 转化成数学模
，
从这个定理可以看出 要判断一个元素是否属于
，
型就是典型的集合成员关系的安全计算问题 但是目
，
一个集合 只要判断这个元素是否是这个集合转化的
．
前这方面的研究文献并不多 由于现实中很多问题都
．
多项式的根即可
2． 2
．
可以归结为此问题 因此研究其理论意义对现实问题
安全多方计算的安全性定义
．
有着重要的应用价值
1． 1
相关工作
( 1)
半诚实参与者
安全多方计算的协议运行环境分为半诚实参与者
，
针对集合成员关系安全计算问题 以往的学者们
［9，10］
，
模型和恶意攻击者模型
半诚实参与者指协议方将
． ［14］ ，
提出了一些解决方案 文献 利用可交换加密 将集
， ，
诚实地执行协议 不会篡改输入和输出信息 但可能会
．
合成员关系安全计算问题转化成元素比较匹配问题
，
保留计算的中间结果 试图推导出协议之外的信息或
，
但是若集合很大的话 这个方案需要多次可交换加密
．
者他人的信息
，
和多次逐一查找和匹配 效率较低
． 2010
，
年 马敏耀等
［15］
( 2)
半诚实模型下的安全性定义
，
先将集合中元素编码 再利用
Goldwasser-Micali
人
的
［9，10］
Goldreich
利用比特承诺和零知识证明理论设
．
异或同态加密算法解决了此问题 由于此方法同样用
，
计了一个编译器 这个编译器可以将在半诚实参与者
，
到了公钥加密算法 并且只能进行自然数组成集合的
f
条件下保密计算函数 的协议 π 自动生成在恶意参与
，
成员判定问题 具有很大局限性
． 2013
，
年 豆永丽等
［16］
f '． '
者条件下也能保密计算 的协议 π 新的协议 π 可以
人
利用混沌加密算法也将原问题转化成多次比较匹
，
迫使恶意参与者以半诚实方式参与协议的执行 否则
， ［14］ ．
配问题 因此存在和文献 方案中同样的问题
． ，
就会被发现 因此大多数情况下 我们只设计半诚实模
由于以上的方案大多是把原问题转化成匹配查找
．
型下的协议 当我们设计出所需要的半诚实模型下的
， ， ．
问题 利用加解密算法 进行逐一比对 当集合的规模较
［9，10］
，
大时 方案并不高效
．
，
安全多方协议时 只要按照
Goldreich
的通用转化方
．
法就可以将原协议转化为恶意模型下的新协议 基于
1． 2
本文贡献
( 1)
，
这一结论 本文也只给出半诚实模型下的协议和相应
将集合成员关系问题转化成一次性多项式求
．
， ，
值问题 避免了前人方案中的多次匹配查找 从而提高
的安全性模拟范例
f( x，y)
， f
为概率多项式函数 π 是计算 的协议
，
．
设
了效率
全部评论(0)