唐樂紅

摘要：隨著科技與網(wǎng)絡的發(fā)展，合作與隱私保護顯得越來越重要，這使得保護私有信息的計算幾何問題得到了更多的應用和發(fā)展。拋物線作為常見圓錐曲線的一種，在許多領域都有著廣泛的應用。本文通過已有的點積及百萬富翁協(xié)議，設計出直線與拋物線的位置關系協(xié)議，并對協(xié)議的正確性、安全性進行分析。

關鍵詞：計算幾何拋物線位置關系直線

引言

如何在各參與方互相不信任的情況下，以及保護各參與方輸入信息安全性的前提下，實現(xiàn)所有參與方協(xié)同完成某項計算幾何問題，這就是保護私有信息的計算幾何問題。例如iA開發(fā)商有計劃要在某區(qū)域建設一條曲線公路，B開發(fā)商也有計劃要在某區(qū)域建設一條直線公路，如何在不告訴對方自己計劃的情況下，求出A開發(fā)商計劃的公路與B開發(fā)商計劃的公路的位置關系。此時，可以把曲線公路抽象成數(shù)學上的一條曲線，直線公路抽象成數(shù)學上的一條線段。從而把問題轉化為求一條曲線與一條線段的位置關系問題。

本文所設計的協(xié)議是建立在半誠實模型下的。在此前提下，通過已有的點積協(xié)議以及百萬富翁協(xié)議，本文提出了直線與拋物線的位置關系協(xié)議以及線段與拋物線的位置關系協(xié)議。

1基礎協(xié)議介紹

1.1點積協(xié)議

點積協(xié)議現(xiàn)已成為計算幾何問題中的一個重要基礎協(xié)議。協(xié)議描述為：Alice擁有向量X一（x1，x2，…，xn），Bob擁有向量Y一（y1，y2，…，yn）。希望在保護各自私有向量的情況下，通過合作，使Alice獲得u=X.Y+v=∑ni=1xiyi+v的值，其中v是Bob選的隨機數(shù)。

I.2高效百萬富翁協(xié)議

高效百萬元富翁協(xié)議要求先構造出滿足一定的性質(zhì)函數(shù)F，還要先將待比較的兩個數(shù)寫成二進制的形式。若Alice有實數(shù)a，Bob有實數(shù)b。在保護各自信息的前提下，通過執(zhí)行高效百萬富翁協(xié)議，Alice得到a>b、a

l.3兩數(shù)相乘結果比較協(xié)議

輸入：Alice有向量A=（x1，x2，…，x。），Bob有向量A=（y1，y2，…，y.）。

輸出：A·B>O、A.B=O、A·B

執(zhí)行過程：

（1）執(zhí)行點積協(xié)議，Alice獲得u1=A·B+Vl的值，Vl是Bob選的隨機數(shù)。

（2）執(zhí)行高效百萬富翁協(xié)議，比較Ul與V1大小。最終由Alice將結果告知Bob，協(xié)議結束。

2直線與拋物線的位置關系協(xié)議

2.1問題分析

已知拋物線（y-yo）2=a（x-xo），且此處要求a>0，點po （x0，yo）是它的頂點，以及一條直線L：y=kx+m，要求k>0。請判斷出直線與拋物線的位置關系，也就是求出直線與拋物線是相離、相切還是相交的關系。直線與拋物線的位置關系如圖l所示。

先將拋物線方程與直線方程聯(lián)立，將得到新方程ky2_2ky0y-ay+kyn2Ta m+a kxo=0。

根據(jù)一元二次方程的性質(zhì)，可以容易求得此方程的根。方程的根有幾個就決定了直線與拋物線的交點有幾個。根據(jù)交點的個數(shù)，就可以很容易知道直線與拋物線的位置關系因為直線與拋物線無交點時，即為相離;有一個交點時，即為相切;有兩個不同的交點時，即為相交。所以，只需要根據(jù)交點的個數(shù)即可知道直線與拋物線的位置關系。最終，問題就可以轉化為判斷方程根的個數(shù)問題。

根據(jù)一元二次方程的性質(zhì)，可以知道根的個數(shù)可以通過△的大小來判斷。當AO時，方程有兩個實數(shù)根。根據(jù)方程，可以得到A=4kyoa_4kma_4k2ax.+a2。

2.2協(xié)議設計

輸入：Alice有拋物線（y-y_0）2=a（x-xo），且a>0。Bob有直線L：y=kx+m，且k>0。

輸出：直線與拋物線是相離，相切、相交。

執(zhí)行過程：

（1） Alice在本地生成私有向量A.=（yoa，a，axo，a2），Bob在本地生成私有向量B1=（4k，4km，4k2，1）。

（2） Alice和Bob共同執(zhí)行兩數(shù)相乘結果比較協(xié)議，就可得u，與v，大小關系，協(xié)議結束。

2.3協(xié)議分析

由協(xié)議可知，當UlV.時，直線與拋物線相交。

正確性分析：由協(xié)議內(nèi)容可知，u1-v1=A1·B1=4kyoa-4krna-4k2axo+a2=A。由△的大小就可知直線與拋物線的關系。所以，協(xié)議是正確的。

安全性分析：在步驟（2）中有信息交互，所以只需分析此步驟中的安全性。在步驟（2）中，Alice和Bob只調(diào)用了1次兩數(shù)相乘結果比較協(xié)議。此協(xié)議只調(diào)用1次點積和1次高效百萬富翁協(xié)議?；谶@兩個協(xié)議的安全性，Alice不能從u1推導出BOlD的數(shù)據(jù)B1，Bob也不能從v1推導出Alice的數(shù)據(jù)A1。但雙方均會知道△與O之間的關系。當相離時，雙方均得知A

綜上，Alice和BOb雙方的私有信息都不會泄露給對方，所以協(xié)議是安全的。

3結束語

本文先通過對問題的分析，將直線與拋物線的位置關系問題轉化為△問題，然后利用點積與高效百萬富翁協(xié)議提出了直線與拋物線的位置關系問題協(xié)議。最后對協(xié)議的正確性和安全性進行分析。

參考文獻

[1]劉文，羅守山，陳萍.保護私有信息的點線關系判定協(xié)議及其應用，北京郵電大學學報，2008，31（2）：72-75.

[2]Atallah M J，Du W.Secure multi-party computationalgeometry[C].Lecture Notes in ComputerScience 2125.Berlin：Springer，2001：165-179.

[3]李順東，戴一奇，游啟友，姚氏百萬富翁問題的高效解決方案.電子學報，2005，33（5）：769-773.