Cloud storage services enable individuals and organizations to outsource data storage to remote servers. Cloud storage providers generally adopt data deduplication, a technique for eliminating redundant data by keeping only a single copy of a file, thus saving a considerable amount of storage and bandwidth. However, an attacker can abuse deduplication protocols to steal information. For example, an attacker can perform the duplicate check to verify whether a file (e.g., a pay slip, with a specific name and salary amount) is already stored (by someone else), hence breaching the user privacy. In this paper, we propose \mathsf{ZEUS}ZEUS (zero-knowledge deduplication response) framework. We develop \mathsf{ZEUS}ZEUS and \mathsf{ZEUS}ZEUS++, two privacy-aware deduplication protocols: \mathsf{ZEUS}ZEUS provides weaker privacy guarantees while being more efficient in the communication cost, while \mathsf{ZEUS}ZEUS++ guarantees stronger privacy properties, at an increased communication cost. To the best of our knowledge, \mathsf{ZEUS}ZEUS is the first solution which addresses two-side privacy by neither using any extra hardware nor depending on heuristically chosen parameters used by the existing solutions, thus reducing both cost and complexity of the cloud storage. In summary, through the evaluation on real datasets and comparison to existing solutions, our proposed framework demonstrates its capability of eliminating data deduplication-based side channel and at the same time keeping the deduplication benefits.