實用的云環(huán)境下可驗證的身份基匿名保序加密

黃 霖 趙運磊

(復(fù)旦大學軟件學院 上海 210203) (復(fù)旦大學計算機科學技術(shù)學院上海市數(shù)據(jù)科學重點實驗室 上海 210203)

0 引 言

隨著大數(shù)據(jù)技術(shù)的日益發(fā)展，越來越多的信息存儲于云數(shù)據(jù)庫中。雖然云計算解決了傳統(tǒng)計算方式存在的許多問題，但是新技術(shù)也帶來了新挑戰(zhàn)：一個重要的問題是云數(shù)據(jù)的管理不完全可信[1-3]。

針對此問題，可以在創(chuàng)建和更新數(shù)據(jù)時采用支持數(shù)據(jù)庫密文域處理的加密方式，如此在查詢時不需進行解密操作，從而防止好奇的管理員偷窺數(shù)據(jù)或服務(wù)器被攻破時數(shù)據(jù)明文泄露，有效提高云數(shù)據(jù)庫的安全性。在眾多支持密文域處理的加密方式中，保序及揭序加密是其中一條重要的分支。其中，揭序加密(Order-Revealing Encryption,ORE)是保序加密的泛化，而保序加密(Order-Preseving Encryption,OPE)是揭序加密的特例。對于范圍查詢，保序及揭序加密可以使用戶在密文上直接比較明文的大小，保護敏感數(shù)據(jù)不會被云數(shù)據(jù)庫服務(wù)器泄露。

保序加密方案的概念和定義由Agrawal等[4]提出。Boldyreva等[5]提出了關(guān)于保序加密的嚴格安全定義理想安全性(IND-OCPA)。IND-OCPA安全性是挑戰(zhàn)者和敵手之間的博弈，通俗來講，可進行如下描述：敵手準備兩個明文序列，這兩個序列具有相同的順序，但數(shù)值是隨機的。敵手把這兩個序列發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者加密一個序列，并將密文發(fā)送給敵手，敵手的目標是猜出挑戰(zhàn)者加密的是這兩個序列中的哪一個；如果敵手猜出正確結(jié)果的概率是50%，則算法具有IND-OCPA安全性。Boneh等[6]受到了密碼學混淆器的啟發(fā)提出了一種新的能夠提供比較密文對應(yīng)明文大小功能的加密方案，即揭序加密。作為保序加密的泛化，揭序加密中對密文所對應(yīng)明文的比較并不是直接通過比較密文數(shù)值的大小來進行，而是借助了公開的比較函數(shù)。所有實現(xiàn)IND-OCPA安全性的ORE方案需要頻繁的客戶端與服務(wù)器的交互[7-10]，而非交互式、無狀態(tài)的ORE方案都需要強大的加密原語，例如多線性映射或不可分辨混淆[6,11]，在今天無法有效實現(xiàn)。Chenette等[12]受到可搜索對稱加密文獻[13-14]中考慮的基于模擬器的定義啟發(fā)，給出了一個基于模擬器的關(guān)于泄露函數(shù)L的ORE安全性定義，在安全和效率之間提供了一個具體的權(quán)衡。擁有泄露的ORE的安全和IND-OCPA都是在僅僅已知密文模型上的安全定義；如果敵手還知道密文集的背景，可能會采取頻率統(tǒng)計攻擊。Kerschbaum[15]提出了抵抗頻率攻擊的理想安全性，即IND-FAOCPA，并提出了一種滿足IND-FAOCPA安全性的保序加密算法。但現(xiàn)今滿足IND-FAOCPA安全性的方案都不具有較強實用性。之后的研究[16-17]聲稱Kerschbaum的定義是不精確的，并描述了對他的方案的攻擊，Cash等[18]提出了新的參數(shù)隱藏方案。

然而，現(xiàn)有的保序及揭序加密算法缺乏對密文正確性及完整性的驗證，缺少對不同身份用戶的權(quán)限管理，因此本文考慮構(gòu)造一種具有身份管理功能的順序揭露簽密方法。簽密是將數(shù)字簽名和公鑰加密的功能合二為一，既保證了加密內(nèi)容的完整性和可驗證性，又保證了加密消息的私密性，并且比簡單地結(jié)合簽名和加密的效率大為提升。匿簽密的概念由Zhao[19]提出，它可以看作是公鑰加密、數(shù)字簽名和身份隱藏的一種新的整體集成。Wang等[20]構(gòu)造了一種基于身份的匿簽密。本文在安全性與實用性之間做了權(quán)衡，最終提出了一種具有“擁有泄露的ORE安全[12]”的便于實現(xiàn)的身份基匿名簽密。具體的泄露函數(shù)為Lf(m1,m2,…,mt)={1(mj

1 系統(tǒng)模型與安全模型

1.1 系統(tǒng)模型

如圖1所示，數(shù)據(jù)分享者A匿名將自己的可進行范圍查詢的敏感數(shù)據(jù)加密并簽名，保存在云數(shù)據(jù)庫服務(wù)器中。

圖1 系統(tǒng)模型與用戶權(quán)限

所有可以訪問這個云服務(wù)器的用戶C都可以直接對密文進行比較(不需要密鑰)，但沒有驗證數(shù)據(jù)正確性、完整性和對密文解密獲得明文的權(quán)限。

擁有更進一步訪問權(quán)限的用戶B?C，除了擁有C所擁有的比較權(quán)限外，還可以得知數(shù)據(jù)來自于A，驗證數(shù)據(jù)正確性和完整性，并且對數(shù)據(jù)進行解密，得知明文。用戶B可以是具有權(quán)力的政府部門、數(shù)據(jù)監(jiān)管者，或者用戶A指定的其他人，其ID固定，可以訪問云中不同數(shù)據(jù)庫里的敏感數(shù)據(jù)。之所以采用身份基簽密，而不是傳統(tǒng)公鑰體系的簽密，是因為身份基簽密可以一個ID對應(yīng)不同的私鑰(不同數(shù)據(jù)庫使用不同的主私鑰)，而在傳統(tǒng)公鑰體系中，一個特定的公鑰只能生成一個私鑰。因而如果B擁有多個數(shù)據(jù)庫的特殊訪問權(quán)限(這與B能訪問包含敏感信息的明文往往是關(guān)聯(lián)的，這是B的身份賦予它的權(quán)利)，身份基簽密更利于私鑰管理。

加密簽名操作在數(shù)據(jù)分享者A的客戶端進行；比較操作在云數(shù)據(jù)庫服務(wù)器中進行，在B和C進行范圍查詢時，服務(wù)器返回結(jié)果給B和C；驗證、解密、獲取數(shù)據(jù)擁有者身份都在B的客戶端進行。

考慮以下場景：A為某保密單位，公布了一些實驗成果或統(tǒng)計結(jié)果，其中一些敏感數(shù)據(jù)使用本文算法加密，公眾可以對其進行范圍查詢，但不能獲取其精確的值。C可以范圍查詢這些數(shù)據(jù)，獲取例如一組數(shù)據(jù)最大的幾個值，并查看這些值對應(yīng)的其他信息；而B作為特權(quán)用戶可以獲得A的身份，并能對它的身份進行驗證，還能在范圍查詢后，獲取加密數(shù)據(jù)的精確數(shù)值。A、B、C與云數(shù)據(jù)服務(wù)器交互的詳細流程見圖2和圖3。

圖2 數(shù)據(jù)分享者A與云服務(wù)器交互流程

圖3 不同權(quán)限數(shù)據(jù)用戶B和C與云服務(wù)器交互流程

數(shù)據(jù)分享者將敏感數(shù)據(jù)明文M使用身份基揭序匿簽密加密簽名為密文C，每個敏感數(shù)據(jù)密文與表格中可被公眾查看相關(guān)信息一一對應(yīng)。之后A將敏感數(shù)據(jù)密文和可被公眾查看信息一起匿名存儲在云服務(wù)器中。

C向云服務(wù)器發(fā)出范圍查詢請求，云服務(wù)器對敏感數(shù)據(jù)密文C進行比較，并由篩選出的密文得出它們對應(yīng)的可被公眾查看的相關(guān)信息，之后服務(wù)器將查詢結(jié)果(這些相關(guān)信息)發(fā)送給C的客戶端。

值得注意的是，在實際的應(yīng)用中，范圍查詢分為兩類：第一類為求出所有密文中的前k大或前k小(k≥1)的值，第二類為求出大于或小于某明文值的信息。對于第一類查詢，則C可以直接進行比較。對于第二類查詢，C需要知道明文所對應(yīng)密文值才可進行比較，但其不能也不應(yīng)該知道任一明文所對應(yīng)密文值，否則其可能發(fā)起選擇明文攻擊，以較快速度獲取任意一個密文所對應(yīng)的明文值，所以應(yīng)當限定C不能進行第二類范圍查詢。

同樣地，具有特殊權(quán)限的B向云服務(wù)器發(fā)出范圍查詢請求時，云服務(wù)器也會經(jīng)歷相同的過程，將可被公眾查看信息發(fā)送給客戶端B。另外，如果B提出了請求，云服務(wù)器還會將符合范圍查詢結(jié)果的可被公眾查看信息也發(fā)送給客戶端B。B可以根據(jù)這些密文，在自己的客戶端進行解密、驗證密文是否真實完整操作，并且能夠獲取到A的身份。在該算法中，B可求出某明文值對應(yīng)的密文，并可以進行所有的范圍查詢；在查詢大于或小于某明文值的信息時，B需要先將此明文值加密為密文再進行問詢。

1.2 安全模型

在本方案中，我們假設(shè)數(shù)據(jù)使用者B和C是經(jīng)過授權(quán)和可信的，所以我們不會考慮數(shù)據(jù)用戶方面的泄露。同時我們認為密鑰分發(fā)渠道不會引起密鑰泄露。此外，我們假設(shè)明文分布是稀疏的。但云服務(wù)器被認為是誠實但好奇的。換句話說，云服務(wù)器會誠實地執(zhí)行算法流程，但會對存儲的數(shù)據(jù)、查詢語句、查詢到的數(shù)據(jù)和其他附加信息的內(nèi)容感到好奇。

表和實驗

考慮云服務(wù)器知道所有密文集。如上所述，所有實現(xiàn)IND-OCPA[5]安全性的非交互式、無狀態(tài)的ORE方案都需要強大的加密原語，在今天無法有效實現(xiàn)，因此作為一個實用的保序加密方案，它的安全需要滿足定義1，即擁有泄露的ORE的安全[12]，這里的泄露函數(shù)為Lf(m1,m2,…,mt)={1(mj

驗證和匿名部分的安全由離散對數(shù)[21]、雙線性映射[22-25]和成熟的對稱加密保證，離散對數(shù)滿足DLP安全，雙線性映射滿足DBDH安全。最終驗證和匿名部分滿足DBDH安全。

考慮本算法是使用了公鑰(身份信息相當于公鑰)的保序加密。一般的保序加密不使用公鑰加密，因為使用公鑰加密模式的保序加密方法容易招致選擇明文攻擊——敵手可選擇明文并得知其加密密文，同時敵手又知道已有密文的順序，從而可通過不斷獲取已知明文的密文，與已有密文進行大小對比，進而得知已有密文所對應(yīng)明文大小。而本算法可以抵抗選擇明文攻擊。

除此以外，本文還會考慮當敵手已知所有密文集和密文集中每個密文出現(xiàn)的頻率時的安全性。我們將計算每個明文出現(xiàn)的頻率可以與明文集中其他的多少個明文出現(xiàn)的頻率混淆。

2 算法描述

本文所提出的可驗證的揭序加密算法包含ORE_INIT、ORE_GEN、ORE_ENC、ORE_COMP、ORE_DEC(非必須)、ORE_CHECK(非必須)六個步驟。

2.1 ORE_INIT：初始化

3) 選擇一個哈希函數(shù)h:{0,1}*→G1，一個密鑰導(dǎo)出函數(shù)KDF:{0,1}*→{0,1}n，一個對稱加密函數(shù)Enc，一個偽隨機函數(shù)F:{0,1}*→ZM。

2.2 ORE_GEN：私鑰生成

PKG不負責驗證B的身份，僅僅負責由用戶ID生成他的私鑰SKID；若B的身份IDB為誤，則他不可以正確地解密和驗證數(shù)據(jù)。在實際應(yīng)用中，為了防止PKG在此處遭到DDoS(分布式拒絕服務(wù))攻擊，可采取同網(wǎng)絡(luò)IP短時間內(nèi)申請生成私鑰次數(shù)限制等措施。

值得注意的是，這里的IDA和IDB起到了PKA和PKB的作用，但因為需要身份匿藏，所以IDA不公開；若需要驗證B的身份，則IDB也不公開。

2.3 ORE_ENC：身份基揭序匿簽密生成

數(shù)據(jù)編碼部分參考了Chenette等[12]提出的方法，并進行修改，使簽密滿足一定的頻率隱藏特性。令M∈{0,1}*為明文信息，設(shè)a1a2…an為明文M的二進制編碼形式，對于二元組(i,M)，定義下面的編碼：E(i,M)=(a1a2…ai-1‖1n-i)。其中，整數(shù)n為消息的比特長度，i∈[n]。

數(shù)據(jù)擁有者A的加密簽名具體步驟如下：

2) 若PS≠1G2，則計算K=KDF(PS)；否則回到1)，重新選取隨機數(shù)x。

4) 將密文串連接成為Cpre=c1c2…cn，計算H=h(Cpre)，Chead=EncK(H||||IDA||||x)，C=Chead‖Cpre。

對于長度為n的二進制字符串，算法復(fù)雜度為O(n)，需要n次對長度為n的二進制字符串進行F(·)運算。如需進一步提高加密效率，可引入并行計算。

2.4 ORE_COMP：揭序匿簽密比較

1) 從C中獲取Cpre=c1c2…cn。

對于長度為n的二進制字符串，算法復(fù)雜度為O(n)，僅僅需要n次數(shù)據(jù)比較。

2.5 ORE_CHECK：揭序匿簽密驗證

非必要步驟。在傳統(tǒng)的保序/揭序加密體系中，僅僅需要2.1節(jié)至2.4節(jié)這四步即可。但需要驗證密文正確性和完整性時，可進行此步操作。

2) 從C中獲取Cpre=c1c2…cn，使用K解密Chead得到H，IDA，x。

3) 驗證H=h(Cpre)，驗證IDA合法，并且X=(h(IDA))x，則說明匿簽密來自于用戶A并且是完整真實的；否則匿簽密C無效。

2.6 ORE_DEC：揭序匿簽密解密

非必要步驟。一般的保序或揭序加密定義中不包含解密算法，因為明文信息可通過對所有密文的二分查找獲得(需要知道加密密鑰和加密方法)，但如此就需要多輪客戶端與服務(wù)器端的通信和對密文的比較。本算法可對密文直接進行解密，解密過程如下：

1) 從C中獲取Cpre=c1c2…cn。

算法需要遍歷一遍密文，對于明文長度為n的二進制字符串，算法復(fù)雜度為O(n)，需要n次對長度為n的二進制字符串進行F(·)運算。

3 性能評估

3.1 正確性

(1) 比較的正確性。對于相同的輸入，F(xiàn)的輸出是相同的，因此對于相同前綴的比特位，F(xiàn)的結(jié)果是相同的。因而，若兩個字符串某i位前面的比特位相同，則F的結(jié)果也是相同的，F(xiàn)(K,E(i,m))+ai可比較在前綴相同時第i位的大小，依次比較每一位編碼的結(jié)果即可比較兩數(shù)的大小。

而結(jié)尾為連續(xù)的0或連續(xù)的1時，若比較到這些0或者這些1的位數(shù)，則這數(shù)一定小于或等于，或者大于或等于另一個數(shù)。那么對于這些0或1，在F(K,E(i,m))的基礎(chǔ)上在密文大小范圍內(nèi)減一個隨機數(shù)或加一個隨機數(shù)，若兩數(shù)不同則不會影響大小比較的結(jié)果，若兩數(shù)相同則會隨機輸出一個數(shù)，這有利于抗頻率統(tǒng)計攻擊。

此外，普通用戶因為沒有特權(quán)用戶的私鑰，所以得不到數(shù)據(jù)分享方加密使用的K，因此他們只能對數(shù)據(jù)進行范圍查詢，而不能執(zhí)行解密驗證以及獲取分享方身份的操作。

3.2 安全性

一般的保序加密不使用公鑰加密，因為公鑰加密容易招致選擇明文攻擊——敵手可選擇明文并得知其加密密文，同時敵手又知道已有密文的順序，從而可通過不斷獲取已知明文的密文，與已有密文進行大小對比，進而得知已有密文所對應(yīng)明文大小。而在本文算法中，加密方在密鑰生成時既使用了公鑰(ID信息)，又使用了私鑰。在單純的簽密中，假設(shè)敵手擁有數(shù)據(jù)擁有者A的IDA，選擇一個明文M試圖進行加密從而獲取密文C′，但因為其不具有A的私鑰SKA(私鑰保存在客戶端，云數(shù)據(jù)庫的好奇的敵手并不能獲得)，所以其不能產(chǎn)生A對數(shù)據(jù)M進行加密產(chǎn)生的結(jié)果C，因此其不能夠進一步將C′與數(shù)據(jù)庫已有密文比較大小，從而不能進行選擇明文攻擊。

首先，S0初始化空查找表L:[q]×[n]→ZM，令stS=L。接下來，對于每一個t∈[q]，當敵手輸出一個問詢mt，輸入stS=L和Lf(m1,m2,…,mt)并調(diào)用模擬算法St。泄露函數(shù)Lf(m1,m2,…,mt)={1(mj

對于每一個s∈[n]，有以下三種情況：

3.3 時間空間性能

對于長度為n的二進制字符串，加密操作需要一次雙線性映射和兩次冪運算，并n次對長度為n的二進制字符串進行偽隨機運算和一次對稱加密；比較操作需要n次對ZM范圍內(nèi)的整數(shù)進行比較；解密和驗證首先需要一次雙線性映射和兩次冪運算，然后解密操作需要n次對長度為n的二進制字符串進行偽隨機運算，驗證操作需要一次對稱加密方式的解密。

為了使性能數(shù)據(jù)更加明顯，在Intel i5、8 GB內(nèi)存、Ubuntu系統(tǒng)下進行測試，對單個數(shù)據(jù)進行各種操作，所得時間性能如表2所示?？梢钥闯鏊惴ㄟm合應(yīng)用于實際，尤其是它的比較操作很快，適合應(yīng)用于需要經(jīng)常進行范圍查詢的場景。因為生成密鑰K耗時占總耗時比例較大，而它與明文長度無關(guān)，所以32 bit和64 bit數(shù)據(jù)的加密、解密、驗證速度差距不大。

表2 時間性能測試

值得注意的是，表2實驗測試的是插入單個數(shù)據(jù)時的加密操作耗時和解密驗證單個數(shù)據(jù)時的耗時。而如果插入多組數(shù)據(jù)，或解密驗證多組數(shù)據(jù)，因為需要很多重復(fù)的雙線性映射和冪模操作，所以如果只進行一次這些操作并記錄結(jié)果，則平均處理每組數(shù)據(jù)的耗時會大大降低。以32 bit長度數(shù)據(jù)為例，圖4以測試的數(shù)據(jù)組數(shù)為橫坐標，以每組數(shù)據(jù)平均耗時為縱坐標，展示了對多組數(shù)據(jù)加密、解密和驗證的耗時。對多組數(shù)據(jù)加解密操作的耗時，隨數(shù)據(jù)組數(shù)增加，逐漸趨近于1.92 μs左右；而對多組數(shù)據(jù)驗證操作的耗時，隨數(shù)據(jù)組數(shù)增加，逐漸趨近于161.1 μs左右。這有利于快速創(chuàng)建數(shù)據(jù)庫和解密獲得已授權(quán)的大量敏感信息。

圖4 加解密多組數(shù)據(jù)時每組數(shù)據(jù)平均耗時

保序揭序加密協(xié)議，在從明文映射到密文時，都需要空間擴展。對于N個相同長度的數(shù)據(jù)，假設(shè)數(shù)據(jù)擁有方ID長度為32 bit，大整數(shù)x長度為256 bit，哈希運算得到的數(shù)據(jù)長度為128 bit，每個明文驗證所需擴展為512 bit(假設(shè)使用的對稱加密方式需要塊對齊)，本算法所需的密文空間如表3所示。

表3 空間性能擴展

4 結(jié) 語

在眾多屬性揭示加密算法中，保序及揭序加密是一條重要的分支，然而現(xiàn)有的保序及揭序加密算法缺乏對密文正確性及完整性的驗證，缺少對不同身份用戶的權(quán)限管理，而滿足理想安全性的算法實用性較差。因此本文提出一種具有擁有泄露的ORE安全的便于實現(xiàn)的具有較優(yōu)解密效率的身份基匿名簽密，在比較時最終會泄露兩個明文的最高不同比特位。在此算法的系統(tǒng)模型中，所有用戶都可以進行比較操作，而特權(quán)用戶可以進行身份發(fā)現(xiàn)、驗證正確完整性和解密操作。算法采用了身份基的加密方式，這有利于對多個數(shù)據(jù)庫的私鑰管理。在算法效率方面，對32 bit數(shù)據(jù)間的一次比較操作約耗時0.28 μs，適用于需要頻繁進行范圍查詢的場景。

本文算法具有一定的頻率隱藏特性，但是頻率隱藏特性較弱，后續(xù)可做更多補充。如何提高算法效率，減少服務(wù)器端與客戶端之間的通信輪次，減少除順序信息以外的信息的泄露，是保序及揭序加密算法領(lǐng)域需要持續(xù)不斷考慮的問題。