吳宏鋒　閆晶晶

摘? ?要：目前，外包計(jì)算已成為減輕用戶龐大計(jì)算量的重要策略之一。針對(duì)大規(guī)模矩陣的Jordan分解需要用戶付出大量的計(jì)算資源問題。文章設(shè)計(jì)了一個(gè)安全、結(jié)果可驗(yàn)證、高效的外包協(xié)議，達(dá)到了節(jié)省用戶計(jì)算資源的目的。通過線性變換、元素的重排列對(duì)原始矩陣進(jìn)行加密，保護(hù)了用戶隱私信息，并運(yùn)用高效的驗(yàn)證算法對(duì)云端返回的結(jié)果進(jìn)行了高效驗(yàn)證。文章通過計(jì)算復(fù)雜度分析，驗(yàn)證了該協(xié)議的高效性。

關(guān)鍵詞：外包計(jì)算;Jordan分解;可驗(yàn)證性

中圖分類號(hào)：TP309? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：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 引言

隨著近年來信息技術(shù)的飛速發(fā)展，云外包計(jì)算愈加受到網(wǎng)絡(luò)行業(yè)的關(guān)注[1，2]。云具有非常強(qiáng)大的計(jì)算能力，相比于傳統(tǒng)計(jì)算模式而言，云計(jì)算為用戶明顯地節(jié)省了計(jì)算時(shí)間和開銷，由此云計(jì)算得到了眾多用戶的青睞。

然而，外包云計(jì)算在給云用戶帶來諸多利益的同時(shí)，也存在著許多安全威脅[3]。由于用戶通常無從得知云端是否誠信，所以如何保證外包計(jì)算中用戶隱私信息的安全成為了首要問題。當(dāng)用戶將計(jì)算任務(wù)外包給云時(shí)，原始計(jì)算任務(wù)中所含有的隱私信息可能會(huì)被云知道，使得用戶隱私信息的安全得不到保障。所以，用戶在云環(huán)境下進(jìn)行外包計(jì)算時(shí)，需要對(duì)原計(jì)算問題中包含的隱私信息進(jìn)行加密，進(jìn)而保證用戶隱私數(shù)據(jù)的安全性。其次，云端返回給用戶的結(jié)果的正確性要如何保證。例如，云端為了減少自身開支而得到更多的收益，從而返回給了用戶一個(gè)不正確的結(jié)果，這時(shí)為了保證用戶自身的利益，就需要用戶對(duì)該結(jié)果進(jìn)行驗(yàn)證。

在解決以上兩個(gè)安全威脅的基礎(chǔ)上，還要確保外包計(jì)算的有效性。相比于自行對(duì)計(jì)算任務(wù)進(jìn)行計(jì)算，用戶選擇外包計(jì)算后所用的計(jì)算時(shí)長要明顯地縮短，提高用戶的計(jì)算效率。

針對(duì)矩陣計(jì)算不同方面的問題，許多學(xué)者提出了外包計(jì)算協(xié)議。在文獻(xiàn)[4]中，作者提出了大規(guī)模矩陣乘積的外包計(jì)算協(xié)議，但沒有實(shí)現(xiàn)結(jié)果的可驗(yàn)證性。在文獻(xiàn)[5]中，利用同態(tài)加密技術(shù)實(shí)現(xiàn)了外包計(jì)算協(xié)議的結(jié)果可驗(yàn)證性，但加密過程的復(fù)雜度較高。在文獻(xiàn)[6]中，作者提出了大規(guī)模線性方程組的求解方案，但其操作成本過高。在文獻(xiàn)[7]中，作者亦提出了大規(guī)模矩陣乘積的外包計(jì)算協(xié)議，但基于非方陣的乘積問題，其采用了分類討論思想，加大了外包計(jì)算的復(fù)雜程度。在文獻(xiàn)[8]中，作者提出了大規(guī)模矩陣分解的外包計(jì)算協(xié)議，包括矩陣的特征值分解、SVD分解等，但沒有涉及矩陣Jordan分解的外包計(jì)算協(xié)議。

Jordan分解在“矩陣方程論”“常微分方程”以及“現(xiàn)代控制論”等方面都有著廣泛的應(yīng)用[9]，同時(shí)基于大規(guī)模矩陣Jordan分解需要耗費(fèi)大量的物力財(cái)力。本文提出了大規(guī)模矩陣Jordan分解的外包計(jì)算協(xié)議，該協(xié)議操作簡便，成本低廉，可以減少用戶的計(jì)算成本與開銷。

2 背景知識(shí)

2.1 Jordan分解

給定一個(gè)的實(shí)對(duì)稱矩陣，如果有一個(gè)實(shí)數(shù)和一個(gè)非零向量使下面的方程成立，

（1）

則稱為矩陣的特征值，是與特征值對(duì)應(yīng)的特征向量。

給定一個(gè)一般的矩陣，可以用Jordan分解對(duì)它進(jìn)行如下分解：

（2）

其中，為的可逆矩陣，稱為Jordan塊，，其中是一個(gè)Jordan陣，稱為矩陣的Jordan標(biāo)準(zhǔn)型，它的對(duì)角元素是矩陣的特征值，如果云端不知道矩陣的特征值，那么云端將無從得知該矩陣的Jordan標(biāo)準(zhǔn)型。稱為變換矩陣。

假設(shè)是矩陣的特征值，是對(duì)應(yīng)的特征向量，則可得到如下方程：

對(duì)任意一個(gè)的矩陣，對(duì)其進(jìn)行如下變換：

其中，為單位矩陣，就可以得到矩陣的Jordan標(biāo)準(zhǔn)型和變換矩陣[10]，所以如果云端不知道和是無法得到的。

2.2 排列和δ函數(shù)

利用柯西表示法，本文提出把集合與其自身相互映射，將排列形式表達(dá)如下：

（3）

在這個(gè)表示中，第一行是映射的原像，第二行是在該映射下的像。在（3）中，本文提出可把排列表示為一個(gè)雙射函數(shù)，其值域和定義域均被設(shè)置為集合。

函數(shù)的定義如下：

（4）

在空間中生成一組隨機(jī)數(shù)，則加密后的矩陣可被定義為：

（5）

在（5）中，的值域和定義域均為。由定義可知，在加密矩陣中，每一行每一列都有且只有一個(gè)非零元素，且加密矩陣是標(biāo)準(zhǔn)正交矩陣。

3 系統(tǒng)模型和協(xié)議設(shè)計(jì)相關(guān)知識(shí)

在外包計(jì)算中，根據(jù)敵手的不同，安全計(jì)算模型主要分為兩大類：半誠實(shí)模型和惡意模型[11]。在半誠實(shí)模型中，雖然云遵守協(xié)議，但它會(huì)被動(dòng)地嘗試去獲得用戶原計(jì)算任務(wù)中的隱私信息[11]。在惡意模型中，云不僅會(huì)主動(dòng)地從用戶獲取隱私信息，還有違背協(xié)議的可能性，任意返回一個(gè)錯(cuò)誤的結(jié)果給用戶，并不愿被用戶檢驗(yàn)出來[11]。所以，在惡意的云模型中，用戶對(duì)云端返回的結(jié)果，必須能夠加以驗(yàn)證，以抵抗云欺騙。本文考慮惡意模型。

本文提出設(shè)計(jì)的矩陣Jordan分解外包模型如圖1所示。首先，用戶生成密鑰，利用密鑰來加密原始矩陣，保護(hù)原始矩陣中所包含的隱私信息，得到加密后的加密矩陣;然后，用戶將加密矩陣發(fā)送給云端，利用云端強(qiáng)大的計(jì)算能力和巨大的存儲(chǔ)容量，對(duì)加密矩陣進(jìn)行Jordan分解;云端再將其計(jì)算后得到的加密矩陣的Jordan分解結(jié)果返回給用戶;在接收到從云中返回的結(jié)果后，用戶對(duì)該結(jié)果進(jìn)行驗(yàn)證，如果結(jié)果正確，用戶將其解密以得到原始矩陣的Jordan分解結(jié)果，反之用戶會(huì)對(duì)云返回的結(jié)果表示否定，并再次讓云進(jìn)行計(jì)算。

本文提出的大規(guī)模矩陣Jordan分解外包協(xié)議需要達(dá)到幾項(xiàng)目的[12]。

（1）安全性：用戶的任何隱私信息云都不能獲取。

（2）可驗(yàn)證性：用戶能夠以極大概率驗(yàn)證結(jié)果的正確性，也能夠以不可忽略的概率在云中發(fā)現(xiàn)錯(cuò)誤的結(jié)果。

（3）有效性：與自行計(jì)算矩陣的Jordan分解相比，用戶通過外包計(jì)算，能夠大大減少本地計(jì)算。

本文提出的系統(tǒng)模型共分為五部分，如圖1所示。

（1）密鑰生成：用戶隨機(jī)生成密鑰用于加密原始矩陣。

（2）加密：用戶利用密鑰加密原始矩陣。在將原始矩陣加密成加密矩陣的過程中，本文用到了矩陣乘法和線性映射。

（3）計(jì)算矩陣的Jordan分解：云對(duì)加密矩陣進(jìn)行Jordan分解，并返回結(jié)果給用戶。

（4）驗(yàn)證：對(duì)于云返回的結(jié)果，用戶要進(jìn)行驗(yàn)證。如果驗(yàn)證結(jié)果正確，用戶接受結(jié)果;否則，用戶會(huì)對(duì)返回的結(jié)果表示否定，并要求云再次進(jìn)行計(jì)算。

（5）解密：如果云返回的結(jié)果正確，用戶把矩陣的Jordan標(biāo)準(zhǔn)型、變換矩陣和變換矩陣的逆解密成矩陣的Jordan標(biāo)準(zhǔn)型、變換矩陣和變換矩陣的逆。由此得到原始矩陣的Jordan分解結(jié)果。

4 協(xié)議設(shè)計(jì)

4.1 密鑰生成

本文利用加密矩陣生成密鑰，生成加密矩陣的過程如下：

（6）

其中，為空間產(chǎn)生的隨機(jī)數(shù)?？臻g的定義由本文提出并在背景知識(shí)中進(jìn)行描述，是雙射函數(shù)。

4.2 加密

在矩陣的Jordan分解外包中，用戶的目的是得到矩陣的Jordan標(biāo)準(zhǔn)型、變換矩陣以及變換矩陣的逆。同時(shí)，用戶希望矩陣本身，以及它的Jordan標(biāo)準(zhǔn)型和變換矩陣都不會(huì)暴露在云中。在本文中，提出要對(duì)用戶的隱私信息進(jìn)行加密，也就是對(duì)原始矩陣以及原始矩陣 的Jordan標(biāo)準(zhǔn)型和變換矩陣進(jìn)行加密，由2.1節(jié)可知，本文提出只需對(duì)原始矩陣以及原始矩陣的特征值和特征向量進(jìn)行加密。

（1）在矩陣Jordan分解外包過程中，如果用戶直接將原始矩陣發(fā)送到云，那么矩陣中的隱私信息可能會(huì)暴露到云中。為了不泄露的隱私信息，用戶先從實(shí)數(shù)集R中隨機(jī)選擇，再對(duì)原始矩陣進(jìn)行如下加密：

（7）

根據(jù)以上加密方法，可知矩陣與矩陣的特征向量相同，且的特征值與的特征值之間的關(guān)系如下：

（8）

上式證明如下：

設(shè)為矩陣的一個(gè)特征值，且是與特征值對(duì)應(yīng)的特征向量，于是有：

（9）

證畢。

由于云對(duì)的確切值無從得知，如果用戶把 發(fā)送到云，那么此時(shí)便保護(hù)了矩陣本身和其特征值中包含的隱私信息，但矩陣和矩陣具有相同的特征向量，也就是說，矩陣的特征向量中包含的隱私信息沒有得到保護(hù)。因此，還要加密的特征向量。

（2）現(xiàn)在，本文對(duì)矩陣的特征向量進(jìn)行加密。首先，令

（ 是標(biāo)準(zhǔn)正交矩陣）. （10）

則（9）式可以表示為：

（11）

（11）式兩邊同時(shí)乘以矩陣 ：

（12）

于是（11）式可以寫成：

（13）

其中，此時(shí)通過加密，原始矩陣轉(zhuǎn)換成了加密矩陣，其關(guān)系可以表示為。由（10）式可知，加密矩陣隱藏了矩陣的特征向量中包含的隱私信息。

經(jīng)上述加密，完成了對(duì)用戶的隱私信息的保護(hù)。這時(shí)，將加密矩陣發(fā)送給云端，云端對(duì)其進(jìn)行Jordan分解，并將分解結(jié)果返回給用戶。此時(shí)，用戶得到了加密矩陣的Jordan標(biāo)準(zhǔn)型、變換矩陣以及變換矩陣的逆，分別為：

矩陣的Jordan標(biāo)準(zhǔn)型為，

矩陣的變換矩陣為：，

矩陣的變換矩陣的逆為。

其中，是一個(gè)Jordan塊，是一個(gè)Jordan陣，的對(duì)角元素為矩陣的特征值;為型矩陣，是一個(gè)可逆的變換矩陣。

在加密過程中，本文使用到了加密矩陣，目的是確保只要云返回了一個(gè)標(biāo)準(zhǔn)正交的特征向量，那么用戶對(duì)其解密后也會(huì)得到標(biāo)準(zhǔn)正交的特征向量，證明如下：

假設(shè)和是云端返回的矩陣的兩個(gè)標(biāo)準(zhǔn)正交的特征向量，用戶對(duì)其進(jìn)行解密，得到的兩個(gè)特征向量滿足和，則有即和是標(biāo)準(zhǔn)的;又因，說明 和是正交的，所以和也是標(biāo)準(zhǔn)正交的。

證畢。

4.3 驗(yàn)證

對(duì)于云端返回給用戶的結(jié)果，用戶有必要對(duì)結(jié)果進(jìn)行驗(yàn)證。為了保證結(jié)果、和是正確的，用戶首先要檢查是否為Jordan陣。如果不是Jordan陣，則用戶認(rèn)為結(jié)果不正確。如果為Jordan陣，那么用戶驗(yàn)證下式是否正確：

（14）

這相當(dāng)于驗(yàn)證以下公式是否成立：

（15）

驗(yàn)證方法如下：

（1）隨機(jī)選擇一個(gè)的向量，中每個(gè)元素均從集合中隨機(jī)選擇;

（2）用戶計(jì)算;

（3）重復(fù)上述兩步驟，共進(jìn)行輪測(cè)試，在 輪測(cè)試中，如果均有，則用戶接受結(jié)果;反之，用戶認(rèn)為結(jié)果錯(cuò)誤，并要求云再次進(jìn)行計(jì)算。

4.4 解密

如果用戶驗(yàn)證云端返回的結(jié)果是正確的，那么將該結(jié)果進(jìn)行解密，將其轉(zhuǎn)化為矩陣的Jordan標(biāo)準(zhǔn)型、變換矩陣和變換矩陣的逆，解密過程如下：

（16）

通過（16），可得到原始矩陣的Jordan標(biāo)準(zhǔn)型、變換矩陣以及變換矩陣的逆：

（17）

然后得到，

（18）

于是，用戶得到了原始矩陣的Jordan分解。

5 協(xié)議分析

5.1 安全性分析

將原始矩陣加密為矩陣，其中為加密矩陣，是一個(gè)由實(shí)數(shù)集R生成的隨機(jī)數(shù)。首先，對(duì)原始矩陣進(jìn)行加密，即。假設(shè)云端知道矩陣，如果云端想使用暴力手段通過來獲取矩陣，那么它也需要猜測(cè)次，其中表示實(shí)數(shù)集R中的元素個(gè)數(shù)。然后，再利用加密矩陣對(duì)矩陣進(jìn)行加密，即。本次加密使得矩陣中的元素被重新排列成以下形式：

（19）

由（19）可知，的元素被函數(shù)進(jìn)行了重排列以及被縮小了。其中，有種可能，有兩種可能。此時(shí)云端即使知道矩陣，并想由矩陣得到矩陣，其概率也僅有，所以在很大時(shí)，其概率可忽略不計(jì)。

用戶將加密矩陣發(fā)送給云端后，云對(duì)矩陣進(jìn)行Jordan分解，所以對(duì)于矩陣的特征值和與其對(duì)應(yīng)的特征向量，云是知道的。下面分析協(xié)議如何對(duì)矩陣的特征值和特征向量進(jìn)行保護(hù)。

矩陣與矩陣兩者的特征值之間的關(guān)系是（8）式。如果不知道隨機(jī)實(shí)數(shù)，云就無法利用得到。

矩陣與矩陣兩者的特征向量之間的關(guān)系是（10）式。顯然，加密矩陣很好地保護(hù)了特征向量。根據(jù)前面的討論，云端若想要得到矩陣，其概率為，所以在很大時(shí)，云沒有辦法從特征向量解密出。

根據(jù)以上分析，可以認(rèn)為用戶的隱私信息都被很好地保護(hù)了。

5.2 結(jié)果可驗(yàn)證性分析

本節(jié)對(duì)本文提出的外包協(xié)議的結(jié)果可驗(yàn)證性進(jìn)行分析。

云端返回的結(jié)果正確與否，通過該協(xié)議，都可以成功得到驗(yàn)證。

如果云返回給用戶一個(gè)正確的結(jié)果，則等于矩陣，所以每輪檢查中，不論取何值，都有，即可以驗(yàn)證任何正確的結(jié)果。

如果云返回給用戶一個(gè)錯(cuò)誤的結(jié)果，用戶也會(huì)有很高的概率發(fā)現(xiàn)云端的這種不誠實(shí)行為。當(dāng)云端返回的矩陣不是Jordan陣時(shí)，用戶直接認(rèn)為結(jié)果錯(cuò)誤，因此不可能接收錯(cuò)誤結(jié)果;當(dāng)云端返回的矩陣為Jordan陣時(shí)，本文提出的協(xié)議有很高的抵抗錯(cuò)誤結(jié)果的概率。本文采用的驗(yàn)證算法的誤差分析表明，錯(cuò)誤結(jié)果通過驗(yàn)證的概率小于[13]，即錯(cuò)誤結(jié)果通過驗(yàn)證的概率是隨驗(yàn)證次數(shù) 的增加呈指數(shù)遞減的。因此，如果選擇的值足夠大，那么從云中返回的任何錯(cuò)誤結(jié)果能夠通過驗(yàn)證的可能性可以忽略不計(jì)。

5.3 有效性分析

與直接計(jì)算矩陣Jordan分解相比，用戶可以通過外包計(jì)算來減輕計(jì)算負(fù)擔(dān)。本文提出的系統(tǒng)模型需要用戶執(zhí)行四種算法，即密鑰生成、加密、驗(yàn)證和解密。以下分別分析了四種算法的計(jì)算復(fù)雜度，驗(yàn)證了外包協(xié)議的有效性。

（1）密鑰生成。生成加密矩陣就是該算法的所有任務(wù)，其算法復(fù)雜度為。

（2）加密算法。加密算法將原始矩陣加密為矩陣，其中。在此加密過程中，計(jì)算加密矩陣與原始矩陣的乘法是最為耗時(shí)的運(yùn)算。由（19）式可得，其算法復(fù)雜度為。

（3）驗(yàn)證算法。每輪隨機(jī)檢測(cè)中，用戶都要計(jì)算和，矩陣和向量的乘法是其中最復(fù)雜的計(jì)算操作，它的算法復(fù)雜度是。因?yàn)轵?yàn)證算法需進(jìn)行輪隨機(jī)檢測(cè)，所以驗(yàn)證算法的總體計(jì)算復(fù)雜度是。相比于大型矩陣，遠(yuǎn)小于，即，所以驗(yàn)證算法的計(jì)算復(fù)雜度是。

（4）解密算法。如果由云返回的、和的結(jié)果正確，則用戶將它解密并得到原始矩陣的、和，解密算法如下：

最耗時(shí)的操作是計(jì)算，其計(jì)算復(fù)雜度為。

一般來說，所有用戶需要執(zhí)行的計(jì)算，其計(jì)算復(fù)雜度是。與之對(duì)比，矩陣Jordan分解直接計(jì)算需要的計(jì)算復(fù)雜度。如果足夠大，與之間會(huì)有很大的區(qū)別。因此，通過外包計(jì)算，用戶可以節(jié)省大量的計(jì)算成本。

6 結(jié)束語

本文設(shè)計(jì)了一個(gè)安全的、結(jié)果可驗(yàn)證的、高效的大規(guī)模矩陣Jordan分解的外包協(xié)議，采用了高效的加密技術(shù)，保證了用戶隱私信息的安全。同時(shí)，本文設(shè)計(jì)了一種高效的驗(yàn)證算法，以確保用戶能夠高效地驗(yàn)證云端返回的結(jié)果是否正確。矩陣的Jordan分解在科學(xué)領(lǐng)域有著廣泛的應(yīng)用，還需要進(jìn)一步深入研究。

基金項(xiàng)目：

1.國家自然科學(xué)基金（項(xiàng)目編號(hào)：61370187）;

2.北京市教委科技計(jì)劃項(xiàng)目（項(xiàng)目編號(hào)：KM201510009013）。

參考文獻(xiàn)

[1] 劉文武.云計(jì)算的特點(diǎn)及重點(diǎn)應(yīng)用領(lǐng)域研究[J].才智， 2014（30）.

[2] 郁德強(qiáng)，王燕妮，李華.一種基于云計(jì)算的服務(wù)外包模式：云外包[J].情報(bào)理論與實(shí)踐，2012，35（8）：97-100.

[3] 馮登國，張敏，張妍，等.云計(jì)算安全研究[J].軟件學(xué)報(bào)， 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] 楊波，武朵朵，來齊齊.矩陣乘積的高效可驗(yàn)證安全外包計(jì)算[J].密碼學(xué)報(bào)，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標(biāo)準(zhǔn)型在矩陣分析中的作用探討[J].滇西科技師范學(xué)院學(xué)報(bào)，2015（1）：119-124.

[10] 顧江永.矩陣Jordan標(biāo)準(zhǔn)化的證明及初等求法[J].長江大學(xué)學(xué)報(bào)（自科版），2009，6（3）：135-136.

[11] 郭姝.云計(jì)算中的外包計(jì)算的研究[D].中國科學(xué)院大學(xué)， 2013.

[12] Duncan S.WONG.可驗(yàn)證安全外包矩陣計(jì)算及其應(yīng)用[J].中國科學(xué)：信息科學(xué)，2013，43（7）：842-852.

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