集合間基本操作的多方保密計(jì)算

亢 佳，楊曉藝，劉 新

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

集合間基本操作的多方保密計(jì)算

亢 佳，楊曉藝，劉 新

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

多方保密計(jì)算是近年來(lái)國(guó)際密碼學(xué)界研究的熱點(diǎn)問(wèn)題。集合是科學(xué)研究中一個(gè)非常重要的概念，其在數(shù)學(xué)領(lǐng)域具有無(wú)可比擬的特殊重要性。現(xiàn)實(shí)生活中的許多問(wèn)題可以轉(zhuǎn)化成集合之間的基本操作問(wèn)題來(lái)解決。對(duì)集合間的保密操作，如保密地計(jì)算集合交集、并集是多方保密計(jì)算中的一個(gè)重要方面，在保密的數(shù)據(jù)挖掘，保密的數(shù)據(jù)庫(kù)查詢(xún)等方面有重要的意義，在現(xiàn)實(shí)生活中也有廣泛的應(yīng)用前景和實(shí)用價(jià)值。為了解決集合之間基本操作的保密問(wèn)題，提出了基于Paillier加法同態(tài)加密算法的安全兩數(shù)差平方計(jì)算協(xié)議和求解集合交集的保密協(xié)議，并設(shè)計(jì)了基于百萬(wàn)富翁協(xié)議的求解集合并集的保密協(xié)議。理論分析表明，基于Paillier加法同態(tài)加密算法的安全兩數(shù)差平方計(jì)算協(xié)議以及求解集合交集與并集的保密協(xié)議具有較好的正確性和安全性。

多方保密計(jì)算；集合交集；集合并集；加法同態(tài)

0 引 言

多方保密計(jì)算是近年來(lái)國(guó)際密碼學(xué)界的一個(gè)研究熱點(diǎn)[1-5]，在計(jì)算科學(xué)中占有重要地位。多方保密計(jì)算問(wèn)題由Yao[6]最先提出，Goldreich等[7]對(duì)其進(jìn)行了深入研究，推動(dòng)多方保密計(jì)算理論的發(fā)展。

許多學(xué)者致力于研究具有實(shí)際應(yīng)用背景的多方保密計(jì)算問(wèn)題以及它們的解決方案，所研究的問(wèn)題包括比較兩個(gè)數(shù)的大小[8-11]、保密的數(shù)據(jù)挖掘[12]、比較兩條信息是否相同[13]、保密的數(shù)據(jù)庫(kù)查詢(xún)、保密拍賣(mài)[14]、保密的統(tǒng)計(jì)分析、保密的計(jì)算幾何[15-18]等。……