Practical Searchable Symmetric Encryption for Arbitrary Boolean Query-Join in Cloud Storage

Secure cloud storage offers encrypted databases outsourcing service for resource-constrained clients, containing numerous tables with certain relations. Searchable symmetric encryption enables a client to search over its encrypted database on the cloud, while rarely considering queries over joins of tables. Join Cross-Tags (JXT) protocol (ASIACRYPT 2022) is thence presented that enables conjunctive queries over joins of tables, while neglecting arbitrary Boolean queries with disjunctive and conjunctive normal forms (DNF/CNF) in TWINSSE (PETS 2023). However, trivially combining JXT and TWINSSE for arbitrary DNF/CNF boolean queries over joins of tables seems infeasible due to: (i) no support for dis/conjunctive query with the same meta-keyword; (ii) returning inaccurate search results; (iii) incurring costly storage overhead. Therefore, we introduce TNT-QJ, a practical TwiN cross-Tag protocol for arbitrary boolean Query-Join over multi-tables. The result is technically obtained from revisiting TWINSSE's framework via using s-term (the least frequent keyword) for the relation between a keyword and its meta-keyword, and non-trivially combined with JXT's query-join approach for introducing a connective attributed in encryption tuples. In addition, we present a semi-full multi-fork searchable tree to store keyword information and reveal keyword containment relations, where the storage consumption is reduced from O(n³) to O(n²). Finally, to clarify practical performance, we conduct extensive experiments on JXT and TNT-QJ using an open database in the HUAWEI cloud. Besides enabling disjunctive queries over joins of tables, TNT-QJ also runs 1.2× faster for conjunctive queries than JXT (with #keywords=2), which confirms rich features and practical efficiency.