Dynamic searchable public-key encryption and its application

Abstract

Public-key encryption with keyword search (PEKS) is a well-known method for privacy-preserving keyword search in encrypted email systems due to its public-key characteristics. However, we have observed that even without a keyword-search trapdoor, traditional PEKS allows the server to distinguish ciphertexts effectively, compromising semantic security. To address this limitation, we introduce dynamic searchable public-key encryption (DSPE), a concept that conceals relationships between searchable ciphertexts and their corresponding encrypted files, ensuring semantic security in both theory and practice. DSPE also enables the server to delete specific ciphertexts as requested by the receiver. We present a DSPE instance with provable semantic security in the random oracle model, which offers the advantage of sublinear complexity in identifying matching ciphertexts and deleting intended ones. Through experimental validation, we demonstrate the feasibility of this instance. Furthermore, we construct a DSPE-based cloud email system in the double-cloud model and evaluate its performance.

Graphical abstract

Keywords

public-key encryption with keyword search / dynamic searchable public-key encryption / semantic security

References

[1] Boneh D, Crescenzo G D, Ostrovsky R, Persiano G. Public key encryption with keyword search. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 2004, 506−522

[2] Zhou Y, Li N, Tian Y, An D, Wang L . Public key encryption with keyword search in cloud: a survey. Entropy, 2020, 22( 4): 421

[3] Xu P, Wu Q, Wang W, Susilo W, Domingo-Ferrer J, Jin H . Generating searchable public-key ciphertexts with hidden structures for fast keyword search. IEEE Transactions on Information Forensics and Security, 2015, 10( 9): 1993–2006

[4] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006, 79−88

[5] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: Proceedings of 2012 ACM Conference on Computer and Communications Security. 2012, 965−976

[6] Boneh D, Franklin M. Identity-based encryption from the Weil pairing. In: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology. 2001, 213−229

[7] Wouters P, Huigens D, Winter J, Niibe Y. OpenPGP. RFC, 2024, 1−166

[8] Xu P, Jiao T, Wu Q, Wang W, Jin H . Conditional identitybased broadcast proxy re-encryption and its application to cloud email. IEEE Transactions on Computers, 2016, 65( 1): 66–79

[9] Stefanov E, Shi E. Multi-cloud oblivious storage. In: Proceedings of 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 247−258

[10] Bohli J M, Gruschka N, Jensen M, Iacono L L, Marnau N . Security and privacy-enhancing multicloud architectures. IEEE Transactions on Dependable and Secure Computing, 2013, 10( 4): 212–224

[11] Chen R, Mu Y, Yang G, Guo F, Wang X . Dual-server public-key encryption with keyword search for secure cloud storage. IEEE Transactions on Information Forensics and Security, 2016, 11( 4): 789–798

[12] Housley R, Polk W T, Ford W, Solo D. Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile. RFC, 2002, 1−129

[13] 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. In: Proceedings of the 25th Annual International Conference on Advances in Cryptology. 2005, 205−222

[14] Di Crescenzo G, Saraswat V. Public key encryption with searchable keywords based on Jacobi symbols. In: Proceedings of the 8th International Conference on Cryptology in India on Progress in Cryptology. 2007, 282−296

[15] Khader D. Public key encryption with keyword search based on k-resilient IBE. In: Proceedings of International Conference on Computational Science and Its Applications. 2007, 1086−1095

[16] Behnia R, Ozmen M O, Yavuz A A . Lattice-based public key searchable encryption from experimental perspectives. IEEE Transactions on Dependable and Secure Computing, 2020, 17( 6): 1269–1282

[17] Zhang X, Xu C, Wang H, Zhang Y, Wang S . FS-PEKS: lattice-based forward secure public-key encryption with keyword search for cloud-assisted industrial internet of things. IEEE Transactions on Dependable and Secure Computing, 2021, 18( 3): 1019–1032

[18] Jiang C, Xu C, Zhang Z, Chen K . SR-PEKS: subversion-resistant public key encryption with keyword search. IEEE Transactions on Cloud Computing, 2023, 11( 3): 3168–3183

[19] Zhou Y, Hu Z, Li F . Searchable public-key encryption with cryptographic reverse firewalls for cloud storage. IEEE Transactions on Cloud Computing, 2023, 11( 1): 383–396

[20] Ming Y, Liu H, Wang C, Zhao Y . Generic construction: cryptographic reverse firewalls for public key encryption with keyword search in cloud storage. IEEE Transactions on Cloud Computing, 2024, 12( 2): 405–418

[21] Park D J, Kim K, Lee P J. Public key encryption with conjunctive field keyword search. In: Proceedings of the 5th International Workshop on Information Security Applications. 2004, 73−86

[22] Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted data. In: Proceedings of the 2nd International Conference on Applied Cryptography and Network Security. 2004, 31−45

[23] Ballard L, Kamara S, Monrose F. Achieving efficient conjunctive keyword searches over encrypted data. In: Proceedings of the 7th International Conference on Information and Communications Security. 2005, 414−426

[24] Hwang Y H, Lee P J. Public key encryption with conjunctive keyword search and its extension to a multi-user system. In: Proceedings of the 1st International Conference on Pairing-Based Cryptography. 2007, 2−22

[25] Ryu E K, Takagi T. Efficient conjunctive keyword-searchable encryption. In: Proceedings of the 21st International Conference on Advanced Information Networking and Applications. 2007, 409−414

[26] Yang Y, Ma M . Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for e-health clouds. IEEE Transactions on Information Forensics and Security, 2016, 11( 4): 746–759

[27] Lu Y, Li J . Privacy-preserving and forward public key encryption with field-free multi-keyword search for cloud encrypted data. IEEE Transactions on Cloud Computing, 2023, 11( 4): 3619–3630

[28] Zhang Y, Zhao Y, Wang Y, Li Y . Searchable public key encryption supporting simple Boolean keywords search. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2020, E103.A( 1): 114–124

[29] Zhang Y, He W, Li Y . Efficient Boolean keywords search over encrypted cloud data in public key setting. Mobile Information Systems, 2020, 2020: 2904861

[30] Xu P, Tang S, Xu P, Wu Q, Hu H, Susilo W . Practical multi-keyword and Boolean search over encrypted email in cloud server. IEEE Transactions on Services Computing, 2021, 14( 6): 1877–1889

[31] Meng L, Chen L, Tian Y, Manulis M, Liu S. FEASE: fast and expressive asymmetric searchable encryption. In: Proceedings of the 33rd USENIX Conference on Security Symposium. 2024, 2545−2562

[32] Xu P, Jin H, Wu Q, Wang W . Public-key encryption with fuzzy keyword search: a provably secure scheme under keyword guessing attack. IEEE Transactions on Computers, 2013, 62( 11): 2266–2277

[33] Shi E, Bethencourt J, Chan T H H, Song D, Perrig A. Multi-dimensional range query over encrypted data. In: Proceedings of 2007 IEEE Symposium on Security and Privacy. 2007, 350−364

[34] Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data. In: Proceedings of the 4th Theory of Cryptography Conference on Theory of Cryptography. 2007, 535−554

[35] Zhang B, Zhang F . An efficient public key encryption with conjunctive-subset keywords search. Journal of Network and Computer Applications, 2011, 34( 1): 262–267

[36] Chenam V B, Tummala S Y, Ali S T . Public key authenticated encryption with field-free subset conjunctive and disjunctive keyword search against keyword guessing attacks. Peer-to-Peer Networking and Applications, 2024, 17( 3): 1036–1050

[37] Desmoulins N, Fouque P A, Onete C, Sanders O. Pattern matching on encrypted streams. In: Proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security. 2018, 121−148

[38] Bouscatié É, Castagnos G, Sanders O. Public key encryption with flexible pattern matching. In: Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security on Advances in Cryptology. 2021, 342−370

[39] Davis D, Monrose F, Reiter M K. Time-scoped searching of encrypted audit logs. In: Proceedings of the 6th International Conference on Information and Communications Security. 2004, 532−545

[40] Cheung D W, Mamoulis N, Wong W K, Yiu S M, Zhang Y. Anonymous fuzzy identity-based encryption for similarity search. In: Proceedings of the 21st International Symposium on Algorithms and Computation. 2010, 61−72

[41] Tang Q, Chen X. Towards asymmetric searchable encryption with message recovery and flexible search authorization. In: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013, 253−264

[42] Ibraimi L, Nikova S, Hartel P H, Jonker W. Public-key encryption with delegated search. In: Proceedings of the 9th International Conference on Applied Cryptography and Network Security. 2011, 532−549

[43] Li J, Lin X, Zhang Y, Han J . KSF-OABE: outsourced attribute-based encryption with keyword search function for cloud storage. IEEE Transactions on Services Computing, 2017, 10( 5): 715–725

[44] Xu L, Li W, Zhang F, Cheng R, Tang S . Authorized keyword searches on public key encrypted data with time controlled keyword privacy. IEEE Transactions on Information Forensics and Security, 2020, 15: 2096–2109

[45] Chaudhari P, Das M L . KeySea: keyword-based search with receiver anonymity in attribute-based searchable encryption. IEEE Transactions on Services Computing, 2022, 15( 2): 1036–1044

[46] Chen Y, Li W, Gao F, Wen Q, Zhang H, Wang H . Practical attribute-based multi-keyword ranked search scheme in cloud computing. IEEE Transactions on Services Computing, 2022, 15( 2): 724–735

[47] Miao Y, Li F, Jia X, Wang H, Liu X, Choo K R, Deng R H . REKS: role-based encrypted keyword search with enhanced access control for outsourced cloud data. IEEE Transactions on Dependable and Secure Computing, 2024, 21( 4): 3247–3261

[48] Ling Y, Zhang K, Chen J, Huang Q, Qian H. Public-key encryption with keyword search in multi-user, multi-challenge setting under adaptive corruptions. In: Proceedings of the 27th IACR International Conference on Practice and Theory of Public-Key Cryptography. 2024, 105−126

[49] Cheng L, Meng F . Server-aided public key authenticated searchable encryption with constant ciphertext and constant trapdoor. IEEE Transactions on Information Forensics and Security, 2024, 19: 1388–1400

[50] Byun J W, Rhee H S, Park H, Lee D H. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data. In: Proceedings of the 3rd VLDB Workshop on Secure Data Management. 2006, 75−83

[51] Baek J, Safavi-Naini R, Susilo W. Public key encryption with keyword search revisited. In: Proceedings of International Conference on Computational Science and Its Applications. 2008, 1249−1259

[52] Rhee H S, Susilo W, Kim H J . Secure searchable public key encryption scheme against keyword guessing attacks. IEICE Electronics Express, 2009, 6( 5): 237–243

[53] Rhee H S, Park J H, Susilo W, Lee D H. Improved searchable public key encryption with designated tester. In: Proceedings of the 4th International Symposium on Information, Computer and Communications Security. 2009, 376−379

[54] Fang L, Susilo W, Ge C, Wang J. A secure channel free public key encryption with keyword search scheme without random oracle. In: Proceedings of the 8th International Conference on Cryptology and Network Security. 2009, 248−258

[55] Rhee H S, Park J H, Lee D H . Generic construction of designated tester public-key encryption with keyword search. Information Sciences, 2012, 205: 93–109

[56] Fang L, Susilo W, Ge C, Wang J . Public key encryption with keyword search secure against keyword guessing attacks without random oracle. Information Sciences, 2013, 238: 221–241

[57] Huang Q, Li H. An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks. Information Sciences, 2017, 403−404: 1−14

[58] He D, Ma M, Zeadally S, Kumar N, Liang K . Certificateless public key authenticated encryption with keyword search for industrial internet of things. IEEE Transactions on Industrial Informatics, 2018, 14( 8): 3618–3627

[59] Chen B, Wu L, Zeadally S, He D . Dual-server public-key authenticated encryption with keyword search. IEEE Transactions on Cloud Computing, 2022, 10( 1): 322–333

[60] Cheng L, Meng F. Public key authenticated encryption with keyword search from LWE. In: Proceedings of the 27th European Symposium on Research in Computer Security. 2022, 303−324

[61] Li H, Huang Q, Huang J, Susilo W . Public-key authenticated encryption with keyword search supporting constant trapdoor generation and fast search. IEEE Transactions on Information Forensics and Security, 2023, 18: 396–410

[62] Zhou X, He D, Ning J, Luo M, Huang X . Single-server public-key authenticated encryption with keyword search and its application in IIoT. IEEE Transactions on Network Science and Engineering, 2024, 11( 1): 404–415

[63] Chen R, Mu Y, Yang G, Guo F, Huang X, Wang X, Wang Y . Server-aided public key encryption with keyword search. IEEE Transactions on Information Forensics and Security, 2016, 11( 12): 2833–2842

[64] Zheng Y, Xu P, Wang W, Chen T, Susilo W, Liang K, Jin H. DEKS: a secure cloud-based searchable service can make attackers pay. In: Proceedings of the 27th European Symposium on Research in Computer Security on Computer Security. 2022, 86−104

[65] Bellare M, Boldyreva A, O’Neill A. Deterministic and efficiently searchable encryption. In: Proceedings of the 27th Annual International Cryptology Conference on Advances in Cryptology. 2007, 535−552

[66] Bellare M, Fischlin M, O’Neill A, Ristenpart T. Deterministic encryption: definitional equivalences and constructions without random oracles. In: Proceedings of the 28th Annual International Cryptology Conference on Advances in Cryptology. 2008, 360−378

[67] Boldyreva A, Fehr S, O’Neill A. On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Proceedings of the 28th Annual International Cryptology Conference on Advances in Cryptology. 2008, 335−359

RIGHTS & PERMISSIONS

Higher Education Press