一、前言

多頭貸問題是網(wǎng)絡(luò)小額貸款平臺(tái)放款時(shí)所要考慮的一個(gè)重要問題。假設(shè)銀行A有一潛在貸款客戶小張，銀行A為了足夠多的了解小張的信用情況，希望向其他多家銀行查詢小張貸款情況或信用記錄。但因?yàn)楹ε缕渌y行搶走該客戶，所以銀行A不希望泄露自己在查詢小張這一事實(shí)。是否可以通過技術(shù)手段解決銀行A的訴求？答案是肯定的，即圖1漫畫中的“隱私信息檢索技術(shù)”——一種不泄露查詢條件和查詢結(jié)果的加密技術(shù)。

圖1 隱私信息檢索技術(shù)應(yīng)用示例漫畫

隱私信息檢索(Private InformationRetrieval – PIR，也叫匿蹤查詢)是安全多方計(jì)算中很實(shí)用的一項(xiàng)技術(shù)，用來保護(hù)用戶的查詢隱私。其目的是保證用戶向服務(wù)器（數(shù)據(jù)源方）提交查詢請(qǐng)求時(shí)，在用戶查詢信息不被泄漏的條件下完成查詢[1]。即整個(gè)查詢過程中服務(wù)器不知道用戶具體查詢信息及查詢出的數(shù)據(jù)項(xiàng)。

二、為什么可搜索加密技術(shù)無法替代隱私信息檢索技術(shù)

通過前面對(duì)PIR技術(shù)的描述，可知PIR的目的是保護(hù)用戶查詢隱私。提到“保護(hù)用戶查詢隱私”，會(huì)有人想到可搜索加密技術(shù)，但可搜索加密技術(shù)并不能替代PIR技術(shù)。

先來簡(jiǎn)單了解可搜索加密技術(shù)。顧名思義，可搜索加密就是在加密的情況下實(shí)現(xiàn)搜索功能，常用于云計(jì)算當(dāng)中。可搜索加密應(yīng)用示例如圖2所示，能夠?qū)崿F(xiàn)將用戶的數(shù)據(jù)進(jìn)行特殊的加密后上傳到云服務(wù)器上, 并且可以實(shí)現(xiàn)根據(jù)關(guān)鍵字進(jìn)行檢索的功能。（更詳細(xì)內(nèi)容可閱讀本公眾號(hào)文章：防止云端數(shù)據(jù)與查詢行為泄露—可搜索加密）

圖2 可搜索加密應(yīng)用示例

可搜索加密實(shí)現(xiàn)密文檢索時(shí)，過程示例如圖3所示。可簡(jiǎn)單描述為：檢索用戶提交密文關(guān)鍵字（keyword3），云服務(wù)器將密文關(guān)鍵字與密文數(shù)據(jù)庫(kù)比對(duì)，比對(duì)成功后則將對(duì)應(yīng)的密文數(shù)據(jù)（數(shù)據(jù)3）返回給檢索用戶，最終檢索用戶對(duì)拿到的密文數(shù)據(jù)進(jìn)行解密。

圖3 可搜索加密密文檢索示例

整個(gè)過程中云服務(wù)器不知道檢索關(guān)鍵字（keyword3）和檢索結(jié)果（數(shù)據(jù)3）對(duì)應(yīng)的原始明文是什么。但是，數(shù)據(jù)擁有者監(jiān)聽到檢索結(jié)果的話，可以直接解密并得到對(duì)應(yīng)的明文。即可搜索加密技術(shù)僅能阻止云服務(wù)器獲得用戶查詢隱私，不能阻止數(shù)據(jù)擁有者獲得用戶查詢隱私（這很正常，云計(jì)算環(huán)境下，云服務(wù)器中一段密文數(shù)據(jù)的擁有者和檢索者，可能是同一用戶）。

三、3類場(chǎng)景隱私信息檢索方案

為了加強(qiáng)保護(hù)用戶查詢隱私，使得查詢條件和查詢結(jié)果僅查詢用戶可知，安全多方計(jì)算中的PIR技術(shù)應(yīng)運(yùn)而生。目前常見的PIR方案實(shí)現(xiàn)有3類，分別是基于不經(jīng)意傳輸（Oblivious Transfer，OT）的PIR實(shí)現(xiàn)、基于同態(tài)加密的PIR實(shí)現(xiàn)和keyword PIR實(shí)現(xiàn)。其中基于不經(jīng)意傳輸?shù)腜IR和基于同態(tài)加密的PIR需要檢索用戶提前知道被檢索數(shù)據(jù)在服務(wù)端數(shù)據(jù)庫(kù)中索引號(hào)。3類方案的實(shí)現(xiàn)過程介紹如下。

3.1基于不經(jīng)意傳輸?shù)腜IR實(shí)現(xiàn)

基于不經(jīng)意傳輸?shù)腜IR實(shí)現(xiàn)過程如圖4所示（不經(jīng)意傳輸協(xié)議此處不在贅述，更多內(nèi)容可閱讀本公眾號(hào)文章：安全多方計(jì)算(1):不經(jīng)意傳輸協(xié)議），主要利用的是n選1的OT協(xié)議。

圖4 基于不經(jīng)意傳輸?shù)腜IR實(shí)現(xiàn)過程

基于OT的PIR實(shí)現(xiàn)過程有5個(gè)重要步驟：

服務(wù)端有n條數(shù)據(jù)，則產(chǎn)生n個(gè)RSA公私鑰對(duì)，并將n個(gè)私鑰保留，n個(gè)公鑰發(fā)送給用戶端。

用戶隨機(jī)產(chǎn)生一個(gè)大整數(shù)key（key為第5步中的解密密鑰），已知用戶要檢索第t條數(shù)據(jù)，則用戶用收到的第t個(gè)RSA公鑰加密大整數(shù)key，將加密結(jié)果s發(fā)送給服務(wù)端。

服務(wù)端用保留的n個(gè)RSA私鑰，依次嘗試解密s，獲得n個(gè)解密結(jié)果，依次為{key1,key2,…,keyt,…,keyn}。

服務(wù)端利用對(duì)稱加密算法（此處為AES算法），利用key1~keyn，加密對(duì)應(yīng)的消息m1~mn，將產(chǎn)生的密文消息M1~Mn發(fā)送給用戶。

用戶利用第2步中的key，對(duì)第t條密文Mt進(jìn)行對(duì)稱解密，則得到想要檢索的第t條原始明文消息mt。

3.2基于同態(tài)加密的PIR實(shí)現(xiàn)

基于同態(tài)加密的PIR實(shí)現(xiàn)過程如圖5所示，此處采用paillier加法半同態(tài)加密算法[2]，paillier同態(tài)加密算法計(jì)算過程參見文獻(xiàn)2，此處不贅述，但強(qiáng)調(diào)3個(gè)paillier算法特點(diǎn)：（1）可以實(shí)現(xiàn)兩個(gè)密文加法計(jì)算；（2）可以實(shí)現(xiàn)一個(gè)密文與一個(gè)明文相乘；（3）由于加密時(shí)用到隨機(jī)數(shù)，所以相同的明文、相同的密鑰，可以產(chǎn)生很多個(gè)不同的密文，這些不同的密文解密后都能得到相同的原始明文。

圖5 基于同態(tài)加密的PIR實(shí)現(xiàn)過程

基于paillier同態(tài)加密的PIR實(shí)現(xiàn)過程有4個(gè)重要步驟：

用戶端產(chǎn)生同態(tài)加密公鑰pk和私鑰sk。

已知服務(wù)端有n條數(shù)據(jù)，用戶要檢索第t條數(shù)據(jù)，則產(chǎn)生一個(gè)n維密文向量vector={v1,…,vn}，其中第t項(xiàng)是公鑰pk加密數(shù)字1后的密文，其他項(xiàng)是公鑰pk加密數(shù)字0后的密文。將vector和公鑰pk發(fā)送給服務(wù)端，paillier算法第3個(gè)特點(diǎn)保證了vector中的n條密文都不重復(fù)，保證服務(wù)端無法猜出哪一條是數(shù)字1的密文。

服務(wù)端將vector和n條明文數(shù)據(jù)集做向量?jī)?nèi)積運(yùn)算，得到密文結(jié)果en_result，將en_result發(fā)送給用戶端。同態(tài)加密的密文計(jì)算結(jié)果解密后與明文計(jì)算結(jié)果相等，相當(dāng)于en_result=E(m1*0 + … + mt-1*0 + mt*1 + mt+1*0+ … + mn*0, pk) = E(mt, pk)。

用戶端利用私鑰sk對(duì)en_result進(jìn)行解密，得到想要檢索的第t條原始明文消息mt。

3.3keyword PIR實(shí)現(xiàn)

實(shí)際上，在大多數(shù)的查詢場(chǎng)景中，查詢方往往不知道自己要查詢的數(shù)據(jù)的索引號(hào)，而大多根據(jù)關(guān)鍵詞進(jìn)行查詢，此類方案又稱keyword PIR，可以利用paillier同態(tài)加密和拉格朗日插值多項(xiàng)式實(shí)現(xiàn)（拉格朗日插值多項(xiàng)式細(xì)節(jié)可閱讀本公眾號(hào)文章：秘密共享—隱私計(jì)算和區(qū)塊鏈共識(shí)中的榫卯），具體實(shí)現(xiàn)過程如圖6所示。

圖6 keyword PIR實(shí)現(xiàn)過程

keyword PIR實(shí)現(xiàn)過程有5個(gè)重要步驟：

服務(wù)端有明文數(shù)據(jù)集{(x1,m1),…,(xn,mn)}，對(duì)此明文數(shù)據(jù)集進(jìn)行拉格朗日多項(xiàng)式插值，插值結(jié)果即為最高次冪為n-1的多項(xiàng)式g(x)；對(duì)于圖6中的多項(xiàng)式f(x)，f(x) = (x-x1)*(x-x2)*…*(x-xn)，展開后即為圖6中的f(x)。數(shù)據(jù)集中任意一個(gè)點(diǎn)（xi,mi），滿足f(xi)=0，g(xi)=mi。

用戶生成paillier同態(tài)加密公鑰pk和私鑰sk。

對(duì)于待查關(guān)鍵字xt，用戶利用pk分別加密xt的1次方到xt的n次方，組成密文向量vector，發(fā)送給服務(wù)端。

服務(wù)端利用密文向量vector，和f(x)、g(x)的系數(shù)，分別計(jì)算同態(tài)密文E(f(xt))、E(g(xt))，將計(jì)算結(jié)果發(fā)送給用戶。

用戶利用私鑰sk對(duì)兩條密文進(jìn)行解密，如果f(xt)=0，則g(xt)即為檢索結(jié)果；否則檢索結(jié)果為空。

四、方案驗(yàn)證及總結(jié)分析

前文對(duì)3類PIR方案實(shí)現(xiàn)方法做了描述，此處對(duì)3類方法做一個(gè)全面的比對(duì)分析，方便讀者對(duì)3類方案有一個(gè)更直觀的理解。

4.1本文所提PIR方案理論分析

表1所示的表格，分別從依賴技術(shù)、通信開銷、計(jì)算開銷等方面對(duì)3類PIR方案特點(diǎn)做了總結(jié)。

表1 3類PIR方案特點(diǎn)總結(jié)

	依賴技術(shù)	通信量與數(shù)據(jù)集（n條）關(guān)系	需要提前知道被檢索數(shù)據(jù)索引號(hào)	計(jì)算開銷與數(shù)據(jù)集（n條）關(guān)系
基于OT的PIR	公鑰密碼，對(duì)稱密碼	n個(gè)RSA公鑰 n條AES密文	是	n次公鑰解密 n次對(duì)稱加密
基于同態(tài)加密PIR	同態(tài)加密	n+1條同態(tài)密文	是	3n次同態(tài)加密
Keyword-PIR	多項(xiàng)式插值； 同態(tài)加密	n+2條同態(tài)密文	否	5n次同態(tài)加密 2次多項(xiàng)式構(gòu)造

在計(jì)算開銷上，由于同態(tài)加密計(jì)算開銷大于RSA計(jì)算開銷，所以基于OT的PIR方案計(jì)算開銷有優(yōu)勢(shì)；通信開銷上，如果服務(wù)端每條明文數(shù)據(jù)都較長(zhǎng)，如數(shù)千字節(jié)，則基于同態(tài)加密PIR通信開銷較小。

4.2代碼實(shí)例驗(yàn)證

本環(huán)節(jié)，我們用python代碼分別實(shí)現(xiàn)了基于OT的PIR和基于同態(tài)加密的PIR，讓讀者對(duì)PIR性能有更清晰的了解。我們模擬服務(wù)端有一個(gè)漏洞庫(kù)，共有2245條數(shù)據(jù)（數(shù)據(jù)為綠盟真實(shí)漏洞庫(kù)數(shù)據(jù)，原始數(shù)據(jù)數(shù)十萬條，此處僅選取一部分用于實(shí)驗(yàn)），用戶輸入“軟件名稱+具體版本號(hào)”可查詢對(duì)應(yīng)的漏洞信息，查詢過程中不會(huì)泄漏檢索條件和檢索結(jié)果。此部分僅展示用戶獲知檢索項(xiàng)在服務(wù)端中的索引號(hào)后（索引號(hào)如何獲取非本文重點(diǎn)，此處略過），分別模擬利用基于OT的PIR和基于同態(tài)加密的PIR實(shí)現(xiàn)漏洞信息檢索。

圖7 基于OT的PIR代碼實(shí)驗(yàn)結(jié)果

圖7為基于OT的PIR代碼實(shí)現(xiàn)，網(wǎng)絡(luò)為內(nèi)部局域網(wǎng)，服務(wù)端為低配Ubuntu虛擬機(jī)，模擬結(jié)果總耗時(shí)3.3秒，通信開銷RSA公鑰傳輸消耗約0.68MB，全量AES密文傳輸消耗約5.6MB。

圖8 基于paillier同態(tài)加密的代碼實(shí)驗(yàn)結(jié)果

圖8為基于paillier同態(tài)加密的PIR代碼實(shí)現(xiàn)，相同配置下，計(jì)算開銷耗時(shí)117秒，通信開銷密文查詢向量消耗約1.3MB網(wǎng)絡(luò)開銷，檢索結(jié)果傳輸消耗約0.14MB。可以明顯比對(duì)出前兩類PIR方案在計(jì)算開銷和網(wǎng)絡(luò)開銷上的差異。

五、總結(jié)

本文介紹了安全多方計(jì)算中很實(shí)用的一類方案——隱私信息檢索方案，此類方案可在保護(hù)用戶隱私的前提下，實(shí)現(xiàn)多方數(shù)據(jù)安全查詢。另外，分別介紹了3種不同的實(shí)現(xiàn)方法原理，并對(duì)其進(jìn)行理論對(duì)比分析，且對(duì)其中的兩類方法做了代碼實(shí)現(xiàn)。通過理論分析和實(shí)驗(yàn)對(duì)比，能夠讓讀者對(duì)隱私信息檢索有一個(gè)更直觀的認(rèn)識(shí)。

參考文獻(xiàn)

[1]https://blog.csdn.net/hellompc/article/details/103784360

[2]Paillier P . Public-key cryptosystemsbased on composite degree residuosity classes[J]. Advances in CryptologyLeurocrypt, 2004.

往期內(nèi)容：

不經(jīng)意傳輸(OT)-總結(jié)

更新｜Cheetah: 精簡(jiǎn)快速的安全兩方DNN推理

CryptFlow2：實(shí)用兩方安全推理

一個(gè)好用的多方隱私求交算法庫(kù)MultipartyPSI-Pro

隱私保護(hù)深度學(xué)習(xí)技術(shù)綜述

CryptGPU：基于GPU加速的快速隱私保護(hù)機(jī)器學(xué)習(xí)框架

安全多方計(jì)算的安全性 (Security of MPC)