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

摘要：私人情報檢索旨在保護用戶的查詢內容和隱私，是情報檢索領域內隱私保護的重要技術擴展。基于成本攤銷的思想設計了一種高度可配置、有狀態的、單服務器私人情報檢索方案。在一個包含100萬個1 kB元素的數據庫上進行的實驗表明，該方法能夠在不到1 s的時間內響應客戶端的查詢請求，同時服務器的響應數據僅放大不到3.6倍。值得注意的是，實驗分析基于一個簡單的、未經過優化的Rust實現，說明該方法在涉及大量客戶端的部署環境中特別適用。綜上，結果表明該方法在私人情報檢索領域具有顯著的潛力，并且可以為處理大規模情報檢索任務提供高效、經濟實惠的解決方案。

關鍵詞：情報檢索；單服務器；在線開銷；攤銷成本；隱私保護

中圖分類號：G354文獻標志碼：A文章編號：1002-4026（2024）05-0122-09

開放科學（資源服務）標志碼（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

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

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

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

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

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

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

1研究方法

1.1數學符號與定理定義

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

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

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

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

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

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

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

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

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

推論1.4假設A是對MatLWEq，n，m，χ具有優勢ε的PPT對手，則我們可以構造一個對 LWEq，n，m，χ具有優勢ε/的 PPT 對手 B。

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

1.2私人情報檢索方案的性質

本文使用有狀態檢索方案，一個優異的有狀態方案必須保證以下內容：

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

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

（2）安全性。本文使用安全的標準定義來強制執行客戶端查詢的不可區分性。

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

（3）效率。保證所需的通信開銷比讓客戶機下載整個服務器數據庫的開銷要小。在有狀態的情況下，當將成本分攤到客戶端查詢的數量上時，它應該成立。

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

1.3方法的具體流程與性質滿足

1.3.1加密設置

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

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

1.3.2處理階段

在單服務器PIR方案中，有兩種有狀態的機器稱為客戶端和服務器端。本文方法包括兩個階段：（1）離線設置階段只預先運行一次，它發生在客戶端對服務器進行任何查詢之前。（2）在線階段，這個階段可以重復多次。客戶端向服務器端發送一條消息，服務器端響應一條消息。接下來將詳細介紹這兩個階段：

（1）離線階段

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

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

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

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

（2）在線階段

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

服務器響應（response）：服務器從客戶端接收b～ ，響應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）

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

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

1.3.4隱私性

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

1.4參數設置

待配置的方案主要包括以下幾個關鍵參數。

（1）具體安全參數：安全參數直接影響到系統對于潛在攻擊的抵抗力和數據泄露風險。

（2）LWE的維數n和模數q：這兩個參數對于LWE問題的求解和加密的強度至關重要。

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

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

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

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

1.4.1所需不變量

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

1.4.2調整LWE參數

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

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

1.4.3數據庫推薦參數

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

2實驗分析

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

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

2.1性能結果

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

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

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

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

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

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

2.2與其他方法對比

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

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

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

3總結

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

參考文獻：

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