Nowadays, an increasing number of companies choose to outsource their data applications to the cloud due to the high service availability and low operation cost. However, directly storing sensitive data on untrusted clouds may lead to serious privacy leakage. To protect data confidentiality, data is often encrypted before being outsourced to the cloud. Meanwhile, as the data size continues to increase, it is also important to compress the data stored in the cloud to improve system performance. Thus, both data encryption and compression are essential for outsourcing large-scale data to the cloud. However, it is a challenging task to combine data encryption with compression.

This dissertation presents algorithms and implementations for building secure and compressed data storage systems, aiming to gain the advantage of both encryption and compression. Firstly, we devise a privacy-preserving key-value store that considers both data compression and encryption, and formulate the problem of optimal compression for encrypted key-value stores, aiming to minimize the overall cost of data outsourcing. Secondly, we devise a K-indistinguishable frequency smoothing scheme for encrypted key-value stores, which can resist access pattern attacks launched by passive persistent adversaries with minimal storage and bandwidth overhead. Thirdly, we extend the idea of K-indistinguishable frequency smoothing to encrypted and compressed stores and propose an encrypted and compressed key-value storage system with pattern-analysis security. It can protect key-value stores from pattern-analysis attacks with bounded storage overhead and minimal bandwidth overhead. Fourthly, we propose a privacy-preserving and compression-based data deduplication system under the fog-cloud network, which supports lossless deduplication of similar data in the encrypted domain. It can reduce cloud storage overhead while providing high deduplication efficiency and strong data confidentiality. The security and performance of each proposed system are carefully analyzed and evaluated. We believe our proposed systems can shed light on how to efficiently combine data encryption and compression to improve system performance while protecting data security.