Cloud storage service providers apply data client-side deduplication across multiple users to achieve cost savings of network bandwidth and disk storage. However, deduplication can be used as a side channel by attackers who try to obtain sensitive information of other users' data. We propose a differentially private client-side deduplication protocol. A storage gateway allows efficient data deduplication while reducing the risk of information leakage. Its security can be strongly guaranteed according to the definition of differential privacy. We evaluate the effectiveness and efficiency of the proposed protocol through experiments.