一些基于私有信息保護(hù)的計(jì)算幾何問(wèn)題研究.pdf

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

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

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

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