[發明專利]一種單輪交互的鏈表ORAM訪問方法

有效

• 申請號: 202110054402.X
• 申請日: 2021-01-15
• 公開（公告）號: CN112966294B
• 公開（公告）日: 2022-09-09
• 發明（設計）人: 吳志強;蔡竹斌;李文軍;王進;鄭少瑩;唐小勇
• 申請（專利權）人: 長沙理工大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F21/60;G06F3/06;G06F16/27;G06F16/22
• 代理公司: 北京迎碩知識產權代理事務所(普通合伙) 11512
• 代理人: 錢揚保;張群峰

本發明公開了一種生成鏈表樹的方法，其中：所述鏈表樹LL?tree是加密的滿二叉樹，所述方法包括生成鏈表樹的各個鏈表樹節點LL?tree node，所述鏈表樹節點包括頭部head和尾部tail，如下：

技術領域

本發明屬于信息安全領域，尤其涉及一種單輪交互的鏈表ORAM 訪問方法，可以應用于安全云存儲系統以及安全計算領域。

背景技術

為了無限廉價計算和存儲資源，很多公司和用戶都將他們的 私有數據外包給云。如果直接將用戶數據以明文形式存儲在云服 務器，不可信云服務提供商或者其他攻擊者可以直接獲取用戶隱 私信息。為了保證用戶隱私數據不被惡意竊取，傳統的手段是對 數據內容進行加密，通過上傳、下載密文數據來使用個人隱私文 檔。數據隱私包括數據內容隱私和數據查詢隱私。在大數據與云 計算等應用場景中，事實上，僅通過對數據內容的加密只能保護 數據的內容隱私，并不能保護數據的查詢隱私。數據查詢隱私主 要指的是搜索模式和訪問模式，也就是指相同關鍵詞的提交頻率 和相同地址的訪問頻率。現有解決方案一般采用不經意隨機訪問 機(Oblivious Random Access Machine，ORAM)技術，對數據在 每次訪問時的存儲位置，進行重新洗牌和重新加密，來實現對外 包數據不經意讀和寫操作。

ORAM是隱私保護領域中保護訪問模式的一種重要手段，其 目的在于隱藏對真實數據塊的訪問，使得攻擊者不能區分每一次 訪問是真實的還是隨機的。現有ORAM方案仍然面臨較多挑戰， 例如用戶和云之間高度交互、用戶端存儲過大、通信帶寬較大以 及高昂的計算開銷。比如Path ORAM及其后續方案，要么用戶與 云的交互次數復雜度為O(logN)(其中N為總的元素個數)，要 么存在大客戶端地址映射表。許多ORAM方案以本地存儲地址映射表為代價來實現單輪不經意訪問，當尋址空間很大時，這些方 法對于資源有限的客戶端來說是不可擴展的，這與ORAM的設計 初衷并不一致。TWORAM是實現了小客戶端存儲和單輪交互的 ORAM協議，但它依賴于大量混淆電路，這在現實中是性能上的 瓶頸。

為此本發明提供了一種單輪交互的鏈表ORAM訪問方法,其 具有以下優勢和技術效果：1)實現了公有云上的單輪密文數據 讀寫訪問，用戶只需要發送請求并接收響應即可得到數據或者更 新數據；2)本地存儲幾乎為零；3)構造簡單且容易實現；4) 可在不犧牲較多效率的前提下將大量本地數組轉換為云存儲的 數組，并提供強隱私保護的快速數據讀寫服務。

發明內容

為實現本發明之目的，采用以下技術方案予以實現：

一種生成鏈表樹的方法，其中：所述鏈表樹LL-tree是加密 的滿二叉樹，所述方法包括生成鏈表樹的各個鏈表樹節點 LL-tree node，所述鏈表樹節點包括頭部head和尾部tail，如下：

其中頭部head包括m和emaps，尾部tail包括M和chunks， emaps和chunks是分別由z項組成的復合結構；M、m、emaps和 chunks的定義分別如下：M表示節點掩碼，節點掩碼是由用戶 生成的一個隨機值，是私密信息，不對云公開；m表示密文掩碼， 是存儲在鏈表樹節點頭部的一個加密值，由節點的節點掩碼和其 父節點的節點掩碼執行異或運算得到，密文掩碼對云公開； chunks包含z個chunk，其中chunk是指一個數據塊，chunk存儲 了四個元素(a,data₀,data₁,leaf)，即一個地址a、兩個相鄰的數 據data₀，data₁和一個葉標識符leaf,葉標識符leaf用于表示節 點屬于哪一條葉子到樹根的路徑；emaps包含z個加密映射表emap，其中每個emap存放兩組鍵值對信息(k₁,v₁,k₂,v₂)，用于 保存加密后的值。

所述的方法，其中包括對emap執行的讀取和寫入操作，具 體讀操作和寫操作過程如下：