直線與拋物線的位置關(guān)系問題

唐樂紅

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

關(guān)鍵詞：計(jì)算幾何拋物線位置關(guān)系直線

引言

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

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

1基礎(chǔ)協(xié)議介紹

1.1點(diǎn)積協(xié)議

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

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

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

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

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

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

執(zhí)行過程：

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

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

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

2.1問題分析

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

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

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

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

2.2協(xié)議設(shè)計(jì)

輸入：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ù)相乘結(jié)果比較協(xié)議，就可得u，與v，大小關(guān)系，協(xié)議結(jié)束。

2.3協(xié)議分析

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

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

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

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

3結(jié)束語

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

參考文獻(xiàn)

[1]劉文，羅守山，陳萍.保護(hù)私有信息的點(diǎn)線關(guān)系判定協(xié)議及其應(yīng)用，北京郵電大學(xué)學(xué)報(bào)，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]李順東，戴一奇，游啟友，姚氏百萬富翁問題的高效解決方案.電子學(xué)報(bào)，2005，33（5）：769-773.