一些基于私有信息保護的計算幾何問題研究.pdf

1、多方保密計算是近幾年國際密碼學界的一個研究熱點。它的應(yīng)用范圍很廣，比如數(shù)據(jù)挖掘、科學計算、數(shù)據(jù)庫利用等等，已成為密碼學領(lǐng)域里一個極端重要的工具，計算領(lǐng)域里一個必不可少的組成部分。雖然一般的多方保密計算問題在理論上可解，但是理論解決方案可能因為效率或計算量的問題而在實際上并不可行，具體問題需要研究具體的解決方案。因此，研究各種各樣的具有實際應(yīng)用背景的多方保密計算問題以及他們的解決方案成為人們熱衷于研究的問題之一。 由于大量應(yīng)用領(lǐng)域

2、提供了特有的幾何問題，對于這些問題必須建立有效的算法，它們是計算幾何的基礎(chǔ)。這些問題包括歐幾里得巡回售貨員問題、最小生成樹問題、線性規(guī)劃問題等等?；谕拱膯栴}已研究得很多，并且已經(jīng)有很多成熟的解決方案，但是，在保護私有信息前提下的一些凸包問題還在研究探索中。保密的計算幾何問題是多方保密計算中的一個新的研究領(lǐng)域，是一類特殊的安全多方計算問題，雖然目前該問題已經(jīng)有一些理論上的通用解決辦法，但是在實際的計算效率上是不可行的，需要特殊的辦法。

3、目前國際上對這類問題的研究尚在起步階段，研究高效實用的安全多方計算協(xié)議成為人們致力于研究的熱門課題之一。 本文所討論的問題是基于私有信息保護的計算幾何基本問題，重點在于問題的發(fā)現(xiàn)和解決方法，而不僅僅是解決了什么問題。將多方保密計算應(yīng)用于計算幾何中解決的兩個問題：一個是保護私有信息的凸多邊形相似判定問題，這是一個特殊的安全多方計算問題。秘密判定兩組數(shù)據(jù)是否相等、是否對應(yīng)成比例是安全多方計算的基本問題，通過利用相應(yīng)的比較相等協(xié)議和點

4、積協(xié)議，以及兩組數(shù)據(jù)對應(yīng)成比例的判定協(xié)議，解決了在保護私有信息的前提下如何判定兩個凸多邊形是否相似的問題。 另一個是在保護私有信息的前提下由兩個保密點確定一條直線的問題。凸包算法是計算幾何中的基本算法，但兩保密點集如何確定一個大的凸包是一個特殊的計算幾何問題，也是一個特殊的安全多方計算問題。通過利用秘密判定兩線段相交協(xié)議、比較相等協(xié)議以及OT1m茫然傳送的思想，提出了一個基于私有信息保護的兩保密點確定一條直線的協(xié)議?；谠搮f(xié)議，