摘  要： 針對(duì)秘密判定兩組數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題提出一種新的解決方案，即運(yùn)用同態(tài)加密方案設(shè)計(jì)一個(gè)安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議，并利用此協(xié)議進(jìn)一步設(shè)計(jì)出安全判定兩組數(shù)據(jù)對(duì)應(yīng)成比例協(xié)議和安全判定空間中兩平面的位置協(xié)議。該方法不但解決了安全判定兩組數(shù)據(jù)對(duì)應(yīng)成比例問(wèn)題，還解決了空間兩平面的相對(duì)位置判定問(wèn)題。與以前的解決方案相比，設(shè)計(jì)方案不但提高了協(xié)議的效率，還降低了通信量。
關(guān)鍵詞： 計(jì)算幾何；數(shù)據(jù)對(duì)應(yīng)成比例個(gè)數(shù)；數(shù)據(jù)對(duì)應(yīng)成比例協(xié)議

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

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)加密方案，因?yàn)榧油瑧B(tài)加密方案是安全多方計(jì)算的基礎(chǔ)知識(shí)，其加密的基本思想已經(jīng)被眾人所熟知，所以此處不再贅述。
2 安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議
2.1 問(wèn)題描述
　安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議(下簡(jiǎn)稱協(xié)議1)問(wèn)題可以描述為：Alice擁有私有數(shù)據(jù)X=(x1，x2，…，xn)，Bob擁有私有數(shù)據(jù)Y=(y1，y2，…，yn)，他們希望在不向?qū)Ψ叫孤蹲约旱男畔r(shí)能判斷出彼此對(duì)應(yīng)成比例的個(gè)數(shù)，除此之外，不能得到對(duì)方的任何其他信息。
2.2 安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議的設(shè)計(jì)
　協(xié)議的主要思想是：首先將兩方的n個(gè)私有數(shù)據(jù)各自分解成n-1個(gè)私有分量，每個(gè)分量中只包含相鄰的兩個(gè)私有數(shù)據(jù)。然后，對(duì)每個(gè)分量分別秘密求解，看兩方分量中的數(shù)據(jù)是否對(duì)應(yīng)成比例，如果數(shù)據(jù)是對(duì)應(yīng)成比例的，則統(tǒng)計(jì)數(shù)據(jù)是對(duì)應(yīng)成比例的變量N+1。這個(gè)過(guò)程中用到了數(shù)據(jù)加密技術(shù)和同態(tài)加密方案。最后，由N的值判定兩組數(shù)據(jù)中對(duì)應(yīng)成比例的個(gè)數(shù)。協(xié)議設(shè)計(jì)如下：

　⑥i++。
　(3)Alice將最終的N值告訴Bob。
2.3 協(xié)議的安全性與復(fù)雜度分析
　安全性分析：由于Alice傳給Bob的數(shù)據(jù)都是通過(guò)其公鑰進(jìn)行加密的，因此Bob是無(wú)法獲得Alice的私有數(shù)據(jù)；而B(niǎo)ob的數(shù)據(jù)都是通過(guò)其自身的隨機(jī)數(shù)加密傳給Alice的，所以計(jì)算的過(guò)程中Alice無(wú)法獲得Bob的私有數(shù)據(jù)。協(xié)議結(jié)束時(shí)，雖然Alice知道n-1個(gè)Si′=xiyi+1-xi+1yi的方程，但這些方程中含有n個(gè)未知數(shù)yi(i=1，2，......，n)，所以Alice不能由它掌握的數(shù)據(jù)推出任何關(guān)于Bob的信息。因此協(xié)議1是安全的。
復(fù)雜度分析：協(xié)議1的計(jì)算復(fù)雜度表現(xiàn)在對(duì)數(shù)據(jù)利用同態(tài)加密方案進(jìn)行計(jì)算的過(guò)程中。所以計(jì)算效率較高，協(xié)議1的通信代價(jià)次數(shù)為3n-2次。

3.1.2 安全求解兩組數(shù)據(jù)是否對(duì)應(yīng)成比例協(xié)議的設(shè)計(jì)
　協(xié)議的主要思想是：首先將兩方的n個(gè)私有數(shù)據(jù)執(zhí)行安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議。最后，由協(xié)議的結(jié)果N的值判定兩組數(shù)據(jù)是否對(duì)應(yīng)成比例。協(xié)議設(shè)計(jì)如下：
輸入：Alice擁有私有數(shù)據(jù)X=(x1，x2，…，xn)，Bob擁有私有數(shù)據(jù)Y=(y1，y2，…，yn)。
輸出：Alice和Bob在不泄露自己信息的情況下安全地判定他們是否對(duì)應(yīng)成比例。
　(1)Alice和Bob協(xié)同執(zhí)行協(xié)議1。
　(2)Alice在本地判斷N值是否等于n-1，如果N= n-1，兩組數(shù)據(jù)是對(duì)應(yīng)成比例；如果0≤N＜n-1，則兩組數(shù)據(jù)不對(duì)應(yīng)成比例。
　(3)Bob在本地判斷N值是否等于n-1，如果N=n-1，兩組數(shù)據(jù)是對(duì)應(yīng)成比例；如果0≤N＜n-1，則兩組數(shù)據(jù)不對(duì)應(yīng)成比例。
3.2 安全判定空間中兩平面的相對(duì)位置協(xié)議
3.2.1 問(wèn)題描述
　空間中兩平面相對(duì)位置關(guān)系判定問(wèn)題可以描述為：Alice擁有一個(gè)平面h1：A1x+B1y+C1z+D1=0，Bob擁有一個(gè)平面h2：A2x+B2y+C2z+D2=0，他們希望在不向?qū)Ψ叫孤蹲约旱男畔r(shí)能判斷出這兩個(gè)平面的相對(duì)位置關(guān)系。
3.2.2 安全判定空間中兩平面的相對(duì)位置協(xié)議的設(shè)計(jì)
　協(xié)議的主要思想是：首先將兩方各自輸入的4個(gè)私有數(shù)據(jù)協(xié)同執(zhí)行安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議。最后，根據(jù)引理1的結(jié)論，對(duì)協(xié)議的結(jié)果N的值進(jìn)行比較，從而判定空間中兩平面的相對(duì)位置關(guān)系。協(xié)議設(shè)計(jì)如下：
輸入：Alice擁有一個(gè)平面h1：x1X+x2Y+x3Z+x4=0，Bob擁有一個(gè)平面h2：y1X+y2Y+y3Z+y4=0。
　輸出：Alice和Bob在不泄露自己信息的情況下能安全地判斷出這兩個(gè)平面的相對(duì)位置關(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ù)向量的情況下能安全地判定他們對(duì)應(yīng)成比例的個(gè)數(shù)N。
　(1)Alice在本地判斷，當(dāng)N=3時(shí)，空間中兩平面是重合的；當(dāng)N=2時(shí)，空間中兩平面是平行的；當(dāng)N=0或1時(shí)，空間中兩平面是相交的。
　(2)Bob在本地判斷，當(dāng)N=3時(shí)，空間中兩平面是重合的；當(dāng)N=2時(shí)，空間中兩平面是平行的；當(dāng)N=0或1時(shí)，空間中兩平面是相交的。
　本文在已有的研究基礎(chǔ)上，設(shè)計(jì)了一個(gè)安全求解兩組數(shù)據(jù)中對(duì)應(yīng)成比例個(gè)數(shù)協(xié)議。并且利用此協(xié)議進(jìn)一步設(shè)計(jì)出安全求解兩組數(shù)據(jù)對(duì)應(yīng)成比例協(xié)議和安全判定空間中兩平面的相對(duì)位置協(xié)議。本協(xié)議雖然能很好地解決此類相關(guān)問(wèn)題，提高了協(xié)議的效率，并降低了通信量。但是其安全性還有待于進(jìn)一步的提高，此問(wèn)題將在以后的工作中進(jìn)行進(jìn)一步研究，以設(shè)計(jì)出更好的協(xié)議。
參考文獻(xiàn)
[1] YAO A C.  Protocols for secure computations [C] . In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science， Chicago， USA， 1982：160-164.
[2] ATALLAH M J， Du Wenliang .  Secure multi-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] 羅永龍，黃劉生.空間幾何對(duì)象相對(duì)位置判定中的私有信息保護(hù)[J].計(jì)算機(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， Lecture Notes in Computer Science， Springer-Verlag， 1999，1592：223-238.