[發明專利]一種基于zigzag解碼的私人信息檢索方法及系統

有效

• 申請號: 201710433563.3
• 申請日: 2017-06-09
• 公開（公告）號: CN107241414B
• 公開（公告）日: 2019-10-22
• 發明（設計）人: 代明軍;李曉鳳;王暉
• 申請（專利權）人: 深圳大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;G06F21/62
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙) 44248
• 代理人: 趙雪佳

本發明提供一種基于zigzag解碼的私人信息檢索方法及系統，屬于計算機技術應用領域。本發明方法包括采用(n,k)MDS碼存儲文件步驟；生成一個隨機向量U用于檢索文件f步驟；解碼并獲取文件f步驟。本發明還提供了一種實現所述基于zigzag解碼的私人信息檢索方法的系統。本發明的有益效果為：在滿足允許用戶下載文件且不顯示正在下載哪個文件等基本安全要求的同時，其通信成本和復雜度相對較低。并且在分布式存儲系統中，可以在任意n?k個節點同時發生故障時恢復出原始文件，增加了數據存儲的安全性。

技術領域

本發明涉及計算機技術應用領域，尤其涉及一種基于zigzag解碼的私人信息檢索方法，還涉及一種實現所述基于zigzag解碼的私人信息檢索方法的系統。

背景技術

為了保證信息查詢的安全性，通常采用私有信息檢索(PIR)技術。私有信息檢索可以為用戶的隱私和數據安全提供保障。

私有信息檢索的大致過程如下：用戶基于要查詢的文件下標i生成k個查詢請求，分別發送給k個服務器(為了隱藏i，在服務器看來，這些查詢應當是關于下標i的隨機函數)。各服務器根據收到的查詢請求和本地數據庫x計算查詢結果返回給用戶。最后用戶根據收到的k個查詢結果計算目標數據x_i，現有的私有信息檢索技術有主要以下幾種。

1、目前效率最高的計算性的PIR協議是由Carlos Aguilar-Melchor和PhilippeGaborit于2007年提出的基于格的PIR協議。文章使用類似NTRU(一種公鑰加密方法)的方法，對數據庫服務器上的數據分塊并構建矩陣形式。用戶查詢時首先生成若干符合一定要求的隨機矩陣，然后對目標塊和非目標塊位置作不同的矩陣變換(乘積、替換等)，并對得到的查詢矩陣再作一次隨機置換，然后將該查詢矩陣發送給服務器。服務器利用本地數據作相應的矩陣乘運算后將結果向量返回給用戶。用戶再對該結果作相應的逆運算以獲得目標數據塊。

2、2009年Wang S.等將基于二次剩余的cPIR和k-匿名方法結合，提出了可供用戶選擇折中的靈活實用的Bounding-Box PIR協議。該協議考慮了信息泄露的概率，以一定的信息泄露來換取性能的提升。

3、Papadopoulos S.等提出了pCloud這樣一個P2P的解決方案，使用網絡上的其他節點共同解決計算性的PIR協議的計算復雜度高的問題。他們采用基于中國剩余定理的計算性的PIR協議，通過將數據分塊并分發到網絡中的不同節點，并讓各節點共同執行計算任務，以此提高查詢效率。

現有技術中存在以下問題：

1、基于格的PIR協議提出了Hidden Lattice Problem(HLP)，證明其與已知的NP完全問題Punctured Code Problem在查詢上的等價性。它指出協議的計算開銷為對數據庫中的每bit，僅需數千bit操作。這比起已知的計算性的PIR，計算開銷降低了至少兩個數量級。不過該協議的通信開銷相對大些。

2、Bounding-Box PIR協議中并沒有對隱私性給出定義及定量的分析。在私有信息檢索問題的研究中，對用戶的查詢隱私性，不論信息論的PIR(要求達到保障用戶的完全隱私)還是計算性的PIR(要求達到保障用戶的計算性隱私)，都要求完全的隱私保護。而完全隱私保護的代價就是高復雜度與不實用。我們需要在效率和隱私性之間尋找一個折中，這就需要一個對隱私性進行度量的方法。

3、Papadopoulos S.等提出的pCloud這樣一個P2P的解決方案。在基于中國剩余定理的PIR協議中，對用戶的每一個查詢，服務器必須計算所有數據。且在這個分布式模式下，用戶的每一個查詢需要所有分塊的計算結果來重構最終的查詢結果。但是由于網絡延時、節點失效等網絡因素的存在，這并不容易。這種情況下，用戶需要重新向服務器發送一次查詢并由服務器執行最基本的非分布式的計算，導致更多的通信開銷與計算開銷。

因此，現有的研究都是高進制存儲，解碼復雜度高。