基于格密码的矩阵乘可验证计算方案

陈泽

(四川大学网络空间安全学院，成都610207)

0 引言

云计算可以协调大量计算机资源，从而提供给客户强大的存储和计算能力，大大提高计算资源的利用率。然而云计算也带来了新的安全问题：云平台可能错误执行客户的应用程序或者安全性无法保证，甚至其自身存在恶意行为，这些都可能侵害到客户数据的隐私性以及完整性以及计算结果的正确性。传统的方法，例如审计依赖于发生错误的频率，而冗余计算无法解决服务器之间相互串通的情况[1]。相比之下，可验证计算协议能够为用户提供一种无需重新本地运行在服务端所部署的程序也可验证结果正确与否的途径，且错误结果通过验证的概率是几乎可以忽略的。然而，虽然可计算协议在近些年来已经有了很大的进展，但适用于任何场景的可验证计算协议的性能开销仍与可应用阶段存在很大的距离。另外，随着同态加密技术的发展，基于同态加密算法构建一个可实现的适用于特定场景的可验证计算协议已成为可能。

矩阵乘在科学以及工程领域中十分普遍。对两个l×l的矩阵而言，传统的算法计算其乘积的复杂度为O(l3)。随着数据量的增大，l可能会达到几万甚至更高，而此时计算其乘积的空间以及时间开销都是个人计算能力难以承受的。本文在现有的基于格理论的同态加密算法基础上，构建了一个具有隐私保护的用于矩阵乘的可验证计算协议。由于格理论上的问题在量子计算机下仍是难解的，本文的协议具有抗量子分析的安全性以及隐私性，且本地的计算开销远小于直接计算矩阵乘所造成的开销。……