Public-Key Authenticated Encryption with Keyword Search Made Easy

Qinyi Li; Xavier Boyen

doi:10.62056/a63z11zn4

Public-Key Authenticated Encryption with Keyword Search Made Easy

Authors

Qinyi Li, Xavier Boyen

Qinyi Li

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

Keywords: Public-Key Authenticated Encryption Keywords Search Post-quantum Token Privacy Generic Constructions

Abstract

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.

References

[AAB⁺13]

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.

Google Scholar ePrint

[ABB10]

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

Google Scholar ePrint

[BBDQ18]

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

Google Scholar ePrint

[BCOP04]

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

Google Scholar ePrint

[BEP⁺21]

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

Google Scholar ePrint

[BF01]

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

Google Scholar ePrint

[BS18]

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

Google Scholar ePrint

[BW06]

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

Google Scholar ePrint

[CKS09]

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

Google Scholar ePrint

[CLM⁺18]

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

Google Scholar ePrint

[CM22]

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

Google Scholar ePrint

[CQFM23]

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

Google Scholar ePrint

[DH76]

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

Google Scholar ePrint

[dK18]

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.

Google Scholar ePrint

[DLP14]

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

Google Scholar ePrint

[DM14]

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

Google Scholar ePrint

[Emu22]

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

Google Scholar ePrint

[FHKP13]

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

Google Scholar ePrint

[GdKQ⁺24]

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.

Google Scholar ePrint

[GPV08]

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

Google Scholar ePrint

[HHK18]

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

Google Scholar ePrint

[KY16]

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

Google Scholar ePrint

[LHHS22]

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

Google Scholar ePrint

[LTT⁺22]

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

Google Scholar ePrint

[LW19]

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

Google Scholar ePrint

[MP12]

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

Google Scholar ePrint

[NE19]

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

Google Scholar ePrint

[QCH⁺20]

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

Google Scholar ePrint

[QCZZ21]

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

Google Scholar ePrint

[Sha85]

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

Google Scholar ePrint

[SOK00]

Ryuichi Sakai, Kiyoshi Ohgishi, and Masao Kasahara. Cryptosystems based on pairing. In Symposium on Cryptography and Information Security. 2000. Springer.

Google Scholar ePrint

[SSW09]

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

Google Scholar ePrint

[XWC⁺24]

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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a63z11zn4

History

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.

License

Copyright is held by the author(s)

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

@article{CiC-1-2-16,
    author = "Li, Qinyi and Boyen, Xavier",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Public-Key Authenticated Encryption with Keyword Search Made Easy",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a63z11zn4"
}

TY - JOUR
AU - Li, Qinyi
AU - Boyen, Xavier
PY  - 2024
TI  - Public-Key Authenticated Encryption with Keyword Search Made Easy
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 2
DO  - 10.62056/a63z11zn4
UR  - https://doi.org/10.62056/a63z11zn4
AB  - <p>    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. </p>
ER  -

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.