張凱鑫， 楊 晨， 李順東

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

1 引言

在大數(shù)據(jù)的時(shí)代， 越來(lái)越多的服務(wù)和產(chǎn)品是圍繞用戶(hù)數(shù)據(jù)(隱私) 建立的. 這樣雖然帶來(lái)了個(gè)性化的服務(wù)， 提高了服務(wù)質(zhì)量和精度， 但是在數(shù)據(jù)收集、使用以及公布的過(guò)程中， 用戶(hù)隱私可能暴露， 隱私保護(hù)尤為重要. 安全多方計(jì)算[1](secure multiparty computation， SMC) 是密碼學(xué)的一個(gè)重要分支， 旨在解決一組互不信任的參與方之間保護(hù)隱私的協(xié)同計(jì)算問(wèn)題， 為數(shù)據(jù)需求方提供不泄露原始數(shù)據(jù)前提下的多方協(xié)同計(jì)算能力. 在整個(gè)計(jì)算協(xié)議執(zhí)行過(guò)程中， 用戶(hù)對(duì)個(gè)人數(shù)據(jù)始終擁有控制權(quán)， 只有計(jì)算邏輯是公開(kāi)的， 計(jì)算參與方只需參與計(jì)算協(xié)議， 無(wú)需依賴(lài)第三方就能完成數(shù)據(jù)計(jì)算， 并且參與各方拿到計(jì)算結(jié)果后也無(wú)法推斷出原始數(shù)據(jù).

在密碼學(xué)與信息安全、計(jì)算科學(xué)領(lǐng)域中， 安全多方計(jì)算有著舉足輕重的作用， 是信息社會(huì)隱私保護(hù)的核心技術(shù)， 主要包括保密的科學(xué)計(jì)算問(wèn)題[2-6]、保密的計(jì)算幾何問(wèn)題[7，8]、保密的統(tǒng)計(jì)分析問(wèn)題、保密的數(shù)據(jù)挖掘問(wèn)題[9]， 以及其他安全多方計(jì)算問(wèn)題.

雖然人們研究解決了很多安全多方計(jì)算問(wèn)題， 但這些方案的效率都亟待提高.

目前， 有關(guān)字符串計(jì)算問(wèn)題的研究有明文下對(duì)字符串匹配算法的改進(jìn)[10-13]、字符串的近似匹配[14-16]、基于Bloom Filter 的字符串匹配[17-20]、字符串相等[21]等問(wèn)題. 含通配符的字符串匹配一般用于找出一系列具有相同組成成分的字符串， 即可以找到具有相似結(jié)構(gòu)的字符串， 在生物序列分析、關(guān)鍵詞搜索、數(shù)據(jù)庫(kù)查詢(xún)等領(lǐng)域具有重要作用. 例如， 公司想要統(tǒng)計(jì)所有員工中姓張的人數(shù)， 可以輸入SQL 語(yǔ)句select COUNT(id) from people where name =‘張*’ (通配符‘*’ 可以表示任意長(zhǎng)度的字符串)，那么張三、張明明、張葉奈珞等人都會(huì)被統(tǒng)計(jì). 我們主要研究?jī)蓚€(gè)問(wèn)題: 字符串模式匹配和含通配符的字符串匹配問(wèn)題.

在文本處理中， 關(guān)鍵字匹配是一個(gè)十分常用且重要的功能. 關(guān)鍵字稱(chēng)為模式串P， 在文本T中尋找模式串P出現(xiàn)的所有位置， 解決這種問(wèn)題的算法叫做字符串模式匹配算法. 現(xiàn)有關(guān)于字符串模式匹配的安全多方計(jì)算方案有: 文獻(xiàn)[21] 將每個(gè)字符編碼成其ASCII 碼的對(duì)應(yīng)二進(jìn)制數(shù)， 用ElGamal 加密算法進(jìn)行加密計(jì)算， 其平均計(jì)算復(fù)雜性較高; 文獻(xiàn)[22] 采用somewhat homomorphic encryption (SHE) 方案和新的數(shù)據(jù)包裝技術(shù)， 將二進(jìn)制數(shù)據(jù)封裝成環(huán)空間上的單一密文， 通過(guò)計(jì)算密文的多個(gè)海明距離來(lái)判斷字符串是否匹配. 該協(xié)議雖然提高了效率， 但其只能進(jìn)行單一的模式匹配(即模式串只能在文本中出現(xiàn)一次). 文獻(xiàn)[23] 在惡意模型下設(shè)計(jì)了字符串模式匹配協(xié)議， 本文在半誠(chéng)實(shí)模型下設(shè)計(jì)協(xié)議， 模型不一樣. 文獻(xiàn)[24]中的協(xié)議2 利用Goldwasser-Micali 同態(tài)加密算法下設(shè)計(jì)了字符串模式匹配協(xié)議， 將每個(gè)字符用其ASCII對(duì)應(yīng)的二進(jìn)制數(shù)異或來(lái)進(jìn)行計(jì)算， 其計(jì)算復(fù)雜性相對(duì)較高. 文獻(xiàn)[24] 中的協(xié)議4 采用了對(duì)稱(chēng)密碼學(xué)算法來(lái)進(jìn)行字符串模式匹配問(wèn)題的計(jì)算， 沒(méi)有進(jìn)行任何加密解密操作.

含通配符的字符串匹配問(wèn)題是對(duì)字符串模式匹配問(wèn)題的擴(kuò)展. 字符串模式匹配中的模式串P是完整的， 均由字符組成. 而含通配符的字符串匹配， 相當(dāng)于把模式串P中某些位置的元素用通配符代替， 該通配符可以代表不同數(shù)量的不同字母， 相當(dāng)于是對(duì)完整模式串的泛化. 含通配符的字符串匹配問(wèn)題廣泛應(yīng)用于文件搜索、數(shù)據(jù)庫(kù)、正則表達(dá)式等領(lǐng)域. 早在20 世紀(jì)70 年代， Fischer 等首先在字符串匹配問(wèn)題中引入通配符[25]這一概念. 在安全計(jì)算中， 大多數(shù)早期的工作都處理沒(méi)有通配符[22，26]或只有一個(gè)通配符[27，28]的模式. 到目前為止， 我們觀察到具有單個(gè)通配符的字符串匹配問(wèn)題是文獻(xiàn)[28] 提出的， 但其是在惡意模型下提出的且只適用于單個(gè)通配符的問(wèn)題. 文獻(xiàn)[17] 基于加密的Bloom Filter 設(shè)計(jì)了字符串匹配協(xié)議， 文獻(xiàn)[18-20] 是在云計(jì)算下基于Bloom Filter 構(gòu)建的字符串匹配協(xié)議， 而B(niǎo)loom Filter 的一個(gè)顯著缺點(diǎn)是誤判的概率是不可忽略的. 這些基于Bloom Filter 的通配符加密方案以不可忽略的概率向用戶(hù)返回假結(jié)果. 文獻(xiàn)[29] 采用SHE 加密算法和新的數(shù)據(jù)包裝計(jì)算， 將字符串包裝成多項(xiàng)式來(lái)進(jìn)行加密計(jì)算， 但SHE 的安全性依賴(lài)于Ring LWE 問(wèn)題， 且只能實(shí)現(xiàn)有限次的乘法， 其適用性沒(méi)有Paillier 強(qiáng).

上述關(guān)于含通配符的字符串匹配協(xié)議存在的問(wèn)題總結(jié)如下:

(1) 文獻(xiàn)[17-20] : 基于Bloom Filter 的加密方案存在一定概率的誤判， 不能實(shí)現(xiàn)精確的字符串匹配;

(2) 文獻(xiàn)[28]: 在惡意模型下只能實(shí)現(xiàn)含單個(gè)通配符的字符串匹配， 通配符的數(shù)量受限使用不靈活;

(3) 文獻(xiàn)[29]: 基于SHE 的加密算法設(shè)計(jì)協(xié)議， 但SHE 的安全性依賴(lài)于Ring LWE 問(wèn)題， 且只能實(shí)現(xiàn)有限次的乘法， 適用性受限.

為了解決以上出現(xiàn)的問(wèn)題， 本文在半誠(chéng)實(shí)模型下利用Paillier 公鑰加密算法和一種新的編碼方法保密判斷含通配符的字符串匹配問(wèn)題， 能夠?qū)崿F(xiàn)含通配符字符串的精確匹配， 且方案使用不受限制. 協(xié)議中通配符的使用靈活， 通配符的數(shù)量和位置是任意的.

本文的主要貢獻(xiàn)如下:

(1) 設(shè)計(jì)了一種新的編碼方法來(lái)處理字符串匹配問(wèn)題， 將每個(gè)參與者的保密數(shù)據(jù)隱藏在向量中， 這種編碼方法可以為其他安全多方計(jì)算問(wèn)題提供一種新的途徑.

(2) 利用本文設(shè)計(jì)的編碼方法和Paillier 同態(tài)加密算法設(shè)計(jì)了字符串模式匹配的保密判定協(xié)議和含通配符的字符串保密匹配協(xié)議， 這些協(xié)議對(duì)半誠(chéng)實(shí)參與者是安全的.

(3) 現(xiàn)有的含通配符的加密方案中， 通配符僅代表單個(gè)字符. 本文通配符可以表示任意數(shù)量的字符，并且可以位于字符串的任意位置.

(4) 大部分現(xiàn)有的含通配符的加密方案是基于Bloom Filter 構(gòu)造的， 會(huì)出現(xiàn)一定概率的誤判. 本文設(shè)計(jì)的方案能夠保證字符串的精確匹配.

2 預(yù)備知識(shí)

2.1 安全性定義

雙方計(jì)算. 雙方計(jì)算是一個(gè)將隨機(jī)輸入對(duì)映射為輸出對(duì)的隨機(jī)計(jì)算過(guò)程， 可表示成如下的函數(shù)形式:

其中f=(f1，f2). 函數(shù)f為輸入對(duì)(x，y) 和輸出對(duì)(f1(x，y)，f2(x，y)) 之間的映射， (f1(x，y)，f2(x，y) 為隨機(jī)變量， 其變化范圍為一對(duì)字符串)， 于是函數(shù)f又可記作:

半誠(chéng)實(shí)參與者[30]. 在半誠(chéng)實(shí)模型中要求所有的參與者都是半誠(chéng)實(shí)的. 所謂半誠(chéng)實(shí)參與者是指在協(xié)議執(zhí)行過(guò)程中按照協(xié)議要求履行協(xié)議， 但他們可能會(huì)將協(xié)議執(zhí)行過(guò)程中獲得的信息記錄下來(lái)， 在執(zhí)行完協(xié)議后試圖根據(jù)記錄的信息推算出其他參與者的輸入信息. 本文假設(shè)協(xié)議的所有參與者都是半誠(chéng)實(shí)的.

模擬范例[30]. 模擬范例在安全性證明中被廣泛使用， 相對(duì)于其他安全性證明方法， 它可以簡(jiǎn)便地模擬參與者執(zhí)行協(xié)議的過(guò)程.

模擬范例的原理: 如果半誠(chéng)實(shí)參與者用自己的輸入和輸出進(jìn)行模擬所得的消息序列與實(shí)際過(guò)程得到的消息序列不可區(qū)分， 則協(xié)議是保密的. 如果一個(gè)多方計(jì)算協(xié)議可以進(jìn)行這樣的模擬， 參與者就不能從協(xié)議的執(zhí)行過(guò)程中得到其他人的任何信息.

一些記號(hào)[30]. 假設(shè)參與者是Alice 和Bob.

2.2 Paillier 同態(tài)加密系統(tǒng)

3 字符串模式匹配的保密判定協(xié)議

問(wèn)題描述. 字符串模式匹配是判斷一個(gè)字符串是否為另一個(gè)字符串的子串問(wèn)題. Alice 擁有字符串SA， 長(zhǎng)度為n， Bob 擁有字符串SB， 長(zhǎng)度為m(m ≤n)， 雙方想知道SB是否為SA的子字符串， 且不泄露SA，SB的任何信息.

方案思想. 在字符串SA中挑選第一個(gè)字符及與其相鄰的m-1 個(gè)字符， 組成長(zhǎng)度為m的子字符串s1，s1與SB中相同索引下的兩個(gè)字符用加法同態(tài)算法來(lái)判斷是否相等. 若兩個(gè)字符相等， 則計(jì)算結(jié)果為0， 因此判斷字符串s1與SB是否相等一共需要進(jìn)行m次比較. 如果m次比較結(jié)果都是0， 說(shuō)明子字符串s1與SB是相等的， 我們稱(chēng)上述操作為一次循環(huán)計(jì)算. 第i次循環(huán)計(jì)算是在字符串SA中挑選第i個(gè)字符及與其后面的m-1 個(gè)字符， 組成長(zhǎng)度為m的字符串si， 字符串si與字符串SB進(jìn)行計(jì)算. 若判斷字符串SB是否為字符串SA的子字符串， 共進(jìn)行n-m+1 次循環(huán)計(jì)算. 如果n-m+1 次循環(huán)計(jì)算結(jié)果中至少有一次結(jié)果全為0， 說(shuō)明字符串SB是字符串SA的子串. 長(zhǎng)度為n的字符串SA有n-m+1個(gè)長(zhǎng)度為m的子字符串， 因此判斷字符串SB是否為字符串SA的子串歸約為SA的n-m+1 個(gè)子串中至少有一個(gè)與SB相等問(wèn)題. 本文首先將保密的字符串編碼成一個(gè)向量， 向量元素由字符在全集中對(duì)應(yīng)的兩位十進(jìn)制數(shù)表示， 在加法同態(tài)性的基礎(chǔ)上設(shè)計(jì)一個(gè)高效的協(xié)議.

例1 Alice 擁有字符串SA= acdec， 字符c在全集中位于第3 位， 兩位十進(jìn)制表示為13， 其他字符也進(jìn)行同樣的編碼， 生成向量A=(11，13，14，15，13)， 并發(fā)送給Bob.

(1) Bob 擁有字符串SB=ac， 按照上述的編碼方法得到向量B=(11，13).

3.1 具體協(xié)議

協(xié)議1 保密判斷字符串SB 是否為字符串SA 的子串輸入: Alice、Bob 各自的私密字符串SA = a1a2···an， SB = b1b2···bm.輸出: P(SA，SB).(1) (G，D，E) 是Paillier 同態(tài)加密方案， τ 是設(shè)定的安全參數(shù)， Alice 運(yùn)行G(τ) 生成同態(tài)加密的公私鑰對(duì)(pk，sk)，Alice 向Bob 公布生成的公鑰pk.(2) Alice 根據(jù)編碼方法構(gòu)造SA 對(duì)應(yīng)的向量A = (a′1，a′2，··· ，a′n)， 并用公鑰pk 加密得到向量E(A) = (E(a′1)，E(a′2)，··· ，E(a′n))， Alice 將E(A) 發(fā)送給Bob.(3) Bob 根據(jù)SB 和集合U 按照上述編碼方法得到向量B = (b′1，b′2，··· ，b′m)， 用Alice 的公鑰加密得到:E(B) =(E(b′1)， E(b′2)，···， E(b′m)).(4) Bob 隨機(jī)選擇s ∈{0，1} 和隨機(jī)數(shù)rij， 對(duì)每個(gè)i ∈[1，n-m+1]) 計(jì)算如下:∏m E(wi) =■■ ■i+j-1)*E(N -b′j))rij， s = 0，∏m j=1(E(N -a′j=1(E(a′i+j-1)*E(b′j))rij， s = 1.(5) Bob 經(jīng)過(guò)n-m+1 次循環(huán)計(jì)算后得到E(W) = {E(w1)，E(w2)，··· ，E(wn-m+1)}， 將E(W) 中的分量進(jìn)行隨機(jī)置換， 置換后仍記為E(W) (因?yàn)閃 為集合， 置換后仍為集合)， 并將E(W) 發(fā)送給Alice.(6) Alice 用自己的私鑰對(duì)E(W) 解密得到集合W， 如果集合W 中至少有一個(gè)為0 的元素， 那么輸出P(SA， SB) = 0，此時(shí)字符串SB 是SA 的子字符串; 否則， 輸出P(SA，SB) = 1， 此時(shí)字符串SB 不是SA 的子串.

3.2 協(xié)議的正確性

定理1 協(xié)議1 能正確判斷保密字符串SB是否為SA的子串.

這樣計(jì)算結(jié)果E(W) ={E(w1)，E(w2)，···，E(wn-m+1)}中只要解密結(jié)果中有一個(gè)為0， 就說(shuō)明字符串SB是字符串SA的子串; 反之， 則不是.

3.3 協(xié)議的安全性

定理2 保密判斷字符串SB是否為SA的子串的協(xié)議1 是安全的.證明: 在半誠(chéng)實(shí)模型下， 通過(guò)構(gòu)造模擬器S1和S2使式(1) 和(2) 成立來(lái)證明本定理. 在協(xié)議1 中

其中，SA、SB是Alice 和Bob 的輸入，r1是Alice 加密時(shí)所選擇的隨機(jī)數(shù)集合，E(W) 是Bob 根據(jù)字符串SB通過(guò)循環(huán)移動(dòng)從SA中抽取對(duì)應(yīng)位置進(jìn)行計(jì)算所得結(jié)果構(gòu)造的集合， 然后將集合中元素置換后發(fā)送給Alice 的結(jié)果，r2是由Bob 加密時(shí)所選擇的隨機(jī)數(shù)和計(jì)算時(shí)所選隨機(jī)數(shù)組成的集合，E(A) 是Alice 發(fā)送給Bob 的密文信息，f1(SA，SB)，f2(SA，SB) 分別是Alice、Bob 收到的輸出結(jié)果.

4 含通配符的字符串匹配

問(wèn)題描述: Alice 擁有字符串SA， Bob 擁有含通配符的字符串SB， Bob 知道SB中通配符的個(gè)數(shù)和每個(gè)通配符所代表字符的個(gè)數(shù). 換句話(huà)說(shuō)，SB中已知字符所處的位置是確定的. 雙方想知道含通配符的字符串SB和SA是否匹配， 且不泄露SA，SB的任何信息. 例如:SA= sunday，SB= sun*y，SB中的通配符代表2 個(gè)字符， 則字符s，u，n，y分別位于SB的第一、二、三、六的位置， 與SA中對(duì)應(yīng)字符所處的位置一樣， 則稱(chēng)SA和SB是匹配的. 本文首先將保密的數(shù)據(jù)編碼成一個(gè)向量， 向量元素是由對(duì)應(yīng)字符在全集中對(duì)應(yīng)位置的兩位十進(jìn)制數(shù)表示， 在加法同態(tài)性的基礎(chǔ)上設(shè)計(jì)一個(gè)簡(jiǎn)單、高效的協(xié)議.

例2 Alice 有字符串SA=privacy， 按照協(xié)議1 編碼方式將其編碼成向量A=(26，28，19，32，11，13，35)， 并發(fā)送給Bob.

(1) Bob 有含通配符的字符串SB=*ri*cy， Bob 知道第一個(gè)通配符代表一個(gè)字符， 第二個(gè)通配符代表2 個(gè)字符， 他根據(jù)已知字符r，i，c，y生成對(duì)應(yīng)向量B=(28，19，13，35).

(2) Bob 根據(jù)SB中已知字符所在位置為第二、三、六和七的位置， 在向量A中挑選第二、三、六和七位置所對(duì)應(yīng)的元素得到向量A′=(28，19，13，35).

(3) Bob 將向量B和向量A′中對(duì)應(yīng)元素相減， 得到向量T=(0，0，0，0)， 并將向量T中元素相加得到total. 如果total=0， 則兩字符串匹配; 反之， 則不匹配.該方法適應(yīng)通配符在任意位置的關(guān)鍵字匹配問(wèn)題:

*vacy，pri*，pri*cy，p*va*，*ri*cy，*va*，p*va*y.

4.1 具體協(xié)議

協(xié)議2 含通配符的字符串保密匹配協(xié)議輸入: Alice、Bob 各自的私密字符串SA = a1a2···an， SB = b1b2···bm.輸出: P(SA，SB).(1) (G，D，E) 是Paillier 同態(tài)加密方案， τ 是設(shè)定的安全參數(shù)， Alice 運(yùn)行G(τ) 生成同態(tài)加密的公私鑰對(duì)， Alice 向Bob公布生成的公鑰.(2) Alice 調(diào)用協(xié)議1 的編碼方法生成向量A = (a′1，a′2，··· ，a′n)， 加密向量A 得E(A) = (E(a′1)，E(a′2)，··· ，E(a′n))并將E(A) 發(fā)送給Bob.(3) Bob 調(diào)用協(xié)議1 的編碼方法生成向量B = (b′1，b′2，··· ，b′m)， 用Alice 的公鑰加密得到E(B) = (E(b′1)，E(b′2)，··· ，E(b′m)).(4) Bob 根據(jù)SB 中已知字符的位置， 在E(A) 中挑選對(duì)應(yīng)的元素得到向量E(?A) = (E(a′i)，E(a′i+1)，··· ，E(a′i+m-1)) = (E(?a1)，E(?a2)，··· ，E( ?am)). Bob 選擇隨機(jī)數(shù)ri(1 ≤i ≤m)，計(jì)算如下:E(total) =m∏(E(?ai)*E(N -b′i))ri，i=1將E(total) 發(fā)送給Alice.(5) Alice 用自己的私鑰對(duì)E(total) 解密得到total， 如果total = 0， 那么輸出P(SA，SB) = 0， 字符串SA 和字符串SB匹配; 否則， 輸出P(SA，SB) = 1.

4.2 協(xié)議的正確性

定理3 協(xié)議2 能正確判斷保密含通配符的字符串SB與字符串SA是否匹配.

因此， 若total=0， 則含通配符的字符串SB和字符串SA匹配; 反之， 含通配符的字符串SB與字符串SA不匹配.

4.3 協(xié)議的安全性

定理4 保密判斷含通配符的字符串SB與字符串SA是否匹配的協(xié)議2 是安全的.證明: 在半誠(chéng)實(shí)模型下， 通過(guò)構(gòu)造模擬器S1和S2使式(1) 和(2) 成立來(lái)證明本定理. 在協(xié)議2 中

由于E(A)是Alice 加密的，Bob 沒(méi)有私鑰，根據(jù)加密算法的語(yǔ)義安全性，對(duì)于Bob 來(lái)說(shuō)E(A)c≡

5 效率分析

5.1 計(jì)算復(fù)雜性分析

(1) 判斷字符串模式匹配時(shí)， 文獻(xiàn)[21] 基于ElGamal 加密算法， 文獻(xiàn)[24] 協(xié)議2 基于Goldwasser-Micali 加密算法， 且都調(diào)用了BMH 算法， 與本文協(xié)議1 均為公鑰加密系統(tǒng). 文獻(xiàn)[22] 采用SHE 和新的數(shù)據(jù)包裝技術(shù)實(shí)現(xiàn)單一模式串匹配(即模式串只能在文本中出現(xiàn)一次)， 文獻(xiàn)[24] 協(xié)議4 基于對(duì)稱(chēng)密碼算法， 只能實(shí)現(xiàn)單一模式串匹配， 本文協(xié)議1 可以實(shí)現(xiàn)多模式串匹配. 文獻(xiàn)[23] 在惡意模型下， 本文協(xié)議1 在半誠(chéng)實(shí)模型下， 效率沒(méi)有可比性. 因此， 本文協(xié)議1 只與文獻(xiàn)[21] 和文獻(xiàn)[24] 協(xié)議2 做對(duì)比.

(2) 判斷含通配符的字符串匹配問(wèn)題時(shí)， 文獻(xiàn)[28] 在惡意模型下只能實(shí)現(xiàn)單個(gè)通配符的匹配， 本文協(xié)議2 在半誠(chéng)實(shí)模型下可以實(shí)現(xiàn)多個(gè)通配符的匹配. 文獻(xiàn)[17-20] 基于Bloom Filter 只能實(shí)現(xiàn)字符串的近似匹配， 本文協(xié)議2 能實(shí)現(xiàn)字符串的精確匹配. 文獻(xiàn)[29] 基于SHE 進(jìn)行字符串匹配， 但SHE 的安全性依賴(lài)于Ring LWE 問(wèn)題， 且只能實(shí)現(xiàn)有限次的乘法， 其適用性沒(méi)有本文協(xié)議2 采用的Paillier 加密系統(tǒng)強(qiáng). 因此， 本文協(xié)議2 不與上述方案做對(duì)比.

5.2 通信效率分析

衡量通信復(fù)雜度的指標(biāo)用協(xié)議交換信息的比特?cái)?shù)， 或用通信輪數(shù)， 在安全多方計(jì)算研究中通常用輪數(shù).

(1) 判斷字符串模式匹配時(shí)， 文獻(xiàn)[21] 需要mn2+mn輪， 文獻(xiàn)[24] 協(xié)議2 需要2mn輪， 本文協(xié)議1 需要2 輪通信. 如表1 所示.

表1 判斷字符串模式匹配方案計(jì)算復(fù)雜性與通信復(fù)雜性的比較Table 1 Comparison of some solutions to string matching

(2) 判斷含通配符的字符串匹配時(shí)， 本文需要2 輪通信. 如表2 所示.

表2 判斷含通配符字符串匹配方案計(jì)算復(fù)雜性與通信復(fù)雜性Table 2 String matching with wildcards

5.3 實(shí)驗(yàn)數(shù)據(jù)分析

實(shí)驗(yàn)測(cè)試環(huán)境: Windows7 64 位操作系統(tǒng)， 處理器是Intel(R) Core(TM) i5-5200U CPU @2.2 GHz，內(nèi)存是4.00 GB， 在PyCharm 2020.1 (Professional Edition) 用python 語(yǔ)言運(yùn)行實(shí)現(xiàn).

實(shí)驗(yàn)方法: 在判斷字符串模式匹配時(shí)， 文獻(xiàn)[21] 和文獻(xiàn)[24] 協(xié)議2 都采用了同態(tài)加密算法， 所以我們通過(guò)模擬實(shí)驗(yàn)來(lái)測(cè)試文獻(xiàn)[21]、文獻(xiàn)[24] 協(xié)議2 和本文協(xié)議1 所用的時(shí)間， 通過(guò)比較協(xié)議執(zhí)行的時(shí)間來(lái)比較效率. 本實(shí)驗(yàn)以字符串SA和字符串SB為例， 設(shè)定字符串SA的長(zhǎng)度為n=26， 字符串SB的長(zhǎng)度m依次取1， 2，···， 20， 針對(duì)每一個(gè)m均進(jìn)行1000 次模擬實(shí)驗(yàn)測(cè)試， 統(tǒng)計(jì)協(xié)議執(zhí)行時(shí)間的平均值(忽略協(xié)議中的預(yù)處理時(shí)間). 文獻(xiàn)[21] 基于ElGamal 加密算法設(shè)計(jì)的協(xié)議， 文獻(xiàn)[24] 的協(xié)議2 基于GM 加密算法設(shè)計(jì)的協(xié)議， 本文協(xié)議1 基于Paillier 加密算法設(shè)計(jì)的協(xié)議， 因此進(jìn)行實(shí)驗(yàn)時(shí)我們采取ElGamal 加密算法、Goldwasser-Micali 加密算法和Paillier 加密算法的模數(shù)均為1024 比特， 選取隨機(jī)數(shù)長(zhǎng)度為64 比特.圖1 為文獻(xiàn)[21]、文獻(xiàn)[24] 協(xié)議2 和本文協(xié)議1 字符串模式匹配的執(zhí)行時(shí)間隨模式串字符個(gè)數(shù)增長(zhǎng)的變化規(guī)律.

圖1 當(dāng)模數(shù)為1024 bit， n=26 時(shí)字符串模式匹配的執(zhí)行時(shí)間隨m 增長(zhǎng)的變化規(guī)律Figure 1 Execution time of string pattern matching with m， when n = 26， modulus is 1024 bit

在判斷含通配符的字符串匹配時(shí)， 我們進(jìn)行本文協(xié)議2 的實(shí)驗(yàn). 本實(shí)驗(yàn)以字符串SA和含通配符的字符串SB為例， 設(shè)定字符串SA的長(zhǎng)度為n=26， 字符串SB的長(zhǎng)度m(不包含通配符的個(gè)數(shù)) 依次取1，2，···， 20， 針對(duì)每一個(gè)m均進(jìn)行1000 次模擬實(shí)驗(yàn)測(cè)試， 統(tǒng)計(jì)協(xié)議執(zhí)行時(shí)間的平均值(忽略協(xié)議中的預(yù)處理時(shí)間). 實(shí)驗(yàn)所選取的Paillier 加密算法的模數(shù)為1024 比特， 選取隨機(jī)數(shù)長(zhǎng)度為64 比特. 圖2 為本文協(xié)議2 字符串模式匹配的執(zhí)行時(shí)間隨m增長(zhǎng)的變化規(guī)律.

圖2 當(dāng)模數(shù)為1024 bit， n=26 時(shí)含通配符字符串匹配的執(zhí)行時(shí)間隨m 增長(zhǎng)的變化規(guī)律Figure 2 Execution time of string with wildcards with m， when n = 26， modulus is 1024 bit

從圖1 協(xié)議執(zhí)行時(shí)間可看出， 隨著模式串長(zhǎng)度m的增加， 本文協(xié)議1 的計(jì)算復(fù)雜度比文獻(xiàn)[21] 和文獻(xiàn)[24] 協(xié)議2 有明顯的降低， 因此本文所設(shè)計(jì)的協(xié)議是高效的.

6 結(jié)論

字符串匹配問(wèn)題是安全多方計(jì)算的常見(jiàn)問(wèn)題之一， 具有重要的研究意義和研究背景. 含通配符的字符串匹配可以用于數(shù)據(jù)處理、數(shù)據(jù)壓縮、詞頻統(tǒng)計(jì)、生物序列分析、SQL 語(yǔ)句查詢(xún)、信息檢索等多種應(yīng)用中. 本文首先設(shè)計(jì)了一種新的編碼方法， 并結(jié)合Paillier 加法同態(tài)加密算法， 在半誠(chéng)實(shí)模型下設(shè)計(jì)了字符串模式的保密匹配協(xié)議和含通配符的字符串保密匹配協(xié)議. 現(xiàn)有的字符串匹配協(xié)議， 大多只能實(shí)現(xiàn)字符串的近似匹配、明文情況下的字符串匹配算法、明文情況下的精確匹配和云計(jì)算下基于Bloom Filter 的字符串匹配. 本文所設(shè)計(jì)的協(xié)議可以實(shí)現(xiàn)在同態(tài)加密下的精確匹配， 時(shí)間復(fù)雜度和效率都比較低. 下一步我們將進(jìn)一步研究云計(jì)算下更高效的含通配符的字符串匹配協(xié)議.