Communications in Cryptology IACR CiC

Public-Key Authenticated Encryption with Keyword Search Made Easy


Qinyi Li, Xavier Boyen
Qinyi Li ORCID
Griffith University, Brisbane, Australia
qinyi dot li at griffith dot edu dot au
Xavier Boyen
QUT, Brisbane, Australia
xavier dot boyen at qut dot edu dot au


Public-key searchable encryption allows keyword-associated tokens to be used to test if a ciphertext contains specific keywords. Due to the low entropies of keywords, the token holder can create ciphertexts from candidate keywords and test them using the token in hand to recover the keywords, known as inside keyword guessing attacks (IKGA). Public-key authenticated encryption with keyword search is a searchable encryption proposed to defend against such attacks. It ensures the sender's private key protects the ciphertexts from the IKGA. PAEKS schemes with reasonable security and practical efficiency remain elusive despite many proposals. This work provides a simple generic PAEKS scheme from non-interactive key exchange (NIKE) and symmetric-key equality-predicate encryption with three new constructions for the latter, respectively from pseudorandom functions (PRFs), the decision bilinear Diffie-Hellman assumption, and the learning-with-errors assumption. Instantiating our generic scheme, we derive several PAEKS schemes from the most well-known assumptions, with some of them achieving full cipher-keyword indistinguishability and full token indistinguishability in the standard model, for the first time. Our instantiated schemes allow practical implementations and outperform the existing PAEKS schemes under the same assumptions.


Shashank Agrawal, Shweta Agrawal, Saikrishna Badrinarayanan, Abishek Kumarasubramanian, Manoj Prabhakaran, and Amit Sahai. Functional Encryption and Property Preserving Encryption: New Definitions and Positive Results. Cryptology ePrint Archive, Paper 2013/744. 2013.
Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient Lattice (H)IBE in the Standard Model. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 553-572. Springer Berlin Heidelberg 2010. DOI: 10.1007/978-3-642-13190-5_28
Fabrice Benhamouda, Olivier Blazy, Léo Ducas, and Willy Quach. Hash Proof Systems over Lattices Revisited. In Michel Abdalla and Ricardo Dahab, editors, Public-Key Cryptography – PKC 2018, pages 644–674, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-319-76581-5_22
Dan Boneh, Giovanni Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public Key Encryption with Keyword Search. In Advances in Cryptology - EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 506-522. Springer Berlin Heidelberg 2004. DOI: 10.1007/978-3-540-24676-3_30
Pauline Bert, Gautier Eberhart, Lucas Prabel, Adeline Roux-Langlois, and Mohamed Sabt. Implementation of lattice trapdoors on modules and applications. In Post-Quantum Cryptography – PQCrypto 2021, pages 195–214. 2021. Springer. DOI: 10.1007/978-3-030-81293-5_11
Dan Boneh and Matt Franklin. Identity-Based Encryption from the Weil Pairing. In Joe Kilian, editor, Advances in Cryptology–CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 213-229. Springer Berlin Heidelberg 2001. DOI: 10.1007/3-540-44647-8_13
Zvika Brakerski and Gil Segev. Function-private functional encryption in the private-key setting. Journal of Cryptology, 31:202–225, 2018. DOI: 10.1007/s00145-017-9261-0
Xavier Boyen and Brent Waters. Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles). In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, volume 4117 of Lecture Notes in Computer Science, pages 290-307. Springer Berlin Heidelberg 2006. DOI: 10.1007/11818175_17
David Cash, Eike Kiltz, and Victor Shoup. The twin Diffie–Hellman problem and applications. Journal of Cryptology, 22:470–504, 2009. DOI: 10.1007/s00145-009-9041-6
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: an efficient post-quantum commutative group action. In Advances in Cryptology–ASIACRYPT 2018, pages 395–427. 2018. Springer. DOI: 10.1007/978-3-030-03332-3_15
Leixiao Cheng and Fei Meng. Public key authenticated encryption with keyword search from LWE. In European Symposium on Research in Computer Security, pages 303–324. 2022. Springer. DOI: 10.1007/978-3-031-17140-6_15
Leixiao Cheng, Jing Qin, Feng Feng, and Fei Meng. Security-enhanced public-key authenticated searchable encryption. Information Sciences, 647:119454, 2023. DOI: 10.1016/j.ins.2023.119454
Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE transactions on Information Theory, 22(6):644–654, 1976. DOI: 10.1109/TIT.1976.1055638
Bor de Kock. A non-interactive key exchange based on ring-learning with errors. PhD thesis, Master’s thesis. Master’s thesis, Eindhoven University of Technology, 2018.
Léo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient identity-based encryption over NTRU lattices. In International Conference on the Theory and Application of Cryptology and Information Security, pages 22–41. 2014. Springer. DOI: 10.1007/978-3-662-45608-8_2
Léo Ducas and Daniele Micciancio. Improved Short Lattice Signatures in the Standard Model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, pages 335–352, Berlin, Heidelberg. 2014. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-44371-2_19
Keita Emura. Generic construction of public-key authenticated encryption with keyword search revisited: stronger security and efficient construction. In Proceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop, pages 39–49. 2022. DOI: 10.1145/3494105.352623
Eduarda SV Freire, Dennis Hofheinz, Eike Kiltz, and Kenneth G Paterson. Non-interactive key exchange. In Public-Key Cryptography–PKC 2013, pages 254–271. 2013. Springer. DOI: 10.1007/978-3-642-36362-7_17
Phillip Gajland, Bor de Kock, Miguel Quaresma, Giulio Malavolta, and Peter Schwabe. Swoosh: Efficient Lattice-Based Non-Interactive Key Exchange. In USENIX Security Symposium – USENIX Security 2024. 2024. USENIX Association.
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th annual ACM symposium on Theory of computing, pages 197–206, New York, NY, USA. 2008. ACM. DOI: 10.1145/1374376.1374407
Julia Hesse, Dennis Hofheinz, and Lisa Kohl. On tightly secure non-interactive key exchange. In Annual International Cryptology Conference – CRYPTO 2018, pages 65–94. 2018. Springer. DOI: 10.1007/978-3-319-96881-0_3
Shuichi Katsumata and Shota Yamada. Partitioning via non-linear polynomial functions: More compact ibes from ideal lattices and bilinear maps. In Advances in Cryptology–ASIACRYPT 2016, pages 682–712. 2016. Springer. DOI: 10.1007/978-3-662-53890-6_23
Hongbo Li, Qiong Huang, Jianye Huang, and Willy Susilo. Public-key authenticated encryption with keyword search supporting constant trapdoor generation and fast search. IEEE Transactions on Information Forensics and Security, 18:396–410, 2022. DOI: 10.1109/TIFS.2022.3224308
Zi-Yuan Liu, Yi-Fan Tseng, Raylin Tso, Masahiro Mambo, and Yu-Chi Chen. Public-key authenticated encryption with keyword search: Cryptanalysis, enhanced security, and quantum-resistant instantiation. In Proceedings of the 2022 ACM on Asia conference on computer and communications security, pages 423–436. 2022. DOI: 10.1145/3488932.3497760
Zengpeng Li and Ding Wang. Achieving one-round password-based authenticated key exchange over lattices. IEEE transactions on services computing, 15(1):308–321, 2019. DOI: 10.1109/TSC.2019.2939836
Daniele Micciancio and Chris Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 700-718. Springer Berlin Heidelberg 2012. DOI: 10.1007/978-3-642-29011-4_41
Mahnaz Noroozi and Ziba Eslami. Public key authenticated encryption with keyword search: revisited. IET Information Security, 13(4):336–342, 2019. DOI: 10.1049/iet-ifs.2018.5315
Baodong Qin, Yu Chen, Qiong Huang, Ximeng Liu, and Dong Zheng. Public-key authenticated encryption with keyword search revisited: Security model and constructions. Information Sciences, 516:515–528, 2020. DOI: 10.1016/j.ins.2019.12.063
Baodong Qin, Hui Cui, Xiaokun Zheng, and Dong Zheng. Improved security model for public-key authenticated encryption with keyword search. In Provable and Practical Security – ProvSec 2021, pages 19–38. 2021. Springer. DOI: 10.1007/978-3-030-90402-9_2
Adi Shamir. Identity-Based Cryptosystems and Signature Schemes. In GeorgeRobert Blakley and David Chaum, editors, Advances in Cryptology, volume 196 of Lecture Notes in Computer Science, pages 47-53. Springer Berlin Heidelberg 1985. DOI: 10.1007/3-540-39568-7_5
Ryuichi Sakai, Kiyoshi Ohgishi, and Masao Kasahara. Cryptosystems based on pairing. In Symposium on Cryptography and Information Security. 2000. Springer.
Emily Shen, Elaine Shi, and Brent Waters. Predicate Privacy in Encryption Systems. In Omer Reingold, editor, Theory of Cryptography, pages 457–473, Berlin, Heidelberg. 2009. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-00457-5_27
Tao Xiang, Zhongming Wang, Biwen Chen, Xiaoguo Li, Peng Wang, and Fei Chen. StopGuess: A framework for public-key authenticated encryption with keyword search. Computer Standards & Interfaces, 88:103805, 2024. DOI: 10.1016/j.csi.2023.103805

PDFPDF Open access

Submitted: 2024-04-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite

Qinyi Li and Xavier Boyen, "Public-Key Authenticated Encryption with Keyword Search Made Easy," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/a63z11zn4.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.