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

申請號：	202110054402.X	申請日：	2021-01-15
公開（公告）號：	CN112966294B	公開（公告）日：	2022-09-09
發明（設計）人：	吳志強;蔡竹斌;李文軍;王進;鄭少瑩;唐小勇	申請（專利權）人：	長沙理工大學
主分類號：	G06F21/62	分類號：	G06F21/62;G06F21/60;G06F3/06;G06F16/27;G06F16/22
代理公司：	北京迎碩知識產權代理事務所(普通合伙) 11512	代理人：	錢揚保;張群峰
地址：	410114 湖南省***	國省代碼：	湖南;43
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種交互 oram 訪問方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【權利要求書】：

1.一種訪問鏈表樹的方法，包括讀操作和寫操作：

1)創建一次性令牌

用戶將輸入的地址通過地址編碼方法轉換成一組塊地址，假設i表示第i棵樹，M_i為第i棵樹用戶掩碼，對每一個塊地址(a_i,b_i)，計算得到L-1棵位置樹的所有令牌(t₁,t₂,…,t_L-1)；

2)在鏈表樹上搜索

在鏈表樹上搜索遞歸表示為：x_i+1＝Compute(T_i,t_i)，其中x_i+1為第i+1棵樹的葉子位置，T_i為第i棵樹，t_i為用戶發送的第i棵樹的令牌，其中Compute算法流程具體描述如下：

步驟A、訪問第一層樹節點，如果當前節點為d，那么用戶使用d.head.m異或t_i，得到一個變量t，如果當前節點包含了(a_i,b_i)數據塊，那么t就是一個正確的塊密鑰，就能在emaps中解密一個數據塊并得到下一棵樹的訪問葉子x_i+1，算法成功結束；否則，繼續搜索下一層節點；

步驟B、假設d為第二層的樹節點，用戶使用d.head.m異或上一步驟A獲得的t；如果當前節點包含了(a_i,b_i)數據塊，那么t就是一個正確的塊密鑰，就能在emaps中解密一個數據塊并得到下一棵樹的訪問葉子x_i+1，算法成功結束；否則，繼續搜索下一層節點；

步驟C、依次訪問，最終得到葉子x_i+1；

3)讀數據

用戶得到一條RLL后，采用兩個步驟讀寫數據：

步驟A、用戶創建L個臨時緩沖區，用于存儲一條RLL，用戶將全部的chunk解密后寫入對應的臨時緩沖區,所述RLL是指根據鏈表樹LL-tree生成隨機鏈表；

步驟B、用戶為所有解密過的chunk重新分配L個隨機葉標識符，其中第i棵樹的chunk(a′,data₀,data₁,leaf)的葉子的標識符，被寫入到第i-1棵樹的chunk(a′/2,data*₀，data*₁，leaf*)中，的data*₀或者data*₁中，如果a′為偶數，寫入data*₀中，a′為奇數，寫入data*₁中；

4)重建RLL

將L個緩沖區中的chunk數據洗牌后生成重新調整chunk的位置，然后對每一個樹節點，采用節點初始化加密算法加密樹節點，并得到一條新的RLL，將新的RLL被打包到下一次讀請求中；在下一次新的讀寫請求時候，用戶將新的查詢令牌連同歷史的被緩沖的RLL一并發送到云服務器，然后首先由云服務器執行歷史的節點覆蓋更新操作，再執行新的查詢操作；

所述鏈表樹是根據以下的生成鏈表樹的方法生成且經由以下的初始化鏈表樹的方法初始化的，其中，

所述生成鏈表樹的方法中，所述鏈表樹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₂)，用于保存加密后的值；

所述初始化鏈表樹的方法中，所述鏈表樹是根據上述生成鏈表樹的方法生成的，該初始化鏈表樹的方法包括：對于一組數據A[.]，假設其中共有N＝2^L個數據塊，用戶將N個數據塊隨機存儲在數據樹T_L的樹節點中，樹節點的一個chunk可以存儲兩個地址相鄰的數據塊，用另外一棵相鄰的較小的樹T_L-1存儲這些隨機節點對應的葉子位置，在T_L-1中，存儲了2^L-1個數據塊，它們的值分別是T_L的2^L-1個葉子位置，它的全部葉子位置保存在T_L-2中，依此類推，直到最后一棵樹T₁，它只包含一個樹節點，T₁-T_L-1稱為位置樹。