Message-locked Encryption (MLE) is the most common approach used in encrypted deduplication systems. However, the systems based on MLE are vulnerable to frequency analysis attacks, because MLE encrypts the identical plaintexts into the identical ciphertexts, which is deterministic. The state-of-theart defense scheme, which named TED, lacks key verification and uses a single key server to record frequency information. Once the key server is compromised, TED will be vulnerable to brute-force attacks. In addition, TED’s key generation algorithm needs to be designed more exquisitely to strengthen protection, and its security indicator is not comprehensive. We propose SDAF, which supports key verification and enhanced protection against frequency analysis attacks. Based on chameleon hash, SDAF realizes key verification to prevent malicious key servers from generating fake encryption keys. In order to disturb the frequency information, SDAF introduces reservoir sample to generate uniformly distributed encryption keys, and uses multiple key servers, which interact with each other via multi-party PSI and rotate spontaneously to avoid the single point of failure. Moreover, a new indicator Kurtosis is pointed out to evaluate the security against frequency analysis attacks. We implement the prototypes of SDAF. The experiments of the real-world data sets show that, compared with the existing schemes, SDAF can better resist frequency analysis attacks with lower time overheads.