×

zbMATH — the first resource for mathematics

Public key encryption with keyword search secure against keyword guessing attacks without random oracle. (English) Zbl 1321.94057
Summary: The notion of public key encryption with keyword search (PEKS) was put forth by Boneh et al. to enable a server to search from a collection of encrypted emails given a “trapdoor” (i.e., an encrypted keyword) provided by the receiver. The nice property in this scheme allows the server to search for a keyword, given the trapdoor. Hence, the verifier can merely use an untrusted server, which makes this notion very practical. Following Boneh et al.’s work, there have been subsequent works that have been proposed to enhance this notion. Two important notions include the so-called keyword guessing attack and secure channel free, proposed by Byun et al. and Baek et al., respectively. The former realizes the fact that in practice, the space of the keywords used is very limited, while the latter considers the removal of secure channel between the receiver and the server to make PEKS practical. Unfortunately, the existing construction of PEKS secure against keyword guessing attack is only secure under the random oracle model, which does not reflect its security in the real world. Furthermore, there is no complete definition that captures secure channel free PEKS schemes that are secure against chosen keyword attack, chosen ciphertext attack, and against keyword guessing attacks, even though these notions seem to be the most practical application of PEKS primitives. In this paper, we make the following contributions. First, we define the strongest model of PEKS which is secure channel free and secure against chosen keyword attack, chosen ciphertext attack, and keyword guessing attack. In particular, we present two important security notions namely IND-SCF-CKCA and IND-KGA. The former is to capture an inside adversary, while the latter is to capture an outside adversary. Intuitively, it should be clear that IND-SCF-CKCA captures a more stringent attack compared to IND-KGA. Second, we present a secure channel free PEKS scheme secure without random oracle under the well known assumptions, namely DLP, DBDH, SXDH and truncated \(q\)-ABDHE assumption. Our contributions fill the gap in the literature and hence, making the notion of PEKS very practical. We shall highlight that our scheme is IND-SCF-CKCA secure.

MSC:
94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdalla, M.; Bellare, M.; Catalano, D.; Kiltz, E.; Kohno, T.; Lange, T.; Malone-Lee, J.; Neven, G.; Paillier, P.; Shi, H., Searchable encryption revisited: consistency properties, relation to anonymous IBE and extensions, (Proc. of The 25th Annual International Cryptology Conference, Advances in Cryptology-CRYPTO 2005, LNCS, 3621, (2005), Springer-Verlag), 205-222 · Zbl 1145.94430
[2] Baek, J.; Safavi-Naini, R.; Susilo, W., Public key encryption with keyword search revisited, (Proc. of Applied Cryptography and Information Security 06, ACIS 2006, LNCS, 5072, (2008), Springer-Verlag), 1249-1259
[3] Baek, J.; Safavi-Naini, R.; Susilo, W., On the integration of public key data encryption and public key encryption with keyword search, (Proc. of 9th Information Security Conference, ISC 2006, LNCS, 4176, (2006), Springer-Verlag), 217-232 · Zbl 1156.94331
[4] Boneh, D.; Di Crescenzo, G.; Ostrovsky, R.; Persiano, G., Public key encryption with keyword search, (Proc. of International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology-EUROCRYPT 2004, LNCS, 3027, (2004), Springer-Verlag), 506-522 · Zbl 1122.68424
[5] Boneh, D.; Waters, B., Conjunctive, subset, and range queries on encrypted data, (Proc. of Fourth IACR Theory of Cryptography Conference, TCC 2007, LNCS, 4392, (2007), Springer-Verlag), 535-554 · Zbl 1156.94335
[6] Byun, J. W.; Rhee, H. S.; Park, H. A.; Lee, D. H., Off-line keyword guessing attacks on recent keyword search schemes over encrypted data, (Proc. of 3rd VLDB Workshop on Secure Data Management, SDM 2006, LNCS, 4165, (2006), Springer-Verlag), 75-83
[7] Canetti, R.; Goldreich, O.; Halevi, S., The random oracle methodology, revisited, (Proc. of the Thirtieth Annual ACM Symposium on the Theory of Computing, STOC 1998, (1998), ACM Press), 209-218 · Zbl 1027.68603
[8] Canetti, R.; Halevi, S.; Katz, J., Chosen-ciphertext security from identity-based encryption, (EUROCRYPT 2004, LNCS, 3027, (2004), Springer Heidelberg), 202-222 · Zbl 1122.94358
[9] C. Dong, N. Dulay, Longitude: a privacy-preserving location sharing protocol for mobile applications, in: Proc. of IFIPTM 2011. IFIP AICT 358, 2011, pp. 133-148.
[10] L. Fang, W. Susilo, C. Ge, J. Wang, A secure channel free public key encryption with keyword search scheme without random oracle, in: Proc. of Cryptology and Network Security, 8th International Conference, CANS 2009, LNCS 5888, Springer, Heidelberg, 2009, pp. 248-258.
[11] Farashahi, R. R.; Schoenmakers, B.; Sidorenko, A., Efficient pseudorandom generators based on the DDH assumption, (Proc. of PKC 2007, LNCS, 4450, (2007), Springer Heidelberg), 426-441 · Zbl 1161.65305
[12] Fuhr, T.; Paillier, P., Decryptable searchable encryption, (Proc. of First International Conference on Provable Security, ProvSection 2007, LNCS, 4784, (2007), Springer-Verlag), 228-236 · Zbl 1138.94363
[13] Gentry, C., Practical identity-based encryption without random oracles, (Proc. of 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology-EUROCRYPT 2006, LNCS, 4004, (2006), Springer-Verlag), 457-464 · Zbl 1140.94340
[14] Gu, C.; Zhu, Y.; Pan, H., Efficient public key encryption with keyword search schemes from pairings, (Proc. of Information Security and Cryptology: Third SKLOIS Conference, Inscrypt 2007, LNCS, 4990, (2007), Springer-Verlag), 372-383 · Zbl 1166.94310
[15] Golle, P.; Staddon, J.; Waters, B., Secure conjunctive search over encrypted data, (Jakobsson, M.; Yung, M.; Zhou, J., Proc. of Second International Conference on Applied Cryptography and Network Security, ACNS 2004, LNCS, 3089, (2004), Springer-Verlag), 31-45 · Zbl 1103.68514
[16] Green, M.; Hohenberger, S., Universally composable adaptive oblivious transfer, (Proc. of of The 14th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2008, LNCS, 5350, (2008), Springer-Verlag), 179-197 · Zbl 1206.94068
[17] Groth, J.; Sahai, A., Efficient non-interactive proof systems for bilinear groups, (Proc. of 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology-EUROCRYPT 2008, LNCS, 4965, (2008), Springer-Verlag), 415-432 · Zbl 1149.94320
[18] Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association. Express, 58, 301, 13-30, (1963) · Zbl 0127.10602
[19] D. Hofheinz, E. Weinreb, Searchable encryption with decryption in the standard model. Cryptology ePrint Archive, Report 2008/423, 2008. <http://eprint.iacr.org/2008/423>.
[20] Jeong, I. R.; Kwon, J. O.; Hong, D.; Lee, D. H., Constructing PEKS schemes secure against keyword guessing attacks is possible?, Computer Communications Express, 32, 2, 394-396, (2009)
[21] E. Kiltz, D. Galindo, Direct chosen-ciphertext secure identity-based key encapsulation without random oracles, in: Proc. of Information Security and Privacy, 11th Australasian Conference, ACISP 2006, LNCS 4058, Springer-Verlag, 2006, pp. 336-347. · Zbl 1176.94046
[22] Kiltz, E.; Galindo, D., Direct chosen-ciphertext secure identity-based key encapsulation without random oracles, Theoretical Computer Science Elsevier, 410, 47-49, 5093-5111, (2009) · Zbl 1194.68111
[23] Kiltz, E.; Vahlis, Y., CCA2 secure IBE: standard model efficiency through authenticated symmetric encryption, (Proc. of RSA Conference 2008, Cryptographers’ Track, CT-RSA 2008, LNCS, 4964, (2008), Springer-Verlag), 221-238 · Zbl 1153.94400
[24] Okamoto, T.; Sakurai, K.; Shizuya, H., How intractable is the discrete logarithm for a general finite group?, (Proc. Eurocrypt 1992, Lecture Notes in Computer Science, 658, (1992), Springer-Verlag Berlin), 420-428 · Zbl 0801.68089
[25] Park, D. J.; Kim, K.; Lee, P. J., Public key encryption with conjunctive field keyword search, (Lim, C. H.; Yung, M., Proc. of Information Security Applications, 5th International Workshop, WISA 2004, LNCS, 3325, (2005), Springer-Verlag), 73-86
[26] Petit, C.; Standaert, F.; Pereira, O.; Malkin, T. G.; Yung, M., A block cipher based pseudo random number generator secure against side-channel key recovery, (Proc. of the 3th international Symposium on information, Computer, and Communications Security, ASIACCS 2008, (2008), ACM New York, NY), 56-65
[27] Rhee, H. S.; Park, J. H.; Susilo, W.; Lee, D. H., Improved searchable public key encryption with designated tester, (Proc. of the 4th international Symposium on information, Computer, and Communications Security, ASIACCS 2009, (2009), ACM New York, NY), 376-379
[28] Rhee, H. S.; Park, J. H.; Lee, D. H., Generic construction of designated tester public-key encryption with keyword search, Information Sciences. Express, 205, 1, 93-109, (2012) · Zbl 1250.94043
[29] Rhee, H. S.; Susilo, W.; Kim, H-J., Secure searchable public key encryption scheme against keyword guessing attacks, IEICE Electron. Express, 6, 5, 237-243, (2009)
[30] Rhee, H. S.; Park, J. H.; Susilo, W.; Lee, D. H., Trapdoor security in a searchable public-key encryption scheme with a designated tester, Journal of Systems and Software, Express, 83, 5, 763-771, (2010)
[31] Shao, J.; Cao, Z.; Liang, X.; Lin, H., Proxy re-encryption with keyword search, Information Sciences. Express, 180, 13, 2576-2587, (2010) · Zbl 1191.94100
[32] Vazirani, U. V.; Vazirani, V. V., Efficient and secure pseudo-random number generation, (Proc. of 25th Annual Symposium on Foundations of Computer Science, LNCS, 3494, (1984), Springer-Verlag), 458-463 · Zbl 0579.65005
[33] Waters, B., Efficient identity-based encryption without random oracles, (Proc. of 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology-EUROCRYPT 2005, LNCS, 3494, (2005), Springer-Verlag), 114-127 · Zbl 1137.94360
[34] B. Waters, D. Balfanz, G. Durfee, D. Smetters, Building an encrypted and searchable audit log, in: Proc. of Network and Distributed System Security Symposium, NDSS 2004, 2004.
[35] Yau, W. C.; Heng, S. H.; Goi, B., Off-line keyword guessing attacks on recent public key encryption with keyword search schemes, (Proc. of the 5th International Conference on Autonomic and Trusted Computing, ATC 2008, LNCS, 5060, (2008), Springer-Verlag), 100-105
[36] Zhang, B.; Zhang, F., An efficient public key encryption with conjunctive-subset keywords search, Journal of Network and Computer Applications. Express, 34, 1, 262-267, (2011)
[37] Zhang, R.; Imai, H., Generic combination of public key encryption with keyword search and public key encryption, (Proc. of Cryptology and Network Security, 6th International Conference, CANS 2007, LNCS, 4856, (2007), Springer-Verlag), 159-174 · Zbl 1282.94075
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.