一种实现大尺度矩阵乘法安全高效的可验证外包计算方法、客户端及云计算系统

摘要

本发明涉及云计算技术领域，公开了一种实现大尺度矩阵乘法安全高效的可验证外包计算方法、客户端及云计算系统。通过本发明创造，提供了一种适用于计算大尺度矩阵乘法结果的新外包计算协议，可使拥有较少计算资源/计算能力弱的客户端在面对大尺度矩阵乘运算时，能够在保证敏感的矩阵数据不被泄露的前提下，通过较少的计算开销将矩阵的乘运算外包给拥有大量计算资源的云服务器，并提供给客户关于矩阵乘结果的安全可靠的验证，从而满足外包计算在安全性(可验证性)、隐私性以及高效性的所存在的需求，便于实际应用和推广。与现有相关协议相比，其验证方案通过猜测结果的概率更低，且不依赖于原始明文矩阵和随机验证次数；验证效率也更高。

说明书

技术领域

本发明属于云计算技术领域，具体涉及一种实现大尺度矩阵乘法安全高效的可验证外包计算方法、客户端及云计算系统。

背景技术

随着云服务相关技术的快速发展和成熟，云计算在各个领域都有着越来越多的作用。云计算将大量计算机资源协调在一起，从而可以向客户提供强大的计算能力，大大提高计算资源的利用率。外包计算是云计算中一个很重要的应用，它可以为计算资源受限的客户免去繁重的计算任务并帮助客户完成该计算任务。但是，这项技术也带来了一些特定的问题需要解决，例如客户敏感数据的隐私性以及返回结果的正确性。

矩阵在科学工程等众多领域中均有着普遍且重要的应用，其中矩阵乘法运算的普遍性尤为突出。对于两个m×m的矩阵而言，传统计算方法的计算复杂度为O(m³)，目前已有的用于矩阵乘的算法已经可以将计算复杂度降到O(m^2.373)(现有文献1：M.Atallah>20的情况下，使用现有文献2(J.Laderman,V.Pan,and>2.775)，然而，当m在达到几万、几十万甚至更高的数量级时，计算资源受限的客户端要完成这样的计算任务所需的时间依旧是很长的。外包计算可以帮助客户节省这种繁重计算所花费的时间，但在将矩阵乘运算外包给云端服务器计算时，有如下3个方面的问题需要解决。

(1)安全性(可验证性)：客户端应当能够检验自己得到的结果是否正确。一方面，由于硬件的故障或者软件的漏洞等意外原因，计算结果可能是错误的；另一方面，敌对的或者自私的云端可能会有意将错误注入到计算中，或者发送回一个似乎正确的结果，来减少对计算资源的使用和成本，从而获得更多的利润。

(2)数据的隐私性：用户的数据可能是敏感且贵重的，但在外包计算过程中，这些数据的输入和结果的输出会被对方出于好奇或者有预谋地获得。比如一些公司的商业机密，或者研究所内重要的观察数据，云端可以将这些数据卖给客户的竞争对手，或者存储起来以备后用。这些都属于外包计算的隐私性问题。虽然数据的安全性对外包计算至关重要，数据的隐私性对个人和商业公司来说，也是至关重要的。

(3)高效性：外包计算协议应该能够保证本地的计算量和开销低于直接计算矩阵乘法所需的开销，也就是外包计算协议所需的本地计算量需要低于O(m^2.775)，否则就失去了外包计算本身的意义。

基于上述原因，设计一个具有安全性(可验证性)、隐私性以及高效性的大尺度矩阵乘法外包计算协议是十分有意义的。

发明内容

为了解决现有关于大尺度矩阵乘法运算的外包计算协议在安全性(可验证性)、隐私性以及高效性的所存在的需求，本发明目的在于提供一种实现大尺度矩阵乘法安全高效的可验证外包计算方法、客户端及云计算系统。

本发明所采用的技术方案为：

一种实现大尺度矩阵乘法安全高效的可验证外包计算方法,包括如下步骤：

S101.采用单向陷门函数生成公私密钥对其中，A表示公钥矩阵且为私钥矩阵且q表示大于2的素数，表示对中每一个元素求关于q的余数，Z_q∈{0,1,2,…,q-1}，m为不小于1000的正整数，n为正整数且n＜＜m；

S102.在导入待乘法运算的第一明文矩阵B₁和第二明文矩阵B₂后，先分别得到对应的第一明文矩阵集合和第二明文矩阵集合然后采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第一明文矩阵集合中的各个矩阵分别进行加密，得到对应的第一密文矩阵集合以及采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第二明文矩阵集合中的各个矩阵分别进行加密，得到对应的第二密文矩阵集合其中，p表示大于2的正整数，Z_p∈{0,1,2,…,p-1}，并按照如下公式得到所述第一明文矩阵集合和所述第二明文矩阵集合

式中，θ₁和θ₂均为对角矩阵且θ₁,θ₁∈Z^m×m，Z表示整数集合，I为单位矩阵；

S103.将所述第一密文矩阵集合和所述第二密文矩阵集合上传至云计算服务器，并在经过外包计算方式的云计算后，获取如下反馈矩阵Φ：

式中，

S104.采用所述私钥矩阵及逆矩阵对所述反馈矩阵Φ进行解密，得到如下待验证矩阵RT：

式中，()modp表示求关于p的余数，()<mod>q表示求在区间范围之间的映射值，

S105.检查RT₀₀是否等于RT₁₁+RT₁₂+RT₂₁+RT₂₂，若发现相等，则将RT₀₀作为所述第一明文矩阵B₁与所述第二明文矩阵B₂的乘法运算结果，否则判定验证失败，拒绝接受外包计算结果。

优化的，在所述步骤S102之前，还随机地选取得到任意两元素均不相等的第一正整数序列{u₁,u₂,u₃,…,u_k},k＜m和第二正整数序列{v₁,v₂,v₃,…,v_l},l＜m，然后按照如下公式计算对角矩阵θ₁和对角矩阵θ₂中的对角元素值：

式中，δ(x)为关于变量x的狄拉克函数，当且仅当x为零时为1，其它情况为零；

在所述步骤S105之前，还根据所述第一正整数序列和所述第二正整数序列检查RT₀₀中的元素除第u₁,u₂,u₃,…,u_k行和第v₁,v₂,v₃,…,v_l列以外是否全部为零，若发现全部为零，则执行步骤S105，否则判定验证失败，拒绝接受外包计算结果。

优化的，所述步骤S101包括如下：

S1011.获取函数参数：其中，σ＞0，

S1012.按照如下方式构造对应所述公钥矩阵A的转置矩阵A^T和对应所述私钥矩阵的转置矩阵

式中，A₁为所述转置矩阵A^T的第一矩阵列分块且A₁随机生成且对应的定义格满足Λ^⊥(A₁)＝{z∈Z^m|(A₁z)modq＝0}，()modq表示求关于q的余数，A₂为所述转置矩阵A^T的第二矩阵列分块且A₂＝-A₁(R+G)；

矩阵其中，第i个矩阵列分块G⁽ⁱ⁾的列数h_i,i为在对应Λ^⊥(A₁)的埃尔米特矩阵H中第i行且第i列的元素，表示对变量x进行向上取整，在第i个矩阵列分块G⁽ⁱ⁾中第j列元素j∈[1,w_i]，e_i表示第i个矩阵列分块G⁽ⁱ⁾所对应的标准基向量且满足特别矩阵列分块M的列宽度表示对变量x进行向下取整，特别矩阵列分块M仅在前d行存在非零元素，d＝(1+σ)nlgq，前d行元素随机取自具有个元素的哈达玛矩阵且任意两个元素不相等；

矩阵其中，第i个矩阵行分块在第i个矩阵行分块P⁽ⁱ⁾中第j列元素是的二进制表示，h_i,j为在对应Λ^⊥(A₁)的埃尔米特矩阵H中第i行且第j列的元素，为在矩阵中第i行且第j列的元素，I为单位矩阵，有

矩阵其中，diag()为对角矩阵构造函数，为对应第i个矩阵列分块G⁽ⁱ⁾的幺模上三角矩阵且在矩阵中第行且第列的元素

矩阵R的前d行元素独立地随机取自整数集合{-1,0,1}，其余行的元素全部为零，其中，针对数值0的随机取值概率为50％，针对数值-1和数值1的随机取值概率分别为25％；

S1013.输出对应转置矩阵A^T的所述公钥矩阵A和对应转置矩阵的所述私钥矩阵

具体的，所述步骤S1011包括如下：

在导入安全参数λ后，根据所述安全参数λ分别计算得到函数参数σ＝f_σ(λ)，n＝f_n(λ)，其中，f_σ(λ)、f_n(λ)和分别为关于安全参数λ的预设函数。

进一步具体的，在所述步骤S101中，按照如下方式对素数q进行取值：

式中，c＝f_c(λ),c＞0，f_c(λ)为关于安全参数λ的预设函数，ω()为满足的函数。

优化的，在所述步骤S102中，针对所述第一明文矩阵集合和所述第二明文矩阵集合中的各个矩阵B，按照如下方式进行加性同态加密：

S1021.获取具有n×m个元素的秘密矩阵S和具有m×m个元素的误差矩阵X；

S1022.按照如下公式计算与矩阵B对应的密文矩阵C：

C＝(AS+pX+B)<mod>q

式中，A为公钥矩阵，()<mod>q表示求在区间范围之间的映射值。

进一步优化的，在所述步骤S1021中，按照如下方式(1)～(3)中的任意一种选取所述秘密矩阵S和所述误差矩阵X：

(1)所述秘密矩阵S均匀地随机取自所述误差矩阵X均匀地随机取自{-1,0,1}^m×m或{0,1}^m×m；

(2)所述秘密矩阵S均匀地随机取自{-1,0,1}^n×m，所述误差矩阵X均匀地随机地取自{-1,0,1}^m×m或(Ψ_β(q))^m×m，其中，Ψ_β(q)为Z_q上的高斯分布，β为高斯分布参数；

(3)所述秘密矩阵S均匀地随机取自{0,1}^n×m，所述误差矩阵X均匀的随机取自(Ψ_β(q))^m×m，其中，Ψ_β(q)为Z_q上的高斯分布，β为高斯分布参数。

具体的，在所述步骤S1021之前包括如下：

在导入安全参数λ后，根据所述安全参数λ计算得到高斯分布参数β＝f_β(λ)，其中，f_β(λ)为关于安全参数λ的预设函数。

本发明所采用的另一种技术方案为：

一种客户端，用于执行如前所述实现大尺度矩阵乘法安全高效的可验证外包计算方法，并包括有密钥生成模块、明文加密模块、收发模块、密文解密模块和结果验证模块；

所述密钥生成模块，用于采用单向陷门函数生成公私密钥对其中，A表示公钥矩阵且为私钥矩阵且q表示大于2的素数，表示对中每一个元素求关于q的余数，Z_q∈{0,1,2,…,q-1}，m为不小于1000的正整数，n为正整数且n＜＜m；

所述明文加密模块，通信连接所述密钥生成模块，用于在导入待乘法运算的第一明文矩阵B₁和第二明文矩阵B₂后，先分别得到对应的第一明文矩阵集合和第二明文矩阵集合然后采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第一明文矩阵集合中的各个矩阵分别进行加密，得到对应的第一密文矩阵集合以及采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第二明文矩阵集合中的各个矩阵分别进行加密，得到对应的第二密文矩阵集合其中，p表示大于2的正整数，Z_p∈{0,1,2,…,p-1}，并按照如下公式得到所述第一明文矩阵集合和所述第二明文矩阵集合

式中，θ₁和θ₂均为对角矩阵且θ₁,θ₁∈Z^m×m，Z表示整数集合，I为单位矩阵；

所述收发模块，通信连接所述明文加密模块，用于将所述第一密文矩阵集合和所述第二密文矩阵集合上传至云计算服务器，并在经过云计算后，获取如下反馈矩阵Φ：

式中，

所述密文解密模块，通信连接所述收发模块，用于采用所述私钥矩阵及逆矩阵对所述反馈矩阵Φ进行解密，得到如下待验证矩阵RT：

式中，()modp表示求关于p的余数，()<mod>q表示求在区间范围之间的映射值，

所述结果验证模块，通信连接所述密文解密模块，用于检查RT₀₀是否等于RT₁₁+RT₁₂+RT₂₁+RT₂₂，若发现相等，则将RT₀₀作为所述第一明文矩阵B₁与所述第二明文矩阵B₂的乘法运算结果，否则判定验证失败，拒绝接受外包计算结果。

本发明所采用的另一种技术方案为：

一种云计算系统，包括云计算服务器和如前所述的客户端；

所述云计算服务器通信连接所述客户端的收发模块，用于在收到第一密文矩阵集合和第二密文矩阵集合后，通过外包计算方式，云计算得到对应的反馈矩阵Φ，并将云计算结果反馈给所述收发模块。

本发明的有益效果为：

(1)本发明创造提供了一种适用于计算大尺度矩阵乘法结果的新外包计算协议，可使拥有较少计算资源/计算能力弱的客户端在面对大尺度矩阵乘运算时，能够在保证敏感的矩阵数据不被泄露的前提下，通过较少的计算开销将矩阵的乘运算外包给拥有大量计算资源的云服务器，并提供给客户关于矩阵乘结果的安全可靠的验证，从而满足外包计算在安全性(可验证性)、隐私性以及高效性的所存在的需求，便于实际应用和推广；

(2)所述可验证外包计算方法与现有相关协议相比，一方面验证方案通过猜测结果的概率更低，且不依赖于原始明文矩阵和随机验证次数；另一方面验证效率更高，即本地在预处理以及验证阶段的计算量较这些协议大大减少，并且不需要原始明文矩阵的参与，客户端仅需要提供2组随机数序列就可以完成对计算结果的验证。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明提供的可验证外包计算方法的流程示意图。

图2是本发明提供的实现可验证外包计算方法的客户端结构示意图。

图3是本发明提供的云计算系统的结构示意图。

具体实施方式

下面结合附图及具体实施例来对本发明作进一步阐述。在此需要说明的是，对于这些实施例方式的说明虽然是用于帮助理解本发明，但并不构成对本发明的限定。本文公开的特定结构和功能细节仅用于描述本发明的示例实施例。然而，可用很多备选的形式来体现本发明，并且不应当理解为本发明限制在本文阐述的实施例中。

应当理解，尽管本文可能使用术语第一、第二等等来描述各种单元，但是这些单元不应当受到这些术语的限制。这些术语仅用于区分一个单元和另一个单元。例如可以将第一单元称作第二单元,并且类似地可以将第二单元称作第一单元，同时不脱离本发明的示例实施例的范围。

应当理解，对于本文中可能出现的术语“和/或”，其仅仅是一种描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，单独存在B，同时存在A和B三种情况；对于本文中可能出现的术语“/和”，其是描述另一种关联对象关系，表示可以存在两种关系，例如，A/和B，可以表示：单独存在A，单独存在A和B两种情况；另外，对于本文中可能出现的字符“/”，一般表示前后关联对象是一种“或”关系。

应当理解，在本文中若将单元称作与另一个单元“连接”、“相连”或“耦合”时，它可以与另一个单元直相连接或耦合，或中间单元可以存在。相対地，在本文中若将单元称作与另一个单元“直接相连”或“直接耦合”时，表示不存在中间单元。另外，应当以类似方式来解释用于描述单元之间的关系的其他单词(例如，“在……之间”对“直接在……之间”,“相邻”对“直接相邻”等等)。

应当理解，本文使用的术语仅用于描述特定实施例，并不意在限制本发明的示例实施例。若本文所使用的，单数形式“一”、“一个”以及“该”意在包括复数形式，除非上下文明确指示相反意思。还应当理解，若术语“包括”、“包括了”、“包含”和/或“包含了”在本文中被使用时,指定所声明的特征、整数、步骤、操作、单元和/或组件的存在性,并且不排除一个或多个其他特征、数量、步骤、操作、单元、组件和/或他们的组合存在性或增加。

应当理解，还应当注意到在一些备选实施例中，所出现的功能/动作可能与附图出现的顺序不同。例如,取决于所涉及的功能/动作,实际上可以实质上并发地执行,或者有时可以以相反的顺序来执行连续示出的两个图。

应当理解，在下面的描述中提供了特定的细节,以便于对示例实施例的完全理解。然而,本领域普通技术人员应当理解可以在没有这些特定细节的情况下实现示例实施例。例如可以在框图中示出系统，以避免用不必要的细节来使得示例不清楚。在其他实例中，可以不以不必要的细节来示出众所周知的过程、结构和技术，以避免使得示例实施例不清楚。

实施例一

如图1所示，本实施例提供的所述实现大尺度矩阵乘法安全高效的可验证外包计算方法，可以但不限于包括如下步骤S101～S105。

S101.采用单向陷门函数生成公私密钥对其中，A表示公钥矩阵且为私钥矩阵且q表示大于2的素数，表示对中每一个元素求关于q的余数，Z_q∈{0,1,2,…,q-1}，m为不小于1000的正整数，n为正整数且n＜＜m。

在所述步骤S101中，所述单向陷门函数是有一个陷门的一类特殊单向函数，其包含两个明显特征:一是单向性，二是存在陷门；所谓单向性，也称不可逆性，即对于一个函数y＝f(x)，若已知x要计算出y很容易，但是已知y要计算出x＝f^-1(x)则计算上不可行。具体的，在所述步骤S101中详细包括有如下步骤S1011～S1013。

S1011.获取函数参数：其中，σ＞0，

在所述步骤S1011中，所述函数参数的获取方式，可以但不限于包括如下：在导入安全参数λ后，根据所述安全参数λ分别计算得到函数参数σ＝f_σ(λ)，n＝f_n(λ)，其中，f_σ(λ)、f_n(λ)和分别为关于安全参数λ的预设函数。所述安全参数λ由用户在客户端操作界面上输入得到，进而可以根据预设函数f_σ(λ)，f_n(λ)和得到对应的函数参数举例的，n＝f_n(λ)＝poly(λ)，poly()表示一个符合要求的多项式函数。

S1012.按照如下方式构造对应所述公钥矩阵A的转置矩阵A^T和对应所述私钥矩阵的转置矩阵

式中，A₁为所述转置矩阵A^T的第一矩阵列分块且A₁随机生成且对应的定义格满足Λ^⊥(A₁)＝{z∈Z^m|(A₁z)modq＝0}，()modq表示求关于q的余数，A₂为所述转置矩阵A^T的第二矩阵列分块且A₂＝-A₁(R+G)。所述第一矩阵列分块A₁的随机生成方式可采用现有常规随机算法实现。

矩阵其中，第i个矩阵列分块G⁽ⁱ⁾的列数h_i,i为在对应Λ^⊥(A₁)的埃尔米特矩阵H中第i行且第i列的元素，表示对变量x进行向上取整，在第i个矩阵列分块G⁽ⁱ⁾中第j列元素j∈[1,w_i]，e_i表示第i个矩阵列分块G⁽ⁱ⁾所对应的标准基向量且满足特别矩阵列分块M的列宽度表示对变量x进行向下取整，特别矩阵列分块M仅在前d行存在非零元素，d＝(1+σ)nlgq，前d行元素随机取自具有个元素的哈达玛矩阵(由+1和-1元素构成的正交方阵，所谓正交方阵，指它的任意两行或两列都是正交的，且任意一行/列的所有元素的平方和等于方阵的阶数，已有人证明，哈达玛矩阵的阶数都是4的倍数)且任意两个元素不相等。此外特别地，为了保证密钥生成算法在Z_p内同态乘法的正确性，可以但不限于按照如下方式对素数q进行取值：

式中，c＝f_c(λ),c＞0，f_c(λ)为关于安全参数λ的预设函数，ω()为满足的函数。

矩阵其中，第i个矩阵行分块在第i个矩阵行分块P⁽ⁱ⁾中第j列元素是的二进制表示，h_i,j为在对应Λ^⊥(A₁)的埃尔米特矩阵H中第i行且第j列的元素，为在矩阵中第i行且第j列的元素，I为单位矩阵(在矩阵的乘法中，有一种矩阵起着特殊的作用，如同数的乘法中的1,人们称这种矩阵为单位矩阵；它是个方阵，从左上角到右下角的对角线或称为主对角线上的元素均为1，以外全都为0)，有

矩阵其中，diag()为对角矩阵构造函数，T_wi为对应第i个矩阵列分块G⁽ⁱ⁾的幺模上三角矩阵(在数学上，幺模矩阵是所有项都是整数而且行列式为1或-1的方阵；所有可逆的同阶幺模矩阵按照矩阵乘法构成一个乘法群)且在矩阵中第行且第列的元素

矩阵R的前d行元素独立地随机取自整数集合{-1,0,1}，其余行的元素全部为零，其中，针对数值0的随机取值概率为50％，针对数值-1和数值1的随机取值概率分别为25％。

S1013.输出对应转置矩阵A^T的所述公钥矩阵A和对应转置矩阵的所述私钥矩阵

S102.在导入待乘法运算的第一明文矩阵B₁和第二明文矩阵B₂后，先分别得到对应的第一明文矩阵集合和第二明文矩阵集合然后采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第一明文矩阵集合中的各个矩阵分别进行加密，得到对应的第一密文矩阵集合以及采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第二明文矩阵集合中的各个矩阵分别进行加密，得到对应的第二密文矩阵集合其中，p表示大于2的正整数，Z_p∈{0,1,2,…,p-1}，并按照如下公式得到所述第一明文矩阵集合和所述第二明文矩阵集合

式中，θ₁和θ₂均为对角矩阵且θ₁,θ₁∈Z^m×m，Z表示整数集合，I为单位矩阵。

在所述步骤S102中，所述第一明文矩阵B₁和所述第二明文矩阵B₂可分别由用户在客户端操作界面上直接输入或从其它设备导出得到，由于参数m为不小于1000的正整数，这两明文矩阵分别为大尺度矩阵或大规模矩阵，若直接计算矩阵乘法结果，将需要很高的计算能力，其计算复杂度为O(m³)，矩阵尺寸m越大，计算越繁杂。

考虑在经典计算机理论中，许多数学难题都可以从2个典型的困难问题引出，即离散对数问题和大整数的分解问题。然而，近些年来随着量子计算机技术的发展，其远超经典计算机的计算能力,使得基于这2个问题的密码方案不再安全。因此，近年来格理论以及相关密码算法得到迅速发展，这是基于格理论中的一些难题即使在量子计算模型下也不具有高效的解决方法，故而本申请使用了基于格理论中的标准LWE(Learn With Errors)问题的加密算法来提供隐私保护。

简单地说，格(Lattice)是实数空间中线性无关向量的整系数组合的集合。给定n个m维的线性无关向量b₁,b₂,…,b_n∈R^m，以这些向量作为基，形成的格是由下列向量组成的集合：

LWE问题是格密码方案构造中最常见的困难问题之一，它相较于格中一些其他困难问题来说能更方便地用于构造密码方案，LWE问题包括搜索型问题和判定型问题，以下即对其进行简单描述。对于正整数q≥2,n≥2以及定义在整数Z上的概率分布χ，均匀随机地选取向量和向量随机选取错误x←χ，最后输出(即被错误扰动的内积)，同时将该输出结果的分布定义为A_s,x。搜索型LWE问题定义为：在已知m个独立地从A_s,x中选取的实例的情况下，以不可忽略的概率找出秘密向量s。而判定型LWE问题要求以不可忽略的概率区分A_s,x和真正的均匀随机分布。特别地，对于这两种类型的标准LWE问题来说，分布χ被设定为高斯分布(即正态分布)，那么若随机变量X服从一个数学期望为μ、方差为σ²的高斯分布χ，则其概率密度函数为：用Ψ_β(q)表示在Z_q上的方差为期望为μ＝0的离散高斯分布。

对于标准LWE问题来说，在参数选取得当的情况下，它是难解的，但它的变种却不一定有着相同的困难性，以下对其2类主要变种LWE问题进行描述。

Binary-error LWE问题：在标准LWE问题的基础上，若将分布χ选为均匀{0,1}分布，就成为了Binary-error LWE问题。Martin R.Albrecht等人就参数m和n的选择对Binary-error LWE问题的困难程度的影响进行了细致的讨论，对于m＝cn，Binary-errorLWE在指数时间内可解；对于m＝cnlgn，Binary-error LWE在次指数时间内可解；对更大的m，Binary-error LWE在多项式时间内可解。因此错误x取自{0,1}分布会导致LWE问题的困难性随m的增大而降低，从而影响到协议的隐私性，但与此同时会大大降低本地的开销，提高协议的效率。另外，错误x也可以从均匀{-1,0,1}分布上选取，该变种LWE问题的困难性较Binary-error LWE问题更大。

LWE with Binary Secrets问题：在标准LWE问题的基础上，若将秘密向量s的取值方式改为均匀随机地取自{0,1}ⁿ分布，标准LWE问题就变成了LWE>n分布，抽样数为O(nlgq)时该变种LWE问题的困难性与秘密向量取自上的随机分布时的困难问题的困难性等同。秘密向量s也可以均匀随机地取自{-1,0,1}ⁿ分布，此时的变种LWE问题的困难性相较于均匀随机地取自{0,1}ⁿ分布的情况的困难性更大。

另外，所述基于变种LWE问题的加性同态加密算法具体为：对于明文矩阵相应的加密过程C＝Enc_k(B)可表示为C＝(AS+pX+B)<mod>q，其中，公钥矩阵X←Ψ_β(q)^m×m，利用私钥矩阵可解密恢复()modp表示求关于p的余数，()<mod>q表示求在区间范围之间的映射值，所对应的映射公式可以但不限于为例如特别地，该算法具有一个矩阵乘法的同态性，即若有：C₁＝Enc_k(B₁),C₂＝Enc_k(B₂)，则有下式成立：C＝C₁(C₂)^T＝Enc_k(B₁(B₂)^T)。

由此在所述步骤S102中，针对所述第一明文矩阵集合和所述第二明文矩阵集合中的各个矩阵B，可按照如下方式进行加性同态加密：S1021.获取具有n×m个元素的秘密矩阵S和具有m×m个元素的误差矩阵X；S1022.按照如下公式计算与矩阵B对应的密文矩阵C：

C＝(AS+pX+B)<mod>q

式中，A为公钥矩阵，()<mod>q表示求在区间范围之间的映射值。

在所述步骤S1021中，可具体按照如下方式(1)～(3)中的任意一种选取所述秘密矩阵S和所述误差矩阵X：(1)所述秘密矩阵S均匀地随机取自所述误差矩阵X均匀地随机取自{-1,0,1}^m×m或{0,1}^m×m；(2)所述秘密矩阵S均匀地随机取自{-1,0,1}^n×m，所述误差矩阵X均匀地随机地取自{-1,0,1}^m×m或(Ψ_β(q))^m×m，其中，Ψ_β(q)为Z_q上的高斯分布，β为高斯分布参数；(3)所述秘密矩阵S均匀地随机取自{0,1}^n×m，所述误差矩阵X均匀的随机取自(Ψ_β(q))^m×m，其中，Ψ_β(q)为Z_q上的高斯分布，β为高斯分布参数。

当所述秘密矩阵S取自{0,1}^n×m或{-1,0,1}^n×m时，算法/协议的隐私性基于LWEwith>m×m或{0,1}^m×m时，算法/协议的隐私性基于Binary-error>m×m时，加密所需的运算全部为加法运算，可以最大化地减少本地的计算量，提高客户端的效率。但该方式(2)和方式(1)存在相同的问题，即对数据隐私的保护不如其他方式，例如方式(3)，因此可在对隐私性要求不高而比较强调效率的情况下使用。因此本实施例中所使用的加解密算法是在现有同态密码系统的基础上进行的补充和改进，即对所述秘密矩阵S和所述误差矩阵X的取值方式进行了改进和扩展，这样在保有隐私性的同时可以降低用户的开销，提升所设计方案的效率。例如，如果客户端想要最大化加密效率和最小化本地的计算量，那么可以选取所述秘密矩阵S和所述误差矩阵X的取值范围分别为{-1,0,1}^n×m和{-1,0,1}^m×m，该选择可使得在不要求取得可证明隐私性的前提下具有较好的实用性。此外，在所述步骤S1021之前包括如下：在导入安全参数λ后，根据所述安全参数λ计算得到高斯分布参数β＝f_β(λ)，其中，f_β(λ)为关于安全参数λ的预设函数，例如

在所述步骤S102之前，优化的，为了避免云计算服务器感知到所述第一明文矩阵B₁和所述第二明文矩阵B₂，进一步提升数据隐私性，还随机地选取得到任意两元素均不相等的第一正整数序列{u₁,u₂,u₃,…,u_k},k＜m和第二正整数序列{v₁,v₂,v₃,…,v_l},l＜m，然后按照如下公式计算对角矩阵θ₁和对角矩阵θ₂中的对角元素值：

式中，δ(x)为关于变量x的狄拉克函数，当且仅当x为零时为1，其它情况为零。其中所涉及到参数k,l可在导入安全参数λ后，根据所述安全参数λ以及对应的预设函数计算得到。

S103.将所述第一密文矩阵集合和所述第二密文矩阵集合上传至云计算服务器，并在经过外包计算方式的云计算后，获取如下反馈矩阵Φ：

式中，

在所述步骤S103中且在将所述第一密文矩阵集合和所述第二密文矩阵集合上传至云计算服务器后，采用外包计算方式的云计算方法为现有方法。

S104.采用所述私钥矩阵及逆矩阵对所述反馈矩阵Φ进行解密，得到如下待验证矩阵RT：

式中，()modp表示求关于p的余数，()<mod>q表示求在区间范围之间的映射值，

S105.检查RT₀₀是否等于RT₁₁+RT₁₂+RT₂₁+RT₂₂，若发现相等，则将RT₀₀作为所述第一明文矩阵B₁与所述第二明文矩阵B₂的乘法运算结果，否则判定验证失败，拒绝接受外包计算结果。

在所述步骤S105之前，若在计算对角矩阵θ₁和对角矩阵θ₂中的对角元素值时，随机地选取了第一正整数序列和第二正整数序列，则还根据所述第一正整数序列和所述第二正整数序列检查RT₀₀中的元素除第u₁,u₂,u₃,…,u_k行和第v₁,v₂,v₃,…,v_l列以外是否全部为零，若发现全部为零，则再执行步骤S105，否则判定验证失败，拒绝接受外包计算结果。

针对前述步骤S101～S105的技术效果，可进行如下几点分析。

(1)正确性：对本实施例所述可验证外包计算方法的正确性推导如下：

可得C＝C₁(C₂)^T＝(AS₁+pX₁+B₁)(AS₂+pX₂+(B₂)^T)^T

＝(A(S₁(S₂)^T)+p(X₁(pX₂+(B₂)^T)+B₁(X₂)^T)+B₁B₂+(pX₁+B₁)(S₂)^TA^T)<mod>q

对C解密：

然后验证单向陷门函数的公私密钥对满足首先证明由于可转而验证

左乘矩阵的列分块与右乘矩阵的行分块方式相同，分块乘法成立。

代入A₂＝-A₁(R+G)和对上式化简：

因为H∈Λ^⊥(A₁)，所以A₁H＝0，由此可得然后根据()<mod>q运算的性质，进一步可得公私密钥对的正确性得证，加密方案的正确性证明完毕。

对于验证算法的正确性，由于和因此有

等式右边恰好是Φ_i′,j′，i′,j′∈{1,2}四个分块解密后的结果，验证算法的正确性得证。

(2)隐私性：所提出的可验证外包计算方法使用了变种GHV同态加密算法(族)，以达到可证明隐私性。原GHV算法(由Gentry等人设计的第一个矩阵同态加密方案)自提出至今，其隐私性已有严格的证明，而本实施例所给出的变种GHV算法(族)的隐私性可以利用相似方法归约证明到变种LWE问题的困难性上。

(3)高效性：本实施例所产生的公私密钥对可以持续使用，因此仅需讨论客户端加解密所需要的计算量。计算量主要来自私钥矩阵及其逆矩阵进行的相关运算，实际上，可以发现私钥矩阵是一个稀疏矩阵，且非零元素中绝大多数为1或2，只有右上的块的元素的值域较大。另一逆矩阵的非零元素数量与参数的选择密切相关，它对应的非零元素数量的上界为其中参数的取值范围如下：

因此，的非零元素数量为固定常数。假设表示加法运算的时间，表示乘法运算的时间，另外假设使用高斯分布的噪声。在所述步骤S102中的加密阶段，所需的计算量为而在所述步骤S104中的解密阶段所需计算量为其中，表示私钥矩阵中非零元素的占比。因为乘法的计算时间远大于加法的计算时间，所以在只考虑乘法运算开销的情况下本方法的计算复杂度为O(nm²lgn)。考虑到目前矩阵乘法的实际计算复杂度可达到O(m^2.775)，本方法需要满足nlgn＜m^0.775，而在实际应用中参数能满足m＝poly(n)且n＜＜m，这就意味着本方法所涉及的m和n一般满足不等式nlgn＜m^0.775，因此本实施例提供的可验证外包计算方法是高效的。

(4)安全性(可验证性)：本实施例提供的新高效验证方法，与之前的基于矩阵-向量乘的方法不同，其安全性是基于敌手正确猜测随机数序列的困难性。对于恶意的云端服务器(关于数据安全的威胁主要来自云计算服务器；威胁模型一般分为2种：半诚实模型和恶意模型；半诚实模型：云端服务器会诚实地执行协议，计算客户端的需求，但是它会记录所有的信息，并以此来推测出客户端的隐私信息，另外云端服务器自身也有被攻击和窃取信息的可能；恶意模型：云端服务器可以不遵从协议的规定，它甚至可以任意返回一个结果作为计算的输出来为自己节省计算资源，同时它不希望客户端检测出伪造的结果)来说，在不知道第一正整数序列{u₁,u₂,u₃,…,u_k},k＜m和第二正整数序列{v₁,v₂,v₃,…,v_l},l＜m的情况下，以一个猜测的结果通过验证的概率为2^-2m，而由于被外包矩阵的行(列)数m＝poly(λ)，所以猜测的结果通过验证的概率可表示为2^-ω(λ)(由于满足其概率可忽略)。

作为概括的，为了将本实施例所提出的方法与已公开的现有协议做一个直观的比较，可用一个表格总结迄今为止的全部相关协议的主要性能指标。

表1.针对矩阵乘法的可验证外包计算协议主要指标对照表

上述表格即为各协议/方法计算矩阵的情况；分别表示运行一次指数运算、乘法运算、随机选择以及判断是否非零元素所需的时间；协议2和协议3的隐私性是基于加密算法所使用的困难假设，例如，当协议使用BGN加密算法时，基于的假设是判定型Diffle-Hellman假设，这时协议的计算开销也是以BGN加密算法(BGN是一种同态加密方案，是Bonel h等人在2005提出的一种具有全同态性质的加密方案)为准；

此外，通过上表可以看出，猜测结果通过验证的概率随着与安全参数λ相关的矩阵行(列)数m的增大而变得微乎其微，这一结论可以基于以下事实：在不知道非零列和行的数量以及具体坐标的情况下，通过验证的概率实际上与正确猜测均匀随机选取地数的概率相等。例如，在区间[0,2^m]内均匀随机地选取两个正整数a和b，它们满足：

那么猜测结果通过验证的概率等于猜测这两个正整数的概率，即为2^-2m。考虑被外包矩阵的行(列)数m＝poly(λ)，这就意味着猜测结果通过验证的概率可表示为2^-ω(λ)(可忽略的)，与表1中协议2,协议5和协议6中的验证方案相比，本方法中的验证方案通过猜测结果的概率更低，且不依赖于原始明文矩阵和随机验证次数。而与表1中协议3,协议4和协议7中的验证方案相比，本方法的效率更高，即本地在预处理以及验证阶段的计算量较这些协议大大减少。另外，本方法提出的验证方案并不需要原始明文矩阵的参与，客户端仅需要提供2组随机数序列就可以完成对计算结果的验证。

综上，采用本实施例所提供的实现大尺度矩阵乘法安全高效的可验证外包计算方法，具有如下技术效果：

(1)本实施例提供了一种适用于计算大尺度矩阵乘法结果的新外包计算协议，可使拥有较少计算资源/计算能力弱的客户端在面对大尺度矩阵乘运算时，能够在保证敏感的矩阵数据不被泄露的前提下，通过较少的计算开销将矩阵的乘运算外包给拥有大量计算资源的云服务器，并提供给客户关于矩阵乘结果的安全可靠的验证，从而满足外包计算在安全性(可验证性)、隐私性以及高效性的所存在的需求，便于实际应用和推广；

(2)所述可验证外包计算方法与现有相关协议相比，一方面验证方案通过猜测结果的概率更低，且不依赖于原始明文矩阵和随机验证次数；另一方面验证效率更高，即本地在预处理以及验证阶段的计算量较这些协议大大减少，并且不需要原始明文矩阵的参与，客户端仅需要提供2组随机数序列就可以完成对计算结果的验证。

实施例二

如图2所示，本实施例提供了一种实现前述实施例一的客户端，用于执行如实施例一所述实现大尺度矩阵乘法安全高效的可验证外包计算方法，并包括有密钥生成模块、明文加密模块、收发模块、密文解密模块和结果验证模块；

所述密钥生成模块，用于采用单向陷门函数生成公私密钥对其中，A表示公钥矩阵且为私钥矩阵且q表示大于2的素数，表示对中每一个元素求关于q的余数，Z_q∈{0,1,2,…,q-1}，m为不小于1000的正整数，n为正整数且n＜＜m；

所述明文加密模块，通信连接所述密钥生成模块，用于在导入待乘法运算的第一明文矩阵B₁和第二明文矩阵B₂后，先分别得到对应的第一明文矩阵集合和第二明文矩阵集合然后采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第一明文矩阵集合中的各个矩阵分别进行加密，得到对应的第一密文矩阵集合以及采用基于变种LWE问题的加性同态加密算法及所述公钥矩阵A对所述第二明文矩阵集合中的各个矩阵分别进行加密，得到对应的第二密文矩阵集合其中，p表示大于2的正整数，Z_p∈{0,1,2,…,p-1}，并按照如下公式得到所述第一明文矩阵集合和所述第二明文矩阵集合

式中，θ₁和θ₂均为对角矩阵且θ₁,θ₁∈Z^m×m，Z表示整数集合，I为单位矩阵；

所述收发模块，通信连接所述明文加密模块，用于将所述第一密文矩阵集合和所述第二密文矩阵集合上传至云计算服务器，并在经过云计算后，获取如下反馈矩阵Φ：

式中，

所述密文解密模块，通信连接所述收发模块，用于采用所述私钥矩阵及逆矩阵对所述反馈矩阵Φ进行解密，得到如下待验证矩阵RT：

式中，()modp表示求关于p的余数，()<mod>q表示求在区间范围之间的映射值，

所述结果验证模块，通信连接所述密文解密模块，用于检查RT₀₀是否等于RT₁₁+RT₁₂+RT₂₁+RT₂₂，若发现相等，则将RT₀₀作为所述第一明文矩阵B₁与所述第二明文矩阵B₂的乘法运算结果，否则判定验证失败，拒绝接受外包计算结果。

本实施例的工作过程和技术效果，可参照实施例一毫无疑议地推导得到，于此不再赘述。

实施例三

如图3所示，本实施例提供了一种包括前述实施例二的云计算系统，包括云计算服务器和如实施例二所述的客户端；所述云计算服务器通信连接所述客户端的收发模块，用于在收到第一密文矩阵集合和第二密文矩阵集合后，通过外包计算方式，云计算得到对应的反馈矩阵Φ，并将云计算结果反馈给所述收发模块。本实施例的工作过程和技术效果，同样可参照实施例一毫无疑议地推导得到，于此不再赘述。

以上所描述的多个实施例仅仅是示意性的，若涉及到作为分离部件说明的单元，其可以是或者也可以不是物理上分开的；若涉及到作为单元显示的部件，其可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

最后应说明的是，本发明不局限于上述可选的实施方式，任何人在本发明的启示下都可得出其他各种形式的产品。上述具体实施方式不应理解成对本发明的保护范围的限制，本发明的保护范围应当以权利要求书中界定的为准，并且说明书可以用于解释权利要求书。