本文是閱讀了論文[1]之后寫的筆記，為了能對論文提出的方案和核心思想有更透徹的了解，

0. 一些定義

可搜索加密

Searchable Encryption, SE

當資料存盤在一個不可信的服務器時，為了讓服務器不能夠了解到資料內容，需要對資料加密后再存盤，為了實作在加密后的資料上進行關鍵詞檢索，提出了可搜索加密的思想，

對稱可搜索加密

SE分為兩種：對稱可搜索加密(Symmetric Searchable Encryption, SSE)和非對稱可搜索加密(Asymmetric Searchable Encryption, ASE)，后者也稱公鑰可搜索加密(Public Key Encryption With Searching, PEKS)，兩者的區別在于前者使用對稱加密演算法，加密和解密的密鑰一樣；后者使用非對稱加密演算法，

SSE相比于ASE，優勢在于計算開銷小、演算法簡單、速度快，通常使用在單用戶模型中，檢索方和資料擁有者是同一個，

前向安全

forward privacy/security

通俗來說，前向安全是指更新操作不會泄露之前的查詢的資訊，也就是說，服務器不知道更新的關鍵字是否在之前被查詢過，

形式化的定義在論文的4.1節給出了，

與之相對的是后向安全，簡單來說，是指如果一個關鍵字/檔案對(w, ind)已經被洗掉，那么之后的在關鍵字w上進行的搜索都不能包含這個ind，形式化的定義在Bost等人于2017年的一篇論文[2]中給出了，這篇論文提出的幾個方案都是基于Σoφo?實作的，

陷門置換

TrapDoor Permutation, TDP

本文方案的核心思想之一，如第四節中的圖1所示，簡單來說就是，在搜索令牌序列 $ST_0, ST_1, \cdots, ST_c$ 中，服務器可以從后往前(從已有的 $ST_c$ 到???????最早的 $ST_0$ )計算ST，而只有用戶可以從前往后生成(從最新的 $ST_c$ 生成更新的 $ST_{c+1}$ )，以控制服務器可以搜索的索引范圍，確保前向安全，

1. 核心思想

舊的搜索令牌不能用于搜索新添加的檔案，因此保證了前向安全，

為每個關鍵字/檔案對(w, ind)生成對應的搜索令牌(search token, ST)，每個關鍵字w對應一個令牌序列 $ST_0, ST_1, \cdots, ST_c$ , $c=n_w-1$ . 初始時令 $ST_0$ 為一個亂數，c=-1；以后每當添加了一個w上的對(w, ind)，就用 $ST_c$ 生成 $ST_{c+1}$ ，同時c自增1.這個程序只能由用戶使用陷門密鑰SK進行，而為了減少存盤開銷，TDP應該滿足這樣的要求：使用公鑰PK可以很方便地從 $ST_i$ 計算 $ST_{i-1}$ ，而只有使用密鑰SK才能從 $ST_i$ 計算 $ST_{i+1}$ ，這樣用戶和服務器都只需要存盤 $ST_c$ ；當需要檢索時，用戶把最新的 $ST_c$ 發給服務器，

2. 具體方案

方案偽代碼如下圖所示，即Σoφo?-B，這個方案只能實作對檔案的添加；不過想要實作洗掉也很容易，只需要再增加一個Σoφo?-B實體用于洗掉，每當一個洗掉操作到達，把對應的(w, ind)添加到洗掉實體中，并在回傳搜索結果時回傳兩個實體的差，但需要注意的是，這樣從用戶的角度來看，(w, ind)已經從資料庫中洗掉；但對服務器來說它還存在，因此并不能實作后向安全，想要實作后向安全，即對服務器來說洗掉的(w, ind)不存在于資料庫中，還需要一些其他的技術，比如穿刺加密，

方案主要使用了兩個映射W、T和兩個哈希函式H1、H2，

H1：使用公鑰 $K_w$ 和搜索令牌ST作為輸入，輸出一個與ST對應的長度為μ的更新令牌UT，
H2：使用公鑰 $K_w$ 和搜索令牌ST作為輸入，輸出一個與ST對應的長度為l的位串，l是ind的長度，
W：用戶使用的映射，它把關鍵字w映射到對應的搜索令牌 $ST_c$ 和一個整數 $c=n_w-1$ ，其中 $n_w$ 是關鍵字的數量，如果不存在這樣的ST和c，則隨機生成一個 $ST_0$ ，設c為-1，需要注意，w對應的ST并不是只有一個，而是有一個序列，為了節省開銷，只存盤了一個最新的 $ST_c$ ，
T：服務器使用的映射，它把更新令牌 $UT_i$ 映射到對應的索引加密e，e是ind和 $H2(K_w, ST_i)$ 的異或，也就是加密形式的索引ind，當需要取出ind時，只需要計算 $H2(K_w, ST_i)$ 和 $T[UT_i]$ ，并把結果相異或，

[1] Σoφo? – Forward Secure Searchable Encryption, Bost R. CCS 2016

[2] Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives, Bost R. et al. CCS 2017

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353283.html

標籤：其他

上一篇：一文搞懂對稱加密：加密演算法、作業模式、填充方式、代碼實作

下一篇：C中的數字輸出