Privacy-preserving social graph search allows the retrieval of relationships within social networks while not com promising individuals' private information. Although numerous solutions enable conjunctive queries for relationships on encrypted social networks, the multi-client model is neglected despite its crucial role in collaborative data sharing, and personalized recommendations. In this paper, we present AuthGraph, a privacy-preserving and conjunctive social graph search system with trusted hardware in the multi-client (i.e., multi-writer/multi reader) model. In AuthGraph, a data owner delegates update rights to writers for maintaining dynamic social relationships, while readers are allowed to perform edge-weighted conjunctive queries via writer-enforced access policy. Technically, AuthGraph builds a multi-writer/multi-reader model with access control delegation for writers via a set-constrained pseudo-random function, and uses attribute-based encryption to configure authorizations for readers. To give a provably secure conjunctive search system over a dynamic social graph database, AuthGraph revisits oblivious dynamic cross tag protocol via providing comprehensive forward privacy and Type-O backward privacy. Different from previous solutions, in AuthGraph, the semi-black-box deployment of trusted hardware effectively ensures system security while maintaining performance. Finally, we demonstrate the performance of AuthGraph through extensive experiments on real social network datasets on AliCloud, revealing that the writer enforced access policy has minimal impact on search time cost.

Dynamic searchable symmetric encryption (DSSE) allows a client to update and retrieve its encrypted database stored on a server. To enable the database contributed by multi-writers to be searched by multi-readers, the multi-writer/multi-reader model is explored for DSSE (M/M-DSSE). Recently, FP-HSE (USENIX Security'22) and FP-MSE (TDSC'24) employed key aggregation methodology to introduce writer-selection property for M/M-DSSE, where a reader uses a single aggregate key to search the database containing selective writers. However, they neglected the reader-selection property where a writer selects which readers can search its data, and only supported single-keyword search. In this paper, we present BiMM, a conjunctive M/M-DSSE scheme with bilateral selection that simultaneously supports writer-selection and reader-selection properties. Additionally, BiMM achieves forward privacy (FP) for both server and client, and Type-O backward privacy (BP). Technically, we introduce a new primitive called bilateral key-aggregate encryption (Bi-KAE) that refines KAE via distributed key generation, by which both writers and readers can specify their selections. Based on ODXT (NDSS'21) that provides conjunctive queries while achieving FP with server and BP, we introduce double-blinded values to match all update records for the search keywords and additionally use the 0/1-Encoding technique to consider FP with client. Besides presenting formal security analysis for BiMM, we also conduct extensive experiments over public datasets on a real cloud server environment. The experiment results demonstrate that BiMM achieves practical performance for desired properties. With #keyword = 50 and #s-term = 10 for conjunctive queries, BiMM runs 6.34× faster than Nomos (AsiaCCS'24) which does not consider either writer-selection or reader-selection.

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$\mathcal {O}(n^{3})$to$\mathcal {O}(n^{2})$. 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\times $faster for conjunctive queries than JXT (with #keywords=2), which confirms rich features and practical efficiency.