高效保密的參數(shù)區(qū)間估計*

陳明艷, 成 雯, 竇家維

1. 陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 西安710062

2. 陜西師范大學(xué) 計算機科學(xué)學(xué)院, 西安710062

1 引言

隨著信息時代的來臨, 信息的隱私保護越來越成為人們所關(guān)注的問題. 同時人們希望合作對雙方甚至多方的信息進行分析計算, 但是實際中擁有數(shù)據(jù)的各方參與者在計算中并不想泄露自己的數(shù)據(jù), 那么如何針對各方的隱私數(shù)據(jù)合作進行保密判計算成為一個重要的問題. 由于這些隱私保護需要的推動, 安全多方計算(Secure multiparty computation, SMC) 已發(fā)展成一個重要的研究方向, 并且成為解決隱私保護問題的重要方法和有力工具[1-5]. 安全多方計算問題是解決兩個或多個互不信任的參與者之間為保護隱私而進行的協(xié)同計算, 計算結(jié)束后, 參與計算的各方除了得到他們設(shè)定的計算結(jié)果外, 不能獲取其他參與方所擁有的隱私數(shù)據(jù)的任何信息.

姚期智教授在文獻[6] 中首次提出兩方安全計算問題, 隨后Ben-Or 和Goldwasser[7]提出了多方安全計算問題, Goldwasser[8]曾預(yù)言安全多方計算將成為計算科學(xué)中必不可少的組成部分. 經(jīng)過眾多學(xué)者多年來的潛心研究, 目前安全多方保密計算已經(jīng)形成了較為完整的理論體系, 針對各種實際應(yīng)用問題研究設(shè)計簡單高效的保密計算協(xié)議大大推動了安全多方計算研究的發(fā)展. 安全多方計算在隱私數(shù)據(jù)的計算、電子商務(wù)、保密拍賣、保密存儲、計算外包、保密遠(yuǎn)程訪問、入侵檢測等方向都有著廣泛且重要的應(yīng)用, 具體可歸結(jié)為下面幾大類: (1) 保密的科學(xué)計算[9-11]; (2) 保密的統(tǒng)計分析[12,13]; (3) 保密的幾何計算[14-16];(4) 保密的數(shù)據(jù)挖掘[17]; (5) 保密的數(shù)據(jù)庫查詢[18,19]; (6) 其他安全多方計算問題.

隨著時代與技術(shù)的發(fā)展, 多數(shù)人都想依靠更精準(zhǔn)的數(shù)據(jù)來使自己的利益最大化, 同時不想泄露自己的隱私. 由于在數(shù)據(jù)眾多的情況下無法做到統(tǒng)計所有的數(shù)據(jù), 因而無法得到完全準(zhǔn)確的數(shù)據(jù)結(jié)果. 根據(jù)統(tǒng)計學(xué)的知識, 在數(shù)據(jù)總體巨大時, 我們可以選取一定數(shù)量的樣本數(shù)據(jù), 通過分析樣本數(shù)據(jù), 由樣本統(tǒng)計量來構(gòu)造總體參數(shù)的估計區(qū)間, 這個區(qū)間稱為參數(shù)的置信區(qū)間. 置信區(qū)間的保密判定在保密的網(wǎng)絡(luò)波動判斷, 保密的患病數(shù)據(jù)預(yù)測, 實際的市場交易中有重要的應(yīng)用. 例如: (1) 一個公司想要保密的檢測另一個公司的產(chǎn)品參數(shù)方差是否滿足自己的要求. 為不泄露對產(chǎn)品參數(shù)方差的要求程度, 保密選取置信度1-α, 判定此參數(shù)方差的置信區(qū)間是否含于自己的區(qū)間中. (2) 兩個公司生產(chǎn)同一類產(chǎn)品, 其中一個公司想要保密檢測自己公司的產(chǎn)品與另一家公司產(chǎn)品參數(shù)均值的差異, 并不泄露產(chǎn)品數(shù)據(jù). 則需要保密計算產(chǎn)品參數(shù)均值差的置信區(qū)間是否含于自己的區(qū)間中, 來觀察兩家產(chǎn)品數(shù)據(jù)的差異. 為解決類似的參數(shù)估計保密判定問題, 本文提出并研究了單個正態(tài)總體, 兩個正態(tài)總體的區(qū)間估計保密判定問題.

在統(tǒng)計學(xué)中, 參數(shù)估計分為點估計和區(qū)間估計, 點估計常用的方法包括矩估計、極大似然估計等[20].文獻[21] 分別以水平型分布數(shù)據(jù)和垂直型分布數(shù)據(jù)為條件設(shè)計了保密的極大似然估計協(xié)議, 研究解決了有關(guān)點估計的保密計算問題. 據(jù)我們所知, 區(qū)間估計目前還沒有很好的研究成果. 本文主要研究參數(shù)區(qū)間估計的保密判定問題, 計算單個正態(tài)總體下方差, 兩個正態(tài)總體下均值差的置信區(qū)間, 結(jié)合Paillier 加密算法、Lifted ElGamal 門限加密算法, 得到置信區(qū)間端點的密文, 并保密判定此置信區(qū)間是否含于一個一方參與者已知的區(qū)間. 在已有的研究成果中, 點與區(qū)間以及區(qū)間與區(qū)間位置關(guān)系的判定都是在已知明文下進行保密計算的. 文獻[22] 首次提出了區(qū)間的保密計算, 將區(qū)間保密計算問題轉(zhuǎn)化成有限集合包含問題. 文獻[23] 利用二叉樹中的一個(固定大小的) 節(jié)點集來表示整數(shù)點和區(qū)間, 根據(jù)兩個節(jié)點集的交集顯示整數(shù)點是否在區(qū)間內(nèi), 來判定整數(shù)點與區(qū)間的關(guān)系, 提高了計算效率. 文獻[24] 根據(jù)函數(shù)的單調(diào)性結(jié)合Paillier加密算法, 將離散點與離散整數(shù)區(qū)間位置關(guān)系的保密判定擴展到實數(shù)點與連續(xù)的實數(shù)區(qū)間位置關(guān)系的保密判定. 文獻[25] 利用密碼學(xué)以及同態(tài)加密的相關(guān)知識, 設(shè)計了從兩個明文區(qū)間的重疊中選擇一個隨機的子區(qū)間的隱私保護協(xié)議并將其應(yīng)用于物物交換. 由此可見, 保密地判定明文點與明文區(qū)間, 明文區(qū)間之間關(guān)系的研究已經(jīng)有比較豐富的成果, 但是目前對密文區(qū)間與明文區(qū)間位置關(guān)系的保密判定研究成果還較少,同時在統(tǒng)計分析中針對參數(shù)區(qū)間估計的保密計算問題還沒有好的研究成果. 因此, 針對這一研究現(xiàn)狀以及實際應(yīng)用的需要, 本文研究設(shè)計了參數(shù)區(qū)間估計問題的保密判定協(xié)議.

本文主要貢獻如下:

(1) 提出并研究了保密統(tǒng)計分析中的新問題, 即參數(shù)區(qū)間估計的保密判定問題. 拓展了保密統(tǒng)計分析的研究內(nèi)容.

(2) 提出判定密文區(qū)間與明文區(qū)間位置關(guān)系的解決方案. 通過添加隨機數(shù)的方法, 將保密判定密文區(qū)間與明文區(qū)間的位置關(guān)系轉(zhuǎn)化成保密判定數(shù)據(jù)相等問題, 首次解決了密文區(qū)間與明文區(qū)間位置關(guān)系的保密判定問題.

(3) 結(jié)合Paillier 加密算法, Lifted ElGamal 門限加密算法, 通過密文區(qū)間與明文區(qū)間的保密判定, 設(shè)計了單個正態(tài)總體參數(shù)區(qū)間估計, 兩個正態(tài)總體參數(shù)區(qū)間估計的保密判定協(xié)議. 并對協(xié)議的安全性和正確性進行了嚴(yán)格證明.

本文第2 節(jié)介紹了協(xié)議設(shè)計中需要用到的預(yù)備知識; 第3、4 節(jié)設(shè)計了具體的協(xié)議解決單個正態(tài)總體參數(shù)區(qū)間估計, 兩個正態(tài)總體參數(shù)區(qū)間估計問題, 并對其進行了正確性以及安全性分析; 第5 節(jié)對本文協(xié)議進行了效率分析; 第6 節(jié)對全文進行了總結(jié).

2 預(yù)備知識

2.1 半誠實模型及其安全性定義

一個半誠實參與者[26]應(yīng)嚴(yán)格按照協(xié)議的要求執(zhí)行協(xié)議, 但有可能會保存在協(xié)議執(zhí)行過程中所得到的信息, 試圖在執(zhí)行協(xié)議后推導(dǎo)計算出其他參與者隱私數(shù)據(jù)的額外信息. 若在協(xié)議中所有參與者全部為半誠實參與者, 稱這樣的模型為半誠實模型.

設(shè)f(x1,x2) = (f1(x1,x2),f2(x1,x2)) 是一個概率多項式時間函數(shù), π 是計算函數(shù)f 的雙方協(xié)議. 對于i=1,2, 參與者Pi的輸入為xi, 在執(zhí)行協(xié)議中Pi得到的信息序列記作

如果需要證明一個兩方計算協(xié)議在半誠實模型下是安全的, 就必須構(gòu)造出滿足式(1) 和式(2) 的模擬器S1與S2. 本文所有協(xié)議是在半誠實模型下設(shè)計的安全計算協(xié)議.

2.2 Paillier 加密方案

加法同態(tài)性Paillier 加密方案具有加法同態(tài)性, 即有下面性質(zhì)成立: 假設(shè)

則有

進一步還可得到Paillier 加密方案的下述乘法性質(zhì)

在Paillier 加密方案中, 若選取g = 1+kN(k 為正整數(shù)), 則E(m) = (1+kN)mrNmod N2=(1+mkN)rNmod N2. 此時, 加密一個明文m 時, 需要1 次模指數(shù)運算; 在解密密文c 時, 由于解密運算中的gλ可以重復(fù)使用, 因此解密一個密文也僅需要1 次模指數(shù)運算. 下文中都將g 選定為1+kN 的形式.

2.3 Lifted ElGamal 門限加密方案

在門限密碼體制中, n 個參與者聯(lián)合生成公鑰, 參與者共同分享私鑰. 所有參與者都可以用公鑰加密消息, 但解密時必須由t 個(1 ＜t ＜n) 參與者合作才能完成, 少于t 個人聯(lián)合都無法解密任何消息, 這樣的門限密碼稱為(t,n) 門限. 為保證數(shù)據(jù)的安全性, 抵抗n-1 個參與者的合謀攻擊, 在一般的門限密碼體制中, 參與者會選擇構(gòu)造(n,n) 門限.

Lifted ElGamal 門限加密算法的產(chǎn)生是基于ElGamal[28]加密算法, 對ElGamal 算法中明文m 進行處理, 用gm替換m. 下面詳細(xì)說明Lifted ElGamal 門限加密方案的構(gòu)造過程.

密鑰生成給定安全參數(shù)λ, 密鑰生成算法生成一個λ 比特的大素數(shù)p 以及的一個生成元g. 每個參與者Pi隨機選取ki∈作為私鑰, 并計算hi=mod p. 公鑰為:

加密為加密明文m, 選擇隨機數(shù)r, 按照下式計算密文c:

解密對于密文c=(c1,c2), 每個參與者Pi按照下式解密:

2.4 參數(shù)區(qū)間估計

在統(tǒng)計學(xué)中, 參數(shù)估計分為點估計(Point estimation) 和區(qū)間估計(Interval estimate). 區(qū)間估計是在點估計的基礎(chǔ)上, 給出總體參數(shù)一個估計的區(qū)間范圍, 該區(qū)間通常通過樣本統(tǒng)計量與估計誤差結(jié)合運算得到. 與點估計不同的是, 在進行區(qū)間估計時, 根據(jù)所測量的樣本統(tǒng)計量不同的抽樣分布可以要求一個樣本統(tǒng)計量與總體參數(shù)的接近程度的概率. 一般地, 利用樣本的置信區(qū)間(Confidence interval) 對這個樣本的總體參數(shù)進行區(qū)間估計. 置信區(qū)間展現(xiàn)的是被估計參數(shù)的真實值在一定概率情況下落在所測量結(jié)果周圍的程度. 它給出的是被測參數(shù)通過計算得到的測量值的可信程度, 即為前面所要求的“概率”, 這個概率被稱作置信水平. 常見的置信區(qū)間分為單個正態(tài)總體的置信區(qū)間, 兩個正態(tài)總體的置信區(qū)間, 本文分別對這兩個問題進行保密的參數(shù)區(qū)間估計.

對于單個正態(tài)總體的參數(shù)區(qū)間估計, 本文以總體方差為例, 在總體均值未知的情況下, 判斷總體方差的置信區(qū)間是否含于另一個已知的區(qū)間中. 設(shè)(x1,x2,··· ,xn) 為取自總體N(μ,σ2) 的樣本, 樣本方差為s2. 均值μ 未知情況下, 方差σ2置信區(qū)間為:

3 單個正態(tài)總體的參數(shù)區(qū)間估計

3.1 問題描述及計算原理

3.2 單個正態(tài)總體的參數(shù)區(qū)間估計保密判定協(xié)議

協(xié)議1 單個正態(tài)總體的參數(shù)區(qū)間估計保密判定協(xié)議

(4) Bob 選擇隨機數(shù)r*, 計算X =(E(t)E(l+4)-1)r*, 并將X 發(fā)送給Alice.

3.3 協(xié)議的正確性

3.4 協(xié)議的安全性

定理1 協(xié)議1 在半誠實模型下是安全的.

證明: 通過構(gòu)造滿足式(1) 和式(2) 成立的模擬器S1,S2證明定理1, 首先構(gòu)造S1.

令

因此, 協(xié)議1 在半誠實模型下是安全的.

4 兩個正態(tài)總體的參數(shù)區(qū)間估計

4.1 問題描述及計算原理

4.2 兩個正態(tài)總體的參數(shù)區(qū)間估計保密判定協(xié)議

4.3 協(xié)議2 的正確性與安全性分析

正確性分析

安全性分析

定理2 協(xié)議2 在半誠實模型下是安全的.

5 效率分析

在統(tǒng)計學(xué)中, 參數(shù)估計分為點估計和區(qū)間估計, 點估計常用的方法包括矩估計、極大似然估計等. 文獻[21] 主要研究了點估計保密計算有關(guān)問題, 分別以水平型分布數(shù)據(jù)和垂直型分布數(shù)據(jù)為條件設(shè)計了保密計算極大似然估計協(xié)議. 本文研究了參數(shù)估計的另一個方向, 即參數(shù)區(qū)間估計, 據(jù)我們所知, 目前還未見到關(guān)于參數(shù)區(qū)間估計的研究結(jié)果. 本文主要研究設(shè)計包括單個正態(tài)總體、兩個正態(tài)總體參數(shù)區(qū)間估計的保密判定協(xié)議. 本文與文獻[21] 同屬參數(shù)估計研究方向, 但研究的問題完全不同, 因此無法將本文結(jié)果與文獻[21] 進行比較. 下面, 我們對本文所設(shè)計的兩個關(guān)于參數(shù)區(qū)間估計保密判定協(xié)議進行效率分析.

通信復(fù)雜度本文應(yīng)用協(xié)議所需要的通信次數(shù)來衡量通信復(fù)雜性.

在協(xié)議1 中, Alice 給Bob 共發(fā)送3 次信息, Bob 給Alice 發(fā)送2 次信息, 所以協(xié)議1 通信次數(shù)為5次.

在協(xié)議2 中, Alice 給Bob 共發(fā)送5 次信息, Bob 給Alice 發(fā)送3 次信息, 所以協(xié)議2 通信次數(shù)為8次.

協(xié)議效率實驗測試 為了進一步分析協(xié)議的效率和方案的實際可行性, 本部分通過模擬實驗來測試本文協(xié)議具體執(zhí)行中所用的時間. 本文所做的模擬實驗均在下面的實驗環(huán)境中進行.

實驗環(huán)境 Windows 10 64 位操作系統(tǒng), 處理器參數(shù)為Intel(R) Core(TM)i5-4590s CPU@3.00GHz,4GB 內(nèi)存. 用Java 語言在Eclipse 上運行實現(xiàn), 本文所有模擬實驗均在此環(huán)境下進行. 本文協(xié)議1 利用Paillier 加密系統(tǒng)進行模擬, 協(xié)議2 利用Lifted ElGamal 門限加密系統(tǒng)進行模擬, 且都忽略預(yù)處理時間.由于Alice 與Bob 所做工作有很大不同, 本文分別對兩方參與者分別進行實驗(見表1).

表1 協(xié)議實驗效率分析Table 1 analysis on experimental eきciency

6 結(jié)論

本文提出了新的多方保密計算問題, 即參數(shù)區(qū)間估計保密計算. 首先, 根據(jù)Paillier 加密算法設(shè)計了單個正態(tài)總體的參數(shù)區(qū)間估計保密計算協(xié)議. 在此協(xié)議中我們同時解決密文區(qū)間與明文區(qū)間的位置關(guān)系保密判定問題, 通過添加隨機數(shù)的方式, 將密文區(qū)間與明文區(qū)間的位置關(guān)系的保密判定轉(zhuǎn)化為保密判定數(shù)據(jù)相等問題. 進一步結(jié)合Lifted ElGamal 門限加密算法, 設(shè)計了兩個正態(tài)總體的參數(shù)區(qū)間估計問題, 并證明了協(xié)議的安全性. 在后續(xù)的研究工作中, 我們將進一步研究惡意模型下有關(guān)參數(shù)估計的安全計算問題.