點和區間包含問題的保密計算

吳宏鋒　胡振華

摘? ?要：安全多方計算問題是近年來密碼學研究的熱點問題，其中多方保密計算是網絡空間隱私保護與信息安全的關鍵技術。文章研究了計算幾何中有理數域內點和區間包含問題的保密計算問題，即保密的判定一個隱私的有理數是否屬于一個保密的有理區間。文章利用安全多方計算的思想設計了一個高效的安全協議，并證明了協議在半誠實模型下的安全性，與現有的其他文獻相比，本文的協議具有更低的計算復雜度。

關鍵詞：密碼學;安全多方計算;點與區間的保密計算;計算幾何

中圖分類號： TP309? ? ? ? ? 文獻標識碼：A

Abstract： The problem of secure multi-party computing is a hot issue in cryptography research in recent years. Among them， multi-party secret computing is a key technology for privacy protection and information security in cyberspace. In this paper， we study the secret calculation problem of the inclusion problem of points and intervals in the field of rational numbers in computational geometry， that is， whether the privacy rational number belongs to a confidential rational interval. This paper uses the idea of secure multi-party computing to design an efficient security protocol， and proves the security of the protocol under the semi-honest model. Compared with other existing literature， the computational complexity of this protocol is lower.

Key words： cryptography; secure multiparty computation; secret computation of points and intervals; computing geometry

1 引言

安全多方計算（Secure Multi-Party Computation，SMC）問題是從具體的密碼學問題中抽象出來的，對它的研究以及由此得到的一些結論對具體的密碼學問題有著指導意義，它可以從原則上告訴人們哪些問題是可以解決的，哪些是不可以解決的。但是，由于安全多方計算問題是一個非常抽象的問題，使得人們很難找到有效的算法去實現它，從而導致了它在具體應用上的局限性。對于一個具體的密碼學問題，可以先根據安全多方計算的結論在原則上確定這個問題是否可以解決，如果可以解決，就需要具體問題具體分析，尋找解決該問題的具體解決方案。實際上，安全多方計算蘊含了對任何密碼學協議問題在原則上的實現方案，它是分布式密碼學和分布式計算研究的一個基本問題。

安全多方計算最早是由Yao[1]在1942年通過百……