陳立軍，張 屹，陳孝如

(廣州軟件學(xué)院 軟件工程系，廣東 廣州 510990)

0 引 言

張量概念是矢量和矩陣概念的推廣，標(biāo)量是零階張量，矢量是一階張量，矩陣是二階張量，三階或階數(shù)更高的張量被稱為高階張量，張量也可以被視為多維數(shù)組，一般所說的張量是高階張量。張量分解從本質(zhì)上來說是矩陣分解的高階泛化，矩陣分解有3個(gè)很明顯的用途，即降維處理、缺失數(shù)據(jù)填補(bǔ)和隱性關(guān)系挖掘，其實(shí)張量分解也能夠很好地滿足這些用途。20世紀(jì)60年代以來多路數(shù)據(jù)分析中已有數(shù)十年歷史的數(shù)學(xué)技術(shù)[1]，張量分解廣泛應(yīng)用于從信號(hào)處理到機(jī)器學(xué)習(xí)領(lǐng)域[2]；張量計(jì)算最近成為大數(shù)據(jù)處理的一種有前途的解決方案，因?yàn)樗軌驅(qū)Ω鞣N數(shù)據(jù)進(jìn)行建模，例如圖形、表格、離散和連續(xù)數(shù)據(jù)[3]，滿足不同數(shù)據(jù)準(zhǔn)確性或缺失數(shù)據(jù)的算法[4]，并為大數(shù)據(jù)速度提供實(shí)時(shí)分析，例如流分析[5]，并且能夠捕獲大量數(shù)據(jù)中復(fù)雜的關(guān)聯(lián)結(jié)構(gòu)，并為許多大數(shù)據(jù)分布式應(yīng)用程序生成有價(jià)值的見解[6]。另一方面，張量網(wǎng)絡(luò)計(jì)算在數(shù)值社區(qū)中是一種成熟的技術(shù)，該技術(shù)提供了前所未有的大規(guī)模科學(xué)計(jì)算，其性能可與稀疏網(wǎng)格方法等競(jìng)爭(zhēng)技術(shù)相媲美[7]，張量網(wǎng)絡(luò)(TN)表示稀疏互連的低階核心張量(通常為3階或4階張量)中的數(shù)據(jù)或張量塊。TN于20世紀(jì)90年代首次在量子物理學(xué)中被發(fā)現(xiàn)，以簡(jiǎn)約的方式捕獲和模擬糾纏量子粒子之間的多尺度相互作用[8]。TN于21世紀(jì)初獨(dú)立地被數(shù)值社區(qū)重新發(fā)現(xiàn)，并發(fā)現(xiàn)了從科學(xué)計(jì)算到電子設(shè)計(jì)自動(dòng)化的廣泛應(yīng)用[9]。

然而，大數(shù)據(jù)可能包含專有信息或個(gè)人信息，例如個(gè)人的位置、健康、情緒和偏好信息，需要適當(dāng)?shù)募用芎驮L問控制保護(hù)用戶的隱私。

TN以犧牲安全性為代價(jià)增加了多方計(jì)算的功能和性能，與基于模算術(shù)并在定點(diǎn)表示上工作的經(jīng)典加密技術(shù)相反，它自然支持浮點(diǎn)和定點(diǎn)運(yùn)算，此外，與加密計(jì)算技術(shù)不同，TN允許進(jìn)一步壓縮，加密計(jì)算技術(shù)通常會(huì)增加存儲(chǔ)和通信開銷，因此，這通常會(huì)使加密計(jì)算無法用于大數(shù)據(jù)處理；而加密之前的數(shù)據(jù)壓縮通常會(huì)使數(shù)據(jù)表示失去一些功能，例如對(duì)原始數(shù)據(jù)的加密計(jì)算。憑借分布式TN在大規(guī)?？茖W(xué)計(jì)算和大數(shù)據(jù)分析中令人印象深刻的記錄，本文提出了一種基于張量網(wǎng)絡(luò)的新型密鑰共享方案，以保護(hù)大數(shù)據(jù)中的隱私安全。

1 相關(guān)工作

密鑰共享方案以較高的存儲(chǔ)和通信成本為代價(jià)，提供了信息理論的安全性，本文回顧了實(shí)際的密鑰共享方案。Krawczyk[10]提出了第一個(gè)計(jì)算密鑰共享方案，采用隨機(jī)生成密鑰的對(duì)稱加密方法對(duì)數(shù)據(jù)進(jìn)行加密，利用Rabin的信息分散算法將加密后的數(shù)據(jù)分成多個(gè)塊，而加密或解密密鑰使用Shamir的密鑰共享方案進(jìn)行分割，這樣收集一定的閾值塊數(shù)就足以進(jìn)行密鑰重構(gòu)，從那時(shí)起，計(jì)算密鑰共享方案的許多不同版本被提出，以提高數(shù)據(jù)安全性、數(shù)據(jù)冗余抵抗、數(shù)據(jù)完整性、碎片大小和不同機(jī)器可信度的管理[11]。由Rivest[12]引入的AONT解決了密鑰暴露問題，它通過在片段之間建立依賴關(guān)系，這樣只獲取密鑰而不獲取所有片段就不會(huì)導(dǎo)致立即的信息泄露。此外，使用新的加密密鑰僅對(duì)一個(gè)數(shù)據(jù)片段進(jìn)行重新加密，大大降低了傳輸成本[13]，然而，這種加密數(shù)據(jù)的用途是非常有限的，如搜索、更新和計(jì)算都必須重建原始數(shù)據(jù)[14]。

數(shù)據(jù)匿名化可能是目前廣泛采用的最簡(jiǎn)單的低成本解決方案，用于在企業(yè)內(nèi)部和跨企業(yè)之間為各種應(yīng)用程序安全共享數(shù)據(jù)。數(shù)據(jù)匿名化技術(shù)包括刪除個(gè)人可識(shí)別信息(例如使用哈?；蜓诖a技術(shù))和數(shù)據(jù)隨機(jī)或擾動(dòng)技術(shù)(例如隨機(jī)噪聲、置換和轉(zhuǎn)換)[15]。隨機(jī)組件或函數(shù)必須精心設(shè)計(jì)，以保存訓(xùn)練數(shù)據(jù)集中的重要信息，并確保模型性能[16]。最近一項(xiàng)關(guān)于不同隱私度量的系統(tǒng)調(diào)查可以在文獻(xiàn)[17]中找到，這些隱私度量基于信息理論、數(shù)據(jù)相似性、不可區(qū)分性度量以及對(duì)手的成功概率，為特定設(shè)置選擇合適的隱私度量取決于對(duì)抗模型、數(shù)據(jù)源、可用于計(jì)算度量的信息以及可度量的屬性。差分隱私(DP)[18]是一個(gè)數(shù)學(xué)框架，用于嚴(yán)格量化在統(tǒng)計(jì)數(shù)據(jù)庫(kù)或機(jī)器學(xué)習(xí)操作期間泄露的信息量[19]，DP是一種已被業(yè)界廣泛采用的已被證明的隱私保護(hù)技術(shù)。最近一種有希望的數(shù)據(jù)匿名化方法是使用生成機(jī)器學(xué)習(xí)模型和計(jì)算機(jī)模擬，該數(shù)據(jù)類似于原始數(shù)據(jù)集中觀察到的統(tǒng)計(jì)分布或行為，這些模型是特定于應(yīng)用程序的(即依賴于訓(xùn)練數(shù)據(jù)集或物理模型)，任何對(duì)合成數(shù)據(jù)的分析都必須在真實(shí)數(shù)據(jù)集上進(jìn)行驗(yàn)證。

雖然隱私保護(hù)矩陣和張量分解技術(shù)在文獻(xiàn)中已經(jīng)得到了很好的研究[20]，但尚未提出用于大數(shù)據(jù)隱私保護(hù)的分布式張量網(wǎng)絡(luò)表示和計(jì)算方法，與數(shù)據(jù)匿名化技術(shù)不同，張量分解是完全可逆和可壓縮的，重構(gòu)精度可以是有損的，也可以是接近無損的。與數(shù)據(jù)分割不同，TN不需要代理服務(wù)器來管理元數(shù)據(jù)，但與計(jì)算密鑰共享方案相比，它提供了更好的分解數(shù)據(jù)的效用，但代價(jià)是更高的特權(quán)泄漏。為了處理大數(shù)據(jù)，隨機(jī)映射或投影技術(shù)利用一個(gè)投影矩陣，如高斯和隨機(jī)正交矩陣，在應(yīng)用張量分解之前，將數(shù)據(jù)張量投影到更小的張量大小。隨機(jī)抽樣技術(shù)，近似整個(gè)數(shù)據(jù)張量，現(xiàn)有隨機(jī)映射和隨機(jī)抽樣算法對(duì)于大數(shù)據(jù)非常有用，張量分解塊通常是有損壓縮以至重建精度，這不同于本文提出的隨機(jī)張量分解，分解張量塊的隨機(jī)性也受到投影矩陣的分布和采樣過程的限制，以保證較小的誤差范圍，而本文提出的算法在張量分解算法中，通過在序列矩陣分解過程中應(yīng)用大而可控的擾動(dòng)，將大數(shù)據(jù)的復(fù)雜結(jié)構(gòu)信息隨機(jī)分散到張量核中，與隨機(jī)投影或映射算法相比，該算法的時(shí)間消耗也很低，可以很容易地適應(yīng)于現(xiàn)有的張量算法。盡管如此，所提出的張量擾動(dòng)技術(shù)可以很容易地與現(xiàn)有的隨機(jī)投影或采樣算法相結(jié)合，用于大數(shù)據(jù)處理和隱私保護(hù)。張量分解在大數(shù)據(jù)降維中得到了廣泛的應(yīng)用，但是對(duì)于張量網(wǎng)絡(luò)編碼方案的研究相對(duì)滯后，在撰寫本文時(shí)僅有少量的文獻(xiàn)[21，22]。

2 威脅模型和安全

客戶端的安全存儲(chǔ)和計(jì)算外包給一組不可信但不相互勾結(jié)的服務(wù)器S1，S2，…，Sn，客戶端在初始設(shè)置階段，在服務(wù)器之間秘密共享它們的輸入，然后服務(wù)器的存儲(chǔ)(例如加密)、計(jì)算和通信使用分散TN計(jì)算協(xié)議，這些服務(wù)器運(yùn)行在不同的軟件堆棧上，以最大限度地減少它們受到惡意軟件攻擊的機(jī)會(huì)，并可以在不同的子組織下操作，以最大限度地減少內(nèi)部威脅。在云場(chǎng)景下，密鑰共享可以被分發(fā)到同一個(gè)云服務(wù)提供商(CSP)提供的多個(gè)虛擬實(shí)例或不同的云(例如多云或混合云環(huán)境)中。本文假設(shè)一個(gè)半誠(chéng)實(shí)的對(duì)手a，他能夠在任何時(shí)間損壞客戶機(jī)的任何子集和最多n-1臺(tái)服務(wù)器，與加密的數(shù)據(jù)處理不同，本文的安全定義要求對(duì)手只了解客戶端輸入的部分信息，而不知道過程中的敏感信息，基于信息理論和基于相似性的隱私度量對(duì)隱私泄露進(jìn)行計(jì)算，基于TN的密鑰共享方案對(duì)每個(gè)服務(wù)器都是不對(duì)稱的，即每個(gè)服務(wù)器都包含特定于索引的信息，如第3節(jié)和第4節(jié)所示，每一個(gè)TN表示都需要高數(shù)據(jù)復(fù)雜度才能在多方設(shè)置中保護(hù)隱私。

3 基于分布式張量網(wǎng)絡(luò)的密鑰共享方案

在本節(jié)中，提出了一種基于分布式張量網(wǎng)絡(luò)(TN)表示的密鑰共享方案，以實(shí)現(xiàn)大數(shù)據(jù)存儲(chǔ)、通信、共享和計(jì)算的無縫安全。TN在語義層對(duì)數(shù)據(jù)塊進(jìn)行分解，每個(gè)包含潛在信息的分解張量塊隨機(jī)分布在多個(gè)不相互勾結(jié)的服務(wù)器上，多路分量分析的成功可以歸因于有效的矩陣和張量分解算法的存在，以及通過引入稀疏性、正交性、平滑性和非負(fù)性[23]等約束條件提取具有物理意義分量的可能性。高階張量分解一般是非唯一的，每個(gè)張量核或因子矩陣包含索引特定的信息，由于分解的非唯一性，這些信息是不可鏈接和不可解釋的，因此它們通常用于降維和壓縮計(jì)算。

本文描述了在多方計(jì)算設(shè)置下的幾種基本張量模型，以增強(qiáng)原始張量的隱私保護(hù)，提出了基于擾動(dòng)技術(shù)(一種數(shù)據(jù)處理和分析的方法，它可用于對(duì)離散事件動(dòng)態(tài)系統(tǒng)的仿真模型進(jìn)行結(jié)構(gòu)或參數(shù)優(yōu)化)的隨機(jī)算法，將每個(gè)數(shù)據(jù)塊分解為隨機(jī)張量塊，每個(gè)張量塊在執(zhí)行張量分布后，可以使用張量舍入算法重新隨機(jī)化，多線性運(yùn)算降低了張量秩復(fù)雜度，提高了存儲(chǔ)和計(jì)算效率。

塔克分解(TD)[24]是矩陣奇異值分解(SVD)在高維張量中的一種自然擴(kuò)展，TD利用核心張量G捕捉潛在因子U(來自張量的模態(tài)矩陣化SVD)之間的相互作用，這個(gè)核心張量G反映了原始張量的每個(gè)模態(tài)的主要子空間變化并對(duì)其進(jìn)行排序，對(duì)于三階張量A∈RI1×I2×I3，張量分解(TD)以通過不同的張量運(yùn)算定義為

A(i1，i2，i3)?GX1X2X3

vec(A)?(3?21vec(G)

(1)

G∈RR1×R2×R3是一個(gè)3維核心張量，Uk∈RI1×Rk，k∈ {1，2，3} 是因子矩陣，Xn是n模乘積，?是張量積，vec(·)是向量化算子[24]，〈·〉表示存儲(chǔ)在服務(wù)器中的私有共享，G是一個(gè)共享張量核心，用于在服務(wù)器之間交換以執(zhí)行張量計(jì)算方案。TD是非唯一的，因?yàn)闈撛谝蜃涌梢栽诓挥绊懼亟ㄕ`差的情況下旋轉(zhuǎn)，然而，TD產(chǎn)生了一個(gè)良好張量的平方誤差低秩近似，當(dāng)G是超對(duì)角線時(shí)，規(guī)范多元(CP)分解是TD的一個(gè)特例。CP由于其唯一性和易于解釋而在信號(hào)處理中非常流行，然而，這些特性也使得CP不適合隱私保護(hù)。

本文提出了分層塔克(HT)分解[25]以減少TD的內(nèi)存需求，HT可以很好地近似高階張量(N?3)，而不會(huì)受到維數(shù)災(zāi)難的影響，HT基于二叉樹層次結(jié)構(gòu)遞歸地分割張量的模式，使得每個(gè)節(jié)點(diǎn)包含模式的子集，因此，HT需要張量矩陣化二叉樹的先驗(yàn)知識(shí)，HT定義如下

Ut?(Ut?Utr)〈Bt〉t

(2)

Bt是重構(gòu)為RtRtr×Rt矩陣的“轉(zhuǎn)移”核心張量(或內(nèi)部節(jié)點(diǎn))，Ut包含原始張量的Rt左奇異向量，t，tr分別對(duì)應(yīng)左節(jié)點(diǎn)和右子節(jié)點(diǎn)，葉節(jié)點(diǎn) 〈U1〉1，〈U2〉2…〈UN〉N包含潛在因子，應(yīng)用分布式存儲(chǔ)以確保隱私保護(hù)，當(dāng)應(yīng)用程序在物理模式上提供直觀和自然的層次結(jié)構(gòu)時(shí)，HT特別有用。

張量列(TT)[26]將一個(gè)給定張量分解成一系列或級(jí)聯(lián)的連通核張量，因此TT可以解釋為HT的一種特殊情況，TT核心張量通過一個(gè)共同的簡(jiǎn)約模式Rk連接，TT的定義如下

A(i1，i2，i3)?〈G[i1]〉1×〈G[i2]〉2×〈G[i3]〉3

(3)

其中，G[ik]是一個(gè)Rk-1×Rk矩陣，R0=R3=1，這個(gè)矩陣是乘法操作，TT格式及其變體非常有用，因?yàn)樗鼈儗?duì)許多分布式、多線性運(yùn)算[27]具有靈活性，并且可以將其它基本張量模型(如CP、TD、HT)轉(zhuǎn)換為TT格式[23]，類似的性質(zhì)也適用于張量鏈或張量環(huán)格式(TR)[28]，TR是TT格式的線性組合，即R1=R3>1，TR表示比TT表示更強(qiáng)大[28]。

3.1 存儲(chǔ)的復(fù)雜性

表1列出了這里提到的不同TN格式的存儲(chǔ)復(fù)雜性和邊界，低秩近似在張量網(wǎng)絡(luò)計(jì)算中非常有用，對(duì)于一些具有低秩結(jié)構(gòu)的高相關(guān)張量數(shù)據(jù)結(jié)構(gòu)或函數(shù)形式，在節(jié)省存儲(chǔ)、通信和計(jì)算成本的同時(shí)，精度損失可以忽略不計(jì)。塔克格式不適用于N>5張量，因?yàn)楹诵膹埩縂的條目數(shù)以N為指數(shù)尺度，因此在處理高階張量[23]時(shí)，塔克格式的存儲(chǔ)和計(jì)算是不實(shí)用的。TT格式及其變體既具有穩(wěn)定的數(shù)值特性，又具有合理的存儲(chǔ)復(fù)雜性。此外，TT允許控制TT分解和TT舍入算法中的近似誤差。

表1 不同張量格式的存儲(chǔ)復(fù)雜度

3.2 圖形化表示

TN可以用一組由邊相連的節(jié)點(diǎn)來表示，邊對(duì)應(yīng)收縮模態(tài)，而不從一個(gè)張量到另一個(gè)張量的線對(duì)應(yīng)開放(物理)模態(tài)，這對(duì)整個(gè)TN的總階數(shù)有貢獻(xiàn)，圖1顯示了不同TN表示的圖形表示，在張量上進(jìn)行的數(shù)學(xué)運(yùn)算(例如張量收縮和重塑)可以用張量的圖形簡(jiǎn)單直觀地表達(dá)，而不用顯式地使用復(fù)雜的數(shù)學(xué)表達(dá)式，連接到節(jié)點(diǎn)的線數(shù)表示張量順序、等級(jí)和模式大小標(biāo)記在邊緣上。

圖1 不同張量網(wǎng)絡(luò)(TN)分解的圖形表示

基于隨機(jī)張量分解的密鑰共享生成，算法1、2、3、4給出了本文提出的隨機(jī)rTD、rHT、rTT-SVD、rTR-SVD算法，通過應(yīng)用擾動(dòng)技術(shù)將大數(shù)據(jù)中的結(jié)構(gòu)信息隨機(jī)分散到張量核中，將n維張量分解為隨機(jī)的秘密份額。算法1基于文獻(xiàn)[29]中提出的高階奇異值分解(HOSVD)對(duì)一個(gè)張量的每個(gè)模態(tài)進(jìn)行SVD，提取潛在因子，然后得到核心張量，獲取潛在因子之間復(fù)雜的相互作用；算法2基于輸入張量的二叉樹矩陣化，遞歸地將rTD應(yīng)用于每個(gè)張量節(jié)點(diǎn)；算法3和算法4分別基于文獻(xiàn)[26，28]中提出的TT-SVD和TR-SVD算法，TT-SVD和TR-SVD在張量上進(jìn)行順序SVD分解，得到TT和TR表示。圖2(詳見算法1)和圖3(詳細(xì)信息參見算法3)顯示了提出的rTD和rTT-SVD算法的圖形表示，在執(zhí)行算法1、2、3中的每一步SVD后，采用隨機(jī)離散。為了在壓縮和隨機(jī)性之間取得平衡，最大(隨機(jī))擾動(dòng)應(yīng)該在基于每個(gè)奇異值的大小的某個(gè)閾值δ內(nèi)，共享再生可以通過本文提出的基于文獻(xiàn)[26]的隨機(jī)TT四舍五入算法(見算法5)來完成，所有算法都在分布式服務(wù)器上以TT格式進(jìn)行，但這并不推薦嵌入現(xiàn)有張量分解算法，因此計(jì)算復(fù)雜度沒有增加太多，只進(jìn)行少量張量核收縮和SVD，存儲(chǔ)擾動(dòng)因子的內(nèi)存大小被認(rèn)為可以忽略不計(jì)。

圖2 3階張量的rTD算法圖形表示

算法1:提出的基于高階SVD (HOSVD) 的隨機(jī)塔克分解 (rTD)

輸入:張量A∈Rl1×l2×…×IN和矩陣R1,R2…RN的秩。

初始化:G1=A;

修改從多重線性SVD 或N模式SVD:

fork=1 toNdo

[Uk,Sk,Vk]←tSVD(Gk(k),Rtrunc.=Rk);

用均勻分布打賭生成對(duì)角擾動(dòng)矩陣

閾值δ和1,Δk～U([δ,1]);

End

隨機(jī)化第一個(gè)TD因子矩陣

算法2：通過遞歸節(jié)點(diǎn)式rTD提出的隨機(jī)分層塔克(rHT)分解。

輸入:張量A∈Rl1×l2×…×IN,矩陣R1,R2…RN的秩,和二叉樹T的矩陣化。

U1←A(1);

從樹T的根節(jié)點(diǎn)開始,選擇一個(gè)節(jié)點(diǎn)t:

設(shè)置t1和tr為t響應(yīng)的左、右子節(jié)點(diǎn);

Ift1is not singleton:Rt1←Rfull;

Iftris not singleton:Rtr←Rfull;

Ut←reshape(Ut,[tl,tr,t]);

在tl和tr上遞歸,直到tl和tr是單例。

算法3：隨機(jī)張量訓(xùn)練-奇異值分解(rTT-SVD)算法。

輸入:張量A∈Rl1×l2×…×lN和錯(cuò)誤的閾值ε。

初始化:TT的非零奇異值個(gè)數(shù)R0=1; 擾動(dòng)閾值δ;

擾動(dòng)參數(shù)δε=√N(yùn)ε-1;

張量的形狀,[I1,I2,…,IN]←shape(A);

Mode-1:張量A的矩陣化,M1←A(1);

序列(SVD+隨機(jī)離散度):

fork=1toN-1do

擾動(dòng)奇異值分解,[Uk,Sk,Vk]←tSVD(Mk,δrel.=δε);

TT的非零奇異值個(gè)數(shù),Rk←shape(Sk,1);

用均勻網(wǎng)格生成對(duì)角擾動(dòng)矩陣

閾值之間的距離δ和1,Δk～U([δ,1]);

End

隨機(jī)分配第一個(gè)TT-core:

R1←shape(S1,1); Δ1～U([δ,1]);

算法4：隨機(jī)張量環(huán)奇異值分解 (rTR-SVD)。

輸入:張量A∈RI1×I2×…×IN和錯(cuò)誤的閾值ε。

初始化:使得近似誤差δ;

準(zhǔn)備第一個(gè)TR核心:

張量形狀,[I1,I2,…,IN]←shape(A);

Mode-1:張量A的矩陣化,M1←A(1);

擾動(dòng)奇異值分解,[U1,S1,V1]←tSVD(M1,δrel.=δ1);

Δ1～U([δ,1]); Split TT-ranksR0,R1:

Set TT-rank,RN←R0;

順序(SVD+隨機(jī)離散):

fork=2 toN-1do

[Uk,Sk,Vk]←tSVD(Mk,δrel.=δk);

Rk←shape(Sk,1); Δk～U([δ,1]);

End

建造最后一個(gè)核心,

隨機(jī)選擇第一個(gè)TR核心:

R1←shape(S1,1); Δ1～U([δ,1]);

算法5：隨機(jī)TT-rounding(rTTrounding)以減小TT-cores的大小

輸入:TT核的和N個(gè)存儲(chǔ)在服務(wù)器上的順序張量s,A=〈G1〉1〈G2〉2…〈GN-1〉N-1〈GN〉N和ε。

初始化:TT的非零奇值班的個(gè)數(shù) 〈R0〉1=1; 〈RN〉N=1;

擾動(dòng)閾值δ;

從右到左的QR正交化:

fork=Nto 2do

[〈Rk-1〉k,〈Ik〉k,〈Rk〉k]←shape(〈Gk〉k);

〈Gk〉k←reshape(〈Gk〉k,[Rk-1,IkRk]);

End

從左到右(SVD壓縮+隨機(jī)分散):

[〈R0〉1,〈I1〉1,〈R1〉1]←shape(〈G1〉1);

fork= 1 toN-1do

〈Gk〉k←reshape(〈Gk〉k,[Rk-1,Ik,Rk]);

[〈Uk〉k,〈Sk〉k,〈Vk〉k]←tSVD(〈Gk〉k,δrel.=δε);

〈Rk〉k←shape(〈Sk〉k,1); 〈Δk〉k～U(δ,1);

End

3.3 隱私的安全性

基于隨機(jī)TN格式的密鑰共享的正確性是明顯的，如果數(shù)據(jù)允許低秩結(jié)構(gòu)，張量表示是可壓縮的，隨機(jī)張量分解算法將大數(shù)據(jù)中復(fù)雜的結(jié)構(gòu)信息隨機(jī)分解為不同的張量核或子塊，對(duì)于復(fù)雜的相關(guān)結(jié)構(gòu)，即奇異值被緊密分離時(shí)，小擾動(dòng)下SVD分解的敏感性是眾所周知的[30]。此外，所提出的算法通過不影響重構(gòu)精度來隨機(jī)化TN分解，隱私泄露受每個(gè)指標(biāo)的張量秩復(fù)雜度的限制，即具有足夠高秩復(fù)雜度的指標(biāo)是隱私保護(hù)的，而張量核中只有0的指標(biāo)意味著原始張量中與該指標(biāo)對(duì)應(yīng)的所有值都為0，但是，在TN分解之前，通過在原始張量中填充隨機(jī)噪聲增加復(fù)雜度，可以很容易地克服這個(gè)問題。在張量秩復(fù)雜度足夠高的情況下，非0值的大小、符號(hào)和精確位置即使被除一臺(tái)服務(wù)器外的所有服務(wù)器合謀也不會(huì)泄露。為了進(jìn)一步增加不確定性，本文沿著每個(gè)張量維隨機(jī)排列模態(tài)變量，并存儲(chǔ)隨機(jī)種子進(jìn)行重構(gòu)，如果多維數(shù)據(jù)高度相關(guān)，則可以在TN分解后進(jìn)行隨機(jī)排列，以確保可壓縮性，每個(gè)張量核只包含特定于索引的信息，因此在大規(guī)模數(shù)據(jù)泄露的情況下它們是不可鏈接的，將更復(fù)雜的TN結(jié)構(gòu)劃分為私有和共享張量核，可以通過基于成對(duì)網(wǎng)絡(luò)距離的分層聚類和隨機(jī)分散張量計(jì)算實(shí)現(xiàn)，從而最小化隱私泄漏。

3.4 加法密鑰共享計(jì)劃

經(jīng)典的加法密鑰共享方案定義為x=〈x1〉1+〈x2〉2+…，從經(jīng)典方案到基于TN格式的密鑰共享方案的轉(zhuǎn)換相對(duì)簡(jiǎn)單，每一方使用所提出的隨機(jī)張量分解算法分解各自的份額，并將相應(yīng)的張量核發(fā)送給其它方，各方使用基于張量多線性運(yùn)算的相應(yīng)張量核執(zhí)行加法運(yùn)算，將生成的張量核分配給對(duì)應(yīng)方并使用分布式張量操作更新所有張量核，除了一方之外，所有各方都將他們更新的張量核傳遞給剩下的一方(之前沒有生成隨機(jī)張量核)以生成他的密鑰份額。未來的工作可能會(huì)考慮如何防止惡意服務(wù)器破壞張量網(wǎng)絡(luò)計(jì)算協(xié)議。

3.5 大數(shù)據(jù)分散存儲(chǔ)、共享和通信

加密對(duì)于大數(shù)據(jù)分布式應(yīng)用的密鑰管理來說是復(fù)雜的，加密需要由受信任的機(jī)構(gòu)集中管理來進(jìn)行身份驗(yàn)證、授權(quán)和撤銷訪問，以防止可能導(dǎo)致大規(guī)模數(shù)據(jù)泄露的潛在密鑰泄漏。本文的提議結(jié)合了基于分布式TN和元數(shù)據(jù)隱私的密鑰共享方案，以無縫保護(hù)大數(shù)據(jù)的存儲(chǔ)、通信和共享。分布式信任可以通過分散片段、元數(shù)據(jù)加密和訪問控制機(jī)制實(shí)現(xiàn)，此外，元數(shù)據(jù)管理是靈活的，可以使用企業(yè)管理系統(tǒng)以集中或分散的方式進(jìn)行，也可以在個(gè)人用戶側(cè)以分布式方式進(jìn)行，如果允許訪問元數(shù)據(jù)信息和切碎的片段，任何軟件應(yīng)用程序都可以重建原始數(shù)據(jù)，可以通過加密散列來確保數(shù)據(jù)完整性；而數(shù)據(jù)可用性可以通過集成在Hadoop分布式文件系統(tǒng)(HDFS)保證，用于安全數(shù)據(jù)隱私保護(hù)、壓縮、粒度訪問控制、可更新性和壓縮計(jì)算。

元數(shù)據(jù)充當(dāng)用戶瀏覽信息和數(shù)據(jù)的邏輯“地圖”，它還可以幫助審計(jì)員進(jìn)行系統(tǒng)審查和違約后損害評(píng)估，在使用本文提出的隨機(jī)張量分解算法分解大數(shù)據(jù)并將每個(gè)張量核或子塊分配到多個(gè)存儲(chǔ)位置后，主元數(shù)據(jù)文件更新為每個(gè)張量塊的位置和匿名文件名、張量結(jié)構(gòu)、加密哈希、隨機(jī)種子用于置換模式變量，以及用戶的訪問權(quán)限；張量片段的存儲(chǔ)位置和文件名可以定期更新，以增強(qiáng)數(shù)據(jù)隱私保護(hù)。主元數(shù)據(jù)文件可以在用戶端進(jìn)一步加密和密碼保護(hù)，存儲(chǔ)在分布式存儲(chǔ)位置的每個(gè)張量核的元數(shù)據(jù)僅包含匿名文件名和位置，以便在發(fā)生大規(guī)模數(shù)據(jù)泄露時(shí)無法鏈接；基于角色管理策略的數(shù)據(jù)加密和訪問控制可以以分散的方式實(shí)現(xiàn)，以保護(hù)張量核。系統(tǒng)架構(gòu)和元數(shù)據(jù)組織超出了本工作的范圍，但將來會(huì)考慮到各種應(yīng)用場(chǎng)景、系統(tǒng)不同大數(shù)據(jù)應(yīng)用的性能和要求。

3.6 大數(shù)據(jù)分布計(jì)算

TN在大數(shù)據(jù)分解后使用較小的、互連的張量核自然支持分布式計(jì)算，塔克格式的一些基本算術(shù)運(yùn)算在文獻(xiàn)[27]中導(dǎo)出，讓

A=[[GA；A(1)，A(2)，…，A(N)]]

B=[[GB；B(1)，B(2)，…，B(N)]]

(4)

其中，GL，L∈{A，B} 和A(k)/B(k)，k∈{1，2，…，N} 分別對(duì)應(yīng)塔克核心張量和因子矩陣

AB=[[GAGB；A(1)B(1)，…，A(N)B(N)]]

AB=[[GAGB；A(1)B(1)，…，A(N)B(N)]]

(5)

(1)對(duì)于所有變量，在每個(gè)張量核中獨(dú)立地添加或相乘可分離的分量；

(2)所有秩和在線性運(yùn)算中相加，在雙線性運(yùn)算中相乘。

在迭代計(jì)算期間，張量等級(jí)快速增長(zhǎng)，尤其是乘法，因此，應(yīng)為張量格式提供另一個(gè)稱為秩擾動(dòng)的重要操作。

TT格式及其變體支持廣泛的多重線性運(yùn)算，例如加法、乘法、逐矩陣或向量乘法、直接和、阿達(dá)瑪積、張量積和內(nèi)積[23]，如圖4所示，TT格式的多線性運(yùn)算可以以分散的方式自然地執(zhí)行，使其非常適合大數(shù)據(jù)處理和科學(xué)計(jì)算。TT等級(jí)隨著每個(gè)多線性運(yùn)算而增長(zhǎng)，并且很快變得計(jì)算量大，可以通過首先使用QR分解對(duì)張量核進(jìn)行正交化，然后使用SVD分解進(jìn)行壓縮，實(shí)現(xiàn)TT舍入(或重新壓縮)過程以減少TT秩，均以TT格式執(zhí)行；算法3中提出的隨機(jī)化TT-SVD算法可以很容易地適應(yīng)TT舍入過程的第二步；算法5顯示了一個(gè)用于N階張量的隨機(jī)rTT舍入算法示例。為了計(jì)算非線性函數(shù)，可以使用TT交叉逼近[31]，張量交叉的思想是從TN中采樣，從樣本點(diǎn)重構(gòu)和計(jì)算任意函數(shù)，分解樣本更新并相應(yīng)地更新原始TN。

圖4 張量網(wǎng)絡(luò)

張量網(wǎng)絡(luò)計(jì)算自然支持浮點(diǎn)表示的多線性運(yùn)算，只需最少的數(shù)據(jù)預(yù)處理，不像經(jīng)典的安全多方計(jì)算(SMPC)方案，只支持有限的安全操作(例如加法和乘法)，并且必須每次進(jìn)行預(yù)處理才能執(zhí)行不同的操作，因此，SMPC通常需要服務(wù)器之間進(jìn)行多次通信，以計(jì)算復(fù)雜的功能。使用TN可以壓縮和分散的方式進(jìn)行多重線性運(yùn)算，而不需要重建原始張量，這是張量計(jì)算在克服大規(guī)模優(yōu)化問題的維數(shù)禍害方面的主要優(yōu)勢(shì)。張量多線性運(yùn)算通常只需要在每個(gè)張量核上進(jìn)行計(jì)算，但一些張量計(jì)算方案需要服務(wù)器之間的通信。與SMPC方案不同的是，該方案的通信主要是張量核，而不是原始張量的密鑰共享，其大小通常要小得多，然而，在通信過程中，離散張量計(jì)算比SMPC方案泄露更多的信息，克服這一問題的一種方法是在執(zhí)行離散張量計(jì)算時(shí)不斷地從復(fù)雜數(shù)據(jù)中獲取新的熵。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

使用64位Intel?Xeon?W-2123 CPU 3.60 GHz，16.0 GB RAM的工作站進(jìn)行。在計(jì)算速度、壓縮比、重構(gòu)數(shù)據(jù)失真分析等方面，對(duì)原隨機(jī)TN分解方法和提出的隨機(jī)TN分解方法進(jìn)行了進(jìn)一步的比較。對(duì)于圖像數(shù)據(jù)，TN壓縮后的失真可以用歸一化L2不相似度來衡量，L2不相似度定義為

(6)

其中，xn，n∈{1，2，…，N} 是一組原始圖像，x′n，n∈{1，2，…，N′} 為TN壓縮后的重構(gòu)圖像集，為歐幾里得范數(shù)。本文研究了提出的rTT-SVD、rTR-SVD和rTD算法，因?yàn)閞TD是基于遞歸rTD的，因此表明rTD是隱私保護(hù)的，意味著rHT對(duì)于更大尺度的張量也是隱私保護(hù)的，所有實(shí)驗(yàn)隨機(jī)化TN的擾動(dòng)因子δ均設(shè)為0.05，因此對(duì)角擾動(dòng)矩陣Δ均在[0.05，1]范圍內(nèi)。

4.2 數(shù)據(jù)集

表2列出了本研究中所有數(shù)據(jù)集的樣本量和模式大小，在一維、二維和三維生物特征數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，以深入研究提出的隨機(jī)化TN算法在不同數(shù)據(jù)維度上的隱私保護(hù)。一般情況下，向量和矩陣數(shù)據(jù)在TN分解前都是被重塑為高階張量的，人類步態(tài)(Human Gait)傳感器數(shù)據(jù)庫(kù)使用智能手機(jī)的慣性傳感器進(jìn)行記錄，采樣頻率為100 Hz，每次行走總距離為640 m；真假人臉(Real &Fake Face Images)檢測(cè)的訓(xùn)練圖像由延世大學(xué)計(jì)算機(jī)科學(xué)系計(jì)算智能與擾影實(shí)驗(yàn)室在Kaggle在線數(shù)據(jù)共享平臺(tái)上提供，實(shí)驗(yàn)中只使用真實(shí)的人臉圖像；人臉圖像的RGB通道具有很高的光譜相關(guān)性，因此將通道進(jìn)行三維疊加進(jìn)行張量分解；耶魯面部(Yale Face Database)數(shù)據(jù)庫(kù)包含15名受試者的GIF圖像，每個(gè)人都有11種不同的面部表情或配置。最后，本文還為調(diào)查研究生成一個(gè)三維超對(duì)角張量 (i，i，i) (Super-diagonal Tensor)。

表2 實(shí)驗(yàn)研究中使用的數(shù)據(jù)集

4.3 隨機(jī)TN分解的數(shù)據(jù)結(jié)構(gòu)復(fù)雜性實(shí)驗(yàn)分析

圖5(利用算法3)和圖6顯示了將噪聲數(shù)據(jù)填充到一個(gè)相對(duì)簡(jiǎn)單的(全秩)超對(duì)角張量之前和之后對(duì)TT分解的影響，兩種方法重建后都是相同的超對(duì)角張量，然而，由于秩復(fù)雜度較高，帶有噪聲的樸素填充通常會(huì)導(dǎo)致TN計(jì)算和存儲(chǔ)成本較高，而本文提出的隨機(jī)TN算法只是利用大數(shù)據(jù)中常見的復(fù)雜相關(guān)結(jié)構(gòu)，生成高度隨機(jī)的張量塊，從而使破解難度增大，進(jìn)而使隱私得到保護(hù)。圖7為人體步行傳感器數(shù)據(jù)的隨機(jī)TT分解，為了在TN壓縮過程中保留重要的數(shù)據(jù)集特征，將每個(gè)屬性標(biāo)準(zhǔn)化到均值為零，方差為1，即z-score。

圖5 使用TT-SVD(上)和rTT-SVD(下)對(duì)超對(duì)角線張量進(jìn)行分解

圖7 人體步態(tài)傳感器數(shù)據(jù)

4.4 隱私泄漏實(shí)驗(yàn)分析

圖8 人臉圖像TT分解的直方圖分析

圖9 兩次隨機(jī)rTT-SVD分解后產(chǎn)生的歸一化TT核

圖10 將隨機(jī)化TN分解過程生成的張量核

圖11 不同隨機(jī)TNs的原始數(shù)據(jù)與重構(gòu)數(shù)據(jù)的歸一化互信息

圖12 原始TT-SVD和隨機(jī)TT-SVD TT核皮爾森相關(guān)系數(shù)絕對(duì)值

4.5 數(shù)據(jù)壓縮性和算法效率實(shí)驗(yàn)分析

表3測(cè)量了真實(shí)和虛假面部圖像數(shù)據(jù)庫(kù)的TN分解和重建的時(shí)間效率，與非隨機(jī)TN分解相比，隨機(jī)化TN分解通常需要稍長(zhǎng)的時(shí)間，這主要是由于生成隨機(jī)化張量塊所需的額外SVD步驟，TR重建很長(zhǎng)(約1 min)，因?yàn)門N結(jié)構(gòu)中有一個(gè)循環(huán)會(huì)浪費(fèi)更多的時(shí)間。圖13顯示了Yale Face Database 在不同TN壓縮比下的圖像失真分析，與非隨機(jī)化TN算法相比，隨機(jī)化TN算法導(dǎo)致重構(gòu)數(shù)據(jù)的失真略高，這是意料之中的，因?yàn)殡S機(jī)化TN算法會(huì)產(chǎn)生次優(yōu)分解，與隨機(jī)rTR和rTD分解相比，隨機(jī)TT分解產(chǎn)生的失真最低，尤其是在高壓縮比的情況下，TT表示在隱私保護(hù)、計(jì)算和存儲(chǔ)效率之間取得了良好的平衡。

表3 真實(shí)和虛假面部圖像數(shù)據(jù)庫(kù)的TN分解和重建的時(shí)間效率

4.6 算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度如何？防攻擊、防破解性如何？華中科技大學(xué)的馮君博士對(duì)張量應(yīng)用于大數(shù)據(jù)的分析與處理進(jìn)行了詳細(xì)的研究，張量分解算法對(duì)用戶的在線破解是非常耗時(shí)和難以實(shí)現(xiàn)的。詳情請(qǐng)見文獻(xiàn)[32]。

5 結(jié)束語

可擴(kuò)展性對(duì)于大數(shù)據(jù)分析的成功和隱私保護(hù)技術(shù)的廣泛采用都是一個(gè)重要的考慮因子。本文提出了一種簡(jiǎn)單的擾動(dòng)技術(shù)，可以很容易地適應(yīng)于各種網(wǎng)絡(luò)結(jié)構(gòu)的隨機(jī)分解，提出的基于離散張量網(wǎng)絡(luò)表示的密鑰共享方案由于支持離散張量計(jì)算，在存儲(chǔ)、計(jì)算和通信復(fù)雜度方面都非常有效。為了驗(yàn)證該方案對(duì)半誠(chéng)實(shí)對(duì)手的安全性，進(jìn)行了隱私泄漏分析，但在進(jìn)行離散張量操作時(shí)仍可能發(fā)生隱私泄漏，這需要進(jìn)一步的研究。