A survey on oblivious keyword search

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

CLC Number:

TP309.7

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

Add to citation manager EndNote|Ris|BibTeX

URL:

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

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

Figures/Tables 4

References 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.

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

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