Cross pattern hiding structured encryption for conjunctive queries

Abstract

Structured encryption, a specialized form of searchable encryption, has been recognized for offering improved tradeoffs between performance, security, and expressiveness. It is designed to protect the privacy of cloud storage data and supports a variety of queries on the ciphertext database. The structured encryption scheme OXT, proposed in 2013, supports conjunctive queries of multi-keywords but was found to incur linear complexity in both token computation and search communication overheads. The ConjFilter scheme, more recently introduced, was aimed at decreasing the token overhead and reducing privacy leakage for structured encryption schemes that support Boolean queries. However, it was observed that this scheme resulted in cross-leakage between different queries. To address this issue, a transformed key encryption (TKE) scheme, based on random permutation and counter encryption modes was proposed. In essence, the TKE scheme was capable of converting ciphertext encrypted by one key into ciphertext encrypted by another key, without the need for decrypting the ciphertext at the serving side and without disclosing any information beyond the transformation modes. Utilizing this scheme, an encrypted multi-map scheme, transformable key filter (TK-Filter), was designed to support conjunctive queries. This scheme was reported to have nearly identical communication and storage overhead as the ConjFilter scheme but effectively prevented cross-leakage between different queries. Experimental analysis results show that TK-Filter reduces the initialization time by 58% to 86% and improves the search efficiency by 34% to 41% compared to ConjFilter across datasets of various sizes.

Keywords

• structured encryption
• conjunctive query
• cross leakage
• counter encryption mode