安全判定兩組數據對應成比例的新方法＊

趙 玉，仲 紅，易 磊

(安徽大學 計算機科學與技術學院，安徽 合肥 230039)

安全多方計算SMC(Secure Multi-Party Computation)[1]是研究一組互不信任的參與方在保護各自私有輸入信息的前提下進行的合作計算問題。計算結束后，各個參與方除了獲得計算結果外，不能獲得其他任何信息。保護私有信息的計算幾何[2]己成為安全多方計算的一個重要分支，其具體定義的模型為：保護私有信息的計算幾何問題的研究就是要設計出相應的協議算法，使得相互合作的用戶在計算過程中既能使用對方的有關隱私信息(如點、線段、多邊形、平面等)，又不可能獲得其具體值。迄今為止，如何設計高效而安全的計算幾何協議仍是一個極具挑戰的研究課題。參考文獻[3]中首次提出了一個秘密判定兩組數據對應成比例判定協議，并基于該協議解決了空間幾何平面與平面之間的相對位置判定問題。本文在前人的研究基礎上對此類問題進行了改善，即運用同態加密方案設計一個安全求解兩組數據中對應成比例個數協議。并且利用此協議進一步設計出安全求解兩組數據對應成比例協議和安全判定空間中兩平面的相對位置協議。本研究不但解決了安全判定兩組數據對應成比例問題，還解決了空間兩平面的相對位置判定問題。它們都是保護私有信息的計算幾何的基本問題，同時對于研究安全的空間幾何對象相對位置問題有著重要的指導意義。

1 相關知識

1.1 基礎知識

引理 1[4]空間兩個平面 h1：A1x+B1y+C1z+D1=0和h2：A2x+B2y+C2z+D2=0的相對位置關系判定如下：

(1)相 交?A1∶B1∶C1≠A2∶B2∶C2；

1.2 同態加密方案

就目前大多數同態加密方案而言，同態加密方案可以分為乘同態加密方案和加同態加密方案。若加密方案滿足 Ek(x)·Ek(y)=Ek(x×y)，則稱其為乘同態，如 ElGamal加密方案[5]。 若加密方案滿足 Ek(x)·Ek(y)=Ek(x+y)，則稱其為加同態，如Paillier加密方案[6]。本文使用的是加同態加密方案，因為加同態加密方案是安全多方計算的基礎知識，其加密的基本思想已經被眾人所熟知，所以此處不再贅述。

2 安全求解兩組數據中對應成比例個數協議

2.1 問題描述

安全求解兩組數據中對應成比例個數協議 (下簡稱協議 1)問題可以描述為：Alice擁有私有數據 X=(x1，x2，…，xn)，Bob 擁有私有數據 Y=(y1，y2，…，yn)，他們希望在不向對方泄露自己的信息時能判斷出彼此對應成比例的個數，除此之外，不能得到對方的任何其他信息。

2.2 安全求解兩組數據中對應成比例個數協議的設計

協議的主要思想是：首先將兩方的n個私有數據各自分解成n-1個私有分量，每個分量中只包含相鄰的兩個私有數據。然后，對每個分量分別秘密求解，看兩方分量中的數據是否對應成比例，如果數據是對應成比例的，則統計數據是對應成比例的變量N+1。這個過程中用到了數據加密技術和同態加密方案。最后，由N的值判定兩組數據中對應成比例的個數。協議設計如下：

輸入：Alice 擁有私有數據 X=(x1，x2，…，xn)，Bob 擁有私有數據 Y=(y1，y2，…，yn)。

輸出：Alice和Bob在不泄露自己信息的情況下安全求解兩組數據中對應成比例個數。

(1)Alice構造一個變量N，并使其滿足N=0。

(2)for i=1 to n-1時，執行以下步驟：

①Alice 在本地生成 Xi=(xi，xi+1)；

②Bob 在本地生成 Yi=(yi，yi+1)， 并計算 Y′i=(yi-r，yi+1-r)，其中r為 Bob 的隨機數，將 Y′i傳送給 Alice；

③Alice使用其公鑰 Ea加密數據得 Ea(xi)、Ea(-xi+1)、Ea(xi(yi+1-r))及Ea(-xi+1(yi-r))，并將加密后的密文全部傳給Bob；

④Bob計算Ui=Ea(xi)rEa(xi(yi+1-r))=Ea(xir+xiyi+1-xir)=Ea(xiyi+1)，Vi=Ea(-xi+1)rEa(-xi+1(yi-r))=Ea(-xi+1r-xi+1yi+xi+1r)=Ea(-xi+1yi)，那么 Si=UiVi=Ea(xiyi+1)Ea(-xi+1yi)=Ea(xiyi+1-xi+1yi)，并將 Si傳給 Alice；

⑤ Alice 解 密 Si， 得 Si′=xiyi+1-xi+1yi， 如 果 Si′=0， 則N++；

⑥i++。

(3)Alice將最終的N值告訴Bob。

2.3 協議的安全性與復雜度分析

安全性分析：由于Alice傳給Bob的數據都是通過其公鑰進行加密的，因此Bob是無法獲得Alice的私有數據；而Bob的數據都是通過其自身的隨機數加密傳給Alice的，所以計算的過程中Alice無法獲得Bob的私有數據。協議結束時，雖然Alice知道n-1個Si′=xiyi+1-xi+1yi的方程，但這些方程中含有 n個未知數 yi(i=1，2，......，n)，所以Alice不能由它掌握的數據推出任何關于Bob的信息。因此協議1是安全的。

復雜度分析：協議1的計算復雜度表現在對數據利用同態加密方案進行計算的過程中。所以計算效率較高，協議1的通信代價次數為3n-2次。

3 安全求解兩組數據中對應成比例個數協議的應用

3.1 安全判定兩組數據對應成比例協議

3.1.1問題描述

3.1.2安全求解兩組數據是否對應成比例協議的設計

協議的主要思想是：首先將兩方的n個私有數據執行安全求解兩組數據中對應成比例個數協議。最后，由協議的結果N的值判定兩組數據是否對應成比例。協議設計如下：

輸入 ：Alice 擁有 私 有數 據 X=(x1，x2， … ，xn)，Bob 擁有私有數據 Y=(y1，y2，…，yn)。

輸出：Alice和Bob在不泄露自己信息的情況下安全地判定他們是否對應成比例。

(1)Alice和Bob協同執行協議1。

(2)Alice在本地判斷N值是否等于n-1，如果N=n-1，兩組數據是對應成比例；如果 0≤N＜n-1，則兩組數據不對應成比例。

(3)Bob在本地判斷N值是否等于n-1，如果N=n-1，兩組數據是對應成比例；如果 0≤N＜n-1，則兩組數據不對應成比例。

3.2 安全判定空間中兩平面的相對位置協議

3.2.1問題描述

空間中兩平面相對位置關系判定問題可以描述為：Alice擁有一個平面 h1：A1x+B1y+C1z+D1=0，Bob擁有一個平面h2：A2x+B2y+C2z+D2=0，他們希望在不向對方泄露自己的信息時能判斷出這兩個平面的相對位置關系。

3.2.2安全判定空間中兩平面的相對位置協議的設計

協議的主要思想是：首先將兩方各自輸入的4個私有數據協同執行安全求解兩組數據中對應成比例個數協議。最后，根據引理1的結論，對協議的結果N的值進行比較，從而判定空間中兩平面的相對位置關系。協議設計如下：

輸入：Alice擁有一個平面 h1：x1X+x2Y+x3Z+x4=0，Bob擁有一個平面 h2：y1X+y2Y+y3Z+y4=0。

輸出：Alice和Bob在不泄露自己信息的情況下能安全地判斷出這兩個平面的相對位置關系。

Alice 在 本 地 構 造 系 數 向 量 X=(x1，x2，x3，x4)；Bob 在本地構 造系數向量 Y=(y1，y2，y3，y4)。 Alice 和 Bob 協同執行協議1，即Alice和Bob在不泄露自己系數向量的情況下能安全地判定他們對應成比例的個數N。

(1)Alice在本地判斷，當N=3時，空間中兩平面是重合的；當N=2時，空間中兩平面是平行的；當N=0或 1時，空間中兩平面是相交的。

(2)Bob在本地判斷，當N=3時，空間中兩平面是重合的；當N=2時，空間中兩平面是平行的；當N=0或 1時，空間中兩平面是相交的。

本文在已有的研究基礎上，設計了一個安全求解兩組數據中對應成比例個數協議。并且利用此協議進一步設計出安全求解兩組數據對應成比例協議和安全判定空間中兩平面的相對位置協議。本協議雖然能很好地解決此類相關問題，提高了協議的效率，并降低了通信量。但是其安全性還有待于進一步的提高，此問題將在以后的工作中進行進一步研究，以設計出更好的協議。

[1]YAO A C. Protocols for secure computations [C].In Proceedingsofthe 23rd AnnualIEEE Symposium on Foundations of Computer Science， Chicago， USA， 1982：160-164.

[2]ATALLAH M J，Du Wenliang. Securemulti-party computational geometry[C]. The 7th Int’l Workshop on Algorithms and Data Structures(WADS 2001)， Providence，Rhode Island， USA， 2001，2125：165-179.

[3]羅永龍，黃劉生.空間幾何對象相對位置判定中的私有信息保護[J].計算機研究與發展，2006，43(3)：410-416.

[4]丘維聲.解析幾何[M].北京：北京大學出版社，1996.

[5]ELGAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory， 1985，31(4)：469-472.

[6]PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[C].Advances in Cryptology-EUROCRYPT’99， LectureNotesin ComputerScience，Springer-Verlag， 1999，1592：223-238.