Input backup data is deduplicated with data of a synthetic backup previously constructed by a deduplication storage. A synthetic backup is constructed by processing metadata instructions provided by a backup application. Deduplication digests are calculated based on the data of the synthetic backup and the deduplication digests are stored in a digests index. When new backup data is processed, deduplication digests of the new data are calculated and searched in the digests index. A data segment of the synthetic backup is partitioned into fixed sized sub-segments. The calculated digests of sub-segment are aggregated to produce the deduplication digest, and the deduplication digest is formed for the synthetic backup.