Abstract: Privacy-Preserving Computational Geometry（PPCG） is a hot research in relation to the Secure Multi-party Computation. The problem of the fermat problem’s extreme values is studied, which is a special case of PPCG and can be applied in many fields such as military and commercial fields. A novel computation protocol for the fermat problem’s extreme values is presented by using the technologies of Scalar Product Protocol which is used 6 times in a privacy-preserving situation. The protocol is much more simple and has more security which the third party is not used. At last, its correctness, security and efficiency are analyzed. The analysis shows that the proposed protocol is secure and has low complexity, and can be used to solve some other secure multi-party computation in computational geometry.

Key words: Secure-Multi-party Computation, privacy-preserving, computational geometry, fermat problem, extreme values

摘要： 隐私保护的计算几何问题是目前安全多方计算领域的一个研究热点。提出了一个费马问题的极值计算问题，费马问题已被广泛地运用在许多领域，比如军事、商业等领域。因此，在保证隐私的前提下，设计了一个基于点积协议的费马问题极值计算协议。提出的协议仅调用了6次点积协议，不仅简化了协议，而且没有使用第三方，安全性更高。给出了协议的正确性，而且对安全性和有效性都进行了详细的理论分析。分析结果标明，所提出的协议是安全的，而且协议复杂度低，也可用于解决其他一些安全多方的计算几何问题。

关键词: 安全多方计算, 隐私保护, 计算几何, 费马问题, 极值