基于大規模矩陣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.