隱私保護的計算三角形面積協議

摘要:在保護隱私的條件下，目前已有的計算面積協議都是兩方。該文提出了兩個基于同態加密的三方計算三角形面積協議，并對這兩個協議的安全性和計算復雜度進行了分析。協議中三個參與方各自擁有一個點，共同計算出參與方擁有的點所圍成的三角形的面積，同時確保不泄漏自己的私有信息。

關鍵詞:保護隱私;同態加密;計算幾何;三角形

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)33-9168-03

A Privacy-preserving Protocol on Calculating the Area of Triangle

LU Lei-ji1， HUANG Hong-sheng2， FANG Zhi1

(1.The Basis of the Department of Computing in the Artillery Academy ， Hefei 230031， China;2.The College of Computer Science and Technology in Anhui University，Hefei 230039， China)

Abstract: Under the condition of privacy preserved， existing protocols on calculating area are executed by two-party. Based on homomorphic encryption， two protocols are proposed which is used to solve the problem of calculating the area of triangle by three-party. The security and computational complexity of two protocols are as well analyzed. Each of three-party has one point and they want to cooperatively calculate the triangle which is formed by their points without bringing risk to private information.

Key words: privacy-preserving; homomorphic encryption; computational geometry; triangle

安全多方計算問題由A.C.Yao首先提出的，安全多方計算的主要思想是:參與計算的多方合作計算一個約定函數，任何一方都不愿意泄露自己的輸入信息，計算結束后每個參與方都知道這個函數的輸出(沒有人知道其他參與者輸入的任何信息)。安全多方計算協議利用了許多基礎的密碼學協議，同時安全多方計算協議中的一些理論和解決問題的思路又可以應用到許多其他密碼學協議。利用安全多方計算協議，即可以實現網上的合作，又可以保證信息的安全性。因此安全多方計算在安全計算幾何、電子投票、電子拍賣以及秘密共享等多方面有非常廣泛的應用。Attallah和Du在文獻[1-2]首先提出了安全多方計算幾何的概念，介紹了點包含、多邊形相交、最近點對以及凸包問題。文獻[3]提出了一個兩方計算面積協議。文獻[4-5]分別提出了一個距離計算協議。然而，上述文獻僅僅對兩方之間的幾何問題的研究，涉及到多方的幾何問題相對較少，我們在此提出了這個問題的解決方案并證明了方案的保密性。本文基于同態加密體制設計了兩個計算面積協議:協議一用到了計算距離協議并實現了在保護隱私條件下三方合作計算面積;協議二用另一種方法實現了三方安全保密計算面積。

該文的組織結構如下:第1節簡單介紹本文所用到的基礎知識和概念;第2節重點提出了兩個三方計算面積協議，并對其進行了詳細介紹以及安全性與復雜度分析;最后是對本協議的總結。

1 預備知識

以下給出本方案所用到的相關基礎工具的簡介，如下:

1.1 安全性定義

半誠實參與方安全多方計算的參與方誠實地執行協議，參與方可以記錄中間結果，以試圖推導出其他參與方的輸入。計算結束后，參與方均不能從自己的輸入與輸出中得到關于其他參與方輸入的任何信息。

1.2 同態加密

Sander和Tschudin提出了整數環上的加法和乘法同態加密機制(HES)。同態加密算法是指具有同態性質的公鑰加密體制。同態加密必須滿足下面的條件:如果存在運算*和運算+，使得對任意x 、y，有E(x)*E (y)=E(x+y)，稱加密函數E是同態的。由上述等式可知，顯然有E(x)*E (-y)=E(x-y)和E(x)y= E(x y)成立。這里要說明的是，公式中符號“=”的含義為等效，即符號兩邊的密文是等效的，而不是嚴格意義上的相等。常見的同態加密有ElGamal和Paillier加密。

2 三方計算面積協議的設計

2.1 問題描述

在同一平面區域上，有三個參與方，Alice有一個點A=(xA，yA)，Bob有一個點B=(xB，yB)，Carol有一個點C=(xC，yC)，該三方之間的線段距離分別為:d1、d2和d3，如圖1所示。三個參與方都不想把自己點的私有信息(點的坐標)告訴其他人，又想知道三個參與方的點所構成的三角形的面積的大小。兩點(P，Q)間的距離 可以間接地通過下面的表達式求出:d2(P，Q)=(xP-xQ)2+(yP-yQ)2。

2.2 協議一

2.2.1 初始化階段

Alice、Bob和Carol都有自己的密碼系統且該密碼系統具有同態性，保密自己的私鑰并向其他兩人公布了自己的公鑰，其中EA()、EB()和EC()分別表示用Alice、Bob和Carol的公鑰加密。

2.2.2 協議執行階段

步驟一 Alice —> Bob:EA(xA2+yA2)， EA(-2xA)， EA(-2yA)

步驟二 Bob計算:

Bob —> Alice:EA(d12)

步驟三 Alice 解密計算得:d1

Alice —> Bob:d1

Alice —> Carol:d1

這樣Alice、Bob和Carol得知一條邊的距離為:d1

(由于Alice和Carol交互計算另一邊的距離d2，以及Bob和Carol交互計算第三邊的距離d3的過程與上述相同，我們不再贅述。)

步驟四Alice、Bob和Carol都知道了:d1、d2和d3，根據海倫公式他們三人都可以求解三角形面積S:

，其中p=1/2(d1+d2+d3)

2.3 協議二

2.3.1 三點面積公式

由幾何知識知三點(xA，yA)、(xB，yB)、(xC，yC)所圍成的面積S:

2.3.2 協議執行階段

步驟一 Alice、Bob和Carol商定一個具有同態性質的密碼系統，Alice選定公私鑰對，并將公鑰告訴Bob和Carol，私鑰保密，其中EA()表示用Alice的公鑰加密。

步驟二 Bob —> Carol:EA(xB)，EA(-xB)，EA(yB)，EA(-yB)

步驟三 Carol計算:EA (xC)*EA (-xB) = EA (xC-xB)

EA (yB)*EA (-yC) = EA (yB-yC)

EA (xB) yC *EA (-yB)xC= EA(xByC - yBxC)

Carol —> Alice:EA (xC-xB)，EA (yB -yC)，EA(xByC - yBxC)

步驟四 Alice計算:EA (yB-yC)xA*EA (xC-xB)yA*EA(xByC - yB xC)

= EA (xAyB +xByC +xCyA-yAxB - yB xC- yC xA)

最后解密并計算出面積S= (xA yB + xB yC +xCyA-yAxB -yBxC- yCxA)

Alice —> Bob:S

Alice —> Carol:S

2.4 安全性及復雜度分析

正確性分析:由于同態加密的性質可知，只要保證加密和解密過程以及計算過程的正確，就可以保證得到的結果，從而最后所求的面積是正確的。

安全性分析:協議一:步驟二中Bob不知道解密密鑰，就無法得知Alice的信息;步驟三中解密得d1，但是并不知道Bob的坐標，只知道Bob點在以自己的點為中心，以d1為半徑的圓周上，故Alice推不出Bob的點的坐標。所以該協議都是安全的且沒有信息泄漏。協議二:Bob和Carol都不知道解密密鑰，只有Alice知道，最后解密出面積S，協議二的安全性在于同態加密的安全性。

復雜度分析:協議一:計算一邊距離時進行了4次加密計算、1次解密計算以及一些簡單運算，進行了4次通信，一共進行了3輪，即求三邊距離。協議二:Bob進行了4次加密，Carol進行了2次加密和5次運算，Alice進行了4次運算和1次解密操作，共進行4次通信。而且與協議一不同，只需一輪。

3 結束語

該文提出了兩個在半誠實模型下保護隱私的三方計算面積協議。這個問題包含三個參與方，每個參與方都希望在不泄漏自己的信息(點的坐標)的情況下，共同計算出參與方擁有的點所圍成的三角形的面積。設計了兩個協議，來求解這個問題。協議一利用海倫公式來求解三角形面積，該協議泄露了部分信息，即參與方都知道了三角形的具體形狀，但是不知道具體位置;協議二利用平面上的三點所確定的行列式的值來求解三角形面積，該協議沒有泄露任何信息。

參考文獻:

[1] ATALLAH M J，DU W L，Secure Multi-party Computational Geometry[C]//Proceedings of the 7th International Workshop on Algorithms and Data StructuresmLNCS 2139，Berlin:Springer-Verlag，2001:165-179.

[2] DU W L，ATALLAH M J.Secure Multi-Party Computation Problems and Their Applications:A Review and Open Problems[C]//In Proceedings of New Security Paradigms Workshop.New Mexico:Cloudcroft，2001:11-20.

[3] DAS A S，SRINATHAN K.Privacy Preserving Cooperative Clustering Service[C]//Advanced Computing and Communications.Washington，DC:IEEE Computer Society，2007:435-440.

[4] LI S D，DAI Y Q.Secure two-party computational geometry[J].Journal of Computer Science and Technology，2005，20(2):258-263.

[5] 羅永龍.安全多方計算中的若干關鍵問題及其應用研究[D].合肥:中國科技大學，2005.