適用于智能環境的高效安全云輔助模式匹配協議

魏曉超 徐 琳 鄭志華 王 皓

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

隨著機器學習、人工智能、物聯網等理論技術的不斷深入和發展，人們的生活和工作方式有了很大的改變.這其中，各種智能設備所構建的智能環境深刻影響著人們的生活甚至思維方式.比如人們使用智能手環監測生命體征、使用智能駕駛模式開車出行、使用智能門鎖進行身份認證等.在帶給人類便利和輔助的同時，智能環境也出現諸多必須引起重視的問題和隱患：1)智能系統在獲取個人數據的同時必然存在隱私泄露[1-2]問題，因此保障用戶的數據隱私性勢必會成為研究的熱門;2)在智能環境中用戶的設備大多數是資源有限的，即不能支持大規模的計算和通信任務，因此就要求所設計的算法或協議必須是輕量級的，這樣才能滿足資源受限設備的工作條件.本文即從上述2個需求出發，考慮在智能場景中設計安全、高效的模式匹配協議，以滿足當下更多智能設備的實際需求.

模式匹配協議是一個典型的安全兩方計算協議，其考慮2個參與方，即數據庫方和用戶方，持有模式信息的用戶期望查詢其模式在數據庫方的數據中存在的信息(比如是否存在、存在位置等).考慮隱私性，用戶在查詢過程中不希望將自己的模式信息暴露給對方，此外還希望僅有自己知道匹配的結果.而數據庫方出于經濟或競爭等原因，也不希望將自己所持有的數據信息告知用戶，這也正是我們設計安全的模式匹配協議的初衷和目標.安全模式匹配協議在諸多領域有著廣泛的應用，比如基因匹配、人臉識別、病毒檢測等.以計算機病毒檢測為例，一般的殺毒軟件公司擁有自己強大的病毒庫，當用戶懷疑自己的手機或電腦中毒后，便會通過殺毒軟件檢測并與病毒庫中的病毒信息進行匹配，最終決定是否刪除或接受某些可疑文件.通過這種方式，用戶的數據隱私勢必要遭到威脅，殺毒軟件公司在提供病毒掃描服務過程中有可能會窺測到用戶其他私密的個人信息.因此，通過設計安全的模式匹配協議，可以實現在保護用戶數據文件隱私的前提下完成病毒查殺的目的.

除了考慮安全性，智能環境中資源受限設備的效率問題也是另一個亟需解決的問題.當前，云計算為用戶的數據存儲和計算提供了極大的便利，用戶可以將本地數據以某種安全的形式上傳至云服務器，并委托云服務器計算，從而達到減輕本地計算負擔的效果.因此在各種智能環境應用場景中引入云服務器進行輔助計算的思想，對于資源受限設備而言無疑是一種有效的途徑.

下面我們詳細論述一下云輔助安全多方計算及安全模式匹配協議的相關工作.

1 相關工作和主要工作

1.1 相關工作

1) 云輔助安全多方計算.安全多方計算[3-4](secure multi-party computation, SMPC)考慮在分布式場景中多個參與方使用各自的私有輸入，安全計算某個功能函數并各自得到輸出.幾乎所有的密碼學協議均可以使用安全多方計算模型來刻畫.模式匹配協議作為一個具體的安全兩方計算問題，也需要在兩方模型下構造協議并證明.傳統的SMPC場景中并不存在外部服務器，因此參與方的計算量通常都與所計算的函數相關.隨著云計算的興起，將云輔助的概念引入多方計算場景，對于提高部分參與方的效率有著很大的益處.云輔助安全多方計算的概念最早是由Kamara等人[5-6]提出，他們在標準安全多方計算模型中引入一個或多個外部服務器，用以承擔部分參與方實體的計算任務，從而減少參與方的計算量，使得安全協議的效率得以提高.相關文獻[7-12]針對基于Yao混亂電路的安全多方計算通用協議，給出諸多基于云輔助的高效協議構造，這些云輔助的安全協議較之于標準模型下的協議有很大的效率提升，尤其適用于某些資源受限設備存在的計算場景.

此外，還有諸多工作在云輔助模型下考慮某些具體問題的安全計算.比如隱私集合求交[13-15]、茫然傳輸[16]等.

2) 安全模式匹配協議.安全模式匹配協議是一個具體的安全兩方計算問題，其主要涉及數據庫方和模式方2個參與方.其中，數據庫方有一個文本t，模式方擁有一個模式p并希望查詢該模式在t中是否出現或出現的位置信息.與此同時，要保證模式信息和匹配結果對數據庫方是保密的，且數據庫的文本對于模式方也是未知的(除了部分匹配成功的信息).自2007年Troncoso-Pastoriza等人[17]最先考慮該協議并基于茫然自動機求值問題構造協議以來，有諸多工作基于不同的密碼工具和技術給出安全高效的構造.比如Hazay等人[18-19]使用茫然偽隨機計算在隱蔽敵手和惡意敵手模型下實現隱私集合求交和模式匹配協議的高效設計.Katz等人[20]則基于Yao混亂電路給出更一般化的構造，即將模式匹配問題轉化成等價電路并結合其它密碼學工具實現安全的模式匹配，他們的協議可以很好地應用于隱私DNA匹配問題中.魏曉超等人[21]基于秘密分享和茫然傳輸給出另一種構造方式，使用茫然傳輸(oblivious transfer, OT)擴展技術可以極大地提高協議效率.

除了標準的模式匹配問題，近年來針對近似模式匹配[18-19,22-23]、帶通配符模式匹配[18-19,24-29]和云輔助模式匹配[30-32]等功能性擴展問題的研究越來越引起國內外學者的研究.這些問題的研究更加符合一些實際的應用場景，比如基因匹配等需要使用近似模式匹配，帶通配符模式匹配可以實現批量數據的查詢.而云輔助模式匹配則是針對云輔助加密數據的匹配，更符合當前云計算的背景.

1.2 本文的主要工作

本文首次在云輔助計算模型下研究安全模式匹配協議，旨在設計出可以滿足智能環境中資源受限設備的安全協議.如圖1中的系統模型所示，數據提供商和用戶作為傳統兩方模式匹配協議中的2個參與方，分別提供數據庫信息和模式信息.除此之外，我還引入2個獨立的外部云服務器，其目的是輔助用戶并承擔其復雜的計算任務，從而提高用戶的效率.整個系統需要保證用戶在不泄露模式信息(數據供應商和云服務器均不獲取模式信息)的前提下查詢其模式在數據供應商的數據庫中出現的位置信息.

Fig. 1 The system model of two-cloud-assisted pattern matching圖1 雙服務器輔助模式匹配系統模型

考慮這樣一個場景，數據供應方是殺毒軟件企業，其擁有大規模的計算機病毒庫，而手機用戶希望在不泄露文件隱私的前提下實現本地的病毒檢測.鑒于手機用戶的計算資源受限，不可能與病毒庫執行大量的交互和操作，因此可以考慮引入云服務器來承擔手機用戶的計算任務，而用戶僅需要知道最終的檢測結果即可.鑒于云服務器的不可信性，手機用戶不希望將自己的文件信息以及最終的檢測結果暴露給云服務器或殺毒軟件企業，因此需要采取措施保障這些信息的隱私性.此外，病毒庫作為殺毒企業的隱私和資產因其重要性也必須受到保護，因此，所設計協議還需要保障病毒庫的信息不被泄露.對于以上各種安全需求，我們將在云輔助安全兩方計算模型中給出形式化的定義.

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

1) 首次在云輔助模型下研究安全模式匹配協議的高效構造，將模式持有方的計算外包至云服務器，所設計的協議適用于當前智能環境中資源受限的設備，比如手機等移動終端.此外，我們在雙服務器模型下給出了云輔助模式匹配協議功能函數的形式化描述.

2) 基于云輔助模式匹配協議功能函數的特性，我們基于0-秘密分享方案和茫然傳輸協議給出協議的具體構造.協議基本思想主要是使用0-秘密分享份額和隨機數表示一個位值，并結合OT協議將匹配問題等價轉化為0值的重構.為了減輕模式持有方的計算開銷，我們將模式信息盲化之后分享至2個獨立的云服務器.因此，原本應當在數據庫端和模式端執行的OT協議也轉移到數據庫端和云服務器之間.通過這種方式，云服務器取代了模式端的主要工作，這使得模式端的計算代價大大減少，其僅需要做一些簡單的異或操作，避免了OT協議中復雜的公鑰操作.假設云服務器和參與方是不合謀的，協議在半誠實敵手模型下是安全的.

3) 雙服務器輔助的安全模式匹配協議需要參與方之間執行4輪交互，模式端(即資源受限設備)僅需要執行少量異或操作.使用OT擴展技術，可以將數據庫端和云服務器之間的OT協議數目從O(nm)降至O(k)，其中n和m分別是數據庫和模式的長度，k是OT擴展協議的基礎OT數，k?nm.

2 基本知識和安全定義

2.1 茫然傳輸及其擴展協議

FOT功能函數

輸入：

① 發送方輸入2個有序值(x0,x1)∈{0，1}*；

② 接收方輸入一個選擇位σ∈(0,1).

輸出：

① 接收方輸出xσ；

② 發送方無輸出.

OT協議可以基于各種不同的困難問題構造而來，且其本身僅涉及少量的模冪運算，具有很高的效率.然而，作為工具運用到其他密碼學協議中時，往往需要數以萬計的OT協議，因此所有OT協議的效率往往成為影響其它密碼協議的瓶頸問題.鑒于此，Ishai等人[34]在2003年提出了OT擴展(oblivious transfer extension)技術，其可以運用較少量的OT協議實現大量OT的傳輸效果.比如可以使用128個基礎OT加上一些快速的對稱密鑰操作，實現106這么多OT協議的傳輸效果.因此對于提升使用大量OT的密碼協議的效率，OT擴展技術起到至關重要的作用.當前，基于OT擴展的隱私集合求交、茫然偽隨機計算等協議較之于其它實現技術有著更好的效率.本文也將使用OT擴展技術來改進云輔助模式匹配協議的效率.

2.2 計算不可區分性

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

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

2.3 安全性定義

本文的協議主要在云輔助安全兩方計算模型下考慮其安全性.該模型最早由Kamara等人[5-6]提出，其在標準的安全兩方計算場景中引入一個或多個云服務器輔助參與方完成計算.此外，他們還基于理想現實模擬范式給出形式化的安全性定義.然而，鑒于該模型規定云服務器與參與方之間不能合謀，因此上述安全性定義較之于標準安全兩方計算的理想現實模擬范式有所弱化，即只要求達到參與方“部分模擬”的程度即可.我們考慮的敵手主要是半誠實的，要求他們嚴格執行協議，但是允許其通過所窺探的消息推測出其他額外信息.此外，我們還假設需要2個云服務器的存在，且要求云服務器之間、云服務器和參與方之間、參與方之間是不能合謀的，這也正是Kamara等人[5-6]提出的云輔助安全兩方計算模型的基本假設.

現實世界執行.現實協議包含2個參與方實體和2個云服務器.每個參與方擁有自己的輸入信息，而云服務器沒有輸入.假設每個敵手僅能腐化一個參與方且不與其他敵手合謀.令OUTj表示所有誠實方的輸出，OUTi表示被腐化方在協議中的視圖，則用{REALi(n,x,y;r,z)}={OUTj:j∈H}∪OUTi表示協議π的第i個部分輸出，其中H表示所有誠實方的集合.

理想世界執行.理想世界中假設存在一個可信第三方，所有參與方將輸入發送給可信第三方并得到相應的輸出信息.同上所述，令OUTj表示所有誠實方從可信第三方得到的輸出信息，OUTi表示被腐化方自己的確定輸出，則理想世界執行中的第i個部分輸出可以表示為

{IDEALi(n,x,y;r,z)}=

{OUTj:j∈H}∪OUTi，

其中，H表示所有誠實方的集合.

下面我們給出云輔助安全兩方計算的安全性定義：

定義1.令f:{0,1}*×{0,1}*→{0,1}*是一個雙輸入單輸出的功能函數，π是一個真實協議.若協議π在雙服務器輔助模型下安全計算f，當且僅當，針對現實世界中每個非均勻概率多項式時間敵手(A1,A2,A3,A4)，總存在理想世界中的非均勻概率多項式模擬器{Simi}i∈[4]，對于2個參與方的輸入x和y，以及隨機帶r和輔助輸z，以及i∈[4]滿足：

{IDEALi(n,x,y;r,z)}n∈N≡
{REALi(n,x,y;r,z)}n∈N，

其中，參與方的輸入x,y∈{0,1}*，S=(S1S2S3S4)，Si=Simi(Ai)，r=(r1,r2,r3,r4)，n∈N是安全參數.

3 安全云輔助模式匹配協議

3.1 安全云輔助模式匹配功能函數

本文所考慮的云輔助符模式匹配功能函數FCPM中主要涉及4個參與方數據供應商DP、用戶U以及2個云服務器C1和C2，其中是DP和U分別持有數據庫t和模式信息p，而云服務器C1和C2作為輔助參與方代替用戶承擔大量的計算任務，從而減少用戶的計算代價.尤其是在當前智能環境中，用戶往往都是具有受限計算能力的設備，將大量計算任務外包至云服務器無疑能提高用戶的效率，同時不影響用戶享受智能場景帶來的便利.功能函數FCPM要求在云服務器的輔助下，用戶U能得到它的模式在數據供應商DP的數據庫中出現的位置信息，從而實現匹配的功能.

我們給出功能函數FCPM的形式化描述：

FCPM功能函數

輸入：

① 數據供應商DP輸入長度為n的二進制字符串t及整數m；

② 用戶U輸入長度為m的二進制字符串p以及整數n；

③ 云服務器C1和C2無輸入.

輸出：

① 用戶U輸出模式p在t中出現的位置；

② 數據供應商DP和云服務器均無輸出.

與此同時，功能函數FCPM要保證3個安全屬性：1)用戶U的模式信息對于數據供應商和云服務器均是保密的；2)數據供應商的數據信息對于云服務器是保密的；3)用戶U僅在匹配成功的情況下才能得到相應的位置信息，而當匹配失敗時，并不能得到關于數據供應商的數據的任何信息.

3.2 雙服務器模型下的安全模式匹配協議構造

在本節中，我們在雙服務器輔助模型下給出一個安全高效的云輔助模式匹配協議構造.協議的基本框架和思想主要源于Wei等人[21]基于OT和秘密分享方案構造的安全模式匹配協議.與之不同的是，我們引入了2個獨立的云服務器來降低資源受限用戶(如手機等移動智能設備)的計算開銷，從而使得協議更適用于當前的各種智能場景.此外，我們使用的秘密分享方案是一種特殊的0-秘密分享，即選取一定數量的隨機數使其異或值為0，這些隨機數即為分享份額.這種秘密分享方案更為簡單，僅涉及到異或操作，因此更加高效.

協議的流程大致分為3個階段：

1) 輸入盲化階段.用戶和數據供應商使用相同的隨機置換來改變各自的輸入值，這里的隨機置換可以是用戶選擇之后發給數據供應商，也可以是提前共享的.之后，用戶將盲化后的模式信息分成等長的2部分，并分別發送給2個云服務器C1和C2.這樣每個云服務器就獲得了部分盲化后的模式信息.

2) 茫然傳輸階段.茫然傳輸協議主要是在數據供應商和云服務器之間進行的，其中數據供應商作為發送方，2個云服務器分別扮演接收方的角色.首先，數據供應商根據其隨機置換后的輸入值，使用0-秘密分享方案表示每一個位信息.具體地，使用一個有序數對來表示輸入的每一個位值，這個數對中包含一個合法的0-秘密分享份額和一個隨機數.具體的順序取決于位是0或是1.之后，數據供應商和云服務器執行OT協議，其中數據供應商作為發送方輸入生成好的有序數對，云服務器作為接收方輸入接收到的部分盲化模式信息.最終2個云服務器分別接收到輸出，并針對每一個子串計算一個異或值發送給用戶.

3) 用戶輸出階段.用戶計算從2個云服務器接收到的數值的異或值，并根據異或值是否為0確定相應子串是否匹配成功，最終輸出結果.

協議具體表述為：

協議1.安全云輔助模式匹配協議πCPM.

輸入：數據供應商DP輸入一個長度為n的二進制字符串t和一個整數m，用戶U輸入一個長度為m的二進制字符串(模式)p和一個整數n，云服務器C1和C2沒有輸入；

輸出：用戶U輸出模式p在t中出現的位置.

協議：

步驟2. 此外，用戶U將所使用的隨機二進制串r發送給數據供應商DP，目的是讓數據供應商使用r針對t中的每一個m位長的子串做同樣的盲化操作(隨機串r也可以是U和DP提前共享的信息).

步驟3. 數據供應商DP使用秘密分享技術來表示每一個盲化后的m位長子串.核心技術是使用一對數值來表示m位長子串的每個位值，這對數值需要滿足其中之一是合法的0-秘密分享份額，另一個是一個隨機值，且合法的秘密分享份額在數對中的位置要與該位值信息對應(即如果位為0，則合法份額在第1位；若位為1，則合法份額在第2位).具體表示方法為：

因為數據供應商的輸入是n位長的字符串t，其中包含n-m+1個m位長的子串，因此DP需要對每一個字串均做上述操作，即共生成m(n-m+1)個有序數對.這些根據子串生成的有序數對會被用于為后序茫然傳輸協議中，作為發送方(即數據供應商)的輸入信息.

② 否則輸出⊥，表示匹配失敗.

3.3 協議正確性

協議1的正確性意味著在協議成功運行之后，用戶U最終一定得到正確的結果.具體而言，如果在數據供應商的數據t中存在與模式串相等的子串，則用戶一定會輸出相同子串開始的位置；反之，若t中無相同子串，則用戶輸出⊥表示匹配失敗.首先需要說明的是，用戶U和數據供應商DP使用相同的置換信息對其各自的輸入作了相同的處理，因此如果存在子串和模式串相同，則置換之后的值依然相等，因此并不影響匹配的正確性.我們以上2種情況分別闡述，以此說明協議的正確性：

② 如果匹配失敗，則表明t中所有n-m+1個m位長子串均與模式p不相等.不失一般性，考慮從t中第1個位開始的m位長子串，則其中必然存在至少一個位信息與模式p中相對應的比特信息不同，不妨設該位置為j，即tj≠pj.因此，在茫然傳輸協議中，在第j個位置上云服務器C1或C2得到的一定是某個隨機數，而不是數據供應商選擇的對于0值的合法秘密分享份額.這樣，用戶U最終求得的異或值必然不是0，而是某個隨機的結果.這也就表明該子串與模式匹配失敗.

綜上所述，用戶U在匹配成功和失敗情況下均能輸出正確的結果，因此協議正確性滿足.

3.4 協議安全性

在給出協議安全性的形式化證明之前，我們先從直觀上分析一下上述協議的安全性.首先我們假設云服務器之間、以及云服務器與參與方之間是不能合謀的，這一假設就保證了用戶的模式信息對于數據提供商以及云服務器是保密的.這其中的關鍵點就在于用戶將隨機置換和最終的盲化結果分別發送給數據供應商和云服務器，只要假設他們不合謀，用戶的輸入隱私性就會得以保證.此外，云服務器的不合謀也使得用戶的輸出隱私性得到保障.因為如果2個云服務器共享最終得到的異或值，通過判斷結果是否為0就可以推斷出匹配的結果.再考慮數據供應商的輸入隱私問題，鑒于OT協議的安全性，云服務器和用戶僅能在匹配成功的情況下得到相應的子串相等信息.而對于那些匹配不成功的子串，任何信息都不會泄露.下面我們根據安全性定義1給出上述云輔助模式匹配協議的形式化安全性證明：

定理1.假設茫然傳輸協議在半誠實敵手模型下是安全的，且2個云服務器之間以及云服務器與參與方之間是不合謀的，則根據定義1，協議πCPM在云輔助安全兩方計算模型下針對半誠實敵手安全計算功能函數FCPM.

證明. 我們在雙服務器輔助的安全兩方計算模型下證明上述協議的安全性.需要強調的是，我們使用混合模型的證明機制，即云輔助模式匹配協議中使用到的茫然傳輸協議由理想功能函數FOT實現.假設協議中涉及到的4個參與方DP,U,C1和C2分別被4個相互獨立的現實敵手A1,A2,A3和A4控制，則我們構造4個獨立的理想世界模擬器S1,S2,S3和S4，執行模擬過程：

{IDEAL1(n,x,y;r,z)}n∈N≡
{REAL1(n,x,y;r,z)}n∈N.

從協議πCPM中可以看出敵手A1在協議中的視圖主要包含在OT協議中從云服務器那里接收到的值.而模擬器在模擬的過程中并不知道這些值是什么，因此選擇了2個隨機二進制串作為接收方的輸入.這也是理想世界模擬過程與現實協議執行中唯一的差別.鑒于我們所使用的OT協議針對半誠實敵手是安全的，因此發送方(即模擬器)對于接收方(即云服務器)的輸入是計算不可區分的.這一安全特性就保證了模擬器S1的模擬過程與真實協議執行是不可區分的.

{IDEAL2(n,x,y;r,z)}n∈N≡
{REAL2(n,x,y;r,z)}n∈N.

以上2個分布的唯一區別是模擬器隨機選擇了本應從云服務器那里接收到的信息，而在現實協議中敵手是直接從云服務器處接收到這些值.但是，因為模擬器知道最終的匹配結果，因此它隨機選取的這些值和敵手接收到的值所能推導出的信息是等價的.換言之，針對匹配成功的情況，最終2個值的異或值為0；反之如果匹配失敗，則2個值的異或值是隨機的.因此，上述模擬過程和現實協議計算不可區分.

{IDEAL3(n,x,y;r,z)}n∈N≡
{REAL3(n,x,y;r,z)}n∈N.

4) 模擬器S4模擬腐化云服務器C2的現實敵手A4，情況同上.

綜上所述，我們完成對定理1的證明.

3.5 協議效率分析與比較

協議的效率一般從輪復雜度、計算復雜度和通信復雜度3方面考慮.下面我們就這3方面作具體闡述，并與相關工作進行效率比較.

1) 輪復雜度.我們所構造的雙服務器輔助模式匹配協議共需要4輪交互.其中在第1輪中，用戶將盲化后的模式信息拆分并發送給云服務器，此外，還需將盲化使用的隨機置換發送給數據庫端.之后的第2輪和第3輪主要體現在OT協議中，因為半誠實模型下的OT協議是一個2輪協議.協議的第4輪中云服務器分別將計算后的數值發送給用戶，用戶計算并最終得到輸出.

2) 計算復雜度.協議的計算復雜度指的是參與方本地的計算量，主要涉及到對稱操作(如Hash，異或等)和非對稱操作(如模冪運算)，其中對稱操作速度快，而非對稱操作速度慢、代價大，因此經常用非對稱操作的數量來衡量整個協議的計算復雜度.從協議描述中可以看出，資源受限的用戶僅針對其輸入模式做簡單的異或操作.而復雜的非對稱操作主要集中在數據庫端和云服務器之間執行的OT協議中.假設用戶的模式長度為m，數據庫端的輸入長度為n，則需要對所有的n-m+1個子串分別執行m次OT協議，因此所需OT協議的總數目為n(n-m+1).我們可以使用OT擴展技術減少OT協議的數目，即僅需要執行k次基礎OT的數目，并結合一些Hash操作，就能實現上述大量OT的效果.這里的k為安全參數，一般而言，執行128次基礎OT便可以實現106個OT協議的效果.

3) 通信復雜度.通信復雜度指的是參與方之間發送和接收的信息數.首先考慮資源受限的用戶，其共發送m位的模式信息給云服務器，并從云服務器那里接收到2(n-m+1)個字符串(即生成0-秘密分享的份額或某一隨機數，長度為選定的某個安全參數s).此外，在OT協議中，每一次OT執行中接收方和發送方共需要發送4個群元素(各自發送2個)，因此所有的OT協議共需要交換O(nm)個數量級的群元素.

在表1中我們給出文中所構造協議與相關模式匹配協議的比較結果.具體的，我們從協議的輪數、計算復雜度、通信復雜度以及協議模型4個方面對協議進行效率比較.其中計算復雜度和通信復雜度均分為用戶量和協議總量2個部分，以此來說明我們協議中用戶的優勢.此外，表1中n和m分別是模式匹配協議中2個參與方的輸入長度，k是使用OT擴展協議的基礎OT數目.

首先，從協議模型來看，文獻[19,21]均在標準模型下設計協議，而我們的協議是在2個云服務器輔助模型下構造的，適用于資源受限設備存在的智能環境.考慮協議輪數，協議[19]考慮惡意敵手，因此需要6輪交互，而協議[21]和我們的協議均考慮半誠實敵手，因此輪數有所減少，但是均為常數輪.關于協議的計算復雜度，我們從用戶和協議總體的計算量2方面進行分析.因為引入了外部云服務器，因此我們協議中的用戶僅需要計算少量的XOR操作，而其它協議中的用戶(即模式方)均需要執行OT協議，因此需要計算大量的模冪運算.假設，n和m分別是模式匹配協議中2個參與方的輸入長度，協議[19]需要計算O(nm)數量級的模冪運算，而協議[21]使用OT擴展技術可以將計算量降至O(k)數量級(k是OT擴展協議的基礎OT數目，遠小于nm).從協議整體計算復雜度而言，因為我們的協議也基于OT擴展技術，因此計算復雜度與協議[21]一樣均為O(k).最后，考慮協議的通信復雜度(即發送群元素的數量)，所有協議的總體通信量均為O(nm).但是，我們協議中的用戶僅需要O(n-m)數量級的通信復雜度，因此更適用于手機等資源受限設備存在的智能環境應用中.

Table 1 Efficiency Comparison表1 協議效率比較

Notes：√ means the protocol is in the cloud-assisted model; × means the protocol is in the standard model.

4 結束語

本文主要考慮適用于智能環境下的安全模式匹配協議設計，首次在云輔助安全兩方計算模型下構造了一個高效的模式匹配協議.我們在傳統模式匹配協議中引入2個獨立的云服務器承擔參與方的部分計算任務，從而使得智能環境中某些資源受限設備的效率得以提升.協議主要基于茫然傳輸和0-秘密分享技術，假設云服務器和用戶之間是不合謀的，則我們的協議在半誠實敵手模型下是安全的.協議共需要4輪交互，總體通信復雜度為O(nm)，通過使用OT擴展技術其計算復雜度可以由O(nm)降至O(k)，其中n和m是參與方的輸入長度，k?nm是基礎OT的數量.考慮資源受限的用戶端，其僅需要執行少量的XOR操作，且僅需要O(n-m)數量級的通信量，因此協議非常適用于手機等之類的設備.