摘要隱私集合運算（PSO）是大數(shù)據(jù)時代保護(hù)用戶隱私的關(guān)鍵技術(shù)，是一類支持多方在隱私保護(hù)前提下進(jìn)行集合運算的專用安全多方計算協(xié)議。其核心協(xié)議包括隱私集合求交，隱私集合交集計算與隱私集合求并，通常通過公鑰密碼學(xué)、混淆電路及OT技術(shù)等密碼機(jī)制實現(xiàn)，并在計算效率、通信開銷及通用性上各有優(yōu)勢。阿里媽媽SDH已集成多種PSO核心能力于廣告場景服務(wù)中。查閱一隱私計算專題隨著大數(shù)據(jù)時代的發(fā)展，用戶在互聯(lián)網(wǎng)上的點擊、停留、分享與購買等行為被實時轉(zhuǎn)化為可計算的數(shù)據(jù)流。數(shù)據(jù)規(guī)模的指數(shù)級增長與算法能力的突破，不僅為企業(yè)帶來精細(xì)化運營能力，更重構(gòu)了傳統(tǒng)營銷模式。數(shù)字廣告在近十年間實現(xiàn)了高效增長，其持續(xù)擴(kuò)張的核心動力在于廣告生態(tài)鏈通過數(shù)據(jù)實現(xiàn)"精準(zhǔn)人群+黃金時段+適配場景"的三維觸達(dá)，這依賴于生態(tài)體系中三大核心參與者：·廣告主（Brand/Advertiser），掌握自有CRM或App用戶數(shù)據(jù).媒體與流量平臺（Publisher/AdNetwork），擁有龐大的受眾訪問面.第三方數(shù)據(jù)服務(wù)商（MMP/CMP），負(fù)責(zé)投放效果評估與反作弊數(shù)據(jù)流會頻繁進(jìn)行交集去重、并集擴(kuò)量、交集計數(shù)等集合類運算，以實現(xiàn)人群匹配、頻次控制和ROI歸因等關(guān)鍵功能。在隱私法規(guī)趨嚴(yán)與瀏覽器淘汰第三方Cookie、移動端限制IDFA的背景下，傳統(tǒng)“明文對接”模式已難以為繼，如何在數(shù)據(jù)共享同時，保護(hù)用戶數(shù)據(jù)隱私成為當(dāng)前的重點問題，隱私集合運算成為破解數(shù)字廣告數(shù)據(jù)協(xié)同瓶頸的關(guān)鍵技術(shù)。隱私集合運算（PrivateSetOperations,PSO）允許多方在保護(hù)各自輸入集合隱私的前提下，共同完成各類集合運算，常用于隱私數(shù)據(jù)庫查詢[1]。按照參與方數(shù)量，PSO可分多兩方和多方隱私集合運算。在兩方場景中，參與方通常分為一個接收方R和一個發(fā)送方S，接收方指得到協(xié)議輸出結(jié)果的一方。根據(jù)不同的功能性，主流PSO協(xié)議可分為以下三類：1）隱私集合求交（PrivateSetIntersection,PSI用于計算集合交集2）隱私集合交集計算（PrivateComputationonSetIntersection,PCSI用于對交集元素進(jìn)行細(xì)粒度的隱私計算主要包括以下兩類：·隱私集合求交集勢（PrivateSetIntersectionCardinality,PSI-Card）：用于計算交集的勢.隱私集合求交集勢與和（PrivateSetIntersectionSumWithCardinality,PSI-Card-Sum）：用于計算交集的勢與和3）隱私集合求并（PrivateSetUnion,PSU用于計算集合并集考慮兩方場景的PSI協(xié)議，接收方和發(fā)送方分別持有集合X,Y，兩方輸入本方集合X,Y執(zhí)行隱私集合求交協(xié)議，輸出交集XnY給接收方[2]。在此過程中，雙方均無法得到除交集外對方集合的任何信息。PSI是在保障隱私的前提下實現(xiàn)數(shù)據(jù)庫安全內(nèi)連接（InnerJoin）的關(guān)鍵技術(shù)，被廣泛應(yīng)用于廣告、保險、醫(yī)療等多個行業(yè)。隨著應(yīng)用場景的不斷豐富，發(fā)展出了多種PSI變體以支撐更加多樣化的場景：多方PSI支持三方及以上參與方的隱私求交，可應(yīng)用于多機(jī)構(gòu)科研與金融協(xié)作；非平衡PSI優(yōu)化了數(shù)據(jù)量懸殊情況下的計算效率，適用于廣告歸因中海量曝光與少量轉(zhuǎn)化等場景；代理PSI借助云端代理降低終端負(fù)擔(dān)，適用于物聯(lián)網(wǎng)協(xié)同或分布式系統(tǒng)；門限PSI僅輸出交集是否達(dá)預(yù)設(shè)閾值，滿足風(fēng)控場景的異常關(guān)聯(lián)判斷需求，避免敏感數(shù)據(jù)泄露。這些衍生協(xié)議不斷擴(kuò)展了PSI的功能邊界，也為隱私計算領(lǐng)域帶來了新的理論與工程挑戰(zhàn)。目前，實現(xiàn)各類PSI及其變體所依賴的底層密碼學(xué)框架大體可歸納為三條路線：1）基于公鑰密碼體制：包括RSA、同態(tài)加密、量子盲簽名等2）基于不經(jīng)意傳輸協(xié)議：包括OT協(xié)議及OT擴(kuò)展協(xié)議3）基于混淆電路：包括姚氏電路、GMW等【基于公鑰密碼體制】基于公鑰密碼體制的PSI的研究可追溯到1986年，Meadows提出首個基于Diffie-Hellman的兩方協(xié)議，將“明文元素比對”巧妙地轉(zhuǎn)化為“會話密鑰比對”。2004年，F(xiàn)reedman等人引入同態(tài)加密與多項式擬合，給出首個可證明安全的PSI方案，為該領(lǐng)域奠定了嚴(yán)謹(jǐn)?shù)睦碚摶A(chǔ)。隨后，學(xué)術(shù)界相繼提出多種基于同態(tài)加密的改進(jìn)協(xié)議，但高計算開銷導(dǎo)致其在大規(guī)模應(yīng)用中存在性能瓶頸。2022年，Vos等人實現(xiàn)了集合元素的安全“與”運算，基于橢圓曲線密碼學(xué)（ECC）的高性能與群運算交換性優(yōu)勢，提出了迄今針對大規(guī)模數(shù)據(jù)集效率最高的多方PSI協(xié)議。【基于混淆電路】混淆電路（GarbledCircuit,GC）能把任何函數(shù)轉(zhuǎn)換為布爾電路，天然適用于“多功能”PSI（求交、求并、門限、勢等）的實現(xiàn)。自2012年Huang等人用Yao電路提出首個半誠實GC-PSI協(xié)議以來，圍繞“如何把電路做小、做淺”，2019年P(guān)inkas利用可編程OPRF（OPPRF）把通信復(fù)雜度壓縮到與集合大小線性。GC-PSI的優(yōu)勢在于通用性強(qiáng)、可支持多種交集派生操作，但因電路設(shè)計復(fù)雜導(dǎo)致其實際性能較差?！净诓唤?jīng)意傳輸】不經(jīng)意傳輸（ObliviousTransfer,OT）是安全多方計算技術(shù)中最基礎(chǔ)的協(xié)議之一：接收方選擇一個比特be{0,1}，發(fā)送方提供兩個元素(ro,r1)，協(xié)議結(jié)束后接收方獲得ri，而發(fā)送方無法得知b的具體值。Ishai等人在2003年提出了OT擴(kuò)展，顯著提高了大量不經(jīng)意傳輸?shù)挠嬎阈阅堋?013年，Dong人首次提出了基于布隆過濾器和OT的PSI協(xié)議，2016年，Kolesnikov等人引入偽隨機(jī)函數(shù)，利用OT擴(kuò)展對偽隨機(jī)函數(shù)進(jìn)行實例化以構(gòu)造高效的PSI協(xié)議。相較于基于公鑰和混淆電路，OT在計算開銷和通信開銷達(dá)到平衡。以基于公鑰密碼體制-ECC方案為例，阿里媽媽營銷隱私計算平臺SecureDataHub（SDH）實現(xiàn)了基于橢圓曲線ECC的Diffie-Hellman的PSI協(xié)議，具體協(xié)議流程如下：1.接收方R和發(fā)送方S協(xié)商一個橢圓曲線群及hash_to_curve算法，并各自生成私鑰SKR,sks。2.R和S將本方元素X={i}ien和Y={yj}jEm通過hash_to_curve算法映射為橢圓曲線上的點X*={i*}ien和Y*={yj*}jzm。3.R和S分別使用本方私鑰SKR和sks對本方元素映射的X'和Y進(jìn)行加密，即分別計算橢圓曲線上的標(biāo)量乘法*={SKR×i*}ien和y*{sksXYj*}jem。5.S對X*使用本方私鑰進(jìn)行二次加密，即計算X*={SKSSKRi*}ien，并發(fā)送Y*,X"*給R。6.R對y,*使用本方私鑰進(jìn)行二次加密，即計算y*={SKSSKRXYj*}jEm。7.R對xii*和yi,*中的每個元素進(jìn)行比較，得到I={i}zi,,*Y,,*，從而計算交集{i}ieI輸出。作為PSO領(lǐng)域的重要技術(shù)分支，PSI技術(shù)已廣泛應(yīng)用于實際業(yè)務(wù)。然而，單純獲取交集難以滿足更復(fù)雜的場景需求，例如交集上的統(tǒng)計分析和加權(quán)計算、并集計算等。因為學(xué)術(shù)界與工業(yè)界延伸出兩大技術(shù)方向：隱私集合交集計算與隱私集合求并，拓展了PSO技術(shù)的應(yīng)用邊界?！净A(chǔ)介紹】以兩方場景的PCSI協(xié)議為例，接收方R與發(fā)送方S分別持有集合X,Y，并共同約定了集合上的目標(biāo)函數(shù)f(·)，兩方分別輸入本方集合X,Y，協(xié)議輸出f(XnY)[3]。協(xié)議過程中保證除結(jié)果f(xnY)外，R和S均不能得到對方集合的其他任何信息，包括交集元素XnY。根據(jù)執(zhí)行的目標(biāo)函數(shù)f(·)的不同，PCSI協(xié)議中有兩種常用的協(xié)議PSI-Card和PSI-Card-Sum。PSI-Card僅輸出交集的勢IxnY，被廣泛應(yīng)用于廣告去重計費、客戶重疊度評估等場景。PSI-Card-Sum在求得Xnyl的同時，對交集元素攜帶的數(shù)值標(biāo)簽進(jìn)行安全求和，應(yīng)用于廣告ROI統(tǒng)計、聯(lián)合授信風(fēng)險敞口計算等場景。相較于傳統(tǒng)的PSI協(xié)議，這種定制化的協(xié)議僅輸出關(guān)于交集的統(tǒng)計量而不泄露交集，更符合數(shù)據(jù)使用中強(qiáng)調(diào)的“最小化原則”。【相關(guān)工作】PCSI協(xié)議從交集計數(shù)逐步擴(kuò)展至任意函數(shù)隱私計算：2005年，Vaidya等人提出首個計算交集大小的PSI-Card協(xié)議；2006年，Hohenberger等人將復(fù)雜度降至亞二次級。2020年，Miao等人基于分布式OPRF與同態(tài)加密提出首個惡意模型安全的PSI-Sum協(xié)議，但計算開銷大。2021年，Garimella引入OT設(shè)計了一個PSO框架，在只泄露交集勢的前提下支持任意函數(shù)隱私計算。目前，PCSI協(xié)議已支持交集上的多功能計算，并持續(xù)向高效方向演進(jìn)?！净A(chǔ)介紹】隱私集合求并協(xié)議允許參與方在不泄露原始集合元素的前提下完成并集計算。以兩方場景的PSU協(xié)議為例，接收方S和發(fā)送方R分別輸入集合X和Y，輸出并集XUY[4]。與PSI、PCSI適用于隱私數(shù)據(jù)庫內(nèi)連接不同，PSU是隱私數(shù)據(jù)庫全連接（FullJoin）的核心組件，對擴(kuò)充隱私數(shù)據(jù)庫的功能性具有巨大價值。與PSI技術(shù)相比，PSU發(fā)展較為滯后，盡管PSU與PSI在功能邏輯上高度相似，但計算性能上PSU與PSI存在數(shù)量級差距，因此制約了其實際的落地應(yīng)用。近年來，隨著OKVS、OPRF等技術(shù)變革，PSU技術(shù)開始進(jìn)入快速發(fā)展階段，研究路線大致分為兩條：.基于公鑰密碼學(xué)：主要采用同態(tài)加密，通信量小，但算力開銷大，適合帶寬受限、算力充裕的場景.基于OT協(xié)議：通過OT擴(kuò)展減少數(shù)據(jù)批量處理的計算開銷，缺點是會帶來額外帶寬消耗【相關(guān)工作】PSU協(xié)議發(fā)展經(jīng)歷了三個關(guān)鍵節(jié)點：2005年Kissner等提出首個基于同態(tài)加密與拉格朗日插值的PSU方案，但性能受限于同態(tài)加密；2017年Davidson團(tuán)隊引入布隆過濾器與Paillier加密，將計算/通信復(fù)雜度首次降至線性；2019年Kolesnikov首次引入OT協(xié)議，構(gòu)造“RPMT+OT”框架，計算效率顯著提升。后續(xù)工作基本沿用了此框架，并圍繞RPMT協(xié)議的性能優(yōu)化展開。2023年，Zhang等提出首個基于OT的線性復(fù)雜度協(xié)議，進(jìn)一步推動PSU技術(shù)成熟。為了提升PSO領(lǐng)域內(nèi)上述協(xié)議的通用性與可部署性，Chen等人提出了一種統(tǒng)一的構(gòu)造框架[5]，將多種協(xié)議的實現(xiàn)整合到一個系統(tǒng)化結(jié)構(gòu)內(nèi)，通過引入多查詢反向成員測試（multi-queryReversePrivateMembershipTest,mq-RPMT）的新型基礎(chǔ)協(xié)議，同時使用OT協(xié)議實現(xiàn)協(xié)同計算，支持快速構(gòu)建PSI-Card、PSI-Card-Sum以及PSU等協(xié)議。盡管該框架具有很強(qiáng)的通用性，但在性能上與前沿的PSI協(xié)議仍存在一定差距。mq-RPMT協(xié)議輸入為接收方S和發(fā)送方R分別輸入本方的集合和，輸出并集一個特征向量e給接收方，該特征向量滿足ei=1ifyiEXelseei=0，用于表示對方元素是否屬于交集。在mq-RPMT協(xié)議中，Reverse含義在于接收方得到的表示對方對應(yīng)位置元素是否屬于交集的特征向量，而R得不到對方元素，因此不能通過此特征向量判斷出交集，進(jìn)而保證了交集的安全性。接收方通過RPMT協(xié)議得到反向的特征向量后，在此之上：對對方集合中中"1"對應(yīng)的元素加和即可實現(xiàn)PSI-Card-Sum得到對方集合中中"0"對應(yīng)的元素即可實現(xiàn)PSU4.應(yīng)用場景隱私集合運算技術(shù)重塑了數(shù)據(jù)協(xié)作的邊界，已被廣泛應(yīng)用于多個行業(yè)，以下簡單列舉幾個典型行業(yè)下的應(yīng)用場景和技術(shù)適配方案：1.金融風(fēng)控：通過集合交集計算+差分隱私，銀行與電商平臺協(xié)同識別關(guān)聯(lián)賬戶，共享欺詐黑名單，提升金融反欺詐能力2.醫(yī)療領(lǐng)域：利用集合交集+并集計算，支持醫(yī)院、科研機(jī)構(gòu)在保護(hù)患者隱私的基礎(chǔ)上進(jìn)行病例數(shù)據(jù)歸因和基因關(guān)聯(lián)性分析，助力精準(zhǔn)藥物研發(fā)3.數(shù)字廣告：依托交集去重+頻次控制，廣告主與平臺協(xié)作實現(xiàn)用戶群體的精準(zhǔn)匹配和冷啟動優(yōu)化，避免重復(fù)投放，優(yōu)化營銷效果4.政務(wù)治理：基于交集計算+數(shù)據(jù)差集歸因，稅務(wù)、公安、民政等部門高效實現(xiàn)跨部門身份認(rèn)證、信息共享與風(fēng)險防控，提升公共服務(wù)效率隱私集合運算技術(shù)通過多種密碼技術(shù)的融合，在數(shù)字廣告、金融風(fēng)控與醫(yī)療研究等領(lǐng)域?qū)崿F(xiàn)了跨機(jī)構(gòu)數(shù)據(jù)“可用不可見”的安全協(xié)作。在SDH中，PSO被深度整合為數(shù)據(jù)協(xié)作的“安全基座”，已實現(xiàn)PSI、PCSI、PSU三大核心能力：.PSI：基于橢圓曲線密碼學(xué)提供高效實現(xiàn)，支持兩種曲線選型—Curve25519（通用性最佳）與FourQ（性能最優(yōu)），適配不同場景需求.PCSI：在ECDH-PSI方案中引入置換技術(shù)混淆交集元素位置，在保障交集元素保密性的同時完成交集計數(shù).PSU：自研基于OPRF的高效保序加密算法，并在此基礎(chǔ)上實現(xiàn)了多方元素的安全合并目前，SDH已將上述PSO技術(shù)能力集成于一方人群上翻追投、全域消費者洞察分析、跨域投放效果衡量、全域消費者流轉(zhuǎn)分析、全域投放頻控等多個營銷應(yīng)用場景，實現(xiàn)跨域數(shù)據(jù)的高效流通和隱私安全運算，為廣告主提供跨域安全一致的數(shù)據(jù)決策能力。隨著隱私計算技術(shù)的持續(xù)演進(jìn)，PSO將在更廣泛的領(lǐng)域釋放潛能。一方面，輕量化協(xié)議設(shè)計與硬件加速（如專用加密芯片）將進(jìn)一步降低計算成本，推動PSO向?qū)崟r場景滲透；另一方面，PSO與聯(lián)邦學(xué)習(xí)的融合，對AI領(lǐng)域的發(fā)展具有重大的意義。當(dāng)數(shù)據(jù)孤島被安全技術(shù)打破，人類將首次有機(jī)會在保護(hù)隱私的前提下，釋放數(shù)據(jù)的全部價值，而這正是隱私計算時代賦予我們的全新可能。1.GarimellaG,MohasselP,RosulekM,etal.Privatesetoperationsfromobliviousswitching[C]//IACRInternationalConferenceonPublic-KeyCryptography.Springer,2021:591-617.2.FreedmanMJ,NissimK,Pinkas