Encryption and compression are two critical techniques to ensure data confidentiality and efficiency for a cloud-based data storage system, respectively. However, directly combing encryption and compression incurs substantial performance degradation. We propose TinyEnc, an encrypted data storage system for cloud-based key-value store. TinyEnc supports encryption and compression simultaneously with rich query support.To reconcile encryption and compression without compromising performance, we propose a new encrypted compression data structure to enable fine-grained access to compressed and encrypted key-value data. We then propose two new transforming mechanisms, namely orthogonal data dividing and hierarchical data padding, to transform a plaintext key-value table into the encrypted compression data structure in a privacy-preserving way. Finally, we craft order-revealing encryption (ORE) and symmetric searchable encryption (SSE) to design a new encrypted search index over the encrypted compression data structure to support rich types of data queries. We implement a prototype of TinyEnc on top of Cassandra. Our evaluation shows that TinyEnc increases the throughput by up to 7 times and compression ratio by up to 1.3 times with respect to previous works.

The primitive of verifiable data streaming (VDS) provides a secure data outsourcing solution for resource-constrained users, that is, they can stream their continuously-generated data items to untrusted servers while enabling publicly verifiable query and update. However, existing VDS schemes either require the server to store the authentication tags of all data items to support data query and auditing, or bind all data items into a constant-size tag to achieve optimal storage on the server side, but cannot achieve public auditing. To close this gap, in this paper, we first design a novel authentication data structure, dubbed retrievable homomorphic verifiable tags (RHVTs), which allows users to aggregate the authentication tags of all data items into a constant-size tag, and enables them to retrieve the original tags from the aggregated tag when necessary. Based on this, we propose a compact verifiable and auditable data streaming (CVADS) scheme, which adopts a single-level authentication mechanism to achieve more efficient data append and update, as well as optimal storage and public auditing. For better robustness and performance, we introduce a nested dual-level authentication mechanism and propose a blockchain-based CVADS (BCVADS) scheme to achieve a distributed CVADS with self-auditing. Finally, we prove the security of our schemes in the random oracle model and demonstrate their practicality through a visual performance evaluation.