加密文档排序中保序加密算法的最优化选取

张久岭; 黄道超; 沈时军

doi:10.13700/j.bh.1001-5965.2020.0414

加密文档排序中保序加密算法的最优化选取

doi: 10.13700/j.bh.1001-5965.2020.0414

国家计算机网络应急技术处理协调中心, 北京 100029

基金项目:

国家重点研发计划 2016YFB1000105

详细信息

通讯作者:
张久岭, E-mail: zhangjl@cert.org.cn

中图分类号: TP399
计量
- 文章访问数: 553
- HTML全文浏览量: 215
- PDF下载量: 39
- 被引次数: 0
出版历程
- 收稿日期: 2020-08-10
- 录用日期: 2020-09-05
- 网络出版日期: 2022-02-20

Optimal choice of order preserving encryption scheme in encrypted document ranking

National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China

Funds:

National Key R & D Program of China 2016YFB1000105

More Information

Corresponding author: ZHANG Jiuling, E-mail: zhangjl@cert.org.cn

摘要

摘要:
对需要存储在服务器端的用户文档进行加密是对用户隐私保护的根本方法。采用不同的保序加密算法对加密文档排序结果有着不同的影响，寻找排序结果最优的保序加密算法是亟待解决的问题。提出了基于鉴别信息的保序加密算法选择的标准，比较了2种保序加密算法下对加密文档排序的性能。在通过保序加密算法得到的密文分布接近明文分布的情况下，排序得到的结果更接近明文检索的情况。所提出的选择标准具有理论上的意义，同时也可以指导在相同安全条件下保序加密算法的选择，以达到最优的检索结果。
- 保序加密 /
- Okapi BM25模型 /
- 鉴别信息 /
- 加密信息检索 /
- 用户隐私保护
Abstract:
Encrypting the documents before uploading them to the untrusted removable server is one of the ultimate solutions to protect the user privacy. As different encryption schemes give different ranking results, finding the order preserving encryption scheme that gives the best ranking result is the key issue to be solved. A discrimination information based on criterion for selecting the order preserving encryption scheme is proposed and then employed to compare the ranking results of two different order preserving encryption schemes. In the case the distribution of the cipher text is closer to that of the plaintext, the ranking result is closer to that in the plaintext scenario. The proposed criterion is not only instructive in theory, but also helpful practically in choosing the order preserving encryption scheme under the same safety conditions, which further lead to the optimal retrieval result.
- order preserving encryption /
- Okapi BM25 model /
- discrimination information /
- encrypted information retrieval /
- user privacy protection

HTML全文

图 1 Okapi BM25模型权重出现频率的分布函数

Figure 1. Probability distribution function of term weights in Okapi BM25 model

下载: 全尺寸图片幻灯片

图 2 开放式保序加密算法与封闭式保序加密算法密文随明文变化情况

Figure 2. Change of cipher text with plaintext for open order preserving encryption scheme and closed order preserving encryption scheme

下载: 全尺寸图片幻灯片

图 3 不同检索排序方式下的准确率-返回率曲线

Figure 3. Curves of precision versus recall rate with different retrieval and ranking methods

下载: 全尺寸图片幻灯片

表 1 参数拟合值

Table 1. Parameter fitting values

参数	拟合值	95%置信区间
p₁	0.500	(0.495, 0.506)
p₂	-1.356	(-1.368, -1.345)
p₃	1.448	(1.442, 1.455)
p₄	-0.960	(-0.964, -0.957)
p₅	1.419	(1.414, 1.424)

下载: 导出CSV

表 2 前N个返回文档的准确率

Table 2. Precision of top N recalled documents

P@N	准确率/%
P@N	开放式保序加密算法	封闭式保序加密算法	明文检索
P@5	63.6	57.2	78.0
P@10	54.0	50.6	74.6
P@20	46.8	42.0	67.6
P@30	42.9	38.7	62.1
P@50	38.0	35.0	56.2
P@100	30.5	29.2	43.5

下载: 导出CSV

参考文献(20)

[1]	SONG D X, WAGNER D, PERRIG A. Practical techniques for searches on encrypted data[C]//Proceedings of 2000 IEEE Symposium on Security and Privacy. Piscataway: IEEE Press, 2000: 44-55.
[2]	BONEH D, CRESCENZO G, OSTROVSKY R, et al. Public key encryption with keyword search[C]//Proceedings of Advances in Cryptology-Eurocrypt 2004. Berlin: Springer, 2004: 506-522.
[3]	PARK D J, KIM K, LEE P J. Public key encryption with conjunctive field keyword search[C]//International Conference on Information Security Applications. Berlin: Springer, 2005: 73-86.
[4]	SWAMINATHAN A, MAO Y N, SU G M, et al. Confidentiality preserving rank-ordered search[C]//Proceedings of the ACM Workshop on Storage Security and Survivability. New York: ACM, 2007: 7-12.
[5]	WANG C, CAO N, LI J, et al. Secure ranked keyword search over encrypted cloud data[C]//Proceedings of 30th IEEE International Conference on Distributed Computing Systems. Piscataway: IEEE Press, 2010: 253-262.
[6]	LU W J, SWAMINATHAN A, VARNA A L, et al. Enabling search over encrypted multimedia databases[C]//Media Forensics and Security. Bellingham: SPIE Press, 2009: 725418.
[7]	PHONG L T, AONO Y, HAYASHI T, et al. Privacy-preserving deep learning via additively homomorphic encryption[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(5): 1333-1345. doi: 10.1109/TIFS.2017.2787987
[8]	OZSOYOGLU G, SINGER D, CHUNG S. Anti-tamper databases: Querying encrypted databases[C]//Proceedings of the 17th Annual IFIP WG. New York: ACM, 2003: 4-6.
[9]	AGRAWAL R, KIERNAN J, SRIKANT R, et al. Order preserving encryption for numeric data[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. New York: ACM, 2004: 563-574.
[10]	BOLDYREVA A, CHENETTE N, LEE Y, et al. Order-preserving symmetric encryption[C]//Proceedings of Advances in Cryptology-Eurocrypt 2009. Berlin: Springer, 2009: 224-241.
[11]	BOLDYREVA A, CHENETTE N, O'NEILL A. Order-preserving encryption revisited: Improved security analysis and alternative solutions[C]//Advances in Cryptology-CRYPTO 2011. Berlin: Springer, 2011: 578-595.
[12]	KHOURY E, MEDLEJ M, JAOUDE C A, et al. Novel order preserving encryption scheme for wireless sensor networks[C]//IEEE Middle East and North Africa Communications Conference (MENACOMM). Piscataway: IEEE Press, 2018: 1-6.
[13]	AHMED S, ANNIS A, ZAMAN A, et al. Semi-order preserving encryption technique for numeric database[J]. International Journal of Networking and Communication, 2019, 9(1): 111-129. http://www.researchgate.net/publication/330457745_Semi-Order_Preserving_Encryption_Technique_for_Numeric_Database
[14]	SHEN N, YEH J, CHEN C, et al. Ensuring query completeness in outsourced database using order-preserving encryption[C]//Proceedings of IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking. Piscataway: IEEE Press, 2019: 776-783.
[15]	REDDY K S, RAMACHANDRAM S. A secure, fast insert and efficient search order preserving encryption scheme for outsourced databases[J]. International Journal of Advanced Intelligence Paradigms, 2019, 13(1/2): 155-177. doi: 10.1504/IJAIP.2019.099949
[16]	DYER J, DYER M, DJEMAME K. Order-preserving encryption using approximate common divisors[J]. Journal of Information and Applications, 2019, 49: 102391. doi: 10.1016/j.jisa.2019.102391
[17]	CHOWDHURY A R, RAMANATHAN P. Public order-preserving cipher generation scheme for distributed computing[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 2273-2275.
[18]	MANNING C D, RAGHAVAN P, SCHUTZE H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008: 253-256.
[19]	WHISSELL J S, CLARKE C. Improving document clustering using Okapi BM25 feature weighting[J]. Information Retrieval, 2011, 14(5): 466-487. doi: 10.1007/s10791-011-9163-y
[20]	LI K, ZHANG W M, YANG C, et al. Security analysis on one-to-many order preserving encryption-based cloud data search[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(9): 1918-1926. http://pdfs.semanticscholar.org/5e9a/1f22db2afcf5f428a7cf310cc672e9270437.pdf