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