基于大规模矩阵Jordan分解的外包计算

吴宏锋　闫晶晶

摘   要：目前，外包计算已成为减轻用户庞大计算量的重要策略之一。针对大规模矩阵的Jordan分解需要用户付出大量的计算资源问题。文章设计了一个安全、结果可验证、高效的外包协议，达到了节省用户计算资源的目的。通过线性变换、元素的重排列对原始矩阵进行加密，保护了用户隐私信息，并运用高效的验证算法对云端返回的结果进行了高效验证。文章通过计算复杂度分析，验证了该协议的高效性。

关键词：外包计算;Jordan分解;可验证性

中图分类号：TP309          文献标识码：A

Outsourcing computing of large matrix Jordan decomposition

Wu Hongfeng， Yan Jingjing

（College of Science， North China University of Technology， Beijing 100144）

Abstract： At present， outsourcing computing has become an important way to reduce the large amount of computing by users. The Jordan decomposition of large-scale matrix requires users to pay a lot of computing resources. In order to save user's computing resources， the article designs a secure， verifiable and efficient outsourcing protocol for Jordan decomposition of large-scale matrix. The original matrix is encrypted by linear transformation and element rearrangement to protect the user's privacy information. Efficient verification algorithm is used to verify the results returned from the cloud. Finally， the computational complexity is analyzed and the efficiency of the protocol is verified.

Key words： outsourcing computing;Jordan decomposition;verifiability

Abstract： At present， outsourcing computing has become an important way to reduce the large amount of computing by users. The Jordan decomposition of large-scale matrix requires users to pay a lot of computing resources. In order to save user's computing resources， the article designs a secure， verifiable and efficient outsourcing protocol for Jordan decomposition of large-scale matrix. The original matrix is encrypted by linear transformation and element rearrangement to protect the user's privacy information. Efficient verification algorithm is used to verify the results returned from the cloud. Finally， the computational complexity is analyzed and the efficiency of the protocol is verified.

Key words： outsourcing computing;Jordan decomposition;verifiability

1 引言

隨着近年来信息技术的飞速发展，云外包计算愈加受到网络行业的关注[1，2]。云具有非常强大的计算能力，相比于传统计算模式而言，云计算为用户明显地节省了计算时间和开销，由此云计算得到了众多用户的青睐。

然而，外包云计算在给云用户带来诸多利益的同时，也存在着许多安全威胁[3]。由于用户通常无从得知云端是否诚信，所以如何保证外包计算中用户隐私信息的安全成为了首要问题。当用户将计算任务外包给云时，原始计算任务中所含有的隐私信息可能会被云知道，使得用户隐私信息的安全得不到保障。所以，用户在云环境下进行外包计算时，需要对原计算问题中包含的隐私信息进行加密，进而保证用户隐私数据的安全性。其次，云端返回给用户的结果的正确性要如何保证。例如，云端为了减少自身开支而得到更多的收益，从而返回给了用户一个不正确的结果，这时为了保证用户自身的利益，就需要用户对该结果进行验证。

在解决以上两个安全威胁的基础上，还要确保外包计算的有效性。相比于自行对计算任务进行计算，用户选择外包计算后所用的计算时长要明显地缩短，提高用户的计算效率。

针对矩阵计算不同方面的问题，许多学者提出了外包计算协议。在文献[4]中，作者提出了大规模矩阵乘积的外包计算协议，但没有实现结果的可验证性。在文献[5]中，利用同态加密技术实现了外包计算协议的结果可验证性，但加密过程的复杂度较高。在文献[6]中，作者提出了大规模线性方程组的求解方案，但其操作成本过高。在文献[7]中，作者亦提出了大规模矩阵乘积的外包计算协议，但基于非方阵的乘积问题，其采用了分类讨论思想，加大了外包计算的复杂程度。在文献[8]中，作者提出了大规模矩阵分解的外包计算协议，包括矩阵的特征值分解、SVD分解等，但没有涉及矩阵Jordan分解的外包计算协议。

Jordan分解在“矩阵方程论”“常微分方程”以及“现代控制论”等方面都有着广泛的应用[9]，同时基于大规模矩阵Jordan分解需要耗费大量的物力财力。本文提出了大规模矩阵Jordan分解的外包计算协议，该协议操作简便，成本低廉，可以减少用户的计算成本与开销。

2 背景知识

2.1 Jordan分解

给定一个的实对称矩阵，如果有一个实数和一个非零向量使下面的方程成立，

（1）

则称为矩阵的特征值，是与特征值对应的特征向量。

给定一个一般的矩阵，可以用Jordan分解对它进行如下分解：

（2）

其中，为的可逆矩阵，称为Jordan块，，其中是一个Jordan阵，称为矩阵的Jordan标准型，它的对角元素是矩阵的特征值，如果云端不知道矩阵的特征值，那么云端将无从得知该矩阵的Jordan标准型。称为变换矩阵。

假设是矩阵的特征值，是对应的特征向量，则可得到如下方程：

对任意一个的矩阵，对其进行如下变换：

其中，为单位矩阵，就可以得到矩阵的Jordan标准型和变换矩阵[10]，所以如果云端不知道和是无法得到的。

2.2 排列和δ函數

利用柯西表示法，本文提出把集合与其自身相互映射，将排列形式表达如下：

（3）

在这个表示中，第一行是映射的原像，第二行是在该映射下的像。在（3）中，本文提出可把排列表示为一个双射函数，其值域和定义域均被设置为集合。

函数的定义如下：

（4）

在空间中生成一组随机数，则加密后的矩阵可被定义为：

（5）

在（5）中，的值域和定义域均为。由定义可知，在加密矩阵中，每一行每一列都有且只有一个非零元素，且加密矩阵是标准正交矩阵。

3 系统模型和协议设计相关知识

在外包计算中，根据敌手的不同，安全计算模型主要分为两大类：半诚实模型和恶意模型[11]。在半诚实模型中，虽然云遵守协议，但它会被动地尝试去获得用户原计算任务中的隐私信息[11]。在恶意模型中，云不仅会主动地从用户获取隐私信息，还有违背协议的可能性，任意返回一个错误的结果给用户，并不愿被用户检验出来[11]。所以，在恶意的云模型中，用户对云端返回的结果，必须能够加以验证，以抵抗云欺骗。本文考虑恶意模型。

本文提出设计的矩阵Jordan分解外包模型如图1所示。首先，用户生成密钥，利用密钥来加密原始矩阵，保护原始矩阵中所包含的隐私信息，得到加密后的加密矩阵;然后，用户将加密矩阵发送给云端，利用云端强大的计算能力和巨大的存储容量，对加密矩阵进行Jordan分解;云端再将其计算后得到的加密矩阵的Jordan分解结果返回给用户;在接收到从云中返回的结果后，用户对该结果进行验证，如果结果正确，用户将其解密以得到原始矩阵的Jordan分解结果，反之用户会对云返回的结果表示否定，并再次让云进行计算。

本文提出的大规模矩阵Jordan分解外包协议需要达到几项目的[12]。

（1）安全性：用户的任何隐私信息云都不能获取。

（2）可验证性：用户能够以极大概率验证结果的正确性，也能够以不可忽略的概率在云中发现错误的结果。

（3）有效性：与自行计算矩阵的Jordan分解相比，用户通过外包计算，能够大大减少本地计算。

本文提出的系统模型共分为五部分，如图1所示。

（1）密钥生成：用户随机生成密钥用于加密原始矩阵。

（2）加密：用户利用密钥加密原始矩阵。在将原始矩阵加密成加密矩阵的过程中，本文用到了矩阵乘法和线性映射。

（3）计算矩阵的Jordan分解：云对加密矩阵进行Jordan分解，并返回结果给用户。

（4）验证：对于云返回的结果，用户要进行验证。如果验证结果正确，用户接受结果;否则，用户会对返回的结果表示否定，并要求云再次进行计算。

（5）解密：如果云返回的结果正确，用户把矩阵的Jordan标准型、变换矩阵和变换矩阵的逆解密成矩阵的Jordan标准型、变换矩阵和变换矩阵的逆。由此得到原始矩阵的Jordan分解结果。

4 协议设计

4.1 密钥生成

本文利用加密矩阵生成密钥，生成加密矩阵的过程如下：

（6）

其中，为空间产生的随机数。空间的定义由本文提出并在背景知识中进行描述，是双射函数。

4.2 加密

在矩阵的Jordan分解外包中，用户的目的是得到矩阵的Jordan标准型、变换矩阵以及变换矩阵的逆。同时，用户希望矩阵本身，以及它的Jordan标准型和变换矩阵都不会暴露在云中。在本文中，提出要对用户的隐私信息进行加密，也就是对原始矩阵以及原始矩阵 的Jordan标准型和变换矩阵进行加密，由2.1节可知，本文提出只需对原始矩阵以及原始矩阵的特征值和特征向量进行加密。

（1）在矩阵Jordan分解外包过程中，如果用户直接将原始矩阵发送到云，那么矩阵中的隐私信息可能会暴露到云中。为了不泄露的隐私信息，用户先从实数集R中随机选择，再对原始矩阵进行如下加密：

（7）

根据以上加密方法，可知矩阵与矩阵的特征向量相同，且的特征值与的特征值之间的关系如下：

（8）

上式证明如下：

设为矩阵的一个特征值，且是与特征值对应的特征向量，于是有：

（9）

证毕。

由于云对的确切值无从得知，如果用户把 发送到云，那么此时便保护了矩阵本身和其特征值中包含的隐私信息，但矩阵和矩阵具有相同的特征向量，也就是说，矩阵的特征向量中包含的隐私信息没有得到保护。因此，还要加密的特征向量。

（2）现在，本文对矩阵的特征向量进行加密。首先，令

（ 是标准正交矩阵）. （10）

则（9）式可以表示为：

（11）

（11）式两边同时乘以矩阵 ：

（12）

于是（11）式可以写成：

（13）

其中，此时通过加密，原始矩阵转换成了加密矩阵，其关系可以表示为。由（10）式可知，加密矩阵隐藏了矩阵的特征向量中包含的隐私信息。

经上述加密，完成了对用户的隐私信息的保护。这时，将加密矩阵发送给云端，云端对其进行Jordan分解，并将分解结果返回给用户。此时，用户得到了加密矩阵的Jordan标准型、变换矩阵以及变换矩阵的逆，分别为：

矩阵的Jordan标准型为，

矩阵的变换矩阵为：，

矩阵的变换矩阵的逆为。

其中，是一个Jordan块，是一个Jordan阵，的对角元素为矩阵的特征值;为型矩阵，是一个可逆的变换矩阵。

在加密过程中，本文使用到了加密矩阵，目的是确保只要云返回了一个标准正交的特征向量，那么用户对其解密后也会得到标准正交的特征向量，证明如下：

假设和是云端返回的矩阵的两个标准正交的特征向量，用户对其进行解密，得到的两个特征向量满足和，则有即和是标准的;又因，说明 和是正交的，所以和也是标准正交的。

证毕。

4.3 验证

对于云端返回给用户的结果，用户有必要对结果进行验证。为了保证结果、和是正确的，用户首先要检查是否为Jordan阵。如果不是Jordan阵，则用户认为结果不正确。如果为Jordan阵，那么用户验证下式是否正确：

（14）

这相当于验证以下公式是否成立：

（15）

验证方法如下：

（1）随机选择一个的向量，中每个元素均从集合中随机选择;

（2）用户计算;

（3）重复上述两步骤，共进行轮测试，在 轮测试中，如果均有，则用户接受结果;反之，用户认为结果错误，并要求云再次进行计算。

4.4 解密

如果用户验证云端返回的结果是正确的，那么将该结果进行解密，将其转化为矩阵的Jordan标准型、变换矩阵和变换矩阵的逆，解密过程如下：

（16）

通过（16），可得到原始矩阵的Jordan标准型、变换矩阵以及变换矩阵的逆：

（17）

然后得到，

（18）

于是，用户得到了原始矩阵的Jordan分解。

5 协议分析

5.1 安全性分析

将原始矩阵加密为矩阵，其中为加密矩阵，是一个由实数集R生成的随机数。首先，对原始矩阵进行加密，即。假设云端知道矩阵，如果云端想使用暴力手段通过来获取矩阵，那么它也需要猜测次，其中表示实数集R中的元素个数。然后，再利用加密矩阵对矩阵进行加密，即。本次加密使得矩阵中的元素被重新排列成以下形式：

（19）

由（19）可知，的元素被函數进行了重排列以及被缩小了。其中，有种可能，有两种可能。此时云端即使知道矩阵，并想由矩阵得到矩阵，其概率也仅有，所以在很大时，其概率可忽略不计。

用户将加密矩阵发送给云端后，云对矩阵进行Jordan分解，所以对于矩阵的特征值和与其对应的特征向量，云是知道的。下面分析协议如何对矩阵的特征值和特征向量进行保护。

矩阵与矩阵两者的特征值之间的关系是（8）式。如果不知道随机实数，云就无法利用得到。

矩阵与矩阵两者的特征向量之间的关系是（10）式。显然，加密矩阵很好地保护了特征向量。根据前面的讨论，云端若想要得到矩阵，其概率为，所以在很大时，云没有办法从特征向量解密出。

根据以上分析，可以认为用户的隐私信息都被很好地保护了。

5.2 结果可验证性分析

本节对本文提出的外包协议的结果可验证性进行分析。

云端返回的结果正确与否，通过该协议，都可以成功得到验证。

如果云返回给用户一个正确的结果，则等于矩阵，所以每轮检查中，不论取何值，都有，即可以验证任何正确的结果。

如果云返回给用户一个错误的结果，用户也会有很高的概率发现云端的这种不诚实行为。当云端返回的矩阵不是Jordan阵时，用户直接认为结果错误，因此不可能接收错误结果;当云端返回的矩阵为Jordan阵时，本文提出的协议有很高的抵抗错误结果的概率。本文采用的验证算法的误差分析表明，错误结果通过验证的概率小于[13]，即错误结果通过验证的概率是随验证次数 的增加呈指数递减的。因此，如果选择的值足够大，那么从云中返回的任何错误结果能够通过验证的可能性可以忽略不计。

5.3 有效性分析

与直接计算矩阵Jordan分解相比，用户可以通过外包计算来减轻计算负担。本文提出的系统模型需要用户执行四种算法，即密钥生成、加密、验证和解密。以下分别分析了四种算法的计算复杂度，驗证了外包协议的有效性。

（1）密钥生成。生成加密矩阵就是该算法的所有任务，其算法复杂度为。

（2）加密算法。加密算法将原始矩阵加密为矩阵，其中。在此加密过程中，计算加密矩阵与原始矩阵的乘法是最为耗时的运算。由（19）式可得，其算法复杂度为。

（3）验证算法。每轮随机检测中，用户都要计算和，矩阵和向量的乘法是其中最复杂的计算操作，它的算法复杂度是。因为验证算法需进行轮随机检测，所以验证算法的总体计算复杂度是。相比于大型矩阵，远小于，即，所以验证算法的计算复杂度是。

（4）解密算法。如果由云返回的、和的结果正确，则用户将它解密并得到原始矩阵的、和，解密算法如下：

最耗时的操作是计算，其计算复杂度为。

一般来说，所有用户需要执行的计算，其计算复杂度是。与之对比，矩阵Jordan分解直接计算需要的计算复杂度。如果足够大，与之间会有很大的区别。因此，通过外包计算，用户可以节省大量的计算成本。

6 结束语

本文设计了一个安全的、结果可验证的、高效的大规模矩阵Jordan分解的外包协议，采用了高效的加密技术，保证了用户隐私信息的安全。同时，本文设计了一种高效的验证算法，以确保用户能够高效地验证云端返回的结果是否正确。矩阵的Jordan分解在科学领域有着广泛的应用，还需要进一步深入研究。

基金项目：

1.国家自然科学基金（项目编号：61370187）;

2.北京市教委科技计划项目（项目编号：KM201510009013）。

参考文献

[1] 刘文武.云计算的特点及重点应用领域研究[J].才智， 2014（30）.

[2] 郁德强，王燕妮，李华.一种基于云计算的服务外包模式：云外包[J].情报理论与实践，2012，35（8）：97-100.

[3] 冯登国，张敏，张妍，等.云计算安全研究[J].软件学报， 2011， 22（1）：71-83.

[4] Atallah M J ， Rice J R . Secure outsourcing of scientific computations[J]. 1998.

[5] BENJAMIN D， ATALLAH M J. Private and Cheating-free Outsourcing of Algebraic Computation[C]//IEEE.Sixth Annual Conference on Privacy， Security and Trust， October 1-3，2008， Fredericton， NB， Canada.NJ：IEEE， 2008：240-245.

[6] GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[J]. Acm Symposium on Theory of Computing， 2009，9（4）：169-178.

[7] 杨波，武朵朵，来齐齐.矩阵乘积的高效可验证安全外包计算[J].密码学报，2017，4（4）：322-332.

[8] Zhou L， Li C. Outsourcing Eigen-Decomposition and Singular Value Decomposition of Large Matrix to a Public Cloud[J]. IEEE Access， 2017， 4：869-879.

[9] 赵云平.矩阵Jordan标准型在矩阵分析中的作用探讨[J].滇西科技师范学院学报，2015（1）：119-124.

[10] 顾江永.矩阵Jordan标准化的证明及初等求法[J].长江大学学报（自科版），2009，6（3）：135-136.

[11] 郭姝.云计算中的外包计算的研究[D].中国科学院大学， 2013.

[12] Duncan S.WONG.可验证安全外包矩阵计算及其应用[J].中国科学：信息科学，2013，43（7）：842-852.

[13] Motwani R， Raghavan P. Randomized algorithms[M]. Cambridge University Press， 1995.