The distributed nature of local differential privacy (LDP) invites data poisoning attacks and poses unforeseen threats to the underlying LDP-supported applications. In this paper, we propose a comprehensive mitigation framework for popular frequency estimation, which contains a suite of novel defenses, including malicious user detection, attack pattern recognition, and damaged utility recovery. In addition to existing attacks, we explore new adaptive adversarial activities for our mitigation design. For detection, we present a new method to precisely identify bogus reports, and thus LDP aggregation can be performed over the ''clean'' data. When the attack behavior becomes stealthy and direct filtering out malicious users is difficult, we further propose a detection that can effectively recognize hidden adversarial patterns, thus facilitating the decision-making of service providers. These detection methods require no additional data or attack information and incur minimal computational cost. Our experiment demonstrates their excellent performance and substantial improvement over previous work in various settings. In addition, we conduct an empirical analysis of LDP post-processing for corrupted data recovery and propose a new post-processing method, through which we reveal new insights into protocol recommendations in practice and key design principles for future research.

Opening up data produced by the Internet of Things (IoT) and mobile devices for public utilization can maximize their economic value. Challenges remain in the trustworthiness of the data sources and the security of the trading process, particularly when there is no trust between the data providers and consumers. In this article, we propose DEXO, a decentralized data exchange mechanism that facilitates secure and fair data exchange between data consumers and distributed IoT/mobile data providers at scale, allowing the consumer to verify the data generation process and the providers to be compensated for providing authentic data, with correctness guarantees from the exchange platform. To realize this, DEXO extends the decentralized oracle network model that has been successful in the blockchain applications domain to incorporate novel hardware-cryptographic co-design that harmonizes trusted execution environment, secret sharing, and smart contract-assisted fair exchange. For the first time, DEXO ensures end-to-end data confidentiality, source verifiability, and fairness of the exchange process with strong resilience against participant collusion. We implemented a prototype of the DEXO system to demonstrate feasibility. The evaluation shows a moderate deployment cost and significantly improved blockchain operation efficiency compared to a popular data exchange mechanism.

The Execute-Order-Validate blockchain enhances performance by allowing parallel transaction execution, yet it also introduces transaction conflicts that can cause state inconsistencies in the ledger. Previous research has focused on resolving conflicts under the assumption of the “good” intent of the senders. In this paper, we explore an unstudied scenario where a malicious user can intentionally generate transaction collisions to disrupt the service request of a target user to the underlying decentralized application (DApp). We call it manipulated transaction collision (MTC) attack. We overcome the challenges of identifying the conditions and best strategies to launch this targeted attack under various network settings. Our experiment results show that the MTC attack can effectively cause the victim to be continuously rejected by the blockchain, i.e., over 90% success rate in all tested cases on the Hyperledger Fabric blockchain. To combat this new threat, we first propose a machine-learning-assisted detection method that helps identify the adversarial behavior within massive background traffic. To further enhance blockchain resilience, we propose a more precise transaction conflicts definition and present a novel mitigation method, which not only prevents the attack but also significantly reduces the probability of natural conflicts by up to 75% in the tested DApp compared to state-of-the-art optimization methods.

Random numbers play a crucial role in decen-tralized applications (dApps) like decentralized finance (DeFi) and non-fungible tokens (NFTs). However, their generation faces challenges due to blolckchain's deterministic and decentralized nature, risking smart contract security and ecosystem stability. Prior solutions, including Oracles, employing commit-execute schemes, suffer from higher transaction fees, extended processing times, and increased on-chain storage, compromising efficiency. This paper proposes a novel random number provider (RNP) protocol for smart contracts, eliminating dependencies on traditional commit-execute approaches. Furthermore, we systematically identify potential random number-related attacks on smart contracts, particularly Post-reveal Undo Attacks (PUAs), where attackers may reverse contract operations when randomness is unfavorable, and discuss the security requirements. Our protocol addresses these attacks by (1) incorporating distributed random beacons (D RBs) with consensus processes, bridging the semantic gap between DRB and consensus, and (2) thoroughly analyzing and classifying four types of PUA and offering robust mitigations, alongside presenting a security proof. Our experiments show the protocol significantly enhances response times and security for random number queries in smart contracts, slashing request fees by at least 89 % and reducing on-chain data by 76.4% versus current methods. This work advances the integration of DRB protocols and consensus mechanisms, securing and optimizing random number applications in dApps, thus fostering the creation of more dependable, robust systems.

Deep learning side-channel attacks can recover encryption keys on a target by analyzing power consumption or electromagnetic (EM) signals. However, they are less portable when there are domain shifts between training and test data. While existing studies have shown that pre-processing and unsupervised domain adaptation can enhance the portability of deep learning side-channel attacks given domain shifts over EM traces, the findings are limited to easy targets (e.g. 8-bit microcontrollers).

Smart meter-based individual load forecasts are more and more widely deployed to serve smart grid and home energy management. Customary load forecasting systems collect a massive amount of fine-grained electrical data from people’s smart meters in plaintext, inevitably raising privacy concerns and even anti-smart-meter initiatives. Current privacy solutions either compromise accuracy and efficacy or require the redeployment of trusted infrastructure. In this paper, we present PrivGrid, the first systematic solution for smart grids that collects, clusters, trains, and forecasts customers’ load data in a privacy-preserving way. Moreover, we highlight the technical contribution of our building block: a novel and fast arithmetic multiplication triple via secure inner product protocol outperforms the existing methods and may be included in other privacy computing modules. Then, we develop efficient secure protocols to enable the arithmetic operations of individual load forecasting in a server-aided model and utilize the best alternatives to nonlinear functions. Besides, aggregating all of our individual forecasts can produce a more accurate estimate of the system-level load than the typical aggregate technique. We rigorously prove that the servers cannot obtain the user’s historical load data and short-term load forecast values while providing services. PrivGrid is also tested on real residential smart meter data to show its efficiency, and the relevant code has been made available to the community for further research.

Online syndicated lending offers quick and convenient financing support to individuals, while diversifying risks by pooling funds from multiple lenders into loan projects. It has experienced explosive growth, reaching a multibillion-dollar market. Establishing transparency is essential for constructing a trusted, fair, and regulation-compliant financial collaboration model. Meanwhile, confidentiality must be maintained to protect the sensitive financial information of individual lenders. Multi-party computation (MPC) can protect the input privacy of lenders, but it cannot safeguard the sensitive information revealed by the fund flow itself. To address these challenges, we propose a new collaborative financial ledger for online syndicated lending. It leverages homomorphic encryption/commitment to enable the reuse of intermediary states without compromising privacy throughout the entire lifecycle of a loan. This system also supports efficient regulation-compliant auditing. We streamline the framework design to optimize performance and develop a prototype system. Even with a large syndicate of 100 lenders, the system still achieves low-latency performance.

Despite the promising performance of deep reinforcement learning (DRL) agents in many challenging scenarios, the black-box nature of these agents greatly limits their applications in critical domains. Prior research has proposed several explanation techniques to understand the deep learning-based policies in RL. Most existing methods explain why an agent takes individual actions rather than pinpointing the critical steps to its final reward. To fill this gap, we propose StateMask, a novel method to identify the states most critical to the agent's final reward. The high-level idea of StateMask is to learn a mask net that blinds a target agent and forces it to take random actions at some steps without compromising the agent's performance. Through careful design, we can theoretically ensure that the masked agent performs similarly to the original agent. We evaluate StateMask in various popular RL environments and show its superiority over existing explainers in explanation fidelity. We also show that StateMask has better utilities, such as launching adversarial attacks and patching policy errors.

Model poisoning attacks greatly jeopardize the application of federated learning (FL). The effectiveness of existing defenses is susceptible to the latest model poisoning attacks, leading to a decrease in prediction accuracy. Besides, these defenses are intractable to distinguish benign outliers from malicious gradients, which further compromises the model generalization. In this work, we propose a novel defense including detection and aggregation, named RECESS, to serve as a “vaccine” for FL against model poisoning attacks. Different from the passive analysis in previous defenses, RECESS proactively queries each participating client with a delicately constructed aggregation gradient, accompanied by the detection of malicious clients according to their responses with higher accuracy. Further, RECESS adopts a newly proposed trust scoring based mechanism to robustly aggregate gradients. Rather than previous methods of scoring in each iteration, RECESS takes into account the correlation of clients’ performance over multiple iterations to estimate the trust score, bringing in a significant increase in detection fault tolerance. Finally, we extensively evaluate RECESS on typical model architectures and four datasets under various settings including white/black-box, cross-silo/device FL, etc. Experimental results show the superiority of RECESS in terms of reducing accuracy loss caused by the latest model poisoning attacks over five classic and two state-of-the-art defenses.

At-home screening systems for obstructive sleep apnea (OSA) can bring convenience to remote chronic disease management. However, the unsupervised home environment is subject to spoofing and unintentional interference from the household member. To improve robustness, this work presents SIENNA, an insider-resistant breathing-based authentication/pairing protocol. SIENNA leverages the uniqueness of breathing patterns to automatically and continuously authenticate a user and pairs a mobile OSA app and a physiological monitoring radar system (PRMS). SIENNA does not require biometric enrollment and instead transforms the respiratory measurements taken during the users routine physical checkup into breathing biometrics comparable with the PRMS readings. Furthermore, it can operate within a noisy multi-target home environment and is secure against a co-located attacker through the usage of JADE-ICA, fuzzy commitment, and friendly jamming. We fully implemented SIENNA and evaluated its performance with medium-scale trials. Results show that SIENNA can achieve reliable (> 90% success rate) user authentication and secure device pairing in a noisy environment against an attacker with full knowledge of the authorized users breathing biometrics.

The equation-solving model extraction attack is an intuitively simple but devastating attack to steal confidential information of regression models through a sufficient number of queries. Complete mitigation is difficult. Thus, the development of countermeasures is focused on degrading the attack effectiveness as much as possible without losing the model utilities. We investigate a novel personalized local differential privacy mechanism to defend against the attack. We obfuscate the model by adding high-dimensional Gaussian noise on model coefficients. Our solution can adaptively produce the noise to protect the model on the fly. We thoroughly evaluate the performance of our mechanisms using real-world datasets. The experiment shows that the proposed scheme outperforms the existing differential-privacy-enabled solution, i.e., 4 times more queries are required to achieve the same attack result. We also plan to publish the relevant codes to the community for further research.

State channel network is the most popular layer-2 solution to the issues of scalability, high transaction fees, and low transaction throughput of public Blockchain networks. However, the existing works have limitations that curb the wide adoption of the technology, such as the expensive creation and closure of channels, strict synchronization between the main chain and off-chain channels, frozen deposits, and inability to execute multi-party smart contracts. In this work, we present Speedster, an account-based state-channel system that aims to address the above issues. To this end, Speedster leverages the latest development of secure hardware to create dispute-free certified channels that can be operated efficiently off the Blockchain. Speedster is peer-to-peer decentralized and provides better privacy protection than prior channel projects. It supports fast native multi-party contract execution, which is previously unavailable in TEE-enabled channel networks. Compared to the Lightning Network, Speedster improves the throughput by about 10,000X and generates 97%$ less on-chain data with a comparable network scale.

Website fingerprinting can reveal which sensitive website a user visits over encrypted network traffic. Obfuscating encrypted traffic, e.g., adding dummy packets, is considered as a primary approach to defend against website fingerprinting. How-ever, existing defenses relying on traffic obfuscation are either ineffective or introduce significant overheads. As recent website fingerprinting attacks heavily rely on deep neural networks to achieve high accuracy, producing adversarial examples could be utilized as a new way to obfuscate encrypted traffic. Unfortunately, existing adversarial example algorithms are designed for images and do not consider unique challenges for network traffic.In this paper, we design a new method, named AdvTraffic, which can customize perturbations produced by any existing adversarial example algorithm on images and derive adversarial examples over encrypted traffic. Our experimental results show that the integration of AdvTraffic, particularly with Generative Adversarial Networks, can effectively mitigate the accuracy of website fingerprinting from 95.0% to 10.2%, even if an attacker retrains a classifier with defended traffic. Compared to other defenses, our method outperforms most of them in mitigating attack accuracy and offers the lowest bandwidth overhead.

Privacy concerns of using sensitive biometric data as credentials arise with the wide adoption of user-friendly face authentication. To protect the facial features of users, two important functions, i.e.,revocabilityandreusability, are anticipated to be realized in a privacy-preserving face authentication design. Revocability requires an effective approach to deregister or replace user credentials when the authentication server is compromised; For reusability, the same credentials should appear independently to non-cooperating applications. Accomplishing these two properties is challenging as the uniqueness of facial features. In this article, we presentPrivFace, a fast privacy-preserving face authentication, supporting revocable, and reusable biometric credentials. The core innovation is a novel secure inner product protocol that employs a lightweight random masking technique instead of time-consuming public-key cryptographic operations to efficiently measure facial data similarity. We rigorously analyze the security to show that the server cannot acquire the user's sensitive biological features during the authentication. Our experiment with real-world datasets shows thatPrivFaceis friendly to edge smart devices, which takes less than$100 ms$per successful authentication on a common smartphone and outperforms the prior art J. Lei, Q. Peiet al.[1]. by$20 \times$. We have made the relevant codes open-source to the community for further research.

Public intelligent services enabled by machine learning algorithms are vulnerable to model extraction attacks that can steal confidential information of the learning models through public queries. Though there are some protection options such as differential privacy (DP) and monitoring, which are considered promising techniques to mitigate this attack, we still find that the vulnerability persists. In this article, we propose an adaptivequery-flooding parameter duplication(QPD) attack. The adversary can infer the model information with black-box access and no prior knowledge of any model parameters or training data via QPD. We also develop a defense strategy using DP called monitoring-based DP (MDP) against this new attack. In MDP, we first propose a novel real-timemodel extraction status assessmentscheme calledMonitorto evaluate the situation of the model. Then, we design a method to guide the differential privacy budget allocation called APBA adaptively. Finally, all DP-based defenses with MDP could dynamically adjust the amount of noise added in the model response according to the result fromMonitorand effectively defends the QPD attack. Furthermore, we thoroughly evaluate and compare the QPD attack and MDP defense performance on real-world models with DP and monitoring protection.

The increasingly sophisticated at-home screening systems for obstructive sleep apnea (OSA), integrated with both contactless and contact-based sensing modalities, bring convenience and reliability to remote chronic disease management. However, the device pairing processes between system components are vulnerable to wireless exploitation from a non-compliant user wishing to manipulate the test results. This work presents SIENNA, an insider-resistant context-based pairing protocol. SIENNA leverages JADE-ICA to uniquely identify a user's respiration pattern within a multi-person environment and fuzzy commitment for automatic device pairing, while using friendly jamming technique to prevent an insider with knowledge of respiration patterns from acquiring the pairing key. Our analysis and test results show that SIENNA can achieve reliable (> 90% success rate) device pairing under a noisy environment and is robust against the attacker with full knowledge of the context information.

This paper investigates the privacy leakage of smart speakers under an encrypted traffic analysis attack, referred to as voice command fingerprinting. In this attack, an adversary can eavesdrop both outgoing and incoming encrypted voice traffic of a smart speaker, and infers which voice command a user says over encrypted traffic. We first built an automatic voice traffic collection tool and collected two large-scale datasets on two smart speakers, Amazon Echo and Google Home. Then, we implemented proof-of-concept attacks by leveraging deep learning. Our experimental results over the two datasets indicate disturbing privacy concerns. Specifically, compared to 1% accuracy with random guess, our attacks can correctly infer voice commands over encrypted traffic with 92.89% accuracy on Amazon Echo.

As an important application of the Internet of Things, many remote monitoring systems adopt a device-to-cloud network paradigm. In a remote patient monitoring case, various resource-constrained devices are used to measure the health conditions of a target patient in a distant non-clinical environment and the collected data are sent to the cloud backend of an authorized health care service for processing and decision making. As the measurements involve private patient information, access control and trustworthy processing of the confidential data become very important. Software-based solutions that adopt advanced cryptographic tools, such as attribute-based encryption and fully homomorphic encryption, can address the problem, but they also impose substantial computation overhead on both client and server sides. In this paper, we deviate from the conventional software-based solutions and propose a secure and efficient remote monitoring framework, called SRM, using the latest hardware-based trustworthy computing technology, such as Intel SGX. In addition, we present a robust and lightweight “heartbeat” protocol to handle notoriously difficult key revocation problem. We implemented a prototype of the framework for SRM and show that SRM can protect user data privacy against unauthorized parties, with minimum performance cost compared to existing software-based solutions.

Search over encrypted data (SE) enables a client to delegate his search task to a third-party server that hosts a collection of encrypted documents while still guaranteeing some measure of query privacy. Software-based solutions using diverse cryptographic primitives have been extensively explored, leading to a rich set of secure search indexes and algorithm designs. However, each scheme can only implement a small subset of information retrieval (IR) functions and often with considerable search information leaked. Recently, the hardware-based secure execution has emerged as an effective mechanism to securely execute programs in an untrusted software environment. In this paper, we exploit the hardware-based execution environment (TEE) and explore a software and hardware combined approach to address the challenging secure search problem. For functionality, our design can support the same spectrum of plaintext IR functions. For security, we present oblivious keyword search techniques to mitigate the index search trace leakage. We build a prototype of the system using Intel SGX. We demonstrate that the proposed system provides broad support of a variety of search functions and achieves computation efficiency comparable to plaintext data search with elevated security protection.

In this paper, we investigate the problem of integrity auditing for cloud deduplication storage. Specifically, in addition to the outsourced data confidentiality, we also aim to ensure the integrity of the deduplicated cloud storage. With the existing works based on Provable Data Possession (PDP)/Proof of Retrievability (PoR), we are either required to rely on a fully trusted proxy server or inevitably sacrifice the privacy and efficiency. In contrast, we present a novel message-locked integrity auditing scheme without an additional proxy server, which is applicable to both file-level and chunk-level deduplication systems. In particular, our scheme is storage efficient in the sense that apart from eliminating the ciphertext redundancy, we also enable the integrity tag deduplication by a message-derived signing key, which merely incurs minimal client-side computation overhead. Besides, we can still publicly perform the integrity check over any client's cloud storage by incorporating the proxy re-signature technique. We show that the proposed scheme will not disclose the data ownership information and is provably secure under the Computational Diffie-Hellman (CDH) assumption in the random oracle model. Finally, the performance evaluation demonstrates its effectiveness and efficiency.

As the cost of human full genome sequencing continues to fall, we will soon witness a prodigious amount of human genomic data in the public cloud. To protect the confidentiality of the genetic information of individuals, the data has to be encrypted at rest. On the other hand, encryption severely hinders the use of this valuable information, such as Genome-wide Range Query (GRQ), in medical/genomic research. While the problem of secure range query on outsourced encrypted data has been extensively studied, the current schemes are far from practical deployment in terms of efficiency and scalability due to the data volume in human genome sequencing. In this paper, we investigate the problem of secure GRQ over human raw aligned genomic data in a third-party outsourcing model. Our solution contains a novel secure range query scheme based on multi-keyword symmetric searchable encryption (MSSE). The proposed scheme incurs minimal ciphertext expansion and computation overhead. We also present a hierarchical GRQ-oriented secure index structure tailored for efficient and large-scale genomic data lookup in the cloud while preserving the query privacy. Our experiment on real human genomic data shows that a secure GRQ request with range size 100,000 over more than 300 million encrypted short reads takes less than 3 minutes, which is orders of magnitude faster than existing solutions.

Uploading data streams to a resource-rich cloud server for inner product evaluation, an essential building block in many popular stream applications (e.g., statistical monitoring), is appealing to many companies and individuals. On the other hand, verifying the result of the remote computation plays a crucial role in addressing the issue of trust. Since the outsourced data collection likely comes from multiple data sources, it is desired for the system to be able to pinpoint the originator of errors by allotting each data source a unique secret key, which requires the inner product verification to be performed under any two parties' different keys. However, the present solutions either depend on a single key assumption or powerful yet practically-inefficient fully homomorphic cryptosystems. In this paper, we focus on the more challenging multi-key scenario where data streams are uploaded by multiple data sources with distinct keys. We first present a novel homomorphic verifiable tag technique to publicly verify the outsourced inner product computation on the dynamic data streams, and then extend it to support the verification of matrix product computation. We prove the security of our scheme in the random oracle model. Moreover, the experimental result also shows the practicability of our design.

Search over encrypted data is a critically important enabling technique in cloud computing, where encryption-before-outsourcing is a fundamental solution to protecting user data privacy in the untrusted cloud server environment. Many secure search schemes have been focusing on the single-contributor scenario, where the outsourced dataset or the secure searchable index of the dataset are encrypted and managed by a single owner, typically based on symmetric cryptography. In this paper, we focus on a different yet more challenging scenario where the outsourced dataset can be contributed from multiple owners and are searchable by multiple users, i.e., multi-user multi-contributor case. Inspired by attribute-based encryption (ABE), we present the first attribute-based keyword search scheme with efficient user revocation (ABKS-UR) that enables scalable fine-grained (i.e., file-level) search authorization. Our scheme allows multiple owners to encrypt and outsource their data to the cloud server independently. Users can generate their own search capabilities without relying on an always online trusted authority. Fine-grained search authorization is also implemented by the owner-enforced access policy on the index of each file. Further, by incorporating proxy re-encryption and lazy re-encryption techniques, we are able to delegate heavy system update workload during user revocation to the resourceful semi-trusted cloud server. We formalize the security definition and prove the proposed ABKS-UR scheme selectively secure against chosen-keyword attack. To build confidence of data user in the proposed secure search system, we also design a search result verification scheme. Finally, performance evaluation shows the efficiency of our scheme.

Encrypted data search allows cloud to offer fundamental information retrieval service to its users in a privacy-preserving way. In most existing schemes, search result is returned by a semi-trusted server and usually considered authentic. However, in practice, the server may malfunction or even be malicious itself. Therefore, users need a result verification mechanism to detect the potential misbehavior in this computation outsourcing model and rebuild their confidence in the whole search process. On the other hand, cloud typically hosts large outsourced data of users in its storage. The verification cost should be efficient enough for practical use, i.e., it only depends on the corresponding search operation, regardless of the file collection size. In this paper, we are among the first to investigate the efficient search result verification problem and propose an encrypted data search scheme that enables users to conduct secure conjunctive keyword search, update the outsourced file collection and verify the authenticity of the search result efficiently. The proposed verification mechanism is efficient and flexible, which can be either delegated to a public trusted authority (TA) or be executed privately by data users. We formally prove the universally composable (UC) security of our scheme. Experimental result shows its practical efficiency even with a large dataset.

Search over encrypted data is a critically important enabling technique in cloud computing, where encryption-before-outsourcing is a fundamental solution to protecting user data privacy in the untrusted cloud server environment. Many secure search schemes have been focusing on the single-contributor scenario, where the outsourced dataset or the secure searchable index of the dataset are encrypted and managed by a single owner, typically based on symmetric cryptography. In this paper, we focus on a different yet more challenging scenario where the outsourced dataset can be contributed from multiple owners and are searchable by multiple users, i.e. multi-user multi-contributor case. Inspired by attribute-based encryption (ABE), we present the first attribute-based keyword search scheme with efficient user revocation (ABKS-UR) that enables scalable fine-grained (i.e. file-level) search authorization. Our scheme allows multiple owners to encrypt and outsource their data to the cloud server independently. Users can generate their own search capabilities without relying on an always online trusted authority. Fine-grained search authorization is also implemented by the owner-enforced access policy on the index of each file. Further, by incorporating proxy re-encryption and lazy re-encryption techniques, we are able to delegate heavy system update workload during user revocation to the resourceful semi-trusted cloud server. We formalize the security definition and prove the proposed ABKS-UR scheme selectively secure against chosen-keyword attack. Finally, performance evaluation shows the efficiency of our scheme.

With the growing popularity of cloud computing, huge amount of documents are outsourced to the cloud for reduced management cost and ease of access. Although encryption helps protecting user data confidentiality, it leaves the well-functioning yet practically-efficient secure search functions over encrypted data a challenging problem. In this paper, we present a verifiable privacy-preserving multi-keyword text search (MTS) scheme with similarity-based ranking to address this problem. To support multi-keyword search and search result ranking, we propose to build the search index based on term frequency- and the vector space model with cosine similarity measure to achieve higher search result accuracy. To improve the search efficiency, we propose a tree-based index structure and various adaptive methods for multi-dimensional (MD) algorithm so that the practical search efficiency is much better than that of linear search. To further enhance the search privacy, we propose two secure index schemes to meet the stringent privacy requirements under strong threat models, i.e., known ciphertext model and known background model. In addition, we devise a scheme upon the proposed index tree structure to enable authenticity check over the returned search results. Finally, we demonstrate the effectiveness and efficiency of the proposed schemes through extensive experimental evaluation.

With the increasing popularity of cloud computing, huge amount of documents are outsourced to the cloud for reduced management cost and ease of access. Although encryption helps protecting user data confidentiality, it leaves the well-functioning yet practically-efficient secure search functions over encrypted data a challenging problem. In this paper, we present a privacy-preserving multi-keyword text search (MTS) scheme with similarity-based ranking to address this problem. To support multi-keyword search and search result ranking, we propose to build the search index based on term frequency and the vector space model with cosine similarity measure to achieve higher search result accuracy. To improve the search efficiency, we propose a tree-based index structure and various adaption methods for multi-dimensional (MD) algorithm so that the practical search efficiency is much better than that of linear search. To further enhance the search privacy, we propose two secure index schemes to meet the stringent privacy requirements under strong threat models, i.e., known ciphertext model and known background model. Finally, we demonstrate the effectiveness and efficiency of the proposed schemes through extensive experimental evaluation.