成本攤銷式單服務(wù)器私人情報檢索方法

摘要：私人情報檢索旨在保護(hù)用戶的查詢內(nèi)容和隱私，是情報檢索領(lǐng)域內(nèi)隱私保護(hù)的重要技術(shù)擴(kuò)展?；诔杀緮備N的思想設(shè)計了一種高度可配置、有狀態(tài)的、單服務(wù)器私人情報檢索方案。在一個包含100萬個1 kB元素的數(shù)據(jù)庫上進(jìn)行的實驗表明，該方法能夠在不到1 s的時間內(nèi)響應(yīng)客戶端的查詢請求，同時服務(wù)器的響應(yīng)數(shù)據(jù)僅放大不到3.6倍。值得注意的是，實驗分析基于一個簡單的、未經(jīng)過優(yōu)化的Rust實現(xiàn)，說明該方法在涉及大量客戶端的部署環(huán)境中特別適用。綜上，結(jié)果表明該方法在私人情報檢索領(lǐng)域具有顯著的潛力，并且可以為處理大規(guī)模情報檢索任務(wù)提供高效、經(jīng)濟(jì)實惠的解決方案。

關(guān)鍵詞：情報檢索；單服務(wù)器；在線開銷；攤銷成本；隱私保護(hù)

中圖分類號：G354文獻(xiàn)標(biāo)志碼：A文章編號：1002-4026（2024）05-0122-09

開放科學(xué)（資源服務(wù)）標(biāo)志碼（OSID）：

Cost amortization-based single-server private information retrieval method

CAI Xinyan1， YU Xiao2

（1.Shandong Institute of Scientific and Technical Information，Jinan 250101，China；2.School of Computer Science and Technology，

Shandong University of Finance and Economics， Jinan 250014，China）

Abstract∶Private information retrieval aims to protect users’ query content and privacy， serving as an important extension of privacy protection in the field of information retrieval. A highly configurable， stateful， single-server private information retrieval scheme was designed based on the concept of cost amortization. Experiments conducted on a database containing 1 million 1 kB elements showed that this method delivered superior performance， being able to respond to client queries in less than 1 s， with the server’s response data being increased by less than 3.6 times. It is noteworthy that the experimental analysis was based on a simple， unoptimized Rust implementation， suggesting that this method is particularly suitable for deployment environments involving a large number of clients. Experimental results indicate that this method holds significant potential in the field of private information retrieval and can provide an efficient and cost-effective solution for handling large-scale retrieval tasks.

Key words∶information retrieval; single-server; online overhead; amortized cost; privacy protection

私人情報檢索專注于在保護(hù)用戶隱私的同時，允許用戶從存儲在可能不可信服務(wù)器上的數(shù)據(jù)中檢索信息。傳統(tǒng)的情報檢索方法通常要求用戶將查詢明文發(fā)送給服務(wù)器，這可能導(dǎo)致用戶的查詢內(nèi)容暴露給第三方或中介者。相比之下，私人情報檢索使用加密技術(shù)和安全協(xié)議，使用戶能夠在不泄露查詢內(nèi)容的情況下從服務(wù)器中獲取所需信息［1-4］。例如使用私人情報檢索方案，學(xué)生可以從數(shù)字圖書館取書，而不必向圖書館透露她取的是哪本書。

在現(xiàn)有的研究中，私人情報檢索主要分為有狀態(tài)和無狀態(tài)兩種方案。在無狀態(tài)的私人情報檢索中，使用了加性同態(tài)加密技術(shù)來隱藏客戶端的查詢內(nèi)容［5-7］，這種模式被稱為無狀態(tài)，因為客戶端無需在本地存儲任何信息就能發(fā)起查詢。然而，Sion等［8］研究表明，當(dāng)網(wǎng)絡(luò)帶寬只有

每秒幾百千比特時，這種方案實際上比簡單地讓客戶端下載整個服務(wù)器數(shù)據(jù)庫要差得多［9］，每個客戶機(jī)查詢都要執(zhí)行O（m）個運(yùn)算。此后，研究人員提出了各種方法進(jìn)行優(yōu)化［10-11］。不幸的是，無狀態(tài)方法仍然需要處理計算開銷，這在大規(guī)模部署中變得很具挑戰(zhàn)性。例如，對于一個包含一百萬個每條記錄大小為256字節(jié)的數(shù)據(jù)庫，響應(yīng)一個客戶端的查詢可能需要超過1 s的時間。這種方法在大量客戶端或需要及時響應(yīng)的情況下并不適用。

最近的研究表明，將昂貴且與查詢無關(guān)的計算移至初始的離線階段可以提升在線性能。這種策略可以減少在線成本，并將離線階段的費用分?jǐn)偟蕉鄠€客戶端查詢中［8］。這種模式被稱為有狀態(tài)私人情報檢索。例如，Aguilar-Melchor等［12］使用基于格的密碼學(xué)設(shè)計高效的單服務(wù)器私人情報檢索方法。在他們的方法中，對于m=220個元素的數(shù)據(jù)庫，服務(wù)器計算時間大約為5 s。Corrigan-Gibbs等［5］提出了一個次線性查詢方法。具體來說，當(dāng)客戶端進(jìn)行m次查詢時，成本為O（m），而之前的方法則需要O（m）的計算開銷。與之前的方案相比，最近的研究進(jìn)一步降低了在線成本，但離線階段的成本與之前的研究相似［13-15］。因此，改進(jìn)私人信息檢索算法以降低計算成本是當(dāng)前研究中一個亟待解決的問題。

最近研究采用構(gòu)造具有次線性服務(wù)器端平攤代價的方法。然而，現(xiàn)有實現(xiàn)次線性平攤時間的方法存在局限性，需要多個非串通服務(wù)器的方案，需要許多業(yè)務(wù)實體之間的仔細(xì)協(xié)調(diào)。此外，這些方案的安全性相對脆弱，因為它依賴于攻擊者無法破壞多個服務(wù)器，而不是依賴于加密的硬度。最近的批處理方法要求客戶端在單個非自適應(yīng)批處理中立即完成所有查詢，但不適用于許多自然應(yīng)用程序（例如，數(shù)字圖書館、網(wǎng)頁瀏覽）。

為了解決上述問題，本文旨在提出一項方案來提高私人情報檢索的技術(shù)水平：它們只需要一個數(shù)據(jù)庫服務(wù)器，有次線性的服務(wù)器時間，允許客戶端自適應(yīng)地發(fā)出數(shù)據(jù)庫查詢。本文的方案進(jìn)一步依賴于標(biāo)準(zhǔn)的加密原語，即使當(dāng)許多客戶端查詢單個數(shù)據(jù)庫時，也具有很好的性能。

1研究方法

1.1數(shù)學(xué)符號與定理定義

對于一組向量x1，…，x，用［x1‖…‖x］來表示這些向量組成的矩陣。x表示將向量x中的每個數(shù)四舍五入到最近的整數(shù)。類似地，使用「x表示將x中的每個數(shù)四舍五入到下一個最高的整數(shù)。對于x∈mq，使用xp表示計算 （p/q）x，其中四舍五入適用于x的每個條目。對于某個集合χ，使用x←$χ 表示從χ中均勻地采樣x，而x←$（χ）m表示從m維向量中進(jìn)行采樣，每個條目均勻地從χ中采樣。此外，本文14a99431fc3683cfe7a13cfe0b4428f8用log（x）表示取x的以2為底的對數(shù)。使用λ表示安全參數(shù)，并稱算法在λ的條件下是概率多項式時間可解的。

本文使用LWE問題的決策版本［16-18］，LWE能夠支持構(gòu)建安全的加密算法和協(xié)議，為保護(hù)信息安全提供有力理論支持，具有如下幾個定義：

定義1.1設(shè)χ是某個分布，而q，n，m>0 依賴于λ。決策性 LWE 問題（LWEq，n，m，χ）是要區(qū)分以下兩種情況：

（A，sT·A+eT）∈n×mq×mq

（A，μ）∈n×mq×mq，（1）

其中A←n×mq，sT←（χ）n，eT←（χ）m，μ←$mq。

假設(shè)1.2當(dāng)χ是三元值（即{-1，0，1}）上的均勻分布時，LWEq，n，m，χ問題仍然難以解決。

定義1.3設(shè)χ為某個分布，設(shè)q，n，m>0依賴于λ。MatLWEq，n，m，χ是為了區(qū)分：（A，S·A+E）∈n×mq××mq（A，U）∈n×mq××mq，（2）

其中A←n×mq，S←（χ）×n，E←（χ）×m，U←$×mq。

推論1.4假設(shè)A是對MatLWEq，n，m，χ具有優(yōu)勢ε的PPT對手，則我們可以構(gòu)造一個對 LWEq，n，m，χ具有優(yōu)勢ε/的 PPT 對手 B。

推論1.5對于足夠大的m=poly（λ），從均勻三元值分布（即 {-1， 0， 1}）中抽取的m個樣本的總和不超過4m。

1.2私人情報檢索方案的性質(zhì)

本文使用有狀態(tài)檢索方案，一個優(yōu)異的有狀態(tài)方案必須保證以下內(nèi)容：

（1）正確性。下面的正確性定義確保客戶端以非常大的概率接收到正確響應(yīng)。

定義1.6給定一個數(shù)據(jù)庫DB，對于查詢 xt∈{0，1，…，n－1}，正確的答案是數(shù)據(jù)庫的第x位。為了保證正確性，要求對于任意的q和n，這些量都在多項式級別受到λ的限制，存在一個可以忽略的函數(shù)negl（·），使得對于任意的數(shù)據(jù)庫DB和任意的查詢序列xt∈{0，1，…，n－1}，在使用數(shù)據(jù)庫DB和查詢xt∈{0，1，…，n－1}的誠實執(zhí)行下，檢索方案以概率 1－negl（·）返回所有正確的答案。

（2）安全性。本文使用安全的標(biāo)準(zhǔn)定義來強(qiáng)制執(zhí)行客戶端查詢的不可區(qū)分性。

定義1.7設(shè)DB為服務(wù)器數(shù)據(jù)庫。能夠通過運(yùn)行服務(wù)器設(shè)置生成參數(shù)，服務(wù)器預(yù)處理生成公共參數(shù)，同時能夠運(yùn)行客戶端預(yù)處理生成客戶端狀態(tài)，則說該方案是安全的。上述定義可以擴(kuò)展為指定查詢不可區(qū)分性，即兩個大小為r的客戶端查詢集彼此是不可區(qū)分的［19］。

（3）效率。保證所需的通信開銷比讓客戶機(jī)下載整個服務(wù)器數(shù)據(jù)庫的開銷要小。在有狀態(tài)的情況下，當(dāng)將成本分?jǐn)偟娇蛻舳瞬樵兊臄?shù)量上時，它應(yīng)該成立。

定義1.8對于啟動c條查詢的單個客戶端，如果客戶端通信開銷小于|DB|/c，則該方案是有效的。對于有狀態(tài)方案，總客戶端通信成本計算公式為：comms（離線）+ c·comms（在線）。

1.3方法的具體流程與性質(zhì)滿足

1.3.1加密設(shè)置

加密設(shè)置是保證私人情報檢索中檢索方和服務(wù)器方信息不被泄露的關(guān)鍵所在，是整個方法的第一步。具體來講，假設(shè)DB是一個包含m個元素的數(shù)組，每個元素由w位組成。索引i對應(yīng)于它在數(shù)組中的位置?，F(xiàn)在，假設(shè)有C個客戶端，每個客戶端將對DB發(fā)起最多c個查詢。對于所使用的LWE實例化：設(shè)n和q分別為LWE維數(shù)和模量;令0<ρ<q;設(shè)χ為{-1，0，1}上的均勻分布;λ代表具體的安全參數(shù)。最后，我們使用PRG（μ，x，y，q）表示偽隨機(jī)生成器，該生成器將種子μ←${0，1}λ擴(kuò)展為x×yq的矩陣。

在定義1.3中，我們給出了LWEq，n，m，χ的一個變體，稱為矩陣LWE問題（用MatLWEq，n，m，χ表示）。推論1.4表明，與LWEq，n，m，χ相比，MatLWEq，n，m，χ很難求解，只有多項式安全損失。

1.3.2處理階段

在單服務(wù)器PIR方案中，有兩種有狀態(tài)的機(jī)器稱為客戶端和服務(wù)器端。本文方法包括兩個階段：（1）離線設(shè)置階段只預(yù)先運(yùn)行一次，它發(fā)生在客戶端對服務(wù)器進(jìn)行任何查詢之前。（2）在線階段，這個階段可以重復(fù)多次?？蛻舳讼蚍?wù)器端發(fā)送一條消息，服務(wù)器端響應(yīng)一條消息。接下來將詳細(xì)介紹這兩個階段：

（1）離線階段

服務(wù)器設(shè)置（setup）：服務(wù)器是包含m個元素的數(shù)據(jù)庫，采樣種子μ∈{0，1}λ。

服務(wù)器預(yù)處理（sprec）：服務(wù)器導(dǎo)出矩陣A←PRG（μ，n，m，q），其中A∈n×mq。然后運(yùn)行D←parse（DB，ρ），將DB編碼為矩陣D∈m×ωρ，其中ω=「w/log（ρ）。

為了生成公共參數(shù)，服務(wù)器運(yùn)行M←A·D，然后將（μ，M）∈{0，1}λ×n×ωq發(fā)布到公共存儲庫。

客戶端預(yù)處理（cpreproc）：每個客戶端從公共存儲庫下載（μ，M），并運(yùn)行A←PRG（μ，n，m，q）。然后，客戶端對向量sj←（χ）n，ej←（χ）m進(jìn)行c個采樣。最后，對于每個j∈［c］，計算bj←sTj·A+eTj∈mq，cj←sTj·M∈ωq，并將這些對內(nèi)部存儲為集合X=（bj，cj）j∈［c］。

（2）在線階段

客戶端查詢生成（query）：對于客戶端希望查詢的索引i，客戶端生成向量：fi=（0，…，0，q/ρ，0，…，0），即除fi［i］=p/ρ外的值全為0。然后客戶端從它維護(hù)的內(nèi)部狀態(tài)表中彈出一對（b， c），計算出b～←b+fi∈mq，并將b～發(fā)送給服務(wù)器。

服務(wù)器響應(yīng)（response）：服務(wù)器從客戶端接收b～ ，響應(yīng)c～←b～T·D∈ωq。

客戶端后處理（process）：客戶端接收c～ ，輸出x←c～－cρ∈ωρ。

1.3.3正確性

客戶端后處理階段的輸出為x←c～－cρ∈ωρ。將等式右邊展開得到：

x=c～－cρ=（sT·A+eT+fTi）·D－（sT·A·D）ρ=（e+fi）T·Dρ。（3）

注意到在數(shù)組中第I 行D［i］∈ωρ被解釋為列向量，則證明在數(shù)組中eT·D+fTi·Dρ=fTi·Dρ能夠產(chǎn)生正確的輸出。這就引出了下面的定義：

定義1.9如果q≥8ρ2m，則檢索的結(jié)果有高概率是正確的。

1.3.4隱私性

首先，本文采用了標(biāo)準(zhǔn)的安全性定義，以確保客戶端查詢的不可區(qū)分性。在定義1.7中描述了安全方案的要求和生成參數(shù)的過程。這些步驟是確保系統(tǒng)在實際運(yùn)行中能夠有效抵御各種潛在攻擊的關(guān)鍵措施。其次，可以擴(kuò)展該定義以便更加具體地指定查詢的不可區(qū)分性。這確保無論客戶端查詢的具體細(xì)節(jié)如何，服務(wù)器都無法區(qū)分兩個大小為r的客戶端查詢集。通過定義1.7的擴(kuò)展，系統(tǒng)可以保證在所有交互中，無論是在線階段還是離線階段，都能夠維持高水平的安全性。這種安全性不僅僅是理論上的保證，還需要通過實際的實驗來驗證和證明。

1.4參數(shù)設(shè)置

待配置的方案主要包括以下幾個關(guān)鍵參數(shù)。

（1）具體安全參數(shù)：安全參數(shù)直接影響到系統(tǒng)對于潛在攻擊的抵抗力和數(shù)據(jù)泄露風(fēng)險。

（2）LWE的維數(shù)n和模數(shù)q：這兩個參數(shù)對于LWE問題的求解和加密的強(qiáng)度至關(guān)重要。

（3）采樣分布：使用均勻三元分布來采樣LWE秘密向量和誤差向量，這是保證數(shù)據(jù)安全性和隨機(jī)性的重要手段。

（4）數(shù)據(jù)庫中每個條目的比特數(shù)w和元素個數(shù) m：這些參數(shù)直接影響到服務(wù)器端數(shù)據(jù)庫的大小和查詢的復(fù)雜度。

（5）通信開銷、計算運(yùn)算次數(shù)和存儲開銷：通信開銷涉及到客戶端和服務(wù)器之間的數(shù)據(jù)傳輸量，計算運(yùn)算次數(shù)涉及到加密和解密操作的復(fù)雜度，存儲開銷則關(guān)注服務(wù)器端存儲數(shù)據(jù)的需求和成本。

通過綜合分析和優(yōu)化上述參數(shù)，可以有效地設(shè)計出一個性能優(yōu)越且安全可靠的私人信息檢索系統(tǒng)，實現(xiàn)高效的在線和離線處理。通信開銷如表1所示，存儲開銷如表2所示。顯然，上述參數(shù)都對效率有影響。

1.4.1所需不變量

為了提高效率，本文方法滿足定義1.8，設(shè)c為單個客戶端查詢的上界，此時可以得出：λ+nωlog（q）+c（m+ω）log（q）<mω，其次，為了正確性，方法滿足q≥8ρ2m成立。最后，對于安全性，MatLWEq，n，m，χ，必須提供至少128位的具體經(jīng)典安全性。本文用格安全估計器估計LWE實例的具體安全性。

1.4.2調(diào)整LWE參數(shù)

在配置本文方法用來提高效率之前，要確定一組參數(shù)，以提供必要的具體安全保證。首先，χ是均勻三元分布。其次，設(shè)置q=232，這允許本文使用標(biāo)準(zhǔn)的32位無符號整數(shù)操作來實現(xiàn)Zq操作。第三，設(shè)n=1 774為LWE維數(shù)。利用Albrecht等［20］的工作，可以得出v=LWEq，n，m，χ，然后利用原始USVP代價模型計算出具體的安全性參數(shù)為λ=v－log（推論1.4）。由于是服務(wù)器觀察到的查詢總數(shù)，我們設(shè)置=252作為一個合適的上界。達(dá)到上界后，A被重置，方案的安全性也被重置。因此，λ=v－52。

以上分析表明，對于大量的查詢，實例的具體安全性將隨著查詢數(shù)量的增加而多項式地降低——直到重新采樣一個新的LWE矩陣A。目前還不存在以這種方式對MatLWEq，n，m，χ，的安全性進(jìn)行攻擊。因此，在允許較小的維度n時，通過簡單地估計較小的值的安全性，或僅估計v=LWEq，n，m，χ的安全性是有價值的。

1.4.3數(shù)據(jù)庫推薦參數(shù)

設(shè)κ=（log（ρ）·m）/（n·log（q））表示與原始DB大小相比，相對于離線客戶端下載的改進(jìn)因子。表3給出了本文方法的推薦參數(shù)設(shè)置。對于252個客戶端查詢，具體的安全參數(shù)為128位。安全性通過增加維數(shù)n來提高，但這會降低κ。

2實驗分析

在性能基準(zhǔn)測試中，我們選擇Amazon t2.2xlarge EC2實例作為測試平臺，該實例配備8個CPU內(nèi)核和32 GB RAM，以確保實驗的穩(wěn)定性和可靠性。所有的計算成本均按照CPU處理時間計算。帶寬成本基于λ=128的詳細(xì)開銷表格計算，具體數(shù)據(jù)顯示從服務(wù)器到客戶端的數(shù)據(jù)傳輸成本為0.09 美元/GB，而客戶端到服務(wù)器的數(shù)據(jù)傳輸成本則免費。此外，計算成本為0.371 2 美元/h，相當(dāng)于每CPU每小時0.046 4 美元。單個服務(wù)器數(shù)據(jù)庫的參數(shù)設(shè)置見表3，以提供非平攤的通信和計算基準(zhǔn)。

我們選定w=213位，對應(yīng)1 kB的數(shù)據(jù)庫元素大?。划?dāng)數(shù)據(jù)庫元素數(shù)m ≤ 218時，設(shè)置ρ=210，否則為29。我們的實驗參數(shù)設(shè)計可以為大約252個客戶端查詢提供了128位安全性。這一安全性級別可以通過增加LWE維數(shù)n來進(jìn)一步提高。總體來說，我們的實驗框架和參數(shù)選擇旨在提供一個全面的性能評估，確保方案在各種應(yīng)用場景下均能表現(xiàn)出色。這些成本和性能數(shù)據(jù)不僅幫助我們驗證了方案的可行性和效果，還將其與現(xiàn)有的PSIR［15］和SOnionPIR［6］方法進(jìn)行了比較，展示了其在多個維度上的優(yōu)勢和競爭力。表4和表5給出了本文方法與以前的無狀態(tài)/有狀態(tài)檢索方案之間的功能、效率和粗略的財務(wù)比較。

2.1性能結(jié)果

本文方法的非平攤性能如表6所示。這包括計算運(yùn)行與單個客戶端交互的單線程服務(wù)器實例的運(yùn)行時間和帶寬使用情況。隨后，分析了離線成本如何在perquery的基礎(chǔ)上攤銷。攤銷根據(jù)可變數(shù)量的客戶端C和每個客戶端查詢的數(shù)量c來計算（我們將所有實驗的C設(shè)置為500）。

在離線階段，服務(wù)器首先生成數(shù)據(jù)庫矩陣DB和公共參數(shù)。這個過程與客戶端無關(guān)，其復(fù)雜度是線性的。具體而言，服務(wù)器會從一個單一的λ位種子計算得到假隨機(jī)派生的LWE矩陣。一旦公共參數(shù)生成完畢并且客戶端下載完成，客戶端開始對每個查詢進(jìn)行與查詢內(nèi)容無關(guān)的預(yù)處理。這些預(yù)處理的結(jié)果會在在線階段使用，這些成本大致呈線性增長，與m成正比。

在通信方面，服務(wù)器發(fā)布λ位種子μ和矩陣M∈n×ωq，其中ω=w/log（ρ）。對于log（ρ）的每個選擇，客戶機(jī)下載的大小是靜態(tài)的。因此，總成本只在增加m導(dǎo)致ρ必須減小時才會增長。

在線階段，客戶端的計算任務(wù)主要包括兩個方面：首先是執(zhí)行單個加法操作，用于修改預(yù)處理數(shù)據(jù)的特定部分。其次，客戶端需要對服務(wù)器返回的響應(yīng)進(jìn)行少量的后處理，這一步驟幾乎在所有實驗中都表現(xiàn)出靜態(tài)性質(zhì)，因為它與參數(shù)ω成線性關(guān)系，且與數(shù)據(jù)庫大小無關(guān)。在服務(wù)器端，主要的計算成本集中在處理客戶端的查詢請求上。不論數(shù)據(jù)庫的規(guī)模如何，服務(wù)器能夠在每次查詢中處理的時間都控制在0.83 s以內(nèi)。此外，通信成本主要取決于客戶端的查詢內(nèi)容，通常為mlog（q）位，這與數(shù)據(jù)庫的大小成正比關(guān)系。關(guān)于服務(wù)器響應(yīng)的大小，它通常遠(yuǎn)小于查詢時傳輸?shù)臄?shù)據(jù)量。具體來說，服務(wù)器響應(yīng)的大小大約為ωlog（q）位，這相對于原始的1 kB數(shù)據(jù)元素的大小增加不到3.6倍。這種低開銷的響應(yīng)確保了在處理和傳輸數(shù)據(jù)時的高效性和經(jīng)濟(jì)性。

離線階段的攤銷是實現(xiàn)系統(tǒng)經(jīng)濟(jì)性和性能優(yōu)化的關(guān)鍵部分。在系統(tǒng)啟動時，許多離線成本可以在服務(wù)的查詢數(shù)量上分?jǐn)?，這對于成本效益至關(guān)重要。在表6中列出的離線成本包括數(shù)據(jù)庫預(yù)處理、參數(shù)生成和客戶端下載。這些成本可以通過在一定查詢量范圍內(nèi)分?jǐn)倎盹@著減少每個查詢的實際成本。例如，數(shù)據(jù)庫預(yù)處理和參數(shù)生成步驟的攤銷率可以根據(jù)服務(wù)的查詢數(shù)量進(jìn)行計算，使得在處理1 000到1×106個查詢時，每個查詢的離線成本相對較低而更加可控。類似地，客戶端的離線預(yù)處理和下載成本也可以在客戶群體中分?jǐn)?，進(jìn)一步降低每個客戶端的成本。存儲成本也是一個重要的考慮因素。隨著數(shù)據(jù)庫大小增長，客戶端存儲開銷也會增加。當(dāng)數(shù)據(jù)庫大小達(dá)到220時，存儲開銷可能會顯著增加，達(dá)到約2 GB。針對存儲受限的客戶端，可以通過實現(xiàn)log（m）的客戶端存儲開銷來減少存儲需求。這種方法雖然能夠節(jié)省存儲空間，但在在線查詢處理時可能會引入額外的計算負(fù)擔(dān)。通過合理的成本分?jǐn)偤痛鎯?yōu)化策略，可以有效控制運(yùn)營成本和提高用戶體驗。

財務(wù)成本：對于一個220大小的數(shù)據(jù)庫，服務(wù)器端數(shù)據(jù)庫的初始預(yù)處理費用略高于1 美分。每個查詢的在線成本非常低，即使對于最大的數(shù)據(jù)庫大小，也只有大約0.001 美分。

2.2與其他方法對比

在安全性方面，本文方法提供了128位的安全性保證，它能夠抵抗包括強(qiáng)大的計算資源在內(nèi)的廣泛攻擊。這種高安全性級別適用于多達(dá)10億個客戶端查詢的情況，確保了即使在極端情況下，例如量子計算機(jī)的威脅下，系統(tǒng)仍能保持穩(wěn)固的保護(hù)。相比之下，SOnionPIR和PSIR提供的安全性最高為115位。雖然它們可以通過增加安全參數(shù)來提高安全級別，但這會導(dǎo)致服務(wù)器在處理大量并發(fā)查詢時在線響應(yīng)顯著增加。因此，本文方法在提供更高安全性的同時，通過有效的算法設(shè)計和參數(shù)選擇，盡量避免了在在線階段引入過多的計算成本。這使得它在安全性和性能之間取得了良好的平衡。

在計算方面，PSIR中的客戶端必須下載整個服務(wù)器數(shù)據(jù)庫，以便在本地進(jìn)行查詢處理。這種設(shè)計使得客戶端必須消耗大量的帶寬和存儲資源來處理大量數(shù)據(jù)。相比之下，本文方法在計算上的成本與數(shù)據(jù)庫大小呈現(xiàn)線性增長。具體來說，隨著數(shù)據(jù)庫中數(shù)據(jù)量的增加，預(yù)處理階段和在線查詢響應(yīng)的計算成本也會相應(yīng)增加。這種線性關(guān)系使得本文方法能夠根據(jù)需要靈活地調(diào)整成本和性能之間的平衡點。盡管在單個客戶端的情況下，SOnionPIR可能在計算效率上優(yōu)于本文方法，但隨著查詢負(fù)載的增加，SOnionPIR在服務(wù)器和網(wǎng)絡(luò)資源方面的消耗也會顯著上升。與此相反，本文方法中的所有預(yù)處理都與具體的客戶端無關(guān)，這意味著無論查詢負(fù)載c或客戶端數(shù)量C如何變化，預(yù)處理和在線查詢響應(yīng)的成本都保持固定。這種特性使得本文方法在大規(guī)模多客戶端環(huán)境中表現(xiàn)出色，尤其是在需要處理高并發(fā)查詢和大量數(shù)據(jù)時，能夠顯著降低整體系統(tǒng)的運(yùn)營成本和復(fù)雜度。

在在線階段，PSIR方案以其高效的計算時間脫穎而出，這主要得益于其基于客戶端的數(shù)據(jù)處理方式。PSIR要求客戶端下載整個服務(wù)器數(shù)據(jù)庫，使得在本地進(jìn)行查詢處理成為可能。與此同時，本文方法和SOnionPIR在在線計算時間上仍然保持著競爭力。特別是對于本文方法而言，在包含220個元素的數(shù)據(jù)庫上，響應(yīng)客戶端查詢的時間不超過0.825 s。這表明了本文方法在處理大規(guī)模數(shù)據(jù)集時的高效性和可靠性，能夠滿足對低延遲和高吞吐量的嚴(yán)格要求。SOnionPIR隨著查詢負(fù)載的增加，其計算時間和資源消耗也會顯著增加。相比之下，本文方法在整體設(shè)計上考慮了計算成本的線性增長，并通過預(yù)處理階段的優(yōu)化來減少在線階段的負(fù)擔(dān)。

3總結(jié)

傳統(tǒng)上，私人情報檢索技術(shù)面臨著實現(xiàn)成本高昂和效率低下的挑戰(zhàn)，特別是在需要處理大規(guī)模數(shù)據(jù)和保護(hù)用戶隱私的應(yīng)用場景中。為了解決這些問題，本文通過成本互攤的方案設(shè)計了一種靈活高效的單服務(wù)器方法。采用Rust編程語言，顯著提升了系統(tǒng)的安全性和執(zhí)行效率。本文方法的另一個突出特點是其在實現(xiàn)成本方面的優(yōu)勢。通過簡化和優(yōu)化有狀態(tài)方案的設(shè)計，降低了部署和維護(hù)的成本，使得這項技術(shù)更加可行和可接受，不僅僅局限于高端應(yīng)用或研究領(lǐng)域，也適用于商業(yè)化和大規(guī)模應(yīng)用的場景。綜上，本文方法不僅為數(shù)據(jù)安全和隱私保護(hù)提供了可靠的解決方案，也為未來的數(shù)據(jù)密集型應(yīng)用和服務(wù)開發(fā)提供了新的可能性和機(jī)會。

參考文獻(xiàn)：

［1］ANGEL S， SETTY S. Unobservable communication over fully untrusted infrastructure［C］// Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2016： 551-569.

［2］ZHOU M X， PARK A， SHI E， et al. Piano： extremely simple， single-server PIR with sublinear server computation［J］. IACRCryptol EPrint Arch， 2023， 2023： 452.

［3］MENON S J， WU D J. YPIR： high-throughput single-server PIR with silent preprocessing ［EB/OL］. ［2024-06-20］. https：//www.cs.utexas.edu/～dwu4/papers/YPIR.pdf.

［4］ULUKUS S， AVESTIMEHR S， GASTPAR M， et al.Private retrieval， computing， and learning： Recent progress and future challenges［J］. IEEE Journal on Selected Areas in Communications， 2022， 40（3）： 729-748. DOI： 10.1109/JSAC.2022.3142358.

［5］CORRIGAN-GIBBS H， HENZINGER A， KOGAN D. Single-server private information retrieval with Sublinear amortized time［M］//DUNKELMAN O， DZIEMBOWSKI S. Lecture Notes in Computer Science. Cham： Springer International Publishing， 2022： 3-33. DOI： 10.1007/978-3-031-07085-3_1.

［6］MUGHEES M H， CHEN H， REN L. OnionPIR： response efficient single-server PIR［C］// CCS ′21： Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York， USA： Association for Computing Machinery， 2021： 2292-2306. DOI： 10.1145/3460120.3485381.

［7］PATEL S， PERSIANO G， YEO K. Private stateful information retrieval［C］// PROCEEDINGS OF THE 2018 ACM Sigsac Conference On Computer and Communications Security （CCS′18）. Toronto， CANADA： ACM， 2018.1002-1019. DOI：10.1145/3243734.3243821.

［8］SION R， CARBUNAR B. On the practicality of private information retrieval［EB/OL］.［2024-06-20］. https：//users.cs.fiu.edu/～carbunar/pir.pdf.

［9］KUSHILEVITZ E， OSTROVSKY R. Replication is not needed： Single database， computationally-private information retrieval［C］//Proceedings 38th Annual Symposium on Foundations of Computer Science. Miami Beach， FL， USA. IEEE， 1997： 364-373. DOI： 10.1109/SFCS.1997.646125.

［10］CACHIN C， MICALI S， STADLER M. Computationally private information retrieval with polylogarithmic communication［M］//Lecture Notes in Computer Science. Berlin， Heidelberg： Springer Berlin Heidelberg， 1999： 402-414. DOI： 10.1007/3-540-48910-x_28.

［11］GENTRY C， RAMZAN Z. Single-database private information retrieval with constant communication rate［M］//Lecture Notes in Computer Science. Berlin， Heidelberg： Springer Berlin Heidelberg， 2005： 803-815. DOI： 10.1007/11523468_65.

［12］AGUILAR-MELCHOR C， BARRIER J， FOUSSE L， et al. XPIR： Private information retrieval for everyone［J］. Proceedings on Privacy Enhancing Technologies， 2016， 2016（2）： 155-174. DOI： 10.1515/popets-2016-0010.

［13］MENON S J， WU D J. SPIRAL： Fast， high-rate single-server PIR via FHE composition［C］//2022 IEEE Symposium on Security and Privacy （SP）. San Francisco， CA， USA. IEEE， 2022： 930-947. DOI： 10.1109/SP46214.2022.9833700.

［14］ANGEL S， CHEN H， LAINE K， et al. PIR with compressed queries and amortized query processing［C］//2018 IEEE Symposium on Security and Privacy （SP）. San Francisco， CA， USA. IEEE， 2018： 962-979. DOI： 10.1109/SP.2018.00062.

［15］CORRIGAN-GIBBS H， KOGAN D. Private information retrieval with sublinear online time［C］// CANTEAUT A， ISHAI Y. 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT）. Zagreb， Croatia： Int Assoc Cryptol Res， 2020： 44-75.

［16］REGEV O. On lattices， learning with errors， random linear codes， and cryptography［J］.JOURNAL OF THE ACM， 2009，56（6）：34. DOI： 10.1145/1568318.1568324.

［17］BRAKERSKI Z， LANGLOIS A， PEIKERT C， et al. Classical hardness of learning with errors［C］// STEHLé D. 45th Annual ACM Symposium on the Theory of Computing （STOC）. Palo Alto， CA： Assoc Comp Machinery Special Interest Grp Algorithms & Computat Theory，2013： 575-584.

［18］MICCIANCIO D， PEIKERT C. Trapdoors for lattices： Simpler， tighter， faster， smaller［J］. IACRCryptol EPrint Arch， 2012， 2011： 501. DOI： 10.1007/978-3-642-29011-4_41.

［19］PATEL S， PERSIANO G， YEO K. Private stateful information retrieval［C］// Proceedings of the 2018 Acm Sigsac Conference on Computer and Communications Security （CCS′18）. New York， USA： Assoc Comp Machinery， 2018：1002-1019. DOI：10.1145/3243734.3243821.

［20］ALBRECHT M R， PLAYER R， SCOTT S. On the concrete hardness of learningwitherrors［J］. Mathematical Cryptology， 2015， 9（3）：169-203.