推荐星级：
- 1
- 2
- 3
- 4
- 5
最小值问题的安全多方计算及其应用
资料介绍
安全多方计算是国际密码学界近年来的研究热点.本文主要研究科学计算中最小值问题的安全多方计算,目前尚没有见到关于这个问题的解决方案.本文设计了一种新的编码方法,应用该编码方法和El Gamal乘法同态加密算法,并结合秘密分享以及门限密码体制,在半诚实模型下设计了三个能够抵抗合谋攻击的最小值安全多方计算方案,并应用模拟范例证明了方案的安全性.以最小值解决方案为基础还可以解决最大值安全计算以及并集的安全计算等科学计算问题.效率分析表明所设计的安全计算方案是高效的方案.
部分文件列表
| 文件名 | 大小 |
| 最小值问题的安全多方计算及其应用.pdf | 1M |
部分页面预览
（完整内容请下载后查看）7
Vol． 45 No． 7
Jul． 2017
第
期
电
子
学
报
2017
7
ACTA ELECTRONICA SINICA
年
月
最小值问题的安全多方计算及其应用
1
1
2
， ，
窦家维 马 丽 李顺东
( 1．
，
陕西师范大学数学与信息科学学院 陕西西安
710062; 2．
，
陕西师范大学计算机科学学院 陕西西安
710062)
:
．
安全多方计算是国际密码学界近年来的研究热点 本文主要研究科学计算中最小值问题的安全多方计
摘
要
， ． ，
算 目前尚没有见到关于这个问题的解决方案 本文设计了一种新的编码方法 应用该编码方法和
ElGamal
乘法同态
， ，
加密算法 并结合秘密分享以及门限密码体制 在半诚实模型下设计了三个能够抵抗合谋攻击的最小值安全多方计算
， ．
方案 并应用模拟范例证明了方案的安全性 以最小值解决方案为基础还可以解决最大值安全计算以及并集的安全计
．
算等科学计算问题 效率分析表明所设计的安全计算方案是高效的方案
．
:
;
;
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
密码学 安全多方计算 最小值 同态加密 秘密分享 门限密码体制
TP309. 7 0372-2112 ( 2017) 07-1715-07
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 07． 023
:
:
A
:
文章编号
文献标识码
电子学报
Secure Multi-Party Computation for Minimum and Its Applications
1
1
2
DOU Jia-wei ，MA Li ，LI Shun-dong
( 1． School of Mathematics and Information Science，Shaanxi Normal University，Xi’an，Shaanxi 710062，China;
2． School of Computer Science，Shaanxi Normal University，Xi’an，Shaanxi 710062，China)
Abstract: Secure multi-party computation is a focus in the international cryptographic community． This paper studies
how to privately compute the minimum of some private numbers． We have not read about any a solution to this problem． In
this study，we introduce a new encoding scheme，and then，based on this new encoding scheme and ElGamal multiplicatively
homomorphic encryption scheme，using secret sharing and threshold decryption，devise protocols for this problem． By using
the simulation paradigm，we prove that these protocols are secure in the semi-honest model． These protocols can resist colli-
sion attack． Based on the computing methods for minimum problem，secure multi-party computation for maximum and union
of sets can also be solved． Efficiency analysis shows that these schemes are efficient．
Key words: cryptography; secure multi-party computation; minimum; homomorphic encryption; secret sharing; thresh-
old decryption
，
结束后 没有参与方能够获得多于规定输出的信息
．
1
引言
［1］
［2，3］
Yao
Goldreich
等人
和
首先提出了安全多方计算问
网络的迅速发展为多个参与者利用各自的保密数
，
题并对其进行了深入的研究 从理论上证明了任意的
、 、
据联合进行数据挖掘 知识发现 信息搜索以及寻求数
，
安全多方计算问题都是可解的 并给出了通用的解决
、
据之间的各种统计规律 合作进行科学研究等提供了
．
方案
，
巨大的机会 同时也给参与者的信息安全带来了巨大
利用通用的解决方案解决具体的计算问题是不实
． ，
的挑战 在互不信任的网络环境中 参与者需要保护各
， ，
际的 从效率方面考虑 对具体问题应该研究具体的解
．
自所拥有数据的隐私性 在联合计算过程中稍有不慎
． ， ，
决方案 近年来 人们研究了各类安全多方计算问题 如
［1，4 ～ 9］
［10 ～ 12］
，
就可能导致数据的机密性丧失 这使得安全多方计算
，
，
保密的科学计算
保密的计算几何
保密的
，
安全多方计算应
［13］
［14，15］
．
越来越受到人们的关注
安全多方计算是指两个或更多参与者利用各自的
，
统计分析
保密的数据挖掘
［16 ～ 18］
． ，
等 在保密的科学计算方面 人们研究了比较两
用
［1，8，9］
［4，5］
，
，
保密计算集合
( ) ， ．
保密数据 作为计算的输入 联合进行保密计算 计算
个数的大小
保密的信息比较
: 2015-08-28;
: 2016-09-20; :
责任编辑 孙瑶
收稿日期
修回日期
:
基金项目 国家自然科学基金
( No. 61272435)
1716
2017
年
电
子
学
报
［6］
［7］
，
，
…，x ) ．
m
，P
在协议执行过程中 得到的信息序列记为
i
的交集
保密计算多重集的并集
保密的多项式计
［19］
1
t
Π
． ( )
等 保密计算多个数据的最小 大 值是保密的科
算
view ( X) = ( x ，r ，M ，…，M ) ，
i
i
i
i
i
j
， ，
学计算中一个非常重要的问题 就我们所知 目前还没
M ( j = 1，…，t)
i
P j ．
收到的第 个信息 对于部
i
其中
分参与 者 构 成 的 子 集
P } ，
表示
．
有见到关于这个问题的解决方案
I = { P ，…，P }
is
{ P ，…，
1
i1
、 、
安全多方计算一般采用加密电路 不经意传输 秘
记
m
Π
Π
Π
、
密分享 同态加密等技术作为基本模块设计针对具体
view ( X) = ( I，view ( X) ，…，view ( X) ) ．
I
i1
is
［3］
． ［20］
问题的解决方案 文献 全面地总结了实现安全多
1(
定义 半诚实参与者协议的安全性
)
在参与
． ，
方计算的各种技术 本文通过巧妙设计编码方法 并结
，
者都是半诚实的情况下 如果存在概率多项式时间算
，
合这些基本技术 将最大最小值保密计算以及集合并
集问题归约到相应数组的保密乘积而得到高效的解决
S，
使得对于任意的
I = { P ，…，P } { P ，…，P } ，
1
法
i1
is
m
( 1)
:
均有式
成立
．
方案 本文的贡献如下
:
*
m
{ S( I，( x ，…，x ) ，f ( X) ) }
i1
is
I
X
( { 0，1}
)
∈
( 1)
( 1)
，
提出了一种新的编码方法 使每个参与者的保
c
Π
*
( { 0，1} )
∈
m
{ view ( X) }
I
≡
X
．
密数据隐藏在一个特殊数组中 这种编码方法可以为
c
， ，
其中 ≡表示计算上不可区分 则称协议 Π 保密地计算
．
解决其他安全多方计算问题提供一种新的途径
( 2) 、ElGamal
f．
了函数
本文的解决方案是对于半诚实参与者安全的方案
利用所设计的新编码方法
同态加密
．
、
算法 秘密分享和门限密码体制的方法设计了三个保
2. 3
．
密计算最小值问题的解决方案 这些方案对半诚实参
同态加密算法
．
．
， ，
与者是安全的 可以抵抗合谋攻击的程度不同 其中第
同态性是某些公钥加密方案所具有的重要性质
ElGamal
．
加密算法是一种具有乘法同态性的加密算法
三个方案可以抵抗任意数量的合谋攻击
( 3) ，
以保密计算最小值方案为基础 可以进一步解
:
具体如下
KeyGen．
k， k
给定安全参数 产生一个位数为 的大
，
决最大值和多个集合并集问题的保密计算 设计获得
*
*
p
素数 以及
Z
g， x Z ，
的一个生成元 随机选取私钥 ∈
p
．
高效安全的解决方案
p
x
h = g mod p．
计算其对应的公钥
Encrypt．
2
预备知识
*
M( M Z ) ，
∈ 选择一个随机
p
为加密消息
2. 1
理想模型
r，
密文为
:
数
r
r
( Trusted Third Party，
假设有 一 个 可 信 的 第 三 者
E( M) = ( c ，c ) = ( g mod p，Mh mod p) ．
2
1
TTP) ， ．
他在任何情况下都不会泄露不该泄露的信息 参
Decrypt．
E ( M) = ( c ，c ) ，
解 密 得 到
2
对于 密 文
1
P ，…，P
1
x ，…，x
告诉
1
与者
分别将各自的秘密消息
:
明文
m
m
－ x
TTP，TTP
f:
自己单独计算函数
M = c ·c mod p．
1
2
f( x ，…，x ) = ( f ( x ，…，x ) ，…，f ( x ，…，x ) ) ，
m
Evaluate．
1
m
1
1
m
1
m
P
参与者 除了从协议得到
i
TTP
发送给自己的计算
E( M ) × E( M ) mod p
2
1
r1 r1 r2 r2
( g ，M h ) × ( g ，M h ) mod p
2
f ( x ，…，x )
m
．
外得不到任何其他信息 上面借助于
结果
≡
≡
≡
i
1
1
r1 + r2 r1 + r2
( g ，( M × M ) h ) mod p
2
TTP
f( x ，…，x )
的协议称为理想的安全
m
保密计算函数
1
1
( ) ． 、
多方计算协议 简称理想协议 理想协议是最简单 安
E( M × M ) mod p．
2
1
，
f( x ，…，x )
的实
全性最高的保密计算协议 任何计算
际保密计算协议的安全性都不可能超过理想协议 实
际保密计算协议可以通过和理想协议进行比较来了解
ElGamal
加密算法是一种具有乘法同态性的
1
m
所以
，
．
加密算法
3
ElGamal
算法的最小值保密计算
基于
．
其安全性
2. 2
3. 1
协议的基本原理
P ，…，P x ，…，x ，
分别拥有数据 假设
m
半诚实模型
本文假设所有的参与者都是半诚实的参与者
所谓半诚实参与者是指那些在协议的执行过程中按照
［3］
1
．
参与者
1
1
m
x
≤ ≤
i
n( i = 1，…，m) ．
y = min{ x ，
他们要保密地计算
1
…，x } ．
m
，
协议要求忠实地履行协议的参与者 但他们可能会记
P ( i = 1，…，m)
首先按照下面的方法构造
i
，
录下协议执行中收集到的信息 在协议执行后试图根
参与者
:
数组
．
据记录的信息推算出其他参与者的输入
X = ( x ，…，x )
in
( 2)
P ，…，P ，
分别具有保密数据
1
x ，…，x ，
1
设参与者
i
i1
m
m
*
f( x ，…，x ) ．
m
X = ( x ，
1
， j ＜ x
其中 当
，x = 1;
ij
j
当 ≥
x
，x = r ，
ij
r
Z
∈
他们利用协议 Π 保密地计算
令
时
时
而
1
i
i
ij
ij
p
全部评论(0)