积分商城

最新搜索： LPC824 ad库文件 半桥 PID控制LABVIEW ICNM8001 Allegro
您现在的位置是：首页 > 技术资料 > 有理区间的安全多方计算与应用
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

有理区间的安全多方计算与应用

更新时间：2019-12-24 19:56:44 大小：724K 上传用户：守着阳光1985查看TA发布的资源 标签：安全多方计算 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

本文研究了有理数与有理区间的位置关系以及两个有理区间位置关系的安全多方计算.它们已广泛应用于数据库匹配、定位搜索等领域,是保密科学计算的一个重要分支.但目前已有文献在解决有理数与有理区间的位置关系时提出的协议效率较低,且两个有理区间位置关系问题的研究较为有限.针对这些问题,本文首先用多项式表示区间,将有理数与有理区间位置关系问题转化为整数向量的内积符号判定问题,设计了新的有理数与有理区间的保密计算协议.其次,以有理数与有理区间协议作为基础模块,设计了两个有理区间位置关系的保密计算协议.最后,理论分析及实验结果均表明本文方案是安全高效的,并给出了本文协议在有理数域上的百万富翁问题及计算几何问题的应用.


部分文件列表

文件名 大小
有理区间的安全多方计算与应用.pdf 724K

部分页面预览

（完整内容请下载后查看）
9
Vol． 46 No． 9  
Sep． 2018  
第
期
电
子
学
报
2018  
9
ACTA ELECTRONICA SINICA  
年
月
有理区间的安全多方计算与应用  
1
1
1
2
，
，
，
窦家维 王文丽 刘旭红 李顺东  
( 1.  
，
710119; 2．  
，
710119)  
陕西师范大学数学与信息科学学院 陕西西安  
陕西师范大学计算机科学学院 陕西西安  
:
．
本文研究了有理数与有理区间的位置关系以及两个有理区间位置关系的安全多方计算 它们已广泛应  
摘
要
、
，
．
用于数据库匹配 定位搜索等领域 是保密科学计算的一个重要分支 但目前已有文献在解决有理数与有理区间的位  
，
．
，
置关系时提出的协议效率较低 且两个有理区间位置关系问题的研究较为有限 针对这些问题 本文首先用多项式表  
，
，
示区间 将有理数与有理区间位置关系问题转化为整数向量的内积符号判定问题 设计了新的有理数与有理区间的保  
．
，
，
．
密计算协议 其次 以有理数与有理区间协议作为基础模块 设计了两个有理区间位置关系的保密计算协议 最后 理  
，
，
论分析及实验结果均表明本文方案是安全高效的 并给出了本文协议在有理数域上的百万富翁问题及计算几何问题  
．
的应用  
:
;
;
;
;
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
密码学 安全多方计算 有理数 有理区间 数据库匹配 定位搜索 百万富翁问题 计算几何  
TP309  
0372-2112 ( 2018) 09-2057-06  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 09． 002  
:
:
A
:
文章编号  
文献标识码  
电子学报  
Secure Multiparty Computation of Rational Interval and Its Applications  
1
1
1
2
DOU Jia-wei ，WANG Wen-li ，LIU Xu-hong ，LI Shun-dong  
( 1. School of Mathematics and Information Science，Shaanxi Normal University，Xi'an，Shaanxi 710119，China;  
2. School of Computer Science，Shaanxi Normal University，Xi'an，Shaanxi 710119，China)  
Abstract: The SMC ( Secure Multiparty Computation) of the location relation between rational numbers and inter-  
vals，and that between two rational intervals has been investigated． As an important branch of the confidential scientific com-  
puting，this problem was widely applied in database matching，positioning search，etc． However，there still exist many prob-  
lems，for example，current solutions to the location relation between rational numbers are low efficiency and the research on  
the location relation between two rational intervals is limited． In order to address the above gaps，firstly，we use polynomials  
to represent the interval，and convert the problem into determining the scalar product signs of two integer vectors． Thus，the  
new protocol of the problem between rational number and interval is worked out． Secondly，with the proposed scheme as the  
basic module，we construct the protocol of the location relation between two rational intervals． Finally，the theoretical analysis  
and experimental results prove that our protocols are safe and efficient，and we give the application of millionaire problem  
and computational geometry problem in rational domain．  
Key words: cryptography; secure multiparty computation; rational number; rational interval; database matching; posi-  
tioning search; millionaire problem; computation geometry  
，
方计算的一个重要研究领域 主要涉及 保 密信 息比  
1
引言  
［5］  
［6］  
［7］  
较［1，4］ 向量保密计算  
保密排序  
等 为研究更复杂的问题提供基础模块  
有理区间的安全多方计算属于保密的科学计算  
: ( 1) ． ( 2)  
，
，
，
集合计算问题  
，
安全多方计算是指在互不信任的网络空间中 参  
，
．
．
与者在不泄露私有数据的情况下合作完成某项计算  
［1］  
该问题首先是  
，
［2，3］  
Yao  
，Goldreich，Cramer  
等人  
提出的  
包括  
有理数与有理区间位置关系的保密计算  
，
对其进行了深入研究 广泛的应用前景使其成为国际  
．
两个有理区间位置关系的保密计算 有理区间的保密  
．
密码学界的一个研究热点 保密的科学计算是安全多  
［8］  
Nishid  
．
计算问题首先由  
等人 提出 郭等人［9］ 基于计  
: 2017-09-20;  
: 2018-02-08; :  
责任编辑 覃怀银  
收稿日期  
修回日期  
:
( No． 61272435)  
基金项目 国家自然科学基金  
2058  
2018  
电
子
学
报
年
1) /N．  
( g，N) ， ，  
私钥为 λ 加密及解密算法分别记  
算几何理论将所输入的有理数或区间端点作为坐标系  
公钥为  
，
中过原点的直线斜率 将区间保密计算问题转化为直  
E
D．  
为
和
线之间的位置关系判定问题提出了有理数与有理区间  
m( m ＜ N) ， r ＜ N，  
选择随机数 密  
加密 加密明文  
．
保密计算的解决方案 以上文献虽然均给出了有理数  
:
文为  
m
N
2
，
，
与有理区间的解决方案 但协议的执行效率并不理想  
c = E( m) = g r mod N .  
2
．
且对于两个有理区间位置关系问题并未提及  
c ＜ N ，  
解密得到明文为  
:
解密 对于密文  
2
λ
，
本文研究的目的 是不但应用新方法解决有理数  
L( c mod N )  
L( g mod N )  
m = D( c) =  
mod N．  
2
λ
，
．
和有理区间的位置关系问题 提高协议的效率 其次要  
，
Paillier  
:
加密算法具有加法同态性  
进一步提出两个有理区间位置关系的保密判定协议  
同态性质  
m1  
N
m2  
N
2
，
E( m ) × E( m ) = ( g r ) ( g r ) mod N  
填补该问题的空白 推进有理区间安全多方计算问题  
1
2
1
2
m1 + m2  
N
2
．
的发展  
= g  
( r r ) mod N = E( m + m ) ．  
1
2
1
2
1
Paillier  
N = p × q， p，q  
其中  
注解  
在
加密算法中  
2
预备知识  
，
m
为大素数 假设整数 满足 记  
| m| ［0，N/2) ， R = D( E  
∈
计算模型及安全性定义［3］  
2. 1  
( m) ) ．  
N/2) ;  
， R ( 0，N/2) ，  
由群论的知识可知 若  
m
∈
( 0，  
∈
则
，
半诚实模型 简单地说 半诚实参与者将会严格  
R
( N/2，N) R = 0，  
m
( － N/2，0］．  
因
若
∈
或
则
∈
，
执行协议 但他们可能会保留计算的中间结果试图推  
R m  
此可由解密结果 的所属范围来判定数据 的正负  
．
． ，  
导出其他参与者的输入 如果参与者是半诚实的 称这  
N = p × q， p，q  
而
，N/2 ，  
不能是整数 因  
由于  
和
为素数  
．
样的模型为半诚实模型 本文假设所有的参与者均为  
R
| m|  
N/2．  
此
不可能取值  
．
半诚实参与者  
3
有理数与有理区间的位置关系保密计算  
协议  
Alice  
x，Bob  
拥有  
y，  
拥有 他们要  
一些记号 假设  
x，y  
，
隐私性的前提下 合作计算函数  
f( x，y) =  
在保证  
( f ( x，y) ，f ( x，y) ) ．  
Alice  
合作计算的目的是  
f ( x，y) f ( x，y) ．  
Bob  
和
分
x
对于有理数 可表示为  
x = x /x  
1
，
的形式 规定  
x
1
2
2
2
f
别得到函数 的两个分量  
和
设 π 表示  
，Alice  
在执行协议 π 的过程中所得到的  
1
2
，x ， gcd( x ，x ) = 1.  
x
y
为正整数  
为整数 且  
若
和
均为  
1
1
2
f
计算 的协议  
，
［x，y］  
．
有理数 则称区间 为有理区间  
信息序列记为  
π
3. 1  
问题描述及计算原理  
1
t
view ( x，y) = ( x，r ，m ，…，m ，f ( x，y) ) ，  
1
1
1
1
1
Alice  
a = a /a ，Bob  
有
问题描述 假设  
有有理数  
1
2
i
r
其中 表示  
1
Alice  
; m ( i = 1，  
独立的硬币抛掷结果  
1
I =［c，d］=［c /c ，d /d ］，  
有理区间  
他们希望保密判  
1
2
1
2
…，t)  
Alice  
i ．  
收到的第 个信息 执行协议 π 后  
，Al-  
表示  
a ［c，d］ ，  
断有理数 与区间 的位置关系 而不泄露其他  
ice  
f ( x，y) ． Bob  
得到的信息序列可类  
得到的输出记作  
1
．
信息  
．
似定义  
a
计算原理 对于有理数 及有理区间  
［c，d］，a  
∈
f
半诚实模型下协议的安全性 对于计算函数 的协  
［c，d］ ( a － c) ( a － d) 0.  
［c，d］  
因此如果将区间 用  
≤
，
议 π 如果存在概率多项式时间算法  
c
S
S
与
使得  
1
2
g( y) = ( y － c) ( y － d)  
，
表示 通过保密判定函数  
多项式  
π
{ S ( x，f ( x，y) ) }  
{ view ( x，y) }  
( 1)  
( 2)  
g( a)  
的正负即可解决该问题 为此 计算  
2
．
，
≡
c
值
1
1
x，y  
x，y  
1
x，y  
x，y  
2
π
g( a) = A( A a + A a a + A a ) ，  
2
1
1
2
1
2
3
2
{ S ( y，f ( x，y) ) }  
{ view ( x，y) }  
c
≡
2
2
2
A = 1 /( a c d ) ，A = c d ，A = － c d － c d ，A  
其中  
2
2
2
1
2
2
2
2
1
1
2
3
f，  
则称 π 保密地计算了函数 其中≡表示计算上不可  
= c d .  
1
1
．
区分  
2
2
2
A ＞ 0，  
所以只需判断  
s = A a + A a a + A a  
1
因为  
a
1
1
2
2
3
，
要证明一个多方计算协议是安全的 就需要构造  
．
的正负 若  
s
0， a ［c，d］;  
则 ∈  
，a ［c，d］．  
否则 具体协  
≤
a
( 1) ( 2) S ，S ，  
出使式  
的方法称为模拟范例  
2. 2 Paillier  
和
成立的模拟器  
如此证明安全性  
1
2
．
议如下  
．
3. 2  
协议设计  
加密方案  
，
P( a，I) :  
a I， P( a，  
如果 ∈ 记  
为叙述方便 定义函数  
Paillier  
加密系统是一种具有加法同态性的公钥加  
I) = 1;  
， P( a，I) = 0.  
否则 记  
［10］  
，
．
密系统 并且是语义安全的 描述如下  
:
k，  
密钥生成 给定一个安全参数 选择两个素数  
p，  
1
协议  
有理数与有理区间位置关系判定协议  
q， N = p × q， = 1cm( p － 1，q － 1) ，  
g
∈
记
λ
随机选择一个  
*
2
λ
2
Z
gcd( L( g mod N ) ，N) = 1， L( x) = ( x －  
定义  
使得  
: Alice  
a，Bob  
输入有理数  
［c，d］．  
输入有理区间  
输入  
N

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号