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

周藝華; 吉文; 楊宇光

doi:10.11999/JEIT180805

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

doi: 10.11999/JEIT180805 cstr: 32379.14.JEIT180805

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

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61572053)

詳細(xì)信息

作者簡(jiǎn)介:
周藝華：男，1969年生，副教授，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全

吉文：男，1993年生，碩士，研究方向?yàn)樾畔踩?/p>
楊宇光：女，1976年生，教授，研究方向?yàn)樾畔踩靶畔踩c其他學(xué)科的交叉學(xué)科

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

中圖分類號(hào): TP309
計(jì)量
- 文章訪問(wèn)數(shù): 1907
- HTML全文瀏覽量: 959
- PDF下載量: 88
- 被引次數(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ù)庫(kù)環(huán)境下，為保證云存儲(chǔ)數(shù)據(jù)的安全性，通常將數(shù)據(jù)加密存儲(chǔ)。針對(duì)加密存儲(chǔ)數(shù)據(jù)查詢開(kāi)銷大，不支持密文排序，查詢等缺點(diǎn)，該文提出一種 f-mOPE數(shù)據(jù)庫(kù)密文檢索方案。該方案基于可變保序編碼(mOPE)，采用二叉排序樹(shù)數(shù)據(jù)結(jié)構(gòu)思想，生成明文一一對(duì)應(yīng)的保序編碼；基于AES加密方案將數(shù)據(jù)明文轉(zhuǎn)化為密文存儲(chǔ)；采用改進(jìn)的部分同態(tài)加密算法提升保序加密方案的安全性。通過(guò)安全性分析及實(shí)驗(yàn)結(jié)果表明，該方案在保證數(shù)據(jù)隱私的基礎(chǔ)上，不但能抵御統(tǒng)計(jì)型攻擊，而且能夠有效地降低服務(wù)器計(jì)算開(kāi)銷，提高數(shù)據(jù)庫(kù)處理效率。
- 密文數(shù)據(jù)庫(kù) /
- 保序加密算法 /
- 可變保序編碼
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$對(duì)重平衡次數(shù)影響圖

下載: 全尺寸圖片幻燈片

圖 3 mOPE方案和f-mOPE方案插入元素時(shí)間消耗對(duì)比

下載: 全尺寸圖片幻燈片

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

下載: 全尺寸圖片幻燈片

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

下載: 全尺寸圖片幻燈片

表 1 公式符號(hào)說(shuō)明

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

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

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

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

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

下載: 導(dǎo)出CSV

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

序號(hào)	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)整算法

符號(hào)定義：ord_num：數(shù)據(jù)的序號(hào)；index：數(shù)據(jù)十進(jìn)制編碼
//將所有的數(shù)據(jù)排序后存入臨時(shí)表tmp中
insertIntoTmpTable(datas)
h = lg(n)+1;
index = 2(n-(2^h-1 -1))+1;
count = index-1;
//更新臨時(shí)表中數(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;
//將臨時(shí)表重平衡結(jié)果更新至數(shù)據(jù)表中，需要將臨時(shí)表中index轉(zhuǎn)換為二進(jìn)制并加入子樹(shù)標(biāo)識(shí)，如式(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ù)	//確定子樹(shù)編碼
//加密明文	treeIndex = partitionTree(plainText);
ciphertext = encryptData(plainText);	//查詢子樹(shù)根節(jié)點(diǎn)
//構(gòu)建保序編碼	rootNode = searchTreeRootNode(treeIndex);
foreach(plainTexts):	//遍歷子樹(shù)尋找所有符合條件密文
//確定子樹(shù)編碼	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)加密方案與本文改進(jìn)方案對(duì)比

	DGHV部分同態(tài)加密方案	本文改進(jìn)部分同態(tài)加密方案
加密效率	1次加密1 bit明文	1次加密$n$bit明文
安全性	$q$是對(duì)外開(kāi)放的，那么如果 $pq$ 作為公鑰，很容易計(jì)算出私鑰$p$的值。	加入一些明文為0加密得到的密文$\{ {x_i}:{x_i} = {2^n}{r_i} + p{q_i}\} $，將這些密文組成一個(gè)集合$s$，以$\sum\nolimits_{1 \le i,j \le \sqrt \tau } {{b_{i,j}}{x_{i,0}}} {x_{j,1}}$作為公鑰，任意選取集合元素${x_i} \in S$加入運(yùn)算，因?yàn)槠涿魑亩际?，不會(huì)改變加密結(jié)果，并且能夠提高算法安全性。在運(yùn)算過(guò)程中只需要將${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}$也無(wú)法獲取密鑰$p$
安全性	$q$是對(duì)外開(kāi)放的，那么如果 $pq$ 作為公鑰，很容易計(jì)算出私鑰$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查詢開(kāi)銷對(duì)比

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

下載: 導(dǎo)出CSV

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

時(shí)間復(fù)雜度	mOPE	f-mOPE
計(jì)算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.

陸海寧. 可隱藏搜索模式的對(duì)稱可搜索加密方案[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ù)庫(kù)系統(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)

訪問(wèn)統(tǒng)計(jì)