0 概述

在大数据快速发展的时代背景下，云计算通过强大的计算能力和存储能力^[1]为云端客户提供各种委托计算服务，能够节省委托方大量的计算时间和计算成本，但委托计算验证结果所消耗的时间必须远少于计算函数本身，否则委托计算将毫无意义。随着计算需求量的增加，委托计算也面临很多严峻的挑战^[2]，如计算协议中会存在恶意的计算方故意偏离协议的执行，从而泄露用户的隐私数据或返回非正确的计算结果，或者计算方诚实地将计算结果返回给用户，而恶意的私自验证客户却声称服务器返回的结果不正确，从而拒绝支付委托费用。因此，有必要设计一种在不泄露用户隐私的前提下能够公开验证的委托计算协议。

针对数据的安全性和隐私性，公开可验证计算（PVC）方案^[3]能够提供较好的解决思路，其计算过程为：委托方对需要委托的函数进行一系列混淆加密后发送给云端服务器；服务器返回正确的计算结果和结果证明，所有的公开验证者都可以验证其结果的正确性，且验证成本远小于本地执行的成本。可验证计算一般分为两类：一类是一般函数的可验证委托计算^[4-5]，适用于任何函数的计算；另一类是特殊函数的委托计算，如矩阵乘法和多项式计算^[6-8]、模指数运算^[9]等。在实际委托计算环境中，许多问题都可以转化为多元多项式的求值模型，如评估一个人的健康状况、根据水源中的COD浓度建立污染物水质分析模型等。

2010年，GENNARO等人^[10]在CRYPTO会议上首次提出可验证计算的概念，并利用全同态加密技术和混淆电路技术构造可验证计算方案，从而保证了委托计算输入与输出的隐私性。文献[11]设计选择明文攻击（CPA）安全的多项式委托计算协议来保证多项式函数的隐私性，以解决可验证计算方案只能私自验证的问题。文献[12]利用全同态加密技术，在所构造的非交互式委托计算方案中降低了委托计算的通信量。文献[13]利用多线性映射和全同态加密技术，在保证输入隐私性的情况下，设计了单变量多项式委托计算方案。文献[14]构造了多项式委托计算协议，但不能保证其可证明安全性。文献[15]通过随机化混淆电路提出的可验证委托计算方案，实现了混淆电路的可重用。文献[16-17]在博弈论的框架下设计理性委托计算协议，利用混淆电路与全同态加密技术设计可证明安全的委托计算方案，保证了可验证计算的有效性。

如何使委托计算能在公开可验证情况下保证计算结果的隐私性以及协议的安全性，一直是众多研究学者所关心的问题。文献[18]针对身份验证过程，提出一种新的方案来解决因用户损坏和服务器受损而引起的各种问题，该方案被证明是安全的，且避免了隐私性与实用性的冲突。文献[19]针对协议中会存在恶意攻击者的问题构造了一种更强大的C2C PAKE协议来应对恶意攻击，以保证协议中通信的安全。文献[20]提出了一种鲁棒的多因素身份验证方案，利用RSA密码系统的不平衡计算特性保证方案的安全性。文献[21]通过使用基于身份的签名方案构造一种针对MCC服务的PAA方案，该方案不仅能够保证参与者的通信安全，而且可以满足MCC服务的安全要求。

本文利用全同态加密与多线性映射技术构造可公开验证的多元多项式委托计算安全协议，并在标准模型下，基于多线性Diffie-Hellman（Multi-linear Diffie-Hellman，MDH）困难性数学问题假设证明协议的有效性和安全隐私性，存在任意第三方利用多线性性质都可以满足委托计算结果的正确性。

1 预备知识 1.1 全同态加密

全同态加密通常包括4个阶段^[22]，即预处理阶段$ (SK, PK)\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}{\mathrm{p}}_{\mathrm{F}\mathrm{H}\mathrm{E}}\left({1}^{\lambda }\right) $、加密阶段$ c\leftarrow \mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}{\mathrm{t}}_{\mathrm{F}\mathrm{H}\mathrm{E}}(PK, m) $、解密阶段$ m\leftarrow \mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}{\mathrm{t}}_{\mathrm{F}\mathrm{H}\mathrm{E}}(SK, c) $和运算函数阶段$ {c}_{\mathrm{f}}\leftarrow $ $ \mathrm{E}\mathrm{v}\mathrm{a}{\mathrm{l}}_{\mathrm{F}\mathrm{H}\mathrm{E}}(PK, {c}_{\mathrm{i}\mathrm{n}}, f) $。

对于任意的$ k\in {\mathbb{Z}}_{N} $且$ k\ge 2 $，BGN同态加密算法$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k}=(\mathrm{G}\mathrm{e}\mathrm{n}, \mathrm{E}\mathrm{n}\mathrm{c}, \mathrm{D}\mathrm{e}\mathrm{c}) $描述如下：

1）密钥生成算法。$ {{\mathit{\Gamma }}}_{k}=(N, {G}_{1}, {G}_{2}, \cdots , {G}_{k}, e, {g}_{1}, $ $ {g}_{2}, \cdots , {g}_{k})\leftarrow G({1}^{\lambda }, k) $表示为随机的$ k $多线性映射实例，其中，$ N=pq $，$ p $和$ q $均为$ \lambda $ bit大素数，$ e $是任意自然常数，$ {g}_{i} $是循环群$ {G}_{i} $的生成元，公钥$ PK=({g}_{1}, h) $和私钥$ SK=p $，$ h={u}^{q}, u\leftarrow {G}_{1} $，$ h={u}^{q}, u\leftarrow {G}_{1} $表示散列函数。

2）加密算法。密文$ c=\mathrm{E}\mathrm{n}\mathrm{c}(PK, m) $，输入明文m和公钥PK，输出密文$ c={g}_{1}^{m}{h}^{r}\in {G}_{1} $，其中，$ r\in {\mathbb{Z}}_{N} $。设$ \mathrm{E}\mathrm{n}\mathrm{c}\left({m}_{l}\right)={g}_{1}^{{m}_{l}}{h}^{{r}_{l}} $ $ (1\le l\le k) $，$ h={g}_{1}^{q\delta } $，$ \delta \in {\mathbb{Z}}_{N} $且$ {r}_{l}\in {\mathbb{Z}}_{N}, {h}_{k}=(h, {g}_{1}, {g}_{1}, \cdots , {g}_{1})={g}_{k}^{q\delta } $。

3）解密算法。明文$ m=\mathrm{D}\mathrm{e}\mathrm{c}(SK, c) $，此算法是以SK和密文$ c $为输入的解密算法，输出消息$ m $，使得$ {c}^{p}=({g}_{1}^{p}{)}^{m}{h}^{rp}=({{g}_{1}}^{p}{)}^{m} $，并求解离散对数问题得到明文$ m $。

1.2 多线性映射

设$ {G}_{1} $和$ {G}_{2} $分别为$ q $阶（$ q $为大素数）加法循环群$ ({G}_{1}, +) $和乘法循环群$ （{G}_{2}, +） $，多线性映射$ e:{G}_{1}^{n}\to {G}_{2} $具有以下性质：

1）多线性：对于任意$ {g}_{1}, {g}_{2}, \cdots , {g}_{n}\in {G}_{1} $和$ {a}_{1}, $ $ {a}_{2}, \cdots , {a}_{n}\in {\mathbb{Z}}_{q}^{\mathrm{*}} $，满足等式$ {e}_{n}({a}_{1}{g}_{1}, {a}_{2}{g}_{2}, \cdots , {a}_{n}{g}_{n})={e}_{n}({g}_{1}, {g}_{2}, \cdots , {g}_{n}{)}^{{a}_{1}{a}_{2}\cdots {a}_{n}} $。

2）非退化性：如果任意$ g $是$ {G}_{1} $的生成元，则$ {e}_{n}(g, g, \cdots , g) $是$ {G}_{2} $的生成元。

3）可计算性：对所有的$ {g}_{1}, {g}_{2}, \cdots , {g}_{n}\in {G}_{1} $，存在有效的计算法则$ {e}_{n}(g, g, \cdots , g) $，则称$ {e}_{n}(g, g, \cdots , g) $为多线性映射。

1.3 困难性问题假设

MDH困难性问题描述如下：在$ ({G}_{1}, {G}_{2}, e) $中，$ {G}_{1}\mathrm{、}{G}_{2} $均是$ N $循环群，随机选取$ {x}_{1}, {x}_{2}, \cdots , {x}_{n}\in {\mathbb{Z}}_{N} $，对于给定$ {G}_{1} $的生成元$ {g}_{1} $，$ {g}_{1}^{{a}_{1}}, {g}_{1}^{{a}_{2}}, \cdots , $ $ {g}_{1}^{{a}_{n}} $，计算$ e({g}_{1}, {g}_{1}, \cdots , {g}_{1}{)}^{{x}_{1}{x}_{2}\cdots {x}_{n}}\in {G}_{i}(i=\mathrm{1, 2}, \cdots ，n) $是困难的。

多线性离散对数问题（MDL）描述如下：设$ {G}_{1} $为$ N $阶循环群，对于所有的$ k>1(1\le i\le k) $以及$ {g}_{i} $是循环群$ {G}_{i} $的一个生成元，给定$ (i, {g}_{i}, {g}_{i}^{x}) $，对于任意$ x\in {\mathbb{Z}}_{N}^{\mathrm{*}} $，求解$ x $是困难的。

2 安全模型

本文提出基于隐私保护可证明安全的委托计算协议及其安全模型，并从安全性和隐私性角度对协议进行验证。

2.1 协议安全性

在安全模型试验中，假设需要委托多元多项式函数$ F $，将函数的输入定义为$ x $。本文协议运用全同态加密算法对输入$ x $进行加密，其中公共值为$ {\sigma }_{x}\leftarrow \left(PK, \mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}\right) $，私有值$ {\tau }_{x}\leftarrow \left(SK\right) $。定义敌手在此安全模型中的优势为$ \mathrm{A}\mathrm{D}{\mathrm{V}}_{\mathrm{A}}\left(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{P}\mathrm{C}, F, \lambda \right)= $ $ \mathrm{P}\mathrm{r}\left[\mathrm{E}\mathrm{x}\mathrm{p}{}_{\mathrm{A}}\left(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{P}\mathrm{C}, F, \lambda \right)=1\right] $，即存在任意多项式概率的敌手A，如果概率$ \mathrm{A}\mathrm{D}{\mathrm{V}}_{\mathrm{A}}\left(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{P}\mathrm{C}, F, \lambda \right)-\frac{1}{2} $是可以忽略的，则协议是安全的。形式化分析如下：

$ \begin{array}{l}\mathrm{E}\mathrm{x}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{E}\mathrm{x}{\mathrm{p}}_{\mathrm{A}}\left[\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{P}\mathrm{C}, F, \lambda \right]\\ （PK, SK）\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}（{1}^{\lambda }, F）\\ （{x}_{1}, {x}_{2}）\leftarrow {A}^{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{G}\mathrm{e}\mathrm{n}}（PK）\\ （{\sigma }_{1}, {\tau }_{1}）\leftarrow \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{G}\mathrm{e}\mathrm{n}（PK, SK, {x}_{1}）\\ （{\sigma }_{2}, {\tau }_{2}）\leftarrow \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{G}\mathrm{e}\mathrm{n}（PK, SK, {x}_{2}）\\ b\leftarrow \left\{\mathrm{0, 1}\right\}\\ {b}^{\text{'}}\leftarrow {A}^{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{G}\mathrm{e}\mathrm{n}}（PK, {x}_{1}, {x}_{2}, {\sigma }_{b}）\\ \mathrm{i}\mathrm{f}\,{b}^{\text{'}}=b\\ \mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\\ \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\,0\\ \mathrm{e}\mathrm{n}\mathrm{d}\,\mathrm{i}\mathrm{f}\end{array} $

公开可验证多元多项式委托计算协议的安全性验证过程如下：

假设该试验中存在敌手A和挑战者C两个主要参与者。

1）初始化阶段：挑战者C首先需要执行KeyGen算法，然后把生成的公钥PK发送给敌手A。

2）询问阶段：敌手A对C进行有界多项式次加密询问后发送函数$ ({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $给C，C加密后将密文$ \sigma =({\sigma }_{{x}_{1}}, {\sigma }_{{x}_{2}}, \cdots , {\sigma }_{{x}_{n}}) $发送给A。

3）挑战阶段：询问结束后，C将敌手A攻击的目标输入$ ({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}) $和加密结果$ {\sigma }^{\mathrm{*}}=({\sigma }_{{x}_{1}}^{\mathrm{*}}, {\sigma }_{{x}_{2}}^{\mathrm{*}}, \cdots , $ $ {\sigma }_{{x}_{n}}^{\mathrm{*}}) $发送给A，A返回输入为$ {\sigma }^{\mathrm{*}} $的计算及证明结果$ (\overline{\rho }, \overline{{\pi }_{1}}, \overline{{\pi }_{2}}, \cdots , \overline{{\pi }_{n}}) $给公开验证者，且$ \overline{\rho }\notin \{{\rho }^{\mathrm{*}}, \perp \} $，$ {\rho }^{\mathrm{*}} $解密为$ {y}^{\mathrm{*}}=f({a}_{1}^{\mathrm{*}}, {a}_{2}^{\mathrm{*}}, \cdots , {a}_{n}^{\mathrm{*}}) $。如果$ \overline{\rho }\in \{{\rho }^{\mathrm{*}}, \perp \} $，则输出1，否则输出0。A成功的优势定义为$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{V}\mathrm{C}, F, \lambda )= $ $ \mathrm{P}\mathrm{r}\left(\mathrm{E}\mathrm{x}{\mathrm{p}}_{\mathrm{A}}^{\mathrm{V}\mathrm{e}\mathrm{r}}\right(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{V}\mathrm{C}, F, \lambda )\mathrm{ }=1) $。如果$ \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{A}}(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{V}\mathrm{C}, $ $ F, \lambda )\mathrm{ }= $ $ \mathrm{P}\mathrm{r}\left(\mathrm{E}\mathrm{x}{\mathrm{p}}_{\mathrm{A}}^{\mathrm{V}\mathrm{e}\mathrm{r}}\right(\mathrm{P}\mathrm{V}\mathrm{M}\mathrm{V}\mathrm{C}, F, \lambda )=1)<\mathrm{n}\mathrm{e}\mathrm{g}\left(\lambda \right) $成立，其中$ \mathrm{n}\mathrm{e}\mathrm{g}\left(\lambda \right) $是关于$ \lambda $的可忽略函数，则表明本文协议是安全的。

2.2 协议隐私性

该协议的隐私性验证过程如下：

假设游戏中存在敌手A、挑战者C和模拟器S 3个主要参与者。

1）初始化阶段：S与C执行Setup算法，并将公钥PK发送给A。

2）询问阶段：A发送$ ({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $给S进行加密询问，S返回$ \sigma =({\sigma }_{{x}_{1}}, {\sigma }_{{x}_{2}}, \cdots , {\sigma }_{{x}_{n}}) $给A，在此过程中的询问可以是重复多次的。

3）挑战阶段：询问结束后，A选择两个输入$ {x}_{1}=({x}_{11}, {x}_{12}, \cdots , {x}_{1n}) $和$ {x}_{2}=({x}_{21}, {x}_{22}, \cdots , {x}_{2n}) $发送给S，S选择$ i\in \{\mathrm{1, 2}, \cdots , k\} $，计算$ {\beta }_{1}={x}_{1}^{{2}^{i}} $和$ {\beta }_{2}={x}_{2}^{{2}^{i}} $，并发送给C，C选择$ b=\left\{\mathrm{0, 1}\right\} $，并发送$ \mathrm{E}\mathrm{n}\mathrm{c}\left({\beta }_{b}\right) $给S，S计算出$ T=\left(\mathrm{E}\mathrm{n}\mathrm{c}\right({x}_{1}), $ $ \mathrm{E}\mathrm{n}\mathrm{c}\left({x}_{1}^{2}\right)\mathrm{ }\cdots , \mathrm{ }\mathrm{E}\mathrm{n}\mathrm{c}\left({x}_{1}^{{2}^{i-1}}\right), \mathrm{ }\mathrm{E}\mathrm{n}\mathrm{c}\left({\beta }_{b}\right), \mathrm{E}\mathrm{n}\mathrm{c}\left({x}_{1}^{{2}^{i+1}}\right), \cdots , \mathrm{E}\mathrm{n}\mathrm{c}\left({x}_{1}^{{2}^{k-1}}\right)) $，并将T发送给A，A返回$ {b}^{\text{'}}=\left\{\mathrm{0, 1}\right\} $给S。

4）猜测阶段：如果$ {b}^{\text{'}}=1 $，则S输出$ \widehat{b}=1 $，否则输出$ \widehat{b}=0 $；如果$ {b}^{\text{'}}=\widehat{b} $，则敌手A赢得这个游戏。

在上述游戏中，本文定义敌手A的优势为$ \left|\mathrm{P}\mathrm{r}\left[{b}^{\text{'}}=\widehat{b}\right]-1/2\right| $，即如果敌手A在多项式时间内经过多次重复询问后，都不能以大于$ ε $的概率赢得游戏，则表明本文协议满足输入输出隐私性。

3 协议构造

在上节构建的安全模型中引入全同态加密技术和双线性映射方案，设计隐私保护下可公开验证的多元多项式委托计算协议，如图 1所示。

假设委托方需要将$ n $元$ d $次多项式函数$ F({x}_{1}, {x}_{2}, \cdots , {x}_{n})=\sum\limits_{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d}{F}_{{i}_{1}{i}_{2}\cdots {i}_{n}}{x}_{1}^{{i}_{1}}{x}_{1}^{{i}_{2}}\cdots {x}_{n}^{{i}_{n}} $以及输入$ ({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $委托给云服务器进行计算，协议算法描述如下：

1）初始化阶段

（1）$ \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({1}^{\lambda }, F) $。首先选取一个随机的$ k $多线性映射实例$ {\mathit{\Gamma}} =（N, {G}_{1}, {G}_{2}, \cdots , {G}_{k(n+1)}, e, {g}_{1}, {g}_{2}, \cdots , {g}_{k(n+1)})\leftarrow $ $ G（{1}^{\lambda }, k(n+1)) $，$ k=\mathrm{l}\mathrm{g}(d+1) $，其中群的阶数为$ N=pq $，且p、q均为$ \lambda $ bit素数，然后选择$ s=({s}_{1}, {s}_{2}, \cdots , {s}_{n})\in {\mathbb{Z}}_{N}^{n} $，并使用$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $加密算法对$ s $进行加密，密文为$ {\sigma }_{s}=\mathrm{ }({\sigma }_{{s}_{1}}, {\sigma }_{{s}_{2}}, \cdots , {\sigma }_{{s}_{n}}) $，$ {\sigma }_{{s}_{i}}=\mathrm{ }({\sigma }_{{s}_{i1}}, {\sigma }_{{s}_{i2}}, \cdots , {\sigma }_{{s}_{ik}})\mathrm{ }\mathrm{ }=（{g}_{1}^{{s}_{i}}, {g}_{1}^{{s}_{i}^{2}}, \cdots , {g}_{1}^{{s}_{i}^{{2}^{k-1}}}) $，$ i\in \mathrm{ }\{1, \mathrm{ }\mathrm{ }2, \cdots , n\} $。为简化计算，先令$ M=({M}_{1}, {M}_{2}, \cdots , {M}_{n})= $ $ （{\sigma }_{{s}_{1}}, {\sigma }_{{s}_{2}}, \cdots , {\sigma }_{{s}_{n}}) $，再计算$ F={g}_{1}^{\mathrm{E}\mathrm{n}\mathrm{c}\left(f\right({s}_{1}, {s}_{2}, \cdots , {s}_{n}\left)\right)} $。令$ u\in {G}_{1} $，则$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $加密算法的公钥为$ PK=\{{\mathit{\Gamma}} , {g}_{1}, h\} $，私钥为$ SK=\{p, q\} $。

（2）$ \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{G}\mathrm{e}\mathrm{n}(SK, {x}_{1}, {x}_{2}, \cdots , {x}_{n}) $。设函数的输入为$ ({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $，使用$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $加密算法对输入进行加密操作，密文为$ {\sigma }_{s}=({\sigma }_{{s}_{1}}, {\sigma }_{{s}_{2}}, \cdots , {\sigma }_{{s}_{n}}) $，其中，$ {\sigma }_{{x}_{l}}=({\sigma }_{{x}_{l1}}, $ $ {\sigma }_{{x}_{l2}}, \cdots , {\sigma }_{{x}_{lk}})，l\in (\mathrm{1, 2}, \cdots , n) $，选取$ {r}_{ij}\in {\mathbb{Z}}_{N} $，则存在$ {\sigma }_{{x}_{ij}}={g}_{1}^{{x}_{i}^{{2}^{j-1}}}{h}^{{r}_{ij}}, i\in \{\mathrm{1, 2}, \cdots , k\}, j\in \{\mathrm{1, 2}, \cdots , k\} $，同时输出公开验证密钥$ V{K}_{x}=(F, M) $和私自验证密钥$ S{K}_{x}=p $。

2）委托计算阶段

（1）$ \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{e}(PK, \sigma ) $。云计算方收到$ \sigma = $ $ ({\sigma }_{{s}_{1}}, {\sigma }_{{s}_{2}}, \cdots , $ $ {\sigma }_{{s}_{n}}) $后，对接收的函数进行计算$ \rho $且验证证明$ \pi $，并返回给公开验证者。

（2）计算加密函数值。先将$ {i}_{b}(b\in \{\mathrm{1, 2}, \cdots , n\left\}\right) $用二进制形式表示，记为$ {i}_{b}=\sum\limits_{l=1}^{k}{i}_{bk}{2}^{k-1} $，则$ {x}_{i}^{{i}_{b}}={x}_{i}^{{i}_{b1}}\cdot ({x}_{i}^{2}{)}^{{i}_{b2}}\cdot \cdots \cdot ({x}_{i}^{{2}^{k-1}}{)}^{{i}_{bk}} $，用户使用$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $加密算法对$ {x}_{b}, {x}_{b}^{2}, \cdots , {x}_{b}^{{2}^{k-1}} $进行加密，再对于任意的$ j\in \{\mathrm{1, 2}, \cdots , k\} $，如果$ {i}_{bj}=1 $，令$ { φ }_{{b}_{j}}={\sigma }_{{x}_{bj}} $，否则令$ {φ }_{{b}_{j}}={g}_{1} $。因此$ {\sigma }_{{x}_{b}^{{i}_{b}}}={e}_{k}({φ }_{b1}, {φ }_{b2}, \cdots , {φ }_{bk})={\mathrm{g}}_{k}^{{\mu }_{{x}_{b}}}={g}_{k}^{m}{h}_{k}^{r} $是明文$ m={x}_{b}^{{i}_{b}} $的密文，其中，$ {\mu }_{{i}_{b}}{=\prod\limits _{j=1}^{k}({x}_{b}^{{2}^{j-1}}+q\delta {r}_{bj})}^{{i}_{bj}} $，$ r=({\mu }_{{x}_{b}}-m)/q\delta , b\in \{\mathrm{1, 2}, \cdots , n\} $，因此，$ {x}_{1}^{{i}_{1}}{x}_{2}^{{i}_{2}}\cdots {x}_{n}^{{i}_{n}} $在协议中所产生的密文为$ {\rho }_{{x}_{1}^{{i}_{1}}{x}_{2}^{{i}_{2}}\cdots {x}_{n}^{{i}_{n}}}={\mathrm{e}}_{n}({\rho }_{{x}_{1}^{{i}_{1}}}, {\rho }_{{x}_{2}^{{i}_{2}}}, \cdots , {\rho }_{{x}_{n}^{{i}_{n}}})={g}_{kn}^{{\mu }_{x1}{\mu }_{x2}\cdots {\mu }_{{x}_{n}}} $，多项式函数值$ f({x}_{1}, $ $ {x}_{2}, \cdots , {x}_{n})=\sum\limits_{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d}{f}_{{i}_{1}{i}_{2}\cdots {i}_{n}{x}_{1}^{{i}_{1}}{x}_{2}^{{i}_{1}}\cdots {x}_{n}^{{i}_{n}}} $对应的密文为$ {\sigma }_{f({x}_{1}, {x}_{2}, \cdots , {x}_{n})}={\prod\limits _{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d}{\sigma }_{{x}_{1}^{{i}_{1}}{x}_{1}^{{i}_{2}}\cdots {x}_{n}^{{i}_{n}}}}^{{f}_{{i}_{1}{i}_{2}\cdots {i}_{n}}} $。

3）验证阶段

（1）计算验证证明$ \pi $。对于$ n $元$ d $次多项式$ F({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $，存在$ {c}_{1}({x}_{2}, {x}_{3}, \cdots , {x}_{n}), {c}_{2}({x}_{3}, {x}_{4}, \cdots , {x}_{n}), \cdots , $ $ {c}_{n}\left({x}_{n}\right) $，因此，用$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $加密算法对$ {c}_{1}({x}_{2}, {x}_{3}, \cdots , {x}_{n}), $ $ {c}_{2}({x}_{3}, {x}_{4}, \cdots , {x}_{n}), \cdots , {c}_{n}\left({x}_{n}\right) $进行加密操作，得到密文如下：

$ {\pi }_{1}={\prod\limits _{{j}_{\mathrm{1, 1}}+{j}_{\mathrm{1, 2}}+\cdots +{j}_{1, n+1}<d}{{g}_{k(n+1)}^{{\lambda }_{\mathrm{1, 1}}, {\lambda }_{\mathrm{1, 2}}, \cdots , {\lambda }_{1, n}{c}_{j, 1}, {c}_{j, 2}, \cdots , {c}_{j, n+1}}}_{}}^{} $

$ {\pi }_{2}={\prod\limits _{{j}_{\mathrm{1, 1}}+{j}_{\mathrm{1, 2}}+\cdots +{j}_{1, n+1}<d}{{g}_{k(n+1)}^{{\lambda }_{\mathrm{1, 1}}, {\tau }_{\mathrm{2, 2}}, \cdots , {\tau }_{\mathrm{1, 2}}{c}_{j, 1}, {c}_{j, 2}, \cdots , {c}_{j, n+1}}}_{}}^{} \\ \vdots \\ {\pi }_{n}={\prod\limits _{{j}_{\mathrm{1, 1}}+\cdots +{j}_{1, n+1}<d}{{g}_{k(n+1)}^{{\lambda }_{\mathrm{1, 1}}, {\tau }_{n, 2}, \cdots , {\tau }_{1, n+1}{c}_{j, 1}, {c}_{j, 2}, \cdots , {c}_{j, n+1}}}_{}}^{} $

(1)

因此，验证证明为$ \pi =({\pi }_{1}, {\pi }_{2}, \cdots , {\pi }_{n}) $。

（2）$ \mathrm{P}\mathrm{u}\mathrm{b}\mathrm{V}\mathrm{e}\mathrm{r}(V{K}_{x}, \rho , \pi ) $。验证方收到$ V{K}_{x}=(F, M), $ $ \rho , \pi $验证下列等式组是否成立：

$ \begin{array}{l}e(F/{g}_{1}^{\rho }, {g}_{k(n+1)})=e({g}_{1}^{{M}_{1}}/{g}_{1}^{{\sigma }_{{x}_{1}}}, {g}_{k(n+1)}^{{\pi }_{1}})\cdot \\ e({g}_{1}^{{M}_{2}}/{g}_{1}^{{\sigma }_{{x}_{2}}}, {g}_{k(n+1)}^{{\pi }_{n}})\cdots e({g}_{1}^{{M}_{n}}/{g}_{1}^{{\sigma }_{{x}_{n}}}, {g}_{k(n+1)}^{{\pi }_{n}})\end{array} $

(2)

如果以上验证成立，则输出计算加密函数值$ \rho $，否则输出$ \perp $。

（3）$ \mathrm{P}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{R}\mathrm{e}\mathrm{t}(V{K}_{x}, P{K}_{x}, \rho ) $。当公开验证者返回计算加密函数值$ \rho $给用户时，用户用私人检索密钥验证计算的真实值$ y=F({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $，且$ y $满足$ {\rho }^{p}=({g}_{kn}^{p}{)}^{y} $，否则公开验证者输出$ \perp $。

4 协议分析

对本文提出的基于隐私保护的可证明安全委托计算协议进行有效性和安全性分析。

4.1 有效性分析

如果协议中服务器返回的计算加密函数值$ \rho $及验证证明$ \pi $能够通过公开验证者的验证，即表明本文协议是正确且有效的。

引理  如果云端服务器是诚实的，则有式（2）成立且$ y=f({x}_{1}, {x}_{2}, \cdots {x}_{n}) $成立。

证明  因为公开验证密钥$ V{K}_{x}=(F, M) $，$ M=({\sigma }_{{s}_{1}}, $ $ {\sigma }_{{s}_{2}}, \cdots , {\sigma }_{{s}_{n}}) $，$ F={g}_{1}^{\mathrm{E}\mathrm{n}\mathrm{c}\left(f\right({s}_{1}, {s}_{2}, \cdots , {s}_{n}\left)\right)} $，$ {\pi }_{1}={g}_{k(n+1)}^{{\lambda }_{\mathrm{1, 1}}, {\lambda }_{\mathrm{1, 2}}, \cdots , {\lambda }_{1, n}{c}_{j, 1}, {c}_{j, 2}, \cdots , {c}_{j, n+1}}= $ $ {g}_{k\left(n+1\right)}^{{c}_{1}({s}_{1}, {s}_{2}, \cdots , {s}_{n})} $，同理可得$ {\pi }_{2}={g}_{k\left(n+1\right)}^{{c}_{2}\left({s}_{2}, {s}_{3}, \cdots , {s}_{n}\right)} $，$ {\pi }_{n}={g}_{k\left(n+1\right)}^{{c}_{n}\left({s}_{n}\right)} $，所以验证式（2）是否成立等同于验证以下等式左右两边是否相等。令$ {C}_{1}={g}_{k(n+1)}^{{c}_{1}({s}_{1}, {s}_{2}, \cdots , {s}_{n})}, {C}_{2}={g}_{k(n+1)}^{{c}_{1}({s}_{2}, {s}_{3}, \cdots , {s}_{n})}, \cdots , {C}_{n}={g}_{k(n+1)}^{{c}_{n}\left({s}_{n}\right)} $，$ {c}_{1}({s}_{1}, {s}_{2}, \cdots , {s}_{n})，$ $ {c}_{1}({s}_{2}, {s}_{3}, \cdots , {s}_{n})，\cdots , {c}_{n}\left({s}_{n}\right) $密文为$ {\sigma }_{{c}_{1}({s}_{1}, {s}_{2}, \cdots , {s}_{n})}, $ $ {\sigma }_{{c}_{1}({s}_{2}, {s}_{3}, \cdots , {s}_{n})}, \cdots , $ $ {\sigma }_{{c}_{n}\left({s}_{n}\right)} $，则验证过程如下：

$ \begin{array}{l}e({g}_{1}^{{M}_{1}}/{g}_{1}^{{\sigma }_{{x}_{1}}}, {g}_{k(n+1)}^{{\pi }_{1}}), e({g}_{1}^{{M}_{2}}/{g}_{1}^{{\sigma }_{{x}_{2}}}, {g}_{k(n+1)}^{{\pi }_{2}}), \cdots , e({g}_{1}^{{M}_{n}}/{g}_{1}^{{\sigma }_{{x}_{n}}}, {g}_{k(n+1)}^{{\pi }_{n}})=\\ e({\mathrm{g}}_{1}^{{\sigma }_{{s}_{1}}}/{g}_{1}^{{\sigma }_{{x}_{1}}}, {g}_{k(n+1)}^{{C}_{1}}), e({\mathrm{g}}_{1}^{{\sigma }_{{s}_{2}}}/{g}_{1}^{{\sigma }_{{x}_{2}}}, {g}_{k(n+1)}^{{C}_{2}}), \cdots , e({g}_{1}^{{\sigma }_{{s}_{n}}}/{g}_{1}^{{\sigma }_{{x}_{n}}}, {g}_{k(n+1)}^{{C}_{n}})=\\ e({g}_{1}, {g}_{k(n+1)}{)}^{{C}_{1}({\sigma }_{{S}_{1}}-{\sigma }_{{x}_{1}})}, e({g}_{1}, {g}_{k(n+1)}{)}^{{C}_{2}({\sigma }_{{S}_{2}}-{\sigma }_{{x}_{2}})}, \cdots , e({g}_{1}, {g}_{k(n+1)}{)}^{{C}_{n}({\sigma }_{{S}_{n}}-{\sigma }_{{x}_{n}})}=\\ e({g}_{1}, {g}_{k(n+1)}{)}^{{\sigma }_{{c}_{1}({s}_{1}, {s}_{2}, \cdots , {s}_{n})({s}_{1}-{x}_{1})}}, e({g}_{1}, {g}_{k(n+1)}{)}^{{\sigma }_{{c}_{2}({s}_{2}, {s}_{3}, \cdots , {s}_{n})({s}_{2}-{x}_{2})}}, \cdots , e({g}_{1}, {g}_{k(n+1)}{)}^{{\sigma }_{{c}_{n}\left({s}_{n}\right)({s}_{n}-{x}_{n})}}=\\ e({g}_{1}, {g}_{k(n+1)}{)}^{{\sigma }_{\left[f\right({s}_{1}, {s}_{2}, \cdots , {s}_{n})-f({x}_{1}, {x}_{2}, \cdots , {x}_{n})]}}=e({g}_{1}^{{\sigma }_{\left[f\right({s}_{1}, {s}_{2}, \cdots , {s}_{n})-f({x}_{1}, {x}_{2}, \cdots , {x}_{n})]}}, {g}_{k(n+1)})=e(F/{g}_{1}^{\rho }, {g}_{k(n+1)})\end{array} $

因此，如果云端服务器是诚实的，则式（2）成立。又因为有如下等式成立：

$ \begin{array}{l}{\mu }_{{x}_{b}}=\prod\limits _{j=1}^{k}({x}_{b}^{{2}^{j-1}}+q\delta {r}_{{b}_{j}}{)}^{{i}_{{b}_{j}}}，r=\frac{1}{q\delta }({\mu }_{{x}_{b}}-m)\\ b\in \{\mathrm{1, 2}, \cdots , m\}\end{array} $

$ \begin{array}{l}p{\mu }_{{x}_{1}}{\mu }_{{x}_{2}}\cdots {\mu }_{{x}_{n}}\equiv p{x}_{1}^{\sum\limits_{j-1}^{k}{2}^{j-1}{i}_{1, j}}p{x}_{2}^{\sum\limits _{j-1}^{k}{2}^{j-1}{i}_{2, j}}\cdots p{x}_{n}^{\sum\limits_{j-1}^{k}{2}^{j-1}{i}_{n, j}}\equiv \\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\qquad\qquad p{x}_{1}^{{i}_{1}} \, p{x}_{2}^{{i}_{2}}\cdots p{x}_{n}^{{i}_{n}} \, \mathrm{m}\mathrm{o}\mathrm{d} \, N\end{array} $

$ {\rho }^{p}=\prod\limits _{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d}{\rho }_{{x}_{1}^{{i}_{1}}{x}_{2}^{{i}_{2}}\cdots {x}_{n}^{{i}_{n}}}^{p{f}_{{i}_{1}{i}_{2}\cdots {i}_{n}}}=\prod\limits _{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d}{g}_{k(n+1)}^{p{f}_{{i}_{1}{i}_{2}\cdots {i}_{n}}{\mu }_{{x}_{1}}{\mu }_{{x}_{2}}\cdots {\mu }_{{x}_{n}}}{=}_{} \\ \qquad\qquad \prod\limits _{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d}{g}_{k(n+1)}^{p{f}_{{i}_{1}{i}_{2}\cdots {i}_{n}}{x}_{1}^{{i}_{1}}{x}_{2}^{{i}_{2}}\cdots {x}_{n}^{{i}_{n}}}=({g}_{kn}^{p}{)}^{f({x}_{1}, {x}_{2}, \cdots , {x}_{n})} $

因此，若式（2）成立，则$ y=f({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $也成立，即证明本文提出的基于隐私保护的可证明安全委托计算协议是正确且有效的。如果存在多元多项式函数，本文协议能够在可公开验证条件下达到隐私保护和可证明安全的目标。

4.2 安全性分析

定理1  在MDH困难性数学问题假设下，本文提出的隐私保护下可公开验证的委托计算协议是可证明安全的。

证明  假设PVMPC方案是不安全的，那么就存在一个PPT敌手A能以不可忽略的概率$ {ε }_{1} $欺骗公开验证者接受一个错误的加密函数值。因此，就可以调用子程序A构建一个PPT模拟器S，以不可忽略的概率$ {ε }_{1} $来解决$ \left(k\right(n+1\left)\right) $-MDH困难问题，即A的目标是在收到$ (p, q, {g}_{1}^{\overline{\rho }}, {g}_{1}^{{\rho }^{\mathrm{*}}}, {g}_{1}^{\overline{\rho }-{\rho }^{\mathrm{*}}}) $之后，S能够计算出$ e({g}_{1}, {g}_{k(n+1)}^{\overline{\rho }-{\rho }^{\mathrm{*}}}) $。游戏开始之前，发送一个向量$ (p, q, {g}_{1}^{s}, {g}_{1}^{{s}^{2}}, \cdots , {g}_{1}^{{s}^{d}}) $。S模拟A过程如下：

1）模拟器S生成系统参数。随机选择一个$ n $元的$ d $次多项$ f({x}_{1}, {x}_{2}, \cdots , {x}_{n})\in {\mathbb{Z}}_{N}\left[x\right] $，运行群生成器得：$ {\mathit{\Gamma}} =\mathrm{ }(N, {G}_{1}, {G}_{2}, \cdots , {G}_{k(n+1)}, e, {g}_{1}, {g}_{2}, \cdots , {g}_{k(n+1)})\leftarrow G({1}^{\lambda }, k(n+1\left)\right) $，$ k=⌈\mathrm{l}\mathrm{g}(d+1) $，$ {g}_{1}\leftarrow {G}_{1} $。令$ {s}_{i}=s+{x}_{i}^{\mathrm{*}} $，$ i\in \{\mathrm{1, 2}, \cdots , n\} $。由于S知道$ (p, q, {g}_{1}^{s}, {g}_{1}^{{s}^{2}}, \cdots , {g}_{1}^{{s}^{d}}) $和$ ({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}) $，因此S可以计算以下结果：

$ \begin{array}{l}{\sigma }_{{s}_{1}}=({\sigma }_{{s}_{11}}, {\sigma }_{{s}_{12}}, \cdots , {\sigma }_{{s}_{1k}})=({g}_{1}^{{s}_{1}}, {g}_{1}^{{s}_{1}^{2}}, \cdots , {g}_{1}^{{s}_{1}^{{2}^{k-1}}})\\ {\sigma }_{{s}_{2}}=({\sigma }_{{s}_{21}}, {\sigma }_{{s}_{22}}, \cdots , {\sigma }_{{s}_{2k}})=({g}_{1}^{{s}_{2}}, {g}_{1}^{{s}_{2}^{2}}, \cdots , {g}_{1}^{{s}_{2}^{{2}^{k-1}}})\\ \vdots \\ {\sigma }_{{s}_{n}}=({\sigma }_{{s}_{n1}}, {\sigma }_{{s}_{n2}}, \cdots , {\sigma }_{{s}_{nk}})=({g}_{1}^{{s}_{n}}, {g}_{1}^{{s}_{n}^{2}}, \cdots , {g}_{1}^{{s}_{n}^{{2}^{k-1}}})\end{array} $

(3)

随机获得$ u\leftarrow {G}_{1} $，通过计算$ h={u}^{q} $，将$ PK=(\Gamma , {g}_{1}, h;{\sigma }_{{s}_{1}}, {\sigma }_{{s}_{2}}, \cdots , {\sigma }_{{s}_{n}};f) $发送给敌手A。

2）询问阶段。敌手A对S进行多次重复询问，A发送函数的输入$ ({x}_{1}, {x}_{2}, \cdots , {x}_{n}) $给S，S选择一个$ {r}_{j}\leftarrow {\mathbb{Z}}_{N} $，然后计算$ {\sigma }_{{x}_{bj}}={g}_{1}^{{x}_{b}^{{2}^{j-1}}}{h}^{{r}_{j}}, j\in \{\mathrm{1, 2}, \cdots , k\} $，其中$ k=⌈\mathrm{l}\mathrm{g}(d+1) $。输出$ {\sigma }_{{x}_{b}}=({\sigma }_{{x}_{b1}}, {\sigma }_{{x}_{b2}}, \cdots , {\sigma }_{{x}_{bk}}) $，$ b\in \{\mathrm{1, 2}, \cdots , n\} $，最终S输出$ \sigma =({\sigma }_{{x}_{1}}, {\sigma }_{{x}_{2}}, \cdots , {\sigma }_{{x}_{n}}) $给敌手A。

3）挑战阶段。S将$ ({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}) $的加密结果$ {\sigma }^{\mathrm{*}}=({\sigma }_{{x}_{1}^{\mathrm{*}}}, {\sigma }_{{x}_{2}^{\mathrm{*}}}, \cdots , {\sigma }_{{x}_{n}^{\mathrm{*}}}) $发送给A，A返回输入值$ ({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}) $的计算结果及验证证明$ (\overline{\rho }, \overline{{\pi }_{1}}, \overline{{\pi }_{2}}, \cdots , \overline{{\pi }_{n}}) $，且解密加密函数值$ \overline{\rho } $后有$ \overline{y}\ne f({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}) $，由$ {\rho }^{\mathrm{*}}=\mathrm{E}\mathrm{n}\mathrm{c}\left(f\right({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}\left)\right) $且解密$ {\rho }^{\mathrm{*}} $，有$ {y}^{\mathrm{*}}=f({x}_{1}^{\mathrm{*}}, {x}_{2}^{\mathrm{*}}, \cdots , {x}_{n}^{\mathrm{*}}) $。由假设可知$ \overline{\rho }\in \{{\rho }^{\mathrm{*}}, \perp \} $以不可忽略的概略$ ε $发生，那么有$ (\overline{\rho }, \overline{{\pi }_{1}}, \overline{{\pi }_{2}}, \cdots , \overline{{\pi }_{n}}) $和$ ({\rho }^{\mathrm{*}}, {\pi }_{1}^{\mathrm{*}}, {\pi }_{2}^{\mathrm{*}}, \cdots , {\pi }_{n}^{\mathrm{*}}) $满足式（2），即式（4）成立，将式（4）和式（5）相除可得式（6），由于$ {s}_{i}=s+{x}_{i}^{\mathrm{*}}, i\in \{\mathrm{1, 2}, \cdots , n\} $，由$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $支持无限次的加法同态性质可得$ {\sigma }_{{s}_{i}}-{\sigma }_{{{x}_{i}}^{\mathrm{*}}}={\sigma }_{s}=t $，因此式（6）变形为式（7），等价于式（8）成立。

$ e(F/{g}_{1}^{\overline{\rho }}, {g}_{k(n+1)})=e({g}_{1}^{{M}_{1}}/{g}_{1}^{{\sigma }_{{x}_{1}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\stackrel{-}{\pi }}_{1}})e({g}_{1}^{{M}_{2}}/{g}_{1}^{{\sigma }_{{x}_{2}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\stackrel{-}{\pi }}_{n}})\cdots e({g}_{1}^{{M}_{n}}/{g}_{1}^{{\sigma }_{{x}_{n}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\stackrel{-}{\pi }}_{n}}) $

(4)

$ e(F/{g}_{1}^{{\rho }^{\mathrm{*}}}, {g}_{k(n+1)})=e({g}_{1}^{{M}_{1}}/{g}_{1}^{{\sigma }_{{x}_{1}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\pi }_{1}^{\mathrm{*}}})e({g}_{1}^{{M}_{2}}/{g}_{1}^{{\sigma }_{{x}_{2}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\pi }_{2}^{\mathrm{*}}})\cdots e({g}_{1}^{{M}_{n}}/{g}_{1}^{{\sigma }_{{x}_{n}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\pi }_{n}^{\mathrm{*}}}) $

(5)

$ e({g}_{1}^{{\rho }^{\mathrm{*}}-\overline{\rho }}, {g}_{k(n+1)})=e({g}_{1}^{{M}_{1}-{\sigma }_{{x}_{1}^{\mathrm{*}}}}, {g}_{k(n+1)}^{{\stackrel{-}{\pi }}_{1}-{\pi }_{1}^{\mathrm{*}}})e({g}_{1}^{{M}_{2}-{\sigma }_{{x}_{2}^{\mathrm{*}}}}, {g}_{k(n+1)}^{\overline{{\pi }_{2}}-{\pi }_{2}^{\mathrm{*}}})\cdots e({g}_{1}^{{{}^{{M}_{n}-}}^{{\sigma }_{{x}_{n}^{\mathrm{*}}}}}, {g}_{k(n+1)}^{\overline{{\pi }_{n}}-{\pi }_{n}^{\mathrm{*}}}) $

(6)

$ e({g}_{1}^{{\rho }^{\mathrm{*}}-\overline{\rho }}, {g}_{k(n+1)})=e({g}_{1}^{t}, {g}_{k(n+1)}^{{\stackrel{-}{\pi }}_{1}-{\pi }_{1}^{\mathrm{*}}})e({g}_{1}^{t}, {g}_{k(n+1)}^{\overline{{\pi }_{2}}-{\pi }_{2}^{\mathrm{*}}})\cdots e({g}_{1}^{t}, {g}_{k(n+1)}^{\overline{{\pi }_{n}}-{\mathrm{\pi }}_{n}^{\mathrm{*}}}) $

(7)

$ e({g}_{1}^{{\rho }^{\mathrm{*}}-\overline{\rho }}, {g}_{k(n+1)})=e({g}_{1}^{t}, {g}_{k(n+1)}^{\sum\limits_{l-1}^{n}\overline{{\pi }_{l}}-{\pi }_{l}^{\mathrm{*}}})={g}_{k(n+1)+1}^{t\sum\limits_{l-1}^{n}\overline{{\pi }_{l}}-{\pi }_{l}^{\mathrm{*}}} $

(8)

由此说明模拟器S能够以不可忽略的概略$ ε $解决数学难题$ \left(k\right(n+1\left)\right)-\mathrm{M}\mathrm{D}\mathrm{H} $，这与假设$ \left(k\right(n+1\left)\right)-\mathrm{M}\mathrm{D}\mathrm{H} $是困难问题相矛盾，因此，假设不成立，则表明构建的PVMPC方案是安全且隐私的。

5 性能分析与实验仿真 5.1 性能分析

$ f({x}_{1}, {x}_{2}, \cdots , {x}_{n})= $ $ \sum\limits_{{i}_{1}+{i}_{2}+\cdots +{i}_{n}\le d} $ $ {f}_{{i}_{1}{i}_{2}\cdots {i}_{n}{{x}_{1}}^{{i}_{1}}{{x}_{1}}^{{i}_{2}}\cdots {{x}_{n}}^{{i}_{n}}} $这个$ n $元$ d $次多项式最多有$ {（d+1)}^{n} $个单项式，如果客户端直接计算，则每一项需要进行$ O\left(n\right) $次指数运算，共需要进行$ O\left({d}^{n}n\right) $次指数运算。当计算任务委托给服务器时，为了保护输入信息的隐私性，用户需要用$ \mathrm{B}\mathrm{G}{\mathrm{N}}_{k(n+1)} $加密方案计算出$ 2n\mathrm{l}\mathrm{g}⌈d+1⌉ $多个密文$ \sigma $。综上分析可得，本文提出的基于隐私保护的公开可验证委托计算协议中各阶段的效率，如表 1所示。本文协议与已有委托计算协议的通信复杂度和可证明安全性对比如表 2所示。

5.2 实验仿真

为更清晰地体现本文协议的效率优势，对本文协议进行仿真实现。用户和云服务器的运行环境分别为Intel^® Core^TM i3 Processor（2.4 GH，4 GB内存）和Intel i5 Processor（3.0 GHz，8 GB内存）。对$ n $元$ d $阶多项式进行实验模拟时，实验的安全参数设置为安全参数$ \left|\lambda \right|={30}_{}\mathrm{b}\mathrm{i}\mathrm{t} $，$ n=4 $，多项式的次数设为$ d=43 $和$ d=127 $。

分别对四元43次多项式和四元127次多项式进行模拟实验，仿真委托计算和直接计算分别与群数阶$ N $和|f|的关系。设置外包任务输入$ {x}_{i} $的长度$ l=30 $ bit，多项式的项数|f|=1 000，5 000，10 000，15 000，20 000，25 000，实验结果如图 2所示。

由仿真结果可知，本文协议中用户的计算消耗量远小于用户直接计算函数的计算量，由此表明本文方案是有效的。

6 结束语

为实现云计算中对计算结果的公开可验证性、敏感数据的隐私性并抵抗对恶意用户偏离协议的行为，本文基于全同态加密技术和多线性映射方案的优势，设计一个适用于多元多项式函数的委托计算协议，其在MDH困难性问题假设下满足可证明安全性。性能分析和实验仿真结果验证了该协议的有效性和隐私保护性。本文工作是在双线性映射方案中保证委托计算协议的安全隐私性，下一步将利用其他加密技术研究更高效的委托计算方案。