喻朝新 雷琳琳 李丹 朱輝輝 凌國瑋

摘 要：Ghosh等在NDSS 2023上首次提出了一種去中心化環(huán)境下用戶建立信任機(jī)制的隱私保護(hù)認(rèn)證人求交（private certifier intersection， PCI）協(xié)議。在PCI協(xié)議中，持有不同證書的雙方能夠計(jì)算出公共的認(rèn)證人即證書中心（certificate authority， CA）集合，同時(shí)以隱私保護(hù)的方式驗(yàn)證這些認(rèn)證人頒發(fā)的證書是否有效。PCI協(xié)議可用于解決去中心化環(huán)境下雙方用戶在沒有先驗(yàn)的情況下建立相互信任機(jī)制的問題，但采用了復(fù)雜的安全多方計(jì)算方法導(dǎo)致效率不高，而且要求參與雙方使用相同的簽名算法，這在實(shí)際應(yīng)用中是不合理的。針對這些問題，基于可信執(zhí)行環(huán)境（trusted execution environment， TEE）提出一個(gè)新的PCI協(xié)議。所提協(xié)議采用TEE完成認(rèn)證人求交過程且支持參與雙方采用任意的數(shù)字簽名算法生成證書，更具有實(shí)用性。實(shí)驗(yàn)結(jié)果表明所提協(xié)議在效率上明顯優(yōu)于Ghosh等的PCI協(xié)議。

關(guān)鍵詞：隱私保護(hù)認(rèn)證人求交；可信執(zhí)行環(huán)境；簽名；去中心化

中圖分類號：TP309

文獻(xiàn)標(biāo)志碼：A

在傳統(tǒng)Web2.0中，個(gè)人隱私保護(hù)已成為人們?nèi)找骊P(guān)注的核心問題［1-3］。用戶依賴有限的身份和服務(wù)提供商以及認(rèn)證機(jī)構(gòu)實(shí)現(xiàn)可信交互。然而，傳統(tǒng)的證書認(rèn)證存在著中心化、高費(fèi)用、弱隱私性和高延遲等不足。

去中心化的Web3.0旨在增強(qiáng)用戶自主創(chuàng)建、更新和選擇性共享身份數(shù)據(jù)的能力，從而替換對集中式服務(wù)提供商的依賴，使用戶能夠證明關(guān)于自身的某個(gè)資質(zhì)（或聲明），而無需依賴集中式的聯(lián)合身份提供商或權(quán)威可信認(rèn)證人即證書中心（certificate authority， CA）集合［4］。

構(gòu)建去中心化CA的一個(gè)挑戰(zhàn)是如何在不同的用戶之間建立信任機(jī)制。在去中心化系統(tǒng)中，證書的頒發(fā)是由多個(gè)CA完成［5-6］。若兩個(gè)用戶存在相同的CA，基于對CA的信任，雙方能夠成功建立起一個(gè)信任關(guān)系［7］。傳統(tǒng)的解決方法是使用隱私保護(hù)集合求交（private set intersection，PSI）協(xié)議［8］進(jìn)行雙方CA集合的求交。PSI協(xié)議是一種在現(xiàn)實(shí)應(yīng)用中被廣泛使用的安全多方計(jì)算（multi-party computation， MPC）原語。在PSI協(xié)議中，參與方分別為發(fā)送者與接收者。協(xié)議開始時(shí)，發(fā)送者與接收者輸入各自的私有集合。當(dāng)PSI協(xié)議執(zhí)行完成時(shí)，接收者可以得到雙方集合的交集。在雙向PSI協(xié)議中，雙方都將得到交集?，F(xiàn)有的高效PSI協(xié)議［9-11］幾乎都是基于不經(jīng)意傳輸擴(kuò)展（oblivious transfer extension， OTE）［10］或者向量不經(jīng)意線性評估（vector oblivious linear evaluation， VOLE）［12］構(gòu)造的，其中最有代表性的高效PSI協(xié)議是KKRT協(xié)議［11］以及RR協(xié)議［13］。但是，在去中心化系統(tǒng)中，沒有一個(gè)中央機(jī)構(gòu)來管理和驗(yàn)證所有證書的合法性。因此，敵手可以偽造CA集合作為輸入從而獲得誠實(shí)參與方的全部或部分CA［14］。

針對以上問題，GHOSH等［15］在2023年信息安全國際頂級會議NDSS上提出隱私保護(hù)認(rèn)證人求交（private certifier intersection， PCI）協(xié)議概念并說明了該協(xié)議能夠很好地保護(hù)Web3.0中用戶的隱私。PCI協(xié)議的輸入是雙方各自持有的證書以及頒發(fā)這些證書的認(rèn)證人。PCI協(xié)議能夠識別出雙方的公共認(rèn)證人集合，同時(shí)驗(yàn)證這些認(rèn)證人頒發(fā)的證書是否有效，以防止惡意的參與方輸入無效的證書和認(rèn)證人。通過PCI，持有證書的雙方可以在互不信任的情況下建立信任基礎(chǔ)。PCI的提出為Web3.0中的用戶提供了更強(qiáng)的隱私保護(hù)機(jī)制。

分析GHOSH等［15］的PCI協(xié)議，不難發(fā)現(xiàn)存在以下問題：

首先，在他們的PCI協(xié)議中，參與雙方在MPC框架下完成證書的驗(yàn)簽與求交，這種方法帶來了巨大的計(jì)算開銷，輸入大小僅為1 000的PCI協(xié)議在局域網(wǎng)需要1.5 h以上。

其次，在現(xiàn)實(shí)應(yīng)用中，不同的認(rèn)證人往往會采用不同的數(shù)字簽名算法（由認(rèn)證人自身決定）。但是GHOSH等［15］的協(xié)議要求所有認(rèn)證人都采用相同的簽名算法。

在本文中，我們提出一種新的PCI協(xié)議。所提協(xié)議不僅能支持認(rèn)證人使用不同的簽名算法，而且相較于原始PCI協(xié)議［15］具有較大的性能優(yōu)勢，具體如下：

1）本文采用可信執(zhí)行環(huán)境（trusted execution environment，TEE）［16］來規(guī)避計(jì)算開銷極大的MPC驗(yàn)簽過程，并基于現(xiàn)有抗惡意敵手的PSI協(xié)議［13］構(gòu)造高效安全的PCI協(xié)議。

2）本文所構(gòu)造的PCI協(xié)議支持認(rèn)證人使用任意的簽名算法，更符合現(xiàn)實(shí)應(yīng)用需求。認(rèn)證人只需將所采用的驗(yàn)簽算法嵌入TEE即可。

3）本文通過實(shí)驗(yàn)與文獻(xiàn)［15］進(jìn)行效率對比。實(shí)驗(yàn)結(jié)果表明，所提PCI協(xié)議在輸入集合大小為1 000時(shí)僅需1 s左右即可完成，相較于原始PCI協(xié)議具有較大的性能優(yōu)勢。同時(shí)，由于所提PCI協(xié)議支持不同的數(shù)字簽名算法，本文還給出了使用ECDSA［17］、RSA［18］、SM2［19］這3種簽名算法的實(shí)驗(yàn)結(jié)果。

1 預(yù)備知識

1.1 符號定義

本文令P1與P2分別代表PCI協(xié)議中的兩個(gè)參與方。雙方PCI協(xié)議的輸入大小分別為N1與N2。令κ為計(jì)算安全參數(shù)，λ為統(tǒng)計(jì)安全參數(shù)。［a，b］表示從a到b的所有整數(shù)數(shù)值。［b］表示從1到b的所有整數(shù)?！碅，B〉表示2個(gè)向量A與B的內(nèi)積。對于集合S，s←S指s是從S隨機(jī)選取元素。V（pk，σ，m）=1表示對于任意的一個(gè)數(shù)字簽名算法的驗(yàn)簽算法V，輸入公鑰pk、簽名消息m、數(shù)字簽名σ，驗(yàn)簽通過。令H1：{0，1}*→{0，1}κ，H2：{0，1}*→{0，1}κ/2。

1.2 可信執(zhí)行環(huán)境

TEE［16］是一種安全計(jì)算環(huán)境，用于保護(hù)敏感數(shù)據(jù)和代碼免受惡意軟件和攻擊者的侵害，保證程序初始狀態(tài)和運(yùn)行時(shí)的機(jī)密性、完整性。TEE提供了一種隔離機(jī)制，使得TEE內(nèi)部的代碼和數(shù)據(jù)能夠與外部環(huán)境隔離開來，使得TEE外部的軟硬件均無法獲得其內(nèi)部的機(jī)密信息。常見的可信執(zhí)行環(huán)境包括硬件級別的Enclave（如Intel SGX）和軟件級別的沙箱（如Google Chrome的沙箱）。TEE的安全性建立在多個(gè)方面的基礎(chǔ)上，其中最重要的是隔離機(jī)制和加密保護(hù)。隔離機(jī)制確保敏感數(shù)據(jù)和代碼只能被授權(quán)的程序和用戶訪問；而加密保護(hù)則用于保護(hù)數(shù)據(jù)的機(jī)密性和完整性。為了實(shí)現(xiàn)這些安全特性，TEE通常需要依賴于硬件支持和操作系統(tǒng)的協(xié)作。

TEE通常由特殊的硬件和安全操作系統(tǒng)組成。這些硬件通常包括安全處理器和特殊的存儲器。在TEE中，所有執(zhí)行代碼和數(shù)據(jù)都必須經(jīng)過認(rèn)證和加密，只有經(jīng)過身份驗(yàn)證和授權(quán)的用戶才能訪問TEE中的數(shù)據(jù)和功能。TEE還支持遠(yuǎn)程認(rèn)證和安全通信，使得與TEE進(jìn)行通信的其他設(shè)備可以驗(yàn)證TEE的身份和確保通信的安全性。在TEE中，所有執(zhí)行的代碼和數(shù)據(jù)都必須滿足高度安全的要求，并且必須經(jīng)過嚴(yán)格的測試和驗(yàn)證，以確保沒有漏洞和后門。

1.3 向量不經(jīng)意線性評估

向量不經(jīng)意線性評估（vector oblivious linear evaluation， VOLE）［12］是構(gòu)造高效MPC協(xié)議的重要基礎(chǔ)組件。VOLE在MPC協(xié)議中起到的作用一般與著名的不經(jīng)意傳輸擴(kuò)展（oblivious transfer extension， OTE）協(xié)議等價(jià)［11］。在VOLE協(xié)議中有2個(gè)參與方P1與P2，當(dāng)協(xié)議結(jié)束時(shí)，P1得到向量A，C，P2得到向量B、標(biāo)量Δ，滿足C=ΔA+B。目前高效的VOLE協(xié)議是由COUTEAU等［12］提出的Silver協(xié)議。本文所提的PCI協(xié)議也是基于Silver協(xié)議生成的VOLE向量。

1.4 不經(jīng)意鍵值對存儲

不經(jīng)意鍵值對存儲（oblivious key-value stores，OKVS）［12， 20-21］是由PINKAS等［21］提出的一種新型的鍵值對數(shù)據(jù)結(jié)構(gòu)。設(shè)計(jì)它的初衷是為了替換PSI協(xié)議中的Cuckoo Hashing［22］，從而得到高效抗惡意敵手的PSI協(xié)議。此外，相比于Cuckoo Hashing，它需要更少的內(nèi)存開銷。OKVS按如下的方式被定義為一種鍵值對數(shù)據(jù)結(jié)構(gòu)。

Encode （（x1，y1），…，（xn ，yn ），r）：給定鍵值對集合{（x1，y1），…，（xn，yn）}與隨機(jī)數(shù)r←{0，1}κ，輸出P∈{0，1}m，其中xi∈{0，1}，yi∈{0，1}，m≤1.3n。

Decode （P，xi ，r）：給定P，xi，r，返回yi。若存在row （xi ，r）→＼{0，1＼}m使得

Decode （P，xi ，r）=〈P，row （xi ，r）〉（1）

成立，則稱OKVS為一個(gè)線性O(shè)KVS。令P是一個(gè)線性O(shè)KVS，設(shè)L是一個(gè)線性變換，且P=P′+P″，則線性O(shè)KVSP滿足以下性質(zhì)：

Decode （L（P），x，r）=L（Decode （P，x，r））

Decode （P，x，r）=Decode （P′，x，r）+Decode （P″，x，r）（2）

2 概念模型與協(xié)議模型

2.1 PCI概念模型

PCI是GHOSH等［15］提出的一種新的密碼學(xué)原語。PCI概念模型如圖1所示。參與方P1與P2擁有不同資質(zhì)對應(yīng)的證書以及CA。當(dāng)Web3.0中的兩方用戶想要在去中心化的CA下建立信任機(jī)制時(shí)，雙方以各自證書以及CA作為PCI協(xié)議的輸入，最終雙方各自得到一個(gè)共有的CA交集以及CA對應(yīng)的資質(zhì)，且不在交集內(nèi)的CA在求交驗(yàn)證過程中完全不會暴漏。如果泄露了不在交集內(nèi)的CA，則會給Web3.0中的用戶造成額外的隱私泄露問題。在圖1中，mi和m′i不一定是同一種資質(zhì)，只要用戶雙方就某個(gè)相同或不同資質(zhì)具有共同的CA達(dá)成一致即可。

2.2 PCI協(xié)議定義

在本協(xié)議中，參與方Pi，i∈{1，2}分別擁有私密輸入pi，1={pki，j，σi，j，mi，j}與公開輸入pi，2={m′i，j}，其中：pki，j為數(shù)字簽名σi，j執(zhí)行驗(yàn)簽算法所需要的公鑰（代表驗(yàn)證人身份）；mi，j為σi，j所對應(yīng)的簽名消息（在PCI協(xié)議中為參與方Pi想證明的某個(gè)資質(zhì)或?qū)傩裕?；pi，2為Pi想要證明的所有資質(zhì)或?qū)傩约稀?/p>

當(dāng)PCI協(xié)議執(zhí)行結(jié)束時(shí)，Pi得到輸出：

I={I1={pk′j}，Ii，2={m′k}（3）

在輸出I1中，滿足任意pk′j∈{{pk1，j}∩{pk2，j}}且存在V（pk′j，σ1，j ，m1，j）=V（pk′j，σ2，j，m2，j）=1成立。在Ii，2中，對于P1，任意m′k∈p2，2且存在pk′j∈I1使得在p2，1中存在V（pk′j，σ2，j ，m′k）=1。對于P2，滿足任意m′k∈p1，2且存在pk′j∈I1使得在p1，1中存在V（pk′j，σ2，j ，m′k）=1。

簡單的說，在PCI協(xié)議中，Pi會得到能夠讓數(shù)字簽名驗(yàn)簽通過的公鑰交集（通過該公鑰交集確定認(rèn)證人的身份）。同時(shí)，Pi也會得到對方的有效資質(zhì)（被雙方共同信任的認(rèn)證人所認(rèn)證）。

2.3 安全性定義

在理想-現(xiàn)實(shí)范式下［23］，敵手可以攻破P1與P2的任意一方。為了便于描述，在此處P1為惡意方（被敵手所攻破的一方），P2為誠實(shí)方。

PCI的理想功能（FPCI）如下所示。

1） 參與方Pi輸入pi，1={pki，j，σi，j，mi，j}與 pi，2={m′i，j}。P2直接向FPCI提供它的正確輸入，P1的輸入由模擬器S提供。

2） FPCI計(jì)算PCI協(xié)議的輸出I={I1，Ii，2}。

3） FPCI發(fā)送{I={I1，I1，2}，N1，p1，2}給模擬器S。

4） 若S要求FPCI中止協(xié)議，則FPCI協(xié)議終止。

5） 若S不要求FPCI終止，則FPCI分別發(fā)送I={I1，Ii，2}，N1，N2給P1與P2。

現(xiàn)實(shí)世界。P2從環(huán)境Z中得到自身的輸入，并誠實(shí)地執(zhí)行PCI協(xié)議。敵手A控制P1與P2和Z進(jìn)行交互。Z為P2提供輸入的同時(shí)也會得到P2的輸出。

理想世界。P2從環(huán)境Z中得到自身的輸入，并作為FPCI的輸入。模擬器S代表P1向FPCI發(fā)送其輸入，并從FPCI得到對應(yīng)的輸出。S也會與Z進(jìn)行交互，旨在使理想世界中的交集與真實(shí)世界中的交集計(jì)算不可區(qū)分。Z為P2提供輸入，并與模擬器S進(jìn)行交互，也會得到P2的輸出。

對于一個(gè)任意的PCI協(xié)議，給定任意的敵手A，環(huán)境Z，模擬器S，可以定義以下隨機(jī)變量。

real A，Z 表示Z與敵手A在真實(shí)世界中交互執(zhí)行PCI協(xié)議所能得到的一切視圖，包括其輸入、輸出、過程中收到的消息、隨機(jī)帶。

idealA，Z表示Z與模擬器S在理想世界中交互執(zhí)行PCI協(xié)議所能得到的一切視圖，包括其輸入、輸出、過程中收到的消息、隨機(jī)帶。

定義1（安全的PCI協(xié)議） 給定安全參數(shù)κ，對于任意的概率多項(xiàng)式敵手A與概率多項(xiàng)式環(huán)境Z，存在一個(gè)模擬器S使得

3 基于TEE的高效PCI協(xié)議

3.1 研究動(dòng)機(jī)

在實(shí)際應(yīng)用中，不同用戶和應(yīng)用場景的需求是不一樣的，從而導(dǎo)致涉及的簽名算法、證書類型以及性能要求也各自不同。例如，個(gè)人筆記本電腦中存有基于多種簽名算法的數(shù)字證書，如圖2和圖3所示。此外，隨著Web3.0中數(shù)字身份的日益普及和信息交流的頻率不斷增加，確保隱私保護(hù)認(rèn)證人求交的速度變得尤為重要。在通信雙方頻繁進(jìn)行認(rèn)證人求交的背景下，證書數(shù)量的增加可能會導(dǎo)致求交過程變得較為緩慢，甚至可能造成敏感信息泄露的風(fēng)險(xiǎn)。因此，設(shè)計(jì)出一種能夠支持靈活簽名算法且安全高效的PCI協(xié)議以滿足這些多樣化的需求，變得尤為迫切和重要。

3.2 協(xié)議框架

本文協(xié)議框架如圖4所示。P1和P2以各自認(rèn)證人即公鑰pk、證書σ、資質(zhì)m為輸入，在TEE中執(zhí)行證書的驗(yàn)簽過程。將驗(yàn)簽算法通過的認(rèn)證人與聲明存入TEE的臨時(shí)安全內(nèi)存M1和M2中。雙方以各自認(rèn)證人集合X與Y為輸入執(zhí)行一個(gè)抗惡意敵手的PSI即VOLE協(xié)議，直到P2生成掩碼集合Y′。P2將掩碼集合Y′輸入TEE。P1將認(rèn)證人集合X：={x}輸入TEE，并在TEE中進(jìn)行掩碼集合X′的生成。然后TEE判斷x∈X′∩Y′是否成立。若成立，則進(jìn)一步判斷x是否在驗(yàn)簽算法通過的臨時(shí)安全內(nèi)存中。若x存在于臨時(shí)安全內(nèi)存中，則TEE將求得的交集列表{I1，I1，2}發(fā)送給P1，{I1，I2，2}發(fā)送給P2。

此外，在協(xié)議框架方面，我們采用TEE代替原始PCI協(xié)議的MPC框架［15］，從而實(shí)現(xiàn)高效、安全、靈活性高的PCI協(xié)議。

3.3 協(xié)議構(gòu)造難點(diǎn)

構(gòu)造PCI協(xié)議的關(guān)鍵是如何在沒有可信第三方情況下安全地執(zhí)行驗(yàn)簽算法。如果能夠高效且安全地完成雙方證書的驗(yàn)簽，那么就能夠結(jié)合一個(gè)高效且抗惡意敵手的PSI協(xié)議，成功構(gòu)造出PCI協(xié)議。那么該如何替代計(jì)算開銷較大的MPC驗(yàn)簽過程？以下有一種看似合理的簡單結(jié)合方法：首先雙方借助TEE執(zhí)行合法驗(yàn)簽過濾錯(cuò)誤輸入，然后執(zhí)行一個(gè)抗惡意敵手的PSI協(xié)議。

但是，上述方法存在以下問題：TEE執(zhí)行簽名流程結(jié)束后，參與方Pi仍然無法過濾掉對方的錯(cuò)誤輸入。因?yàn)镻i無法獲取對方的簽名結(jié)果，畢竟有些通過驗(yàn)簽的合法輸入不一定在交集中。如何克服這一問題是將TEE與惡意PSI協(xié)議結(jié)合形成PCI協(xié)議的關(guān)鍵。因此，在新的PCI協(xié)議中，我們必須更加細(xì)致地設(shè)計(jì)PCI協(xié)議的具體流程以保證參與方Pi隱私不會泄露。

本文結(jié)合TEE與現(xiàn)今高效的惡意PSI協(xié)議［13］構(gòu)造一個(gè)新的安全高效的PCI協(xié)議。該協(xié)議不僅不會有以上樸素的結(jié)合方法帶來的隱私泄露問題，而且相較于GHOSH等的PCI協(xié)議［15］具有效率更高的優(yōu)勢。此外，因?yàn)槊總€(gè)用戶選擇的證書頒發(fā)機(jī)構(gòu)采用的簽名算法是不統(tǒng)一的，該協(xié)議支持認(rèn)證人在一次PCI協(xié)議中使用任意簽名算法，更加符合現(xiàn)實(shí)Web3.0中的應(yīng)用場景。

3.4 協(xié)議概述與技術(shù)細(xì)節(jié)

為了用戶雙方能夠安全且成功地執(zhí)行PCI流程，分別介紹所使用的惡意PSI協(xié)議［13］以及TEE的具體功能。

3.4.1 PSI協(xié)議

首先，參與方Pi執(zhí)行一個(gè)VOLE協(xié)議［12］，P1得到向量A，C；P2得到向量B與標(biāo)量Δ滿足C=ΔA+B。然后，設(shè)向量P是{x，H2（x）}的線性O(shè)KVS。P1發(fā)送A′：=P+A給P2，P2隨后計(jì)算B′=B+ΔA′。因此，P1與P2安全地將VOLE輸出（A，B，C，Δ）轉(zhuǎn)化為（P，B′，C，Δ），滿足C=B′－ΔP。利用線性O(shè)KVS的性質(zhì)，此處有

Decode （C，x）=Decode （B′，x）-ΔDecode （P，x）

Decode （C，x）=Decode （B′，x）-ΔH2（x）（5）

成立。因此，上述等式的左右兩式即為該P(yáng)SI協(xié)議的掩碼。P1可計(jì)算X′：={Decode（C，x）|x∈X} ，P2可計(jì)算Y′={Decode（B′，y）-ΔH2（y）|y∈Y}。X′∩Y′即可計(jì)算出雙方的交集。

3.4.2 TEE

令TEE支持以下3個(gè)安全算法，這些安全算法由TEE在安全內(nèi)存中執(zhí)行，保證其算法的正確性、隱私性。在TEE中定義兩塊隔離的安全內(nèi)存M1、M2分別作為參與方P1與P2調(diào)用執(zhí)行TEE算法時(shí)所執(zhí)行使用的內(nèi)存空間。即便是Pi也只能通過安全算法才能獲取Mi中的臨時(shí)計(jì)算數(shù)據(jù)。

1）TEEV（Pi：{（pkj，σj，mj）}，{m′j} ）：參與方Pi輸入認(rèn)證人公鑰pkj，數(shù)字簽名σj，參與方資質(zhì)mj。在安全內(nèi)存Mi中以（pk，m）的形式維護(hù)表Ti。若滿足V（pkj，σj，mj）=1且mj∈{m′j}，則更新列表Ti：=Ti∪{（pkj，mj）}，否則說明Pi偽造了非法輸入，PCI協(xié)議中斷。

2）TEEQ （P1：X，C，r;P2：Y′）：P1輸入認(rèn)證人集合X，VOLE協(xié)議輸出的C，隨機(jī)值r∈{0，1}κ；P2輸入集合Y′：={{0，1}κ}。初始化輸出集合I={I1，Ii，2}，i∈{1，2}。對于每一個(gè)x∈X，算法判斷H1（Decode （C，x，r））∈Y′，x∈T1，x∈T2是否均成立。若成立，則I1：=I1∪{x}，I1，2：=I1，2∪{m″}，I2，2：=I2，2∪{m′}，其中：m′為T1中x對應(yīng)的資質(zhì)；m″為T2中x對應(yīng)的資質(zhì)。TEE向P1輸出{I1，I1，2}，向P2輸出{I1，I2，2}。此外，若H1（Decode （C，x，r））∈Y′成立但xTi，可說明Pi偽造輸入x，PCI協(xié)議中斷。

3）TEEF（P1，P2）：參與方P1與P2要求TEE對安全內(nèi)存M1，M2進(jìn)行內(nèi)存釋放。

TEEQ與TEEF 必須由雙方同時(shí)調(diào)用，TEEQ 用于在TEE中得到PCI協(xié)議的輸出。同時(shí)，TEEV與TEEQ 還能檢測參與方是否使用了惡意的輸入。此外，TEEQ算法執(zhí)行結(jié)束（即PCI協(xié)議結(jié)束）后，雙方才會共同調(diào)用TEEF進(jìn)行安全內(nèi)存的釋放，即TEEF必須兩方同時(shí)釋放。這避免了惡意參與方提前釋放安全內(nèi)存。

3.5 協(xié)議構(gòu)造

參與方為P1與P2，它們的私有輸入分別為p1，1={xj，σ1，j，m1，j}與p2，1={yj，σ2，j，m2，j}，公開輸入分別為p1，2={m′2，j}與p2，2={m′2，j}。本文所提PCI協(xié)議的正式描述如協(xié)議1所示。

協(xié)議1：基于TEE的高效PCI協(xié)議

輸入：P1：p1，1；P2：p2，1

輸出：P1：{I1，I1，2}；P2：{I1，I2，2}

公共：P1：p1，2={m′2，j}；P2：p2，2={m′2，j}

//簽名校驗(yàn)階段

1： P1調(diào)用T1←TEEV （p1，1 ，p1，2 ），注意T1保存于安全內(nèi)存M1，且Pi無法訪問。

2： P2調(diào)用T2←TEEV （p2，1 ，p2，2 ），注意T2保存于安全內(nèi)存M2，且Pi無法訪問。

//計(jì)算掩碼階段

3： P1選擇隨機(jī)數(shù)r，r′←{0，1}κ，計(jì)算線性O(shè)KVS：P：=Encode （L，r），其中L=（xj，H2（xj，r′））。

4： P1與P2執(zhí)行一個(gè)VOLE協(xié)議，P1得到向量A，C；P2得到向量B與標(biāo)量Δ滿足

C=ΔA+B。

5： P1發(fā)送A′：=P+A給P2，P2隨后計(jì)算B′=B+ΔA′。

6： P2計(jì)算Y′={ H1（Decode （B′，yj ）-ΔH2（yj ））}。

//安全求交階段

7： P1輸入{xj}，C，r，P2輸入Y′，共同調(diào)用{ I1，Ii，2} ←TEEQ （{ xj}，C，r;Y′），i∈{ 1，2＼}。

TEE將{I1，I1，2}發(fā)送給P1，將{I1，I2，2}發(fā)送給向P2。

8： P1與P2執(zhí)行調(diào)用TEEF對安全內(nèi)存M1，M2進(jìn)行內(nèi)存釋放。

T1與T2是由TEEV 生成的2個(gè)臨時(shí)列表，存儲雙方驗(yàn)簽通過的認(rèn)證人與資質(zhì)集合。在最后的安全求交階段，TEEQ 算法的本質(zhì)是計(jì)算P1的掩碼X′，然后計(jì)算X′∩Y′，并詢問交集是否存在于Ti。若存在則說明該交集元素（認(rèn)證人）與對應(yīng)的資質(zhì)是合法輸出。這表明該交集元素既屬于雙方認(rèn)證人的交集，同時(shí)該認(rèn)證人所發(fā)布的簽名證書在TEE中被驗(yàn)簽通過。因此，我們在此處只需證明PSI協(xié)議是有效的即可，即X′∩Y′確是兩方的認(rèn)證人的交集。當(dāng)x=y時(shí)，我們需證明掩碼H1（Decode （C，x，r））與H1（Decode （B′，y）-ΔH2（y））相等，如下所示。

Decode （B′，y）-ΔH2（y）

=Decode （B+Δ（A+P），y）-ΔH2（y）

=Decode （C+ΔP，y）-ΔH2（y）

=Decode （C，y）+ΔDecode （P，y）-ΔH2（y）

=Decode （C，y）+ΔH2（y）-ΔH2（y）

=Decode （C，y）

=Decode （C，x）（6）

因此，所提PCI協(xié)議正確性成立。此外，由于TEE中可嵌入不同的簽名驗(yàn)簽算法，即便在同一個(gè)TEEV中，TEE也可執(zhí)行不同的驗(yàn)簽算法。

3.6 協(xié)議應(yīng)用

在Web3.0中，當(dāng)2個(gè)用戶需要在無可信第三方CA下建立信任機(jī)制時(shí)，他們可以采取以下步驟：首先，雙方公開生成證書的簽名算法，并選擇合適的第三方TEE機(jī)構(gòu)，以便進(jìn)行證書的驗(yàn)證服務(wù)和CA的求交。這一過程遵循PCI協(xié)議。在該過程中，用戶雙方需要將CA的公鑰列表嵌入到TEE中，以便TEE提供證書驗(yàn)證服務(wù)，同時(shí)確保不在交集內(nèi)的CA公鑰不會泄露，因?yàn)門EE是可信的。最后TEE將求得的交集分別發(fā)送給2個(gè)用戶。值得一提的是，類似螞蟻的隱語等平臺已經(jīng)提供了類似的TEE服務(wù)。與GHOSH等［15］提出的PCI協(xié)議相比，本文所介紹的PCI協(xié)議更適用于Web3.0中的實(shí)際應(yīng)用場景。

3.7 安全性分析

本文所提PCI協(xié)議是抗惡意敵手的。

首先，上述協(xié)議的驗(yàn)簽過程是由TEE完成，且由于數(shù)字簽名的公開驗(yàn)證性質(zhì)，TEE能夠?qū)1與P2的輸入進(jìn)行校驗(yàn)。同時(shí)，在驗(yàn)簽過程中（第1、2步），P1與P2沒有收到消息，因此視圖為空。

協(xié)議1的第3步到第6步本質(zhì)是一個(gè)抗惡意敵手的不經(jīng)意偽隨機(jī)函數(shù)（oblivious pseudorandom function， OPRF）協(xié)議，具體證明可查閱文獻(xiàn)［20］。其中VOLE協(xié)議的具體證明可查閱文獻(xiàn)［12］。

協(xié)議1的第7、8步由TEE完成，因此P1與P2在第7、8步從得到的視圖中無法獲取額外的信息。此外，第7、8步的正確性（在惡意敵手存在時(shí)能得到正確的輸出）可查閱文獻(xiàn)［13］。

4 實(shí)驗(yàn)與分析

本節(jié)實(shí)現(xiàn)所提PCI協(xié)議并對其進(jìn)行性能測試，并與文獻(xiàn)［15］的PCI協(xié)議進(jìn)行對比。

4.1 實(shí)驗(yàn)環(huán)境以及參數(shù)

測試的硬件平臺采用Intel i7-1165G7處理器、內(nèi)存為16 GiB、主頻為2.8 GiHz。操作系統(tǒng)為Ubuntu20.04，編程語言為C++。TEE本文采用螞蟻集團(tuán)提出的TEE框架［24］。根據(jù)文獻(xiàn)［15］ PCI協(xié)議的設(shè)定，我們將輸入大小設(shè)置為1 000。此外，由于本文所提PCI協(xié)議支持多種數(shù)字簽名算法，我們分別使用ECDSA［17］、RSA［18］、SM2［19］這3種算法在128位安全等級下進(jìn)行效率測試。

4.2 功能分析

文獻(xiàn)［15］的PCI協(xié)議與本文所提PCI協(xié)議在功能方面的對比結(jié)果如表1所示。從表1可以看出，所提PCI協(xié)議不僅能夠在保護(hù)非交集認(rèn)證人隱私的前提下完成PCI協(xié)議，同時(shí)能在同一個(gè)協(xié)議中使用不同的數(shù)字簽名算法。在本文的PCI協(xié)議中，驗(yàn)簽算法是由TEE完成的。因此，僅需在TEE中事先實(shí)現(xiàn)各種驗(yàn)簽算法，然后在執(zhí)行驗(yàn)簽過程時(shí)根據(jù)簽名類別調(diào)用不同的驗(yàn)簽算法即可。此外，由本文3.7節(jié)可知本文所提PCI協(xié)議也是抗惡意敵手的。

4.3 性能分析

從協(xié)議1中可以看出所提PCI協(xié)議需要的計(jì)算開銷大約為N1+N2次數(shù)字簽名的驗(yàn)簽算法與1次PSI求交。在PCI協(xié)議中，我們僅統(tǒng)計(jì)一些較為耗時(shí)的計(jì)算操作，如表2所示。

從表2中可以看出，所提PCI協(xié)議的性能主要取決于3點(diǎn)：驗(yàn)簽算法TEEV性能；VOLE協(xié)議效率；OKVS構(gòu)造加解碼效率。在所提PCI協(xié)議中，我們使用目前最優(yōu)的VOLE協(xié)議［12］（僅需0.3 s即可生成百萬量級的OKVS）與OKVS構(gòu)造［13］（能夠在0.2 s左右完成百萬量級數(shù)據(jù)的加解碼）。同時(shí)，驗(yàn)簽算法TEEV不再需要耗時(shí)的基于秘密共享的MPC協(xié)議。因此，本文所提PCI協(xié)議在性能方面遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn)［15］的PCI協(xié)議。

4.4 實(shí)驗(yàn)效率

本節(jié)首先給出在使用不同的數(shù)字簽名算法時(shí)，本文所提PCI協(xié)議的實(shí)際運(yùn)行時(shí)間，如圖5所示。

由圖5可知：當(dāng)使用ECDSA與SM2的驗(yàn)簽算法時(shí)，本文所提PCI協(xié)議可在1.2 s左右完成輸入大小為1 000的雙方認(rèn)證人集合求交。此外，當(dāng)認(rèn)證人使用RSA簽名算法進(jìn)行證書的驗(yàn)簽時(shí)，協(xié)議的效率相比于使用ECDSA與SM2簽名算法較慢（需要17 s）。這是因?yàn)楸疚乃酨CI協(xié)議的大部分計(jì)算存在于證書的驗(yàn)簽階段。本文所使用的PSI協(xié)議是極度高效的，具體詳情可查閱文獻(xiàn)［13］。在相同安全等級下，RSA執(zhí)行一次證書驗(yàn)簽過程比ECDSA與SM2簽名算法慢了很多。在我們的實(shí)驗(yàn)環(huán)境下，當(dāng)安全等級為128位時(shí)，執(zhí)行一次RSA、ECDSA、SM2的證書驗(yàn)簽過程分別需要17.51 ms、0.49 ms、0.56 ms。因此，在本文提出的PCI協(xié)議中，我們推薦認(rèn)證人使用ECDSA、SM2等基于橢圓曲線的數(shù)字簽名算法。

此外，我們還將本文所提的PCI協(xié)議與文獻(xiàn)［15］的PCI協(xié)議進(jìn)行了效率方面的對比，如表3所示。在NDSS中，GHOSH等的PCI協(xié)議僅支持ECDSA的驗(yàn)簽算法，出于對比實(shí)驗(yàn)的公平，在運(yùn)行本文PCI協(xié)議時(shí)使用的也是ECDSA的驗(yàn)簽算法。

從表3可以看出，本文所提PCI協(xié)議在效率上明顯優(yōu)于文獻(xiàn)［15］的PCI協(xié)議。本文所提PCI協(xié)議的運(yùn)行與輸入大小呈線性關(guān)系，而文獻(xiàn)［15］的PCI協(xié)議的運(yùn)行時(shí)間會隨著輸入大小的增加快速地增加。因此，本文所提的PCI協(xié)議即便是認(rèn)證人集合存在較大輸入量時(shí)，仍能在穩(wěn)定的時(shí)間內(nèi)完成認(rèn)證人求交，而文獻(xiàn)［15］的PCI協(xié)議則無法實(shí)現(xiàn)該功能。此外，本文所提PCI協(xié)議比文獻(xiàn)［15］的PCI協(xié)議效率更高的主要原因是本文所提PCI協(xié)議沒有使用耗時(shí)更高的MPC框架進(jìn)行驗(yàn)簽。同時(shí)，由于本文所提的協(xié)議是基于現(xiàn)有的高性能PSI協(xié)議［13］構(gòu)造而來，所以其進(jìn)行隱私保護(hù)認(rèn)證人求交過程異常高效。

5 結(jié)論

本文基于TEE和現(xiàn)有高效的抗惡意敵手PSI協(xié)議提出了一種新的PCI協(xié)議。該協(xié)議能夠?qū)崿F(xiàn)參與雙方在去中心化CA場景下建立信任機(jī)制。本文提出的PCI協(xié)議能夠在1 s左右完成輸入大小為1 000的求交與驗(yàn)證，相較于GHOSH等的原始PCI協(xié)議具有較大的性能優(yōu)勢。此外，本文PCI協(xié)議能夠支持不同的認(rèn)證人使用不同的數(shù)字簽名算法生成證書，更加符合實(shí)際需求。本文所提出的PCI協(xié)議顯著地增強(qiáng)了Web3.0中用戶數(shù)據(jù)的隱私性，具有較好的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1]楊雄. 云環(huán)境下融合FHE和人臉識別的身份認(rèn)證方案［J］. 貴州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2019， 36（6）： 37-41.

［2］ 徐慧華， 楊雄， 張曉惠. 云計(jì)算環(huán)境下基于全同態(tài)加密的人臉信息保護(hù)［J］. 貴州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2021， 38（3）： 83-91.

［3］ TANG F， LING G W， CAI C C， et al. Solving small exponential ECDLP in EC-based additively homomorphic encryption and applications［J］. IEEE Transactions on Information Forensics and Security， 2023， 18： 3517-3530.

［4］ LI Z T， XIANG Y X， SHI J， et al. Make Web3.0 connected［J］. IEEE Transactions on Dependable and Secure Computing， 2021， 19（5）： 2965-2981.

［5］ TANG F， MA S， XIANG Y， et al. An efficient authentication scheme for blockchain-based electronic health records［J］. IEEE Access， 2019， 7： 41678-41689.

［6］ 唐飛， 包佳立， 黃永洪， 等. 基于屬性的多授權(quán)中心身份認(rèn)證方案［J］. 通信學(xué)報(bào)， 2021， 42（3）： 220-228.

［7］ DUA A， BARPANDA S S， KUMAR N， et al. Trustful： a decentralized public key infrastructure and identity management system［C］// 2020 IEEE Globecom Workshops GC Wkshps. Piscataway： IEEE， 2020： 1-6.

［8］ CHEN H， LAINE K， RINDAL P. Fast private set intersection from homomorphic encryption［C］// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2017： 1243-1255.

［9］ GORDON S D， HAZAY C， LE P H. Fully Secure PSI via MPC-in-the-Head［C］// Privacy Enhancing Technologies. Cham： Springer， 2022： 291-313.

［10］PINKAS B， SCHNEIDER T， ZOHNER M. Faster private set intersection based on OT extension［C］// USENIX Security Symposium. Berkeley： USENIX， 2014： 797-812.

［11］KOLESNIKOV V， KUMARESAN R， ROSULEK M， et al. Efficient batched oblivious PRF with applications to private set intersection［C］// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 818-829.

［12］COUTEAU G， RINDAL P， RAGHURAMAN S. Silver： silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes［C］.//Annual International Cryptology Conference. Cham： Springer， 2021： 502-534.

［13］RAGHURAMAN S， RINDAL P. Blazing fast PSI from improved OKVS and subfield VOLE［C］//ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2022： 2505-2517.

［14］GHOSH B C， VINAYAGAMURTHY D， RAMAKRISHNA V， et al. Privacy-preserving negotiation of common trust anchors across blockchain networks［C］// 2022 IEEE International Conference on Blockchain and Cryptocurrency （ICBC）. Piscataway： IEEE， 2022： 1-5.

［15］GHOSH B C， PATRANABIS S， VINAYAGAMURTHY D， et al. Private certifier intersection［C］// The Network and Distributed System Security Symposium 2023. Rosten： ISOC， 2023： 1-18.

［16］DAI W Q， JIN H， ZOU D Q， et al. TEE： a virtual DRTM based execution environment for secure cloud-end computing［C］// ACM Conference on Computer and Communications Security. New York： ACM， 2010： 663-665.

［17］JOHNSON D， MENEZES A， VANSTONE S. The elliptic curve digital signature algorithm （ECDSA）［J］. International Journal of Information Security， 2001， 1： 36-63.

［18］RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems［J］. Communications of the ACM， 1978， 21（2）： 120-126.

［19］國家密碼管理局. SM2 橢圓曲線公鑰密碼算法 第 1 部分： 總則： GM/T 0003.1—2012［S］. 北京： 中國標(biāo)準(zhǔn)出版社， 2012.

［20］RINDAL P， SCHOPPMANN P. VOLE-PSI： fast OPRF and Circuit-PSI from Vector-OLE［C］// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham： Springer， 2021： 901-930.

［21］PINKAS B， ROSULEK M， TRIEU N， et al. PSI from PaXoS： fast， malicious private set intersection［C］// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham： Springer， 2020： 739-767.

［22］PAGH R， RODLER F F. Cuckoo hashing［J］. Journal of Algorithms， 2004， 51（2）： 122-144.

［23］CANETTI R. Security and composition of multiparty cryptographic protocols［J］. Journal of Cryptology， 2000， 13： 143-202.

［24］SHEN Y， TIAN H， CHEN Y， et al. Occlum： secure and efficient multitasking inside a single enclave of intel SGX［C］// International Conference on Architectural Support for Programming Languages and Operating Systems. New York： ACM， 2020： 955-970.

Private Certifier Intersection Protocol Based on

Trusted Execution Environment

Abstract：

Ghosh et al. first introduced the Private Certifier Intersection （PCI） protocol at NDSS 2023， aiming to establish trust among users within a decentralized environment. In the PCI protocol， parties holding different certificates can compute a common set of certifiers， i.e.， Certificate Authorities （CA）， and verify the validity of these certificates while maintaining privacy.The PCI protocol can be used to solve the problem of establishing mutual trust mechanisms between two users in a decentralized environment without prior knowledge. Ghosh et al.s protocol utilizes a complex secure multi-party computation approach， leading to inefficiency. Additionally， it requires both participating parties to utilize the same signature algorithm， making it impractical. To address these issues， a new PCI protocol is introduced， which leverages a Trusted Execution Environment （TEE）. This novel protocol utilizes TEE to accomplish private certifier intersection， allowing both parties to use their preferred digital signature algorithms， thereby enhancing practicality. Experimental results show that the proposed protocol surpasses Ghosh et al.s PCI protocol in terms of efficiency.

Key words：

private certifier intersection; trusted execution environment; signature; decentralized