第37卷第2期 (2021年 3 月）
福建师范大学学报（自然科学版）
Journal of Fujian N o n n a l University (N a t u r a l S c i e n c e Edition)
Vol. 37,N o. 2
M a r. 2021
D O I：10. 12046/j. issn. 1000-5277. 2021. 02. 005文章编号：1000-5277(2021)02-0031-08
非交互式可验证的模指数外包方案
李朝珍“2，林昌露u’3’4，黄可可u
1,2,3.4
(1.福建师范大学数学与信息学院，福建福州350117;
做梦梦见前女友2.福建师范大学福建省网络安全与密码技术重点实验室，福建福州350007;
交叉遗传3.网络空间与信息安全重庆市重点实验室，重庆400065;
4.桂林电子科技大学广西可信软件重点实验室，广西桂林541004)
摘要：基于现有的模指数外包方案中单个服务器验证概率较低，以及2个服务器完全可验证需要多次交互等问题，设计了 2个不可信的服务器模型下非交互式可验证的模指数安全外包方案.利用逻辑分割的
方式，保护用户数据的隐私性；利用安全外包形式化定义证明了该外包方案是安全的.方案具有以下优势：输入数据具有保密性；服务器与用户不需要交互；服务器计算的每一部分结果都可以验证.相比于其他方
案，提出的方案同时具有完全可验证性、输入保密性和非交互性的优势.
关键词：外包计算；可验证计算；模指数；恶意敌手
中图分类号：T P309文献标志码：A
Non-Interactive and Verifiable Outsourcing Computation
Scheme for Modular Exponentiation
(1. College of Mathematics and Informatics y Fujian Normal University，Fuzhou 350117,China；
2. Fujian Provincial Key Lab of Network Security & Cryptology y Fujian Normal University，Fuzhou 350007,China；
3. Chongqing Municipal Key Laboratory of Cyberspace and Information Security^ Chongqing 400065,China；
4. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004,China)
Abstract：In this paper, a non-interactive and verifiable outsourcing computation scheme for modular exponentiation under two untrusted rver models was designed, which is bad on limita
tions of the existing modular exponential outsourcing schemes, such as the low probability of single rver validation and the need for multiple interactions between two fully verifiable rvers . The pro
pod scheme protects the privacy of ur data by logical gmentation, and the formal definition of curity outsourcing proves that the outsourcing scheme is cure . The scheme has the following ad
vantages ：The input data is confidential. There is no interaction between the rver and the ur.
Each part of the results calculated by the rver can be verified. Compared with existing schemes, the propod scheme has the advantages of complete verifiability, input confidentiality and non-in
teractivity.
Keywords ：outsourcing computation ；verifiable calculation ；modular exponentiation ；malicious adversary
外包计算是计算能力有限的个体或公司，以按次计费的方式将艰巨的计算任务外包给具有强大计 算能力服务器来完成的过程.在这信息技术快速发展的时代，大量的工作需要较强的计算能力才能够收稿日期：2020-10-12
好看的书基金项目：国家自然科学基金资助项目（U1705264)；福建省ft然科学基金资助项目（2019J01275)；广西可信软件重点实验室研 究课题（K X202039)
通信作者：林昌露（1978 -)，男，副教授，研究方向为密码学及其应用.cllin@ fjnu.edu
小暑诗词LI Chaozhen1 2, LIN Changlu12 3 4 , HUANG Keke1
32福建师范大学学报（自然科学版)2021 年
完成；由于现阶段计算资源分配不均衡，大部分的设备没有能力计算闲难度较大的任务，只能将该任
务外包给云服务器进行计算.外包计算一般要满足以下两点基本要求：一是要确保云服务器返回给用
家庭开放日
户的计算结果是正确的；二是用户外包计算的代价要小于自己独立计算.
1992年，C h a u m和Peder S e n[1：提出了 “电子钱包”的概念，用来解决客户和银行之间有关交易
的计算问题，称之为“带有观察者的钱包它就是将复杂的计算任务外包给一个不可信的设备进行
计算的思想，即称为“外包计算2005年，Hohenberger和Lysyanskaya”将“电子钱包”概念形式
化，提出了外包计算的一般模型，并给出了在该模型下安全性定义.2010年，G e n n a r o等人[3]引人了
非交互式可验证外包计算的概念，它允许计算能力较弱的客户端将计算任务外包到一个更强大但不受
信任（即具有恶意攻击行为）的服务器中.2015年，C h e n等人[4]提出了一种高效的计算双线性对外
包方案，该方案是基于2个不可信服务器的模型下，用户只进行5次加法和4次乘运算，不进行任何
扩展操作.此外，其他学者还研究了其他特定类别的函数外包计算，如矩阵运算:5]等.
模指数运算是公钥密码体制中最基础运算，但其运算又极其复杂.例如，在算法中，加密解密过
程中都需要用到模指数运算.H oh enberger和LySyanSkaya[2：提出了第一个外包加密计算的安全模型，
并提出了第一个模指数运算的安全外包方案.在他们的方案中，用户仅有|的概率能检验出云服务器
的恶意行为.C h e n等人[6]在一个半诚实和一个恶意服务器模型下提出了一种新的安全的模指数外包
方案，结果的可验证概率是M a等人m针对批量模指数运算，提出了几类外包计算方案，但计算
的底数或指数对服务器是公开的，不能保护用户输入数据的隐私性.R e n等人[8]提出了一种基于2个
不可信服务器的模指数的安全可验证外包方案，方案过程中需要一次交互过程；如果其中一个服务器
有恶意的行为，被用户检测到的概率为1.上述的3种方案都是基于2个不可信服务器模型假设.Dijk
等人[9]提出了一个基于单个服务器的模指数外包方案，但用户的输入对服务器是公开的，因此它不
能确保输人的隐私性.S u等人[">]基于单个不可信服务器构造了模指数安全外包方案，结果可验证的 11Q
概率为现有基于单个不可信服务器模型假设的模指数运算外包方案，其计算效率较高，但它不
兰花养殖方法与技巧能完全检查出服务器的恶意行为，并存在泄露用户隐私数据的风险.现有的基于一个半诚实和一个恶
意服务器模型假设的模指数运算外包方案，其通信代价较大，例如存在多次的交互现象等，其结果可
完全验证比较少.
本文针对上述问题，本文设计了一种新的非交互式可验证的模指数外包方案.主要研究内容及贡
献如下：
(1)基于1个半诚实服务器和一个恶意服务器假设，提出了 1个双服务器模型下非交互式可验 证的模指数安全外包方案；
(2)借助R a n d子程序对用户输人的数据进行逻辑分割，以保护用户数据的隐私性并提高了计算 效率，实现对底数和指数的隐藏，其输人数据的安全性是基于离散对数困难问题假设；
(3)在外包过程中用户和服务器都只进行1次发送和1次接收，即不需要多余的交互过程；
(4)本文方案中2个服务器计算返回任意的结果都有相应的等式给予验证，验证服务器恶意行 为的概率为1，即只要服务器返回错误结果，用户可以检测到该行为.
1预备知识
1.1计算不可区分
计算不可区分f〜的概念：设概率簇义=|；f(a,n.;n e N是无穷数列，其中索引为a e
[0, 1]*，/I e N，且N为自然数集.X = U(a，W L m,,r;…E P^y= m a，n)L e[。，u.;…eN是 2 个
概率簇，对任意非一致性多项式时间算法Z)，存在可忽略函数m>g Z(n)使得可以区分的优势为：
第2期李朝珍，等：非交互式可验证的模指数外包方案33
AdvD=1P r[D(A'(a, n) ) = 1] -P r[D( Y(a,ra) ) = 1] I<negl(n),
则称义=U(a,r〇|与F H F(a,n)丨是计算不可区分的，即.可忽略函数对任意多
项式p U)都有《eg/(n)矣其中《足够大.在模拟实验中，计算不可区分性可用以证明外包计算
P(n)
方案的安全性.
1.2安全外包方案的定义
在2005年，Hohenberger和Lysyanskaya -将C h a u m和Pedern 1“电子钱包”概念形式化，提出了一种外包计算的模型并给出了该模型下安全外包方案的定义.该模型将执行算法分成两部分：可信但计算能力相对较弱的部分r；以及不可信但计算能力相对较强的部分c，当c会发生恶意行为 时，记为c'.r和c一起完成算法，即Aig= f.在算法执行后，不可信部分c与外界交互需要通过可 信部分r一起执行.定义敌手J= (£, c')，其中£代表恶意环境（类似于实际模型中的外部敌手），它可能在算法A i g执行前同r共谋出一个攻击方式，通过向A i g发送一些自己选取的输入来执行该攻 击.算法A l g定义如下：
(r s.y P,x hp,x hu,x ap,x au).
根据信息的来源以及保密程度，将算法的输人分为5种可能的类型：
(1) *。诚实隐私的输人，由诚实方生成，对£和<^都保密；
(2) 诚实受保护的输入，由诚实方生成，对c'保密，对£公开；
(3) \u：诚实不受保护的输人，由诚实方生成，对£和（：'都公开；
(4) 、：敌对受保护的输人，由五生成，对C'保密；
(5) \u：敌对不保护的输人，由E生成，对C'公开.
根据保密程度算法的输出可分为3种类型：
(1)y s：隐私的输入，对£和匸'都保密；
(2) yp：受保护的输人，对C'保密，对£公开；
(3) y u：不保护的输入，对£和（：'都公开•
安全外包方案是指：若C)满足下列要求，则执行A l g算法的（7\ C)就是安全外包计方案
(1) 正确性：产是A l g正确执行的结果.
(2) 安全性：对于所有概率多项式时间能力的敌手j= C')，存在概率多项式时间能力的模 拟器（S,,S2)使得下列两组随机变量对都是计算不可区分的.
第一对 ~£K/£lF i d e a l，说明了恶意环境£在执行，过程中得不至I J隐私的输入与输出，即外部敌手£无法得到任何有用信息.在实际和理想的操作过程中都是分回合进行的.E K/E l F d表示 恶意环境£在参与实际操作过程中得到的信息，按以下过程进行.
①实际过程E V/E r—=丨（邮咖，，<，乂）}:
.，<，〇—/(1*, )：在第i轮中，诚实的程序/输人安全参数/r和第i- 1轮中保留状态1，输出下一轮所需的状态t'W a t d和，，：^，，在此操作过程中，恶意环境 £不能访问/.
•(e伽e'，/，*;，<u，仙£(1*，£V7£r J，£基于上一轮所得到的信息£V7£r J 和这一轮/生成的；选择下次调用时的状态标记的索引/，£可以输入 将索引i—/，但不能改变其值；£生成的输入；<u和一个决定进程是否在^'轮终止一个布尔变 量stop1.
•(加a，e’，c副e1，y:，y;，乂）―严―’丨)（如a«e‘—1，<，4，<，*;，O ：算法产在输人第卜1轮中保留状态如ate' — 1和4，<,<,，<p，上运行，生成了下一轮调用时的状态mate1，estate^i\y\, y'p,y\.
■当=T R U E时，有=£V7£tT…_a l，在此操作过程中，£最终只能获得最后一轮的信息
34福建师范大学学报（自然科学版)2021 年
estate,y p,y'u.
表示恶意环境£在参与理想的操作过程中能得到的信息，具体执行过程如下•
②理想过程£V7£F i d,.a l = | (咖加e',z;，〇 | :
•(b«a<e',)<—/(I4,〜ate'—1)：在第；轮中，诚实的程序/输入安全参数A：和第i- 1中保留状态以a f d_l，输出下一■轮所需的状态i i'ta fe'和，；(^，4,,,，在此操作过程中，恶意环境£ 不能访问/.
•(如灿1，/，^，<…，伽— £(1*，E V7E H£基于上一轮所得到的信息£V7£ITJ」和这一轮/生成的‘，<…选择下次调用时的状态标记，的索弓丨/, £生成的输人4p,<u和一个决定进程是否在i'轮终止一个布尔变量^〇//.
.(a福e'，X:，<，乂）—A lg(a伽e'—1，a/二4p，a4, <p,()：算法Alg在输人第卜 1轮中保留 的状态aWafel_1和;^，4，4，输出下一轮用到的状态a.s«ate'和乂:，y丨，/u.
•(sstate',estate,Y p,Y u,rep1) <^S c l c s,a,e''(sstate'~',x/'hp,xl'h l l,x'ap,xa X i y\, y l u) ：起运行算法S,e'在不知道吨情况下，输人i_ 1轮保留的状态和<,*1, , <… <，}d输出如a k1，}；，F u，r e//■其中rep'—个布尔变量它决定了y；，y：，是否等于;k;,，y i，在此过 程中S，可以向C'数据库发出询问.
•(4，O — r e p Z a c e‘（K，〇+ (1 - r e p/a c e1) (y;，〇：若r e p Z a c e1 — 0，则S'输出y;，义；若哪/ace‘ —1，则S，输出r p,r….当灿p^T R U E时，有£W£『,d e a l=£：V7£l^l f a l.
第二对 C K/£l Tr e a l~ C V7£I F,d p a l，说明了不受信任的软件C'在产执行过程内部敌手无法得到任 何额外信息.从第一个对中得到的信息为s<o// =77?(/£时，有C K/£lF…a l =«^w/…a l.
理想过程c i;ieM；;,l<;a l:
•(八1A_,i s t o f1)：在第i轮中，诚实的程序/输人安全参数/c和第i- 1中保留状态输出下一轮所需的状态m a t e1和，^4, a^u.
•(estate,/,x\v,x ap,stop') E ( l l, estate-', x hp,x[u, y~', E k,±—eWafe'—丨，输出（丨，乂_l和输入<，：^的基础上生成了es<a<e’，/，W o p'，其中stop'是决 定进程是否在i轮终止一个布尔变量.
•{astate ,y\, y'p,/…)•<-A l g(,x'i,x!'hp,,x'a p,x'a u) ：Alg ftasiaie'"1,x'l,o d'h p ^,'u»x ap,xl a u j s^f^^lastate',y's,y\, y u.
•(s s t f l Z e’，iwmte丨）<—贫…‘故’1，C <:u)：模拟器S丨和C’一■起运行算法S/’在只有上一轮状态wtaie…和;t^u，4输出了如咖1,i w t a k两种状态.
•C K/EtF^ = (cw a t e')：当伽=T R U E 时，有C W£lFi d e a丨=C F/£IF；(W，只能得到最后一轮的输出 estate1.
在理想过程中，具有状态的模拟器S2的输入只有<…)，并且允许访问C'，最终得到的信息 也是.e state1.
综上所述，£V7£lF…a l ~£V7£lF,,l p a d1]C V/£r r e a l ~C F/£%(W都是计算不可区分的.它们的计算不可 区分性是指得到一些信息的外部敌手和恶意服务器与不知道这些信息的模拟器,S2最终得到的信 息是一样的.安全性外包定义要求£，C'对产的隐私输人与输出&，y, —无所知.
文献[2]还定义了外包方案的a-效率和少可验证的概念：a-高效的外包方案是算法A l g对任何输 人用户的操作的时间不会超过算法A l g的a乘法因子倍；小可验证的外包方案是用户对任意输人的算 法执行过程中能检测出错误的概率不小于/3.同时具有效率和/3-可验证的外包方案记为（ct，办）. 1.3子程序
子程序[12]是生成随机对的算法.设h9是2个大素数，以V g e Z/，A e Z,，作为R a n d的输入，每次调用它将会生成随机对i m o d p).若输人参数为Z比特长，则调用子程序R a n d生成的随机值
第2期李朝珍，等：非交互式可验证的模指数外包方案35
一般有2种方法：一是需要用0( log2/)次模乘运算的B P V产生器方法，二是需要0(1)次的查找表格 法.在H o h e n b e r g e r和Lysyanskaya方案⑵中用户调用子程序R a n d生成随机对来肓化输人数据，避免 了用户自己去选取类似与/m o d p这样的随机值产生高额代价，从而提高了用户的计算效率.
1.4外m u■算模型
本文讨论可验证外包计算方案是由1个恶意服务器和1个半诚实服务器组成的两服务器模型，且 2个服务器不共谋，本文把这种假设称为“单恶意服务器模型”.其中恶意服务器会有恶意行为，例如欺骗用户返回给用户错误的计算结果和损坏用户存储在服务器的数据等.半诚实的服务器又称为是 好奇的服务器，它会严格地按照协议进行计算，由于它是好奇的服务器可能会记录用户计算的数据，并试图通过记录的数据推测出有用的信息.外包计算模型如图1所示，具体流程如下.
服务器C,
服务器
图1外包计算模型
Fig. 1O u t s o u r c i n g c o m p u t a t i o n m o d e l
(1) 用户调用R a n d子程序生成随机数对(A,/m o d/〇，用于数据的隐藏；
(2) 用户利用逻辑分割的方式盲化数据，并将盲化数据发给服务器C,,C2;
(3) 服务器（：,，心收到盲化数据后，按照用户要求和顺序计算结果，将其计算结果发给用户;
(4) 用户收到相应的结果进行验证，验证通过，计算最终结果，否则输出终止符号“丄
2方案构造
2.1具体构造
本文针对1个半诚实服务器和1个恶意服务器模型，对模素数的指数运算构造1个新外包计算方 案.设1
个用户为r和2个服务器分别为C,，C2，用户r利用子程序R a n d把自己的模指数运算外包给 服务器心和(：2.在下列方案中，C,U，y)->/代表着输入数据X，y，C，计算结果/，其中〖=1，2.
萝卜海带排骨汤做衣服设/>，g是2个大素数，且g I /? - 1.模指数运算的输入为a e &和u e•，有u9三1(m o d/?)，要计算z/m o d p，其中数据u，a对服务器是保密的.方案的具体执行过程如下：
第一步用户:T调用 R a n d生成随机对（a，g a)，（0，/)，（q，#)，（《2,#)•记f = g am〇d p9fi =m o d p.
第二步用户r利用---厂，沒=(a a-)8)m o d9，V c/，e，6丨，62，C丨，C2e Z对输人进
f m o d p
行分割：
(1)对底数的拆分：= (f . <p)° =疒.
