質數(shù)內積編碼方案設計案例綜述目錄TOC\o"1-3"\h\u18819質數(shù)內積編碼方案設計案例綜述 112391.1方案介紹 149291.1.1基本思想及方案構建 1300851.1.2向量構造及向量匹配 2312601.1.3正確性分析 6118691.2方案介紹 7161211.2.1基本思想 7273241.2.2方案構造 8239671.2.3正確性分析 101.1方案介紹1.1.1基本思想及方案構建本節(jié)將介紹方案構造，方案在選擇密文攻擊下是語義安全的[12]。該方案建立在索引向量編碼和查詢向量編碼上，其基本思想是編碼查詢關鍵字或索引關鍵字為一個向量，這些元素都設置為整數(shù)或者整數(shù)的倒數(shù)，確保只有當兩個關鍵詞相似時，向量的內積才是一個整數(shù)。方案是用戶和云服務器之間的一個協(xié)議。方案一般由四個部分組成，分別是GenKey，BuildIndex，Trapdoor，Search。：云用戶輸入一個安全參數(shù)，輸出一個秘密密鑰SK。：給定一個具有個關鍵詞的集合，云用戶利用秘密密鑰對文件中的關鍵詞集合生成索引并進行加密，生成一個被加密的索引集合。：給定一個具有需要查詢的搜索關鍵詞集合，云用戶使用秘密密鑰SK為搜索關鍵詞集合生成一個陷門。：云服務器將陷門與被加密的索引共同運算，如果陷門與索引匹配，則輸出1，否則輸出0。1.1.2向量構造及向量匹配下面將詳細介紹索引向量編碼、查詢向量編碼和向量匹配過程。在介紹向量編碼之前，先簡單介紹后面可能會用到的相關符號，如表1.1所示。表1.1方案相關符號及說明符號說明一組文件的集合一組含m個關鍵詞的集合一組含n個密文文件的集合所有關鍵詞中的最大長度文件的m個關鍵詞文件的索引搜索向量中的個關鍵詞搜索向量的陷門含有26個英文字母的集合填充字符集，且與集合A沒有交集長度為L的質數(shù)序列詳細的索引向量編碼算法如下圖1.1所述，第一步（(1)-(2)）首先用集合S中的字符將索引關鍵詞填充至關鍵詞最大長度L。填充之后，第二步（（3）-（4））將索引向量的每一個元素初始化為1。第三步（（5）-（7））將指定質數(shù)的倒數(shù)放置在索引向量的適當位置。比如，關鍵詞第l（）個字符對應的質數(shù)是，對應索引向量的位置是。然后索引向量對應的位置將乘以對應的質數(shù)，即。圖1.1索引向量編碼算法詳細的搜索向量編碼算法如下圖1.2所述，第一、二步（1-4）為填充步驟和初始步驟，與索引向量編碼的第一、二步一致。第三步（5-15）將把指定的素數(shù)放在搜索向量的適當位置。對于關鍵詞的第l個字符，這里有兩種情況，如果該字符不為通配符“*”時，將計算，并且在這個位置乘以對應的質數(shù)，即。如果該字符為通配符“*”時，則將搜索向量上所有元素的值都乘以該位置的質數(shù)。圖1.2搜索向量編碼算法圖1.3和圖1.4展示了向量編碼和向量匹配的一個樣例，假設文件與關鍵字的關系如圖1.3-(a)所示，此時云用戶發(fā)出查詢請求和去搜索合適的文件。給定關鍵詞最長長度為，隨機數(shù)序列為，填充字符集合。圖1.4描述了索引向量編碼和搜索向量編碼的過程。下面將用索引關鍵詞“key”和搜索關鍵詞“k*y”描述向量編碼和向量匹配的過程。在向量編碼第一步中，用字符“A”和“B”填充兩個關鍵詞，使其最大長度為5。第二步分別將兩個d維向量和中的所有元素初始化為1。對于索引關鍵詞“key”，素數(shù)的倒數(shù)擺列如下，因為“k”是第一個字符，所以將乘以1/3；因為“e”是第二個字符，所以將乘以1/5；因為“y”是第三個字符，所以將乘以1/7；因為“A”是第四個字符，所以將乘以1/11；因為“B”是第五個字符，所以將乘以1/13；對于搜索關鍵詞“k*y”，質數(shù)按如下順序排列：因為“k”是第一個字符，所以將乘以3；因為“*”是第二個字符，且“*”是通配符，那么集合A和S中的任意元素都可能位于這個位置，所以該向量上所有元素即全部乘以5；因為“y”是第三個字符，所以將乘以7；因為“A”是第四個字符，所以將乘以11；因為“B”是第五個字符，所以將乘以13；由于質數(shù)的不可分解性，所以兩個向量內積是一個整數(shù)（等于21）。結果與兩個關鍵詞相似的事實是一致的。當需要多關鍵詞搜索時，方案也支持AND和OR查詢方式。查詢方式為AND意味著只有當搜索詞集合包含在某文件的關鍵詞集合內時，該文件才會被返回給用戶。查詢方式為OR意味著當搜索詞集合和某文件的關鍵詞集合有交集時，該文件就會被返回。給定圖1.4所示的索引/查詢向量，對應的搜索詞矩陣如圖1.3-(b)所示。如果的查詢方式是AND，則文件將被返回，因為只有在在每個列中有一個整數(shù)元素；如果的查詢方式是OR，則文件都將被返回，因為中至少有一個整數(shù)元素。如果的查詢方式是AND，則文件將被返回，因為只有在每個列中有一個整數(shù)元素。如果的查詢方式是OR，則文件都將被返回，因為文件和都至少有一個整數(shù)元素。由此可以看出方案也具有支持布爾搜索的功能。圖1.3關鍵詞搜索過程圖1.4向量編碼1.1.3正確性分析本條將介紹方案搜索原理的正確性。設表示英文字母和填充字符的并集，其中U[i]表示U中的第i個元素。首先考慮一個文件和一個搜索關鍵詞中僅含有單個關鍵詞的情形，分別表示為和。如果出現(xiàn)以下情況，基本PIPE方案被認為是不正確的：如果索引關鍵詞和搜索關鍵詞相似，關鍵詞向量和搜索關鍵詞向量的內積不是一個整數(shù)。如果索引關鍵詞和搜索關鍵詞不相似，關鍵詞向量和搜索關鍵詞向量的內積是一個整數(shù)。對于情形1，不是一個整數(shù)意味著中至少有一個倒數(shù)不能被消除。由于BuildIndex的構造，表示U[i]是的第i個字符。如果1/不能被消除，那么就一個不能被整除的整數(shù)。由于搜索向量編碼運算的構造規(guī)則，不會是通配符“*”，也不會是U[i]。因此兩個關鍵詞不相似，情形1是不正確的。對于情形2，是一個整數(shù)意味著中所有倒數(shù)都能被消除。由于表示U[i]是的第i個字符。會等于或者一個能被整除的數(shù)。由于搜索向量編碼運算的構造規(guī)則，是通配符“*”或者U[i]。因此情形2也是不正確的，綜上所述，方案在文件或搜索關鍵詞中僅含單個關鍵詞的情況是正確的。當擴展到多關鍵詞設置時，方案的正確性推導如下：結果矩陣第k行第l列的元素是的內積，如果中的第k個索引關鍵詞和中的第l個搜索關鍵詞相似，那么的結果將是一個整數(shù)。當查詢方式為AND時，如果每一列都至少有一個整數(shù)，則中每一個索引關鍵詞至少和中的一個搜索是相似的，那么搜索關鍵詞和索引關鍵詞對應的文件相匹配。當查詢方式為OR時，如果結果矩陣至少有一個整數(shù)，那么中至少有一個索引關鍵詞和中的一個搜索關鍵詞是相似的。綜上所述，在文件或搜索關鍵詞中含多個關鍵詞的情況是正確的。1.2方案介紹1.2.1基本思想本節(jié)將介紹方案。前面已經(jīng)介紹過PIPE方案是基于安全KNN結構構造的，但是安全KNN結構難以抵抗線性分析，因此提出了去抵抗線性分析，從KNN的構造可知，索引向量和查詢向量的內積可以通過它們的加密形式計算出來：，其中只有索引向量p中的d個元素對云服務器是未知的。在已知背景模型中，云服務器能夠通過有效的背景信息推斷某些明密文對。正如Yao等人[27]所證，一個敵手擁有d個查詢向量及其加密形式的向量后能夠通過求解線性方程回復索引向量。為了抵抗這種攻擊，將查詢向量擴展到隨機矩陣，從而在內積結果中加入噪聲。發(fā)起這種攻擊的困難來自于構造正確方程的可能性極小。對于所有的索引向量有:。解決方案基于以下關鍵技術：1、矩陣編碼查詢。搜索向量首先由搜索向量編碼算法（見圖1.5）產(chǎn)生，再通過搜索矩陣編碼算法（見表3.4）生成一個d*s的矩陣。對于，搜索矩陣編碼算法將設置到第l行的隨機一個位置，并且用隨機數(shù)填滿其他位置，要求滿足以下幾個條件：Condition1：的每一列至少有向量中的一個元素。Condition2：第l行隨機數(shù)之和應該等于，記為，其中或者為一個質數(shù)，且要求該質數(shù)不在質數(shù)序列P中。圖1.5搜索矩陣編碼算法2、相似性的確定。給定一個由關鍵詞生成的索引向量、一個由關鍵詞生成的搜索矩陣，一個通過計算得到的中間向量。如果一行中所有相加，即，和如果為一個整數(shù)，那么關鍵詞和被認為是相似的。1.2.2方案構造方案和方案最大的區(qū)別在于和，下面將介紹這兩個部分：：搜索序列含有個關鍵詞，云用戶任意選擇一個整數(shù)。為了對中的個關鍵詞加密并得到一個的矩陣，他將執(zhí)行以下操作：對第k個關鍵詞使用搜索向量編碼算法（見圖1.2）生成一個d維向量對d維向量使用搜索矩陣編碼算法（見圖1.5）生成一個d*s的矩陣對于，將搜索詞矩陣元素的賦值為。其中是個搜索向量的結合（例子可見圖1.6-(a)）：給定一個索引矩陣和搜索矩陣。再做匹配運算時，云服務器將產(chǎn)生一個的中間矩陣，即。矩陣由的中間向量組成（見圖3.3-(c)），元素表示。為了確定搜索向量是否與文件匹配，需要執(zhí)行以下操作：首先構造一個結果矩陣對于和，設置，且（見圖1.6-(b)）當查詢方式為AND時，如果每列至少有一個整數(shù)時，則輸出1，否則輸出0；當查詢方式為OR時，如果至少有一個整數(shù)時，則輸出1，否則輸出0；圖1.6展示了一個PIPE-s方案的簡單構造，假如s=3，搜索關鍵詞的搜索矩陣為，如圖1.6-(a)所示，的前s列為，的后s列為。正如圖1.3-(b)矩陣一樣，圖1.6-(b)為結果矩陣，圖1.3-(c)為中間變量矩陣圖1.6方案構造樣例1.2.3正確性分析方案的正確性是基于假設查詢矩陣中引入的隨機性不會影響結果的