可驗證的安全內積計算協議的設計與實現*

冉　鵬，張文科，楊浩淼

（1.電子科技大學計算機科學與工程學院，四川 成都 611731；2.中電集團30所保密通信重點實驗室，四川 成都 610041）

可驗證的安全內積計算協議的設計與實現*

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

（1.電子科技大學計算機科學與工程學院，四川 成都 611731；2.中電集團30所保密通信重點實驗室，四川 成都 610041）

安全多方計算旨在解決一組互不信任的參與方之間隱私保護的協同計算問題。自姚期智從1982年提出以來，隨著云計算、電子商務技術的發展，安全多方計算得到了更加廣泛的研究及應用。余弦相似性是用于度量兩個樣本點之間相似度的有效方法，且廣泛應用于數據挖掘、神經網絡和機器學習等領域。目前存在的大多數安全多方計算研究都忽略了用戶輸入和結果的驗證過程，都假設各參與方是誠實地執行協議。為了彌補這一塊的缺陷，設計了一種可驗證的安全內積計算的協議，并證實了此協議會更加安全。

安全內積計算；余弦相似性；隱私保護；可驗證

圖1　安全多方計算在密碼學中的地位

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

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

1　相關研究

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

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

2　基礎知識

2.1可驗證的安全多方計算

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

2.2余弦相似性

余弦相似性是度量兩個樣本點之間相似度的有效方法，主要度量他們之間的余弦角θ（θ∈（0,π）），而余弦角的大小決定了兩個向量之間的相似度。比如，當余弦角為0°時，說明兩向量方向相同、線段重合；如果角度為90°，說明兩向量形成直角，方向完全不相似；如果角度為180°，說明兩向量方向剛好相反。因此，可以通過計算余弦角的大小來判斷兩向量的相似程度。夾角越小，說明兩向量越相似。

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

在大數據分析中，余弦相似性已經成為數據挖掘和機器學習等領域的一個重要模塊。

2.3同態加密

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

本文采用快速Paillier加密算法［11］作為可驗證部分的同態加密算法。

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

第三，解密，即：

加法同態性：

2.4不經意傳輸協議

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

3　可驗證的安全內積計算協議的設計

3.1基本方案描述

3.2可驗證的安全內積計算協議

圖2　基本方案

協議2描述如下：

（1）Alice和Bob共同協商兩個n維隨機向量

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

此方法將各自的秘密輸入外包到第三方，由第三方來執行計算過程，減輕了參與方的計算壓力。但是，由于第三方P的存在，直接發送各參與方的秘密輸入易導致輸入方的隱私信息泄露，且第三方P并不是完全可信的，它不一定返回正確的內積

（5）Alice和Bob對消息m1和m2進行驗證（此步驟可以單獨進行，將在后文單獨給出），如果驗證通過，則繼續協議；如果驗證不通過，則終止協議；

（6）Alice和Bob通過計算：的消息給各參與方來進行欺騙。

（8）待交換過程結束后，Alice和Bob就可以分別計算余弦值。步驟（5）中的驗證過程如下：

Bob計算如下信息：

④同理，Alice和Bob互換角色再次執行上述步驟①到③，Bob可對Alice的輸入進行驗證。

下面進行安全性分析。

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

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

第三，步驟（6）中增加了Alice和Bob對內積結果的驗證過程，防止了不可信第三方P的欺騙行為。

此協議中由于不可信第三方的存在，在某種特定情形下并不完全安全。同時，由于存在證書交互過程，加大了通信成本。接下來，將設計一個無不可信第三方的無證書的可驗證的安全多方計算協議。

3.2.2無不可信第三方的可驗證的安全兩方內積計算協議（協議3）

同樣，假設有兩個參與方Alice和Bob，分別擁有一個秘密向量，協議結束后輸出Alice和Bob的內積。

協議3描述如下：

（1）Alice和Bob共同協商兩個整數p和m，使得pm足夠大；

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

（8）Bob收到消息后，首先驗證消息｛｝' ue-是否等于步驟6中計算得到的｛｝ue-，如果相等，則說明Alice正確發送消息；如果不等，則終止協議。

下面進行安全性分析。

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

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

第三，無不可信第三方的存在，安全性較協議2高；

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

第五，此協議中沒有證書交互過程，通信成本較協議2更低。

4　結 語

現有的大多數安全多方計算協議沒有考慮參與方輸入輸出結果的驗證。考慮到這種情況，本文在總結前人的基礎上，設計了兩個可驗證的安全內積計算協議，彌補了大多數安全多方計算缺乏驗證過程的缺陷，大大提高了安全多方計算協議的安全性。

［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］ 耿濤.安全多方計算若干問題以及應用研究［D］.北京:北京郵電大學，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—），男，碩士，主要研究方向為密碼學理論與技術、安全多方計算；

張文科（1973—），男，碩士，高級工程師，主要研究方向為密碼理論與信息安全；

楊浩淼（1974—），男，博士，副教授，主要研究方向為密碼理論與技術。

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　引 言

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

國家自然科學基金（No.U1633114，No.U1333127）；四川省科技廳國際合作計劃（No.2015HH0040）；中國博士后科學基金資助項目（No.2014M562309）