直线与抛物线的位置关系问题

唐乐红

摘要：随着科技与网络的发展，合作与隐私保护显得越来越重要，这使得保护私有信息的计算几何问题得到了更多的应用和发展。抛物线作为常见圆锥曲线的一种，在许多领域都有着广泛的应用。本文通过已有的点积及百万富翁协议，设计出直线与抛物线的位置关系协议，并对协议的正确性、安全性进行分析。

关键词：计算几何抛物线位置关系直线

引言

如何在各参与方互相不信任的情况下，以及保护各参与方输入信息安全性的前提下，实现所有参与方协同完成某项计算几何问题，这就是保护私有信息的计算几何问题。例如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.