基于f-mOPE的數(shù)據(jù)庫密文檢索方案

周藝華; 吉文; 楊宇光

doi:10.11999/JEIT180805

基于f-mOPE的數(shù)據(jù)庫密文檢索方案

doi: 10.11999/JEIT180805

北京工業(yè)大學(xué)信息學(xué)部 ??北京 ??100124

基金項目: 國家自然科學(xué)基金(61572053)

詳細(xì)信息

作者簡介:
周藝華：男，1969年生，副教授，研究方向為網(wǎng)絡(luò)與信息安全

吉文：男，1993年生，碩士，研究方向為信息安全

楊宇光：女，1976年生，教授，研究方向為信息安全及信息安全與其他學(xué)科的交叉學(xué)科

通訊作者:
吉文　jwnba24@163.com

中圖分類號: TP309
計量
- 文章訪問數(shù): 1877
- HTML全文瀏覽量: 930
- PDF下載量: 85
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-08-16
- 修回日期: 2019-01-29
- 網(wǎng)絡(luò)出版日期: 2019-02-21
- 刊出日期: 2019-08-01

Database Ciphertext Retrieval Scheme Based on f-mOPE

Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China

Funds: The National Natural Science Foundation of China (61572053)

摘要

摘要: 在云數(shù)據(jù)庫環(huán)境下，為保證云存儲數(shù)據(jù)的安全性，通常將數(shù)據(jù)加密存儲。針對加密存儲數(shù)據(jù)查詢開銷大，不支持密文排序，查詢等缺點，該文提出一種 f-mOPE數(shù)據(jù)庫密文檢索方案。該方案基于可變保序編碼(mOPE)，采用二叉排序樹數(shù)據(jù)結(jié)構(gòu)思想，生成明文一一對應(yīng)的保序編碼；基于AES加密方案將數(shù)據(jù)明文轉(zhuǎn)化為密文存儲；采用改進的部分同態(tài)加密算法提升保序加密方案的安全性。通過安全性分析及實驗結(jié)果表明，該方案在保證數(shù)據(jù)隱私的基礎(chǔ)上，不但能抵御統(tǒng)計型攻擊，而且能夠有效地降低服務(wù)器計算開銷，提高數(shù)據(jù)庫處理效率。
- 密文數(shù)據(jù)庫 /
- 保序加密算法 /
- 可變保序編碼
Abstract: In a cloud database environment, data is usually encrypted and stored to ensure the security of cloud storage data. To overcome the shortcomings of encrypting the data that the query overhead is big, the cipher text sortings and query are not support, etc, this paper puts forward a kind of f - mOPE cryptograph database retrieval scheme. Based on the mOPE sequential encryption algorithm, the idea of binary sort tree data structure is used to generate plaintext one-to-one corresponding sequential coding. Data plaintext is converted into ciphertext storage based on the AES encryption scheme. The improved partial homomorphic encryption algorithm is used to improve the security of sequential encryption scheme. The security analysis and experimental results show that this scheme can not only resist statistical attack, but also reduce effectively server computing cost and improve database processing efficiency on the basis of guaranteeing data privacy.
- Ciphertext database /
- Sequential encryption algorithm /
- Mutable Order-Preserve Encoding(mOPE)

HTML全文

圖 1 保密數(shù)據(jù)分塊處理方案

下載: 全尺寸圖片幻燈片

圖 2 平衡因子$k$對重平衡次數(shù)影響圖

下載: 全尺寸圖片幻燈片

圖 3 mOPE方案和f-mOPE方案插入元素時間消耗對比

下載: 全尺寸圖片幻燈片

圖 4 元素個數(shù)與重平衡次數(shù)關(guān)系

下載: 全尺寸圖片幻燈片

圖 5 檢索執(zhí)行時間對比

下載: 全尺寸圖片幻燈片

表 1 公式符號說明

　$\lambda $：安全參數(shù);

　$\rho $：噪聲長度,為抵抗暴力攻擊$\rho = \omega (\lg \lambda )$;

　$\eta $：私鑰二進制長度， $\eta $滿足$\eta \ge \rho \varTheta (\lambda {\lg ^2}\lambda )$，這樣才能保證壓縮　　解密可行;

　$\gamma $：公鑰二進制長度，為抵抗格攻擊，$\gamma = \omega ({\eta ^2}\lg \lambda )$；

　$\tau $：公鑰個數(shù)，$\tau \ge \gamma + \omega (\lg \lambda )$，文中需要的公鑰個數(shù)為$2\sqrt \tau $；

下載: 導(dǎo)出CSV

表 2 序號與保序編碼對應(yīng)關(guān)系表

序號	1	2		3		4		5		6		7		8
保序編碼	[000] 1=1	[00] 10=2	[001] 1=3	[0] 100=4	[010] 1=5	[01] 10=6	[011] 1=7	[1] 000=8	[100] 1=9	[10] 10=10	[1] 011=11	[1] 100=12	[110] 1=13	[11] 10=14	[1111] =15

下載: 導(dǎo)出CSV

表 3 算法1: 保序編碼調(diào)整算法

符號定義：ord_num：數(shù)據(jù)的序號；index：數(shù)據(jù)十進制編碼
//將所有的數(shù)據(jù)排序后存入臨時表tmp中
insertIntoTmpTable(datas)
h = lg(n)+1;
index = 2(n-(2^h-1 -1))+1;
count = index-1;
//更新臨時表中數(shù)據(jù)索引編碼
if(ord_num > count):
foreach():
updateTmpTable(ord_num):
index = ord_num + (ord_num-count);
update tmp set index = index where ord_num=ord_num;
else:
foreach():
update tmp set index = ord_num where ord_num=ord_num;
//將臨時表重平衡結(jié)果更新至數(shù)據(jù)表中，需要將臨時表中index轉(zhuǎn)換為二進制并加入子樹標(biāo)識，如式(7)描述
foreach(data):
update OPE_Table A inner join tmp B on A.ciper = B.ciper set A.ord_code = B.index;

下載: 導(dǎo)出CSV

表 4 算法2: 數(shù)據(jù)插入及檢索算法

插入元素算法：	查找元素算法：
key,IV = generateInitAttr();//初始化加密參數(shù)	//確定子樹編碼
//加密明文	treeIndex = partitionTree(plainText);
ciphertext = encryptData(plainText);	//查詢子樹根節(jié)點
//構(gòu)建保序編碼	rootNode = searchTreeRootNode(treeIndex);
foreach(plainTexts):	//遍歷子樹尋找所有符合條件密文
//確定子樹編碼	datalist = search(rootNode,tree,plainText):
treeIndex = partitionTree(plainText);	foreach(datalist)://解密所有密文
//數(shù)據(jù)模糊化處理	data = decrypt(value,key);
fuzzyData=FuzzyData(plainText);	return datalist;
//與服務(wù)端交互確定數(shù)據(jù)保序索引
code_index=connectToServer(fuzzyData,treeIndex)；
//插入數(shù)據(jù)
insertData(fuzzyData,code_index);

下載: 導(dǎo)出CSV

表 5 DGHV部分同態(tài)加密方案與本文改進方案對比

	DGHV部分同態(tài)加密方案	本文改進部分同態(tài)加密方案
加密效率	1次加密1 bit明文	1次加密$n$bit明文
安全性	$q$是對外開放的，那么如果 $pq$ 作為公鑰，很容易計算出私鑰$p$的值。	加入一些明文為0加密得到的密文$\{ {x_i}:{x_i} = {2^n}{r_i} + p{q_i}\} $，將這些密文組成一個集合$s$，以$\sum\nolimits_{1 \le i,j \le \sqrt \tau } {{b_{i,j}}{x_{i,0}}} {x_{j,1}}$作為公鑰，任意選取集合元素${x_i} \in S$加入運算，因為其明文都是0，不會改變加密結(jié)果，并且能夠提高算法安全性。在運算過程中只需要將${2^n}$上傳到服務(wù)器即可，把${2^n}\sum\nolimits_{1 \le i,j \le \sqrt \tau } {{b_{i,j}}{x_{i,0}}{x_{j,1}}} $作為公鑰，即使獲取${2^n}$也無法獲取密鑰$p$
安全性	$q$是對外開放的，那么如果 $pq$ 作為公鑰，很容易計算出私鑰$p$的值。
復(fù)雜度	該方案公鑰尺寸約為$O({\lambda ^{10}})$	該方案中，參數(shù)取$\rho = \lambda $, $\eta = O({\lambda ^2})$,$\gamma = O({\lambda ^5})$,$\tau = O({\lambda ^3})$，所以該部分同態(tài)加密公鑰尺寸為$r + \tau (\lambda + \eta ) = O({\lambda ^5})$

下載: 導(dǎo)出CSV

表 6 mOPE與f-mOPE查詢開銷對比

數(shù)據(jù)個數(shù)	mOPE查詢開銷	f-mOPE查詢開銷
500	8	10
5000	11	10
10000	12	10
20000	13	10
50000	15	10

下載: 導(dǎo)出CSV

表 7 mOPE與f-mOPE時間復(fù)雜度比較

時間復(fù)雜度	mOPE	f-mOPE
計算OPE編碼	$O(\lg n)$	$O(\lg n)$
調(diào)整編碼	最好情況O(1) 最壞情況O(n)	O(1)
檢查是否平衡/需要調(diào)整	最好情況O(1) 最壞情況O(n)	最好情況O(n) 最壞情況O(n)

下載: 導(dǎo)出CSV

參考文獻(xiàn)(16)

GABEL M and MECHLER J. Secure database outsourcing to the cloud: Side-channels, counter-measures and trusted execution[C]. The 2017 IEEE 30th International Symposium on Computer-Based Medical Systems, Thessaloniki, Greece, 2017: 799–804.

陸海寧. 可隱藏搜索模式的對稱可搜索加密方案[J]. 信息網(wǎng)絡(luò)安全, 2017(1): 38–42. doi: 10.3969/j.issn.1671-1122.2017.01.006

LU Haining. Searchable symmetric encryption with hidden search pattern[J]. Netinfo Security, 2017(1): 38–42. doi: 10.3969/j.issn.1671-1122.2017.01.006

DEMERTZIS I and PAPAMANTHOU C. Fast searchable encryption with tunable locality[C]. 2017 ACM International Conference on Management of Data, Chicago, Illinois, USA, 2017: 1053–1067.

PENG Tianyue, LIN Yaping, YAO Xin, et al. An efficient ranked multi-keyword search for multiple data owners over encrypted cloud data[J]. IEEE Access, 2018, 6: 21924–21933. doi: 10.1109/ACCESS.2018.2828404

AGRAWAL R, KIERNAN J, SRIKANT R, et al. Order preserving encryption for numeric data[C]. 2004 ACM SIGMOD International Conference on Management of Data, Paris, France, 2004: 563–574.

BOLDYREVA A, CHENETTE N, LEE Y, et al. Order-preserving symmetric encryption[C]. The 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, 2009: 224–241.

LIU Zheli, CHEN Xiaofeng, YANG Jun, et al. New order preserving encryption model for outsourced databases in cloud environments[J]. Journal of Network and Computer Applications, 2016, 59: 198–207. doi: 10.1016/j.jnca.2014.07.001

TERANISHI I, YUNG M, and MALKIN T. Order-preserving encryption secure beyond one-wayness[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Taiwan, China, 2014: 42–61.

MAVROFORAKIS C, CHENETTE N, O’NEILL A, et al. Modular order-preserving encryption, revisited[C]. 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, 2015: 763–777.

ZHANG Huanguo, HAN Wenbao, LAI Xuejia, et al. Survey on cyberspace security[J]. Science China Information Science, 2015, 58(11): 1–43. doi: 10.1007/s11432-015-5433-4

LIU Dongxi and WANG Shenlu. Programmable order-preserving secure index for encrypted database query[C]. The 2012 IEEE 5th International Conference on Cloud Computing, Honolulu, USA, 2012: 502–509.

LIU Dongxi and WANG Shenlu. Nonlinear order preserving index for encrypted database query in service cloud environments[J]. Concurrency and Computation: Practice and Experience, 2013, 25(13): 1967–1984. doi: 10.1002/cpe.2992

張成果. CryptDB密文數(shù)據(jù)庫系統(tǒng)研究[D]. [碩士論文], 南京郵電大學(xué), 2017.

ZHANG Chengguo. The research of cryptDB encrypted database system[D]. [Master dissertation], Nanjing University of Posts and Telecommunications, 2017.

POPA R A, REDFIELD C M S, ZELDOVICH N, et al. processing queries on an encrypted database[J]. Communications of the ACM, 2012, 55(9): 103–111. doi: 10.1145/2330667.2330691

POPA R A, LI F H, and ZELDOVICH N. An ideal-security protocol for order-preserving encoding[C]. 2013 IEEE Symposium on Security and Privacy, Berkeley, USA, 2013: 463–477.

VAN DIJK M, GENTRY C, HALEVI S, et al. Fully homomorphic encryption over the integers[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, 2010: 24–43.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計