Page 344 - 《软件学报》2021年第6期

1918 Journal of Software 软件学报 Vol.32, No.6, June 2021

受该计算结果(如图 6 所示).当输出为 0 时,委托方向可信第三方 TTP 提出申诉,TTP 对计算方 C 进行惩罚,取回
罚金交给委托方 P.
当委托方 P 在 t 2 时间没有收到计算方 C 的计算结果 F(D)和承诺 com,委托方 P 考虑可能是因为网络问题
等客观因素导致没有及时收到,委托方 P 在自己能容忍的范围内继续等待 t″时间.若委托方 P 在 t″时间内收到
计算方发送的计算结果 F(D)和承诺 com,委托方 P 在 t+t″时间内按上述步骤进行验证和支付;若委托方 P 在 t″
时间仍没有收到计算结果 F(D)和承诺 com,则判定计算方 C 背叛协议,委托方 P 向 TTP 提出申诉,可信第三方
TTP 对计算方 C 进行惩罚,取回罚金交给委托方 P.
若计算方 C 选择“诚实”行动,如约提交了正确的计算结果 F(D)和承诺 com,并且通过了委托方 P 的验证,但
在响应时间没有收到相应的酬金和奖励,此时,计算方 C 可向 TTP 提出申诉,TTP 对委托方进行惩罚,取回罚金ω
交给计算方 C.

3. VerCom(r,com,F(D))→{0,1}.验证承诺算法由委托方 P 执行.输入随机数 r、
r
函数值 F(D)和承诺值 com,若 com = g ()FD g 1 modq ,输出 1;否则,输出 0.
Fig.6 Formalization of verifying commitment stage
图 6 验证承诺阶段形式化

4 协议分析

本节首先通过证明定理 1 与定理 2 的形式,对基于理性信任模型的理性委托计算协议进行正确性分析与安
全性分析;其次,采用表格的形式列出 l i 和α i 与效用 u i 的关系,并通过实验证明引入参数 l i (服务器 S i (i=1,2,…,n)
的生存周期)作为计算方 C 诚实执行协议时,得到奖励的参数对计算方的影响;然后,对本文所提基于理性信任
模型的理性委托计算协议的复杂性与文献[6,30,31]的方案进行性能对比.
4.1 正确性分析

定理 1. 本文基于理性信任模型的理性委托计算协议具有正确性.
证明:根据上述博弈分析可知,“诚实”是该理性委托计算协议的纳什均衡点,即:只有委托方 P 和计算方 C 都
选择诚实执行协议时,委托方 P 和计算方 C 才能获得最大效益.假设计算方 C 背叛协议,发送错误的计算结果给
委托方 P,则计算方 C 将会受到严重的处罚,罚金为|re 2 (f)|=ρl i .此外,该计算方的生存时长将会被清零,即 l i =0,从而
导致产生未来的损失γ=3ρl i .因此,若计算方 C 想要使自己获得的效益最大,将会选择“诚实”行动,正确完成计算
任务,并向委托方 P 返回正确的计算结果,保证计算结果的正确性. □
4.2 安全性分析
定理 2. 假设格中最短向量问题(shortest vector problem,简称 SVP)是困难的,本文基于理性信任模型的理
性委托计算协议满足语义安全性.
证明:定理的证明采用 IND 游戏的方法,假设游戏中存在多项式时间敌手 A,用 Adv IND (A)表示敌手 A 在游戏
中的优势.
初始化阶段:挑战者产生系统Π,调用密钥生成算法得到公钥私钥对(pk,sk),并将公钥 pk 发给敌手.
挑战阶段:敌手 A 在得到公钥 pk 后选择两个长度相同的明文消息 m 0 和 m 1 提交给系统.
*
*
Phase0:挑战者选择一个随机比特 b∈{0,1},调用加密算法将 m 加密成目标密文 e =δs+pc+m,同时将 e 发送
*
给 A.A 收到 e 后输出一个比特 b′作为对 b 的猜测,敌手 A 的优势为:
1
Adv IND () =A Pr[ ′ = b ] − b .
2
∗
Phase1:改变 Phase0 中公钥的生成方式,Phase1 中的公钥直接从 R 中随机均匀选取.文献[32]中指出,根据
q
∗
高斯离散分布输出的样本与 R 上的均匀分布是概率不可区分的.因此,敌手 A 无法区分 Phase0 和 Phase1,即:
q
|Adv Game0 (A)−Adv Game1 (A)|=0.