浅析基于可验证计算的可信云计算优秀论文
1 引 言
云计算作为一种新兴的网络计算商业服务模式，使得用户可以随时在远端的云服务器存储数据和运行程序.但这种新兴的计算模式在给用户带来诸多便利性的同时，也带来了一些新的安全挑战.用户可能担心云计算平台本身的安全性，比如云平台漏洞和错误配置、管理员的恶意行为等等，而这都可能直接导致用户数据的完整性和隐私性受到危害，导致用户应用程序无法正确执行.这就产生了一个问题：用户如何相信云提供商执行的程序结果是正确的?如何确保存储在远端的数据的完整性和私密性?检测远程服务器返回的结果是否正确的传统解决方案有以下几种：
(1)采用审计的方法，即随机选取服务器执行的一小部分程序进行验证，这就可能发生错误执行的程序没有被服务器验证的情况，所以说这种方法必须假设错误执行的程序的发生频率是很小的;
(2)利用可信硬件和远程证明来保证远程服务器运行的程序是正确的，但是这种方法必须假设云提供商是完全可信的，由于硬件基础设施是在云提供商的控制之下，如果云提供商内部人员恶意控制了可信硬件(如CPU、TPM)，就无法保障云提供商运行的程序的机密性和可验证性.而且还需要假设存在一个可信链，而运行时可信链的建立在可信计算领域依然是一个难题.事实上，在实际的云计算应用场景中这两个假设通常是无法满足的.在云计算场景中，用户无法完全相信云提供商，即使用户出于声誉的考虑相信云提供商本身，也无法相信其内部管理人员;
(3)采用冗余计算的方法，用户可以让多个远程服务器把相同的程序执行多次，然后检测他们返回的结果是否一致.但这在云计算中也是行不通的，云计算中的软硬件平台配置通常是相同的，而这违背了冗余计算中错误必须是不相关的假设，且远程服务器很容易窜通，合谋返回一个错误的程序执行结果.
而可证明数据持有(Provable Data Possession，PDP)方法和可恢复证明(Proof of Retrievability，POR)方法可以用来确保存储在远端的数据的完整性，避免云提供商删除和篡改数据.相比PDP方法，POR除了能确保数据的完整性之外，还能确保数据的可恢复性，但是PDP和POR无法确保在云提供商端执行的程序的正确性.另一方面，基于复杂性理论的交互式证明系统(Interactive Proof system，IPs)和概率可验证证明系统(Probabilistically Checkable Proof system，PCPs)以及密码学理论构造的可验证计算协议能以很高的正确率检测出远程服务器返回的程序执行结果是否正确并且不需要对远程服务器(云提供商)做任何假设.可验证计算协议致力于设计验证者与证明者之间的协议，协议允许在计算能力上相对较弱的验证者(如云计算中的用户)将其程序发送到一个计算能力强大的，但不可信的证明者(例如云提供商)，并要求证明者执行其发送的程序.所设计的协议应确保证明者不但返回程序的执行结果给验证者，并且使得验证者相信这个程序执行结果是正确的.其主要目标是使得服务器在发送程序执行结果的同时提供程序正确执行的证据，而用户验证证据的过程必须要比用户自己执行程序的开销小(当然有时由于资源比如存储的限制，用户根本无法自己执行程序，在这种情况下是指和假设用户有足够的资源执行程序时的开销相比要小)。
2 问题描述和协议设计原则问题描述：
验证者V把程序f和输入变量x发送给证明者P，P计算f(x)，并把f(x)赋值给变量y，返回y给V，然后V 和P 以如下方式进行交互：
(1)如果y=f(x)，那么P 应该能向V 证明y的正确性，即使得V 接受y.其中，证明可以通过回答V 提出的一些问题完成，也可以通过给V 提供一个证书完成.
(2)如果y≠f(x)，V 能以很高的概率拒绝接受y.可验证计算协议的设计必须满足3个基本原则：(1)协议应该使得验证者的开销比其在本地执行程序f(x)的开销要低，但可以允许证明者为达到协议的目标产生合理的开销，因为提供运行程序的正确性保障本身就需要用户付出一定的代价，在云计算实际场景中，表现为云提供商可能会对需要提供程序正确执行证据的用户收取额外的费用;
(2)不能假设证明者完全遵守协议，也就是说证明者可能是恶意的，这和云计算中不能假设云提供商是完全可信的实际场景也是十分吻合的;
(3)f 应该是通用程序，然而在具体的协议设计中，可能需要对f 表示的程序做一些假设，从而通过限制可验证计算协议适用的应用程序种类使得协议的性能达到实际应用场景的要求，但是可验证计算协议的设计原则依然是尽量能表示通用程序.
通常的安全保障工具比如说病毒检测关注的都是不正确的行为的识别和防范，可验证计算协议则有所不同，其不关心证明者可能的不正确行为，比如犯了什么错误，出现了什么故障等等，而只关心其执行程序的结果是否是正确的，却无法推测程序错误执行的原因.这和云计算中用户对于程序执行的要求也是相符的.
3 协议流程和关键
3.1 可验证计算协议流程
可验证计算协议的流程主要包括编译处理和证明系统，具体流程如图1所示.首先是编译处理阶段，验证者V 和证明者P 将高级语言(比如C 语言)编写的程序转换成一组布尔电路集(根据协议的不同，也可以是其他计算模型比如算术电路集或者约束集等).接下来，P 和V 进行一系列协议交互，不失一般性，这里用布尔电路集C表示程序f.V 把输入变量x传输给P，P 计算C，输出程序执行结果y和C正确执行的一组轨迹{C，x，y｝给V，{C，x，y｝也称为C的一个可满足性赋值z.其中，C正确执行的一组轨迹是指C的输入线路被赋值为x，输出线路被赋值为f(x)时，电路集中所有电路门的赋值集合.在程序执行的过程中，证明者P 获得了正确计算电路的执行轨迹{C，x，y｝.如果P 声称的输出y是不正确的，即y不等于f(x)，那么对于{C，x，y｝，就不可能存在一个有效的执行轨迹(电路C正确计算的一个证明).因此，如果P 能够对{C，x，y｝构建一个有效的执行轨迹，那么就一定能使得验证者V 相信它返回的结果是正确的.显然，电路正确计算过程中的各个门的赋值本身就能说明存在有效的执行轨迹.但是，如果需要V 依次验证所有电路门在计算电路过程中的值，进而确定程序是否正确执行，这个工作量和V 本地执行f 是相当的，这就违背了可验证计算协议设计的基本原则.所以，图中第步就需要证明者对程序执行轨迹编码，生成一个很长的字符串，并使得不同的执行轨迹生成的编码在所有不同的位置的取值是不相同的.这样，验证者就可以通过检查随机选择的编码的特定的位置的取值，来验证执行轨迹的有效性，进而对返回的结果采取特定的测试来确定证明者返回的结果是否正确.
3.2 可验证计算协议的理论依据
理解可验证计算协议的原理和流程关键在于理解两个等价关系，如3.1节所述，可验证计算协议的流程主要包括编译处理和证明系统.其中，编译处理阶段，编译器完成高级语言程序到电路集或者约束集(可以看做方程组)等计算模型的转化，其实现的理论依据在于等价关系：程序执行的正确性等价于电路集或者约束集可满足问题.