直線與拋物線的位置關系問題

唐樂紅

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

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

引言

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

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

1基礎協議介紹

1.1點積協議

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

I.2高效百萬富翁協議

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

l.3兩數相乘結果比較協議

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

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

執行過程：

（1）執行點積協議，Alice獲得u1=A·B+Vl的值，Vl是Bob選的隨機數。

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

2直線與拋物線的位置關系協議

2.1問題分析

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

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

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

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

2.2協議設計

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

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

執行過程：

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

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

2.3協議分析

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

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

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

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

3結束語

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

參考文獻

[1]劉文，羅守山，陳萍.保護私有信息的點線關系判定協議及其應用，北京郵電大學學報，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.