Outsourcing storage to the cloud can save storage costs and is commonly used in businesses. It should fulfill two major goals: storage efficiency and data confidentiality. Encrypted deduplication can achieve both goals via performing deduplication to eliminate the duplicate data within encrypted data. Traditional encrypted deduplication generates the encryption key on the client side, which poses a risk of offline brute-force cracking of the outsourced data. Server-aided encryption schemes have been proposed to strengthen the confidentiality of encrypted deduplication by distributing the encryption process to dedicated servers. Existing schemes rely on expensive cryptographic primitives to provide a decentralized setting on the dedicated servers for scalability. However, this incurs substantial performance slowdown and can not be applied in practical encrypted deduplication storage systems. In this paper, we propose a new decentralized server-aided encrypted deduplication approach for outsourced storage, called ECDedup, which leverages secret sharing to achieve secure and efficient key management. We are the first to use the coding matrix as the encryption key to couple the encryption and encoding processes in encrypted deduplication. We also propose a acceleration scheme to speed up the encryption process of our ECDedup. We prototype ECDedup in cloud environments, and our experimental results based on the real-world backup datasets show that ECDedup can improve the client throughput by up to 51.9% compared to the state-of-the-art encrypted deduplication schemes.