Secure-channel free searchable encryption with multiple keywords: a generic construction, an instantiation, and its implementation. (English) Zbl 1458.94233
Summary: In public key encryption with keyword search (PEKS), a secure channel is required in order to send trapdoors to the server, whereas in secure-channel free PEKS (SCF-PEKS), no such secure channel is required. In this paper, we propose a generic construction of SCF-PEKS with multiple keywords (SCF-MPEKS) from hidden vector encryption, tag-based encryption, and a one-time signature. Our generic construction provides adaptive security, where the test queries are allowed in the security model, and does not require random oracles. In addition to providing an instantiation of our generic construction, which is the first adaptive secure SCF-MPEKS scheme in the standard model, we implement the SCF-MPEKS scheme by using the PBC library. Moreover, we extend the Boneh-Waters range search technique, and show that the running time of our encryption algorithm is approximately twice as fast as that of the Boneh-Waters encryption algorithm.
MSC:
| 94A60 | Cryptography |
| 94A40 | Channel models (including quantum) in information and communication theory |
References:
| [1] | The PBC (pairing-based cryptography) library, available at |
| [2] | Abdalla, Michel; Bellare, Mihir; Catalano, Dario; Kiltz, Eike; Kohno, Tadayoshi; Lange, Tanja; Malone-Lee, John; Neven, Gregory; Paillier, Pascal; Shi, Haixia, Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions, J. Cryptol., 21, 3, 350-391 (2008) · Zbl 1161.94378 |
| [3] | Abdalla, Michel; Bellare, Mihir; Neven, Gregory, Robust encryption, (TCC (2010), Springer), 480-497 · Zbl 1274.94032 |
| [4] | Agrawal, Rakesh; Kiernan, Jerry; Srikant, Ramakrishnan; Xu, Yirong, Order-preserving encryption for numeric data, (ACM SIGMOD (2004), ACM), 563-574 |
| [5] | Attrapadung, Nuttapong; Hanaoka, Goichiro; Ogawa, Kazuto; Ohtake, Go; Watanabe, Hajime; Yamada, Shota, Attribute-based encryption for range attributes, (Security and Cryptography for Networks (2016), Springer), 42-61 · Zbl 1400.94114 |
| [6] | Attrapadung, Nuttapong; Imai, Hideki, Dual-policy attribute based encryption: simultaneous access control with ciphertext and key policies, IEICE Trans., 93-A, 1, 116-125 (2010) |
| [7] | Baek, Joonsang; Safavi-Naini, Reihaneh; Susilo, Willy, On the integration of public key data encryption and public key encryption with keyword search, (ISC (2006), Springer), 217-232 · Zbl 1156.94331 |
| [8] | Baek, Joonsang; Safavi-Naini, Reihaneh; Susilo, Willy, Public key encryption with keyword search revisited, (ICCSA (2008), Springer), 1249-1259 · Zbl 1156.94331 |
| [9] | Bellare, Mihir; Boldyreva, Alexandra; Kurosawa, Kaoru; Staddon, Jessica, Multirecipient encryption schemes: how to save on bandwidth and computation without sacrificing security, IEEE Trans. Inf. Theory, 53, 11, 3927-3943 (2007) · Zbl 1326.94073 |
| [10] | Bellare, Mihir; Dowsley, Rafael; Keelveedhi, Sriram, How secure is deterministic encryption?, (Public-Key Cryptography (2015), Springer), 52-73 · Zbl 1345.94038 |
| [11] | Bellare, Mihir; Fischlin, Marc; O’Neill, Adam; Ristenpart, Thomas, Deterministic encryption: definitional equivalences and constructions without random oracles, (CRYPTO (2008), Springer), 360-378 · Zbl 1183.94020 |
| [12] | Bellare, Mihir; Rogaway, Phillip, Collision-resistant hashing: towards making UOWHFs practical, (CRYPTO (1997), Springer), 470-484 · Zbl 0882.94015 |
| [13] | Blundo, Carlo; Iovino, Vincenzo; Persiano, Giuseppe, Private-key hidden vector encryption with key confidentiality, (CANS (2009), Springer), 259-277 |
| [14] | Boldyreva, Alexandra; Chenette, Nathan; Lee, Younho; O’Neill, Adam, Order-preserving symmetric encryption, (EUROCRYPT (2009), Springer), 224-241 · Zbl 1239.94037 |
| [15] | Boldyreva, Alexandra; Chenette, Nathan; O’Neill, Adam, Order-preserving encryption revisited: improved security analysis and alternative solutions, (CRYPTO (2011), Springer), 578-595 · Zbl 1290.94045 |
| [16] | Boldyreva, Alexandra; Fehr, Serge; O’Neill, Adam, On notions of security for deterministic encryption, and efficient constructions without random oracles, (CRYPTO (2008), Springer), 335-359 · Zbl 1183.94024 |
| [17] | Boneh, Dan; Di Crescenzo, Giovanni; Ostrovsky, Rafail; Persiano, Giuseppe, Public key encryption with keyword search, (EUROCRYPT (2004), Springer), 506-522 · Zbl 1122.68424 |
| [18] | Boneh, Dan; Waters, Brent, Conjunctive, subset, and range queries on encrypted data, (TCC (2007), Springer), 535-554 · Zbl 1156.94335 |
| [19] | Buccafurri, Francesco; Lax, Gianluca; Anand Sahu, Rajeev; Saraswat, Vishal, Practical and secure integrated PKE+PEKS with keyword privacy, (SECRYPT (2015), SciTePress), 448-453 |
| [20] | Wook Byun, Jin; Suk Rhee, Hyun; Park, Hyun-A.; Hoon Lee, Dong, Off-line keyword guessing attacks on recent keyword search schemes over encrypted data, (SDM (2006), Springer), 75-83 |
| [21] | De Caro, Angelo; Iovino, Vincenzo; Persiano, Giuseppe, Fully secure hidden vector encryption, (Pairing-Based Cryptography (2012), Springer), 102-121 · Zbl 1305.94039 |
| [22] | Chatterjee, Sanjit; Mukherjee, Sayantan, Framework for efficient search and statistics computation on encrypted cloud data, (IWSEC (2014), Springer), 276-285 · Zbl 1420.68083 |
| [23] | Chen, Rongmao; Mu, Yi; Yang, Guomin; Guo, Fuchun; Wang, Xiaofen, Dual-server public-key encryption with keyword search for secure cloud storage, IEEE Trans. Inf. Forensics Secur., 11, 4, 789-798 (2016) |
| [24] | Chen, Yu; Zhang, Jiang; Lin, Dongdai; Zhang, Zhenfeng, Generic constructions of integrated PKE and PEKS, Des. Codes Cryptogr., 78, 2, 493-526 (2016) · Zbl 1344.94040 |
| [25] | Cui, Hui; Deng, Robert H.; Liu, Joseph K.; Li, Yingjiu, Attribute-based encryption with expressive and authorized keyword search, (ACISP (2017), Springer), 106-126 · Zbl 1386.94068 |
| [26] | Cui, Hui; Wan, Zhiguo; Deng, Robert; Wang, Guilin; Li, Yingjiu, Efficient and expressive keyword search over encrypted data in the cloud, IEEE Trans. Dependable Secure Comput., 15, 3, 409-422 (2018) |
| [27] | De Caro, Angelo; Iovino, Vincenzo, JPBC: Java pairing based cryptography, (ISCC (2011), IEEE), 850-855 |
| [28] | Keita, Emura, A generic construction of secure-channel free searchable encryption with multiple keywords, (Network and System Security (2017), Springer), 3-18 |
| [29] | Emura, Keita; Miyaji, Atsuko; Omote, Kazumasa, Adaptive secure-channel free public-key encryption with keyword search implies timed release encryption, (ISC (2011), Springer), 102-118 |
| [30] | Emura, Keita; Miyaji, Atsuko; Rahman, Mohammad Shahriar; Omote, Kazumasa, Generic constructions of secure-channel free searchable encryption with adaptive security, Secur. Commun. Netw., 8, 8, 1547-1560 (2015), Available at Cryptology ePrint Archive Report 2013/321 |
| [31] | Emura, Keita; Rahman, Mohammad Shahriar, Constructing secure-channel free searchable encryption from anonymous IBE with partitioned ciphertext structure, (SECRYPT (2012), SciTePress), 84-93 |
| [32] | Fang, Liming; Susilo, Willy; Ge, Chunpeng; Wang, Jiandong, A secure channel free public key encryption with keyword search scheme without random oracles, (CANS (2009), Springer), 248-258 |
| [33] | Fang, Liming; Susilo, Willy; Ge, Chunpeng; Wang, Jiandong, Public key encryption with keyword search secure against keyword guessing attacks without random oracle, Inf. Sci., 238, 221-241 (2013) · Zbl 1321.94057 |
| [34] | Fuller, Benjamin; O’Neill, Adam; Reyzin, Leonid, A unified approach to deterministic encryption: new constructions and a connection to computational entropy, (TCC (2012), Springer), 582-599 · Zbl 1296.94111 |
| [35] | Furukawa, Jun, Request-based comparable encryption, (ESORICS (2013), Springer), 129-146 · Zbl 1436.94064 |
| [36] | Furukawa, Jun, Short comparable encryption, (CANS (2014), Springer), 337-352 · Zbl 1436.94065 |
| [37] | Gay, Romain; Méaux, Pierrick; Wee, Hoeteck, Predicate encryption for multi-dimensional range queries from lattices, (Public-Key Cryptography (2015), Springer), 752-776 · Zbl 1345.94062 |
| [38] | Golle, Philippe; Staddon, Jessica; Waters, Brent R., Secure conjunctive keyword search over encrypted data, (Applied Cryptography and Network Security (2004), Springer), 31-45 · Zbl 1103.68514 |
| [39] | Gu, Chunxiang; Zhu, Yuefei, New efficient searchable encryption schemes from bilinear pairings, Int. J. Netw. Secur., 10, 1, 25-31 (2010) |
| [40] | Gu, Chunxiang; Zhu, Yuefei; Pan, Heng, Efficient public key encryption with keyword search schemes from pairings, (Inscrypt (2007), Springer), 372-383 · Zbl 1166.94310 |
| [41] | Guo, Lifeng; Yau, Wei-Chuen, Efficient secure-channel free public key encryption with keyword search for EMRs in cloud storage, J. Med. Syst., 39, 2, 11 (2015) |
| [42] | Guttman, Antonin, R-trees: a dynamic index structure for spatial searching, (SIGMOD (1984), ACM), 47-57 |
| [43] | Hahn, Florian; Kerschbaum, Florian, Poly-logarithmic range queries on encrypted data with small leakage, (ACM CCSW (2016), ACM), 23-34 |
| [44] | Hattori, Mitsuhiro; Hirano, Takato; Ito, Takashi; Matsuda, Nori; Mori, Takumi; Sakai, Yusuke; Ohta, Kazuo, Ciphertext-policy delegatable hidden vector encryption and its application to searchable encryption in multi-user setting, (Cryptography and Coding (2011), Springer), 190-209 · Zbl 1291.94095 |
| [45] | Hayata, Junichiro; Ishizuka, Masahito; Sakai, Yusuke; Hanaoka, Goichiro; Matsuura, Kanta, Generic construction of adaptively secure anonymous key-policy attribute-based encryption from public-key searchable encryption, IEICE Trans., 103-A, 1, 107-113 (2020) |
| [46] | Herranz, Javier, Attribute-based encryption implies identity-based encryption, IACR Cryptol. ePrint Arch., 2017, 54 (2017) |
| [47] | Horst, Caleb; Kikuchi, Ryo; Xagawa, Keita, Cryptanalysis of comparable encryption in SIGMOD’16, (SIGMOD (2017), ACM), 1069-1084 |
| [48] | Hwang, Sangyong; Kwon, Keunjoo; Cha, Sang Kyun; Suk Lee, Byung, Performance evaluation of main-memory r-tree variants, (SSTD (2003)), 10-27 |
| [49] | Ho Hwang, Yong; Lee, Pil Joong, Public key encryption with conjunctive keyword search and its extension to a multi-user system, (Pairing (2007)), 2-22 · Zbl 1151.68405 |
| [50] | Iovino, Vincenzo; Persiano, Giuseppe, Hidden-vector encryption with groups of prime order, (Pairing-Based Cryptography (2008), Springer), 75-88 · Zbl 1186.94449 |
| [51] | Jiang, Peng; Mu, Yi; Guo, Fuchun; Wen, Qiaoyan, Public key encryption with authorized keyword search, (ACISP (2016), Springer), 170-186 · Zbl 1346.94107 |
| [52] | Karras, Panagiotis; Nikitin, Artyom; Saad, Muhammad; Bhatt, Rudrika; Antyukhov, Denis; Idreos, Stratos, Adaptive indexing over encrypted numeric data, (SIGMOD (2016), ACM), 171-183 |
| [53] | Kasamatsu, Kohei; Matsuda, Takahiro; Emura, Keita; Attrapadung, Nuttapong; Hanaoka, Goichiro; Imai, Hideki, Time-specific encryption from forward-secure encryption, (Security and Cryptography for Networks (2012), Springer), 184-204 · Zbl 1310.94154 |
| [54] | Kasamatsu, Kohei; Matsuda, Takahiro; Emura, Keita; Attrapadung, Nuttapong; Hanaoka, Goichiro; Imai, Hideki, Time-specific encryption from forward-secure encryption: generic and direct constructions, Int. J. Inf. Secur., 15, 5, 549-571 (2016) · Zbl 1310.94154 |
| [55] | Kerschbaum, Florian, Frequency-hiding order-preserving encryption, (ACM Conference on Computer and Communications Security (2015), ACM), 656-667 |
| [56] | Kerschbaum, Florian; Härterich, Martin, Searchable encryption to reduce encryption degradation in adjustably encrypted databases, (DBSec (2017), Springer), 325-336 |
| [57] | Kerschbaum, Florian; Schröpfer, Axel, Optimal average-complexity ideal-security order-preserving encryption, (ACM Conference on Computer and Communications Security (2014), ACM), 275-286 |
| [58] | Khader, Dalia, Public key encryption with keyword search based on k-resilient IBE, (ICCSA (2007), Springer), 1086-1095 · Zbl 1171.94354 |
| [59] | Kiltz, Eike, Chosen-ciphertext security from tag-based encryption, (TCC (2006), Springer), 581-600 · Zbl 1113.94008 |
| [60] | Lacharité, Marie-Sarah; Minaud, Brice; Paterson, Kenneth G., Improved reconstruction attacks on encrypted data using range query leakage, (IEEE Symposium on Security and Privacy (2018)), 297-314 |
| [61] | Lai, Junzuo; Zhou, Xuhua; Deng, Robert Huijie; Li, Yingjiu; Chen, Kefei, Expressive search on encrypted data, (ASIA CCS (2013), ACM), 243-252 |
| [62] | Lu, Yanbin, Privacy-preserving logarithmic-time search on encrypted data in cloud, (NDSS (2012), The Internet Society) |
| [63] | Lv, Zhiquan; Hong, Cheng; Zhang, Min; Feng, Dengguo, Expressive and secure searchable encryption in the public key setting, (ISC (2014), Springer), 364-376 |
| [64] | Naveed, Muhammad; Kamara, Seny; Wright, Charles V., Inference attacks on property-preserving encrypted databases, (ACM Conference on Computer and Communications Security (2015), ACM), 644-655 |
| [65] | Nishide, Takashi; Yoneyama, Kazuki; Ohta, Kazuo, Attribute-based encryption with partially hidden ciphertext policies, IEICE Trans., 92-A, 1, 22-32 (2009) |
| [66] | Park, Dong Jin; Kim, Kihyun; Lee, Pil Joong, Public key encryption with conjunctive field keyword search, (WISA (2004), Springer), 73-86 |
| [67] | Park, Jong Hwan, Efficient hidden vector encryption for conjunctive queries on encrypted data, IEEE Trans. Knowl. Data Eng., 23, 10, 1483-1497 (2011) |
| [68] | Park, Jong Hwan; Hoon Lee, Dong, A hidden vector encryption scheme with constant-size tokens and pairing computations, IEICE Trans., 93-A, 9, 1620-1631 (2010) |
| [69] | Park, Jong Hwan; Lee, Kwangsu; Susilo, Willy; Lee, Dong Hoon, Fully secure hidden vector encryption under standard assumptions, Inf. Sci., 232, 188-207 (2013) · Zbl 1293.68113 |
| [70] | Paterson, Kenneth G.; Quaglia, Elizabeth A., Time-specific encryption, (Security and Cryptography for Networks (2010), Springer), 1-16 · Zbl 1291.68163 |
| [71] | Phuong, Tran Viet Xuan; Yang, Guomin; Susilo, Willy, Efficient hidden vector encryption with constant-size ciphertext, (ESORICS (2014), Springer), 472-487 · Zbl 1481.94120 |
| [72] | Phuong, Tran Viet Xuan; Yang, Guomin; Susilo, Willy; Guo, Fuchun; Huang, Qiong, Sequence aware functional encryption and its application in searchable encryption, J. Inf. Secur. Appl., 35, 106-118 (2017) |
| [73] | Poh, Geong Sen; Chin, Ji-Jian; Yau, Wei-Chuen; Choo, Kim-Kwang Raymond; Mohamad, Moesfa Soeheila, Searchable symmetric encryption: designs and challenges, ACM Comput. Surv., 50, 3, 40:1-40:37 (2017) |
| [74] | Popa, Raluca A.; Li, Frank H.; Zeldovich, Nickolai, An ideal-security protocol for order-preserving encoding, (IEEE Symposium on Security and Privacy (2013), IEEE), 463-477 |
| [75] | Qiu, Shuo; Liu, Jiqiang; Shi, Yanfeng; Zhang, Rui, Hidden policy ciphertext-policy attribute-based encryption with keyword search against keyword guessing attack, Sci. China Inf. Sci., 60, 5, Article 052105 pp. (2017) |
| [76] | Rhee, Hyun Sook; Park, Jong Hwan; Lee, Dong Hoon, Generic construction of designated tester public-key encryption with keyword search, Inf. Sci., 205, 93-109 (2012) · Zbl 1250.94043 |
| [77] | Rhee, Hyun Sook; Park, Jong Hwan; Susilo, Willy; Lee, Dong Hoon, Improved searchable public key encryption with designated tester, (ASIA CCS (2009), ACM), 376-379 |
| [78] | Rhee, Hyun Sook; Park, Jong Hwan; Susilo, Willy; Lee, Dong Hoon, Trapdoor security in a searchable public-key encryption scheme with a designated tester, J. Syst. Softw., 83, 5, 763-771 (2010) |
| [79] | Rhee, Hyun Sook; Susilo, Willy; Kim, Hyun-Jeong, Secure searchable public key encryption scheme against keyword guessing attacks, IEICE Electron. Express, 6, 5, 237-243 (2009) |
| [80] | Saraswat, Vishal; Sahu, Rajeev Anand, Short integrated PKE+PEKS in standard model, (SPACE (2017), Springer), 226-246 · Zbl 1505.94079 |
| [81] | Sedghi, Saeed; van Liesdonk, Peter; Nikova, Svetla; Hartel, Pieter H.; Jonker, Willem, Searching keywords with wildcards on encrypted data, (Security and Cryptography for Networks (2010), Springer), 138-153 · Zbl 1286.68115 |
| [82] | Shen, Emily; Shi, Elaine; Waters, Brent, Predicate privacy in encryption systems, (TCC (2009), Springer), 457-473 · Zbl 1213.94133 |
| [83] | Shi, Elaine; Bethencourt, John; Chan, Hubert T.-H.; Song, Dawn Xiaodong; Perrig, Adrian, Multi-dimensional range query over encrypted data, (IEEE Symposium on Security and Privacy (2007), IEEE), 350-364 |
| [84] | Shi, Jie; Lai, Junzuo; Li, Yingjiu; Deng, Robert H.; Weng, Jian, Authorized keyword search on encrypted data, (ESORICS (2014), Springer), 419-435 · Zbl 1477.68099 |
| [85] | Sun, Wenhai; Hou, Shuchehomas; Ng Yu, Hui; Lou, Wenjing; TLi, Y., Protecting your right: verifiable attribute-based keyword search with fine-grained owner-enforced search authorization in the cloud, IEEE Trans. Parallel Distrib. Syst., 27, 4, 1187-1198 (2016) |
| [86] | Suzuki, Tatsuya; Emura, Keita; Ohigashi, Toshihiro, A generic construction of integrated secure-channel free PEKS and PKE, (ISPEC (2018)), 69-86 · Zbl 1515.68123 |
| [87] | Suzuki, Tatsuya; Emura, Keita; Ohigashi, Toshihiro, A generic construction of integrated secure-channel free PEKS and PKE and its application to EMRs in cloud storage, J. Med. Syst., 43, 5, 128:1-128:15 (2019) |
| [88] | Teranishi, Isamu; Yung, Moti; Malkin, Tal, Order-preserving encryption secure beyond one-wayness, (ASIACRYPT (2014), Springer), 42-61 · Zbl 1317.94136 |
| [89] | Tseng, Fu-Kuo; Liu, Yung-Hsiang; Chen, Rong-Jaye; Lin, Bao-Shuh Paul, Statistics on encrypted cloud data, (IWSEC (2013), Springer), 133-150 · Zbl 1419.68051 |
| [90] | Wang, Boyang; Hou, Yantian; Li, Ming; Wang, Haitao; Li, Hui, Maple: scalable multi-dimensional range search over encrypted cloud data with tree-based index, (ASIA CCS (2014), ACM), 111-122 |
| [91] | Wang, Boyang; Li, Ming; Wang, Haitao, Geometric range search on encrypted spatial data, IEEE Trans. Inf. Forensics Secur., 11, 4, 704-719 (2016) |
| [92] | Wang, Peng; Ravishankar, Chinya V., Secure and efficient range queries on outsourced databases using \(\hat{R} \)-trees, (ICDE (2013), IEEE), 314-325 |
| [93] | Wang, Tingting; Ho Au, Man; Wu, Wei, An efficient secure channel free searchable encryption scheme with multiple keywords, (Network and System Security (2016), Springer), 251-265 |
| [94] | Wee, Hoeteck, Public key encryption against related key attacks, (Public Key Cryptography (2012), Springer), 262-279 · Zbl 1290.94138 |
| [95] | Yang, Yang; Ma, Maode, Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for E-health clouds, IEEE Trans. Inf. Forensics Secur., 11, 4, 746-759 (2016) |
| [96] | Zhang, Rui; Imai, Hideki, Combining public key encryption with keyword search and public key encryption, IEICE Trans., 92-D, 5, 888-896 (2009) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
