信息論安全的3個基礎(chǔ)外包計算協(xié)議及空間位置關(guān)系保密判定

陳振華 昔路琪 史曉楠 聶靖靖

摘要：現(xiàn)存的安全幾何計算協(xié)議大多采用公鑰加密方法保護數(shù)據(jù)隱私，計算成本較大。當計算能力不強的用戶解決復(fù)雜問題時，效率往往較低。針對這些問題，避開公鑰加密的方法，而是利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機數(shù)混淆的方法來保護數(shù)據(jù)隱私，并且為了進一步提高效率，將大量的用戶計算外包出去。在此基礎(chǔ)上，首先設(shè)計了常用的3個基礎(chǔ)向量外包計算協(xié)議，分別是安全外包計算的向量模長計算協(xié)議，向量內(nèi)積計算協(xié)議和向量夾角計算協(xié)議，并利用模擬范例證明了協(xié)議的安全性，然后利用這3個基礎(chǔ)協(xié)議進一步解決了現(xiàn)實意義中如何保密判斷空間面與面位置關(guān)系的問題，并給出了具體協(xié)議。最后，通過理論分析與實驗仿真顯示：由于協(xié)議沒有使用公鑰加密的方法，因此達到了信息論安全;并且由于外包計算的使用，為用戶節(jié)省了更多的計算成本，取得了比較高的效率;此外，協(xié)議能夠解決的問題也更加廣泛，可作為新的云計算技術(shù)的基礎(chǔ)協(xié)議應(yīng)用到安全多方計算的其它分支中。

關(guān)鍵詞：安全多方計算;外包計算;內(nèi)積協(xié)議;空間位置;信息論安全

中圖分類號：TP 309

文獻標志碼：A

文章編號：1672 -9315（2019）06 -1049 -08

DOI：10. 13800/j.cnki. xakjdxxb. 2019. 0618

開放科學(xué)（資源服務(wù)）標識碼（OSID）：

收稿日期：2019 -05 - 20

責(zé)任編輯：高佳

基金項目：國家自然科學(xué)基金（ 61872289）;廣西密碼學(xué)與信息安全重點實驗室開放課題（GCIS201714）

第一作者：陳振華（1976 -），女，陜西寶雞人，博士，副教授，E-mail：chenzhenhua@ snnu.edu.cn

通信作者：黃路琪（1996 -），女，山東平陰人，碩士研究生，E-mail：huanguqi_xust@ 163.com

0 引言

安全多方計算最早由Yao提出，是指各個參與方在不泄露各自輸入隱私的情況下，能正確合作計算出某個問題。保護隱私的合作計算都可歸為安全多方計算[1]，例如，保護隱私的數(shù)據(jù)挖掘[2-4]，統(tǒng)計計算[5-7]，機器學(xué)習(xí)[8-1O]，數(shù)據(jù)聚合[11-14]，外包計算[15-17]，和數(shù)據(jù)查詢[18 -19]等。

安全幾何計算是安全多方計算的一個重要分支，是指各參與方在保護各自數(shù)據(jù)隱私的情況下，共同計算一個幾何問題。例如：投資公司A，B想要擴展市場，A想知道自己的投資范圍是否在B的范圍內(nèi)，但B的計劃是商業(yè)機密，而A也不想告訴B自己的投資計劃，在不暴露各自商業(yè)機密的前提下，雙方如何解決這個問題？

若將公司的投資計劃看成平面區(qū)域，對應(yīng)的數(shù)學(xué)模型是：保密判定空間中2個平面是否相交。而要判定此關(guān)系，需要先解決向量安全計算問題。外包計算是目前流行的一種計算模式，但服務(wù)器作為不可信第三方，可能會泄露用戶隱私。因此，在利用外包服務(wù)的同時，如何保護各參與方數(shù)據(jù)隱私解決向量計算問題并進一步解決平面判定問題，成為目前一個較新的研究方向。

針對向量安全計算，以往的學(xué)者提出了一些解決方案。周素芳等人利用哥德爾編碼和同態(tài)加密解決了向量線性組合計算問題，該方案使用了公鑰加密，不是信息論安全，也不適用于外包計算[20]。陳振華等人提出了基于同態(tài)加密的向量內(nèi)積外包計算協(xié)議。該協(xié)議適用于外包計算，但不是信息論安全且復(fù)雜度較高[21]。張衛(wèi)國等人引入不可逆矩陣來保護數(shù)據(jù)隱私，計算了向量內(nèi)積[22]，Li等人借助內(nèi)積運算來判定空間位置關(guān)系[23]。雖然協(xié)議都達到了信息論安全，但并不適用于外包計算。

針對以上方案的不足，文中利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機數(shù)混淆的方法來保護數(shù)據(jù)隱私，并利用外包計算節(jié)省成本。在此基礎(chǔ)上，設(shè)計了安全外包計算的向量內(nèi)積、向量模長和向量夾角計算協(xié)議，并解決了空間面與面的保密位置判定問題。

1 模型簡介

1.1 半誠實模型

安全多方計算的協(xié)議運行環(huán)境分為半誠實參與者模型和惡意參與者模型[24-29]。文中協(xié)議都建立在半誠實模型下，因此這里只給出半誠實模型定義。半誠實參與者是指協(xié)議方誠實地執(zhí)行協(xié)議，不會篡改輸入和輸出信息，但可能會保留計算的中間結(jié)果，試圖從中間結(jié)果和最后輸出推導(dǎo)出協(xié)議之外的信息或者他人的信息。

1.2 半誠實模型下的安全性定義

外包計算中半誠實模型下的安全兩方計算的模擬范例定義如下：設(shè)Alice擁有x，Bob擁有y，Server是外包服務(wù)器，f（x，y）為概率多項式函數(shù);π是計算f的協(xié)議。Alice，Bob和Server要在不泄露x，y給任何一方的前提下，合作計算函數(shù)f（x，y）=

分析：在協(xié)議1中，Alice和Bob利用函數(shù)f的正交性，將對向量X和Y的內(nèi)積計算轉(zhuǎn)換成fX和fY的內(nèi)積計算。又利用f的單向性對向量X和Y保護隱私，得到fX和fX，由于f具有單向性，因此任何人都不能得到初始輸入X和Y.又因為隨機數(shù)的加入，所以數(shù)據(jù)r1X，數(shù)據(jù)r2Y和隨機數(shù)具有了不可區(qū)分性，因此保護了X和Y的隱私。此外，Alice和Bob利用隨機數(shù)r1和r2混淆了fX和fy內(nèi)積結(jié)果，由于結(jié)果中含有Alice和Bob的隨機數(shù)乘積r1 r2，因此外包服務(wù)器無法獲得真正的內(nèi)積值。即使考慮合謀，由于Alice和Bob不可能合謀，因此外包服務(wù)器無法同時獲得兩方的隨機數(shù)r1和r2，從而無法獲得合謀條件下內(nèi)積結(jié)果。即協(xié)議

1 保密地計算了向量的內(nèi)積。

類似的方法可以分析協(xié)議2和協(xié)議3，得到類似結(jié)論。

3 安全性證明

在本節(jié)，應(yīng)用2.2節(jié)的模擬范例我們給出以上3個協(xié)議的安全性證明，先證明協(xié)議1.

定理1協(xié)議1保密地外包計算了2個向量X和Y的內(nèi)積。

證明 按照2.2節(jié)外包計算中半誠實模型下安全兩方計算安全性的定義，需要構(gòu)造表1中的5個模擬器Sl，S2，S3，S4和S5，由于文章篇幅有限，因此安全性證明只給出了模擬器S1的詳細過程，其他模擬器可按同樣的道理得到。

以上過程證明了Alice和Server合謀的視圖只能從自身輸入X，E（X），E（ Y）和所獲得的輸出fi（X，Y），E（X，Y）中得到，并沒有包含Bob的信息。同理，Bob和Server合謀的視圖也只能從自身的輸入和輸出中得到，并沒有包含Alice的信息。因此證明了在外包計算過程中，即使Server與其中任何一方參與者合謀，也得不到另一方的信息。

證畢。

類似的方法可證明協(xié)議2和協(xié)議3的安全性，得到以下定理。

定理2協(xié)議2保密地外包計算了向量長度。

定理3協(xié)議3保密地外包計算了向量夾角。

4 效率分析與比較

本節(jié)給出在外包計算的模式下，保密判斷空間面與面位置關(guān)系的協(xié)議及其效率分析比較。

協(xié)議4保密判斷空間面與面的位置關(guān)系

由于協(xié)議4是依靠文中的協(xié)議1，協(xié)議3設(shè)計的，而第3節(jié)的安全性證明已經(jīng)證明了協(xié)議1，協(xié)議3都是安全的，因此可以得到協(xié)議4也是安全的，這里不再詳細證明。

由于文中和文獻[21-23]都處理了空間面面位置關(guān)系問題，而文獻[20]并沒有處理該問題。因此就文獻[21-23]處理的共同的面面位置保密判定協(xié)議做出比較和分析。為了方便比較，將模冪運算記為M_，模乘運算記為MN，乘法運算記為M，向量維數(shù)記為n，統(tǒng)一使用文獻[21]的模數(shù)Ⅳ.整個協(xié)議執(zhí)行過程中，計算開銷比較大的是模冪運算，模乘運算，乘法運算，因此把這些運算總個數(shù)作為衡量計算復(fù)雜度的指標，其他忽略不計。

4.1 理論分析與比較

4.1.1 計算復(fù)雜度

文獻[21]的面面位置關(guān)系保密判定（協(xié)議6），整個協(xié)議計算過程中調(diào)用了2次內(nèi)積協(xié)議，用戶加解密過程中使用了模冪和模乘運算，其運算總個數(shù)為2MN +18Me.

文獻[22]的安全計算面與面的位置關(guān)系（協(xié)議5），整個協(xié)議計算過程中調(diào)用了4次內(nèi)積協(xié)議，每調(diào)用一次內(nèi)積協(xié)議，用戶進行2次矩陣相乘，需16次乘法，因此運算總個數(shù)為64M.

文獻[23]的保密判定面與面的位置關(guān)系協(xié)議（協(xié)議4），整個協(xié)議計算過程沒有調(diào)用內(nèi)積協(xié)議，而是進行了3個3階矩陣行列式運算，和3個3維向量內(nèi)積運算，即9個乘法運算，因此運算總個數(shù)為36M.

文中面面位置關(guān)系保密判定（協(xié)議4），整個協(xié)議計算過程需要調(diào)用1次保密計算夾角和1次保密計算內(nèi)積協(xié)議，用戶運算總個數(shù)8MN +6M.

4.1.2 通信復(fù)雜度

衡量通信復(fù)雜度的指標用協(xié)議交換信息的比特數(shù)，或者用通信輪數(shù)，在多方保密計算研究中通常使用輪數(shù)。

文獻[21]的面面位置關(guān)系保密判定（協(xié)議6），整個協(xié)議計算過程中調(diào)用了2次保密計算內(nèi)積協(xié)議和1次比較協(xié)議，內(nèi)積協(xié)議每調(diào)用一次需要3輪交互，比較協(xié)議需要2次交互。則用戶和外包服務(wù)器總共進行了8輪交互。

文獻[22]的安全計算面與面的位置關(guān)系（協(xié)議5），整個協(xié)議計算過程中調(diào)用了4次內(nèi)積協(xié)議，內(nèi)積協(xié)議每調(diào)用一次需要2輪交互，用戶之間總共進行了8輪交互。

文獻[23]的保密判定面與面的位置關(guān)系協(xié)議（協(xié)議4），整個協(xié)議計算過程中沒有調(diào)用內(nèi)積協(xié)議，用戶之間總共進行了2輪交互。

文中面面位置關(guān)系保密判定（協(xié)議4），整個協(xié)議計算過程調(diào)用了1次保密計算夾角協(xié)議和1次保密計算內(nèi)積協(xié)議，分別需要進行5輪和3輪交互。則用戶和外包服務(wù)器之間的總輪數(shù)為8輪。

4.1.3性能

以各個協(xié)議取得的安全性級別，是否適用于外包計算和能夠解決的空間位置問題作為衡量性能的標準。以“√”代表協(xié)議能夠解決的空間位置問題。

綜合以上，得到文中協(xié)議4和文獻[ 21 - 23]的效率比較見表2，性能比較見表3.

由文獻[30]可知，1個模冪運算等價于logN個模乘運算。假設(shè)這里所有協(xié)議都采用和文獻[30]同樣的操作平臺，可將表2中文獻[21]方案的計算個數(shù)換算為2MN +36logNM.因此由表2可以看到，相比于文中協(xié)議4，以往的方案[21-23]計算開銷較大。由于文中利用矩陣論中一些特殊函數(shù)心基礎(chǔ)，為了方便其他復(fù)雜安全多方計算問題架構(gòu)于此，因此文中協(xié)議1提供了外包模式下簡潔的保密內(nèi)積計算方案。這里仍采用和上文相同的標記符號，計算復(fù)雜度記為0，得到協(xié)議1在傳統(tǒng)模式（非外包）下的計算成本為3MN +M，計算復(fù)雜度為0（1）;外包模式下計算成本為2MN+（n+1）M，計算復(fù)雜度為O（n），得到協(xié)議1在2種計算模式下的計算復(fù)雜性對比如圖1所示。

從圖1可以看出，未借助外包計算的內(nèi)積協(xié)議（曲線1）不僅用戶計算成本較大，且計算復(fù)雜度隨著向量維數(shù)的增大呈線性增長，因此為了節(jié)省用戶的計算成本，以按需付費的方式將保密內(nèi)積計算外包出去。由于該部分的計算量已經(jīng)由外包服務(wù)器計算，因此不再包含在用戶計算成本之內(nèi)，那么架構(gòu)于此基礎(chǔ)協(xié)議（即文中協(xié)議1）的協(xié)議4也的性質(zhì)保護數(shù)據(jù)，并沒有使用公鑰加密的方法，因此計算復(fù)雜度和通信復(fù)雜度較低，更具有實踐意義。從表3可以看出，方案相比以往的方案，不僅實現(xiàn)了信息論安全，也適合外包計算，并且所能處理的空間位置關(guān)系也更加廣泛。

4.1.4 傳統(tǒng)模式和外包模式下計算成本比較

由于保密內(nèi)積計算是整個安全外包計算的核不需要保密計算內(nèi)積，這樣就極大地節(jié)省了用戶的計算成本。

4.2 仿真實驗

為了直觀呈現(xiàn)以上協(xié)議的理論效率分析結(jié)果，在Java語言環(huán)境下將表2的4個協(xié)議編程實現(xiàn)。采用的計算機運行環(huán)境如下：操作系統(tǒng)為Windows 7旗艦版，CPU為Intel i5 - 5200U 2.20CHz，內(nèi)存為4.00 GB.文中協(xié)議4和文獻[21]協(xié)議6主要運算為模運算，而文獻[22]協(xié)議5和[23]協(xié)議4的主要運算為乘法運算。因此分為2種情況進行分析比較，第一種是將文中協(xié)議4和文獻[21]協(xié)議6進行效率比較（不同模數(shù)下的耗時）;第二種是將文中協(xié)議4和文獻[22]協(xié)議5，文獻[23]協(xié)議4進行效率比較（判斷不同位置關(guān)系的耗時）。

1）將文中協(xié)議4和文獻[21]協(xié)議6在不同模式下進行耗時比較。在實驗中分別取不同的模數(shù)Ⅳ為143，437，899，1 517 bits，得到2個協(xié)議的平均耗時，如圖2所示。

2）將文中協(xié)議4和文獻[22]協(xié)議5，文獻[23]協(xié)議4判斷不同位置關(guān)系進行耗時比較，分別得到3個協(xié)議平行、相交、垂直、重合情況下的平均耗時，見表4.

從圖2和表4可以看出，文中協(xié)議4的平均耗時低于文獻[21]協(xié)議6，文獻[22]協(xié)議5和文獻[23]協(xié)議4的平均耗時。此外，從表4還可以看出文中協(xié)議4能判斷的面面位置關(guān)系更多（文獻[22]協(xié)議5不能判斷面面重和，文獻[23]協(xié)議4既不能判斷面面重和，也不能判斷面面垂直）。

綜合以上實驗結(jié)果，得到如下結(jié)論：無論理論分析還是實驗分析，本文協(xié)議效率較高，而且能判斷的空間位置關(guān)系更加廣泛。

5 結(jié)論

1）利用矩陣論中一些特殊函數(shù)的性質(zhì)和隨機數(shù)混淆方法在外包計算下設(shè)計了3個基礎(chǔ)的信息論安全向量計算協(xié)議，分別是安全外包計算的向量內(nèi)積，向量模長和向量夾角計算協(xié)議。

2）利用這些基礎(chǔ)協(xié)議解決了空間面與面位置關(guān)系保密判斷問題，可進一步解決金融投資等實際問題。

3）將提出的保密判定面與面的位置關(guān)系協(xié)議與其他已有方案進行了理論分析和仿真實驗比較。結(jié)果顯示文中提出的方案效率更高，可判斷的空間位置關(guān)系更加廣泛。

參考文獻（ References）：

[1]

Yao A C.Protocols for secure computations[Cl//Pro-ceedings of 23rd IEEE Symposium on Foundations ofComputer Science， Chicago， USA， 1982： 160 - 164.

[2]

Kantarciogu M ， Clifton C. Privacy-preserving distributedmining of association rules on horizontally partitioneddata[J] IEEE Transactions on Knowledge and DataEngineering ， 2004 ， 16 （ 9） ： 1026 - 1037.

[3]楊靜，趙家石，張健沛，一種面向高維數(shù)據(jù)挖掘的隱私保護方法 [J]電子學(xué)報 ， 2013 （ 11 ） ： 2187 -

2192.

YANC Jing， ZHAO Jia-shi ， ZHANC Jian-pei. A privacypreservation method for high dimensional data mining[J] . Acta Electronica Sinica ， 2013 （ 11） ：2187 - 2192.

[4]

Kenthapadi K， Mironov I， Thakurta A. Privacy-preser-ving data mining in industry [ C ] //Companion Proceed-ings of the 2019 World Wide Web Conference. ACM，2019 ：1308 - 1310.

[5]

Kamm L， Bogdanov D ， Pankova A ， et al. Statistical anal- ysis methods using secure multi-party computation [ J ] .Cryptology and Information Security Series ，2015 ， （ 13 ） ：58 - 80.

[6] Duverle D A ， Kawasaki s ， Yamada Y ， et al. Privacy-pre- serving statistical analysis by exact logistic regression [C] //IEEE Symposium on Security and Privacy ， 2015.

[7]

Wen L D， Atallah M J. Secure multi-party computation problems and their applications ： a review and open prob-lems [C]//New Security Paradigms Workshop， ACM，2001 ：13 - 22.

[8]

Mohassel P ， Zhang Y. Secure M L ： A system for scalable privacy-preserving machine learning [ C ]//IEEE Sym- posium on Security and Privacy ， 2017 ： 19 - 38.

[9]

Dowlin N ， Giladbachrach R，Laine K ， et al. CryptoNets ： applying neural networks to encrypted data with highthroughput and accuracy [ C ] //International Conferenceon Machine Learning ， 2016 ： 201 - 210.

[10] Mohassel P， Rindal P. ABY3 ： a mixed protocol frame-work for machine learning [ C l//Proceedings of the2018 ACM SIGSAC Conference on Computer and Com-munications Security ， ACM ，2018 ：35 - 52.

[11]

Jung T， Mao X F， Li X Y， et al. Privacy-preserving dataagggregation without secure channel ： Multivariate polyno-mial evaluation [ C l//INFOCOM， 2013 ProceedingsIEEE. IEEE ， 2013 ： 2634 - 2642.

[12]

Groat M M ， Hey W ， Forrest S. KIPDA ： k-indistinguisha-ble privacy-preserving data aggre-gation in wireless sen-sor networks [ C ] //INFOCOM ， 2011 Proceedings IEEE.IEEE ，2011 ：2024 - 2032.

[13]

Ozdemir S， Peng M ， Xiao Y. PRDA ： polynomial re～7es-sion-based privacy-preserving data ag～Tegation for wire-less sensor networks [J] . Wireless Communications andMobile Computing ， 2015 ，15 （4） ：615 - 628.

[14]

Liu Y， Guo W， Fan C I ， et al. A practical privacy - pre-serving data aggregation （3PDA） scheme for smart grid[J] . IEEE Transactions on Industrial Informatics ， 2018 ，15 （3） ：1767 -1774.

[15]

Huang J J ， Juang W S， Fan C I， et al. Robust and priva-cy protection authentication in cloud computing [ J ] . In-temational Joumal of Innovative Computing ， Informationand Contr01，2013 ，9 （ 11） ：4247 - 4261.

[16] Wei L， Zhu H， Cao Z， et al. Security and privacy forstorage and computation in cloud computing [ J] . Infor-mation Sciences ， 2014 ，258 ：371 - 386.

[17]

Yang D ， Chen Y C ， Ye S. Privacy-preserving outsourcecomputing for binary vector similarity [ C ] //Internation-al Conference on Security with Intelligent Computingand Big-data Services. Springer， Cham， 2017： 161 - 169.

[18]

Samanthula B K， Elmehdwi Y， Howser C ， et al. A securedata sharing and query processing framework via federa- tion of cloud computing[ J] . Information Systems ， 2015 ，48 ：196 - 212.

[19]

Campos R， Dias G， Jorge A M， et al. Survey of temporalinformation retrieval and relatd applications [J] . ACMComputing Surveys（ CSUR） ， 2015 ，47 （ 2） ： 15.

[20]周素芳，竇家維，郭奕旻，等，安全多方向量計算[J].計箅 機學(xué)報 ， 2017 （ 5 ） ：1134 - 1150.

ZHOU Su-fang， DOU Jia-wei ， GUO Yi-min ， et al. Securemultiparty vector computation [ J ] . Chinese Journal ofComputers ，2017 ，40 （ 5） ：1134 - 1150.

[21]陳振華，李順東，黃瓊，等，云外包計算中空間位置關(guān)的保密判定[J] .計算機學(xué)報，2017，40 （2） ：351 - 363.

CHEN Zhen-hua， LI Shun-dong， HUANC Qiong， et al.Privacy-preserving determination of spatial location-rela-tion in cloud computing[ J] . Chinese Journal of Comput-ers ，2017 ，40（2） ：351 - 363.

[22]張衛(wèi)國，孫嫂，陳振華，等.空間位置關(guān)系的安全多方計算及其應(yīng)用[J].電子與信息學(xué)報，2016，38（9）：2294 - 2300.

ZHANG Wei-guo， SUN Man， CHEN Zhen-hua， et al.Se-cure multi-party computation of spatial relationship andits application[J].Journal of Electronics&InformationTechnology， 2016 ，38（9）：2294 - 2300.

[23]

LiS D，Wu C Y，Wang D S.Secure multiparty computa-tion of solid geometric problems and their applications [J]. Information Sciences， 2014 ，282（ 10）：401 - 413.

[24]荊巍巍，安全多方計算中若干基礎(chǔ)協(xié)議及應(yīng)用的研究[D].北京：中國科學(xué)技術(shù)大學(xué)，2008.

JING Wei-wei. Research on several basic protocols andapplication of secure multi-party computation[D].Bei-jing： University of Science and Technology of China，2008.

[ 25]

Katz J，LindellY.Introduction to modern cryptography[M].BocaRaton Florida： Chapman and Hall/CRC， 2014.

[26] Guo F，Susilo W， Mu Y.Introduction to security reduc-tion[M].Springer，2018.

[27]

Coldreich 0.Foundations of crypto～7aphy： basic applica-tions[M].London： Cambridge University Press， 2004.

[28]

Goldreich 0， Micali S，Wigderson A.How to play anymental game[C]//Proceedings of the nineteenth annualACM symposium on Theory of computing. ACM， 1987：218 - 229.

[29]

Hazay C， LindellY.Efficient secure two-party protocols：Techniques and constructions[M].Springer Science&Business Media.2010.

[30]

Lin H Y， Tzeng W G.An efficient solution to the mil-lionaires' problem based on homomorphic encryption[Cl//International Conference on Applied CryptogTa-phy and Network Security， Springer， Berlin， Heidelberg，2005 ，3531：456 -466.