高性能兩方隱私集合求交技術研究及應用探索*

雷術梅，張舒黎，彭夕茈，付 俊，谷 欣，洪 運

（1.中電科網絡安全科技股份有限公司，四川 成都 610041；2.可信云計算與大數據四川省重點實驗室，四川 成都 610041；3.中國星網網絡創新研究院有限公司，北京 100029）

0 引言

隨著信息技術的迅猛發展，個人隱私信息在互聯網、社交媒體、電子商務等領域的泄露事件頻頻發生，在眾多安全威脅中，數據泄露已成為全球范圍高發的安全事件之一，且這個趨勢仍在持續。因此，在數據共享流通的過程中，加強數據安全和隱私保護同等重要。2021 年國家相繼通過了《數據安全法》和《中華人民共和國個人信息保護法》，對個人和企業隱私數據的保護的重視程度越來越高，數據隱私保護已成為業界關注的熱點問題。

隱私計算是一種保護數據隱私的技術手段，在保證數據隱私的前提下實現數據的流通與共享，為數據安全和隱私保護提供了有力支撐。隱私集合求交（Private Set Intersection，PSI）作為隱私計算中的一項專用技術，允許互不信任的各方協同計算私有數據的交集，且不透露交集以外的任何信息。

近年來PSI 的理論研究活躍且應用廣泛。早期的PSI 協議主要是基于公鑰密碼構造，根據實際應用的性能需求，新的技術手段和構造框架被提出，除了基于密碼原語中的混淆電路（Garbled Circuit，GC）、不經意傳輸（Oblivious Transfer，OT）、同態加密（Homomorphic Encryption，HE）等技術，高性能OT 擴展（OT Extension，OTE）技術使PSI 效率大大提高。PSI 技術是多類隱私計算應用的先決步驟，如聯合建模前需采用PSI 進行樣本對齊，基于索引的安全查詢前可采用PSI 進行索引獲取等。PSI獨立支撐了許多應用程序，包括隱私保護位置共享[1]、DNA 測試和模式匹配[2]、隱私通訊錄查找[3]等。

現有的PSI 已經非常高效，但隨著應用場景的多樣化，在實際應用中仍然存在性能和安全問題。如新興的衛星互聯網，其網絡和數據蘊藏著巨大的應用價值，可融合諸多行業應用充分挖掘數據價值，而研究更高性能和安全的PSI 對促進衛星互聯網數據融合應用有很大的意義。

本文首先簡要分析了PSI 的分類和設計框架，重點聚焦高性能兩方PSI，詳細梳理了涉及的密碼技術和研究進展，分析和評估了業界先進的算法協議；其次以衛星互聯網新型應用場景為例，探索提出高性能兩方PSI 應用方案，實驗測試不同數據類型在多種網絡環境下的性能，給出新型場景下的PSI 實踐范式；最后進行總結，給出了PSI 的發展思考與建議。

1 概述

PSI 是安全多方計算（Secure Multi-party Computation，MPC）的一類專用協議，傳統的兩方PSI 指互不信任的兩個參與方分別持有各自的數據集X和Y，希望學習他們集合之間的交集X∩Y，而不透露任何額外的信息。為了滿足不同實際場景的應用，除了傳統的兩方PSI，已衍生出了多種新型場景下的PSI協議?；诓煌艽a原語構建的PSI 協議的設計框架多種多樣，經過廣泛的理論和實驗驗證，基于不經意傳輸擴展（Oblivious Transfer Extension，OTE）的兩方PSI 更高效。

1.1 PSI 的分類

為應對不同實際場景的需求，當前PSI 可從參與方數量、求交數據量差距、敵手行為和交集的重解釋4 個方面進行分類，如表1 所示。從兩方PSI到多方，若依舊使用傳統PSI 兩兩求交以達到多方PSI 的功能，則存在多輪通信開銷和合謀攻擊的問題，目前較有效的技術框架是基于OTE 構造的可編程不經意偽隨機函數（Oblivious Programmable Pseudo-Random Function，OPPRF）與零共享結合[4]。非平衡PSI 中兩方數據量相差較大，若采用通用的平衡PSI 則存在小數據方的計算資源需求和消耗太大的問題。主流的非平衡PSI 主要采用全同態（Fully Homomorphic Encryption，FHE）技術且將大數據加密放在離線階段[5]。惡意安全的PSI 更滿足實際場景的安全需求，但相較于半誠實的開銷更大，因此當前研究者傾向于探索安全性易擴展的PSI 框架，這種框架從半誠實到惡意安全僅需非常小的開銷。門限PSI 是有條件的多方PSI，包括對元素出現次數的約束和對交集大小的約束兩種情況。

表1 PSI 分類

1.2 PSI 的設計框架

兩方PSI 的性能優化主要依賴底層密碼原語的發展，根據密碼原語的不同可劃分為4 種設計框架。

（1）基于公鑰密碼的設計框架。主要采用橢圓曲線迪菲-赫爾曼密鑰交換（Elliptic Curve Diffie-Hellman Key Exchange，ECDH）和RSA 技術構造PSI 協議，基于ECDH 采用橢圓曲線上的倍點運算效率更高，協議易于理解、實現簡單且對網絡帶寬不敏感，目前工業界仍廣泛使用ECDH-PSI。

（2）基于混淆電路（Garbled Circuit，GC）的設計框架。此類協議基于GC 的通用特性，對構造可計算交集結果的PSI 比較友好。由于電路構造和深度復雜、比較次數大，此類協議的開銷昂貴。

（3）基于HE 的設計框架。利用HE 密文運算和明文運算等價的特點實現PSI 功能，構造通用的PSI 計算量大，常用于非平衡場景。

（4）基于OT 的設計框架。使用傳統的OT 技術給PSI 帶來了很大的通信開銷，隨著OTE 技術的發展，基于OTE 的PSI 性能突出，被業界廣泛研究和實際應用。本文重點研究基于OTE 設計框架的高性能兩方PSI。

1.3 密碼技術

1.3.1 不經意傳輸擴展

OT 由Rabin[6]于1981 年提出，是一個安全的兩方通信協議，指發送方有多個輸入值，接收方希望得到其中某一個值，與此同時需保證發送方不知道接收方的選擇信息，且接收方除了得到自己選擇的值，不知道其他輸入值的相關信息。OT 是MPC中最重要的原語之一，可被應用到許多密碼學協議的構造中，目前業界高性能的PSI 協議主要依賴OT 的構造，對PSI 性能的提升直接轉化為對OT 協議的改進。

OT 協議性能的優化主要是從“base OT”到OTE 的發展，如表2 所示?！癰ase OT”主要基于公鑰密碼技術構造，在具體實現時表現為計算效率低、通信開銷大，可通過橢圓曲線上的倍點運算和多線程技術進行性能優化。OTE 的提出是為了解決“base OT”的開銷問題，核心思想是參與方交互式獲取“種子信息”，然后使用高效的對稱密碼原語在沒有交互的情況下擴展種子，以獲取大量的OT 實例。OTE 從構造方式的角度又分為IKNP-OTE 和Silent-OTE，前者計算效率高、通信開銷大，后者是前者的改進，旨在降低通信開銷且尋求計算和通信的最佳平衡。

表2 OT 發展及特點

Ishai 等人[7]于2003 年提出的IKNP 協議是OTE 的突破性工作，基于矩陣變換的思想采用少量的“base OT”加對稱加密獲得幾乎任意數量的OT實例，后續有很多基于IKNP 協議的改進性研究[8-9]，此類協議最大的瓶頸是通信?；趥坞S機相關發生器（Pseudorandom Correlation Generator，PCG）構造的Silent-OTE[10-13]優化了通信開銷，其Silent 特性根據PCG 的性質，經過一次廉價的交互后，雙方可以存儲小的密鑰種子，這些種子可以離線本地生成大量OT 實例，通信和計算開銷基本上獨立于OT的目標數量。2019 年Boyle 等人[10]基于對偶一帶噪聲學習奇偶校驗（dual-Learning Parity with Noise，dual-LPN）假設和函數秘密共享（Function Secret Sharing，FSS）技術提出Silent-OTE，但在密鑰建立和dual-LPN 計算上復雜度高。為了降低Silent-OTE 的計算開銷，后續的研究改用支持高效編碼的原始-LPN（primal-LPN）假設[11-12]或低密度奇偶校驗碼（Low-Density Parity-Check Codes，LDPC）進行構造[13]。

1.3.2 向量不經意線性評估

不經意線性評估（Oblivious Linear Evaluation，OLE）是一種使參與雙方能夠獲得相關輸出的功能。一方輸入值u和v，另一方輸入值x且獲得輸出w=ux+v。向量不經意線性評估（Vector OLE，VOLE）是OLE 的一個向量化變體，更具體地說，發送方持有向量u和v，接收方有值x。該協議的目的是使接收方能夠學習w=ux+v，而不向任何一方透露進一步的信息。VOLE 協議隱含了一個偽隨機變體，如圖1 所示，其中向量u和v是偽隨機的，并在協議執行過程中隨機生成，作為輸出到達發送方。偽隨機VOLE 是MPC 的一個基礎構件，被廣泛用于構造當前高性能的PSI 協議。

圖1 偽隨機VOLE

VOLE 與Silent-OTE 有深刻的聯系，相互之間可以構造轉化。因此，VOLE 的發展同Silent-OTE。

1.3.3 不經意鍵值存儲

2 高性能兩方PSI

早期提出的基于樸素哈希的PSI 方案存在暴力破解的風險，后續為解決這個問題提出了不經意偽隨機函數（Oblivious Pseudo-Random Function，OPRF）的PSI 構造范式，其成為實現隱私性和高性能兩方PSI 的核心。當前OPRF 高效的實例化主要分為兩條技術路線：（1）將IKNP-OTE 解釋為OPRF；（2）結合VOLE 和OKVS 構造OPRF。通過以上兩種實例化的OPRF 構建的PSI 分別為IKNP-OTE PSI 協議和VOLE-OTE PSI 協議。

2.1 不經意偽隨機函數

如圖2 所示，運行OPRF 協議之后，發送方可獲得一個偽隨機函數F的密鑰k，接收方可以得到一系列偽隨機函數的計算結果，同時，發送方不知道接收方的輸入，接收方也不知道發送方獲得的密鑰k。OPRF 協議保證了發送方無法反推輸入，同時接收方沒有密鑰k，也無法得到結果后暴力搜索。

圖2 OPRF 范式

2.2 IKNP-OTE PSI

IKNP-OTE PSI 技術發展如圖3 所示，核心思想是對基于公鑰密碼的“base OT”技術擴展為高效的OTE，然后將OTE 解釋為OPRF，由OPRF 構建PSI 協議。隨著OT 技術的提出，Pinkas 等人提出的PSSZ15 協議[14]及許多衍生協議[9,15-16]發起了對IKNP-OTE 新協議族的研究，這類協議以增加通信為代價提高了效率。

圖3 IKNP-OTE PSI 技術發展

2013 年Ishai 等人[7]基于矩陣轉置提出突破性的1-out-of-2 IKNP03-OTE 工作，Kolesnikov 等人[8]指出IKNP-OTE 使用了一個編碼方案，存在對選擇比特ri∈{0,1}重復編碼的問題。因此，使用一定碼字長的?維線性糾錯碼，構造出1-out-of-2?的KK13-OTE 協議。2016 年Kolesnikov 等人[9]指出PSSZ15 隱私相等性檢測協議執行OT 次數依賴于集合元素的比特長度，計算和通信開銷非常大。為了移除上述依賴關系，作者改進KK13-OTE 協議，使用偽隨機函數替換線性糾錯碼構造出1-outof-∞的KKRT16-OTE 協議。后續將OTE 解釋為批量密鑰相關的OPRF（Batched Related-key OPRF，BaRK-OPRF），OPRF 則可很容易構建PSI 協議。此外，融入了Cuckoo hash 技術將集合映射到hash表中，確保雙方相同的數據必定在同一箱中，降低比較次數且減少OPRF 實例的計算而減少了通信開銷。鑒于KKRT 協議對每個元素需執行多個單點OPRF 操作，Pinkas 等人[15]從通信負載上，采用多項式插值技術改進IKNP03-OTE，實現了多點OPRF且允許每個元素只計算一個OPRF 實例，降低了通信開銷，但高階多項式插值產生了較高的計算開銷。2020 年Chase 等人[16]從通信和計算平衡的角度，僅采用OT、對稱密碼和偽隨機函數設計出多點OPRF，實現了通信和計算開銷平衡的PSI 協議。

2.3 VOLE-OTE PSI

VOLE-OTE PSI 協議主要采用VOLE 和OKVS技術構造OPRF 實例，比對OPRF 實例即可獲取交集結果。2020 年Pinkas 等人[17]首次將OKVS 數據結構融入PSI 中，使用一個Cuckoo 圖來實現PaXoS（probe-and-XOR of strings），它提供了一個非常高效和便捷的方法來表示集合X和Y，作者將他們的OKVS 和文獻[15]的PSI 協議結合起來，以獲得當時最高效的PSI 協議之一。Rindal 等人[18]觀察到OKVS 可以更有效地與VOLE[11]相結合，以獲得更高效的PSI 協議，還提出了改進的XoPaXoS（X-oblivious PaXoS）以構造OPPRF，使用OPPRF以很小的開銷實現惡意安全的PSI。與此同時，Garimella 等人[19]通過放大技術驗證OKVS 隨機構造的失敗概率在一個相對較高的上界，改進的OKVS 使文獻[15]的PSI 協議通信效率提高。到目前為止，基于IKNP-OTE 的KKRT 協議仍然是計算效率最高的，文獻[18]是通信效率最高的，而文獻[19]是兩者之間的折中方案。2022 年Rindal 等人[20]基于文獻[18]的PSI 框架，對OKVS 進行了顛覆性的改進，基于高維線性方程求解的思想，采用簡化矩陣下三角和分塊聚類的方法，可有效并行化OKVS 編碼，并且將VOLE 擴展成子域-VOLE（subfield-OKVS）[13]降低通信量。同年，Bui 等人[21]提出了一個相似貢獻的PSI 協議，采用的是hash 和VOLE 技術。

總的來說，VOLE-OTE PSI 框架如圖4 所示，分為OKVS 編碼、OPRF 密鑰生成和OKVS 解碼并獲得交集3 個階段。假設發送方有數據集Y={y1,y2,…,yn}，接收方有數據集X={x1,x2,…,xn}，雙方提前協商兩個hash 函數，即HF:{0,1}*→F，H*:{0,1}→{0,1}out，參數m為OKVS 編碼輸出向量的維度，m＞n。

圖4 VOLE-OTE PSI 框架

（1）OKVS 編碼。接收方采樣隨機值r并發送給發送方，接收方本地執行OKVS 編碼過程，輸入數據是關于集合數據的 (xi,HF(xi,r))，獲得輸出向量P∈Fm。

（2）OPRF 密鑰生成。發送方和接收方交互式地進行VOLE 過程，發送方獲得有限域整數Δ∈F，向量B∈Fm，接收方獲得向量A∈Fm和C∈Fm，其中C=ΔA+B。接收方計算A+P并發送給發送方，然后發送方計算OPRF 密鑰K=B+Δ(A+P)。

（3）OKVS 解碼并獲得交集。接收方對每個數據xi進行OKVS 解碼Decode(C,xi)，并對其計算hash 值H*(Decode(C,xi))。發送方對每個數據yi進行OKVS 解碼Decode(K,yi)，然后計算H*(Decode(K,yi)-ΔHF(yi,r))，并將所計算的hash 結果發送給接收方。最后，接收方比對兩個OPRF 集合獲得最終的交集。

此外，基于VOLE 和OKVS 技術實現的PSI提供了一個非常優秀的范式，既可以為半誠實安全又可抗惡意安全。PSI 的安全級別依賴于VOLE 和OKVS 實例化的OPRF 輸出長度out，當out=λ+log2(nxny)時達到半誠實安全，當out=κ時達到抗惡意安全，其中λ和κ分別為統計安全參數和計算安全參數，且相對于半誠實到惡意安全僅需非常小的開銷。

3 面向衛星互聯網的PSI 應用方案及實驗分析

3.1 面向衛星互聯網的PSI 應用方案設計

衛星互聯網作為新型戰略基礎設施，其網絡和數據蘊藏著巨大的應用價值。不同于傳統通信網絡，衛星互聯網具備“天—地”一體化組網、多源信息融合等新特性，典型的衛星互聯網場景如圖5 所示。

圖5 衛星互聯網場景

衛星互聯網數據涵蓋網絡運行、測試控制、行業應用、個人增值、物聯網（Internet of Things，IoT）等多元信息，數據種類多、時空尺度大、覆蓋范圍廣、數據價值高，可作為重要的數據來源支撐其他行業的數據融合應用。比如，衛星互聯網的高價值測繪、遙感等數據可為環境、旅游等行業提供數據支撐；衛星互聯網多維度的網絡流量數據可與傳統運營商互補，以更好地刻畫用戶行為和分析業務情況等。本文以衛星互聯網新型場景為背景，提出衛星互聯網和地面運營商的高性能PSI 應用解決方案，探索PSI 技術如何在新型場景落地，賦能行業應用。方案整體框架見圖6。

衛星互聯網和地面運營商數據融合的PSI 應用方案主要包含數據準備、元信息共享、數據預處理、安全求交4 個階段。

（1）數據準備階段。衛星互聯網業務平臺采集網絡數據、用戶信息、流量數據等，并將業務平臺的數據接入隱私計算節點，節點將對用戶、業務的原始數據（或數據表）進行管理，如元信息的展示和統計分析等。同樣地，地面運營商業務平臺在本地隱私計算節點形成自身的原始數據及相應的元信息。

（2）元信息共享階段。衛星互聯網和地面運營商作為隱私計算的兩個獨立節點，先確定待融合應用的樣本數據，然后通過原始數據隔離、元數據共享的安全業務模式，交互式確定需對齊的ID信息，如用戶身份證號、業務ID 等。

（3）數據預處理階段。雙方對確定的ID 信息本地預處理，包括數據去重和數據標準化。ID 信息進行本地數據去重，海量數據可采用BloomFilter 方式，針對一般量級的數據可借助K-V 數據庫進行去重，或采用樸素HashSet 的方式。對于ID 信息的本地數據標準化，雙方提前協商規則進行數據填充和清洗。

（4）安全求交階段。雙方根據場景需求選擇PSI 協議并運行，結合實際需求設置一方或者兩方獲取交集結果，但不能獲得交集以外的任何信息。PSI 協議執行的對比分析見3.2 節。

3.2 對比實驗

本文主要對業界關注度比較高且廣泛用于實際場景的4 個PSI 算法進行實驗分析，包括基于公鑰密碼的ECDH-PSI[22]、IKNP-OTE 的KKRT[9]、VOLE-OTE 的BC22[21]和RR22[20]，前3 個算法是基于隱語的安全處理單元（Secure Processing Unit，SPU）平臺[23]實現的，最后一個算法是基于文獻對應的開源庫Vole-PSI[20]實現的，該庫是跨平臺的（win，linux，mac），依賴于libOTe（大量OTE 算法實現庫）、sparsehash（hash 映射庫）和Coproto（基于協程的跨平臺協議框架）。實驗環境為兩臺Intel至強5218@2.3 GHz 服務器上的CentOS7.6-x64 虛擬機（16 GB 內存、251 GB 硬盤），在兩臺物理機上分布式地運行PSI 任務。

針對實際應用，設置兩項細分場景進行實驗分析。一是面向用戶行為分析的海量用戶ID 求交，二是面向業務邏輯分析的小批量業務ID 求交。

3.2.1 用戶ID 求交

4 種PSI 算法的性能統計如表3 所示，測試數據量兩方均為1 億條（ID 為18 位十進制字符），交集結果為5 000 萬條，分別在100 Mbit/s、500 Mbit/s 和1 000 Mbit/s 三種網絡帶寬下的統計結果。從表中可知：（1）ECDH-PSI 對網絡配置不敏感，對計算資源敏感；（2）IKNP-OTE PSI 受帶寬影響較大，計算性能較好；（3）VOLE-OTE PSI 是通信和計算的平衡，性能開銷上表現更好，億級數據的求交可在10 min 內完成。

表3 基于用戶ID 的安全求交

3.2.2 業務ID 求交

使用“設備ID－網絡情況－業務信息”模擬30 字符的業務ID，雙方數據量分別為100 萬條，交集結果為50 萬條，在低帶寬10 Mbit/s 的網絡環境下，4 種PSI 算法的性能統計如表4 所示。實驗數據表明，在低帶寬網絡環境下，ECDH 和VOLEOTE（RR22）的PSI 算法性能較好，運行速度是KKRT 和BC22 的2～3 倍。

表4 10 Mbit/s 帶寬下基于業務ID 的安全求交

由表4 可知RR22 算法性能最好，表5 展示了在多個參數優化下的性能統計。設置較大的聚類分塊參數（mBinSize）和較小的統計安全參數（mSsp），降低了總體通信量且可進行多線程運算。此外，在局域網下的運行速度是廣域網下的3～15 倍。

表5 不同參數下基于RR22 算法的安全求交

3.3 對比結論

基于公鑰密碼技術的ECDH-PSI 協議簡單，易于理解和實現，且易于擴展為非平衡和多方的PSI 場景，具有低通信量和中計算量的特性?；诰仃囎儞Q的IKNP-OTE 類PSI 協議具有最佳的計算效率，但通信開銷為該類方案在廣域網場景下的主要瓶頸?；赩OLE 和OKVS 構造的VOLE-OTE 類PSI 協議在通信和計算效率上做到了較好的平衡，在廣域網下性能具有優勢。此外，VOLE 和OKVS 技術為PSI 提供了一個優秀的范式，可很容易從半誠實安全轉化為惡意安全，開銷非常小。VOLE-OTE 類PSI 協議的局限性是依賴的基礎技術理解和實現層面都有一定難度。

在衛星互聯網場景，在計算資源允許的情況下推薦采用RR22 協議構建高性能PSI 應用方案，此外海量數據高帶寬下可選用KKRT 協議，少量樣本低帶寬下可選用ECDH 方案。針對RR22 協議，需進一步優化OKVS 聚類分塊大小、安全參數和線程數等協議參數以取得最優性能。在實際應用中，可結合數據樣本大小和網絡、計算資源選擇算法，以達到最優性能。

4 結語

在政策和個人意識的推動下隱私保護需求愈加強烈，數據隱私保護已成為業界關注的熱點問題。隱私計算是一種保護數據隱私的技術手段，PSI 作為隱私計算中的一項專用技術，是促進數據融合應用的先決步驟，在保證數據隱私的前提下推動了數據的流通與共享。然而，在多樣性的實際場景下，現有的PSI 協議仍存在高效性、安全性和適用性等方面的問題，有待進一步探索和突破，如下文所述。

（1）提高PSI 協議的性能。密碼技術的性能瓶頸是其與實際業務相結合的一大難點，相較于明文計算慢幾個數量級。一直以來，PSI 協議的性能都是計算和通信開銷的博弈，基于VOLE-OTE 的PSI 協議在計算和通信開銷上做到了較好的平衡，但在低網絡帶寬下海量數據求交的性能仍然不理想。因此，基于VOLE-OTE PSI 的范式，可進一步改進底層OKVS 和VOLE 的計算和通信性能。

（2）研究高安全性的PSI 方案。當前絕大部分的PSI 方案僅抵御半誠實攻擊，但抗惡意安全更具有實用性。從一般的半誠實安全協議擴展到惡意安全，往往需要更高的開銷，在滿足實際可用的情況下高安全性的PSI 協議需進一步研究。

（3）構建新型場景的PSI 協議。為應對不同實際場景的需求，通用的PSI 協議并不能適用于所有的業務場景，如參與方數據不平衡的場景，通用的方案導致小數據方的計算資源需求和消耗太大；某些交集結果仍是敏感的特定場景，如電子醫療的病患數據，通用方案則會泄露交集結果。因此，需根據實際情況構造滿足場景需求的PSI 協議。