Synthetic backups are created without accessing previous backup data or retrieving backup data from a cloud storage service. A backup system provides two or more backup data sets to a cloud spanning storage interface for storage in deduplicated form as label maps and data segments in a cloud storage service. A specification defines portions of two or more previous backup data sets to be copied into the synthetic backup. Labels corresponding with the specified portions of previous backup data sets are identified and added to a new label map to create a deduplicated synthetic backup. The completed label map is transferred to the cloud storage service. To provide access to the synthetic backup, the cloud spanning storage interface reconstructs all or a portion of the synthetic backup from the new label map and the data segments created during deduplication of previous backup data sets.