Cuckoo hashing serves as a fundamental technique in various privacy-enhancing cryptographic primitives, such as Private Information Retrieval, Symmetric Searchable Encryption, owing to its excellent performance. However, achieving space-efficient Cuckoo hashing that maintains fast insertion and query operations, while facilitating its applications with customized design, remains highly challenging. In this work, we propose a multi-segment permutation-based Cuckoo hashing (MS-PCH) that can be efficiently parallelized on multi-threaded platforms, followed by a strategy for further parallelization over the hashing within single segments (MH-MS-PCH). To demonstrate its practical utility, we then investigate its application on encrypted data search by constructing full-fledged Public Key (Authenticated) Encryption with Keyword Search schemes (PCH(-MD)-PEKS and PCH(-MD)-PAEKS). We evaluate the performance of these schemes on a public dataset, showing that, with 16 segments and 4 hash functions, both PCH(-MD)-PEKS and PCH(-MD)-PAEKS outperforms the plain PEKS and PAEKS across index generation, query, and update. Notably, our optimized Cuckoo hashing achieves up to a 10 times improvement over plain cuckoo hashing, and our enhanced P(A)EKS schemes demonstrate approximately a 6 times improvement in index generation efficiency and a 335 times acceleration in query processing.

Searchable symmetric encryption (SSE) enables keyword search over encrypted data but inevitably leaks patterns that adversaries can exploit to infer sensitive information. Differential privacy (DP) has been adopted to mitigate such leakages efficiently, yet existing DP-enhanced schemes are limited to single-user settings, lacking support for multi-user data sharing under diverse privacy needs. In such settings, distinct encryption keys and heterogeneous privacy levels raise two critical challenges: (i) leakage amplification, a prevalent yet under-explored threat where adversaries infer keywords from low-privacy data and link them to high-privacy data in cross-user retrieval; and (ii) inefficient privilege management, where cross-user search requires cumbersome key transmissions and frequent updates due to changing privileges. To bridge these challenges, we propose DPE-MUSE, a DP-Enhanced Multi-User Searchable Encryption scheme that achieves secure mutual retrieval while hiding access and size patterns. At its core is an adaptive keyword-level budget allocation strategy that derives budgets from data distributions and mitigates cross-user inference. A unified key management strategy further eliminates direct key sharing and streamlines privilege updates. Experiments on the Enron dataset show that DPE-MUSE achieves high recall (98.96%) under strict privacy requirements with relative low overhead, requiring only 58.951 ms for budget computation on a dataset of size 214.