文摘
与移动设备和无线技术的快速发展,移动社交网络日益普及。人们可以实现很多应用程序移动社交网络的基础。安全计算,如交换信息和文件共享,是一个这样的应用程序。公平安全的计算,这意味着各方实现应用程序或没有人,被视为一个不可能完成的任务在传统安全计算没有移动社交网络。我们认为移动社交网络应用程序的特定功能和强调公平的实现这些功能在移动社交网络的存在两个理性的政党。理性的政党价值公用事业当他们参与移动社交网络的安全计算协议。因此,我们的声誉来自移动社交网络引入到效用定义,这样理性的政党有激励机制来实现应用程序给予更高的效用。我们所知,协议是第一个公平安全的移动社交网络的计算。此外,它在恒轮结束,允许双方了解终端。
1。介绍
移动计算和通信领域的快速增长。移动社交网络连接使用现成的个人或组织,sensor-enabled手机通过社交网络与信息共享应用,如Facebook、MySpace和科学合作网络(1]。移动社交网络中扮演一个重要的角色,信息的传播和影响的形式“口碑”2]。无线通信的优点是,他们可以提供许多新的服务,将彻底改变社会处理信息的方式(3]。最重要的属性对于移动用户在移动社交网络在于他们的声誉在网络互动时(4- - - - - -6),可以利用来提高安全的两党合作计算。确保党计算(7]意味着两个分布式政党希望正确地计算一些功能使用他们的私人投入而披露除了为输出。计算应满足三个基本要求:(i)隐私:没有什么比输出从其他的协议,(ii)正确性:根据规定的功能,输出是分布式和(3)独立性:政党不能使他们的输入根据其他党派的输入。另一个要求是公平这意味着各方学习结果或者没有人。大量的研究人员深入研究政党之间实现公平。不幸的是,克里夫(8)表明,党公平无法实现设置。所以,公认的民间传说是什么重要的计算与公平。通常的治疗安全党计算(9)提醒一个公平的理想世界是没有保证的。
两党游戏设置的不完全信息下,两个自私的政党希望他们与私人信息的效用最大化。每一方都有一组策略和某些私人信息,如类型。双方在每一轮战略同时或交替(也许只是一箭)和最后一轮会导致一个结果分配一个实用程序。密码学和博弈论都关心理解相互不信任政党和利益冲突之间的交互。密码协议设计的初衷是为了保护个人对任意输入的每一方的行为,而博弈论协议是为了达到各种纳什均衡对理性的偏差。
1.1。相关的工作
研究显示大的增加通信通过移动电话,短信,和社交网络的空间范围10- - - - - -12]。人们经常在远处有关系,他们与这些关系通过手机社交等等。拉森et al。13)考虑如何使用移动电话来协调与朋友和家庭成员之间面对面的会议。王等人。14处理这个问题的影响最大化在移动社交网络网络中,用户通过手机进行通信。移动社交网络可以从通话记录中提取和建模为加权有向图。手机用户对应一个节点。一个节点的重量是其声誉和建立与网络中其他节点。Miluzzo et al。15]讨论的设计、实现和评价cenceme应用程序的移动社交网络的基础上。冈萨雷斯et al。16]代表移动代理的模型构建社交网络的基础上,系统的跟踪移动粒子的碰撞在他们系统中永恒。海滩等。17]讨论移动社交网络的安全和隐私问题当用户在网络上分享他们的id或处理。
另一方面,用户在移动社交网络被假定为理性方关心他们的公用事业的博弈论。王等人。18)提出社会理性的安全多方计算协议当理性方属于一个社交网络。理性的政党,由Halpern引入和爱尔兰人19),既不像诚实方始终遵循的协议也不喜欢恶意方任意违反协议。理性的政党只采用策略,最大限度地发挥其效用。Halpern,爱尔兰人19与理性方]证明不可能的结果,然后给一个随机理性多方计算的解决方案。然而,考虑到至少三个恶意的政党,他们的协议无法实现公平。
1.2。动机和贡献
理性的政党在安全计算预计将相互合作。然而,他们没有激励合作根据传统效用的定义。因此必须考虑新的效用定义分配激励理性的政党。声誉的动机来自于移动社交网络可以提高用户之间的合作,我们认为合理的安全计算在移动社交的作品,因此理性方可以利用网络的声誉。特别是,移动社交网络中用户愿意合作的人合作的良好的声誉。此外,良好的声誉可以朋友间的传播网络。例如,如果爱丽丝与鲍勃合作一次,然后鲍勃的朋友愿意配合Alice和Bob将配合爱丽丝当他们再次见面。因此,声誉是一个有用的工具来鼓励相互合作。
在本文中,我们只考虑理性双方安全地计算一个函数。双方来自移动社交网络,他们都有声誉价值和使用针锋相对(TFT)策略来促进合作。注意,声誉影响聚会的方式实现他们的工具。这种理性的理性计算协议在政党分为若干次迭代。每次迭代结束时双方获得一些实用程序和更新他们的声誉。这个过程类似于重复游戏游戏阶段。Maleka et al。20.)第一次引入重复游戏的秘密共享方案和得到积极/消极的结果在无限/有限重复游戏。他们讨论重复游戏场景的完整信息和得出结论,当事人不能重建秘密当他们知道终端迭代。在这篇文章中,我们介绍了TFT战略、声誉的假设和不完整的信息以促进双方之间的相互合作。因此,它是可能的政党在恒轮实现公平。
我们设置大约类似的克罗齐和卡茨(21)除了TFT策略(22)、声誉的假设和不完全信息情况。本文的主要贡献是TFT的引入策略和声誉的假设。(我)理性党计算的主要目标在移动社交网络是如何促进合作双方为了完成协议(如囚徒困境博弈)。在博弈论的场景中(特别是在重复游戏),TFT是一种有效的策略来促进合作。事实上,这看似简单的和很自然的策略击败其他策略在阿克塞尔罗德的囚徒困境锦标赛(23]。主要TFT战略的直觉是政党实现合作在第一轮试图引起相互合作从他们的对手和复制下一轮的对手的最后的动作。换句话说,TFT方(采用TFT策略)与方合作合作和芬克方告发。诺瓦克和西格蒙德24)设计实验基于阿克塞尔罗德的比赛来模拟社会互惠互利的作用。在rational安全党计算,各方参与使用TFT的计算策略。(2)在以前的作品,各方理性多方计算没有私有类型。即,当事人是理性是常识(两党之间的共同知识事件意味着一方知道事件,他知道对方知道事件,反之亦然(25])和各方协议在完全信息情况下运行。因此,双方执行协议根据纳什均衡。然而,可行性条件是可以有自己的私人的类型。例如,一些人,一些人恶性,还有一些人可能会报复的。每个人都知道自己的类型,只有先验概率对私人类型的其他各方。我们称之为不完全信息的场景。在这种情况下,当事人采取的策略咨询前面的操作在执行协议。前面的动作形成一个某种类型的声誉。例如,在移动社交网络经常帮助别人的人有良好的声誉,而经常欺骗别人的人有一个坏名声。在rational计算在不完全信息情况下,政党需要建立一个好名声,如果他们想要获得计算结果。另一方面,各方应出示私人通过他们的行为对他人的类型。否则,其他各方可能总是采用控制策略可能导致较低的实用工具。(3)传统效用假设理性多方计算包括两个方面:(i)正确性正确,各方希望计算功能,(2)排他性,党希望各方不获得正确的结果。后的结果(19),双方都没有激励参与协议,更不用说如何实现公平。因此,应该引入新的假设,这样方愿意参与协议。除了上述效用的假设,我们引入一个新的声誉假设当党来自移动社交网络。即政党价值网络中,形成他们的声誉。我们注意,各方的良好的声誉可以激励其他各方配合他们,提高他们的终极工具。声誉存在在许多业务相关,金融、政治和外交设置和良好的声誉是十分关注的。有时,企业、机构和个人不能涉及尴尬,声誉的损失。(iv)在这篇文章中,有两个私有类型的政党:理性方总是采用控制策略和TFT方遵循TFT的策略。每一方知道自己的私人类型和先验概率在另一方的类型。我们强调,先验概率(对应于他们的声誉)不是静态的,它是在每一轮的更新协议。
松说,我们假设有两个政党(每个人都有他的私人类型),说和,希望共同计算一个函数与他们的私人投入和,分布的常识。后(26- - - - - -28),我们的协议包括两个阶段,第一阶段被视为“预处理”阶段和第二阶段包括几个迭代。
1.3。论文大纲
部分2提出了一些预赛在我们的协议,如TFT策略,效用的假设,假设和声誉。部分3介绍了描述我们的协议ideal-real世界的范式。然后一节4证明了如何构建一个公平的协议与常数轮。本文在最后一节中,我们总结和预测一些开放的问题。
2。预赛
2.1。效用的假设
我们首先介绍的概念阶段的游戏构建块的重复的游戏和我们的协议。让表示一个阶段比赛,。在以下部分,我们表示的互补。此外,让,在那里包括战略芬克(F)和合作(C),让是实用的。让的效用与结果,让是一个指示器是否概念学习函数的输出,让表示数量的聚合方学习函数的输出。根据(19),我们做效用函数假设如下。
(一)正确性。如果,然后;也就是说,方宁愿学习函数的输出。
(b)排他性。如果和,然后;也就是说,希望对方不了解的输出函数。
为简单起见,我们定义以下结果:(我) 如果学习函数的输出,而不;(2) 如果两个和学习函数的输出;(3) 如果既不也不学习函数的输出;(iv) 如果学习函数的输出,而没有。在这里,,持有(如果,双方战略合作是Pareto-dominated的策略,双方交替芬克和合作);否则政党没有激励参与协议(这是非常像“囚徒困境”游戏的场景23])。
在重复游戏中,政党互动在几个同时或异时期和采取行动在每个阶段的比赛,在那里是一个有限数。的总效用重复的游戏
2.2。声誉的假设
理性的当事人允许公用事业,然后我们不妨认为理性党一个社交网络和赋予他们这样的额外属性的名声。声誉起着重要的作用在不完全信息下不信任政党互动场景,一个先验概率只有在其他党派的类型。不完全信息下著名的“囚徒困境”游戏占声誉如何鼓励在多级互利合作游戏。在这篇文章中,我们使用声誉效应为目的。换句话说,一个理性的派对他的声誉值,因为较高的声誉可以吸引其他各方配合他,提高他的总效用。也就是说,名声使得公用事业不同。正是出于这个原因,我们引入了另一个假设效用理性方不完全信息下高度评价他们的声誉。摘要声誉的定义是按照(29日]。(虽然有改善30.名誉上的定义),我们仍然使用原始的定义。自从声誉等于信任当只有两个政党,我们不区分这两个概念。)
定义1。让表示政党的声誉交办时期这样和,0表示协议的最初阶段。
名声不是静态的。如果没有具体指示,在下面几节中,我们表示其他各方除外。方调整他的名声的th时期根据的行动th时期(定义2)。防止当事人恶意芬克,我们组,在那里积极的证据来奖励双方合作和谁芬克是当事人反面证据来惩罚他。换句话说,名声增长缓慢时各方合作迅速滴一次政党芬克。
定义2。后th阶段比赛,声誉根据规则表更新1。
在不完全信息情况下,每一方都有一个私人的类型。在这里,我们假设当事人有两种类型:理性的当事人最大化他们的公用事业和TFT方采用TFT的策略。很明显,效用更高时他们都比当他们没有得到正确的值。派对将会倾向于与其他各方合作具有较高的声誉。双方当事人更频繁合作,他们获得更高的实用程序。因此政党激励与他人合作以维持较高的声誉。与此同时,高声誉将使对方更容易合作。这形成了一个良性循环。我们模拟的声誉价值定义2在图1,水平轴表示的总时间(50倍)表示一开始的偏离。
我们观察到的名声将减少一次政党偏离,所以政党没有动机偏离在每个阶段游戏中如果他们想保持更高的声誉。到目前为止,我们给第三个假设如果协议被认为是一个长期的过程。
(c)的声誉。每个政党都有动机保持更高的声誉为了诱导相互地合作和相互合作因此促进党的整个事业从长远来看。
事实上,假设是一个虚拟的声誉在公用事业的定义。它的主要作用是警告其他各方不要芬克。否则,该协议将因此进入相互芬克。如果是这样,各方将不会得到正确的结果,他们的事业将减少从长远来看。即,虽然名声不干预的直接工具当前迭代中,确实会影响未来的工具。在未来的工作中,我们将添加声誉的假设作为一个实部为公用事业的定义。
3所示。Ideal-Real世界范式
3.1。执行在理想世界
在理想的世界里,第三信任方(TTP)的存在,它是微不足道的实现公平。出于完整性的考虑我们代表两党(,在一个自然的方式)协议。(1)每一方知道他私人类型和另一方只有一个先验概率对私人类型的对手。(2) (分别地, )随机选择他的输入值(分别地, 根据联合概率分布)在输入对。(3)每一方发送它的价值TTP。在停止运行故障设置,被限制为一个特殊的符号吗和。(4)如果然后TTP发送双方协议结束。否则,TTP发送两党。(5)每一方输出一些价值观和协议结束。
最终协议,双方得到实用程序1(当双方遵守协议)或得到效用0(当至少一方发送TTP)。由于效用函数是常识,双方将按照协议在停止运行故障设置。我们假设全力支持,如果每一个和分布给一个独特的元素非零概率的范围。换句话说,并不存在任何元素(分别地, ),这样(分别地, )。如果一方发送一个虚构的价值TTP,双方得到效用零,这绝对是小于1,所以双方有激励机制TTP发送他们的真实值。
3.2。在现实世界中执行
更复杂的构造一个协议没有TTP完成计算。首次提出混合协议包括两个阶段过渡。第一阶段是一个理想的功能和第二阶段由几轮(部分1.3)。在每一轮中,他们相互沟通和交流一些信息。每个理性方满足效用假设(a)和(b) (c)和声誉的假设。在理想的世界中,TTP是约束双方的仲裁员的偏离。在世界混合,TFT的策略,声誉的假设和不完整的信息刺激双方遵守协议。
在第二阶段,一个政党,说是不确定是一个tft聚会。我们假设有先验概率的类型。换句话说,认为概率是一个理性的晚会吗有一个小概率和tft聚会。根据TFT策略,党必须从合作开始和对方合作在之前的阶段。一方有好/坏名声意味着党合作/芬克的名声。从效用定义,效用1当合作效用高于0时芬克。所以每个党希望在每一轮合作。相互合作双方都TFTers时很容易实现。然而,各方陷入困境时双方都是理性的。因为战略概要,理性的芬克方达到纳什均衡。不完整的信息在一定程度上可以解决这个难题。每一方的条件不确定他的对手是正确的类型,甚至理性党有激励机制建立一个良好的声誉希望在未来获得更高的实用程序。
作为的结果21),协议被认为是在混合的世界,在那里是由一个值得信赖的经销商。我们将删除这个限制。幸运的是,Canetti [31日证明一个secure-with-abort协议在现实世界中存在如果有增强的活板门排列。因此,协议可以建立在现实世界中使用可组合定理[32]。
在本文有限的协议轮时,方知道最后一轮协议终止。我们将证明相互合作是一个连续的平衡。演示顺序平衡特别是在最后一轮很麻烦。然而,是否有这样的序贯均衡存在(33]。我们强调,股票总迭代的长度在第二阶段,因此,协议将在恒轮结束。为了清晰起见,我们重新描述的引理18]。
引理3。鉴于,在那里表示保持轮协议中,存在一个连续的平衡,这样双方合作之前轮在协议表示的总轮协议。
4所示。公平与常数轮
在完全信息情况下,没有两党协议计算功能的逆向归纳(25]。当最后一轮,双方不再害怕未来惩罚和倾向于芬克。正如我们知道,芬克是主导战略合作,因此,圆的现在是最后一轮,芬克和球员将策略。这个过程以这种方式继续向后在时间和芬克在轮表明党更好。如果我们释放这个条件,困境就会被打破。我们假设每个政党都有一个私有类型像理性或tft的派对。根据引理3,双方合作前最后几轮。灵感来自于这个结果,我们构造一个协议双方之间的公平。非正式描述节中给出1.3,现在我们给协议的特定表现。
4.1。停止运行故障设置
正如克罗齐和卡茨(21),我们的协议由两个阶段组成。在停止运行故障设置,第一阶段是一个功能(见框1)。第二阶段包括协议(见框2),双方交换他们的股票在不完整的信息。
4.2。积极的结果
定理4(主要定理)。考虑到效用假设(a)和(b)和声誉的假设(c),存在一个完全公平的协议与常数轮来计算在不完全信息下停止运行故障设置,当事人是tft的概率。如果增强活板门排列存在,完全公平的协议也是建立在现实世界中。
证明。我们将首先分析协议在一个混合的世界,那里是一个值得信赖的经销商计算。然后后(32),如果协议是计算在混合的世界,也是建立在现实世界中当增强活板门排列存在。协议的正确性和隐私是担保的理想功能。这里省略了正式的定义和简单的证明。我们证明公平在停止运行故障设置。(我)当第一步的盒子2完成时,很明显,聚会可以获得使用拉格朗日插值后接收。剩下要做的就是与他的对手交换股票和恢复用拉格朗日插值。然后最后他得到。(2)当第二步的盒子2结束,我们知道,即使当事人知道价值,他们仍然在第一次合作轮(引理3)。因此双方之前的之前没有激励偏离轮,沙米尔的阈值的秘密共享方案。在这种情况下,双方将获得至少从他们的对手。换句话说,聚会可以检索利用拉格朗日插值,最后学习。
总之,公平是实现在两个设置。圆形的复杂性这是更有效的比在[21]。我们强调,我们的结论的纳什均衡比(21),只有计算建立了纳什均衡。在这里,停止运行故障的序贯均衡设置是根据引理3。
4.3。我们的协议的应用程序
我们最重要的财产协议是公平合理安全的成就党计算。虽然公平是实现在以前的作品,这是第一次,它是通过声誉的假设,各方在协议采用TFT的策略。公平性是至关重要的在大多数的财产安全多方计算,如电子投票和电子拍卖。电子投票;例如,选民投票给候选人,希望得到一个公平和正确的结果。也就是说,结果不能被敌人有偏见,真正应该反映他们的意见。传统的安全多方计算不能实现公平的财产。因此,他们不能阻止对手偏压结果。幸运的是,rational安全多方计算可以实现公平。一方面,我们的理性协议保证每一方可能得到相同的投票结果。 On the other hand, the adversary cannot bias the result.
协议的应用在电子投票存在如下。我们描述的电子投票协议停止运行故障设置使用的协议。假设选民参与投票可能在未来参与其他投票。当他们再次相遇时,他们将评估通过之前的互相交互。几次会议后,每个选民对他赢得声誉类型。类型表明,选民是理性的,或者他们可能采用TFT的策略。正如上面提到的,有一个概率描述类型的先验概率。到目前为止,电子投票的选民的有相同的特性。接下来,我们将描述电子的过程上面提到的选民参加投票。(我)选民运行分别使用他们的特定的输入和接收他们的输出(盒子1)。(2)选民运行协议根据他们的类型和每一步后更新的声誉(盒子2)。(3)选民输出他们收到的协议。
我们证明,给予适当的参数,可以实现公平的协议。因为选民的政党有相同的特性,定理4可以正确地应用到电子投票,公平也实现了。
5。结论
安全保障的重要性在移动社交网络和电信服务迅速增加,因为应用程序在移动社交网络越来越受欢迎。公平的财产是在安全的计算成为一个引人注目的方面尤其是在理性双方之间。博弈理论开辟了另一个大道集中研究公平安全多方计算。Asharov et al。34基于效用假设不当)给负面结果。他们的结论是,没有党激励与他人合作。克罗齐和卡茨(21)修改缺陷与新的效用假设和两个修改带来一些新的问题。因此,该协议在21有一双大而圆的复杂性和经销商的信任是需要参与的协议甚至在现实世界中。
受方在移动社交网络声誉价值,可以提高两个理性的政党之间的合作,我们修改工具定义,允许各方考虑声誉来自移动社交网络的影响时的交互协议。结果表明,合作出现在最后一个“几”轮甚至当他们知道终端在有限重复游戏下不完整的信息。然后我们构造一个协议就像克罗齐和卡茨(21]。最后,借助TFT策略和移动社交网络的声誉,协议在本文中可以实现公平和序贯均衡。
信息披露
本文介绍的一种抽象INCOS2013会议,309 - 314年,2013页(35]。
利益冲突
作者宣称没有利益冲突有关的出版。
确认
这项工作得到了中国自然科学基金批准号。61173139和61173139下,山东省自然科学基金批准号下BS2014DX016博士项目的基础下Ludong大学批准号LY2015033。