盲百万富翁问题的高效解决方案

安全多方计算是密码学研究的一个重要领域,也是国际密码学研究的热点之一.百万富翁问题是第一个安全多方计算问题,它研究的是Alice和Bob各拥有一个私有数据x、y,保密比较x、y大小的问题.研究人员提出了许多解决方案,并在其基础上拓展出了许多新的问题.本文对百万富翁问题进行了新的拓展,提出这样的问题:Alice、Bob、Carol和Dove各拥有保密数据x、y、u、v,他们要保密判定x+y和u+v的大小关系,但是都不愿意泄露自己的保密数据.在此情况下,没有人知道x+y、u+v的具体数值.我们称这个问题为盲百万富翁问题,其具有重要的理论与实际意义.为解决此问题,我们利用概率加密算法的性质和移位寄存器的思想设计了新的保密移位添加方法.然后在半诚实模型下设计了参与者为三方、四方和n方的三个不同盲百万富翁问题的解决方案,并应用模拟范例证明了方案的安全性,可以抵抗任意的合谋攻击.最后,对协议进行了效率分析和实验测试,理论分析和实验结果都表明本文的协议是高效的、实用的.保密移位添加方法不仅可用于解决本文的盲百万富翁问题,还可以作为基础模块去解决其它安全多方计算问题.盲百万富翁问题也为安全多方计算提供了新的研究思路.

姚氏百万富翁问题的高效解决方案

姚氏百万富翁问题解决方案已经成为许多多方保密计算问题解决方案的一个基本模块,但现有的解决方案效率低下,因而影响到其他多方保密计算方案的效率.本文利用长度函数与不经意传输设计了一个高效的解决方案,新方案同原有方案相比,计算复杂性明显降低.

姚氏百万富翁问题的高效解决方案

姚氏百万富翁问题是安全多方计算的典型问题,但已有解决方案多数存在效率低的问题。通过采用0编码与1编码,将百万富翁问题转换为集合交集问题,提出一种基于可交换加密函数的百万富翁问题高效解决方案,并进行了安全性证明。该方案无需复杂的模指数运算,加解密运算为O(n),通信轮数为4,整体性能优于其他方案。

基于1-r编码的高效百万富翁问题协议及应用

安全多方计算是近年来国际密码学的研究热点,已经成为密码学的一个重要研究方向.本文研究的百万富翁问题是安全多方计算最基本、最重要的问题,其本质就是保密比较两数据的大小问题.然而,目前已有的方案效率低下,影响实际应用,而且,大多数方案不能区分两数是否相等这种情况.针对这些问题,本文首先给出一种新的1-r编码方法,应用这种方法和给定的全序集合对保密数据进行编码,构造一个向量,使得保密数据与所编码的向量是一一对应的.基于此,本文把百万富翁问题转化为计算此向量中两个元素的乘积问题,通过乘积结果区分两个保密数据的大小,进而解决了原问题.此外,因为要保护双方的隐私,所以本文利用同态加密算法,设计了一个解决百万富翁问题的高效协议,并在半诚实模型下利用模拟范例的方法证明了协议的安全性.分析表明,相比已有的方案,本文的新方案不仅简单、高效,还能够更加细粒度地进行比较.最后,以新方案为基础,构造了一个具有验证机制的百万富翁协议,并应用协议1设计一个高效的保密查询数据在有序集合中排序的协议.

一种高效的百万富翁问题协议及其应用

百万富翁问题是安全多方计算的基础问题,但现有解决方案计算复杂度高且效率较低,在两数相等时无法进行精确比较。针对该问题,提出一种基于0-1编码的百万富翁问题协议。使用改进的0-1保密数据编码规则构建向量,利用ElGamal同态加密变体算法的同态性质,将百万富翁问题转化为向量中两元素求和的问题,同时在半诚实模型下利用模拟范例证明协议的正确性与安全性,并将其应用于安全两方集合交集个数问题的求解。实验结果表明,与采用ElGamal和Paillier同态加密算法的协议相比,该协议计算复杂度更低且效率更高,可在两数相等时进行准确对比。

同态加密的百万富翁问题高效解决方案

安全多方计算问题由图灵奖得主姚期智于上世纪八十年代首先提出,现在已经成为密码学的一个重要研究方向.百万富翁问题是多方安全计算研究的热点问题之一,也是其他安全多方计算协议的基本构成模块,但现有的解决方案效率低下,因而会影响其他安全多方协议的效率.基于同态加密算法,通过对保密的数据进行0-1编码,设计了一个计算百万富翁问题的协议,并利用模拟范例对协议进行安全性证明.通过效率分析显示我们的方案是简单、高效的.最后利用这个新的协议作为基本模块,设计了一个保密数据查询问题的协议,并给出了应用实例.

抗恶意敌手的百万富翁问题解决方案

安全多方计算是国际密码学界研究的热点,百万富翁问题是安全多方计算最基础最重要的问题,是构造其他安全多方计算协议的基本模块.这个问题已经有许多解决方案,但除了基于混淆电路的协议之外,目前基于公钥加密算法的解决方案几乎都是半诚实模型下的解决方案,抗恶意敌手的解决方案极少,仅有的个别解决方案效率很低,这制约着恶意模型下许多安全多方计算问题的解决.抗恶意敌手的解决方案更符合安全多方计算的实际应用场景,研究抗恶意敌手的百万富翁问题解决方案,具有重要的理论与现实意义.本文首先设计了一个半诚实模型下百万富翁问题的解决方案,进一步分析了恶意敌手可能的恶意行为,并用零知识证明和分割选择阻止或发现这些恶意行为,将半诚实模型下安全的计算协议改造成恶意模型下安全的计算协议,并用理想–实际范例证明了协议的安全性,分析了恶意敌手攻击成功的概率和方案的效率.理论分析表明与现有方案相比,我们提出的方案效率至少提高6倍.

基于博弈论的百万富翁协议

在经典的百万富翁协议中,一方在得到最后的财富比较结果后,没有动机将结果告诉另一方,或者告诉另一方一个错误的结果。结合博弈论和密码算法,提出一种百万富翁协议。在此协议中,参与者背离协议的收益小于遵守协议的收益,遵守协议是参与者的最优策略,任何百万富翁的欺骗行为都能被鉴别和发现,因此理性的参与者有动机发送正确的数据。最后每个参与者都能公平地得到最后的财富比较结果。

乘法同态加密的百万富翁协议的改进

百万富翁问题的解决方案已经成为许多安全多方计算问题解决方案的一个基本模块,给出了一个基于乘法同态加密的百万富翁改进协议,该协议在比较出"≤"的关系上,增加了比较"="的关系,同时还给出协议的正确性、安全性和效率的分析。

半诚实模型下安全多方排序问题的研究

安全多方排序问题是百万富翁问题的推广问题,用于n个参与方在不泄漏各方秘密输入的前提下比较出其输入在全体输入中按照一定顺序所处的位置.本文首先提出了半诚实模型下基于同态加密的安全两方排序协议.然后将该协议推广到多方排序的情况,并提出两种提高效率的改进算法.最后本文还提出了基于模糊贴近度的安全多方排序协议,并对这几个协议的安全性和效率做了分析、比较.

有关保护私有信息的三角不等式判定问题研究

安全多方计算是信息安全领域研究的热点问题之一,保护私有信息的三角不等式判定问题是一类基于三方的特殊安全多方计算问题。文章设计了一个基于Paillier加密算法的百万富翁比较协议,并扩展该协议至三方参与者,形成一个基于Paillier加密算法的三角不等式判定协议;结合点积协议与百万富翁协议,设计了一个保护私有信息的三角不等式判定协议,在保护用户私有输入信息的条件下,解决了三角不等式的判定问题。

基于同态加密的高效多方保密计算

多方保密计算是信息社会隐私保护的核心技术,是国际密码学界的研究热点之一.本文首先提出了一种新的对保密数据进行编码的方案,接着利用这种新的编码方案和同态加密方案,构造了一个百万富翁问题新的解决方案,并证明了方案的安全性.新的方案更简洁、更具有普遍意义,能够对可定义全序关系的任意两个对象进行比较.最后用这个新的解决方案解决了另一个新的多方保密计算问题-两个整数的互素问题,证明了方案是安全的.

安全向量优势协议及其应用

百万富翁问题是安全多方计算研究的热点问题之一,也是其他安全多方计算协议的基本构成模块.安全向量优势统计问题是百万富翁问题的推广,用于两方在不泄漏自己保密向量信息的前提下统计出满足大于关系的分量的数目.本文基于同态加密算法,通过对保密的数据进行编码,设计了一个计算百万富翁问题的协议,并利用模拟范例对协议进行安全性证明.然后利用这个新的协议作为基本模块,设计了一个向量优势统计协议,通过效率分析显示我们的方案是简单、高效的.最后将向量优势统计协议应用到整除判定问题和点与若干直线关系判定问题.

基于字符串排序的高效保密数据库查询

安全多方计算是近年来国际密码学界研究的热点问题之一,是信息社会隐私保护的核心技术.保密地将字符串按照字典序排序问题是一个全新的安全多方计算问题,在信息安全领域有重要的实际意义和广泛的应用前景.它不仅可以提高保密数据库查询的效率,还可以解决大数据情况下的百万富翁问题.为了保密地判断两个字符串按照字典序排序的位置关系,首先设计了一种新的编码方法和一种基于ElGamal加密算法的云外包计算下的同态加密方案,在此基础上提出了一个高效、简单的协议,并对协议进行了正确性和安全性分析,同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.最后将保密的字符串排序问题协议应用于解决百万富翁问题,从根本上解决了大数据情况下的百万富翁问题.

理性的安全两方计算协议

在传统的安全两方计算协议中,一方在得到计算结果后,可能会告诉另一方一个错误的结果,或者立即中断协议,这样不能保证协议的完全公平性.针对此问题,结合博弈论和密码学理论,提出一种理性的安全两方计算协议.首先假设理性的参与者最大的利益是得到计算结果,其次是越少的其他人得到结果越好.然后,研究了参与者遵守和背离协议的策略、效用和动机,构建了安全两方计算的博弈模型.在所设计的协议中,参与者遵守协议是参与者的最优策略,任何参与者的欺骗行为都能被检验,参与者背离协议,没有遵守协议的收益大,这样参与者有动机发送真实的数据,最终,每个参与者都能得到计算结果.分析表明,协议是安全和公平的.

一种改进的两方安全议价协议

提出了一种基于Paillier同态公钥密码体制的两方安全议价协议。该协议在保障出价信息的私密性和结果正确的前提下,协议参与双方可以完成对商品交易价格的协商,仅在价格协商成功的情况下由第三方参与计算出最终的成交价格。通过对复杂度和安全性的分析可知,该协议具有较高的执行效率和安全特性,在电子商务应用中具有一定的实用价值。

基于加同态公钥密码体制的两方安全议价协议

安全多方计算及其应用是目前密码学领域的一个重要研究方向。在不需要第三方参与且保证安全的前提下,如何完成多方的协作运算是其研究的核心。基于加同态公钥加密算法的议价协议,是安全多方计算应用的一个具体实现,通过协议的执行,参与方可以进行商品价格的协商,并保障输入的私密性和结果的正确性。协议的执行过程中不需要第三方的参与,协议的安全性基于所采用的同态公钥加密算法。

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

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

基于滑动窗口和交换加密函数解决SMP的新方案

社会主义百万富翁问题(SMP)的解决方案可以作为许多应用系统的基本模块。该文提出了滑动窗口的模型,利用此滑动窗口模型和交换加密函数设计了一种社会主义百万富翁问题新的解决方案,并应用模拟器的思想对该方案安全性进行证明。

半诚实模型下公平高效的安全两方比较协议

姚氏百万富翁问题的实质是在秘密状态下比较两个数的大小,它是其他保密计算的一个基本模块,并在电子商务如投标、拍卖等应用中具有重要作用。当前的解决方案存在计算和通信开销较高、比较的数的范围有限等缺点。基于修改的ElGamal算法提出并证明了乘法和减法同态加密系统。基于此设计了半诚实模型下公平高效的安全两方比较协议。通过证明、实例和与其他协议比较表明其具有安全性、公平性、低的计算和通信开销和可秘密比较两个实数等特性。