Ciphertext-Policy Attribute-Based Boolean Keyword Search with Negation for EHR Sharing

Abstract

The growing volume of electronic health records (EHRs) has made cloud-assisted storage increasingly important, but outsourced records require both encrypted storage and controlled retrieval. Attribute-based keyword searchable encryption (ABKS) combines search with fine-grained authorization; nevertheless, many existing constructions provide only restricted Boolean queries, particularly when negation is involved. This paper presents a ciphertext-policy ABKS search layer for EHR sharing. The proposed construction operates over a fixed application dictionary and assumes a non-colluding honest-but-curious cloud server. Each record is represented by one signed literal per dictionary term, where a positive literal denotes presence and a negated literal denotes absence. Before query evaluation, Boolean formulas involving AND, OR, and NOT are converted into negation normal form using De Morgan’s laws, so that NOT appears only at leaf nodes. The resulting query is then evaluated as a monotone threshold tree. An authorized user can generate a valid query token only when the user’s multi-valued attribute vector matches the policy selected by the data owner. Keyed pseudorandom tags hide literal and policy values from the cloud server while enabling efficient component lookup. We define a selective chosen-keyword security model, state the resulting leakage, and give a game-based proof under the decisional bilinear Diffie–Hellman and pseudorandom-function assumptions. Theoretical and implementation-based comparisons show that the pairing-dominant costs grow linearly with the attribute and dictionary sizes. The construction therefore improves Boolean expressiveness while retaining practical search-layer overhead under the stated assumptions.