凸多边形相似判定问题
2017-12-22唐乐红
洛阳师范学院学报 2017年11期
唐乐红
(福州阳光学院, 福建福州 350015)
凸多边形相似判定问题
唐乐红
(福州阳光学院, 福建福州 350015)
本文通过利用已有的秘密判定相等协议、 集合相等判定协议、 数据对应成比例判定协议, 设计出凸多边形相似判定协议, 并分析了其正确性、 安全性和复杂性.
计算几何; 集合相等; 凸多边形; 相似判定
0 引言
如果一个多边形的所有边中, 任意一条边向两方无限延长成为一条直线时, 其他各边都在这条直线的同一侧, 那么我们就称这个多边形为凸多边形(边数大于3). 生活中常见的正多边形等都是凸多边形. 判定两个凸多边形是否相似, 在数学、 物理等学科上都有很多的实际应用.
本文假定双方的计算环境是安全的, 且前提 是双方都能严格遵守协议的规程. 在满足以上条件的情况下, 利用秘密判定相等协议、 集合相等判定协议、 数据对应成比例判定协议, 本文设计出凸多边形相似判定协议.
1 基础协议
1.1 秘密判定相等协议
两个用户希望在不向对方泄露自己数据信息的情况下, 比较出各自所持有数据是否相等. 如果双方数据不相等时, 则要求任何一方都不能够知道对方的数据. 这就是秘密判定问题[1].
1.2 集合相等判定协议
两个用户各自拥有一个集合, 如何在不泄露双方各自集合信息的情况下, 判定出两个集合是否相等[2], 这就是集合相等判定问题. 协议具体如下:
输入: Alice拥有集合X={x1,…,xm},Bob拥有集合Y={y1,…,ym}.
输出: 谓词P(X,Y).
执行过程:


(3) Alice和Bob各自在本地利用商量好的散列函数, 计算出S′=hash(S)和T′=hash(T).……p>
登录APP查看全文
