不经意关键词检索技术综述

doi:10.12267/j.issn.2096-5931.2022.05.011

摘要/Abstract

摘要：

随着数据成为新型生产要素,数据流通的需求日益增长。但是,数据中存在的隐私信息会在流通过程中面临泄露风险。隐私计算可以在满足隐私保护约束的同时促进数据价值的释放,而不经意关键词检索是隐私计算的基础任务,对隐私计算的落地应用至关重要。对不经意关键词检索的任务定义以及相关任务进行了介绍,详细解析了目前不经意关键词检索的典型技术路线,最后对不经意关键词检索面临的技术挑战以及未来发展趋势进行了分析与探讨。

关键词: 不经意检索, 信息检索, 隐私计算

Abstract:

As data becomes a new factor of production, the demand for data circulation is growing. However, the sensitive information faces the risk of leakage during the circulation process. Privacy-preserving computing can promote the release of data value while satisfying privacy-preserving constraints. Oblivious keyword search (OKS) is one of the basic tasks of privacy-preserving computing, and it is very important for the application of privacy-preserving computing. In this paper, we first introduce the task definition of OKS and the related tasks. Then, we introduce in detail the typical technical routes of OKS. Finally, we analyze and discuss the technical challenges and future research directions of current OKS technology.

Key words: oblivioussearch, information retrieval, privacy preserving computing

中图分类号:

TP309.7

韩宗达, 邓宇涛, 程祥. 不经意关键词检索技术综述[J]. 信息通信技术与政策, 2022, 48(5): 82-90.

HAN Zongda, DENG Yutao, CHENG Xiang. A survey on oblivious keyword search[J]. Information and Communications Technology and Policy, 2022, 48(5): 82-90.

导出引用管理器 EndNote|Ris|BibTeX

链接本文:

http://ictp.caict.ac.cn/CN/10.12267/j.issn.2096-5931.2022.05.011

http://ictp.caict.ac.cn/CN/Y2022/V48/I5/82

图/表 4

表1 不经意关键词检索、隐私信息检索以及不经意传输的关系

	隐私保护要求		查询媒介
	用户端	数据库端	数组下标	关键词
PIR	√		√
OT	√	√	√
OKS	√	√		√

图1 基于OPE的不经意关键词检索协议流程[3]

图2 基于OPRF的不经意关键词检索协议流程[3]

图3 基于Key-Value Store的不经意关键词检索协议执行流程[10-11]

参考文献 48

[1]	OGATA W, KUROSAWA K. Obliviouskeyword search[J]. Journal of Complexity, 2002, 20(2-3):356-371. doi: 10.1016/j.jco.2003.08.023 URL
[2]	NAOR M, PINKAS B. Oblivioustransfer with adaptive queries[C]// International Cryptology Conference. Springer Berlin Heidelberg, 1999.
[3]	FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keywordsearch and oblivious pseudorandom functions[C]// Second International Conference on Theory of Cryptography. Springer Berlin Heidelberg, 2005.
[4]	CHEN H, LAINE K, RINDAL P. Fastprivate set intersection from homomorphic encryption[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas Texas USA: ACM, 2017.
[5]	CHEN H, HUANG Z, LAINE K, et al. Labeled PSI fromfully homomorphic encryption with malicious security[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Toronto Canada: ACM, 2018.
[6]	CONG K, MORENO R C, GAMA M B, et al. Labeled PSI fromhomomorphic encryption with reduced computation and communication[C]// Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021.
[7]	NAOR M, REINGOLD O. Number-theoretic constructions of efficient pseudo-random functions[C]// Foundations of Computer Science, 1997. Proceedings. 38th Annual Symposium on, 1997.
[8]	CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]// International Conference on the Theory and Application of Cryptology and InformationSecurity. Springer, Cham, 2017:409-437.
[9]	FAN J, VERCAUTEREN F. Somewhat practical fully homomorphic encryption[J]. Cryptology ePrint Archive, 2012.
[10]	ALI A, LEPOINT T, PATEL S, et al. {Communication- Computation}trade-offs in {PIR}[C]// 30th USENIX Security Symposium (USENIX Security 21), 2021:1811-1828.
[11]	LEPOINT T, PATEL S, RAYKOVA M, et al. Private join and compute from PIR with default[C]// International Conference on the Theory and Application of Cryptology and InformationSecurity. Springer, Cham, 2021:605-634.
[12]	CHASE M, MIAO P. Private set intersection in the internet setting from lightweight oblivious PRF[C]// Annual International Cryptology Conference. Springer, Cham, 2020:34-63.
[13]	CHOR B, GOLDREICH O, Kushilevitz E, et al. Private information retrieval[C]// Proceedings of IEEE 36th Annual Foundations of Computer Science. IEEE, 1995:41-50.
[14]	KUSHILEVITZ E, OSTROVSKY R. Replication is not needed:single database, computationally-private information retrieval[C]// Proceedings 38th annual symposium on foundations of computer science. IEEE, 1997:364-373.
[15]	STERN J P. A new and efficient all-or-nothing disclosure of secrets protocol[C]// International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 1998:357-371.
[16]	ALI A, LEPOINT T, PATEL S, et al. Communication-computation trade-offs in PIR[J]. IACR Cryptol. ePrint Arch., 2019:1483.
[17]	ANGEL S, CHEN H, LAINE K, et al. PIR with compressed queries and amortized query processing[C]// 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018:962-979.
[18]	YI X, KAOSAR M G, PAULET R, et al. Single-database private information retrieval from fully homomorphic encryption[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(5):1125-1134. doi: 10.1109/TKDE.2012.90 URL
[19]	MELCHOR C A, BARRIER J, FOUSSE L, et al. XPIR: Private information retrieval for everyone[J]. Proceedings on Privacy Enhancing Technologies, 2016:155-174.
[20]	ANGEL S, SETTY S. Unobservable communication over fully untrusted infrastructure[C]// 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16), 2016:551-569.
[21]	PARK J, TIBOUCHI M. SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval[C]// European Symposium on Research in ComputerSecurity. Springer, Cham, 2020:86-106.
[22]	CANETTI R, HOLMGREN J, RICHELSON S. Towards doubly efficient private information retrieval[C]// Theory of Cryptography Conference. Springer, Cham, 2017:694-726.
[23]	HOLZBAUR L, HOLLANTI C, WACHTER-ZEH A. Computationalcode-based single-server private information retrieval[C]// 2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020:1065-1070.
[24]	MELCHOR C A, GABORIT P. A lattice-based computationally-efficient private information retrieval protocol[Z], 2007.
[25]	GROTH J, KIAYIAS A, LIPMAA H. Multi-query computationally-private information retrieval with constant communication rate[C]// International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2010:107-123.
[26]	ALFARANO G N, KHATHURIA K, WEGER V. On single server private information retrieval in a coding theory perspective[J]. arXiv preprint arXiv:2008. 06417, 2020.
[27]	FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]// International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2004:1-19.
[28]	MEADOWS C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]// 1986 IEEE Symposium on Security and Privacy. IEEE, 1986:134-134.
[29]	CRISTOFARO E, TSUDIK G. Practical private set intersection protocols with linear complexity[C]// International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2010:143-159.
[30]	FREEDMAN M J, HAZAY C, NISSIM K, et al. Efficient set intersection with simulation-based security[J]. Journal of Cryptology, 2016, 29(1):115-155. doi: 10.1007/s00145-014-9190-0 URL
[31]	HUANG Y, EVANS D, KATZ J. Private set intersection:are garbled circuits better than custom protocols?[C]// NDSS, 2012.
[32]	RINDAL P, ROSULEK M. Fastermalicious 2-party secure computation with {online/offline} dual execution[C]// 25th USENIX Security Symposium (USENIX Security 16), 2016:297-314.
[33]	DONG C, CHEN L, WEN Z. When private set intersection meets big data: an efficient and scalable protocol[C]// Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013: 789-800.
[34]	RINDAL P, ROSULEK M. Faster malicious 2-party secure computation with online/offline dual execution[C]// 25th {USENIX} Security Symposium ({USENIX} Security 16), 2016:297-314.
[35]	RINDAL P, ROSULEK M. Improved private set intersection against malicious adversaries[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2017:235-259.
[36]	RINDAL P, ROSULEK M. Malicious-secure private set intersection via dual execution[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017:1229-1242.
[37]	KOLESNIKOV V, KUMARESAN R, ROSULEK M, et al. Efficient batched oblivious PRF with applications to private setintersection[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016:818-829.
[38]	PINKAS B, SCHNEIDER T, ZOHNER M. Faster private set intersection based on {OT} extension[C]// 23rd {USENIX} Security Symposium ({USENIX} Security 14), 2014:797-812.
[39]	CHASE M, MIAO P. Private set intersection in the internet setting from lightweight oblivious PRF[C]// Annual International Cryptology Conference. Springer, Cham, 2020:34-63.
[40]	ISHAI Y, KILIAN J, NISSIM K, et al. Extending oblivious transfers efficiently[C]// Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2003:145-161.
[41]	KOLESNIKOV V, KUMARESAN R. Improved OT extension for transferring short secrets[C]// Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013:54-70.
[42]	ASHAROV G, LINDELL Y, SCHNEIDER T, et al. More efficient oblivious transfer and extensions for faster secure computation[C]// Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, 2013:535-548.
[43]	CHOU T, ORLANDI C. The simplest protocol for oblivious transfer[C]// International Conference on Cryptology and Information Security in Latin America. Springer, Cham, 2015:40-58.
[44]	HAUCK E, LOSS J. Efficient anduniversally composable protocols for oblivious transfer from the CDH assumption[J]. IACR Cryptol. ePrint Arch, 2017:1011.
[45]	PEIKERT C, VAIKUNTANATHAN V, WATERS B. A framework for efficient and composable oblivious transfer[C]// Annual international cryptology conference. Springer, Berlin, Heidelberg, 2008: 554-571.
[46]	CLAUDE C. Equivalence between two flavours of obliv- ious transfers[C]// In A Conference on the Theory and Appli- cations of Cryptographic Techniques on Advances in Cryptol- ogy, CRYPTO’87, 1988.
[47]	MOHASSEL P, ZHANG Y. Secureml:a system for scalable privacy-preserving machine learning[C]// 2017 IEEE symposium on security and privacy (SP). IEEE, 2017:19-38.
[48]	HUANG Y, EVANS D, KATZ J, et al. Fastersecure {two-party} computation using garbled circuits[C]// 20th USENIX Security Symposium (USENIX Security 11), 2011.