一個抗隱蔽敵手的n選t不經(jīng)意傳輸框架.pdf

1、不經(jīng)意傳輸(oblivious transfer,OT)可能是密碼學(xué)中最重要的原語。從理論的角度看,它是一個基礎(chǔ)性的原語,因為如果可以安全地實現(xiàn)OT協(xié)議,那么就可以安全地實現(xiàn)其它一切密碼學(xué)協(xié)議。從應(yīng)用的角度看,它本身就是安全數(shù)據(jù)庫查找和電子商務(wù)領(lǐng)域中的重要工具。
　　通常密碼學(xué)假定敵手是惡意的。惡意敵手是個一有機(jī)會就作弊的狂徒,不會在乎利害得失。這樣的假設(shè)太過悲觀,設(shè)計出的協(xié)議往往開銷高昂。本文采納Aumann和Lindell的觀

2、點,假定敵手是隱蔽的。隱蔽敵手會顧慮抓捕后的懲罰而不敢肆意作弊?？闺[蔽敵手的安全并不能去除敵手所有成功的作弊。盡管如此,但是它可以保證,一旦敵手作弊了,誠實用戶可以以某個滿意的概率檢測到這一點。
　　n選t不經(jīng)意傳輸(t-out-of-n oblivious transfer,OTnt)可描述如下。發(fā)送者擁有n個私有值m1、m2、……、mn。接收者擁有t個私有的索引i1、i2、……、it。接收者希望得到值mi1、mi2、……、mi

3、t且不向敵手泄露它得到了哪些值;發(fā)送者希望接收者最多只能獲取t個值,而不是超過t個值。
　　我們提出了一個新的光滑投影哈希(smooth projective hashing,SPH)變種來構(gòu)造OTnt框架。新的SPH變種與現(xiàn)有SPH及其變種的最大區(qū)別是,它既給光滑實例提供見證,又給投影實例提供見證。它解決了兩個問題。其一,它使得SPH得以處理通用的OTnt問題而不只是OT21問題。其二,它能夠為使用SPH的OTnt框架帶來遵循理

4、想世界/現(xiàn)實世界仿真范式的安全性證明。
　　在我們之前,學(xué)術(shù)界有個傳說,在有錯學(xué)習(xí)難假設(shè)下實現(xiàn)SPH存在著技術(shù)上的困難。我們的解決思路是,將負(fù)責(zé)計算哈希值的算法視為一個公鑰加密算法,而負(fù)責(zé)計算投影值的算法被視為一個解密算法。自然而然,我們可以將(公鑰,私鑰)對視為(實例,見證)對。在有錯學(xué)習(xí)難假設(shè)下實現(xiàn)SPH新變種,意味著我們?yōu)镾PH開創(chuàng)了一個新的實例。此外,像現(xiàn)有的SPH可以在判定Diffie-Hellman假設(shè),判定N階剩余假

5、設(shè),判定平方剩余假設(shè)實現(xiàn)那樣,我們也在這些難題假設(shè)下一一實現(xiàn)了新的SPH變種。
　　使用新的SPH變種,我們構(gòu)造了一個抗隱蔽敵手的、安全性證明遵循理想世界/現(xiàn)實世界仿真范式的OTnt框架。我們的框架很實用,它有如下特點。
　　它可以在廣泛的數(shù)學(xué)難題假設(shè)下實例化。我們證明框架可以在判定Diffie-Hellman假設(shè),判定N階剩余假設(shè),判定平方剩余假設(shè)和有錯學(xué)習(xí)假設(shè)下分別實現(xiàn)。
　　它可以在現(xiàn)實生活中廣泛使用。這是因為它

6、工作在平凡模型中,不需要可信的初始裝置。
　　它非常高效。它只需要4輪通信。其主要的計算開銷是發(fā)送者的n個公鑰加密運算和接收者的(K g)t個公鑰解密運算。與現(xiàn)在已知抵抗隱蔽敵手的,或者抵抗惡意敵手的協(xié)議相比,我們的框架,通常更高效。其中,K,g是滿足K>g的正整數(shù)。
　　當(dāng)敵手成功賄賂發(fā)送者時,敵手的作弊能以100％的概率被誠實的接收者檢測到。當(dāng)敵手成功賄賂接收者時,敵手的作弊能以1-1/(K K-g)的概率被誠實的發(fā)送者

7、檢測到。
　　框架只使用了一個密碼學(xué)原語,即SPH新變種,這意味著我們將OTnt規(guī)約到了SPH。在我們之前,唯一已知的規(guī)約就是Halevi和Tauman Kalai所給出的OT21到SPH的規(guī)約。然而,該規(guī)約的安全性證明無法遵循理想世界/現(xiàn)實世界仿真范式。
　　安全性證明是件極為復(fù)雜的事情。為了簡化證明,我們給出了幾個基于多次取樣的計算不可區(qū)分的引理。這些引理大大簡化了我們的安全性證明。我們相信它們在其它場合中的安全性證明中