Paper 2026/2945

Generic Construction of Public-key Encryption with Bidirectional Keyword Search

Riku Matsui, Kanazawa University
Keita Emura, Kanagawa University, National Institute of Advanced Industrial Science and Technology
Abstract

Public-key Encryption with Bidirectional Keyword Search (PEBKS), proposed by Zhang, Qin, Dong, and Tian (Computer Standards & Interfaces, 2021), extends the functionality of Public-key Encryption with Keyword Search (PEKS) by allowing not only the receiver but also the sender to generate trapdoors for keyword search. In this paper, we identify a close relationship between PEBKS and Public-key Authenticated Encryption with Keyword Search (PAEKS). Leveraging the generic construction of PAEKS proposed by Li and Boyen (IACR Communications in Cryptology, 2024), which is based on Non-Interactive Key Exchange (NIKE) and symmetric-key Equality Predicate Encryption (EPE), we show that PEBKS can also be generically constructed from the same building blocks. While Zhang et al. proposed a concrete pairing-based PEBKS scheme, our generic construction yields PEBKS instantiations under a wide range of cryptographic assumptions, including pairing-free Diffie-Hellman assumptions, lattices, isogenies, and codes. Furthermore, we define Key Collision Resistance for EPE as a new security property required for proving Consistency of PEBKS. We prove that the Li-Boyen EPE construction based on a pseudorandom function (PRF) achieves this property if the underlying PRF is Key Collision Resistant. We also discuss the use of AES and HMAC as the underlying PRF in light of the key collision attack reported by Taiyama et al. (Asiacrypt 2024). Since Key Collision Resistance is likewise required for proving Consistency of PAEKS, our result complements the Li-Boyen generic construction of PAEKS and is of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Searchable EncryptionBidirectional Keyword SearchGeneric ConstructionKey Collision Resistance
Contact author(s)
k-emura @ se kanazawa-u ac jp
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2945
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2945,
      author = {Riku Matsui and Keita Emura},
      title = {Generic Construction of Public-key Encryption with Bidirectional Keyword Search},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2945},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2945}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.