隐私保护的两方几何圆位置关系判定

两圆间的位置关系判定问题是常见的几何计算问题之一.在保护两方各自输入圆信息的条件下,本文设计了一个隐私保护的两方几何圆位置关系判定方案,以实现在半诚实模型下安全地求解两圆间五种位置关系.本文运用Paillier同态加密技术实现了圆心间欧几里德距离的保密计算,通过将Paillier明文空间划分为两等长区间以实现解密结果在明文空间中正确映射的方法,提出隐私保护的欧几里德距离计算协议.此外,基于该协议我们设计了一个隐私保护的两圆间位置关系判定协议,在未泄露两圆半径与圆心等敏感信息的前提下提高了两方的计算效率.本文给出了方案具体的设计步骤、详细的安全性分析和实际的性能测试.实验结果表明,在两圆相距较近和相距较远的情况下判定两圆相离、外切、相交、内切和内含五种位置关系时,本方案均适用.同时,我们的方案具有计算复杂度不高及通信开销低等优势.

A Privacy-Preserving Positional Determining Protocol for Two Geometry Circles

The determination of the position relationship between two circles is one of the common geometric calculation problems. In order to protect the privacy of the position information of two parties, this paper designs a privacy-preserving scheme to determine the position relationship of two geometric circles which can solve the five position relations between two circles under the semi-honest model. The proposed scheme employs the Paillier encryption method to compute Euclidean distance of the centers secretly, then a privacy preserving computation protocol of Euclidean distance is proposed by dividing the plaintext space into two equal length intervals. The protocol can achieve the correct mapping of the decrypted result in the plaintext space. In addition, a privacy-preserving computation protocol of Euclidean distance is proposed and a privacy-preserving positional determining protocol is proposed for two geometry circles, which improves the computational efficiency of both parties without divulging the sensitive information such as the radius and center of the two circles. This paper gives the specific design steps, detailed security analysis and performance test of the scheme.The experimental results show that, regardless whether the two circles are close or far apart, the proposed scheme is applicable to determine the five positional relations of two circles, i.e., being separated, circumscribed, intersected, inscribed, and contained. Meanwhile, the proposed scheme has low computational complexity and low communication overhead.