一、前言

多頭貸問題是網絡小額貸款平臺放款時所要考慮的一個重要問題。假設銀行A有一潛在貸款客戶小張，銀行A為了足夠多的了解小張的信用情況，希望向其他多家銀行查詢小張貸款情況或信用記錄。但因為害怕其他銀行搶走該客戶，所以銀行A不希望泄露自己在查詢小張這一事實。是否可以通過技術手段解決銀行A的訴求？答案是肯定的，即圖1漫畫中的“隱私信息檢索技術”——一種不泄露查詢條件和查詢結果的加密技術。

圖1 隱私信息檢索技術應用示例漫畫

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

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

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

先來簡單了解可搜索加密技術。顧名思義，可搜索加密就是在加密的情況下實現搜索功能，常用于云計算當中?？伤阉骷用軕檬纠鐖D2所示，能夠實現將用戶的數據進行特殊的加密后上傳到云服務器上, 并且可以實現根據關鍵字進行檢索的功能。（更詳細內容可閱讀本公眾號文章：防止云端數據與查詢行為泄露—可搜索加密）

圖2 可搜索加密應用示例

可搜索加密實現密文檢索時，過程示例如圖3所示?？珊唵蚊枋鰹椋簷z索用戶提交密文關鍵字（keyword3），云服務器將密文關鍵字與密文數據庫比對，比對成功后則將對應的密文數據（數據3）返回給檢索用戶，最終檢索用戶對拿到的密文數據進行解密。

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

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

三、3類場景隱私信息檢索方案

為了加強保護用戶查詢隱私，使得查詢條件和查詢結果僅查詢用戶可知，安全多方計算中的PIR技術應運而生。目前常見的PIR方案實現有3類，分別是基于不經意傳輸（Oblivious Transfer，OT）的PIR實現、基于同態加密的PIR實現和keyword PIR實現。其中基于不經意傳輸的PIR和基于同態加密的PIR需要檢索用戶提前知道被檢索數據在服務端數據庫中索引號。3類方案的實現過程介紹如下。

3.1基于不經意傳輸的PIR實現

基于不經意傳輸的PIR實現過程如圖4所示（不經意傳輸協議此處不在贅述，更多內容可閱讀本公眾號文章：安全多方計算(1):不經意傳輸協議），主要利用的是n選1的OT協議。

圖4 基于不經意傳輸的PIR實現過程

基于OT的PIR實現過程有5個重要步驟：

服務端有n條數據，則產生n個RSA公私鑰對，并將n個私鑰保留，n個公鑰發送給用戶端。

用戶隨機產生一個大整數key（key為第5步中的解密密鑰），已知用戶要檢索第t條數據，則用戶用收到的第t個RSA公鑰加密大整數key，將加密結果s發送給服務端。

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

服務端利用對稱加密算法（此處為AES算法），利用key1~keyn，加密對應的消息m1~mn，將產生的密文消息M1~Mn發送給用戶。

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

3.2基于同態加密的PIR實現

基于同態加密的PIR實現過程如圖5所示，此處采用paillier加法半同態加密算法[2]，paillier同態加密算法計算過程參見文獻2，此處不贅述，但強調3個paillier算法特點：（1）可以實現兩個密文加法計算；（2）可以實現一個密文與一個明文相乘；（3）由于加密時用到隨機數，所以相同的明文、相同的密鑰，可以產生很多個不同的密文，這些不同的密文解密后都能得到相同的原始明文。

圖5 基于同態加密的PIR實現過程

基于paillier同態加密的PIR實現過程有4個重要步驟：

用戶端產生同態加密公鑰pk和私鑰sk。

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

服務端將vector和n條明文數據集做向量內積運算，得到密文結果en_result，將en_result發送給用戶端。同態加密的密文計算結果解密后與明文計算結果相等，相當于en_result=E(m1*0 + … + mt-1*0 + mt*1 + mt+1*0+ … + mn*0, pk) = E(mt, pk)。

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

3.3keyword PIR實現

實際上，在大多數的查詢場景中，查詢方往往不知道自己要查詢的數據的索引號，而大多根據關鍵詞進行查詢，此類方案又稱keyword PIR，可以利用paillier同態加密和拉格朗日插值多項式實現（拉格朗日插值多項式細節可閱讀本公眾號文章：秘密共享—隱私計算和區塊鏈共識中的榫卯），具體實現過程如圖6所示。

圖6 keyword PIR實現過程

keyword PIR實現過程有5個重要步驟：

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

用戶生成paillier同態加密公鑰pk和私鑰sk。

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

服務端利用密文向量vector，和f(x)、g(x)的系數，分別計算同態密文E(f(xt))、E(g(xt))，將計算結果發送給用戶。

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

四、方案驗證及總結分析

前文對3類PIR方案實現方法做了描述，此處對3類方法做一個全面的比對分析，方便讀者對3類方案有一個更直觀的理解。

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

表1所示的表格，分別從依賴技術、通信開銷、計算開銷等方面對3類PIR方案特點做了總結。

表1 3類PIR方案特點總結

	依賴技術	通信量與數據集（n條）關系	需要提前知道被檢索數據索引號	計算開銷與數據集（n條）關系
基于OT的PIR	公鑰密碼，對稱密碼	n個RSA公鑰 n條AES密文	是	n次公鑰解密 n次對稱加密
基于同態加密PIR	同態加密	n+1條同態密文	是	3n次同態加密
Keyword-PIR	多項式插值； 同態加密	n+2條同態密文	否	5n次同態加密 2次多項式構造

在計算開銷上，由于同態加密計算開銷大于RSA計算開銷，所以基于OT的PIR方案計算開銷有優勢；通信開銷上，如果服務端每條明文數據都較長，如數千字節，則基于同態加密PIR通信開銷較小。

4.2代碼實例驗證

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

圖7 基于OT的PIR代碼實驗結果

圖7為基于OT的PIR代碼實現，網絡為內部局域網，服務端為低配Ubuntu虛擬機，模擬結果總耗時3.3秒，通信開銷RSA公鑰傳輸消耗約0.68MB，全量AES密文傳輸消耗約5.6MB。

圖8 基于paillier同態加密的代碼實驗結果

圖8為基于paillier同態加密的PIR代碼實現，相同配置下，計算開銷耗時117秒，通信開銷密文查詢向量消耗約1.3MB網絡開銷，檢索結果傳輸消耗約0.14MB?？梢悦黠@比對出前兩類PIR方案在計算開銷和網絡開銷上的差異。

五、總結

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

參考文獻

[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.

往期內容：

不經意傳輸(OT)-總結

更新｜Cheetah: 精簡快速的安全兩方DNN推理

CryptFlow2：實用兩方安全推理

一個好用的多方隱私求交算法庫MultipartyPSI-Pro

隱私保護深度學習技術綜述

CryptGPU：基于GPU加速的快速隱私保護機器學習框架

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