趙 玉，仲 紅，易 磊

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

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

1 相關(guān)知識

1.1 基礎(chǔ)知識

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

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

1.2 同態(tài)加密方案

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

2 安全求解兩組數(shù)據(jù)中對應(yīng)成比例個數(shù)協(xié)議

2.1 問題描述

安全求解兩組數(shù)據(jù)中對應(yīng)成比例個數(shù)協(xié)議 (下簡稱協(xié)議 1)問題可以描述為：Alice擁有私有數(shù)據(jù) X=(x1，x2，…，xn)，Bob 擁有私有數(shù)據(jù) Y=(y1，y2，…，yn)，他們希望在不向?qū)Ψ叫孤蹲约旱男畔r能判斷出彼此對應(yīng)成比例的個數(shù)，除此之外，不能得到對方的任何其他信息。

2.2 安全求解兩組數(shù)據(jù)中對應(yīng)成比例個數(shù)協(xié)議的設(shè)計

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

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

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

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

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

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

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

③Alice使用其公鑰 Ea加密數(shù)據(jù)得 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 協(xié)議的安全性與復(fù)雜度分析

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

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

3 安全求解兩組數(shù)據(jù)中對應(yīng)成比例個數(shù)協(xié)議的應(yīng)用

3.1 安全判定兩組數(shù)據(jù)對應(yīng)成比例協(xié)議

3.1.1問題描述

3.1.2安全求解兩組數(shù)據(jù)是否對應(yīng)成比例協(xié)議的設(shè)計

協(xié)議的主要思想是：首先將兩方的n個私有數(shù)據(jù)執(zhí)行安全求解兩組數(shù)據(jù)中對應(yīng)成比例個數(shù)協(xié)議。最后，由協(xié)議的結(jié)果N的值判定兩組數(shù)據(jù)是否對應(yīng)成比例。協(xié)議設(shè)計如下：

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

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

(1)Alice和Bob協(xié)同執(zhí)行協(xié)議1。

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

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

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

3.2.1問題描述

空間中兩平面相對位置關(guān)系判定問題可以描述為：Alice擁有一個平面 h1：A1x+B1y+C1z+D1=0，Bob擁有一個平面h2：A2x+B2y+C2z+D2=0，他們希望在不向?qū)Ψ叫孤蹲约旱男畔r能判斷出這兩個平面的相對位置關(guān)系。

3.2.2安全判定空間中兩平面的相對位置協(xié)議的設(shè)計

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

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

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

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

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

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

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

[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].計算機研究與發(fā)展，2006，43(3)：410-416.

[4]丘維聲.解析幾何[M].北京：北京大學(xué)出版社，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.