[發明專利]采用亞線性公鑰操作的私有信息檢索

在審

• 申請號: 201880095465.6
• 申請日: 2018-05-07
• 公開（公告）號: CN112400171A
• 公開（公告）日: 2021-02-23
• 發明（設計）人: 沙瓦·帕特爾;凱文·楊;朱塞佩·佩爾夏諾
• 申請（專利權）人: 谷歌有限責任公司
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 上海華誠知識產權代理有限公司 31300
• 代理人: 肖華

方法(500)包括通過執行私有批量求和檢索指令(200)來計算來自不可信存儲設備(150)的數據塊(102)的c個總和O，以初始化客戶端設備(120)上的客戶端狀態(250)c個總和O。每個計算出的總和O存儲在客戶端設備的存儲器硬件(122)上，并且包括正好k個數據塊的對應子集S的總和。所述方法還包括查詢指令(300)，通過遍歷數據塊的c個總和O中的每一個來識別不包括查詢塊B_q的c個總和O之一，指示服務將不可信存儲設備偽隨機地劃分為多個分區并對每個分區中的數據塊求和以確定對應的加密數據塊總和(302)，以檢索存儲在不可信存儲設備上的查詢塊B_q的c個總和O。

技術領域

本公開涉及采用亞線性加密操作的私有信息檢索。

背景技術

企業和個人正在使用分布式存儲系統(例如，云存儲服務)將數據存儲在位于多個存儲器位置上的存儲器中。為了使用云存儲服務提供的基本功能(例如對存儲的數據執行搜索查詢)，企業需要向云存儲服務提供純文本訪問。由此，雖然云存儲服務提高了便利性和成本優勢，許多政府和敏感的私營部門(例如衛生，金融和法律)仍不愿使用云存儲服務。例如，用戶的數據訪問模式可以提供有關數據和/或用戶的大量信息。

私有信息檢索(PIR)方案允許用戶從一個或多個存儲設備檢索數據，而不會向托管一個或多個存儲設備的服務器透露有關用戶或檢索到的數據的任何信息。對于PIR，服務器存儲設備通常不受保護，而且，私有信息被一組允許從整個存儲設備下載數據的用戶從公共存儲設備或服務器存儲設備中檢索。盡管用戶可以簡單地從服務器存儲設備下載所有內容，而不會透露訪問模式，但是當不得不從跨多個存儲設備的云存儲服務下載所有內容時，將花費很長時間。此外，允許訪問多個用戶的傳統的PIR方案一般要求用戶是無狀態的，以便允許同步的且獨立的查詢而沒有用戶之間的碰撞或沖突。由于用戶不保持任何狀態，因此這些傳統的PIR方案在計算上很昂貴，需要服務器對具有n個塊的數據庫執行Ω(n)加密操作。

發明內容

在具有多個客戶端的單服務器私有信息檢索(PIR)系統中，服務器將在存儲資源上存儲一組純文本數據塊。當服務器負責生成和存儲數據塊時，從存儲資源中檢索特定數據塊的客戶端希望保證服務器將無法識別客戶端檢索了哪個數據塊。例如，純文本數據塊可以包括服務器為不同應用的多樣性而生成和分發的機器學習模型。如果客戶端在該純文本中檢索到機器學習模型，則服務器以及最終與服務器相關聯的實體將能夠在沒有PIR提供的保證的情況下了解有關客戶端的重要私有信息。

在使用兩個或多個服務器的現有PIR協議中，每個服務器共同負責托管純文本數據以提供多個客戶端的訪問，假設服務器是非沖突的，即，服務器沒有相互共享信息。但是，在現實情況下，多服務器PIR協議是不可行的，因為與共同托管純文本數據的服務器相關聯的不同實體可能成為彼此的競爭者。另一方面，采用單服務器的現有PIR協議要求客戶端設備不保持狀態，以確保客戶端設備可以同時彼此獨立地訪問純文本數據塊。但是，隨著諸如智能電話的現代客戶端設備允許應用存儲100MB的數據，由于單個服務器必須執行的加密操作的數量，無狀態客戶端的需求既浪費又計算量巨大。

本文的實施例針對采用異步客戶端存儲模型的單服務器PIR例程，其中允許每個客戶端獨立于其他客戶端的狀態而保持狀態。因此，在對存儲在服務器管理的存儲資源上的純文本數據塊執行查詢之后，客戶端設備可以獨立于其他客戶端設備的狀態來更新其狀態。類似地，當客戶端的狀態丟失時，只有該客戶端需要與服務器執行計算以重新獲得該狀態。由于允許客戶端利用它們的本地存儲來彼此獨立保持狀態，因此單服務器PIR例程通過最小化確保數據塊以對服務器不經意的方式被檢索所需的加密操作的數量，極大地提高了計算效率。例如，一百萬個加密操作(求冪)需要幾分鐘的CPU時間，而一百萬個純文本操作(例如，加法/異或)需要的時間少于一秒。