一個高效安全三方帶通配符模式匹配協議

魏曉超 鄭志華 王 皓

(山東師范大學信息科學與工程學院 濟南 250358)

分布式計算場景中存在多個獨立的參與方，他們通過網絡相互連接并希望使用自己的私有數據協同完成某項任務.隨著隱私泄露事件的不斷發生以及人們隱私保護意識的不斷增強，如何在分布式計算過程中實現隱私數據的保護成為當下分布式計算安全的重要研究內容.在密碼學研究中，安全多方計算(secure multiparty computationm, SMPC)[1-3]是實現分布式場景中數據隱私保護的重要技術，其形式化的安全模型、安全性定義、可證明安全技術以及豐富的基礎工具為實現分布式安全提供強大的理論和技術支持.此外，隨著云計算、大數據等新興技術的發展，分布式計算的場景和模式也隨之而發生變化，急切需要新的解決方式，如云輔助安全多方計算[4]等來應對新模型、新問題的挑戰.

模式匹配是計算機科學領域一個非常基本的問題，在信息檢索、生物信息學等領域應用廣泛.它本質上是一個搜索問題，即查找一個給定的模式p∈[Σ]m在文本t∈[Σ]n中出現的位置，其中Σ是一個字母表集合，譬如假設p和t均為二進制表示，則Σ={0,1}.我們將上述問題成為精確模式匹配問題，即尋找整個模式串出現的位置.除此之外，模式匹配問題還有諸多變種，譬如近似模式匹配、帶通配符的模式匹配等.近似匹配廣泛出現在人類基因測序和拼接，由于核苷酸多態性或排序偏差，不同基序列可以組合成相同的基因，只要滿足他們的差異在某個閾值以內，因此只需要近似相等就可以識別出一個人.此外，當我們想查詢某一類帶有共同特性的數據時，可以使用通配符來表示數據中不同的信息，只保留相同的數據信息，進而使用帶通配符的模式匹配方案來完成批量數據的搜索，提高搜索的效率.

不難看出模式匹配及其變種問題應用極廣，但是在當前分布式計算場景下，數據的隱私性威脅日益嚴峻，人們不希望將自己查詢的信息泄露給其他個人或機構，因此需要我們在完成模式查詢的同時，保證數據隱私不被泄露.在上述應用場景中涉及到至少2個參與實體，即文本數據持有者和模式持有者，因此我們從協議層面考慮可以使用安全兩方計算對模式匹配協議進行形式化描述.具體地，安全模式匹配協議中包含2個參與方——數據庫和用戶，其中數據庫持有一個文本t∈[Σ]n，用戶持有一個模式p∈[Σ]m.協議希望確定模式p出現在文本t中的位置，同時要滿足2個安全屬性：1)模式p要對數據庫方保密；2)用戶除了p出現的位置之外不知道文本t中的其他任何信息.

1 相關工作和主要工作

1.1 相關工作

針對安全模式匹配協議的研究最早可以追溯到2007年Troncoso-Pastoriza等人[5]的工作.他們主要針對精確匹配問題，將其轉化為茫然自動機求值問題.之后又有諸多文獻對此進行效率和安全性的改進[6-9].此外，還有學者使用茫然偽隨機計算[10-11]和Yao混亂電路[12]等不同技術分別給出不同協議構造.近些年該領域的發展主要表現在安全模式匹配的功能性擴展上，包括近似模式匹配、帶通配符模式匹配和外包模式匹配等.

1) 近似模式匹配

近似模式匹配不像精確匹配要求的那么嚴格，只要模式和文本中子串的不同信息滿足一個給定的閾值，就意味著匹配成功.鑒于現實生活中很多數據的采集都不是絕對一致的，因此近似匹配在基因比對、人臉識別等領域應用廣泛.2009年Jarrous和Pinkas[13]首次安全計算2個等長字符串的Hamming距離，并將其應用到近似模式匹配協議中去.該協議主要基于茫然多項式計算(oblivious polynomial evaluation)技術，協議通信和計算量均為O(nm).之后，Vergnaud[14]使用快速傅里葉變換(fast Fourier transform, FFT)技術分別構造了可以抵抗半誠實和惡意敵手近似模式匹配協議.Hazay和Toft[15-16]使用編輯距離(edit distance)來衡量2個字符串的相似度，基于具有加同態性質的加密方案，并結合知識的零知識證明協議，實現安全計算2個等長字符串的編輯距離.編輯距離指的是將一個字符串變成另一個字符串所需要的操作步數，該協議的核心就是如何針對加密數據安全計算編輯距離.他們所構造的協議通信和計算復雜度分別為O(nτ)和O(nm)，其中τ是衡量“近似”特性的閾值.Wei等人[17]使用門限秘密分享和OT協議(oblivious transfer protocol)給出新的協議構造.其主要思想是用秘密分享份額來表示文本t的每一個位信息，并通過OT擴展協議完成對份額的傳輸，最終將匹配問題等價轉化為秘密能否重構.協議的通信復雜度和計算復雜度分別為O(nm)和O(k)，其中k是OT擴展協議中的基礎OT數目，其值遠小于nm.

2) 帶通配符模式匹配

通配符意味著其可以被字符集合中的任意字符所代替，在模式中設置通配符位可以起到批量查找的作用.譬如，學校要查找所有2017級的學生信息.只需將查詢學號的前4位設置成“2017”，后面設置為通配符就可以了，即形如“2017****”.針對安全帶通配符模式匹配的研究是近幾年的研究熱點，其核心問題是如何實現通配符信息與任意字符串的成功匹配.Hazay和Toft[15-16]通過2個參與方秘密地將通配符作相同的替換處理，從而將帶通配符匹配轉化為精確匹配.使用加同態加密方案，其協議的通信復雜度和計算復雜度分別為O(n+m)和O(nm).Baron等人[18]針對非二進制字母表的一般化帶通配符模式匹配協議做了研究，其主要思想是基于線性代數公式及加同態加密方案，其通信和計算復雜度與文獻[15-16]相同.此外，文獻[19-20]基于對稱類同態加密技術構造了安全帶通配符模式匹配協議.他們構造了一種數據包裝技術，可以針對加密數據高效計算多個Hamming距離.該協議可以適用于非二進制數據，經過對真實DNA序列的實驗測試，其可以實現一秒鐘查詢長度為16 500的基因序列.基于此，Saha等人[21]考慮如何在外包數據中實現帶通配符模式匹配.通過改變上述包裝技術使其能夠適用于外包場景，協議效率有了k倍的提升.2017年，Kolesnikov等人[22]基于OT擴展協議構造了一個高效的安全帶通配符模式匹配協議.他們的協議首先使用OT協議使得2個參與方能共同計算出一個隨機值，然后調用安全字符串相等性測試(secure string equality test)協議來確定計算出來的值是否相等，以此來確定模式是否匹配.協議的計算和通信復雜度分別為O(k)和O(nm)，缺點是要額外調用字符串相等性測試協議.2018年，Darivandpour等人[23]使用輕量級密碼給出更為高效的協議構造.他們的方案可以針對所有的字符集并支持任意規模的輸入，但是需要一個離線服務器(云服務器)幫助參與方生成一些協議中使用到的隨機數.

3) 外包模式匹配

云計算的發展使得外包計算成為一種潮流和趨勢，因此外包模式匹配也成為大家研究的熱點.在外包模式匹配場景中，用戶將自己數據加密并發送至云服務器上，在搜索某個模式是否存在時，委托云服務器代勞并將匹配結果秘密返回給用戶.就隱私性而言，用戶的數據、查詢的模式以及匹配結果都要對服務器保密.2013年，Faust等人[24]首次將模式匹配問題等價轉化為子集和問題，即如果一個值可以被表示為某一個子集中元素的和，則意味著模式存在于文本中.他們的協議可以抵抗半誠實和惡意敵手，但是需要隨機預言機的存在.與之類似的，Chase和Shen[25]提出子串對稱可搜索加密的概念，即使用對稱可搜索加密的思想實現外包加密文本中子串的匹配問題.使用后綴樹技術，他們給出的方案相對高效，且可以抵抗惡意敵手攻擊.后續又有諸多工作[26-28]針對這一全新的功能函數給出更優的實現.此外，Li等人[29]在外包場景下針對隱私保護的模式匹配問題給出了一個安全協議構造，他們的協議主要使用帶聚合的加密方案對數據加密，匹配階段的計算量為O(nm).文獻[30]首次構造了一個隱私保護的多模式匹配協議，其可以針對加密的模式集合執行秘密檢索.該協議主要基于Aho-Corasick自動機，其計算復雜度在最壞情況下為O(n+d)，其中n是本文的長度，d是多個模式中最長模式的長度.

1.2 本文的主要工作

本文首次在三方場景下考慮安全帶通配符模式匹配協議.之前的帶通配符模式匹配協議往往僅涉及2個參與方，即模式持有者查詢其模式信息是否出現在某一數據庫文件中.然而，在當今信息化時代，信息的有償使用也日益成為一種消費形式，即用戶希望通過支付方式來獲得他人信息的使用權，但前提是要保證信息提供者的隱私性，同時也要保證用戶的結果是保密的.因此，我們考慮如下帶通配符模式匹配場景，如圖1所示：

Fig. 1 The system model圖1 系統模型

圖1中2個數據提供方分別提供數據庫文件和帶通配符模式信息，用戶希望了解模式是否存在于數據庫文件中，以此為后續工作奠定基礎.很顯然，數據提供方不希望將自己的數據泄露給其他人，而且用戶也希望自己得到的結果是保密的.現實生活中有諸多這樣的例子，譬如在購買保險時，保險公司通常會根據投保人是否有某些疾病來設定保險的價格，但是個人的疾病信息是及其隱私的，每個人都不想讓保險機構知道這些信息.這樣我們就可以使用圖1的模型，設定信息提供方分別為醫院和個人，其中醫院有某些疾病的基因庫，個人則提供自己的健康信息.模型中的用戶即為保險公司，它希望知道投保人是否得某種病，即投保人的健康數據是否能與醫院的某種疾病匹配成功.這樣一來，在保證隱私的前提下，保險公司就可以完成對投保人疾病信息的核實和檢驗，從而為后期保費的設定提供依據.

本文的貢獻主要包含以下3個方面：

1) 首次在三方場景下根據具體的應用需求考慮一種三方帶通配符模式匹配協議，從而擴展了帶通配符模式協議在當前數據時代的全新應用.同時，我們對該協議的功能函數給出了形式化的描述和論述；

2) 針對協議功能函數的特點，本文基于秘密分享和外包OT協議給出了一個半誠實安全的協議構造.帶通配符模式匹配的難點在于如何使得通配符位可以匹配任意值，因此就需要通過一定的方法將一個帶通配符的模式轉換成正常的模式(即去除通配符)，進而進行精確的模式匹配操作.鑒于此，我們首次使用秘密分享份額表示法，針對通配符位和非通配符位上的位做2種不同的表示.其中非通配符位按照其真實比特值構造一對數值，滿足與真實比特對應位置的數值是合法的秘密分享份額，另一個值為隨機數；而針對通配符位，將2個數值均設置位合法的秘密分享份額.通過這種表示方法，并結合外包OT協議的使用，使得無論欲匹配的文檔中與模式中通配符位對應的位信息是什么，都能得到合法的秘密分享份額，這樣就在不泄露通配符位置的情況下完成了通配符的匹配.

3) 本文所構造的安全三方帶通配符模式匹配協議需要3輪交互.通過使用OT擴展技術，協議中參與方的計算復雜度可以從O(nm)降低至O(k)，其中n和m分別是數據提供方的輸入長度，k是協議所需基礎OT協議的個數，其值遠小于nm，譬如，nm=106，則k僅為128即可滿足.

2 基本知識和安全定義

2.1 秘密分享協議

秘密分享(secret sharing)協議最早是由Shamir[31]和Blakley[32]在1979年提出的，并分別基于Lagrange插值定義和射影幾何理論給出具體構造，其在門限加密、安全多方計算領域有著廣泛應用.在秘密分享協議中考慮將一個秘密值s分享至n個參與方，其中每個參與方得到的分享值稱為分享份額.協議要求只有當n個參與方中的某些授權子集提供正確的分享份額時，才能夠成功恢復出正確的秘密值，而那些不在授權子集中的參與方不可能重構出秘密.如果將授權子集中參與方的個數t稱之為門限值，則相應的秘密分享協議也被稱之為(t,n)-門限秘密分享協議，其要求只有當共享份額的數目至少為t個時才能夠恢復出正確秘密值.

2.2 外包茫然傳輸協議

外包茫然傳輸協議(outsourced oblivious tran-sfer, OOT)[33]是在傳統茫然傳輸協議[34]的基礎上，增加一個云服務器作為協議第三方.在外包OT協議中，不再是接收方得到其選擇的輸出信息，而是由云服務器最終獲得這些值.換言之，傳統OT協議中的發送方和接收方依然輸入相應的信息，只不過輸出值最終發送給云服務器.與此同時，仍需要保證每個參與方的輸入信息向其他參與方保密.

OT擴展協議(oblivious transfer extension)[35]可以用很少的(如128個)基礎OT加上廉價的對稱密鑰操作實現大規模(如106)OT的效果。因此OT擴展技術被廣泛應用于需要大量使用OT協議的場景中，從而提高協議的整體效率.同理，在外包OT場景中，仍然可以使用OT擴展技術來達到相同的目的，其基本思想是在發送方和接收方之間執行OT擴展協議，然后再將得到的值置換之后發送給云服務器.下面我們給出外包OT擴展協議的具體描述：

協議1. 外包茫然傳輸擴展協議.

輸入：Alice輸入長度為n的的字符串ea，Bob輸入數對(x0,j,x1,j)，其中j=1,2,…,n，云服務器無輸入;

輸出：云服務器輸出Bob選擇的相應值.

步驟1. 初始化：Alice生成一個規模為n×t的隨機矩陣T，Bob生成一個長度為t的隨機串s.

步驟2. 基礎OT：Alice和Bob執行t個1-out-of-2茫然傳輸協議，其中Alice輸入(Ti,Ti⊕ea)，Bob輸入選擇比特s，Ti表示矩陣T的第i列.Bob將接收到的列信息設置為矩陣Q.

步驟3. 選擇置換：Alice生成一個長度為n的隨機串p，并將其發送給Bob.

步驟4. 加密輸出：Bob將加密后的輸出對設置為(y0,j,y1,j)，其中，yb,j=xb,j⊕H1(j,Qj⊕(b·s)),Qj表示矩陣Q的第j行.

步驟5. 輸出置換：Bob將加密后的輸出對置換為y0⊕pj,j,y1⊕pj,j，然后將最后的數對集合Y發送給云服務器.

步驟6. 解密輸出：Alice將h=ea⊕p和T發送給云，云服務器計算出zj=yhj,j⊕H1(j,Tj)，其中j=1,2,…,n，Tj表示矩陣T的第j行.

2.3 計算不可區分性

假設2個分布總體X={X(a,n)}a∈{0，1}*;n∈和Y={Y(a,n)}a∈{0，1}*;n∈是計算不可區分的，表示為X≡Y，則對每個非均勻多項式時間算法D，總存在一個可忽略函數μ(·)，對于每個a∈{0,1}*和每個n∈，有不等式成立：

|Pr[D(X(a,n)=1)]-Pr[D(Y(a,n)=1)]|≤μ(n).

2.4 安全性定義

本文主要考慮半誠實敵手，即參與方嚴格按照協議規定執行，但是期望從其視圖中獲取其他參與方的輸入信息.需要說明的是，我們假設誠實方大多數情況，即在三方場景中至多有一個參與方被腐化.我們使用文獻[36]中的安全性定義：

定義1. 令f:{0,1}*×{0,1}*×{0,1}*→{0,1}*×{0,1}*×{0,1}*是一個三方功能函數，π是一個真實的三方協議.若協議π在半誠實敵手模型下安全計算f，必須滿足針對現實模型中的每個非均勻概率多項式時間敵手A，總存在一個理想模型中的非均勻概率多項式時間敵手S，對于每個i∈{1,2,3}，

{IDEALf,S (z),i(x,y,z,n,s)}≡
{REALπ,A (z),i(x,y,z,n,s)}，

其中,x,y,z∈{0,1}*滿足|x|=|y|，且n,s∈.

3 安全三方帶通配符模式匹配協議

3.1 三方帶通配符模式匹配功能函數

本文所考慮的三方帶通配符模式匹配功能函數FTWPM中主要涉及3個參與方P1，P2和P3，其中P1，P2是傳統兩方帶通配符模式匹配協議中的文本提供方和模式提供方，而P3是我們附加的一個參與方，其希望使用其他2個參與方的數據來實現自己的意圖(如統計信息等).下面給出功能函數FTWPM的形式化描述.

輸入：

1)P1輸入長度為n的二進制字符串t及整數m；

2)P2輸入長度為m的帶通配符二進制字符串p以及整數n，其中通配符表示為*，且其個數為τ；

3)P3無輸入.

輸出：

1)P3確定模式p是否在t中出現，并輸出出現的次數；

2)P1，P2無輸出.

需要強調的是，在利用數據的同時，P1和P2并不希望將自己的輸入泄露給P3，同時P3也不希望自己的查找結果讓別人知道，因此功能函數的安全性要保證這2點.

3.2 安全三方帶通配符模式匹配協議構造

在本節中，我們在半誠實敵手模型下構造一個安全三方帶通配符模式匹配協議.協議具體表述如下：

協議2. 三方帶通配符模式匹配協議πTWPM.

輸入：P1輸入一個長度為n的二進制字符串t和一個整數m，P2輸入一個長度為m的帶通配符(個數為τ)的二進制字符串(模式)p和一個整數n，P3沒有輸入；

輸出：P3輸出p是否在t中出現以及出現次數.

步驟1. 參與方P2使用秘密分享方案表示其輸入，即帶通配符的模式p.具體地，針對p的每一個位，使用一組數對來表示.對于非通配符位(即0/1比特)，與位對應位置的數值是一個合法的秘密分享份額，另一個數值為隨機數；對于通配符位上的比特值，2個數值均為合法的秘密分享份額.假設針對某一個秘密s，使用一個秘密分享方案來生成秘密分享份額，其中該秘密分享方案需要滿足至少需要m個共享份額才能恢復出秘密.具體表示方法如下：

鑒于P1的輸入t中有n-m+1個長度為m的子串，因此參與方P2需要針對每一個子串使用不同的秘密值來表示其自己的輸入，即P2要生成如下數值：

這些數值作為下一步茫然傳輸協議中發送方的 輸入信息.

步驟2. 參與方P1，P2和P3共同運行一個外包茫然傳輸協議(OOT)，其中P1代表接收方R，P2代表發送方S，P3代表最終獲得輸出的服務器方.考慮OOT協議中的輸入信息，作為接收方的P1輸入字符串t，而作為發送方的P2輸入步驟1中生成的所有數值(除此之外還需將生成秘密份額所使用的所有n-m+1個秘密值按照順序發送給P3)，參與方P3無輸入.執行完OOT協議之后，參與方P3會得到所有的輸出，即根據P1的輸入從P2生成的所有數對中得到的與之匹配的值.

步驟3. 參與方P3根據其從OOT協議中得到的輸出值分別執行秘密重構操作，并比較重構出的秘密值和接收到的秘密值，最終確定模式p是否在t中有出現，具體地：

① 若重構出的數值中存在與接收到的秘密值相等的，則輸出1，表示匹配成功，并輸出相等的個數；

② 否則，輸出0，表示不存在匹配成功的值.

3.3 正確性分析

在證明協議安全性之前，我們首先分析一下協議的正確性，即在運行完上述協議之后，參與方P3最終會得到正確的結果.我們從2個方面說明其正確性：

1) 若匹配成功，則意味著t中至少有一個長度為m的子串與模式p匹配，這就表明模式p中非通配符位上的所有值與該子串中相應位置上的值均相等.因此，在OOT協議中，使用該子串作為接收方輸入時，P3會接收到所有合法的秘密分享份額，其中非通配符位是因為值相同所致，而通配符位總是會得到合法份額.最終，只用這些合法的共享份額，P3能夠重構出相同的秘密值，并確定存在匹配成功的子串信息.

2) 若無成功匹配時，則意味著t中所有長度為m的子串均與模式p不匹配.以某一個子串為例，這表明模式中的非通配符位中至少有一位的值與該子串中相應位置的值不等.因此，在OOT協議中，在這一位置上P3得到的值是一個隨機數，而非一個合法的秘密分享份額.根據所選秘密分享方案的性質，合法共享份額的數量少于m，這就使得在秘密重構階段無法正確構造出相應的秘密值，從而也就確定匹配不成功.

3.4 安全性分析

協議2主要涉及2個密碼學基礎原語的應用，即秘密分享和外包茫然傳輸.直觀上來看，因為外包茫然傳輸協議是安全的，因此P1(即接收方R)的輸入信息對于P2和P3而言是保密的，即保證了t不被泄露.此外，根據秘密分享方案的性質，當分享份額數目不足以重構出秘密時，其不泄露分享份額的信息，因此P3根據接收到的值僅僅能知道是否匹配成功，但是并不能推測出P2的每一位的值到底是什么.這樣，通過以上2個基礎原語的性質，協議的安全性得以保障.下面，我們根據2.4節中的安全性定義，給出協議πTWPM的形式化安全證明.

定理1. 假設外包茫然傳輸協議在半誠實敵手模型下是安全的，秘密分享方案滿足僅當共享份額數目大于等于m時才能重構出秘密，則協議πTWPM在半誠實敵手模型下安全計算功能函數FTWPM.

證明. 我們在混合模型下證明協議2的安全性，其中外包模式匹配協議通過一個理想功能函數FOOT計算實現.我們分別針對P1，P2和P3被腐化這3種情況進行證明.

1)P1被腐化.令A1為現實世界腐化P1的敵手.我們構造一個模擬器S1按照如下方式模擬敵手A1：S1調用敵手A1的輸入t，n和m，并將其發送給理想世界中計算理想功能函數FTWPM的可信第三方.之后，模擬器S1模擬理想功能函數FOOT，并以OOT協議中誠實發送方P2的身份使用一個隨機的模式p生成相應的秘密分享份額發送給FOOT. 最后，模擬器S1輸出敵手A1的輸出.

以上是P1被腐化的理想模擬過程.我們要證明在上述理想世界的模擬過程中敵手和模擬器執行的聯合輸出分布，與在現實世界的真實協議中敵手和誠實參與方產生的聯合輸出分布式計算不可區分的，即

注意到P1在協議中沒有輸出，且其視圖信息僅包含在OOT協議中收到的P2的消息.此外，理想模擬過程與現實協議的唯一不同是模擬器選擇了一個隨機的模式p，而不是使用P2的真實輸入.鑒于外包模式匹配協議是半誠實安全的，因此敵手沒有能力區分P2的真實輸入到底是什么，這就使得隨機選擇一個模式p對于敵手而言是計算不可區分的.所以上述IDEAL分布和HYBRID分布是計算不可區分的.

2)P2被腐化.令A2為現實世界腐化P2的敵手.我們構造一個模擬器S2按照如下方式模擬敵手A2：S2調用敵手A2的輸入p，n，m和τ，并將其發送給計算理想功能函數FTWPM的可信第三方.之后，模擬器S2模擬理想功能函數FOOT，并以OOT協議中誠實接收方P1的身份將一個長度為n的隨機串t發送給FOOT.最后，模擬器S2輸出敵手A2的輸出.

我們欲證明上述模擬過程和真實協議執行分別產生的輸出聯合分布式不可區分的，即證明

通過比較IDEAL和HYBRID的執行過程可以發現，唯一的不同在于模擬器選擇了一個隨機的t作為誠實參與方P1在OOT協議中的輸入.根據外包茫然傳輸協議的安全性，P2在OOT協議中的視圖可以在不知道P1真實輸入的前提下生成，且生成的視圖對于敵手而言是與真實協議中的視圖計算不可區分的.鑒于此，我們推出上述理想模擬和現實協議的輸出分布是不可區分的.

3)P3被腐化.令A3為現實世界腐化P3的敵手.我們構造一個模擬器S3按照如下方式模擬敵手A3：S3調用敵手A3的輸入(為空)，并從理想世界中計算功能函數FTWPM的可信第三方那里接收到相應的匹配結果.假設匹配結果為t1,t2,…,ti，其中1≤t1≤…≤t1≤n-m+1.則模擬器就可以根據所接收到的這些信息，模擬理想功能函數FOOT所輸出的消息，也就是敵手A3從OOT協議中接收到的輸出信息.具體的，對于匹配成功的相應子串，模擬器選擇一個隨機秘密值并將子串中每一位上的秘密分享份額均設置為合法的，相反，對于那些未匹配成功的子串，就可以隨機設置分享份額的值(選取等長的隨機串即可).最后，模擬器S3輸出敵手A3的輸入，并終止協議.

同上所述，我們要證明理想模擬和現實協議所生成的2個分布不可區分，即

模擬器在模擬OOT協議輸出時，唯一不同的地方在于如何處理那些未匹配成功的字符串.因為秘密分享方案需要至少m個合法秘密分享份額才能重構出秘密，因此，當匹配不成功時，也就意味著至少存在一個不合法的秘密分享份額，從而導致不能重構出正確的秘密值.與此同時，在這種情況下也不會泄露具體哪些位置匹配成功，哪些位置未匹配成功.所以，模擬器針對這些匹配失敗的子串，通過選擇隨機數的方式來生成輸出信息，與真實協議中實際接收到的信息是計算不可區分的.

證畢.

3.5 協議效率分析與比較

協議2的交互主要體現在外包OT擴展協議中，根據2.2節中的協議過程可知共需要3輪的交互.考慮計算復雜度，主要包含秘密分享協議和外包OT協議中的計算量.其中，秘密分享協議中主要涉及共享份額的生成以及秘密重構，共需要O(mn)次操作.注意到這里的秘密分享需要全部的分享份額來恢復密鑰，因此可以使用隨機數異或的形式，這樣主要涉及對稱密鑰操作，因此實現起來更高效.外包OT階段主要涉及公鑰密碼操作，因此我們主要考慮OT階段的計算開銷.通過協議可知，參與方之間共需要執行O(nm)次1-out-of-2 OT協議來傳輸分享份額.然而，通過OT擴展技術，我們可以將其降低至O(k)的級別，其中k?mn.此外，協議的通信復雜度也為O(mn).表1是我們的協議與之前兩方帶通配符模式匹配協議的比較結果.

Table 1 Comparison of Wildcard Pattern Matching Protocols表1 帶通配符模式匹配協議比較

從功能性而言，之前的協議均考慮兩方場景，我們首次考慮三方帶通配符模式匹配協議.其次，考慮使用的密碼學工具，文獻[16]基于分布式的ElGmal加密方案，因此協議最后需要執行一個聯合解密協議，文獻[18]則使用帶有加法性質的同態加密方案，文獻[22]和我們的協議均基于OT擴展協議，不同的是他們的協議最后需要多次調用安全字符串相等性測試協議.從協議計算復雜度而言，文獻[16,18]需要O(nm)的計算量，其中n和m是2個參與方的輸入長度；文獻[22]和我們的協議的計算復雜度為O(k)，其中k是基礎OT的數目，遠小于nm的值.

4 結束語

本文主要考慮安全帶通配符模式匹配協議的高效構造，首次以具體三方場景應用為驅動，構造了一個半誠實安全的三方帶通配符模式匹配協議.協議主要基于秘密分享和外包茫然傳輸2個密碼學基礎工具，通過秘密分享份額的設置，對通配符位和非通配符位進行分別表示，并結合外包OT協議，將帶通配符模式匹配轉化成精確模式匹配.協議需要3輪交互，計算和通信復雜度分別為O(k)和O(nm)，其中n和m是2個數據提供方的輸入長度，k是實現OT擴展協議的基數，其值遠小于nm.