冉　鵬，張文科，楊浩淼

（1.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731；2.中電集團(tuán)30所保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

可驗(yàn)證的安全內(nèi)積計(jì)算協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)*

冉鵬1,2，張文科2，楊浩淼1,2

（1.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731；2.中電集團(tuán)30所保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

安全多方計(jì)算旨在解決一組互不信任的參與方之間隱私保護(hù)的協(xié)同計(jì)算問(wèn)題。自姚期智從1982年提出以來(lái)，隨著云計(jì)算、電子商務(wù)技術(shù)的發(fā)展，安全多方計(jì)算得到了更加廣泛的研究及應(yīng)用。余弦相似性是用于度量?jī)蓚€(gè)樣本點(diǎn)之間相似度的有效方法，且廣泛應(yīng)用于數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)等領(lǐng)域。目前存在的大多數(shù)安全多方計(jì)算研究都忽略了用戶輸入和結(jié)果的驗(yàn)證過(guò)程，都假設(shè)各參與方是誠(chéng)實(shí)地執(zhí)行協(xié)議。為了彌補(bǔ)這一塊的缺陷，設(shè)計(jì)了一種可驗(yàn)證的安全內(nèi)積計(jì)算的協(xié)議，并證實(shí)了此協(xié)議會(huì)更加安全。

安全內(nèi)積計(jì)算；余弦相似性；隱私保護(hù)；可驗(yàn)證

圖1　安全多方計(jì)算在密碼學(xué)中的地位

余弦相似性（Cosine Similarity，CS）［4］是用于度量?jī)蓚€(gè)樣本點(diǎn)之間相似度的有效方法，且廣泛應(yīng)用于數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)等領(lǐng)域。特別是近幾年，隨著大數(shù)據(jù)分析的興起，在大規(guī)模數(shù)據(jù)集中進(jìn)行數(shù)據(jù)挖掘得到可使用的信息變得異常重要。余弦相似性是一個(gè)非常有用的算法，只要涉及計(jì)算兩個(gè)樣本點(diǎn)之間的相似度都可以使用它。比如，當(dāng)需要查找某本書籍中的某幾個(gè)關(guān)鍵字時(shí)，移動(dòng)社交網(wǎng)絡(luò)中查找潛在的用戶或好友時(shí)，余弦相似性度量就是一個(gè)非常高效的方法。

在如今的大數(shù)據(jù)環(huán)境下，基于余弦相似性的安全多方計(jì)算協(xié)議，能夠保證用戶的輸入信息不被泄露的情況下，通過(guò)協(xié)同計(jì)算各自輸入樣本點(diǎn)之間的相似度可以對(duì)各自的數(shù)據(jù)集進(jìn)行挖掘?，F(xiàn)有的大多數(shù)多方安全計(jì)算協(xié)議都著力于保護(hù)數(shù)據(jù)隱私，卻忽略了計(jì)算的可驗(yàn)證性，而協(xié)議的正確性依賴于所有參與方完全誠(chéng)實(shí)地遵守協(xié)議的執(zhí)行。但是，在實(shí)際中很難實(shí)現(xiàn)。由于缺乏對(duì)參與方輸入數(shù)據(jù)與輸出結(jié)果的驗(yàn)證，惡意用戶可以通過(guò)對(duì)輸入數(shù)據(jù)、中間計(jì)算結(jié)果和輸出結(jié)果進(jìn)行撒謊，使協(xié)議得到錯(cuò)誤的計(jì)算結(jié)果，從而破壞計(jì)算機(jī)的系統(tǒng)安全。對(duì)此，本文在總結(jié)前人的基礎(chǔ)上，設(shè)計(jì)了一個(gè)可驗(yàn)證的安全多方計(jì)算協(xié)議，以彌補(bǔ)大多數(shù)安全多方計(jì)算缺乏驗(yàn)證過(guò)程的缺陷。實(shí)驗(yàn)證明，可驗(yàn)證的安全多方計(jì)算協(xié)議較之前的大多數(shù)安全多方計(jì)算協(xié)議更加安全。

1　相關(guān)研究

姚期智（A.C.Yao）最早于1982在著名的“百萬(wàn)富翁”問(wèn)題［5］中提出了安全多方計(jì)算問(wèn)題。百萬(wàn)富翁問(wèn)題即有兩個(gè)百萬(wàn)富翁，他們想在不泄露各自錢財(cái)?shù)那闆r下，知道誰(shuí)擁有更多的財(cái)富，實(shí)際上是比較兩個(gè)整數(shù)大小的安全多方計(jì)算問(wèn)題。隨后，在1986年，Goldreich、Micali、Wigderson提出了可以計(jì)算任意函數(shù)的、基于密碼學(xué)安全模型的安全多方計(jì)算協(xié)議［6］。該協(xié)議證明了被動(dòng)攻擊時(shí)n-secure的協(xié)議是存在的，主動(dòng)攻擊時(shí)（n-1）-secure的協(xié)議是存在的。接下來(lái)的兩年，Chaum和Goldreich分別考慮了信息論安全模型和密碼學(xué)安全模型下的安全多方計(jì)算問(wèn)題［7］。此后，許多學(xué)者在如何提高安全多方計(jì)算協(xié)議的效率、如何對(duì)安全多方計(jì)算進(jìn)行形式化的定義、如何對(duì)通用的安全多方計(jì)算協(xié)議進(jìn)行剪裁使之更加有效地適用于不同的應(yīng)用環(huán)境、新的安全多方計(jì)算協(xié)議的構(gòu)造方法、安全多方計(jì)算攻擊者結(jié)構(gòu)定義等方面進(jìn)行了大量研究。

雖然安全多方計(jì)算在理論上的研究很成熟，但是通用的安全多方計(jì)算協(xié)議的計(jì)算代價(jià)極其昂貴。這些現(xiàn)存的方法都集中考慮了隱私保護(hù)方面，卻忽略了各參與方的輸入和最后結(jié)果的驗(yàn)證過(guò)程［8］。大多數(shù)協(xié)議的正確性都是基于這樣的假設(shè)：假設(shè)各個(gè)參與方都能嚴(yán)格執(zhí)行協(xié)議。實(shí)際上，很難保證各個(gè)參與方都是完全誠(chéng)實(shí)的。因此，可驗(yàn)證的安全內(nèi)積計(jì)算協(xié)議應(yīng)運(yùn)而生。本文將在分析前人的結(jié)果上，設(shè)計(jì)一種可驗(yàn)證的安全內(nèi)積計(jì)算協(xié)議。

2　基礎(chǔ)知識(shí)

2.1可驗(yàn)證的安全多方計(jì)算

可驗(yàn)證的安全多方計(jì)算（Verifiable Secure Multiparty Computation）問(wèn)題，就是說(shuō)在分布式網(wǎng)絡(luò)中，有n個(gè)參與方，每一方都有一個(gè)自己的秘密輸入，他們希望不泄露彼此的秘密輸入的情況下，能夠協(xié)同完成某種計(jì)算任務(wù)。要求計(jì)算結(jié)束后，他們每一方都能接收到正確的輸出，且每一方只能了解自己的秘密輸入和輸出。這里，如果在該協(xié)議中，一個(gè)惡意參與方無(wú)法欺騙其他參與方接受一個(gè)錯(cuò)誤的計(jì)算結(jié)果，那么就稱這類安全多方計(jì)算協(xié)議是可驗(yàn)證的。

2.2余弦相似性

余弦相似性是度量?jī)蓚€(gè)樣本點(diǎn)之間相似度的有效方法，主要度量他們之間的余弦角θ（θ∈（0,π）），而余弦角的大小決定了兩個(gè)向量之間的相似度。比如，當(dāng)余弦角為0°時(shí)，說(shuō)明兩向量方向相同、線段重合；如果角度為90°，說(shuō)明兩向量形成直角，方向完全不相似；如果角度為180°，說(shuō)明兩向量方向剛好相反。因此，可以通過(guò)計(jì)算余弦角的大小來(lái)判斷兩向量的相似程度。夾角越小，說(shuō)明兩向量越相似。

余弦值的范圍在［-1,1］之間，余弦值越接近于1，代表兩個(gè)向量的方向越接近于0，他們的方向更加一致，相應(yīng)的相似度也越高。

在大數(shù)據(jù)分析中，余弦相似性已經(jīng)成為數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域的一個(gè)重要模塊。

2.3同態(tài)加密

1978年，在RSA密碼算法剛提出不久，Rivest等人提出了全同態(tài)加密算法的概念［9］。一個(gè)加密方案E如果滿足對(duì)密文做任意操作后再解密，其結(jié)果與對(duì)明文進(jìn)行相應(yīng)操作結(jié)果相同，就稱該加密方案是全同態(tài)加密方案。形式化描述為：Decrypt是方案E的解密算法，sk的私鑰，pk是公鑰，f（x1,x2,…,xt）是一個(gè)t元函數(shù)，則Decrypt（ f （c1,c2,…,ct）, sk）=f（m1,m2,…,mt）。目前的同態(tài)加密方案都是部分同態(tài)加密的，還沒(méi)有完全的全同態(tài)加密方案出現(xiàn)。同態(tài)加密方案目前滿足加同態(tài)和乘同態(tài)兩種運(yùn)算［10］。

本文采用快速Paillier加密算法［11］作為可驗(yàn)證部分的同態(tài)加密算法。

快速Paillier加密算法描述如下：

第三，解密，即：

加法同態(tài)性：

2.4不經(jīng)意傳輸協(xié)議

假設(shè)A有一個(gè)秘密，想以1/2的概率傳遞給B，即B有50%的機(jī)會(huì)收到這個(gè)秘密，另外50%的機(jī)會(huì)什么也沒(méi)有收到。協(xié)議完成后，B知道自己是否收到了這個(gè)秘密，但是A卻不知道B是否收到了這個(gè)秘密。這種協(xié)議稱為不經(jīng)意傳輸協(xié)議（Oblivious Transfer，OT）。

3　可驗(yàn)證的安全內(nèi)積計(jì)算協(xié)議的設(shè)計(jì)

3.1基本方案描述

3.2可驗(yàn)證的安全內(nèi)積計(jì)算協(xié)議

圖2　基本方案

協(xié)議2描述如下：

（1）Alice和Bob共同協(xié)商兩個(gè)n維隨機(jī)向量

（3）P收到Alice和Bob的秘密輸入后，計(jì)算

此方法將各自的秘密輸入外包到第三方，由第三方來(lái)執(zhí)行計(jì)算過(guò)程，減輕了參與方的計(jì)算壓力。但是，由于第三方P的存在，直接發(fā)送各參與方的秘密輸入易導(dǎo)致輸入方的隱私信息泄露，且第三方P并不是完全可信的，它不一定返回正確的內(nèi)積

（5）Alice和Bob對(duì)消息m1和m2進(jìn)行驗(yàn)證（此步驟可以單獨(dú)進(jìn)行，將在后文單獨(dú)給出），如果驗(yàn)證通過(guò)，則繼續(xù)協(xié)議；如果驗(yàn)證不通過(guò)，則終止協(xié)議；

（6）Alice和Bob通過(guò)計(jì)算：的消息給各參與方來(lái)進(jìn)行欺騙。

（8）待交換過(guò)程結(jié)束后，Alice和Bob就可以分別計(jì)算余弦值。步驟（5）中的驗(yàn)證過(guò)程如下：

Bob計(jì)算如下信息：

④同理，Alice和Bob互換角色再次執(zhí)行上述步驟①到③，Bob可對(duì)Alice的輸入進(jìn)行驗(yàn)證。

下面進(jìn)行安全性分析。

第一，步驟（2）和步驟（3）中，添加隨機(jī)向量的目的是增加Alice和Bob初始輸入向量的隨機(jī)性，同時(shí)保護(hù)各自的隱私信息；

第二，步驟（5）中增加了Alice和Bob對(duì)彼此消息的相互驗(yàn)證過(guò)程，防止了Alice和Bob之間的欺騙行為；

第三，步驟（6）中增加了Alice和Bob對(duì)內(nèi)積結(jié)果的驗(yàn)證過(guò)程，防止了不可信第三方P的欺騙行為。

此協(xié)議中由于不可信第三方的存在，在某種特定情形下并不完全安全。同時(shí)，由于存在證書交互過(guò)程，加大了通信成本。接下來(lái)，將設(shè)計(jì)一個(gè)無(wú)不可信第三方的無(wú)證書的可驗(yàn)證的安全多方計(jì)算協(xié)議。

3.2.2無(wú)不可信第三方的可驗(yàn)證的安全兩方內(nèi)積計(jì)算協(xié)議（協(xié)議3）

同樣，假設(shè)有兩個(gè)參與方Alice和Bob，分別擁有一個(gè)秘密向量，協(xié)議結(jié)束后輸出Alice和Bob的內(nèi)積。

協(xié)議3描述如下：

（1）Alice和Bob共同協(xié)商兩個(gè)整數(shù)p和m，使得pm足夠大；

（4）對(duì)每一個(gè)j=1,2,…,m，Alice和Bob按照以下步驟進(jìn)行計(jì)算：

（8）Bob收到消息后，首先驗(yàn)證消息｛｝' ue-是否等于步驟6中計(jì)算得到的｛｝ue-，如果相等，則說(shuō)明Alice正確發(fā)送消息；如果不等，則終止協(xié)議。

下面進(jìn)行安全性分析。

第一，在步驟（4）中，如果Bob想進(jìn)行猜測(cè)攻擊，那么他正確猜測(cè)的概率為，由于足夠大，因此其概率接近于0；

第二，在步驟（4）③中加入隨機(jī)數(shù)jr的目的是增加的隨機(jī)性，防止了Alice猜測(cè)Bob的秘密輸入向量的行為；

第三，無(wú)不可信第三方的存在，安全性較協(xié)議2高；

第四，步驟（6）到（8）主要用于驗(yàn)證，由于驗(yàn)證過(guò)程的存在，防止了Alice和Bob彼此的欺騙行為；

第五，此協(xié)議中沒(méi)有證書交互過(guò)程，通信成本較協(xié)議2更低。

4　結(jié) 語(yǔ)

現(xiàn)有的大多數(shù)安全多方計(jì)算協(xié)議沒(méi)有考慮參與方輸入輸出結(jié)果的驗(yàn)證?？紤]到這種情況，本文在總結(jié)前人的基礎(chǔ)上，設(shè)計(jì)了兩個(gè)可驗(yàn)證的安全內(nèi)積計(jì)算協(xié)議，彌補(bǔ)了大多數(shù)安全多方計(jì)算缺乏驗(yàn)證過(guò)程的缺陷，大大提高了安全多方計(jì)算協(xié)議的安全性。

［1］ Lu R X，Zhu H，Liu X M.Toward Efficient and Privacy-Preserving Computing in Big Data Era［J］.IEEE Network，2014，28（04）:46-50.

［2］ Wen Liang Du.A Study of Several Specific Secure Two-party Computation Problems［D］.USA:Purdue University，2000.

［3］ 耿濤.安全多方計(jì)算若干問(wèn)題以及應(yīng)用研究［D］.北京:北京郵電大學(xué)，2012. GENG Tao.Research on Several Secure Multi-party Computation Problems and Applications［D］.Beijing:Beijing University Of Posts And Telecommunications，2012.

［4］ De Xin Yang，ChunJing Lin，Bo Yang.A Novel Secure Cosine Similarity Computation Scheme With Malicious Adversaries［J］.International Journal of Network Security & Its Applications（IJNSA），2013，5（02）:171-178.

［5］ YAO A.C.Protocols for Secure Computations［J］.Foundations of Computer Science Annual Symposium on，1982:160-164.

［6］ Goldreich O，Micali S，Wigdeson A.How to Play Any Mental Game［C］.In Proceedings of the 19th Annual ACM Symposium on Theory of Computing，1987：217-229.

［7］ Chaum D，Crepeau C，Damgard I.Multiparty Unconditionally Secure Protocols［C］.In Proc.20th Annual Symposium on the Theory of Computing，1988:11-19.

［8］ ZHANG Lan，LI Xiang-Yang，LIU Yun-hao.Verifiable Private Multi-party Computation:Ranging and Ranking［J］. In Proceedings IEEE INFOCOM，2013，12（11）:605-609.

［9］ Rivest R L，Adleman L，Dertouzos M L.On Data Banks and Privacy Homomorphisms［J］.Foundations of Secure Computation，1978:169-179.

［10］ Gentry C，Halevi S.Fully Homomorphic Encryption over the Integers［D］.Palo Alto:Stanford University，2010.

［11］ Paillier P.Public-key Cryptosystems based on Composite Degree Residuosity Classes［J］.In Proc. of EUROCRYPT，1999，（05）:223-238.

［12］ Rabin M.How to Exchange Secrets with Oblivious Transfer，Technical Report TR-81，Aiken Computation Lab［D］.Cambridge:Harvard University，1981.

［13］ Ham L，Lin H.Noninteractive Oblivious Transfer［J］. Elcetronic Leters，1990，26（10）:635-636.

［14］ Naor M，Pinkas B.Oblivious Transfer and Polynomial Evaluation（Extended Abstract）［M］.Atanta:ACM press，1999.

冉 鵬（1991—），男，碩士，主要研究方向?yàn)槊艽a學(xué)理論與技術(shù)、安全多方計(jì)算；

張文科（1973—），男，碩士，高級(jí)工程師，主要研究方向?yàn)槊艽a理論與信息安全；

楊浩淼（1974—），男，博士，副教授，主要研究方向?yàn)槊艽a理論與技術(shù)。

Design and Implementation of Verifiable Secure Inner-Product Computation Protocols

RAN Peng1，2， ZHANG Wen-ke2， YANG Hao-miao1，2
（1.College of Computer Science and Engineering， University of Electronic Science and Technology of China， Chengdu Sichuan 611731， China；2.Laboratory of Science and Technology on Communication Security， Chengdu Sichuan 610041， China）

Secure multi-party computation is designed to solve the privacy-preserving cooperative computing problem between a set of mutually untrusting participants， since A.C.Yao proposed it in 1982，with the development of cloud computing， e-commerce technology， secure multi-party computation get more extensive research and application. Cosine similarity is an effective method to measure similarity between two sample points， which is widely applied in data mining， neural network and machine learning. At present， the most existing secure multi-party computation researches ignore the verification process of user’s inputs and results， all of which assume that each participant will follow the protocol honestly. So， in order to make up the blemish in this part， we design a verifiable secure inner-product computation protocol， which confirmed to be more secure.

secure inner-product computation； cosine similarity； privacy-preserving； verifiable

0　引 言

互聯(lián)網(wǎng)的快速發(fā)展，為協(xié)同計(jì)算提供了大量機(jī)會(huì)，其結(jié)果主要依賴于各個(gè)參與方的隱私輸入［1］。但是，由于互聯(lián)網(wǎng)的開放性，直接發(fā)送各自的輸入易導(dǎo)致隱私的泄露。因此，人們更希望能夠在安全環(huán)境下進(jìn)行各自協(xié)同計(jì)算，同時(shí)保護(hù)用戶各自的隱私信息不被泄露，這便是安全多方計(jì)算問(wèn)題。通常來(lái)講，安全多方計(jì)算（Secure Multi-Party Computation，SMC）問(wèn)題［2］是指在分布式網(wǎng)絡(luò)環(huán)境中，一組互不信任的用戶之間能夠在不泄露各自私有的輸入信息的情況下，協(xié)同執(zhí)行某個(gè)計(jì)算任務(wù)的問(wèn)題。如果存在一個(gè)可信的第三方（Trusted Third-Party，TTP），那么該類問(wèn)題就可以很好地解決。我們只需要每個(gè)參與方將各自的輸入分別發(fā)送給TTP，由TTP來(lái)進(jìn)行計(jì)算得到最后的結(jié)果，然后再將最后計(jì)算的結(jié)果廣播給各個(gè)參與方，這樣每個(gè)參與方就能得到正確的結(jié)果。但是，現(xiàn)實(shí)生活中很難找到這樣完全可信的第三方。因此，安全多方計(jì)算協(xié)議的研究應(yīng)運(yùn)而生。如今，安全多方計(jì)算在密碼學(xué)中擁有相當(dāng)重要的地位，在電子選舉、電子拍賣、電子投票、秘密分享門限簽名等場(chǎng)景中有著極其重要的作用。圖1說(shuō)明了安全多方計(jì)算在密碼學(xué)中的地位［3］。

National Natural Science Foundation of China （No.U1633114，No.U1333127）；International Science and Technology Cooperation and Exchange Program of Sichuan Province（No.2015HH0040）；China Postdoctoral Science Foundation-Funded Project（No.2014M562309）

TP309

A

1002-0802（2016）-10-1369-06

10.3969/j.issn.1002-0802.2016.10.020

2016-06-16；

2016-09-12

data:2016-06-16；Revised data:2016-09-12

國(guó)家自然科學(xué)基金（No.U1633114，No.U1333127）；四川省科技廳國(guó)際合作計(jì)劃（No.2015HH0040）；中國(guó)博士后科學(xué)基金資助項(xiàng)目（No.2014M562309）